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
Implikatsioon 2. Missugused seaduse tepoolest on olemas? Neeldumisseadus DeMorgani seadus vlistatud kolmanda seadus kontrapositsiooniseadus vastuolu seadus topelteituse seadus 3. "TAUTOLOOGIA" on lause, mis on alati vr? False 4. Vali loetelust alternatiivne nimetus neile loogika tehetele! Disjunktsioon - VI-tehe Konjunktsioon - JA-tehe Implikatsioon - jreldamine 5. Milliseid kvantoreid on vimalik eitada? Olemasolu kvantorit 6. Millised kvantorid on olemas? Olemasolukvantor ldsusekvantor 7. Kui loogikaavaldises pole sulgudega mratud tehete jrjekorda,siis KONJUNKTSIOONI, INVERSIOONI, DISJUNKTSIOONI leidumisel tehaksekigepealt... a-inversioon b-konjunktsioon c-disjunktsioon 8. Mitu erinevat tehet kasutatakse lausearvutuses? 5 9. Loogika tehetel on olemas vrsnalised nimetused! Loogiline korrutamine - konjunktsioon Eitus - Inversioon Jreldamistehe - Implikatsioon Loogiline liitmine - disjunktsioon
Vali üks: Tõene Väär Küsimus 2 Õige - Hinne 1,00 / 1,00 Märgista järgnevas loetelus need nimed, mis loogikaseaduste hulgas tõepoolest eksisteerivad: Vali üks või enam: topeltjaatuse seadus kontrapositsiooni seadus Morgani seadus päritolu seadus neeldumisseadus DeMorgani seadus välistatud kolmanda seadus välistatud teise seadus eeldusseadus topelteituse seadus vastuolu seadus Küsimus 3 Õige - Hinne 1,00 / 1,00 Millised kvantorid on olemas? Vali üks või enam: Lausekvantor Üldsuse kvantor Tõekvantor Normaalkvantor Olemasolu kvantor Loogikakvantor Küsimus 4 Õige - Hinne 1,00 / 1,00 Mitut erinevat loogikatehet kasutatakse lausearvutuses? (sisesta arv/number: ) Vastus: 5 Küsimus 5 Õige - Hinne 1,00 / 1,00 Loogikatehetel on olemas võõrsõnalised nimetused. Loogiline korrutamine on konjunktsioon Loogiline liitmine on disjunktsioon
Kui loogikaavaldises pole sulgudega määratud tehete järjekorda, siis KONJUNKTSIOONi, DISJUNKTSIOONi ja INVERSIOONi leidumisel avaldises . . . kõige esimesena tehakse loogikaavaldises INVERSIOON ...selle järel järgmisena tehakse KONJUNKTSIOON ...ja viimasena tehakse DISJUNKTSIOON Küsimus 10 Õige Hinne 1,00 / 1,00 Flag question Küsimuse tekst Millised kvantorid on olemas? Vali üks või enam: Üldsuse kvantor Loogikakvantor Olemasolu kvantor Normaalkvantor Lausekvantor Tõekvantor
..selle järel järgmisena tehakse ...ja viimasena tehakse Question 7 Mitut erinevat loogikatehet kasutatakse lausearvutuses? Correct (sisesta arv/number: ) Mark 1 out of 1 Answer: 5 Question 8 Millised kvantorid on olemas? Correct Mark 1 out of 1 Select one or more: Loogikakvantor Olemasolu kvantor Üldsuse kvantor Tõekvantor Lausekvantor
Kahekohaline predikaat on kahe muutujaga nt P(x,y), predikaat P sisaldab kahte muutujat x ja y Kuidas nimetatakse teisiti ühekohalisi predikaate? Ühekohalisi predikaate nimetatakse omaduseks. Mida näitab predikaadi määramispiirkond? Näitab, milliseid väärtusi võib predikaatmuutuja omandada. Millal on predikaatlause täidetav ehk kehtestatav? Kui ta on tõene ainult osade muutujaväärtuste x korral, ehk on tõene osas oma määramispiirkonnas. Millised kvantorid on olemas? Millised on nende tähised? On olemas kaks kvantorit, nendeks on Üldsuse kvantor(tagurpidi A) ja eksistentsikvantor(Peegelpildis E). Üldsuse kvantor näitab, et predikaat kehtib oma määramispiirkonna kõikide muutujate väärtuste korral. Eksistentsi kvantor näitab, et predikaat kehtib vähemalt ühe oma määramispiirkonna muutuja väärtuste puhul. Millise loogikatehte üldistuseks on üldsuse kvantor? Konjuktsioon Millise loogikatehte üldistuseks on eksistentsikvantor?
liikmeid Iga Boole'i funktsiooni f(x1 , ... , xn ) saab esitada lausearvutuse valemina milles ei ole muid tehtemärke kui &, ja o Boole'i funktsioon on funktsioon (x1 , ... , xn ):{0,1} {0,1}. Ka tõeväärtustel defineeritud funktsioone võib vaadelda Boole'i funktsioonidena, iga lausearvutuse tehe on Boole'i funktsioon Venni diagrammide leidmine tähendab, et viime vaadeldavad avaldised TDNK-le, et neid saaks võrrelda 3. PREDIKAADID JA KVANTORID Hulgal M määratud n-kohaliseks predikaadiks nimetatakse kujtust P: Mn -> {1,0} o Hulka, millel predikaat on määratud, nimetatakse selle predikaadi indiviidide piirkonnaks o Vastavalt predikaadi definitsioonile saame igale predikaadile seada vastavusse tema tõesuspiirkonna = { (1, ... , ) |P(1, ... , ) = } Olgu P(1, ... , ) hulgal defineeritud -kohaline predikaat. Siis iga korral tähistavad P(1, ... , ) ja P(1, ..
7. Binaarse predikaadi ees paikneb kaks kvantorit, üks rakendub predikaadi esimesele indiviidimuutujale, teine kvantori teisele indiviidimuutujale. Milline järgnevatest väidetest on väär? Neid kvantoreid tohib vahetada kui … Olemasolukvantor tõstetakse üldsuskvantori ette (ÕIGE, HÄSTI VÕIB- OLLA) Üldsuskvantor tõstetakse olemasolukvantori ette. Mõlemad on üldsuskvantorid Kvantorid on üht tüüpi (VALE) Mõlemad on olemasolukvantorid 8. Kui tingiv-kategoorilise süllogismi suurem eeldus on üldväide ja väiksem eeldus on üksikväide, siis kehtiva süllogismi saamiseks tuleb teostada … Vali üks: Üldsuskvantori eemaldamine väiksemas eelduses Eelduste tõesuse kontroll Olemasolukvantori eemaldamine suuremas eelduses Üldsuskvantori eemaldamine suuremas eelduses (ÕIGE)
!!! Esimest järku predikaatarvutuses: - predikát konstandid—puuduvad predikát muutujad st.kui predikát on defineeritud, siis arutluse käigus tema tähendus ei muutu, - üks predikaat ei tohi olla teise predikaadi argumendiks. • Liitlausete formaliseerimine: - Atomaarne lause e. aatom–sisaldab vaid ühte predikaati -Liitlause – moodustatakse aatomitest lausearvutuse tehete abil • Kvantorid Üldistuse ja abstraktsiooni väljendamiseks Predikaatarvutuse arutlus kehtib mingi valdkonna objektide kohta Valdkonna objektide hulka kokku nimetatakse universumiks. - Üldisuskvantor (universal quantifier) - universumi kõikide objektide kohta käiva väite esitamiseks. Muutuja on valemis seotud, kui ta esineb koos kvantoriga ja avaldises kvantori
Loogiline liitmine on disjunktsioon Vastus 3 Loogiline korrutamine on konjunktsioon Vastus 4 Järeldamistehe on implikatsioon Vastus 5 Eitus on inversioon Küsimus 5 Õige Hinne 1,00 / 1,00 Millised kvantorid on olemas? Vali üks või enam: Tõekvantor Olemasolu kvantor Loogikakvantor Üldsuse kvantor Lausekvantor Normaalkvantor Küsimus 6 Õige Hinne 1,00 / 1,00 Vali loetelust õige alternatiivne nimetus nendele loogikatehetele. Vastus 1 implikatsioon on järeldamine Vastus 2 konjunktsioon on JA-tehe Vastus 3
tõene, kui ta on kehtiv kogu oma mpk-s ; samaselt väär, kui ta ei kehti oma mpk mitte mingite muutujaväärtuste korral. Kvantoriteks on üldsuse kvantor ja eksistentsikvantor. Muutuja on seotud, kui talle on rakendatud kvantorit ja vaba, kui predikaatmuutuja on kvantormärgiga mitteseotud (∀𝑥𝑃(𝑥,𝑦) korral x on seotud ja y vaba muutuja). Hüüumärgiga eksistentsikvantor tähendab, et „leidub täpselt üks x …“. Kvantorid on omavahel seotud nagu ∀𝑥𝑃(𝑥)≡∃̅𝑥∃𝑃̅(𝑥). Predikaadid on võrdväärsed (ekvivalentsed), kui nende tõeväärtuspiirkonnad langevad kokku. Loogikaseadused on kuni kolme operandiga lihtsaimad samaselt tõesed lausearvutusvalemid ja samaselt tõesed lausearvutusvalemite võrdused. Implikatsioon ei ole kommutatiivne. HULGAD Hulk on koosvaadeldavate hulgaelementide kogum. Hulk koosneb hulgaelementidest. Hulka tähistatakse suurtähtedega A B C D
- ühe sõnaliigi sõnad seonduvad ühesuguste morfoloogiliste kategooriatega; - ühe sõnaliigi sõnad saavad esineda lauses ühesugustes süntaktilistes funktsioonides; - enamasti iseloomustab ühe sõnaliigi sõnu ühelaadiline leksikaalne tähendus. Sõnaliigid IV Noomenite alaliigiks on: substantiivid (muutuvad sarnaselt) adjektiivid pronoomenid numeraalid (võimlaiema käsitluse järgi kvantorid e hulgasõnad) Partiklid on verbi laiendid: - 1) mis väljendavad aega, kohta, viisi jms ehk adverbid (nt kiiresti), - 2) verbi tähendust konkretiseerivad afiksaaladverbid e abimäärsõnad (nt üle lugema), - 3) proadverbid e asemäärsõnad (nt mistõttu), - 4) lause üldlaienditena toimivad modaaladverbid e rõhumäärsõnad (nt veel), - 5) lauseid või lauseosi siduvad konjunktsioonid e sidesõnad,
— samaselt väär: kui ta ei kehti mitte mingite muutujaväärtuste Reeglina eelistame predikaate võimalusekorral esitada formaalselt ehk korral oma määramispiirkonnas valemitekujul (predikaatvalem). Predikaatmuutujate kohta tuleb alati eelnevalt täpsustada, milliseid KVANTORID ∀ ∃ väärtusi ta võib omandada ehk milline on predikaadi Kui soovime väita, et predikaat P (x) kehtib oma määramispiirkonna määramispiirkond. kõikide x-ide ( x1 x2 x3 . . . ) korral ehk: Olgux täisarv ja vaatleme ühekohalist predikaati: P ( x1 ) ∧ P ( x2 ) ∧ P ( x3 ) ∧ P ( x4 ) ∧ . . . . = 1
K VA N T O R I D . K VA N T O R I T E DUAALSUSREEGLID. Predikaatarvutuse põhiideed: 1. Arvestatakse, et lauses on kaks osa: ! ! ! - objektid (see, mille kohta midagi väidetakse) - predikaat (see, mis väljendab indiviidide teatud omadusi või nendevahelisi seoseid). 3. Lausearvutuse reeglid ja sümbolid jäävad kehtima, kuid tehakse täiendusi. 4. Mõnikord tehakse täiendavaid nõudeid (nt, et indiviidide hulk ei tohi olla tühi). Kvantorid: ∀ – üldisuskvantor ∃ – olemasolukvantor Kvantorite duaalsusreeglid. Kvantoreid on võimalik omavahel asendada kasutades kvantorite duaalsusreegleid. ¬∀x p = ∃x ¬p Mitte kõik x on p. = Mõni x on ¬p. või Mõni x ei ole p. ¬∃x p = ∀x ¬p Pole x-i, mis on p. = Iga x on ¬p. ∀x p = ¬∃x ¬p Kõik x on p. = Pole x-i, mis on ¬p. või Pole x-i, mis ei ole p. ∃x p = ¬∀x ¬p Mõni x on p. = Pole nii, et kõik x on ¬p. 20
K VA N T O R I D . K VA N T O R I T E DUAALSUSREEGLID. Predikaatarvutuse põhiideed: 1. Arvestatakse, et lauses on kaks osa: ! ! ! - objektid (see, mille kohta midagi väidetakse) - predikaat (see, mis väljendab indiviidide teatud omadusi või nendevahelisi seoseid). 3. Lausearvutuse reeglid ja sümbolid jäävad kehtima, kuid tehakse täiendusi. 4. Mõnikord tehakse täiendavaid nõudeid (nt, et indiviidide hulk ei tohi olla tühi). Kvantorid: üldisuskvantor olemasolukvantor Kvantorite duaalsusreeglid. Kvantoreid on võimalik omavahel asendada kasutades kvantorite duaalsusreegleid. ¬x p = x ¬p Mitte kõik x on p. = Mõni x on ¬p. või Mõni x ei ole p. ¬x p = x ¬p Pole x-i, mis on p. = Iga x on ¬p. x p = ¬x ¬p Kõik x on p. = Pole x-i, mis on ¬p. või Pole x-i, mis ei ole p. x p = ¬x ¬p Mõni x on p. = Pole nii, et kõik x on ¬p. 20
kui ta on kehtiv kogu oma mpk-s ; samaselt väär, kui ta ei kehti oma mpk mitte mingite muutujaväärtuste korral. Kvantoriteks on üldsuse kvantor ja eksistentsikvantor. Muutuja on seotud, kui talle on rakendatud kvantorit ja vaba, kui predikaatmuutuja on kvantormärgiga mitteseotud (∀𝑥𝑃(𝑥, 𝑦) korral x on seotud ja y vaba muutuja). Hüüumärgiga eksistentsikvantor tähendab, et „leidub täpselt üks x …“. Kvantorid on omavahel seotud nagu ∀𝑥𝑃(𝑥) ≡ ∃ ̅𝑥∃𝑃̅(𝑥). Predikaadid on võrdväärsed (ekvivalentsed), kui nende tõeväärtuspiirkonnad langevad kokku. Loogikaseadused on kuni kolme operandiga lihtsaimad samaselt tõesed lausearvutusvalemid ja samaselt tõesed lausearvutusvalemite võrdused. Implikatsioon ei ole kommutatiivne.
kohta midagi väidetud. Sealhulgas võib tähisena kasutada ka sedasama muutujat , kui ta ei esine eeldustes (vaba muutujana). 11. **Kvantorite distributeerumine konjunktsiooni ja disjunktsiooniga. **Kvantorite ettetoomine. [3] o Kvantorite distributiivsus: 8x(F(x) & G(x)) = 8xF(x) &8xG(x), 9x(F(x) v G(x)) = 9xF(x) v9xG(x). o vajaduse korral konjunktsiooni ja disjunktsiooni kommutatiivsust, toome kvantorid osavalemite eest valemi ette. HULGAD, FUNKTSIOONID 10 12. Hulgateooria alusmõisted: hulk, element, hulkade võrdsus, tühi hulk. [3, 4, 5] Hulk o üksteisest erinevate objektide kohumit, mida vaadeldakse ühe tervikuna ja kus iga objekti korral on võimalik üheselt kindlaks määrata, kas ta kuulub antud hulka. Element o hulka kuuluv objekt Hulkade võrdsus
poiss + + + - Primitiivid: substantiivid I, YOU, SOMEONE MINA, SINA, KEEGI (ISIK), (PERSON), MISKI (ASI), INIMESED, SOMETHING (THING), KEHA PEOPLE, BODY määratlejad THIS, THE SAME, SEE, SAMA, TEINE OTHER kvantorid ONE, TWO, SOME, ÜKS, KAKS, MÕNI, PALJU, MANY/MUCH, ALL KÕIK atribuudid GOOD, BAD, BIG, HEA, HALB, SUUR, VÄIKE SMALL Mentaalsed THINK, KNOW, WANT, MÕTLEMA, TEADMA, predikaadid FEEL, SEE, HEAR TAHTMA, TUNDMA,
Jakob Bernoulli, hiljem ka Gottfried Ploucquet (1716-1790) ning matemaatikud Johann Heinrich Lambert (1728-1777) ja Leonhard Euler (1707-1783) pakkusid välja sama laadi ideid. Paraku ei suutnud ei Leibniz ega ükski teine mainitutest konstrueerida loogika jaoks vähegi rahuldavat sümbolkeelt, arutlemise aritmeetikast rääkimata. Gottfried Ploucquet ehitas Leibnizi ideedel, kuid mitte Leibnizi süsteemil baseeruva lausearvutuse sümbolsüsteemi. Ploucquet tõi sisse kvantorid ``iga ...'' ja ``on olemas ...'', tõsi küll, suhteliselt kohmakal ja piiratud viisil. Johann Heinrich Lambert konstrueeris, tõenäoliselt Leibnizist sõltumatult, Leibnizi süsteemiga sarnase sümboolse loogikasüsteemi, kus ta tõi olulise uuendusena sisse matemaatikast tuttava funktsiooni mõiste ja kasutas seda mitmekohaliste suhete (nagu näiteks ``A on B isa'') tähistamiseks. Ülimõjukad Saksa filosoofid Immanuel Kant (1724-1804) ja Georg Wilhelm Friedrich Hegel (1770-1831) tegelesid
Objekt on positiivse väärtusega siis ja ainult siis, kui selle objekti puudumine on negatiivse väärtusega. Ükskõiksust defineeritakse kui mittehalb ja mittehea. Esimene objekt on teisest parem siis ja ainult siis, kui teine on esimesest halvem. Võrdväärsust defineeritakse kui mitteparem ja mittehalvem. EPISTEEMILISED LAUSED (ik epistemic, ld. epistéme teadmine) väljendavad teadmiste astet. Teadmise astme väljendamist kindlustavad modaalsed kvantorid (operaatorid): on tõestatud, et ... on ümberlükatud, et ... on lahendamatu, et ... Episteemiliste mõistete süsteemi töötas esimesena välja Kurt Gödel (1906-1978). Selles süsteemis on määravaks modaalsus on tõestatav. Seaduspärasused on järgmised: Teadmine on alati tõene. Kui väide on tõestatav, siis on ta tõene. Loogilised järeldused tõestatud väitest on tõestatavad.
Kui koos teoreemiga (Kui A, siis B) kehtib ka pöördteoreem (Kui B, siis A), siis võetakse tavaliselt need teoreemid kokku üheks lauseks, kasutades ühte väljenditest ,,on tarvilik ja piisav," ,,siis ja ainult siis," ,,parajasti siis, kui.". Näide: Teoreem: Nelinurk on rööpkülik parajasti siis, kui tema diagonaalid poolitavad teineteist. Näide: Definitsioon: Rööpkülikuks nimetatakse nelinurka, mille diagonaalid poolitavad teineteist. Olemasolu ja üldistuse kvantorid Paljudes matemaatika lausetes esinevad sõnad ,,kõik," ,,iga," ,,leidub," ,,eksisteerib," ,,on olemas," ,,vähemalt üks.". Osa neist lausetest on tõesed, osa väärad. Selliste lausete kirjutamisel kasutatakse loogikas kahte märki. Üks neist on olemasolu kvantor (loetakse ka ,,leidub"), teine üldisuse kvantor (loetakse ka ,,iga"). Kvantori märgi taha tuleb alati kirjutada muutuja, millele see kvantor rakendub. Näide: x, x3 - 27 = 0 tähendab, et leidub x, mille korral x3 - 27 = 0.
.. (suurtähed, võivad olla alaindeksitega); · predikaadisümbolile lisatud ülaindeks näitab predikaadi aarsust, unaarsete ja binaarsete predikaatide aarsuse võib märkimata jätta; · indiviidimuutujad: x, y, z, x1, z2, y6, ... (tähestiku viimased tähed, võivad olla alaindeksitega); · indiviidikonstantide sümbolid: a, b, c, h, a1, j6, ... (tähestiku esimesed tähed, võivad olla alaindeksitega); · loogiliste tehete sümbolid: ¬, &, , , ; · kvantorid , ; · metasümbolid: o =; o ; o kuuluvusseos (a X element a kuulub hulka X); o või järeldumine; o vastastikune järeldumine; o kirjavahemärgid: (), [ ]; · funktsionaalsümbolid, mis tähistavad baashulgal määratud funktsioone (nt naturaalarvude hulga N puhul ,,+" ja ,,"). Traditsioonilises loogikas peab sageli arutlema väidete konteksti üle. Predikaatarvutuses on
• predikaadisümbolile lisatud ülaindeks näitab predikaadi aarsust, unaarsete ja binaarsete predikaatide aarsuse võib märkimata jätta; • indiviidimuutujad: x, y, z, x1, z2, y6, … (tähestiku viimased tähed, võivad olla alaindeksitega); • indiviidikonstantide sümbolid: a, b, c, h, a1, j6, … (tähestiku esimesed tähed, võivad olla alaindeksitega); • loogiliste tehete sümbolid: ¬, &, ∨, →, ↔; • kvantorid ∀, ∃; • metasümbolid: o=; o ≡; o ∈ – kuuluvusseos (a ∈ X – element a kuulub hulka X); o ⇒ või ╞ ‒ järeldumine; o ⇔ – vastastikune järeldumine; o kirjavahemärgid: (), [ ]; • funktsionaalsümbolid, mis tähistavad baashulgal määratud funktsioone (nt naturaalarvude hulga N puhul „+” ja „–”). Traditsioonilises loogikas peab sageli arutlema väidete konteksti üle. Predikaatarvutuses on
annaabi.ee 
