SML kordamisküsimustele vastused. (2)

SISSEJUHATUS MATEMAATILISSE LOOGIKASSE Kordamisküsimused (orienteeruv)
Mõnede sümbolite tähendused sõna Materjal puudub & Konjuktsioon Ekvivalents üldisuskvantor Järeldumine Disjunktisoon ¬ Eitus olemasolukvantor Signatuur Implikatsioon Samaväärsus Loogiline järeldumine
I. Lausearvutus Laused . Lausearvutuse tehted . Valem. Valemi tõeväärtus. Tõeväärtustabel. Laused Põhilised uuritavad objektid lausearvutuses on laused, mis võimaldavad pärineda ükskõik millisest valdkonnast. Oluline on, et igale lausearvutusele saaks vastavusse seada tõeväärtuse, mis kirjeldab lause tegelikkusele vastava määra. Eeldame, et käsitlevad laused rahuldavad järgmisi tingimusi: · Välistatud kolmanda seadus. Iga lause on kas tõene või väär · Mittevasturääkivuse seadus. Ükski lause ei saa olla nii tõene kui ka väär Lausearvutuse tehted Tähtsamad lausearvutuse tehted: · Eitus ¬ Väljendab lause mittekehtimist · Konjuktsioon & tähendab seost ,,ja". · Disjunktsioon väljendab seost ,,või". Kasutatakse mittevälistavas tähenduses: ,,Kas A või B või mõlemad". · Implikatsioon , väljendab ,,kui...,siis..." · Ekvivalents tähendab ,, parajasti siis, kui..." 1) Tehted võib teostada ükskõik milliste lausetega 2) Tehte tulemuseks saadud lause tõeväärtus sõltub ainult komponentlausete tõeväärtustest. Pole oluline lause sisu vaid tõeväärtus. Valem. Valemi tõeväärtus. Tõeväärtustabel. Def 1. Lausearvutuse valemid on parajasti need, mida saab koostada alltoodud reeglite abil 1) Iga lausemuutuja on lausearvutuse valem. 2) Kui F on lausearvutuse valem, siis ka ¬F on Lvalem 1. 3) Kui F ja G on Lvalemid, siis ka (F&G), (FG), (FG) ja (FG) on Lvalemid. Def 2. Lvalemi F tõeväärtus etteantud väärtustusel leitakse järgmiste reeglite abil. 1) Kui F= ¬G, siis F=1 parajasti siis, kui G=0 2) Kui F=G&H, siis F=1 parajasti siis, kui F=1 ja G=1 3) Kui F=GH, siis F=1 parajasti siis, kui F=1 või G=1 4) Kui F=GH, siis F=1 parajasti siis, kui F=0 või G=1 5) Kui F=GH, siis F=1 parajasti siis, kui F=1 ja G=1 või F=0 ja G=0
1 Lühend. L tähendab ,,Lausearvutus" (-e) 1 Tõeväärtusetabel F G F&G FG FG FG 1 1 1 1 1 1 1 0 0 1 0 0 0 1 0 1 1 0 0 0 0 0 1 1
Samaselt tõesed, samaselt väärad ja kehtestatavad valemid. Def 3. Lvalemit F nimetatakse · samaselt tõeseks, kui ta on igal väärtusel tõene. · samaselt vääraks, kui ta on igal väärtusel väär. Def 4. Lvalemit F nim kehtestatavaks, kui ta on vähemalt ühel väärtusel tõene. Teoreem 1. Valem F on samaselt tõene parajasti siis, kui tema eitus on samaselt väär. Tõestus. Andes valemis F esinevatele lausemuutujatele suvalise väärtustuse, näeme, et valemite F ja ¬ F tõeväärtused on vastupidised. Järelikult kui F on igal väärtusel tõene, siis ¬ F on igal väärtusel väär ja ümberpöördult. Teoreem 2. Valem F on kehtestatav parajasti siis, kui tema eitus ¬ F ei ole samaselt tõene Tõestus. Kui F on keht ., siis väärtustusel, kus F on tõene, on valem ¬ F väär ja ei saa seetõttu olla samaselt tõene. Ümberpöördult, kui ¬ F ei ole samaselt tõene, siis leidub väärtustus, kus ¬ F on väär ja F järelikult tõene.
Järeldumine lausearvutuses. Def 5. Ütleme, et valemitest F1, F2,...,Fn järeldub valem G, kui igal neis valemeis esinevate muutujate väärtustusel, millel F1, F2,...,Fn on tõesed, on ka G tõene.
Asjaolu, et valemitest F1, F2,...,Fn järeldub valem G, tähistatakse kirjutisega F1, F2,...,Fn G Arusaamise jaoks võiks lihtsamalt öelda: Valem G järeldub valemist F siis, kui G on tõene nendel väärtustel, kus F on tõene. G peaks olema tõene igal väärtusel, kus F tõene. Kui mingil väärtusel on F tõene ja G väär, siis järeldumine ei kehti. Samuti ei kehti selline asi, et kui F-ist järeldub G, siis ka G-st järeldub F. Teoreem 3. Valmitest F1, F2,...,Fn järeldub valem G parajsti siis, kui valem F1& F2&...&FnG on samaselt tõene. Tõestus. Kui valemitest F1, F2,...,Fn järeldub valem G, siis neilväärtustustel, millel valemid F1, F2,...,Fn on tõesed, on ka valem G tõene, mistõttu F1& F2&...&FnG on tõene. Väärtustustel, millel mõni valemitest F1, F2,...,Fn on väär, on valem F1& F2&...&FnG tõene seetõttu, et impl eesliige on väär. Ümberpöördult, kui valem F1& F2&...&FnG on samaselt tõene, siis igal väärtustusel, millel valemid F1, F2,...,Fn on tõesed, on ka F1& F2&...&Fn tõene, mistõttu valem G on samuti tõene.
Loogiliselt samaväärsed valemid. Lausearvutuse põhisamaväärsused. Valemite avaldamine etteantud tehete kaudu. Def 6. Valemeid F ja G nim samaväärseteks, kui nende tõeväärtused on võrdsed igal neid valemeis esinevate muutujate väärtused. Ehk siis valemite F ja G tõeväärtustabelid võrdsed. See tähendab lõplikud tõeväärtused.
2 Teoreem 4. Valemid F ja G on samaväärsed parajasti siis, kui valem FG on samaselt tõene. Tõestus... 2 Lausearvutuse põhisamaväärsused. Valemite avaldamine etteantud tehete kaudu.
2 Tõestus SML õpikus lk 21 3 Valemite disjunktiivne ja konjunktiivne normaalkuju . Nende leidmise algoritmid. Def 7. Lvalemi F täielikuks TDNK nim valemiga F samaväärset valemit, mis kujutab endast erinevate täielike EKD 3 Valemi F TKNK nim valemiga F samaväärset valemit, mis kujutab endast erinevate täielike EDK. Kui valem F ei ole samaselt väär, siis tal leidub TDNK. Kui valem F ei ole samaselt tõene, siis tal leidub TKNK (Teoreem 5+Järeldus 1) 4 Täielikule disjunktiivsele normaalkujule viimise algoritmi sammud
1) Elimineerida valemist implikatsioonid ja ekvivalentsid. 2) Viia eitused vahetult lausemuutujate ette, jätta ära kahekordsed eitused. 3) Viia konjunktsioonid disjunktsioonidest sügavamale. 4) Jätta ära samaselt väärad ja korduvad liikmed ning liikmetest korduvad literaalid. 5) Lisada liikmetele puuduvad lausemuutujad ning viia uuesti konjunktsioonid disjunktsioonidest sügavamale. 6) Järjestada igas liikmes literaalid ja jätta ära korduvad liikmed.
Täielikule konjunktiivsele normaalkujule viimise algoritmi sammud
1) Elimineerida valemist implikatsioonid ja ekvivalentsid. 2) Viia eitused vahetult lausemuutujate ette, jätta ära kahekordsed eitused. 3) Viia disjunktsioonid konjunktsioonidest sügavamale. 4) Jätta ära samaselt tõesed ja korduvad liikmed ning liikmetest korduvad literaalid.
3 elementaarkonjuktsioonide disjunktsiooni 4 SML õpik lk. 27 4 5) Lisada liikmetele puuduvad lausemuutujad ning viia uuesti disjunktsioonid konjunktsioonidest sügavamale. 6) Järjestada igas liikmes literaalid ja jätta ära korduvad liikmed.
Formaalse aksiomaatilise teooria üldskeem. Teooria korrektsus ja täielikkus semantika suhtes. Formaalse aksiomaatilise teooria üldskeem 1) Fikseeritakse tähestik ja antakse valemi definitsioon. 2) Osa valemeid loetakse aksioomideks. Neid pole teoorias vaja tõestada. 3) Fikseeritakse lõplik hulk tuletusreegleid kujul 1 ,2 ,..., , mis lubavad valemitest 1 , 2 , ... , vahetult tuletada valemi G.
Def 2. Aksiomaatilist teooriat T nim semantika S suhtes · korrektseks, kui iga teoorias T tuletatav valem on semantikas S tõene. · täielikuks, kui iga semantikas S tõene valem on teoorias T tuletatav. (Def 1. Tuletuseks ehk formaalseks tõestuseks nim valemite jada 1 , 2 , ... , , milles iga valem on kas aksioom või saadud mingi tuletusreegliga mõnedest temale eelnevatest valemitest. Valemist F nim tuletatavaks, kui leidub tuletus, mille viimane liige on valem F)
Sekventsiaalne lausearvutus. Tuletamine lausearvutuses. Eesmärk on formuleerida lausearvutuse jaoks aksiomaatika, mis on korrektne ja täielik samaselt tõesuse semantika suhtes. Kasutame Gentzeni-tüüpi süsteemi, mis vastab matemaatiliste väidete tõestamisel esinevatele arutluskäikudele paremini kui ajalooliselt vanemad Hilberti-tüüpi süsteemid.
Lugeda lk. 88-96
Lausearvutuse korrektsus, mittevastusrääkivus (tõestustega). Teoreem 1. (korrektsuse teoreem) Kui sekvents 1 , 2 , ... , G on tuletatav, siis tema valemkuju on samaselt tõene. Tõestus lk. 91 Teoreem 2.(mittevasturääkivuse teoreem) Sekventsiaalne lausearvutus on mittevasturääkiv. Tõestus lk. 93
Lausearvutuse täielikkuse teoreemi põhilemma ja täilekkuse teoreem (tõestustega) Teoreem 4. Kui sekventsi 1 , 2 , ... , G valemkuju on samaselt tõene, siis sekvents on tuletatav. Tõestus lk. 96
II. Turingi masinad Turingi masin. Arvuliste funktsioonide arvutamine Turingi masinal .
Kõike, mida saab arvutada protsessiga, mis vastab meie intuitsioonile algoritmilisest protsessist, saab arvutada ka Turingi masina abil. Teesi analooge saab kirja panna ka algoritmi teiste formalisatsioonide kohta. Churchi teesi ei saa tõestada, sest ta seob intuitiivse mitteformaalse mõiste täpse formaalse mõistega. Kuid teda saab ümber lükata. 5 Turingi masina töötamine: · Aeg on jagatud diskreetseteks ühikuteks, taktideks. · Igal taktil määratakse pea all oleva sümboli ja masina seisundi järgi järgmisena täidetava käsu vasak pool. · Käsu parem pool kirjeldab, milline sümbol lindile kirjutada, millisesse seisundisse masin läheb ja kummale poole pea liigub. · Töö lõpeb, kui masin siirdub passiivsesse seisundisse q0 või kui täitmisjärg jõuab tühja lahtrisse .
Turingi masina omadused: · Vastab hästi meie intuitiivsele arusaamale algoritmist. · Lihtsuse ja elementaarsuse tõttu võib tabel olla üsna mahukas, kuid praktilise kasutatavusega seotud küsimused on antud juhul teisejärgulised. · Samas on hõlpus tõestada Turingi masinate kohta üldisi teoreeme, mh algoritmide mitteleidumist. · Taktide arv sobib hästi algoritmi keerukuse mõõduks.
Arvude ja arvujärjendite esitamine lindil:
Turingi masinate kompositsioon ja hargnemine. Definitsioon 3. Turingi masinat M nim masinate M1 ja M2 konpositsiooniks, kui iga algkonfiguratsiooni X korral kehtib võrdus M(X)=M2(M1(X)) 6 Teoreem 1. Kui M1 ja M2 on samas tähestikus töötavad Turingi masinad, siis saab nende masinate tabelite järgi alati koostada kompositsioonmasina tabeli. Tõestus. Olgu masinal M1 aktiivsed seisundid q1,q2,...,qk ning masinal M2 seisundid r1,r2,...rl. Kirjutame masinate M1 ja M2 tabelid teinteise järele, andes esimese masina peatumiskohtades juktimise teise masina esimesele seisundile. Selleks asendame igal pool seisundi q0 seisundiga r1, esimese masina tabeli igasse tühja lahtrisse saqb kirjutame aga sar1C. Niisugune teisendatud tabel ongi kompos.masina tabel, sest kui esimese masina töö on valmis, siis suundub täitmisjärg alati teise masina avaseisundisse. Def. 4 Olgu Turingi masinal M0 kaks passiivset seisundit 01 ja 02 . Masinat M nim masinate M1 ja M2 hargnemiseks masina M0 järgi, kui iga algkonfiguratsiooni X korral 1 0 (), 0 õ öö 01 () = 2 0 (), 0 õ - öö 02 0 (), Teoreem 2. Kui M0, M1 ja M2 on samas tähestikus töötavad Turingi masinad, kusjuures masinal M0 on kaks passiivset seisundit 01 ja 02 , siis saab nende masinate tabelite järgi alati koostada sellise masina tabeli, mis on masinate M1 ja M2 hargnemine masina M0 järgi. Tõestus. Kirjutame masinate M0, M1 ja M2 tabelid järjest. Asendame kõik seisundid 01 masina M1 esimese seisundiga ning seisundid 02 masina M2 esimese seisundiga.
Turingi masinate numeratsioon.
Turingi mõttes mittearvutatavad funktsioonid. Eneselerakendatavuse ja peatumise probleemi mittelahenduvus. Rice 'i teoreem (tõestuseta). Järeldused programmeerimise jaoks. Def 5. Ütleme, et Turingi masin M lahendab omadust R, kui tema poolt arvutatav ühe muutuja funktsioon on 1, , () = 0, . Teoreem 3.Ei leidu Turingi masinat, mis lahendaks enese,erakendatavuse omadust. Tõestus lk 124
Teoreem 4. Ei leidu Turingi masinat, mis kontrolliks argumentide x ja y järgi, kas masin Tx lõpetab argumendil y töö lõpliku arvu sammudega. Tõestus lk. 125
Teoreem 5. (Rice'i teoreem) Olgu A kõigi Turingi mõttes arvutatavate funktsioonide hulga mittetühi pärisalamhulk. Ei leidu Turingi masinat, mis kontrolliks argumendi x järgi, kas Turingi masina Tx poolt arvutatav funktsioon kuulub hulka A.
III. Predikaatarvutus Predikaadid ja indiviidid . Kvantorid .
Predikaadid: · Seoseid elementide vahel väljendavad predikaadid. · Predikaate tähistame predikaatsümbolitega A, B, C, koos argumentidega; argumentideks on termid . · Predikaate võib omavahel kombineerida lausearvutuse tehete ja kvantoritega 7 Indiviidid: · objektid, mille kohta midagi väidetaks · Hulka M nimetatakse indiviidide piirkonnaks, see fikseerib objektid, mille kohta predikaat midagi väidab
Kvantorid:
Term . Predikaatarvutuse valem. Vabad ja seotud muutujad. Keele signatuur: konstant-, funktsionaal- ja predikaatsümbolid. Term. Def. 2 Termid on parajasti need, mida saab koostada alltoodud reeglite abil: · Iga indiviidmuutuja on term · Iga C-sümbol on term · Kui f on n- kohaline funktsionaalsümbol ja t1,t2,...,tn on termid, siis f(t1,t2,...,tn) on term. Termi, milles ei esine ühtegi indiviidmuutujat, nim muutuajateta termiks. Predikaatarvutuse valem Def 3. Predikaatarvutuse valemid on parajasti need, mida saab koostada alltoodud reeglite abil: · Kui P on n-kohaline predikaatsümbol ja t1,t2,...,tn on termid, siis P(t1,t2,...,tn) on predikaatarvutuse valem. · Kui F on pvalem 5, siis ¬ F on pvalem · Kui F ja G on pvalemid, siis (F&G), (FG), (FG) ja (FG) on pvalemid · Kui x on indiviidmuutuja ja F on pvalem, siis on pvalemid. Vabad ja seotud muutujad. Indiviidmuutuja x esineb valemis F seotult, kui ta asub mingi kvantori mõjupriikonnas, st osavelmit õ moodustavas valemis G. Ülejäänud esinemisi nim. vabadeks. Kui indiviidmuutuja x esineb valemis F vabalt, siis märgime sellist valemit mõnikord ka tähisega F(x). Keele signatuur: konstant-, funktsionaal- ja predikaatsümbolid.
Signatuur fikseerib termides ja valemites lubatud mitteloogiliste sümbolite hulgad.
5 predikaatarvutuse... 8 Väidete tüübist sõltumatud sümboled (lausearvutuse tehtemärgid, kvantorid, sulud , indiviidmuutujad) võivad esineda kõikides valemites. Fikseerime sümbolite klassid. · Indiviidmuutujad, mida märgime tavaliselt tähtedega u,v,w,x,y,z. Iga indiviidmuutuja võib tähistada vaadeldava hulga ükskõik millist elementi (indiviidi) · C-sümbolid a,b,c,d jne. C-sümbol tähistab vaadeldava hulga mingit kindlat elementi. · Funktsionaalsümbolid f,g,h jne. Need tähistavad vaadeldaval hulgal määratud f-oone. Pannes mitmesugused väiteid kirja pvalemiga, võivad väidete tüübist sõltumatud sümbolid, nagu ltehtemärgid, kvantorid, sulud ja indiviidmuutujad, esineda ükskõik millistes valemites, olgu siis tegemist valemitega, mis puudutavad naturaal-,reaalarve, vektoreid, alamhulki või muid objekte. Seevastu C-,funktsionaal- ja predikaatsümbolid võivad teooriati erineda. Tihtipeale fikseeritakse need kolm sübmolite klassi eelnevalt ning lubatakse valemites kasutada ainult sümboleid, mis kuuluvad kindlasmääratud klassidesse. Kolmikut =, kus C on Csümbolite, F funktsionaalsümbolite ja P predikaatsümbolite hulk, nim signatuuriks.
Signatuuri interpretatsioonid (algebralised süsteemid, mudelid).
Kehtestatav, samaselt tõene ja samaselt väär predikaatarvutuse valem. Def 7. Predikaatarvutuse valemit F nim · samaselt tõeseks, kui ta on tõene igas interpretatsioonis oma vabade muutujate kõikidel väärtustel · samaselt vääraks, kui ta on väär igas interpretatsioonis oma vabade muutujate kõikidel väärtustel · kehtestatavaks, kui ta on tõene vähemalt ühes interpretatsioonis vabade muutujate mingitel väärtustel.
Järeldumine ja samaväärsus predikaatarvutuses. Predikaatarvutuse põhisamaväärsused. Nende tõestamine interpretatsioonide terminites. Suvalise valemi samaselt tõesuse tõestamise või ümberlükkamise ülesanne. 6 · Ütleme, et valemitest 1 , 2 , ... , järeldub valem G, kui igas interpretatsioonis valmite vabade muutujate kõikidel väärtustel, kus valemid 1 , 2 , ... , on tõesed, on ka valem G tõene · Valemid F ja G nim samaväärseteks, kui nende tõeväärtused on võrdsed igas interpretatsioonis valemite vabade muutujate kõikidel väärtustel.
6 Ülesandeid konspektis ei vaatle 9 Prefikskuju. Valemi prefikskujule viimise algoritm .
Ütleme, et valem F on prefikskujul, kui F = Q1x1Q2x2 . . . QnxnF, kus Q1, Q2, . . . , Qn on kvantorid, x1, x2, . . . , xn indiviidmuutujad ja F kvantoriteta valem. Prefikskuju on lähtekoht paljudele predikaatarvutuse algoritmidele, ta mängib predikaatarvutuses sarnast rolli nagu TDNK ja TKNK lausearvutuses
Teisendamise algoritm: Olgu antud valem F. 1) Elimineerida implikatsioonid ja ekvivalentsid. 2) Viia eitused kvantorite alla. Kahekordsed eitused jätta ära. 3) Nimetada seotud muutujad ümber nii, et iga kvantor seoks erinevat muutujat ja et ükski kvantor ei seoks muutujat, mis esineb kuskil vabalt. 4) Tuua kvantorid valemi ette.
10 Sekventsiaalne predikaatarvutus. Tuletamine predikaatarvutuses.
Kvantoritega seotud tuletusreeglid
Tingimuse tähendus
11 Predikaatarvutuse korrektsus, mittevasturääkivus, täielikkus (neist viimane tõestuseta). Teoreem 5. (korrektsuse teoreem) Kui sekvents 1 , 2 , ... , G on tuletatav, siis tema valemkuju on samaselt tõene. Tõestus lk. 99-100 Teoreem 6. (Mittevasturääkivuse teoreem) Sekventsiaalne predikaatarvutus on mittevasturääkiv. Tõestus. Tõestus on analoogiline lausearvutuse juhuga. Teoreem 7.(Täielikkuse teoreem) Kui sekventsi 1 , 2 , ... , G valemkuju on samaselt tõene, siis sekvents on tuletatav. Selle teoreemi tõestas austria loogik ja matemaatik Kurt Gödel aastal 1930. Omal ajal oli see matemaatilise loogika üks silmapaistvamaid tulemusi. Meie seda teoreemi käesolvas kursuses ei tõesta.
Võrdusega predikaatarvutus. Sümmeetrilisuse ja transitiivsuse tuletamine võrdusega predikaatarvutuses. Korrektsus, mittevasturääkivus, täielikkus (neist viimane tõestuseta).
Esimest järku aksiomaatilised teooriad. Teoreemid nende korrektsuse, mittevasturääkivuse ja täielikkuse kohta. Formaalne aritmeetika. Gödeli tulemused (mittetäielikkus, mittevasturääkivuse tõestamatus). Teoreem 8. (korrektsuse teoreem) Kui sekvents 1 , 2 , ... , G on esimest järku teoorias tuletatav, siis ta on tõene teooria omaaksioomide kõikides mudelites. Tõestus lk. 105 Teoreem 9.(mittevasturääkivuse teoreem) Kui esimest järku teooria omaaksioomidel leidub mudel, siis on see teooria mittevasturääkiv. Tõestus. Kui teoorias oleksid tuletavad sekventsid F ja ¬F ning teooria omaaksioomidel leidub mudel, siis peaksid valemid F ja ¬F olemas selles mudelis mõlemad tõesed, mis on aga võimatu. Teoreem 10. (täielikkuse teoreem) Kui sekvents 1 , 2 , ... , G on tõene esimest järku teooria omaaksioomide kõikides mudelites, siis sekvents on teoorias tuletatav.
12 Formaalne aritmeetika:
Naturaalarvude aksiomaatikast · Esimest järku teooria semantika on teooria omaaksioomide kõikides mudelites tõesuse semantika: (valem on semantikas tõene, kui ta on tõene omaaksioomide igas mudelis). · Naturaalarvude puhul on loomulik selle asemel vaadelda ühes konkreetses mudelis tõesuse semantikat ja ka siin püstitada küsimuse aksiomaatika korrektsusest, mittevasturääkivusest ja täielikkusest. · Et on aksioomide A1­A7 mudel, siis on teooria korrektne. · Täielikkuse kohta tõestas K. Gödel 1931 . aastal aritmeetika mittetäielikkuse teoreemi: kui formaalne aritmeetika on mittevasturääkiv, siis 1) leidub valem, mis on mudelis tõene, aga pole formaalses aritmeetikas tuletatav; 2) ka lõpliku (või üldiselt lahenduva) hulga mudelis tõeste aksioomide lisamine ei muuda formaalset aritmeetikat täielikuks. · Mittevasturääkivuse küsimus on seotud küsimusega, mis üldse on mudel .
13