Logika ir teisingumas

SUTRUMPINTOS TEISINGUMO LENTELĖS Mes 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  pradinę teisingumo lentelę. Jeigu mes formulei A priskiriame reikšmes t arba k, tai esant fiksuotoms A reikšmėms A  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~B B~A AB BA T B B t K B t B Lentelės (  ) tęsinys (  ) AB BA AB BA A B t k k B t Pavyzdž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  R toliau kai R yra t: Q  t  t t  k k kai R yra k: Q  k  k Q  t t Pateikta formulių sistema vadinama analize pagal teisingumą. Šį metodą pritaikė 1950 m. W. van O. Quine. PAGRINDINĖS IŠPLAUKIMO TAISYKLĖS G. Geutzeu (kažkoks austras) Šios taisyklės yra dedukcinių samprotavimų pagrindas. 1 Jei iš , A╞ B, tai ,╞ A  B (implikacijos įvedimas) Ši taisyklė įveda implikaciją, jeigu įrodyta, kad iš A╞ B. Galbūt dar darant kitas prielaidas (aibė ) ši taisyklė plačiai naudojama įrodymuose. Tarkim, kad reikia įrodyti implikacinės struktūros sakinį A  B. ??? prie jo įrodytų sakinių  prijungiamas sakinys A ir tada iš  ir A išvedama B. Po to sakoma, kad teorema įrodyta. Toks formulavimas ir nusako, kaip taikoma implikacijos įvedimo taisyklė, t.y. , A╞ B prie išplaukimo ,╞ A  B. 2 Jeigu , A╞ C ir , B╞ C, tai , 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 , A╞ C ir , B╞ C. 1) P  (Q  R) = t 2) P  Q = P ~ Q 3 Jeigu iš , A╞ B ir , A╞ B, tai iš ╞ 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  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 , A╞ B ir , A╞ B, tai ╞ t. 4 Jeigu iš ╞ A ir ╞ A  B, tai ╞ 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š ╞ A, tai ╞ AB (pirmasis disjunkcijos įvedimas) 6 Jeigu iš ╞ B, tai ╞ 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 KALBAI NATŪRALIOS KALBOS SAKINIŲ UŽRAŠYMAS MATEMATINĖS LOGIKOS KALBA Natū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 = 2n + u (kur 0  u 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  bet kuri formulių aibė, tuomet: a) jei  |- A=>B, tai , 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  galima paversti formulės B išvedimu iš aibės  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..An 3n-4. A1...An |- A1 3n-3. A1...An |- A1...An. Iš 2.2, 2.1 pagal 2.1T b) dalį gauname A1....An |- B. ĮRODYMŲ TEORIJA. DEDUKCIJOS TEOREMA Dedukcijos 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š ,A├B, tai ├AB b)jeigu iš A├B, tai ├AB Pagal teoremos sąlygą egzistuoja formulės B išvedimas. B1 ,…,Bm Kur Bm=B iš formulių aibės,  ir A, t.y. duotasis išvedimas. Reikia įrodyti, kad egzistuoja formulės AB išvedimas iš formuliu aibės , 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 . Tačiau prieš kiekv. formulę ABI galima įrašyti papild. formules taip, kad formuliu seka pavirstų gaunamuoju išvedimu iš formulių aibės . 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  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 . Š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 formules Pvz.: 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.) AS4a 9.ABA 10.(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 įrodoma 9.├(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C už įrodymo ženklo yra …. 6.A(BC), B,A ├C norint 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) prielaida 2.B prielaida 3.A prielaida 4.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ŠTARINGUMAS Apibendrinant 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  ir bet kurioms f-lėms A, B, C teisingos taisyklės užrašytos lentelėje. Op. Nr. Įvedimas Pavad.  1 jei ,A├B,tai DT ├AB IĮ  3 A,B├AB KĮ  6 A├AB DĮ1 7 B├AB DĮ2  9 Jei ,A├B ir ,A├B,tai ├A RA,NI  12 AB,BA EĮ ├AB Op. Nr. Pašalinimas Pavad.  2 A,AB├B MP,IP  4 AB├A KP1 5 AB├B KP2  8 Jei ,A├C ir ,B├C,tai ,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įrodoma 3-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 , A├C ir , B├C, tai ,AB├C 1. ,A├C 1.prielaida 2. ,B├C 2. Prielaida 3. ├AC 3. IĮ (1) 4. ├BC 4. IĮ (2) 5.AC,BC, 5.Įrodymas bus AB├C pateiktas atskirai 6.,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’ AS6 5.’ (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.’ ,AB├E,E 1.’2.1Ta 2.’ ├AC 2.’pagr. įr.3 žings. 3.’,AB├AC;3.’2.1Tb(2’,1’) 4.’├BC 4.’pagr.įr.4 žings. 5.’,AB├BC;5.’2.1Tb(1’,4’) 6.’,AB├AB 6.’ 2.1Ta 7.’AC,BC,AB├C 7.’Pagr. įrodymo 5 žingsnis 8.’,AB├C;8.’2.1Tb(3’,5’,6’,7’ 9)taisyklė ‘’įved. (savarank.) 11)taisyklė silpno ‘’ pašalini-mas A,A├B 1.A,A,B├A 1. 2.1Ta 2. A,A,B├A 2. 2.1Ta 3. A,A├B 3. NĮ(1,2) 4. B├B 4.NNP 5. 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.1a 2)AB,B,A├AB 2)2.1a 3)AB,B,A├A 3)2.1a 4)A,AB├B 4)MP 5)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.1a 2)AB├BA 2)EP2 3)AB,A├BA 3)2.1b(1,2) 4)AB,A├A 4)2.1a 5)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’ PILNUMAS Svarbiausia 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 ┐A 1.k k A ├ ┐┐A 2.k t ┐A ├ ┐A A B AB 3.t t t A, B ├ AB 4.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B 7.t t t A, B ├ AB 8.t k t A, ┐B ├ AB 9.k t t ┐A, B ├ AB 10.k k k ┐A, ┐B ├ ┐(AB) A B AB 11.t t t A, B ├ AB 12.t k k A, ┐B ├ ┐(AB) 13.k t t ┐A, B ├ AB 14.k k t ┐A, ┐B ├ AB A B A~B 15.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~B 1-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 ├ Q 2 P, Q, R ├ Q 3 P, Q, R ├ Q 4 Q, R ├ ( Q  R ) 5 P,Q,R├ R 6 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 žingsnis 2 2.1 a 3 2.1 b ( 2,1) 4 2.1 L (10 eilutė) 2 žingsnis 5 2.1 a 6 2.1 b (3,4,5) 7 2.1 L (17 eilutė) 3 žingsnis 8 2b (6,3,7) 4 žingsnis analogiškas 3-iam Konkrečios formulės kokrečiai eilutei taikomas metodas tinkamas kiekvienu atveju L 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 ├ E Analogiš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  A 2 ( A  A ), A ├ ( A  A ) 3 ( A  A ) ├ A 4 ( A  A ), A ├ A  A 5 ( A  A ), A ├ ( A  A ) 6 ( A  A ), A ├ A 7 ├   ( A A ) 8├ A  A 1 DĮ 1 2 2.1 a 3 NĮ (1,2) 4 DĮ 2 5 2.1 a 6 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 skaiciavimas 1.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”, tuomet a)  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)XQ(X,Z)YR(X,Y)VQ(Z,X). formules dalije XQ(X,Z), X susietas kvantoriumi X Si 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)X1Q(X1,Z)Y2P(X3,Y2))VQ(Z,X) kintamieji kurie neturiindeksu yra laisvi dar viena formule Y(P(Y)XQ(X,Z)ZR(Y,Z))VQ(Z,X). sudeja inde-ksus : Y3(P(Y3)X1 Q(X1,Z)Z2 R(Y3,Z2))VQ(Z,X) nutrinam kintamuosius kurie turi indeksus 3(P(3)1 Q(1,Z)2 R(3,2))VQ(Z,X) 3(P(3)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)XQ(X,Z)YR(X,Y)VQ(Z,X). 2) Y(P(Y)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)XQ(X,Z)XR(X,X)VQ(Z,X). 4) Z(P(Z)XQ(X,Z)YR(Z,Y)VQ(Z,X). 5) X(P(X)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 X

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!