Excerpt
2. Nubraižyti kontaktines schemas: a). "(pL4) => CpAU, | ») ((((p=29)VIP)84)v 14), e) (p2312(4> p), a). ((p24) K (22-)= (pa, ) (p24)> Gp le Va), : 3. Įkelti neiginį į skliaustus: a) Tipvia žm), 5) T1(PR(GV Op V(p ip, e) T(0PV14) L (gv i(paz), d) 1 (Gpv …
Excerpt
37 b) Nepirminiai skaičiai yra sudėtiniai. Skaičiai, dalūs iš 2, yra sudėtiniai šitai šiai, dailūs iš 5, taip pat yra su- dėtiniai. Vadinasi, skaičiai dalūa iš 2, yra dalūs ir …
Excerpt
38 M elementas. Tačiau aibę M |adaro tik antrosios grupės aibės. Prieštaravimas rodo, kad šio spėjimo turime atsisaky- ti. Vadinasi, aibė M yra antrosios grupės ir nėra savo pa- čios elementas. Bet ir to negali būti: juk M yra visų an- trosios grupės …
Excerpt
39 Dvi logikos algebros funkcijos vadinamos lygiomis, jei- gu jas alitinkšnoiks lentelės yra lygios. n argumentų logi- kos algebros funkcijų skaičius yra lygus 2 * „ Tai labai greitai auganti funkcija. Vieno argumento logikos algebros funkcijų yra 4, …
Excerpt
40 Iš tikrųjų, jeigu, esant reikšmėms < Bs.---, Pn? funkcija lygi 1, tai tos reikšmės sutampa su S reikšmių sekos nariu, ir formulė įgyja 1 reikšmę, nea £! af tada ir tik tada, kai 4=B . Jeigu f(P4,.-,Bn)]=0 bad …
Excerpt
41 X X XtX, 2751 0 NS Jao 1 0-2 il: 0. 0 0 „Taigi neiginys bei konjunkcija yra duotos aibės su-' perpozicija. Pastebėsime, kad *, A 3 Formulėje, ; kurią įeina tik konstantos 0, 1 ir funkci- jos X,X, bei X tr „ atlikę algebrinius-perdirbimus, gaus: 'name …
Excerpt
Išsprendę sistemą art+C+4=i Lid=i c+4> 1 d=0 Gauname Ū=4 „4=> 4 „€=4 |, d=O0 „taigi A,VXAr = X, X,KX,+X5. Funkcijų aibė Lit, vadinama uždara, jei kiekviena aibės funkcijų superpozicija priklauso šiai aibei t.y. Erna aibės funkcijų superpozicijai galima …
Excerpt
43 B(o a El 00 Eal0 01) = Pla, 0 = 0. 2. Aibė Tą. ) Apibrėžimas. f£lx4,...,*4) € T, tada ir tiktai tada, kai £4,...,1) = 1. Gauname kad 0 k 1€T, xe T, ax AT,,x 4 ET, „avy ET, x+4 4 [0 ir t.t. Aibė uždara, nes, jei f(*4,..-,Xm) Ei Bal aklej, be DE, vp Atai …
Excerpt
4 Šios funkcijos yra monotoninės: BL AR Riva. '" šios funkcijos nėra monotoninės: a) x> 4 „nes 4 0020-1457 0= 120, b)xX+4 „nes A «415 00+4=4 20=1+4 Raide M žymėsime visų monotoninių funkcijų klasę. Užduotis. Įrodykite, kad M - uždara aibė. 12 TEOREMA. Jei …
Excerpt
Eik ATS A a ias > 2 45 Nagrinėsime Zunkciją Gix)=£0€4, 1. Ka „usa, Val Ųiol= f 4... Teo 20 0 A ne 4( Y;) 7 4( Šri) = = La, Ya, 1, Var, . .,Šal = pu). Tai reiškia, kad ((0)=1 „o Y(4l=0 , kys Ų(x) =7X. Teorema įrodyta. 5. Aibė L. ; Tai visų tiesinių …
Excerpt
46 į UK] = X X, +£2, +B22 +X “Jei K=B=X=0,, tai U(A;,X2) = 411. Jei bent vienas iš £ , B ,Y nelygus nuliui, tai at- liksime tokius pakeitimus: X, keisime X, +B + I, keisime Z;14 (X4+8)(X1+1) + £4, +BX7 +V = X k Pži + K, +£B +41, +RBX1tY = i = 42; t£B +1. …
Excerpt
dės i 11 c) J EA Ek, a yre A NB e) fs €A, BL. 1 Įrodysim, kad aibė F= It fo, fa, Į] (o tuo pačiu ir At) ia Mas da A re ini T k are tiekia, Naja m yra pilna. Kadangi 4, KT, „iai galimi'du atvejai: 1 Ais, 1 Tada Ų(x)]= f (x,...,x) yra lygi konstantai 1, nes …
Excerpt
48 ce) A= [0,X, x VA, XV, VAS, 3 Ž 1212 ta ka, „Aka, e) A= [X4, z tRĘ "5, rA A aa4 ias, T) 2 eA tada ir tiktai tada, kai L[0,---,0)=4(4,-- 3. Perdirbti į Žegalkino polinomą ir k a, ar priklauso aibei L šios formulės: a) 1P2313,, b) 1p £09v(1> p)), e) …
Excerpt
= 49 jeigu jie sudaryti iš tų pačių raidžių, vienodų raidžių skaičius sutampa ir raidžių tvarka žodžiuose ta paii. To- kia lygybė vadinama grafine lygybe ir ją žymime simboliu = Žoažiai 1+1, 1+1 abėcėlėje ]1,+, 0] yra grafiškai lygūs, o 1+ 0 ir 1 yra …
Excerpt
50 . (19) sekoje. Jeigu (19) yra įrodymas, tai P. vedinama įro- doma; 0 (19) seka - formulės įrodymu. 1 pavyzdys: A=(!, J F - visi žodžiai abė- cėlėje A, Alt= [V , T=(P-PP). Kintamųjų kitimo sritis - žodžių abėcėlėje (p aibė. Tada II, IIII yra žo- džio. …
Excerpt
51 $10. Teiginių. skaičiavimas K Plačiau panagrinėsime vieną formalios teorijos pavyzdį. Pavadinsime jį teiginių skaičiavimu K. Teorijos abėcėlė A“ (12,8, V.) P, iš E) Susitarsime žodžius pP, PPP» PPPP» -++ Žymėti p, P.) Pjioos (panašiai su žodžiais gą, …
Excerpt
52 ponens (MP): 2 A A=B:6B, kur A ir B - bet kurios formulės. š Įrodymu teiginių skaičiavime K (žr. praeitą paragrafą) vadinsime baigtinę formulių seką, kurioje formulė yra arba aksioma, arba gauta iš kairėje jos stovinčių formulių pagal Balis ponens …
Excerpt
> : 53 Raide T žymėsime baigtinę (gali būti ir tuščia) žalio lių seką. , Formulės B įrodymu iš prielaidų T vadinsime baigtinę į seką B,, B,,-+- Bm s kurioje kiekviena B,(l+(* "m ) yra arba aksioma, arba viena iš prielaidų, arba gauta iš kairėje jos …
Excerpt
"E 3 m i 54 3 jam“ ir likusius A „ Lieka TFB 7. Jeigu T-A> 2B „iai T,AF-B. . i Įrodymas. Tarkime, B, B1s+- + B,ų „A> Byra formu= lės A > B žioūdugis iš prielaidų T. Prijungę prie tos ser kos A (kaip prielaidą) bei B (pagal MP taisyklę iš Ai3 B. ir A), …
Excerpt
4 | šiuo atveju = prielaida). Pirmuoju atveju A 2 B, pakeisime A=> B4 įrodymu: B, (akaioma), B,2(A= B.) (1.1*aksiomų schema), A2 B, (pagal liP taisyklę). Antruoju atveju A> B; keičiame analogiška seka (tik B. 1 Trečiuoju atveju A2A keičiame jos įrodymu, …
Excerpt
, 56 Įrodykite teiginių skaičiavime K šias formules: s) TNA = TA, b) (44B) > (BA), ce) (AVB) > (BVA), 2. Remiantis dedukcijos teorema, įrodyti: a) (A> B) > 2((b> 2C)] > (A> 0)), ») (4=(A2C) > (B> (A= 61 2(A=(Bvc). $12. Nepriešiaringumas į Formali teorija …
Excerpt
57 5.1A> 116 (pagal MP taisyklę iš 1, 4 formulių), 6. TA (prielaida), 7. TB (pagal MP taisyklę iš 5, 6 Aaaa 8. 7152 B (aksiomų schema 4.3, A pakeitėme 8), 9. B (pagal MP taisyklę iš 7,8 formulių). Prieštaringa teorija bloga tuo, kad joje įrodoma bet kuri …
Excerpt
58 $13. Pilnumas Mes norime įrodyti, kad bet kuri formulė F teiginių skeičiavime K yra įrodoma tada ir tik tada, kai F yra tapa- čiai teisinga. Pagal 16 teoremą, jeigu P įrodoma, tai ji ta- pačiai teisinga. Šiame paragrafe įrodysime, kad kiekviena +a- …
Excerpt
"- 59 (a> 214)2 (A2B) (1 lema), A> 26 (pagal MP taisyklę), Lema įrodyta. Tarkime, A - bet kuri E ių Pa.P2 + BN = pilnas sąrašas skirtingų teiginių, sudarančių A. Pažymėkime v P.isje v=1 P s ap = ju v=0 s A za Bie "kys - „Loginių operacijų skaičių …
Excerpt
60 1“; 1 2 w Bt Pa 4 Pra (28) au A Ra 2-2 Pk pažymėkime raide T. Galimi du atvejai: W=0 ,W-=1. . Jei W=0 , tai (28) grafiškai lygus TH-026 . Šiuo at- | vejų U=4 „Todėl AZ A „ty. A'=A6. Iš kur TA", Jei M=1 , tai (28) grafiškai lygus TF6 „ Šiuo at- veju v=0 …
Excerpt
f. 2 "A 61 Bb =B,CzC Duota (pagal indukcinę prielaidą)T-B,T-TC. Reikia įrodytiT-Bb> 2C arbaT,BF-C . Tai išplaukia iš ant- ros įrodymų iš prielaidų savybės (žr. $11). . d) M=1,W-=0 | šiuo atveju ATA te. A“= 1(82c),B“+B, C*1C. Duota (pagai indukeiūę …
Excerpt
2 VA , Mes norime įrodyti, kad Pr AI Rai FA. Tam pakanka parodyti, kad - (P„> 2A]=(0P-241> A) „nes, pasinaudojus MP taisykle, iš šios formulės ir (29), (30) nesunku gauti norimą rezultatą. Visų pirma įrodysimę: : J LUDB2O)> ( 088120) « a!) -U> (B20)> …
Excerpt
63 „kę MP Šai spaiai, 5, (1(AV1A1> 1A)> CAA TA) > CAVIAI (TA TAM (iš aksiomų schemos 2.3) i ; L 6. T(AVMA) Ž(MAŠTA) | (iš 3,4,5 formulių, pritaikę du kartus MP taisyklę) : į + T. 2(AV1A] 27(A> A) (15 formulių a, B, aksiomų schemos | 1,2, pritaikę du …
Excerpt
64 Pakarioję analogiškus samprotavimus (n-2) kartus, gauname PA: Teorema įrodyta. 614. Kiti teiginių skaičiavimai Teiginių skaičiavimo K formulėse yra „loginės ope- racijos 7,8,V,> 2 Pateiksime vieną teiginių skaičiavimą (nu- rodydami aksiomų schemas ir …
Excerpt
je - moūus ponens. as igiikam nė ana ago sieno, S 65 6) A> (AVD, 7) B= (ĄVB), 8) (A50 > (B201> ((AVB)> A), 9) (A> B1)> 2 ((A> 7B1!> 1A1, | 10) T1A> A, kur A,B,C - bet kurios formulės. Taisyklė vienintelė, Tai - E f Į '"Aprašytuose teiginių skaičiavimuose …