Buvo manoma, kad visi ilgiai ir pločiai gali būti bendramačiai.Va.pr.Kr. atrasta, kad kvadrato įstrižainė neturi bendro mato su kraštine. Nebendramačiai dydžiai: apskritimo l ir d, kvadrato ir apskritimo, apie jį apibrėžto, plotai. Krizių pabaiga – 370 m.pr.Kr. Tai siejama su Eudoksu (graikas). Sukurti nauji skaičiai – iracionalūs (proto nesuvokiami). Antroji krizė – matematinės analizės. XVIIa.pab. Niutono ir Leibnico mokiniai mažai rūpinosi analizės pagrindais. Rezultatai rėmėsi neaiškiu be galo mažų dydžių aiškinimu. Krizė kilo dėl šios sąvokos neaiškumo. Be galo mažas dydis buvo prilyginamas 0 ir jis buvo atmetamas. Kitais kartais reikšmė 0. XIXa. Atsisakyta tos teorijos. Koši pakeitė griežta ribų teorija. Antros krizės pabaiga siejama su šia teorija. Xxa. grįžtame prie labai mažų dydžių sąvokos patikslinimo. 1960 m. Robinsonas pasiūlė kaip pagrįsti XVII – XVIIIa. Analizę. Pasiūlyta į be galo mažus dydžius žiūrėti kaip į pastovius. Taip kūrėsi matematinė analizė. Robinsonas įvedė be galo mažų ir didelių skaičių sąvokas. Kuriasi kitokia matematinė analizė – nestandartinė analizė. Trečioji krizė prasidėjo 1897 m., kai pasirodė C. Burali – Forti darbai. Atrasti aibių teorijos prieštaravimai. PVZ.: 1.Tarkim, kad kirpėjas skuta visus, kurie patys nesiskuta. Ar kirpėjas pats skutasi? Tarkim, kad jis nusiskuta. Gaunam prieštaravimą, nes jis yra to kaimo gyventojas. Tarkim, kad jis nesiskuta, bet pagal apibrėžimą jis privalo skustis. 2. Vienas sako: “Viską, ką aš kalbu – melas”. Tai melas ir šis jo posakis. O tai reiškia, kad ne viskas, ką jis pasako yra melas. Bet tai irgi prieštaravimas.Tiksliosios matematikos paradoksai: tarkim x bet kuri aibė. Tai aibę A apibrėžiame taip: x priklauso A, tada ir tik tada, kai x nepriklauso x. Tuo atveju, kai x sutampa su A gaunam prieštaravimą. Kadangi aibių teorijoje buvo aptikta paradoksų, tai reiškia yra ne viskas gerai. Ji remiasi į daug mat. šalių. Dėl to susvyravo matematikos pagrindai trečią kartą. Manyta, kad paradokso priežastis slypi logikoje. Įkurta visapusiška logikos pagrindų analizė. Logika nagrinėja žmogaus mąstymo formą. Ji vystėsi kaip f-jos mokslo šaka. Susiformavo IVa.pr.Kr. Ją sukūrė Aristotelis. Logikos mokslas laikui bėgant nesivystė. Tai įrodo graiko genialumą, todėl logika vadinama sustingusiu mokslu. Dėl to į ją žiūrėta skeptiškai. Tik XVIIa. Leibnicas sukūrė logiką – skaičiavimo meną. Joje kiekvienai sąvokai būtų priskirtas simbolis, o samprotavimai įgytų skaičiavimo pavidalą, tačiau tai nebuvo suprasta ir pritarta. Idėja nepaplito ir nesivystė. Tik XIXa. vid. G.Boole įgyvendino Leibnico idėją. Jis sukūrė logikos algebrą, kurioje veikiantys dėsniai yra panašūs į įprastinius algebros dėsnius. Tik čia raidėmis žymimi ne skaičiais, o teiginiai. Bulio algebra – matem. logikos pradininkė. Skirtingai nuo matematinės logikos logika sukurta Aristotelio vad. tradicine formaliąja logika.Matematinės logikos bruožai: 1) M.L. – logika, taikanti matematinę kalbą ir metodus. 2) M.L. – matematikos mokslo šaka, atsiradusi dėl matematikos poreikių. XXa. atrastas glaudus M.L. ryšys su kibernetika. Šio ryšio atradimas atvėrė daugybę M.L. taikymų. Ji naudojama medicinoje, lingvistikoje, kompiuterių moksle ir gamyboje. Ji patikslino formaliosios logikos metodus ir išplėtė jos taikymo sritis.TEIGINIŲ LOGIKA1.1 TEIGINIAI IR LOGINĖS OPERACIJOSTeiginys – sakinys, kuris arba teisingas arba klaidingas. Jis yra pirminė teiginių logikos sąvoka. Jei jis atitinka tikrovę, tai jis yra teisingas, jei ne – klaidingas. Visi teiginiai skirstomi į teisingus ir klaidingus. Ne kiekvienas sakinys yra teiginys. Klausiamieji ir šaukiamieji sakiniai – ne teiginiai. Jais negali būti ir sakiniai, kurie neturi vieningos nuomonės. Sakinys a2=4 irgi gali būti teiginiu, jei a turėtų kokią nors reikšmę. Sakinys, turintis nors vieną kintamąjį, įstačius vietoj jų reikšmes, tampantis teiginiu vadinamas teiginio forma. Iš teiginio fomų teiginius gauname ne tik įstatant vietoj kintamojo reikšmes. Galima panaudoti spec. žodžius: kiekvienas, bet kuris, egzistuoja, nors vienas. Sakiniai gali būti elementarūs ir sudėtiniai. Iš elementarių sudaromi sudėtiniai sakiniai vartojant jungtukus ir, o, bet, kad.
Gramatikoje sakiniai – paprasti ir sudëtiniai. Paprastas sakinys gramatinë struktûra gali bûti sudëtinis logikos poþiûriu
PVZ: 2 tiesës lygiagreèios arba kertasi.Ar sudëtinis sakinys tampa teiginiu, jei já sudarantys sakiniai yra teiginiai?PVZ: skaièius 2 pirminis arba lyginis. Tai 2 teisingi teiginiai. Taèiau teisingumas nustatomas jungtuko arba reikðmæ iðsiaiðkinus. Jei jis vartojamas alternatyvø iðjungiamàja prasme, tai sakinys klaidingas. Taèiau, jei gali galioti abi alternatyvos, tai sakinys teisingas.Matematinëje logikoje kad jungtukai turëtø tà paèià prasmæ, reikðmæ apibrëþiama ið anksto ir vienareikðmiðkai. Todël bet koks sakinys, sudarytas ið teiginiø, sujungtø jungtukais, yra taip pat teiginys.Neigimas Já atitinka jungtukà “ne”. Galima vartoti ir posaká “netiesa, kad …”Sakinys, neturintis formokiø neigimo poþymiø, bet turintys tokià pat prasmæ kaip neigimo sakinys, bus laikomas sakinio neigimu.Konjunkcija A B ABT t TT k KK T KK k KSakinys AB teisingas tik tada, kai abu A ir B yra teisingi. PVZ: rytoj bus ðiltas oras ir nelis lietus. Konjunkcija þymima “ir”, o kartais “o”Disjungcija A B ABT t TT k TK T TK k KJungtuku “arba” nepaskiriama iðjungiamoji alternatyvø prasmëPVZ: skaièius 2 pirminis arba lyginis (teisingas)Implikacija A B ABT t TT k KK T TK k KPVZ: jei n/4 be liekanos, tai ir n/2 be liekanos.Teisingais reikia laikyti tokius teiginius:Jei 16/4 be liekanos, tai irgi dalinasi 16/2 be liekanos. Tai I lentelës eilutë, jei 18/4 be liekanos, tai be liekanos 18/2 (III eilutë),Jei 17 (IV eilutë). Implikacija A vadiname antecedentu, o B – konsekventu.Ið apibrëþimo seka:1. implikacija su neklaidingu A yra visada teisinga2. implikacija su teisingu B teisinga3. implikacija klaidinga tada ir tik tada, kai jos A teisingas, o B klaidingasTai jungtuko “jei … tai”atitikimasPVZ: 2*2=4, tai Vilnius – sostinë; jei 2*2=5, tai egzistuojaraganosloginiø operacijø apibrëþime sakiniø prasmë nevertinama, todël sakiniai teisingi teiginiai.Ekvivalencija Tai loginë operacija, atitinkanti jungtukà “tada ir tik tada“.A B ABT t TT k KK T TK k KKai sakome A tada ir tik tada kai B, galvojame, kad abu teiginiai vienu metu yra arba teisingi arba klaidingi.PVZ: Að vaþiuosiu á Talinà tada ir tik tada, kai tu vaþiuosi á Rygà. Tvirtinu, kad ávyks tas ir kitas arba neávyks nieko.Teiginiø logikos abëcëlë ir formulësTeiginiø logikoje teiginiai vadinami atomais. Juos þymësime didþiosiomis raidëmis, pradedant P, Q, R ir t.t. Jei reikës naudosime indeksus P1, P2 … Laikysime, kad skirtingo turinio raidës reðkia skirtingus atomus.Sudëtiniai teiginiai – molekulës, ir þymimi A, B, C … Molekulës sudaromos ið atomø, sujungtø loginëmis operacijomis. Atomø þymëjimas, loginiø operacijø simboliai ir apvalûs skliaustai sudaro teiginiø logikos abëcëlæ.Teiginiø logikos abëcëlë vadinama aibë, kuri þymima ATL={P,Q,R,..Z, P1, P2, …,,,,,,(,)}Abëcëlës elementai vadinami raidëmis. ATL baigtinës raidþiø sekos – þodþiai. Kai kurie þodþiai yra teiginiø logikos formulës.a) P,Q,R,..Z, P1, P2 – formulësb) Jeigu A yra formulë, tai (A) irgi formulëc) Jeigu A ir B yra formulës, tai (AB) taip pat formulësd) Kitø formuliø, iðskyrimus, iðvardintas a punkte ir sudarytas pagal b ir c punktus nëra.A punkto formulës – elementarios arba atomai, o formulës gautos pagal b ir c – sudëtinës arba molekulës. Naudojant kintamuosius ir loginiø operacijø þenklus, teiginius galima formalizuoti, t.y. reikia atlikti formuliø iðreiðkianèià jo loginæ struktûrà.Formalizavimo procedûra:1. jei teiginys elementarusis, jam atitinka elementari formulë2. jei sudëtinis, tai reikia:a) iðsiaiðkinti visus elementarius teiginius ir jungtukusb) pakeisti juos atitinkamais simboliaisc) sudëti skliaustus atitinkamai pagal teiginiø prasmæ1,2 apibrëþimai vadinami efektyviu, jei já naudojant baigtiná þingsniø skaièiø galima nustatyti, kur þodis – formulë, o kur ne.
Skliaustų rašymo taisyklės. 1)Nerašysime išorinių skliaustų2)Nerašysim visų skliaustų jei log. Operacijos atliekama tokia tvarka:,,,,.Kalba ir metakalba Sakinių formų formalizavimą galima nagrinėti kaip vertimą iš natūralios į spec. dirbtinę log. kalbą.
Verčiant iš vienos natūraliosios kalbos į kitą laikomasi sakinių prasmės. Struktūra gali keistis.Verčint į log. kalbą sakinių prasmė prarandama, bet struktūra išlaikoma.Yra daug dirbtinių kalbų. Dirbtinė kalba reikalinga tuomet kai daugiareikšmiškumas būdingas natūralioms kalboms yra nepriimtinas.Tiap atsitinka bendraujant su kompiuteriu, kuris negali išrinkti iš keleto reiškinių tinkamą,remiantis sveiku protu.Žodžių ir išraiškų daugiareikšmiškumas yra nesuderinamas su loginės kalbos tikslumu.Dirbtinės kalbos sukurtos loginiams poreikiams vad. formalizuotomis. Ji sudaroma taip: pirmiausia sudaroma abėcėlė, po to nusakomi indeksai. Tai taisyklių rinkinys išskiriantis iš visų formų k. žodžių žodžius vad. formulėmis.Tokia formalizuota kalba yra teiginių logikos kalba. Ji turi apibrėžimą, kuris nusako, kokios simbolių sekos yra formulės.Formulės apibrėžime naudojami lietuviški žodžiai ir simboliai. Kurie neįeina į teiginių logikos abėcėlę. Formalizuota kalba apibrėžta per neformalizuotą kalbą.Kai kalbame apie kalbą e1 kalboje e2 tai e2 e1 kalbos atžvilgiu vad. metakalba. O e1 – e2 atžvilgiu – kalba – objektu.Teiginių logikos atveju simboliai A,B ir lietuvių kalba yra metakalba log. kalbos atžvilgiu.Kartais kalbos objekto ir metakalbos žodžiai naudojami iš to pačio šaltinio.Formulių teisingumo lentelių sudarymas Sakysim, kad formulė A susideda iš P1…Pn atomų. Kadangi kiekvienas atomas gali įgyti 1 iš 2 galimų reikšmių (t ar k), tai n atomų rinkinys gali įgyti 2n reikšmių.Ap.1.3 Teiginių logikos formulės A interpretacija vad. bet kokį į formulę A įeinančių atomų teis. reikšmių rinkinį.Formulė pati įgyja vieną iš dviejų teisingų reikšmių (t ar k), kuri gaunama atlikus visas log. operacijas, nurodytas formulėje.Tarkim reikia apskaičiuoti formulės teisingumo reikšmę.(PQR)SQ (P,Q,R,S) = (t,t,k,t). Galima apiforminti taip, kad pradinės sąlygos būtų rašomos žemiau atitinkamų atomų, o operacijos rezultatas – žemiau operacijos ženklo.(PQR)SQ t t k t t k t t k tKaratais reikia rasti visų galimų form. Interpretacijų teisingumo reikšmes.1.4Ap.Lentelė, kurioje parašytos visos galimos formulės interpretacijos ir šias interpretacijas atitinkančių formulių reikšmės, vad. formulių teisingumo lentele.Bet kuri formulė apibūdinama teisingumo lentele. Ji gali atitikti ir ne vieną formulę.Formulių ekvivalentiškumas 1.5Ap. Formulės A(P1…..Pn) ir B(P1….Pn) vad. ekvivalenčiomis, jei įgija vienodas reikšmes, esant bet kokioms kintamųjų P1…Pn reikšmėms. Žymima: Akivaizdu jog ekvivalenčios formulės turi vienodas teisingumo lenteles ir atvirkščiai. Ekvivalenčių formulių savybės: a) bet kuriai formulei A tenkinama sąlyga AA;b) bet kurioms formulėms A ir B, jeigu AB, tai BA;c) bet kurioms formulėms A,B,C, jei AB, BC, tai AC. Apibendrinimas atvejui, kai į formules įeina ne tik vienodi loginiai kintamieji.1.6Ap Formulės A(P1,…,Pn, Q1,…,Qs) ir B(P1,…,Pn,R1,…,Rt) vad. ekvivalentiškomis, jei esant bet kurioms loginėms kintamųjų (P1,…,Pn,Q1,…,Qs, R1,…,Rt) reikšmėms A ir B įgija vienodas reikšmes.1.7Ap Kintamasis Pi formulėje A(P1,…,Pi-1,Pi,Pi+1,…,Pn) vad. fiktyviu jei esant bet kuriai sekai 1,…,i-1,i+1,…,n, kur j(t,k), A(1,…,i-1,t,i+1,…,n) = =A(1,…,i-1,k,i+1,…,n) Priešingu atveju Pi vad. esminiu. Teisingumo funkcijos Kiekvienoje interpretacijoje formulė įgyja 1 iš 2 teisingumo reikšmių: t arba k. Kitaip tariant formulė apibrėžia {t,k}n{t,k} pavidalo funkcija.1.8Ap Funkcija {t,k}n{t,k} vad. n – viete teisingumo funkcija arba teiginių logikos funkcija.Dvi ekvivalentiškos formulės apibrėžia vieną teisingumo funkciją. Iš n atomų rinkinio galima sudaryti sukaičiuojamą formulių aibę. Visos šios apibrėžia baigtinę teisingumo funkcijų aibę.Formulių klasifikacija Teiginių logikoje kai kurios formulės turi spec. pavadinimus. 1.9Ap. Formulė A vad. tapačiai teisinga jeigu visoms savo interpretacijoms įgyja reikšmę t.Tapačiai teisinga formule vad. teiginių logikos dėsniu.Juo vad. ir pora ekvivalenčių formulių.1.10Ap. Formulė A vad. tapačiai klaidinga , jei visoms savo interpretacijoms įgyja reikšmę k.1.11Ap. Formulė A vad. neutralia, jei ji nėra nei tapačiai teisinga, nei tapačiai klaidinga.1.12Ap. Formulė A vad. įvykdoma, jei ji tapačiai teisinga arba neutrali.1.13Ap. Formulė A vad. netapačiai teisinga, jei ji tapačiai klaidinga arba neutrali.Tik t Nors viena t ar k Tik kTapačiai teisingos Neutralios Tapačiai klaidingosĮvykdomos NeįvykdomosTapačiai teisingos Netapačiai teisingosSvarbiausios tapačiai teisingų formulių savybės Tapačiai t. formulės išreiškia logikos dėsnius. Jos teisingos ir nesvarbu ar ją sudarančios formulės teisingos.Pvz. Bet kurioje formulėje A formulių schema AA įgyja t reikšmę nepriklausomai nuo A reikšmės. Ištikrųjų, jei A=t, AA įgyja t reikšmę. Ši išnagrinėta formulių scheme išreiškia logikos dėsnį – trečio negalimo dėsnį. AA nėra formulė nes A yra metaženklas. Užrašas išreiškia bendrą schemą , jei vietoj A įrašoma kitos formulės. AA vad. formulių schema. Sakinio formulę E tap. Teisingą žymėsime FE.F AA tai reiškia kad bet kuri formulė gaunama iš tos schemos yra tap. teisinga.Norint patikrinti ar formulė A(P1,…,Pn) yra tap. teisinga, reikia sudaryti teisingumo lentelę ir patikrinti ar paskutineme stulpelyje yra vien tik t reikšmės. Sudarant teis. lentelę reikia apskaičiuoti formulės A reikšmę 2n kintamųjų reikšmių rinkiniams. Tai labai greitai auganti funkcija. Todėl praktiškai galima naudotis teis. lentele tik nedidelėms n reikšmėms.Tarkime, kad formule A (P1,..,Pn) yra teisinga, o B1,..,Bn – bet kokios formules, tuomet A(B1,..,Bn) yra teisinga.Irodymas. Priskirkim elementu teiginiams, sudarantiems formules B1,..,Bn, bet kokias reiksmes. Tarkim, kad esant toms reiksmems: B1=a1,..,Bn=an, kur a priklauso {t,k}.Tuomet formules A(B1,B2,..,Bn) reiksme, esant toms pacioms loginems reiksmemssutaps su formules A(a1,..,an) reiksmemis. Kadangi formule A(P1,P2,..,Pn) igyjareiksme ‘t’, esant bet kokioms elem. reiskiniu reiksmems, tai ji igys reiksme ‘t’ ir kai P1=a1,..,Pn=an.Irodyta.Formule A gali pasikartoti formuleje B kelis kartus. Tarkim A1, A, B- bet kokios formules ir A yra A1 sudetyje. Tuomet pazymesime A1[A->B], formule, kuri gauta is A1, pakeitus kuria nors A formule B.Tarkim A1 yra tokia formule (P=>Q)=>((-P-Q)=>Q)A: -PQB: QRTuomet A1[A->B]: bus formule (P=>Q)=>(QR=>Q)T.1.2. Jeigu A ir B – ekvivalentines formules, tai formules A1[A->B] ir A1 irgiyra ekvivalencios.Irodymas.Sudarykime A1 teisingumo lentele taip, kad pirmiausia joje butu apskaiciuojama A reiksme.Analogiskai, A1[A->B] ir pradziu apskaiciuojamos B reiksmes.Tuomet gali skirtis tik A1[A->B] ir A1 teisingumo lenteles reiksmemis iki stulpeliu A ir B. O visos reiksmes desineje lenteles puseje sutampa, nesA ir B ekvivalencios. Tuo pacius ir sutampa ir A1 bei A1[A->B] reiksmes.Irodyta.
T.1.3. Esant bet kokioms formulems A,B,C tolesnes formuliu schemos zhymitapaciai teisingas formules.1) Loginio operatoriaus ivedimo ir pasalinimo schemos.1.a. |= A=>(B=>A)1.b. |= (A=>B)=>((A=>(B=>C))=>(A=>C))3. |= A=>(B=>AB)4.a. |= AB=>A4.b. |= AB=>B5.a. |= A=>AB5.b. |= B=>AB6. |= (A=>C)=>((B=>C)=>(AvB=>C))7. |= (A=>B)=>((A=>-B)=>A)8. |= A=>A9. |= (A=>B)=>((B=>A)=>(A=>B))10.a. |= (A~B)=>(A=>B)10.b. |= (A~B)=>(B=>A)2) Loginiu operaciju isreiskimas kitomis.14. |= (A~B)~(A=>B)(B=>A)15. |= A=>B~-AB16. |= A=>B~-(AB)17. |= AB~-(AB)18. |= AB~(A=>B)19. |= AB~(-AB)20. |= AB~A=>B3) Perstatomumo (komutatyvumo) desnis.21. |= AB~BA22. |= AB~BA23. |= (A~B)~(B~A)4) Jungiamumo (asociatyvumo) desnis.24. |= (AB)C~A(BC)
25. |= (AB)C~A(BC)26. |= ((A~B)~C)~(A~(B~C))5) Skirstomumo (distrybutyvumo) desnis.27. |= A^(BvC)~A^BvA^C28. |= Av(B^C)~(AvB)^(AvC)29. |= Av(B=>C)~AvB=>AvC30. |= Av(B~C)~A~B~A~C31. |= A=>B^C~(A=>B)^(A=>C)32. |= A=>BvC~(A=>B)v(A=>C)33. |= A=>(B~C)~(A=>B~A=>C)6) Idempotentumo desnis34. |= A^A~A35. |= AvA~A7) Absorbcijos desnis36. |= A^(AvB)~A37. |= AvA^B~A8) Loginiu operaciju neigimo desnis38. |= (A^B)~AvB (De Morgano)39. |= (AvB)~ A^B (irgi De Morgano)40. |= (A=>B)~A~B41. |= (A~B)~(AvB)^ (A^B)42. |= A~A9) Tradicines logikos tapatybes.43. |= A~A44. |= Av-A45. |= (A^A)10) Suklijavimo desniai.46. |= (AvB)^( AvB)~A47. |= (A^B)v(A^B)~B11) Kiti dazniau naudojami logikos desniai.48. |= (A=>B)=>((B=>C)=>(A=>C)) (Silogizmas)49. |= (A=>(B=>C))~(B=>(A=>C)) (Anticedentu perstatymas)50. |= A=>(B=>C)~A^B=>C (Anticedentu sujungimas ir skyrimas)51. |= A=>(A=>B) (Anticedentu neigimas )52. |= A=>B~B=>AFormules nuo 1 iki 10 sudaro viena is galimu pilnu nepriklausomu teiginiu logikos aksiomatiku. Kartu jos yra vienas is budu isreiksti svarbiausioms irpaprasciausioms samprotavimu schemoms.14-16 padeda pasalinti ~ ir =>,Is 21 -26 matyti, kad => negalioja nei komutatyvumo, nei asociatyvumo desniai.Tai patvirtina dvieju spec. pavadinimu suteikimas => nariams :1-asis – anticedentas, 2-asis – konsekventas.^, v ir ~ galioja komutatyvumo ir asociatyvumo desniai, todel lygiavercius pertvarkymus atliekant narius galima jungti bet kuriuo budu.Formules 27-33 parodo, kad ^ yra skirstoma tik v atzvilgiu. O v yra skirstoma ^, => ir ~ atzvilgiu. => skirstoma ^, v, ~ atzvilgiu. O ~ neskirstoma is viso.TEISINGUMO FUKCIJU TOBULOSIOS IR NORMALIOSIOS FORMULESKiekviena teiginiu logikos formule galima isreiksti keliais veiksmais : -, v, ^. Formule tures normaliaja išraišką, tuomet, kai pasitaikys tik ,V, . Loginėms išraiskoms galima suteikti 2 normalizuojančias formas : 1) normaliąją disjunkcinę 2)normaliąją konjunkcinę formas. 1.14Ap Elemntariąją disjunkcija vad. Formas P1vP2v…vPn, kai P – elementarusis teiginys arba elementaraus teiginio junginys. 4T. Elementari disjunkcija yra tapačiai teisinga tada ir tik tada, kai joje yra bent vienas elementarus teiginys kartu su savo neigimu. Įrod. Į vieną puse aišku AvA pagal 1.3T 44 formulę. Iš kitos pusės: tegu žinome, kad joje nėra nė vieno elementaraus teiginio kartu su savo neigimu. Parodysime, kad šiuo atveju tai negali būti tapačiai teisinga. Jei teiginiams kurie yra sudaryti be neiginio priskirtumeme k reikshme, o likusiems t reiksme, tai dešinėje V įgys k reikshmeč todėl nėra tapačiai teisinga. 1.15Ap. Elementariaja vad. Forma P1P2…Pn, kur Pi- elementarusis teiginys arba elem. teiginio neiginys.Elementari yra tapatingai klaidinga tada ir tik tada kai joje yra bent vienas elem. teiginys kartu su savo neiginiu.1.16Ap. P vad. Formulei A disjunkcine normaliaja forma, jei P~A ir turi forma: M1vM2v…vMn, kur Mi vad. Elementariosiomis konjunkcijomis.1.17Ap. Formule k vad. Formulės A konjunkcine normaliąja forma, jei k~A ir k turi form Ų M1M2…Mn, kur Mi – elementariosios disjunkcijos.5T. Kiekvieną Formulę galima paversti į disjunkcinę normaliąją formą: Tatkime A bet kuri formulė ir A galima per vesti 1) Sudarome A1~A, kurioje yra tik logines operacijos , V, . Tokia A1 visada galima sudaryti naudojantis 3T formulemis 14-16.2) Sudarome A2~A1, kuriopje ženklas yra tik prieš elementariuosius teiginius. Tai galima gauti naudojantis 3T 38-49 formulemis3) Sudarome A3~A2, kuri yra disjunkcijos normaliosios formos. Nudojames 27 formule. Jei galima tai 34-35-44 formulemis supaprastiname gauta reiškinį.•6T. Kiekvieną formulę galima perdirbti į konjunkcinę normliąją forma. Kaip 5T.(analogiškas) tik 3 žingsnyje naudojamės 28 formule.•[1.18AP] Formulės Q(P1,…,Pn) disjunkcinė normalioji forma kur ki – elem. konjunkcijos, vad. tobula.[1.19AP] Formulės Q(P1,…,Pn) konjunkcinė normalioji forma vad. tobula, kur Pi, i = 1,…,l – elem. disjunkcijos, jei Pj arba jo neiginys įeina į kiekvieną elem. disjunkciją Di .Kiekvienos disjunkcijos norm. formą bei konjunkcinę norm. formą galima pertvarkyti į tobulą naudojantis: K ~ KPKPD ~ (DP) DP)Sios formules leidzia efektingai prirasyti trukstamus kintamuosius. Zinome, kad teisingumo funkcijos gali buti apibr. 2 budais: formulem ir teisingumo lenteles.Is formuliu daznai sudaromos teisingumo lenteles ir atvirksciai. Disjunkc. norm.
form sudaroma:1) isrenkami atomu rinkiniai kurie igyja reiksme t,2) kiekvienam tokiam rinkiniui is atomu P1,…, Pn arba ju junginiu sudaroma konjunkcija, kuri tam rink igyja reiksme t,3) sudaroma gautu elemtu konjunkciju disjunkcija.Sudaryta tokia norm disjunkcine forma isreiskia ta pacia teisingumo f-cija kaip ir teisingumo lentele.Ir. prad. Sakykim, kad esant tam tikram atomu rink. L1, L2, …, Ln teisingumo f-cija igyja reiksme t. Tuomet sis rinkinys bus tarp isrinktuju. Vadinasi, tarp sudarytu elem. konjunkciju bus tokia, kuri esant siam rinkiniui igis reiksme t. Todel tobuloje norm disjunkcineje formoje bus tik vienas narys, turintis reiksme t. Pagal disjunkcijos [AP] t reiksme igis ir tobula norm disjunkcine forma. Sakykim, kad esant tam tikram atomu rinkiniui L1, L2, …, Ln teisingumo f-cija is lenteles igyja reiksme k. Tuomet sio rinkinio nebus tarp isrinktuju vadinasi ir visos sudarytos elementariosios konjunkcijos igys reiksme k. Taigi visi tobulos norm. disjunkcijos formos nariai ir ji pati igys reiksme k. Ir. Pab.Galiausiai apjungiame disjunkcijos zenklu. Norint sudaryti tobula konjuncine norm forma pagal teis lentele darome:1) Isrenkame tokius atomu rinkinius, kuriems esant f-ja igyja reiksme k.2) Kiekvienam tokiam rinkiniui sudarome atomu arba ju junginiu disjunkcija, kur tam rinkiniui igyja reiksme k.3) Sudarome siu junginiu konjunkcija.PILNOSIOS TEISINGUMO F-JU SISTEMOSIs 5 ir 6tos teoremu isplaukia, kad bet kokiai teis f-jai isreiksti pakanka 3 log. operaciju.[1.20 AP] Teis f-ju sistema vadinama pilnaja, jei ja naudojantis galima isreiksti bet kuria teis f-ja. Sistema sudaryta is yra pilnoji. Yra ir kitu tipu sistemu.[7.T] Teis f-ju sistemos: {}, {} {} yra pilnosios.Irod. prad{}: (is pilnosios sistemos {} isreiskiame per analogiskaineduotas?isreiskiame per Irod. Pab.Salia gerai zinomu log. operaciju yra 2 reciau vartojamos: Šeferio brūkšnelis ir Prise strėlė (pilnosios sistemos):A B A|Bt t kt k tk t tk k tA B A|Bt t kt k Kk t kk k t
AIMPLIKACIJOS IR EKVIVALENCIJOS SAVYBESJei A tapaciai teisinga, kai A=>B tapaciai teisinga, tai B tapaciai teisingaIrod. Prad.Sudarome teis lentele A (jos pask stulpelyje tik t reiksmes, nes ji tapaciai teisinga).Sudarome B teis lentele pagal formule A=>B. Zinome, kad tapaciai teisinga, tai jos visos reiksme bus t.Pagal => apibrezima, jei => reiksme ir anticedento reiksme yra t, tai ir konsekvento reiksme yra t. Todel formules B paskutiniame stupelyje bus tik t reiksme, vadinasi B yra tapaciai teisinga.Irod. Pab.[10T] a) formule A~B turi reikmes t visose implikacijose tada ir tik tada, kai A ir B turi vienodas reiksmes.b) A~B yra tapaciai teisinga tada ir tik tada, kai A ir B turi vienodas teisingumo lentelesIrod. Prad.a) Sudaroma teisingumo lentelė ir suskaiciuojama formuliu A ir B reiksmes. Tada pagal apibrezima zinome, kad formulėje AB įgyja reiksmę tada ir tik tada, kai A ir B reiksmės sutampa.6) todėl mūsų formulės AB lentelė turės t reiksmes tada ir tik tada, kai A ir B turi vienodas reiksmes esant bet kokioms atomų reiksmėms.3. Užduotis (log. lygties sprendimas) PQR = t PPQ = PQ
PPQ = t PQ = t
PPQ) = k PQ = kPer dvi sistemas išspresim duotą lygtį. Bus Šeferio brūkšnelis ir Pirso strėlė.Tapačiai teisingų formulių nustatymo metodai1. Teisingumo lentelių metodas2. Prieštaros metodasJis susijęs su loginių lygčių sprendimu.Logine lygtimi vadiname lygybę F1 = F2, kur F1 ir F2 yra teiginių logikos formulės arba teisingumo reikšmės t arba k. Išspręsti lygtį – tai surasti visas F1 ir F2 sudarančių atomų teisingumo reikšmes, kurioms lygybė F1 = F2 yra teisinga.3. Lygiaverčių pertvarkymų metodasJis remiasi 1.9.T., kuri sako, kad AB tapačiai teisinga tada ir tik tada, kai AB. Todėl taikome 1.3.T. formules 14-42, 46, 47, 49, 50, 52. Tai pat atsižvelgiame į tokias A savybes: At = A Ak = k At = t Ak = AModelių teorija – dualumas1.21.A Formulė A* yra duali f-lei A, jei A*(P1, P2, …, Pn) A(P1, …, Pn).Pvz. P* PP (PQ)*(PQ)PQAnalogiškai(PQ)*(PQ)PQ
t*tkk*ktJeigu formulė nusakyta teisingumo lentele pvz.:P Q At T tt K kk T kk K tTai jai duali formulė nusakoma lentele:P Q A*t T kt K tk T tk K kNorint rasti reikšmę, randam kam lygu A(k, t) matome, kad yra k. Ją invertuojame, gauname, kad A*(t, k) = tDualių formulių savybės1.11.T. Dualumo dėsnisJei A(P1, …, Pn)B(P1, …, Pn) tai ir A*(P1, …, Pn)B*(P1, …, Pn)Irodymas. Kadangi AB tada ir tik tada, kai AB, tai lieka įrodyti, kad A(P1, …,Pn) B(P1, …,Pn), kai A(P1, …,Pn) B(P1, …,Pn). Kadangi formulė A(P1, …,Pn) įgyja tas pačias reikšmes kaip ir formulė B(P1, …,Pn) esant bet kokioms teiginių reikšmėms tai formulės A(P1, …,Pn) ir B(P1, …,Pn) bus irgi ekvivalentiškos.Irodyta.
Išvada. A(P1, …,Pn) B(P1, …,Pn) tada ir tik tada, kai A*(P1, …,Pn) B*(P1, …,Pn).
Ženklu žymėsime grafinę formulių lygybę. Formulės yra tam tikros baigtinės abėcėlės raidžių sekos. Sakoma, kad dvi formulės yra grafiškai lygios, jeigu jas sudarančios elementų sekos sutampa.1.22.A. Formulė B(P1, …,Pn) yar aibės A formulių superpozicija, jeigu:a) Formulė B(P1, …,Pn) A, arbab) Atsiras formulė C(Q1, …,Qs) A, ir C1, C2, …, Cs, kur Ci – aibės A formulių superpozicija arba log. kintamasis ir B(P1, …,Pn) yra grafiškai lygi C(Q1, …,Qs).
1.12.T. Jei B(P1, …,Pn) = B(B1(P11, …, P1l1), …, Bm(Pm1, …, Pmlm)), tai B*(P1, …, Pn) B*(B1*(P11, …, P1l1), …, Bm*(Pm1, …, Pmlm)).Įrodymas.Pagal T. salygą ir dualių formulių ap. B*(P1, …,Pn) B(B1(P11, …,P1l1), …, Bm(Pm1, …,Pmlm)) B(B1(P11, …,P1l1), …, Bm(Pm1, …,Pmlm))
Pagal dualių formulių ap. bus B(B1*(P11, …,P1l1), …, Bm*(Pm1, …,Pmlm)) B*(B1*(P11, …,P1l1), …, Bm*(Pm1, …,Pmlm)). Įrodyta.Kadani disjunkcija ir konjunkcija yra viena kitai dualios operacijos, tai teisinga sakyti, jei turim formulę kurioje yra tik log. operacijos , ir , tai jai dualią formulę galim gauti visur pageitę: ,
Panagrinėkim formulių PQ ir PQ teisingumo lenteles:P Q P Q PQ PQt t k k k kt k k t t tk t t k t tk k t t k t
Matome, kad esant visiems P ir Q rinkiniams, kuriems formulė PQ įgyja reikšmę t, formulė PQ taip pat turi reikšmę t.
Tai sakome, kad iš P Q logiškai išplaukiaP Q. Žymime P Q |= P Q.24 AP Iš formulės A log. Išplaukia formulė B, jei esant bent 2 formulių atomų rinkiniams, kuriuose formulės A ir B reikšmės yra t. Atvirkštinis išplaukimas negalioja šiuo atveju.Pabrėšime, kad formulė A|=B yra stipresnis teiginys nei, jei A – tapačiai teisinga, tai ir B – tapačiai teisinga. Iš I-ojo visada seka II-asis. Norint tuo įsitikinti sakykime, kad galioja I-asis teiginys ir dar turime prielaidą, kad A yra tapačiai teisinga. Tuomet, kadangi AB, formulė B turi reikšmes t visose eilutėse, kuriose A turi reikšme t. O kadangi A tapačiai teisinga, tai A turės t reikšmes visose eilutėse. Vadinasi B tapačiai teisinga.Apibendrinsim 1.24AP n prielaidų atveju1.25 AP Iš formulių A1, A2,…An išplaukia B, jeigu formulė B įgyja reikšmę t bent tada, kai į formulės A1, A2,…An, B įeinančių atomų rinkiniai tuo pačiu metu suteikia formulėms A1, A2,…An reikšmę t. Simboliškai užrašoma: A1, A2,…An |= B. To pačio simbolio vartojimas tapačiai teisingoms formulėms ir log. Išplaukimui žymėti paaiškinamos teorema:13T a) A |= B tada ir tik tada, kai |= A B (tapačiai teisinga). b) A1, A2,…An-1 An |= B tada ir tik tada, kai A1, A2,…An-1 |= An B (išplaukia ).Įrodymas. Panagrinėkime: A, B, A B teisingumo lenteles. Norint nustatyti, ar A |= B, reikia nekreipti dėmesio į lenteles, kur A turi reikšmę k, nes jose A B visada turės reikšmę t. Nagrinėjam tas eilutes, kur A turi reikšmę t. Jei A |= B, tai ir B turės reikšmę t šiose eilutėse. O pagal AP ir A B turės t reikšmę. Kitose eilutėse A B irgi turės reikšmę t. Vadinasi A B yra tapačiai teisinga.
Įrodymas (į kitą puse). Jei A B yra t, teisinga , tai ji turės t visose eilutėse nepriklausomai nuo A. Vadinasi, pagal AP B turės t reikšmę, jei A turės reikšmę t, todėl A |= B (a dalies įrodymas).b) Įrodymas. Sakykime A1, A2,…An-1 An |= B, bet A1, A2,…An-1 (neišplaukia) | An B. Tada iš šio teiginio seka, kad egzistuoja bent vienas į bent vieną iš formulių A1, A2,…An-1 An, B įeinančių atomų rinkinys, kuriam esant visos formulės A1, A2,…An-1 įgyja reikšmę t, o A B reikšmę k. Iš AP seka, kad formulės An reikšmė tuomet yra t, o B – k. Taigi, egzistuoja toks atomų rinkinys, kuriam esant visos formulės A1, A2,…An-1 An įgyja t reikšmę, o B – k. Todėl iš A1, A2,…An-1 An | B, o tai prieštarauja sąlygai, kad A1, A2,…An-1, An |= B.Įrodymas (į kitą puse). Tegul iš A1, A2,…An-1 |= A B, o A1, A2,…An-1, An | B. Pagal 1.25 AP turi būti bent vienas formulės A1, A2,…An-1, An ir B sudarantis atomų rinkinys, kuriam esant visos formulės A1, A2,…An-1, An įgyja reikšmę t, o B – k. Esant tam atomų rinkiniui A B įgyja reikšmę k. Taigi, yra toks atomų rinkinys, kai visos formulės A1, A2,…An-1, įgyja reikšmę t, o formulė An B įgyja k. Vadinasi, A1, A2,…An-1 | An B, o tai prieštarauja A1, A2,…An-1 |= An B. Įrodyta.Išvada:a) A … ╞ B tada ir tik tada, kai ╞ ( A =>…=>b) A … ╞ B tada ir tik tada, kai A … ╞ B
a) gauname n kartų pritaikę 13Teoremą , o b) iš a) gauname pritaikę 50-tą formulę iš 3Teoremos.Pritaikę 13Teoremą šiai išvadai galime parašyti , kad A… ╞ B tada ir tik tada , kai ╞ A… => B14Teorema a) A … ╞ A ( i = 1, …, n ) b) jeigu A … ╞ B1 , A … ╞ B2 ir t.t. A … ╞ Bk , o B … ╞ C, tai A … ╞ C. Užrašu sutrumpintai Γ pažymėsime bet kurią formulių aibę , galbūt ir tuščią. Tuomet 13Teoremos b) dalį galima suformuluoti taip : Γ, A╞ B tada ir tik tada, kai Г╞ A=>B.
15Teorema a) Jeigu Γ , A╞ C ir Г, B╞ C, tai Г, AUB╞ C. b) Jeigu Г╞ AUB ir Г, A╞ C ir Г, B╞ C, tai Г╞ C. c) Jeigu Г, A╞ B ir Г, A╞ B, tai Г╞ A.Įrodymas a) daliesSakykim, kad Г, A╞ C ir Г, B╞ C, bet Г, AUB ╞ ! C. Tuomet egzistuoja į bent vieną aibės Г U{A,B,C } formulę įeinančių atomų rinkinys, kuriam esant visos aibės Г U {AUB} formulės įgyja reikšmę t , o formulė C – reikšmę k.Bet jeigu esant tam tikram rinkiniui formulė AUB įgyja reikšmę t, tai pagal disjunkcijos apibrėžimą – reikšmę t turi įgyti bent viena iš formulių A arba B.Jei tai yra A formulė, tai esant šiam rinkiniui visos aibės Г U {A } formulės įgyja reikšmę t, o C – k.Todėl Г, A!C , o tai prieštarauja 1-ai sąlygai. Jei B įgyja t, tai analogiškai gausim prieštarą 2-ajai sąlygai. Sutrumpintos teisingumo lentelės Naudojam teisingumo lenteles norėdami nustatyti, ar formulė tapačiai teisinga, ar iš duotų formulių išplaukia kita formulė. Tačiau, kad įrodyti , ar formulė tap. teisinga, dažnai paprasčiau yra taikyti teoremas. Jei reikia įrodyti, kad formulė nėra tap. teisinga ar logiškai neišplaukia, nereikia sudarinėti pilnos teisingumo lentelės. Tereikia surasti tinkamą eilutę, kad tai įrodytų. Jei reikia atlikti daug skaičiavimų pagal teisingumo lenteles, tai galime naudoti metodą, pagreitinantį skaičiavimą. Jo esmė tokia, kad t ir k reikšmės priskiriamos vienai vieninteliai 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ėkim kokią nors dvejetainio ryšio o pradinę teisingumo lentelę. Jei formulei A priskiriam t arba k, tai esant fiksuotoms A reikšmėms A o B tampa vienetinio ryšio, priklausančio nuo B lentele. Vienetiniam ryšiui galimos tik 4 lentelės. 1) t, t 2) t, k ( kaip ir B ) 3) k, t ( B ) 4) k, k
Taigi parenkant vieną iš A reikšmių, formulė gali įgyti vieną iš reikšmių: t, B, !B, k. Žinomų log. operacijų atveju gaunam tokias lenteles :A A~B AB BA B∩A A∩B B∩AA∩B ATK BB Bt tBBK TB ktPateikta formulių schema vad. Analize pagal teisingumą. Metodą pirmiausia pritaikė 1950 m.Pagrindinės išplaukimo taisyklėsJas suformulavo G.Gentzen. Jos yra dedukcinių samprotavimų pagrindas.Viena iš šių taisyklių 13-oje teoremoje.1 taisyklė. Jeigu Г, A ╞ B , tai Г ╞ A => B.Ji įveda implikaciją, jei įrodyta , kad A╞ B. Galbūt dar darant kitas prielaidas aibėj Г.Taisyklė naudojama įrodymuose. Tegul reikia įrodyti implikacinės struktūros sakinį A=>B.Dažniausiai prie jau įrodytų sakinių aibėj Г prijungiamas sakinys A ir tada iš Г ir A išvedama B. Tada teorema įrodyta.Toks formulavimas ir nusako , kaip taikoma implikacijos ivedimo taisykle , tai yra pereinama nuo Г, A╞ B prie Г╞ A=>B.Dar dvi buvo pateiktos 15-oje teoremoje.2. taisyklė. Jeigu Г, A╞ C ir Г, B╞ C, tai Г, AUB╞ C ( disjunkcijos pasalinimas ) Pagal šia taisyklę išvadai c) iš disjunkcijos AB gauti pakanka išvadą c) gauti iš A ir iš B. Kitaip tariant, norint išvesti c iš A arba B, ši disjunkcija pašalinama ir įrodomi du skiritngi išplaukimai:, A |= c ir , B |= c3 taisyklė. Jei iš , A |= B ir iš , A |= B, tai iš |= A (NĮ)NĮ – neigimo įrodymas.NĮ taisyklė yra netiesioginio įrodymo loginis pagrindas. Netiesioginis įrodymas – tai įrodymas prieštaros metodu.Teiginį A įrodyti darome prielaidą, kad A yra klaidinga, o A – teisinga. Ir tada iš A ir jau įrodytų teiginių aibės išvedame prieštarą B ir B. Po to sakome, kad gauta prieštara įrodo teoremą.Toks formulavimas reiškia, kad NĮ taisyklė taikoma netiesiogiai. Iš tikrųjų, pagal NĮ taisyklę gauname:, A |= B ir , A |= B, tai iš |= A.Tuomet pritaikę dvigubo neigimo pašalinimo taisyklę gauname iš |= A.4 taisyklė. Jei |= A ir |= A B, tai |= B (IP, MP).IP – implikacijos pašalinimas;MP – modus……………;Ši taisyklė bus pagrindinė tolimesnėje teorijoje. Su šia taisykle jau buvo susidurta netiesiogiai, kai samprotavom, kad tap. teisingas teiginys A B nei teiginys, jei |=A, tai |=B. Tuomet ši taisyklė buvo įrodyta.5 taisyklė. Jei |= A, tai |= AB (DĮ1).DĮ1 – pirmasis disjunkcijos įvedimas.6 taisyklė. Jei iš |= B, tai |= AB (DĮ2).Čia buvo pateiktos 6 taisyklės. Jų yra žymiai daugiau. Jos visos turi pavadinimus.Teiginių logikos taikymas natūraliai kalbai.Natūralios kalbos sakinių užrašymas matematinės logikos kalba.Natūralios kalbos sakiniai yra įvairių konstrukcijų. Daugelyje jų galima išskirti tokias komponentes, kurios pačios yra sakiniai. Šie paprastesni sakiniai jungiami jungtukais ir skyrybos ženklais. Kalboje yra daug jungtukų ir kiekvienas jų turi savo atspalvį. Logikoje šie atspalviai išnyksta. Visa kalbinių jungimo priemonių gausybė išreiškiama nedideliu loginių operacijų skaičiumi.Samprotavimų analizė teiginių logikos metodais.Ši analizė susideda iš dviejų dalių:a) samprotavimų struktūros nustatymas,b) patikrinimas, ra išvada išplaukia iš duotų prielaidų;Samprotavimo struktūros pvz.: PQ, P?QNorint nustatyti ar teisinga išvada, galima naudoti įvairius metodus. Pats paprasčiausias yra teisingumo lentelių metodas. Šio samprotavimo struktūra atitinka MP taisyklę.Tačiau ne visuomet samprotavimus galima išanalizuoti taikant teiginių logikos taisykles.Pateiksime sąrašą loginių operacijų ir jiems atitinkamų kalbos išsireiškimų:1. A~B – A jei ir tik jei B; Jei A, tai ir B, ir atvirkščiai; A jei B, ir B jei A; Dėl A būtina ir pakanka B; A ekvivalentiška B; A tada ir tik tada, kai B;2. AB – jei A, tai B; A atveju bus B; Dėl B pakanka A; Dėl A būtina B; A iššaukia B; B, jei A;3. AB – A ir B; Ne tik A, bet ir B; B, nors ir A; A tuo pat metu, kaip ir B; B, nepaisant A; Kaip A, taip ir B; A kartu su B;4. AB – A arba B, arba abu; A arba B; A, jei ne B;Nors teiginių skaičiavime AB yra lygiavertė BA, tačiau frazės “Neringai gimė vaikas ir ji ištekėjo”, “Neringa ištekėjo ir jai gimė vaikas” yra labai skirtingos. Čia problema susijusi suįvykių tvarka laike. Tačiau dėl loginės analizės dažnai galime nekreipti dėmesio į laiką. Kita problema yra susijusi su terminų dviprasmiškumu, kai juos reikia pakeisti loginėmis operacijomis