SUTRUMPINTOS TEISINGUMO LENTELĖSMes naudojame teisingumo lenteles, kai norime nustatyti ar formulė tapačiai teisinga, ar iš duotų formulių išplaukia kita formulė. Tačiau, kad įrodyti, ar formulė yra tapačiai teisinga, ar formulė logiškai išplaukia, dažnai yra paprasčiau taikyti teoremas. Jeigu mums reikia įrodyti, kad formulė nėra tapačiai teisinga ar logiškai išplaukia, mums nereikia sudarinėti pilnos teisingumo lentelės. Tereikia surasti tinkamą eilutę, kuri tai įrodytų. Jeigu vis dėlto tenka atlikti daug skaičiavimų pagal teisingumo lenteles, tai galima panaudoti metodą, pagreitinantį skaičiavimą. Jo esmė tokia, kad t ir k reikšmės priskiriamos vienintelei raidei. Raidė pasirenkama ta, kuri dažniausiai naudojama formulėje. Tuomet formulė supaprastėja. Po to t ir k reikšmės priskiriamos kokiai nors kitai raidei. Panagrinėkime kokio nors dvejetainio ryšio s pradinę teisingumo lentelę. Jeigu mes formulei A priskiriame reikšmes t arba k, tai esant fiksuotoms A reikšmėms A s B lentelė tampa vienetinio ryšio, priklausančio nuo B, lentele. Vienetiniam ryšiui galimos tik 4 lentelės:T t T K (kaip ir B)K T (ŲB)K K Taigi, parenkant vieną A reikšmių, formulė gali įgyti vieną iš reikšmių t, B, ŲB, k. Žinomų loginių operacijų atveju gauname tokias lenteles:A A_BB_A AŽB BŽAT B B tK ŲB t ŲBLentelės ( ) tęsinys ( Æ )AŁBBŁA AŚBBŚA ŲAB t kk B tPavyzdžiui:P Ž (Q Ś R Ž (R Ž ŲP))kai P yra k, tai viskas yra t: k Ž (Q Ś R Ž (R Ž Ųk))kai P yra t: t Ž (Q Ś R Ž (R Ž Ųt))Q Ś R Ž (R Ž k)Q Ś R Ž ŲRtoliau kai R yra t:Q Ś t Ž Ųtt Ž kkkai R yra k:Q Ś k Ž ŲkQ Ž ttPateikta formulių sistema vadinama analize pagal teisingumą. Šį metodą pritaikė 1950 m. W. van O. Quine.PAGRINDINĖS IŠPLAUKIMO TAISYKLĖSG. Geutzeu (kažkoks austras)Šios taisyklės yra dedukcinių samprotavimų pagrindas.1 Jei iš G, A╞ B, tai G,╞ A Ž B (implikacijos įvedimas)Ši taisyklė įveda implikaciją, jeigu įrodyta, kad iš A╞ B. Galbūt dar darant kitas prielaidas (aibė G) ši taisyklė plačiai naudojama įrodymuose. Tarkim, kad reikia įrodyti implikacinės struktūros sakinį A Ž B. ??? prie jo įrodytų sakinių G prijungiamas sakinys A ir tada iš G ir A išvedama B. Po to sakoma, kad teorema įrodyta. Toks formulavimas ir nusako, kaip taikoma implikacijos įvedimo taisyklė, t.y. G, A╞ B prie išplaukimo G,╞ A Ž B.2 Jeigu G, A╞ C ir G, B╞ C, tai G, AŚB╞ C (disjunkcijos pašalinimas)Pagal šią taisyklę išvadai C iš disjunkcijos A arba B gauti pakanka gauti išvadą C iš A ir iš B, t.y., norint išvesti C iš AŚB, ši disjunkcija pašalinama ir įrodomi du skirtingi išplaukimai G, A╞ C ir G, B╞ C.1) P Ł Ų(ŲQ Ž R) = t
2) P Ž Q = P _ Q
3 Jeigu iš G, A╞ B ir G, A╞ ŲB, tai iš G╞ ŲA (neigimo įvedimas)Ši taisylė yra netiesioginio įrodymo pagrindas. Netiesioginis įrodymas – tai įrodymas prieštaros metodu. Teiginiui A įrodyti daroma prielaida, kad A yra klaidingas, o ne A yra teisingas. Tada iš ŲA ir jo įrodytų teiginių aibės G išvedame prieštarą BŁŲB. Po to sakome, kad gauta prieštara įrodo teoremą. Toks formulavimas reiškia, kad neigimo įvedimo taisyklė taikoma netiesiogiai. Iš tikrųjų, pagal ją gauname G, ŲA╞ B ir G, ŲA╞ ŲB, tai G╞ ŲŲt.4 Jeigu iš G╞ A ir G╞ A Ž B, tai G╞ B (implikacijos pašalinimas)Ši taisylė bus pagrindinė tolimesnėje mūsų teorijoje. Su ja jau buvom susidūrę netiesiogiai, kai samprotavom, kad tapačiai teisingas teiginys A Ž B yra stipresnis nei teiginys jei A tapačiai teisinga, tai B tapačiai teisinga. Tuomet ši taisyklė ir buvo įrodyta.5 Jeigu iš G╞ A, tai G╞ AŚB (pirmasis disjunkcijos įvedimas)6 Jeigu iš G╞ B, tai G╞ AŚB (antrasis disjunkcijos įvedimas)Šios taisyklės kaip ir tapačiai teisingos formulės išreiškia logikos dėsnius. Kartu šios taisyklės akivaizdžiau nei tapačiai teisingos formulės išreiškia samprotavimų metodus.TEIGINIŲ LOGIKOS TAIKYMAS NATŪRALIAI KALBAINATŪRALIOS KALBOS SAKINIŲ UŽRAŠYMAS MATEMATINĖS LOGIKOS KALBANatūralios kalbos teiginiai esti įvairių konstrukcijų. Daugelyje jų galima išskirti tokias komponentes, kurios pačios yra sakiniai. Šie paprastesni sakiniai grupuojami į sudėtinius jungtukais ir skyrybos ženklais. Kiekvienas jungtukas turi savo atspalvį. Logikoje šie atspalviai išnyksta. Ir visa kalbinių jungimo priemonių gausybė išreiškiama nedideliu loginių operacijų skaičiumi. Pvz.:
1 Nustatykite sakinio “Jis baigė, o aš stovėjau ir vis klausiau” loginę struktūrą.Pažymėsim elementarius teiginius: P – jis baigė; Q – aš stovėjau; R – vis klausiau. Tada PŁQŁR. Pirmu atveju konjunkcija išreikšta “,” ir jungtuku “o”, antru atveju – jungtuku “ir”. Logine prasme abu sąryšiai konjunkciniai. Semantine prasme sąryšių atspalviai yra skirtingi. Jungtukas “o” turi reiškinių sugretinimo prasmę, o jungtukas “ir” turi neutralią jungiamąją prasmę.2 Nustatyti sakinio “Kadangi skaičių x galima užrašyti x = 2pn + u (kur 0 £ u < 2p, n Ī Z), tai funkcijų sin x ir cos x reikšmių apskaičiavimas pakeičiamas intervale 0 £ u < 2p esančio argumento sin ir cos reikšmių apskaičiavimu.” loginę struktūrą.Pažymim P – skaičių x galime užrašyti formule x = 2pn + u; R – 0 = u; Q – 0 < u; S – u < 2p; T – n Ī Z; V – sin x reikšmės apskaičiavimas pakeičiamas; W – cos x reikšmės apskaičiavimas pakeičiamas.PŁ(QŚR) ŁSŁTŽVŁWŁ(QŚR) ŁS3 Kokia yra sakinio “Funkcija y = cos x apibrėžta intervale (0, p) turi atvirkštinę funkciją.” loginė struktūra? Šio sakinio loginė struktūra iš karto nepastebima. Sakinys tvirtina, kad “funkcija turi atvirkštinę funkciją” – R, bet tik esant sąlygoms “funkcija y = cos x” – P ir “funkcija apibrėžta intervale (0, p)” – Q, t.y. šis sakinys yra lygiavertis tokiam sakiniui: “Jeigu funkcija y = cos x nagrinėjama intervale (0, p), tai ji turi atvirkštinę funkciją”. O šio sakinio loginė struktūra labai aiški.LOGIKASAMPROTAVIMŲ ANALIZĖ. TEIGINIŲ LOGIKOS METODAIŠi analizė susideda iš 2 dalių:a) samprotavimo struktūros nustatymasb) patikrinimas, ar išvada išplaukia iš duotų prielaidų.Pvz.:4. Išanalizuokim samprotavimą:“Jeigu 10-taine sistema parašytas skaičius (sveikas) baigiasi 5” -P, “tai jis dalijasi iš 5” -Q. 10-taine sistema parašytas skaičius dalijasi iš 5. Mums reikia patikrinti, ar ši išvada išplaukia iš duotų prielaidų. Užsirašom samprotavimo struktūrą: PŽQ, P?Q. Norint nustatyti, ar teisinga išvada, galima naudoti įv. metodus. Pats paprasčiausias yra teis. lent. metodas (nenaudosim, nes per daug paprasta). Ši samprotavimo struktūra atitinka MP taisyklę: gaunam PŽQ, P╞ Q.5. “Aš užmokėčiau už televizoriaus remontą” -Q, “jeigu jis dirbtų” -P, jis nedirba, todėl aš nemokėsiu (prielaida). QŽP, P Q 1. QŽP čia kontrpozicija 4. Q, todėl QŽP, P╞ Q 2. P (arba 52 formulė) 3. PŽ Q;6. “Jeigu jis nebūtų jai pasakęs” – Q, “ji nebūtų sužinojusi” – P, “jei ji nebūtų paklaususi” – R, jis jai nebūtų pasakęs. Ji sužinojo, vadinasi, ji paklausė.QŽ P, RŽ Q, P RSurašom prielaidas: tuomet taikom kontrpoziciją: 1. QŽ P 2. RŽ Q 3. P 4. PŽQ 5. Q (MP, 3, 4) 6. QŽR (52) 7. R (MP, 5, 6)todėl išvada teisingaQŽ P, RŽ Q, P╞R7. “Profsąjungos palaikys prezidentą” -P, “tik tuo atveju, jei jis pasirašys įstatymą” -Q; “žemdirbiai jį palaikys “ -R, “tik tuo atveju, jei jis uždės veto” -S. Aišku, kad prezidentas arba nepasirašys įstatymo, arba neuždės jam veto. Vadinasi, prezidentas praras arba darbininkų, susivienijusių į profsąjungas, balsus, arba praras žemdirbių balsus.PŽQ, RŽS, QŚ S, PŚ RŠio samprotavimo teisingumui nustatyti naudosime disjunkcijos pašalinimo taisyklę, t. y. skaidysim įrodymą į 2 dalis. 1) PŽQ PŽS, Q PŚ R 2) PŽQ RŽS, S PŚ R1) 1. PŽQ 2. RŽ 3. 4. QŽ P 52, 5. P MP, 3, 6. PŚ P D?įrodėm2) 1. PŽQ 2. RŽS 3. S 4. SŽ R 52 5. R MP 6. PŚ Rišplaukimas įrodytasToliau pateiksime sąrašą loginių operacijų ir joms atitinkamų kalbos…A_B A jei ir tik jei B1. jei A, tai ir B ir atvirkščiai, jei B, tai ir A ir atv.2. A jei B ir B jei A3. dėl A būtina ir pakanka B4. A_B5. A tada ir tik tada, kai BA_B1. jei A, tai B2. A atveju bus B3. dėl B pakanka A4. dėl A būtina B5. A iššaukia B6. B jei AAŁB1. AŁB2. ne tik A, bet ir B3. B nors ir A4. A tuo pat metu, kaip ir B5. B nepaisant A6. kaip A, taip ir B7. A kartu su BAŚB1.AŚB arba abu2.AŚB3.A jei ne BSakinių pervedimas į logikos kalbą Nors teiginių skaičiavimetačiau frazes “Neringai gimė vaikas ir ištekėjo” ir “Neringa ištekėjo ir jai gimė vaikas” Neringos pažįstami suprastų labai skirtingai. Tai susijų su įvykių tvarka laike. Tačiau dėl loginės analizės dažnai galima nekreipti dėmesio į laiką. Kita problema susijusi su terminų dviprasmiškumu, kuriuos reikia pakeisti loginėmis operacijomis. Pvz., jei meniu parašyta: “Arbata arba kava nemokamai”. Mes nenustebsime, jei mes paprašysime dviejų ir mums teks už tai susimokėti. Tačiau jei parašyta, kad “knygų aukas priima fakulteto raštinė arba biblioteka”, mes negalvojame, kad jei paaukojam raštinėj, tai vėliau bibliotekoj nepriims, nes mes aukojom raštinėj. Ši problema susijusi su jungtuko “arba” dviprasmiškumu.ĮRODYMŲ TEORIJA1. Formalusis įrodymas ir formalusis išvedimasMatematikai įrodinėja teoremas, t. y. išveda jas iš duotų prielaidų tokiu būdu: teiginiai rašomi į tam tikrą sąrašą, vad. įrodymu arba išvedimu.Mes kalbėsim apie įrodymą ir prielaidas vadinsime aksiomomis, jei jos išlaiko savo statusą visoje nagrinėjamoje teorijoje, t. y. jos yra tpč. teisingos. Mes kalbėsim apie išvedimą, jei nebūsim tikri, kad visos prielaidos išlaiko savo statusą. Kiekvienas perėjimas nuo vieno teiginio prie kito nagr. sąraše yra pagrįstas logiškai. Pvz.: Teiginys seka iš kitų teiginių, jei jis tenkina išplaukimo apibrėžimą. Išplaukimas buvo apibrėžtas remiantis teisingumo lentelėmis. Apibrėždami išplaukimą, tapačiai teisingas formules, mes naudojome meta kalbą, t.y. kitą kalbą, nei kurioje rašomi teiginiai. Būtent meta kalboje mes gauname įvairius rezultatus apie tapatųjį teisingumą ir išplaukimą, kurie yra patogesni nei teisingumo lentelių vartojimas. Toks logikos nagrinėjimas vadinamas modelių teorija. Pakeisdami atomus t ir k reikšmėmis, mes gauname modelius arba konkrečias realizacijas.Kitas būdas: Šis būdas vadinamas įrodymų teorija,nagrinėja klausimą, ar negalima parašyti loginius įrodymus ir išvadas taip, kaip yra daroma geometrijoje. Tačiau kadangi pati logika yra nagrinėjimo objektas, tai išvedimai negali remtis loginiais kriterijais, jie gali remtis tik aksiomomis ir taisyklėmis. Įrodymų teorijoje kai kurie teiginai vadinami aksiomomis,o naujų teiginių sudaymui naudojamos išvedimo tasyklės. Vėliau mes pamatysime, kad modelių ir įrodymų teorija duoda ekvivalenčius rezultatus.2.1Ap. Teorijos L aksiomomis vadinamos visos formulės, turinčios 1.3 T-os 1A-10B formulių pavidalą. Šios formulių formos vad. aksiomų schemomis.Kiekviena aksiomų schema sukuria begalinę aksiomų aibę, pvz.:aksiomų schema 1a AŽ(BŽA) atitinka tokios formulės : PŽ(PŽP), QŽ(PŽQ),PŽ(QŁRŽP), (PŽ(RŽP))Ž(RŽ(PŽ(RŽP)))Pateiktame aksiomų schemų sąraše yra kiekvieno iš 5 loginių operacijų : neig. Konj. Disj. Injekc. Ekviv. aksiomų schemos.1a ir 1b aksiomų schemos – tai implikacijos AS. 3 AS įveda konjunkcijos operatorių, o 4 ir 5 jį pašalina. 5a ir 5b įveda disjunkcijos operatorių, o 6 jį pašalina. 7 schema įveda neigimo operatorių, o 8 jį pašalina. 9 schema įveda ekvivalencijos operatorių, o 10a ir 10b jį pašalina.2.2 Teorijos L vienintelė išvedimo taisyklė vadinama implikacijos pašalinimu arba MP taisykle. Ši taisyklė leidžia pereiti nuo formulių pavidalo A ir AŽB prie formulės B. Naudojant MP taisyklę A ir AŽB vadinamos prielaidomis, o B – šios taisyklės išvada.2.3 Formaliuoju įrodymu teorijoj L vad. baigtinė formulių B1, B2, … BN seka kai kiekviena šios sekos formulė yra arba aks. schema, arba gaunama pagal MP taisyklę iš kurių nors dviejų ankstesnių šios sekos formulių.Form. Įrodymas yra paskutiniosios formulės BK įrodymas. F-lė B vadinama formaliai įrodoma, arba formaliąja teorema, jei ji turi formalųjį įrodymą. Teiginį “f-lė B formaliai įrodoma teorijoje L” žymėsime ├L B ir ir sutarsim iki naujų formalių teorijų pasirodymo indeksą L praliesti, tai ├ B.Pvz.: Pabandykime įrodyti, kad ├AŽA (AŽA) yra įrodoma). F-lės AŽA įrodomumui nustatyti pagal 2.3 apibr. reikia užrašyti baigtinę formulių seką, kurios paskutinė formulė būtų AŽA ir taip, kad kiekviena šios sekos formulė būtų aks. schema arba gauta pagal MP taisyklę. Aišku, kad pirmosios šios sekos f-lės turėtų būti aksiomos. Be to, viena iš šių aksiomų turi bagtis formule AŽA. Galima būtų panaudoti aks-ų schemą 1b, kuri baigtųsi f-le AŽA , jei f-lę C pakeistume į f-lę A : (AŽB)Ž((AŽ(BŽA))Ž(AŽA)) (1)dabar, norint iš šios f-lės pagal MP taisyklę gauti f-lę AŽA, reikia pašalinti (?) implikaciją : F1=(F2Ž(AŽA)), kur F1 žymi (AŽB), o F2 žymi (AŽ(BŽA)). Iš pradžių pašalinti F1, o po to F2. Norint pašalinti F1 reikia ją tirėti formulių sekoje. O vietoj F1 gali būti įrašyta tik aks. schema. Palyginę F1 su 1a aks. schema, galime pastebėti, kad B reikia pakeist BŽA. Tuomet (1) atrodys taip : (AŽ(BŽA))Ž((ŽA)ŽA))Ž(AŽA))yra aks. schema 1a.Dabar šį įrodymą galime užrašyti tokia seka :1. AŽ(BŽA) 1. AS 1a2. (AŽ(BŽA))Ž((AŽ(BŽA))ŽA))Ž(AŽA)) 2. AS 1b; C keičiam A, B keičiam BŽA3. (AŽ((BŽA))Ž(AŽA) 3. MP ( 1,2 )4. AŽ((BŽA)ŽA) 4. AS 1a, B keičiam BŽA.5. AŽA 5. MP ( 4,3 )Reikia pasakyti, kad čia faktiškai įrodyta ne konkreti formulė, o visa AŽA pavidalo klasė, nes šiame įrodyme A ir B yra bet kokios formulės. Taip pat reikia pasakyti, kad kiekviena iš 5 šio įrodymo formulių yra teoremos, taip pat ir aksiomos. Bet kurios aksiomos įrodymą sudaro pati aksioma.2.4 Formulės B formaliuoju išvedimu iš prielaidų A1, A2, … An vadinama baigtinė formulių B1, B2, …Bk seka, pasibaigianti formule B, kur B = Bk . Kiekviena iš šios sekos formulių yra arba viena iš prielaidų A1, A2, … An, arba aksioma, kuri gaunam pagal MP taisyklę. Iš dviejų ankstesniųjų. Akivaizdu, kad įrodymas yra atskiras formaliojo išvedimo atvejis iš tuščios pirelaidų aibės.Pvz.: Nustatykime, kad iš AŽ(BŽC), AŁB ├ C.Padarę prielaidą AŁB ir aksiomų schemos 4a, pagal MP galim gauti f-lę B. O iš f-lių A ir B ir prielaidos AŽ(BŽC), pagal MP gausime C.1. AŁB 1. Prielaida2. AŁBŽA 2. AS 4a3. A 3. MP ( 1,2 )4. AŁBŽB 4. AS 4b5. B 5. MP ( 1,4 )6. AŽ(BŽC) 6. Prielaida7. BŽC 7. MP ( 3,6 )8. C 8. MP ( 5,7 )1. Išvedamumo santykio savybės1.1 T a) A1, A2, … An ├ Ai ( i = 1,n ) b) A1, A2, … An ├ B1, A1, A2, … An ├ B2, … …, A1, A2, … An ├ Bk ir B1, B2, … Bn ├ C, tai A1, A2, … An ├ C.a) Iš duotos prielaidų aibės išvedama kiekviena šios aibės prielaida.b) Jei iš duotos prielaidų aibės išvedama kiekviena formulė iš kokios nors prielaidų aibės, o iš šios prielaidų aibės išvedama formulė C, tai C išvedama ir iš pradinės prielaidų aibės.sa) f-lei Ai išvesti iš A1, A2, … An pakanka paeiliui užrašyti f-les A1, A2, … An bet kokia tvarka, tik paskutinę užrašant f-lę Ai.b)Išvedant f-lę C iš f-lių B1, B2, … Bn , šias formules pakeitus duotaisiais jų išvedimais iš formulių A1, A2, … An gaunamas f-lės C išvedimas iš iš formulių A1, A2, … An.Taigi, pagal 2.1T, formulių, išvedamų iš A1, A2, … An klasę sudaro kiekviena iš šių formulių, taip pat visos formulės, išvedamos iš f-lių, jau priklausančių šiai klasei.Teiginių logikos modelių teorijoje buvo vartotos dvi svarbis sąvokos : tapačiojo teisingumo ir loginio išplaukimo. Įrodymų teorijoje panašią reikšmę turi įrodomumo ir išvedamumo sąvokos. Palyginsim šių sąvoku prasmę:1. ╞ AŽB tai reiškia, kad f-lė AŽB yra tapačiai teisinga, t.y. kad esant visiems į bent vieną iš formulių A arba B įeinančių Išvedamumo santykio savybės2.1T.a) A1, A2,..,An |- Ai (i=1,n). b) jei A1, …, An |- B1; A1, …, An |- B2; A1, …, An |- Bk ir B1,…,Bk |- C, tai A1, …, An |- C. a) Iš duotosios prielaidų aibės išvedama kiekviena iš šios aibės prielaida. b) Jei iš duotos prielaidų aibės išvedama kiekviena formulė iš kurios nors prielaidų aibės, o iš šios prielaidų aibės išvedama C, tai C išvedama ir iš pradinės prielaidų aibės. Įrodymas: a) Formulei Ai išvesti iš formulių A1, A2,…An pakanka paeiliui užrašyti visas formules A1, A2,…An bet kuria tvarka, tik paskutinę užrašant Ai. b) išvedant formulę C iš formulių B1,…,Bk , formules B1,…,Bk pakeitus duotaisiais jų išvedimais iš formulių A1, A2,..,An, gaunamas formulės C išvedimas iš A1, A2,..,An. Taigi, pagal 2.1T. formulių išvedamų iš A1, A2,..,An klasę sudaro kiekviena iš šių formulių, taip pat visos formulės, išvedamos iš formulių jau priklausančių šiai klasei. Teiginių logikos modelių teorijoje buvo naudotos 2 svarbios sąvokos: tapačiojo teisingumo ir loginio išplaukimo. Įrodymų teorijoje panašią reikšmę turi įrodomumo ir išvedamumo sąvokos. Palyginsim šių sąvokų variantus: 1) |= A=>B. Toks užrašymas reiškia, kad formulė A=>B yra tapačiai teisinga, t.y. kad esant visiems į bent vieną iš formulių A arba B įeinančių atomų rinkiniams formulė A=>B įgyka tik t reikšmes. 2) A|=B. Tai reiškia, kad iš formulės A išplaukia formulė B, t.y. kad esant visiems į bent vieną iš formulių A arba B įeinančių atomų reikšmių rinkiniams, kai formulė A įgyja reikšmę t, tai ir B įgyja t reikšmę. 3) |- A=>B, reiškia , kad formulė A=>B įrodoma, t.y. kad egzistuoja baigtinė formulių seka pasibaigianti A=>B, be to, kiekviena šios sekos formulėyra aksioma arba gaunam pagal MP taisyklę. 4) A |- B. Reiškia, kad iš A išvedama B, t.y. kad egzistuoja baigtinė formulių seka pasibaigianti B, be to, kiekviena šios sekos formulė yra arba A, arba aksioma, arba gaunama pagal MP taisyklę.Sąvokos 1-4 yra tarpusavyje susijusios. 1.13T. nustatė ryšį tarp tapačiojo teisngumo ir loginio išplaukino. Dabar pateiksim teoremas. kurios nurodys ryšį tarp įrodomumo ir išvedamumo, tarp tapčiojo teisingumo ir įrodomumo.
2.2T. Tarkime. kad G bet kuri formulių aibė, tuomet: a) jei G |- A=>B, tai G, A|-B; b) jei |-A=>B, tai A|-B (vienos formulės atžvilgiu). Įrodymas: sąlygoje duotų formulės A=>B išvedimą iš formulių aibės G galima paversti formulės B išvedimu iš aibės G ir A. 1….k. A=>B; k+1. A; k+2. B (MP k+1, k). Išvados: a) jei įrodoma formulė |-A1=>(…Ž(An-1Ž(AnŽ))…), tai A1, A2, …, An |-B b) Jei įrodoma konjunkcija |- A1ŁA2Ł..ŁAnŽ B, tai A1, A2, …, An |-B. Įrodymas: a) Įrodoma pritaikius n kartų 2.2T. b) Pagal išvados sąlygą gauname A1ŁA2Ł..ŁAn |- B (2.1). Įrodysima, kad iš sekos išvedame konjunkciją A1, A2, …, An|- A1ŁA2Ł..ŁAn. Kad sėkmingai tai padaryti, pritaikysim konjunkcijos įvedimo (KĮ) taisyklę: A, B |- AŁB. Įrodymas: 1. A; 2. B; 3. AŽ(BŽ AŁB) (AS3); 4. BŽ AŁB; 5. AŁB. (įrodyta).1. A1, ..An |- An 2.1T a);2. A1, ..An |- An-1 2.1T a);3. An, An-1 |- AnŁAn-1 KĮ;4. A1, .., An |- AnŁAn-1 2.1T b)5. A1, .., An |- An-2 2.1T a)6. An-2, An-1, An |- An-2ŁAn-1ŁAn 7. A1,.., An |- An-2ŁAn-1ŁAn 2.1Tb …..3n-5. A1…An |- A2Ł..ŁAn3n-4. A1…An |- A13n-3. A1…An |- A1Ł…ŁAn.Iš 2.2, 2.1 pagal 2.1T b) dalį gauname A1….An |- B.ĮRODYMŲ TEORIJA. DEDUKCIJOS TEOREMADedukcijos teoremoje yra išreikšta formalaus išvedimo savybe, atitinkanti gerai žinomą neformalaus mąstymo būdą. Šią teoremą suformulavo ir įrodė moksl. J.herbrand 1930m. 2.3T a)jei iš G,A├B, tai G├AŽB b)jeigu iš A├B, tai ├AŽBPagal teoremos sąlygą egzistuoja formulės B išvedimas. B1 ,…,Bm Kur Bm=B iš formulių aibės, G ir A, t.y. duotasis išvedimas. Reikia įrodyti, kad egzistuoja formulės AŽB išvedimas iš formuliu aibės G, t.y. gaunamasis išvedi-mas. Šie abu išvedimai turi 2 skirtumus: 1. Duotasis išvedimas baigiasi formule B, o gaunamasis AŽB; 2. Duotajam išvedime galima remtis prielaida A, o gaunamąjame išvedime tokios prielaidos nėra. Egzistuoja algoritmas, paverčiantis duotąjį išvedimą gaunamuoju išvedimu. Jį panagrinėsime: sakykim, kad duotąjame išvedime prieš kiekv. Formulę parašome simbolius AŽ, tuomet paskutinė formulė bus AŽB. Tačiau tai nėra iš tiesų išvedimas iš formulių aibės G. Tačiau prieš kiekv. formulę AŽBI galima įrašyti papild. formules taip, kad formuliu seka pavirstų gaunamuoju išvedimu iš formulių aibės G. Papild. formu-lės parenkamos atsizvelgiant į tai, su kokiu pagrindimu formulė Bi įeina I duortąjį išvedimą. Galimi 4 variantai: 1.Bi aibės G prielaida; 2. Bi tai prielaida A; 3.BI tai aksioma; 4. BI tai formulė gauta pagal MP taisyklę iš kurių nors dviejų ankstesniųjų.Panagrinėsime: 1. Tarkim Bi = Aj kur Aj ĪG. Šiuo atveju Bi yra ne tik duotojo, bet ir gaunamojo išvedimo prielaida. Tuomet gaunamajame išvedime prieš formulę AŽAj įrašysim 2 formu-les Aj ir Aj Ž(AŽAj) o tai yra AS1a, kur galimi pakeitimai vietoj A – Aj, o vietoj B – A. Mūsų pageidaujamą formulę gaunam pagal MP taisyklę. 2.Tarkim, kad BI prielaida A, tuomet BI yra duotojo išvedimo, bet ne gaunamojo išvedimo prielaida. Šiuo atveju gaunamajame išvedime bus formulės AŽA. Šios formulės įrodymas buvo pateiktas kaip pvz. ir jį sudarė 4 formulės, vadinasi į gaunamąjį išvedimą reikia patalpinti šias 4 įrodymo formules. 3. tarkim BI yra aksioma, tuomet elgiamės taip pat kaip ir pirmuoju atveju. 4. tarkim, kad BI yra formulė, gauta pagal MP taisyklę iš formulių Bp ir Bq. Tuomet formu-lė Bq turi turėti pavidalą BpŽBi. Gaunamajame išvedime mes turim turėti formules s. AŽBp, t.AŽ(BpŽBI) ir v. AŽBi. O tai galima pastebėti, kad šie trys nariai atitinka AS1b. tuomet tas formules mes jau turime sekoje, įterpiame AS1b su atitinkamais pakeitimais (AŽBp)Ž((AŽ (BpŽBI)Ž(AŽBI)) AS1b(B-Bp, C-BI) ir 2*MP taisyklė. v+1. (AŽ(BpŽBI))Ž(AŽBI),MP(s,v). v+2. AŽBI ,MP(t,v+1)Šiuo atveju įterpiam 3 formulesPvz.: sakykim kad duotas išvedi-mas AŽ(BŽC), AŁB├C reikia įrodyti AŽ(BŽC) ├AŁBŽC 1.AŽ(BŽC) 1.prielaida 2.(AŽ(BŽC))Ž(AŁB)Ž(AŽ(BŽC)) 3.AŁBŽ(AŽ(BŽC)) AS1a (A-AŽ(BŽC), B-AŁB)4.(AŁBŽ(BŽ(AŁB))Ž((AŁBŽ((BŽAŁB)ŽAŁB))Ž(AŁBŽAŁB)) AS1b(A-AŁB,B-BŽAŁB, C-AŁB)5.AŁBŽ(BŽAŁB) AS1a (A-AŁB)6.(AŁBŽ((BŽAŁB)ŽAŁB))Ž(AŁBŽAŁB) MP (2,4)7.AŁBŽ((BŽAŁB)ŽAŁB) AS1a (A-AŁB, B-BŽAŁB)8.AŁBŽAŁB 3)AŁBŽA (3 var.) AS4a9.AŁBŽA10.(AŁBŽA)Ž(AŁBŽ(AŁBŽA)) AS1a(A-AŁBŽA,B-AŁB)11.AŁBŽ(AŁBŽA) MP(9,10) 4)A MP(2,3) (4 var.)12.(AŁBŽAŁB)Ž((AŁBŽ(AŁBŽA))Ž(AŁBŽA)) AS1b(A-AŁB,B-AŁB,C-A)13.(AŁBŽ(AŁBŽA))Ž(AŁBŽA) MP(8,12)14.AŁBŽA MP(11,12) 5)AŁBŽB AS4b (3 var.)17.AŁBŽ(AŁBŽB) 6)B MP(2,5) 7)BŽC MP(4,1) 8)C MP(6,7)18.,19.,20.lygiagrečiai 6 6.B 20.AŁBŽB MP(17,19) 21.,22.,23.lygiag.7 BŽC 23.AŁBŽ(BŽC) MP(3,22)24.,25.,26.lyg.8 C 26.AŁBŽC MP(23,25)remdamiesi įrodymu teorija sudarėm gaunamą išvedimą. Taikant aprašytą algoritmą ir imant 26 formules kaip duotąjį išvedimą, gausime formulės įrodymą, kurį sudarys 80 formulių (AŽ(BŽC))Ž(AŁBŽC)kaip matyti iš pvz.2.3T įrodyme aprasytas duotojo išvedimo trans-formavimas į gaunamąjį labai išplečia gaunamąjį išvedimą. Duotajame išvedime yra k f-lių, o gaunamajame 3k+2. Tačiau dažnai nebūtina turėti patį įrodymą. Užtenka nustatyti tik patį įrodomumo faktą. Pvz. irodomumo fakto nustatymui daug padeda dedukcijos teorema. Pvz. nustatykime kad formulė yra įrodoma9.├(AŽ(BŽC))Ž(BŽ(AŽC))už įrodymo ženklo yra ‘Ž’, tai yra ši formulė buvo gauta taikant deduk.T tokiai formulei 8.AŽ(BŽC)├BŽ(AŽC)į dešinę už įrodymo ženklo yra ‘Ž’. Vadinasi ši f-lė buvo gauta taikant deduk.T 7.AŽ(BŽC),B├AŽCuž įrodymo ženklo yra ….6.AŽ(BŽC), B,A ├Cnorint nustatyti pradinės f-lės įrodomumą, pakanka nustatyti kad egzistuoja f-lės C išvedimas iš duotų prielaidų. Bandom sudaryti f-lės C išvedimą1.AŽ(BŽC) prielaida2.B prielaida 3.A prielaida4.BŽC MP(3,1) 5.C MP(2,4)suradom f-lės C išvedimą iš duotų prielaidų. Toliau darydami žingsnius tiesiogine tvarka, taikydami deduk.T gausim kad pradinė f-lė yra įrodoma. Jei A├B ,tai├AŽB Jei 9 f-lėje pakeisim A į B, o B į A gausime f-lę 10. ├(BŽ(AŽC))Ž(AŽ(BŽC))Panaudosim AS9, kurioje atliksim pakeitimus 11.├((AŽ(BŽC))Ž(BŽ(AŽC)))Ž((BŽ(AŽC))Ž(AŽ(BŽC)))Ž((AŽ(BŽC))_(BŽ(AŽC))) AS9(A-AŽ(BŽC),B-BŽ(AŽC))12.├((BŽ(AŽC))Ž(AŽ(BŽC)))Ž((AŽ(BŽC))_(BŽ(AŽC))) MP(9,11)13.├(AŽ(BŽC))_(BŽ(AŽC)) MP(10,12)turėdami paprastą išvedimo įro-dymą, deduk.T galime nustatyti, kad egzistuoja įrodymas daugeliui sudėtingų f-lių. Neturim pačio įrodymo, bet nu-statom, kad jis egzistuoja. TEORIJOS NEPRIEŠTARINGUMASApibendrinant 2.2T ,2.3T rezultatus galima tvirtinti, kad AŽB įrodoma tada ir tik tada, kai iš A išvedama B.tokiu budu ryšys tarp įrodomumo ir išveda-mumo yra nustatytas. Panašiai buvo nustatytas ryšys tarp tapačiojo teisingumo ir loginio išplaukimo modelių teorijoje. Jeigu pavyktų įrodyti, kad sąvokos f-lė E yra įrodoma ir f-lė E tapačiai teisinga yra lygiareikšmės, tai užbaigtume ekvivalentumo nustatymą tarp modelių ir įrodymų teorijų. 2.5Ap. Formalioji aksiominė teorija ,vad. neprieštaringa jei nėra nei vienos tokios f-lės A, kad f-lės A ir ŲA būtų įrodomos vienu kartu. Formalioji aksiomine teorija vadinama prieštaringa, jei egzistuoja tokia f-lė A, kad f-lės A ir ŲA yra įrodomos abi kartu. 2.4T kiekviena įrodoma f-lė yra tapačiai teisinga. Jei ├ E, tai ╞ E.teorijos L aksiomos tai 1.3T pirmosios 13 f-lių. Ir pagal šią te-oremą jos yra tapačiai teisingos. Atitinkamai pagal 1.9T jei MP taisyklės prielaidos A ir AŽB yra tapačiai teisingos, tai šios taisyklės išvados B yra tapačiai teisinga. Pagal šios teoremos sąlygą, f-lė E yra įrodoma, tai yra ji užbaigia baigtinę f-lių seką, sudarytą iš aksiomų arba iš f-lių gautų pagal MP taisyklę iš bet kurių 2 ankstesnių f-lių. Bet visos šitos f-lės yra tapačiai teisingos. Todėl tapačiai teisinga ir f-lė E. išvada: teorija neprieštaringa. ∆ tarkime, kad teorija prieštarin-ga. Tada pagal 2.5Ap egzistuoja tokia f-lė A, kad A ir ŲA įrodomos abi kartu. Pagal 2.4T jos yra abi tapačiai teisingos. Tačiau taip būti negali, nes pagal neigimo Ap, kai A=t, tai ŲA=k. LOGINIŲ OPERATORIŲ ĮVEDIMO IR PAŠALINIMO TAISYKLĖS.T. atvirkštinę 2.4T įrodyti yra žymiai sunkiau. Todėl reikia plėtoti teoriją. Iki šiol įvedimo ir išvecimo egzistavimui įrodyti taikėme tik 2 taisykles. Tai MP leidžianti pašalinti ‘Ž’, todėl dar vad. ‘Ž’ pašalinimo taisykle ir deduk. teorema, leidžianti įvesti ‘Ž’, todėl dar vad. ‘Ž’ įvedimo taisykle. Dabar nustatysime ir ki-tų loginų operatorių įvedimo ir pašalinimo taisykles.2.5T. bet kuriai baigtinių f-lių ai-bei G ir bet kurioms f-lėms A, B, C teisingos taisyklės užrašytos lentelėje. Op. Nr. Įvedimas Pavad. Ž 1 jei G,A├B,tai DT G├AŽB IĮŁ 3 A,B├AŁB KĮŚ 6 A├AŚB DĮ1 7 B├AŚB DĮ2Ų 9 Jei G,A├B ir G,A├ŲB,tai G├ŲA RA,NI_ 12 AŽB,BŽA EĮ ├A_BOp. Nr. Pašalinimas Pavad.Ž 2 A,AŽB├B MP,IPŁ 4 AŁB├A KP1 5 AŁB├B KP2Ś 8 Jei G,A├C ir G,B├C,tai G,AŚB├C DPŲ 10 ŲŲA├A NNP 11 A,ŲA├B SNP _ 13 A_B├AŽB EP1 A_B├BŽA EP2Įrodysim kiekvieną taisyklę 1)taisyklė, įvedanti ‘Ž’ buvo įrodyta kaip T.2.3 2) taisyklė, pašalinti ‘Ž’ yra pra-dinė teorijos taisyklė, todėl neįrodoma3-7, 10, 12-14 taisyklės pagrin-džiamos naudojant atitinkamą aksiomų schemą ir MP. Pvz-iu galima laikyti konj. Įvedimo taisyklės įrodymą pateiktą 2.2T įrodyme. 8) yra disj. pašalinimo taisyklėJei G, A├C ir G, B├C, tai G,AŚB├C 1. G,A├C 1.prielaida2. G,B├C 2. Prielaida3. G├AŽC 3. IĮ (1)4. GG├BŽC 4. IĮ (2)5.AŽC,BŽC, 5.Įrodymas bus AŚB├C pateiktas atskirai6.G,AŚB├C 6.Įrodymas bus žemiau 5 eilutę 1’AŽC 1’priel. 2’BŽC 2’priel 3’ AŚB 3’prielaida 4’(AŽC)Ž((BŽC)Ž(AŚBŽC)) 4’ AS65.’ (BŽC)Ž(AŚBŽC) 5.’ MP(1’,4’) 6.’ AŚBŽC 6.’ MP(1’, 5’)7.’ C 7.’MP(3’,6’)6 eilutė1.’ G,AŚB├E,EĪG 1.’2.1Ta2.’ G├AŽC 2.’pagr. įr.3 žings.3.’G,AŚB├AŽC;3.’2.1Tb(2’,1’)4.’G├BŽC 4.’pagr.įr.4 žings.5.’G,AŚB├BŽC;5.’2.1Tb(1’,4’)6.’G,AŚB├AŚB 6.’ 2.1Ta7.’AŽC,BŽC,AŚB├C 7.’Pagr. įrodymo 5 žingsnis8.’G,AŚB├C;8.’2.1Tb(3’,5’,6’,7’9)taisyklė ‘Ų’įved. (savarank.) 11)taisyklė silpno ‘Ų’ pašalini-mas A,ŲA├B1.A,ŲA,ŲB├A 1. 2.1Ta2. A,ŲA,ŲB├ŲA 2. 2.1Ta3. A,ŲA├ŲŲB 3. NĮ(1,2)4. ŲŲB├B 4.NNP5. A,ŲA├B 5. 2.1Tb(3,4) Įrodytosios taisyklės aprašo labai paplitusius samprotavimo būdus. Norint įrodyti konj. struk-tūros sakinį AŁB atskirai įrodo-ma A ir B, o po to sakoma-teore-ma įrodyta, t.y. įrodyta AŁB. frazėje – teorema įrodyta slypi netiesioginis perėjimas nuo A ir B prie AŁB. Pvz.: įrodom sakinį trapecijos vidurinė linija yra lygiagreti su pagrindais ir yra lygi jų sumos pusei. Įrodomas atskirai kiekvienas iš šių sakinių. Konj. Pašalinimo taisyklės taiko-mos jau įrodytiems konjunkcinės struktūros sakiniams. Sakykim, reikia spręsti uždavinį : raskite trapecijos kurios pagrindai A ir C vidurinę liniją. Iš įrodyto sakinio naudojamas tik 2 narys ir randa-ma trapecijos vidurinė linija. Ekvivalencinės struktūros sakinių įrodymas susideda iš 2 etapų:1) AŽB įrodymas ir 2) BŽA įrodymo. Ekvivalencijos pašalinimo taisyklės taikomos jau įrodytiems sakiniams- ekvi-valencijoms. Pvz.: trikampis yra statusis tada ir tik tada, kai jo didžiausios kraštinės kvadratas = kitų dviejų kraštinių kvadratų sumai. Tai ekvivalencija. Pagal taisyklę EP2 gauname- jei trikampio didžiausios kraštinės kvadratas=kitų 2 kraštinių kvad-ratų sumai, tai toks trikampis sta-tusis. Praktikoje dažnai taikomos trumpesnės samprotavimo sche-mos, pagrįstos tokiais išvedimais iš ekvivalencijos: 1)A_B, A├B; 2)A_B,B├A;3) A_B, ŲA├ŲB;4) A_B, ŲB├ŲA; 5) A_B├ŲAŽŲB;6) A_B├ŲBŽŲA;7)AŽB,ŲB├ŲA; (MT)8)AŽB├ŲBŽŲA;(K)kontrapozicija 7)-oji taisyklė įrodoma tokia seka∆ 1)AŽB, ŲB,A├ŲB 1)2.1a2)AŽB,ŲB,A├AŽB 2)2.1a3)AŽB,ŲB,A├A 3)2.1a4)A,AŽB├B 4)MP5)AŽB,ŲB,A├B 5)2.1b(3,2,4)6)AŽB,ŲB├ŲA 6)MĮ(5,1) ▲7-ajam taisymui pritaikę IĮ tai-syklę gausime 8-ąją taisyklę.3)-ioji taisyklė: ∆ 1)A_B,ŲA├A_B 1)2.1a2)A_B├BŽA 2)EP23)A_B,ŲA├BŽA 3)2.1b(1,2)4)A_B,ŲA├ŲA 4)2.1a5)BŽA,ŲA├ŲB 5)7 tais.(MT)6)A_B,ŲA├ŲB 6)2.1b(3,4,5) Teorijoje L kaip ir bet kurioje ak-siominėje teorijoje, turinčioje silpno neigimo pašalinimo, konj. pašalinimo(KP1 ir KP2), galima naudoti lygiavertį 2.5A.2.6Ap. Formalioji aksiominė teorija vad. neprieštaringa, jei jos teorijoje egzistuoja nors viena neįrodoma f-lė. Jei visos f-lės įrodomos, tai teorija vad. priešta-ringa. Iš tikrųjų kad duotoji teorija ne-prieštaringa pagal 2.5Ap. tuomet nėra nė vienos tokios f-lės A, kad A ir ŲA būtų įrodomos vienu metu. Todėl f-lė AŁŲA yra neį-rodoma. Jei būtų įrodoma tai pagal KP1 ir KP2 taisykles būtų įrodomos ir A ir ŲA. tokiu būdu surandame neįrodomą f-lę, todėl pagal 2.6Ap. teorija L neprieš-taringa. Tarkim, kad teorija L nepriešta-ringa pagal 2.6Ap. tuomet egzis-tuoja tokia f-lė B, kuri nėra įrodoma. Vadinasi nė vienai –lei A neturi galioti, kad A ir ŲA yra įrodomos, nes jei taip būtų,tai pagal SNP taisyklę turėtų būti įrodoma ir f-lė B.
TEORIJOS ‘L’ PILNUMASSvarbiausia matematikos problema – neprieštaringumas, kuris buvo išnagrinėtas prieš tai buvusiame skyrelyje.Kita svarbi problema – teorijos pilnumas.Teorija L turi 13 formulių, vadinamų aksiomomis. Kyla klausimas, ar galima prie šių aksiomų prijungti naujas formules, kad įrodymų formulių būtų daugiau. Atsakant į šį klausimą, reikia apibrėžti, kokių savybių formules norime turėti teorijoje. Skirtingas savybes atitiks skirtingo pilnumo sąvokos.Teorijoje L tokia pageidaujama savybe būtų formulių tapatusis teisingumas, nes kiekviena tapačiai teisinga formulė išreškia logikos dėsnius.A 2.7.Logiškai neprieštaringas skaičiavimas vadinamas pilnu tapataus teisingumo požiuriu juo įmanoma bet kuri tapačiai teisinga formulė.Prieš nustatant teorijos pilnuma, įrodysim 4 lemas:L 2.1.Tarkim, kad duoti loginių operatorių ┐, Ł, Ś, Ž, _ apibrėžimai. Kiekvieno iš 5-ių loginių operatorių teisingumo lentelės kiekvienoje eilutėje yra teisingas toks išvadamumas: A ┐A1.k k A ├ ┐┐A2.k t ┐A ├ ┐A A B AŁB3.t t t A, B ├ AŁB4.t k k A, ┐B ├ ┐(AŁB)5.k t k ┐A, B ├ ┐(AŁB) 6.k k k ┐A, ┐B ├ ┐(AŁB) A B AŚB7.t t t A, B ├ AŚB8.t k t A, ┐B ├ AŚB 9.k t t ┐A, B ├ AŚB10.k k k ┐A, ┐B ├ ┐(AŚB) A B AŽB 11.t t t A, B ├ AŽB12.t k k A, ┐B ├ ┐(AŽB)13.k t t ┐A, B ├ AŽB14.k k t ┐A, ┐B ├ AŽB A B A_B15.t t t A, B ├ A_B 16.t k k A, ┐B ├ ┐(A_B)17.k t k ┐A, B ├ ┐(A_B)18.k k t ┐A, ┐B ├ A_B1-os įrodymas:∆1)A, ┐A├ A 1) 2.1 a 2)A, ┐A├ ┐A 2)2.1 a 3)A├ ┐┐A 3)NĮ(1,2)▲9-os įrodymas:∆1) ┐A, B├ B 1)2.1 a 2) B├ AŚB 2)DĮ2 3)┐A, B├ AŚB 3)2.1 b (1,2) ▲15-os įrodymas:∆1) A,B, A├ B 1)2.1 a 2)A, B├ AŽB 2)IĮ(1) 3)A, B, B├ A 3)2.1 a 4)A, B├ BŽA 4)IĮ(2) 5)AŽB, BŽA├ A_B 5) EĮ 6)A, B├ A_B 6)2.1 b (2,4,5)▲16-os įrodymas:∆1)A,┐B, A_B├ A 1)2.1 a 2)A,┐B,A_B├ A_B 2)2.1 a 3)A_B├ AŽB 3)EP1 4)A,┐B,A_B├ AŽB 4)2.1b(2,3) 5)A,AŽB├ B 5)IP(1,4) 6)A,┐B,A_B├ B 6)2.1b(1,4,5) 7)A,┐B,A_B├ ┐B 7)2.1a 8)A,┐B├ ┐(A_B) 8)NĮ(6,7)▲2.1. lemos savybę išplėsime bet kuriai formulei:L 2.2 Bet kurios formulės E, sudarytos iš atomų P1, …, Pn, kiekviena is 2n teisingumo lentelės eilučiu yra teisingas atitinkamas išvedamumas.2.2 lemos, įrodymas pateiktas pavyzdžiu:Tarkim, formulė E yra tokia formulė:PŽ( Q Ś R _ łQ ) ( P,Q,R)=(t,k,k)P, łQ, łR ├ ł( PŽ ( QŚR_łQ))
1 łQ ├ łQ2 P, łQ, łR ├ łQ3 P, łQ, łR ├ łQ4 łQ, łR ├ ł( Q Ś R )5 P,łQ,łR├ łR6 P, łQ, łR├ł( Q Ś R )7 ł( Q Ś R ), łQ├ ł( Q Ś R _łQ )8 P, łQ, łR ├ ł( Q Ś R _ łQ ) 1 2.1 L (2 eilutė) 1 žingsnis2 2.1 a3 2.1 b ( 2,1)4 2.1 L (10 eilutė) 2 žingsnis5 2.1 a6 2.1 b (3,4,5)7 2.1 L (17 eilutė) 3 žingsnis8 2b (6,3,7)4 žingsnis analogiškas 3-iamKonkrečios formulės kokrečiai eilutei taikomas metodas tinkamas kiekvienu atvejuL 2.3 Jei formulė E, sudaryta iš atomų P1, .. ,Pn ir tik iš jų yra tapačiai teisinga, tai galioja tokios aksiomos:P1 Ś łP1 , P2 Ś łP2 , Pn Ś łPn ├ EAnalogiškai galima įrodyti n atvejį. Jei yra n, tai DP reikia taikyti 2k+1+2n-2+..+2+1 kartų.L 2.4 Bet kuriai formuliai A arba łA ęrodoma formulė ├ AŚ łA∆ 1 ł( A Ś łA ), A ├ A Ś łA2 ł( A Ś łA ), A ├ ł( A Ś łA )3 ł( A Ś łA ) ├ łA4 ł( A Ś łA ), łA ├ A Ś łA5 ł( A Ś łA ), łA ├ ł( A Ś łA )6 ł( A Ś łA ), A ├ łA7 ├ ł ł ( AŚ łA )8├ A Ś łA 1 DĮ 12 2.1 a3 NĮ (1,2)4 DĮ 25 2.1 a6 NĮ (4.5)7 NĮ (3.6)8 NNP (7)
T 2.6. Jei formulė E yra tapačiai teisinga, tai ji įrodoma∆ Pagal 2.4 lemą žinoma, kad formulės P1Ś┐P1, P2Ś┐P2, …, PnŚ┐Pn yra įrodomos. Formulė E – tapačiai teisinga, todėl pagal 2.3 lemą ji yra išvedama iš formulių P1Ś┐P1, P2Ś┐P2, …, PnŚ┐Pn. Remiantis gauta išvada ur 2.1 teoremos dalimi, gauname, kad E yra įrodoma.▲Šia teorema baigiasi modelių teorijos ir įrodymų teorijos lygiavertiškumo įrodymas. Dabar galim perrinkti visus rezultatus iš modelių teorijos, keisdami tapataus teisingumo ženklą į įrodomumo ženklą. Tokiu būdu visos formulės, pateiktos 1.3 teoremoje, yra įrodomos. Nors teiginių skaičiavimas, naudojant teisingumo lenteles, atrodo labiau natųralus, tačiau, istoriškai jis parodė vėliau. Pirmiausiai tai padarė amerikiečių matematikas E. Kostas 1921m., įrodęs 2.4 ir 2.6 teoremas, ir lenkų matematikas J.Lukoševičius.Redikatu skaiciavimas1.Lingvistiniai samprotavimai formules , laisvi ir susieti kintamieji.Teiginiu skaiciavimuose mes nagrinejam loginius santykius priklausancius nuo budo, kuriais loginiai teiginiai yra sujungti I tam tikrus blokus. Patys sie blokai nebuvo analizuojami. Predikatu skaiciai. Tuo tikslu ivesim dvi naujas operacijas:“- visuotinumo kvantorius; $egzistavimo kvantorius
panagrinekim teigini “Sokratas yra zmogus”. Sio teiginio dalis isreiksta konstrukcija “-yra zmogus” arba “X yra zmogus” vad. predikatu. Ziurint is matematiniu poziciju, predikatas yra isreiskiamas teigianciaja junkcija, kurios reiskiniu aibe yra teiginiai.si funkcija kekvienam kintamojo X reiksmiai pateikia tam tikra teigini. Jei X yra “sokratas” tai teiginys bus teisngas. Jei X bus “seironas “ tai teiginys bus klaidingas . teiginys taip pat bus kalidinghas jei vietoj X istatysim koki nors daikta. “Jonas myli Onute”. Tai teiginys kuris gali buti sudarytas is 3 tokiu funkciju: “X myli Onute”,”Jonukas myli Y”,”X myli Y”. mes vadinsime predikatu bet kokia teigiancia funkcija, esant bet kokiam n , n>=0 objektu vadinsime bet kuria X, Y reiksme. Jei n=0 tai predikatas yra teiginys. Jei n=1 tai predikatas atitinka tai , kas yra savybe. Jei n=2 tai predikatas yra dvejetainis rysis( jei n=3 … trejetainis ir t.t.)kintamieji israiskose naudojami kaip loginiai, vietoj kuriu galima istatyti reiksmes . Vietoj kintamuju nebutina statyti vardus, galima sakyti ir taip:a)kazkas myli Onute b) niekas nemyli Onutes c) visi myli Onute d) kekvienas ka nors myli e) ka nors visi myli f) kekvienas myli save g) nera tokio kuris nemyletu saves. Pazymekime L( X, Y) teigini “ X myli Y”, tuometa) $ X L(X, Onute) b) Ų$ X L(X, Onute) c) ” X L( X, onute) d) ” X $ Y L ( X, Y )e) $ Y ” X L ( X,Y) f) “X L(X,X) g) Ų$XŲL(X,X) teiginiu logikoje ziamiausias lygis buvo – atomai. Predikatu logikoja zemiausias israusku lygis vad. elementariomis predikatu israiskomis , arba jonais.P, P(-), P(-,-), P(-,-,-)Q,Q(-), Q(-,-), Q(-,-,-)P- zymi nulvieti jona, P(-) – vienvieti jona ir t.t.Israiskas su kintamaisiais pvz: P(x,y,z ), P(y,z,x), P(u,v,w) ir t.t. vad skirtingomis 3-viecio jono ivardinimo formomis. Ivardinimo formu kintamieji turo buti skirtingi. Ivardinimo formos P(x,y,z ), P(y,z,x), P(u,v,w) vad. elementariomis predikatinemis israiskomis su duotais kintamaisiais.Dabar jau galime aprasyti sakiniu klase , kuir gales buti formuojama is jonu. Koks bebutu n-vietis jonas P(-…-) ir koks bebutu sakinys nebutinai skirtingu kintamųjų r1, r2,..rn išraišką P(r1,r2…rn) vad. Elemntaria formule arba atomu. Formulių klasę sudaro visos elementarios formulės ir sudėtinės formulės, kurios gaunamos iš elementarių formulių daugkartinių loginių simolių panaudojimo.”,$,,Ł,Ś,Ž,_. Jei A, B yra elementarios formulės, tai A, AŁB, AŚB, AŽB, A_B yra sudėtinės formulės. Jei A yra formulė, o x kintamasis, tai “xA, $xA yra sudėtinės formulės. Kvantorių prioritetasyra didesnis už aukčiau žinomų log. Operacijų prioritetus. “xAŽB, tai reiškia (“XA)ŽB, o jei norim kitaip, reikia rasyti su ( ) “X(AŽB). Kintamasis esantis po kvantoriaus zenklu, vad. susietu kintamuoju. Kintamasis kuris neturi su juo susijusio kvantoriaus, vad, laisvuoju kintamuoju. Panagrinekim formule “X(P(X)L$XQ(X,Z)Ž$YR(X,Y)VQ(Z,X). formules dalije $XQ(X,Z), X susietas kvantoriumi $XSi susietuma galima zymeti visiems formules X-ams, suteokiant indeksa 1. Indeksas 2, 3 galima pazymeti kintamuosius, susietus kvantoriais $Y ir “X . formules nagrinejimas prasideda nuo giliausio lygio. Esant tam paciamlygmenyje keliems kvantoriams , nagrinejams kairiausias dar nepazymetas kvantorius. Tuomet musu formule atrodys taip:“X3(P(X3)L$X1Q(X1,Z)Ž$Y2P(X3,Y2))VQ(Z,X)kintamieji kurie neturiindeksu yra laisvidar viena formule “Y(P(Y)L$XQ(X,Z)Ž$ZR(Y,Z))VQ(Z,X). sudeja inde-ksus : “Y3(P(Y3)L$X1 Q(X1,Z)Ž$Z2 R(Y3,Z2))VQ(Z,X) nutrinam kintamuosius kurie turi indeksus “3(P(3)L$1 Q(1,Z)Ž$2 R(3,2))VQ(Z,X)“3(P(3)L$1 Q(1,Z)Ž$2 R(3,2))VQ(Z,X)pastebesim kad sios 2 formules yra lygevertes. Dar karta perasom be indeksu ir susietuma pakeiciam “– “1) “X(P(X)L$XQ(X,Z)Ž$YR(X,Y)VQ(Z,X).2) “Y(P(Y)L$XQ(X,Z)Ž$ZR(Y,Z))VQ(Z,X).ir dar 3 formules . pagal schematini sujungima galima spresti , kad sios formules yra lygiavertes.3) “X(P(X)L$XQ(X,Z)Ž$XR(X,X)VQ(Z,X).4) “Z(P(Z)L$XQ(X,Z)Ž$YR(Z,Y)VQ(Z,X).5) “X(P(X)L$XQ(X,Z)Ž$YR(X,Y)VQ(Z,Y).(5) nera lygeverte (1) ir (2), nes nesutampa laisvuju kintamuju vardai. Kintamuju apibrezimo sritis. Tapatusis teisingumas .Teiginiu logikoje mes sakome, kad kekvienas atomas isreiskia koki nors teigini, kuris yra tiesa arba melas. Analogiskai sakome kiekvienam klasikiniam skaiciavime apie kekviena jona. Taciau , kad butu ka nors galima teigti apie n-vieti jona, pirmiausia reikia nustatyti is kokios srities reiksmes gali igyti kintamieji. Sakykim kad ta sritis yra tam tikra ne tuscia aibe poziuriu D. Dabar galima sakyti , kad predikatai isreiksti jonu P(-,,-) arba yvardijimo forma P(r1,…,r n) tampa teiginiu bet kokiam kintamojo r1,..r n reiksmems is aibes D. Pvz . galima naudotis predikatu X0)1)Pvz D sriti sudaro du objektai kuriuos pazymesim skaiciais 1 ir 2. Tai yra D= {1,2} sakysim mums reikia sudaryti teisngumo lentele tokiai formuliaiP(Y) V”X(P(X)ŽQ) sudarant sios formules teisingumo lentele mums reikia vienvietes logines funkcijos attitinkancios P(X), nulvietes atitinkancios Q ir elementu is D atitinkanciu laisvaji kintamaji Y. tures 3 iejimo stulpelius . norin sudaryti lentele reikia sudaryti vienviete funkcija X g1 g2 g3 g41 t T k k2 t k t k