välja arvatud siis, kui alus on tõene ja tagajärg on väär. Ekvivalents p↔q. Loomulikus keeles on ekvivalentsi indikaatoriteks väljendid … siis ja ainult siis, kui … ; … parajasti siis, kui … ; tarvilik ja piisav tingimus; ühekorraga. Lause on tõene siis, kui oponendid on korraga tõesed või väärad. Antiekvivalents p ⊕q (välistav disjunktsioon) Emb-kumb, kas...või... p ⊕q on tõene parajasti siis, kui p ja q tõeväärtused on erinevad. Lausearvutuse tehete järjekord: 1) tehted sulgudes 2) tehted eitusega 3) konjunktsioon 4) disjunktsioon 5) implikatsioon 6) ekvivalents 7) antiekvivalents Võrdse prioriteediga tehted sooritatakse vasakult paremale. Väidete süsteem on vastuoluline siis, kui tõesustabelis pole ühtegi rida, kus väited oleksid kõik korraga tõesed. Kui aga leidub rida, milles süsteemi väited on korraga tõesed, siis oleme leidnud kontranäite väitele, et selle süsteemi kõik väited ei saa korraga tõesed olla
Tähistagu: A Ants on Jüri isa B Ants on Mari isa C Jüri on Mari vend D Mari on Jüri õde E Anne on Antsu ema F Anne on Jüri vanaema 1. Olgu teada, et 1) Kui Anne on Jüri vanaema, siis on Ants Mari isa ja Mari on Jüri õde. 2) Kui Ants ei ole Jüri isa, siis ei ole Ants ka Mari isa. 3) Ants ei ole Jüri isa. Kas on võimalik, et Anne on Jüri vanaema. Lahendus. Teisendame ülaltoodud väited lausearvutuse keelde. (1) F B & D (2) ¬A ¬B (3) ¬A (4) F (hüpotees) (5) ¬B (2) ja (3), MP (6) B & D (4) ja (1), MP (7) B (6), Simp (8) Vastuolu (5) ja (7) vahel. Vastus. Ei ole võimalik.
Arutluse tõestamine Arutlust saab loogikas esitada kujul: E1 E2 E3 ... En J kus E1 ... En on lausearvutuse avaldistena esitatud eeldused ja J (kontrollimist ootav) järeldus. Seoseks, mis viib eeldusest järelduseni saab kasutada lausearvutust. Nimelt võib ülaltoodud arutluse esitada ühe lausearvutuse valemina kujul: E1&E2&...&En J Kui nüüd sellise lause tõeväärtustabel on samaselt tõene, siis võime öelda, et järeldus J järeldub eeldustest E1 ... En. Näide 1. Kui Marile meeldib Jüri, siis Mari naeratab Jürile. Marile meeldib Jüri. Mari naeratab Jürile. Teisendame arutluse lausearvutuse kujule MN M N Ja esitame selle ühe avaldisega: (MN)&MN. 1. 2. 3. M N (M N) & M N
puhul võib eristada kahte formaalset keelt – lausearvutust ja predikaatarvutust. Lausearvutus on klassikalise loogika lihtsaim osa, mis tegeleb lihtlausete vaheliste seoste uurimisega ning mille abil on võimalik välja selgitada, kuidas liitlause tõeväärtus sõltub osalausete tõeväärtustest.Lausearvutust kasutatakse väga paljudes valdkondades, rakendusalad ulatuvad arutluste analüüsist filosoofias liittingimuste konstrueerimiseni programmeerimises. Predikaatarvutus on lausearvutuse laiendus, milles kasutatakse täiendavalt redikaadi, inviidi ja kvantori mõisteid. Lausearvutus Lausemuutujad: A, B, C, ... Loogikatehted: &, V, , , Kirjavahemärgid: () Loogikatehted Konjunktsioon - &, AND Konjunktsioon kahe lause vahel on tõene täpselt siis, kui mõlemad tema osalaused on tõesed. Disjunktsioon – V, OR Disjunktsioon kahe lause vahel on väär täpselt siis, kui mõlemad tema osalaused on väärad. Implikatsioon -, IF...THEN...
Tingimused 1. Välistatud kolmanda seadus. Iga lause on kas tõene või väär. 2. Mittevasturääkivuse seadus. Ükski lause pole korraga tõene ja väär. Lausearvutuse valemid on parajasti need, mida saab koostada alltoodud reeglite järgi: 1. Iga lausemuutuja on lausearvutuse valem. 2. Kui F on lausearvutuse valem, siis ka F on lausearvutuse valem. 3. Kui F ja G on lausearvutuse valemid, siis ka (F&G), (FVG),(F->G) ja (F<->G) on lausearvutuse valemid. Osavalem : Kõiki antud valemi konstrueerimise käigus tekkinud valemeid nimetatakse selle valemi osavalemiteks ehk alamvalemiteks, konstrueerimise viimasel sammul kasutatud suhet aga peatehteks. Kokkulepped sulgude kohta: 1. Tehete prioriteet kõrgemast madalamani on , &, V, ->, <->. 2. Vasakassotsiatiivsus: kui mitme liikme konjuktsioonis või disjunktsioonis sooritatakse. tehteid vasakult paremale, siis võib tehete järjekorda täpsustavatest
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
MATEMAATILINE LOOGIKA 1. LAUSEARVUTUS Lausearvutuse tehted: Eitus (¬) Konjuktsioon (&) Disjunktsioon (V) Implikatsioon (->) Ekvivalents (<->) Lausearvutuse valemid on parajasti need, mida saab koostada alltoodud reeglite abil: o iga lausemuutuja on lausearvutuse valem o kui F on lausearvutuse valem, siis ka ¬F on lausearvutuse valem o kui F ja G on lausearvutuse valemid, siis ka (F&G), (FVG), (F->G) ja (F<->G) on lausearvutuse valemid Lausearvutuse valemi F tõeväärtus etteantud väärtustusel leitakse järgmiste reeglite abil: o 1) Kui F = ¬G, siis F = 1 parajasti siis, kui G = 0 o 2) Kui F = G & H, siis F = 1 parajasti siis, kui G = 1 ja H = 1 o 3) Kui F = G H, siis F = 1 parajasti siis, kui G = 1 või H = 1 o 4) Kui F = G H, siis F = 1 parajasti siis, kui G = 0 või H = 1
Lause mittekehtimine. b. Konjunktsioon (märk &) tähendab seost ,,ja". c. Disjunktsioon (märk ) väljendab seost ,,või". Siin on kasutusel mittevälistav ,,või". d. Implikatsioon (märk ) väljendab tingimuslikku konstruktsiooni ,,kui ..., siis ...". e. Ekvivalents (märk ) tähendab matemaatikas sagedasti kasutatavat seost ,,parajasti siis, kui". f. Tehete järjekord kõrgemast madalamani ¬, &, , , . g. Def. Lausearvutuse valemid on parajasti need, mida saab koostada alltoodud reeglite abil. g.i. Iga lausemuutuja on lausearvutuse valem. g.ii. Kui on lausearvutuse valem, siis ka ¬ on lausearvutuse valem. g.iii. Kui ja on lausearvutuse valemid, siis ka ( & ), ( ), ( ) ja ( ) on lausearvutuse valemid. 3) a. Kui vaatluse all on korraga hulk lausemuutujaid ja me omistame tõeväärtuse
[Karl Marx] jne.). Lisaks sellele võib sõnavalik mängida olulist rolli kõlalises mõttes. Euroopa kultuuris võib osutada nn kolme fenomenile: paljud loosungid, mis kätkevad endas kombinatsiooni kolmest sõnast või mõttest, on olnud väga populaarsed: "Tulin. Nägin. Võitsin.". "Kiiremini! Kaugemale! Kõrgemale!". "Õppida, õppida, õppida!". "Rahu, leiba, maad!". "Üks riik. Üks rahvas! Üks juht" jne. Lausearvutuse süntaks ja semantika Lausearvutuse tähestiku moodustavad kolme tüüpi sümbolid: 1) lausemuutujate sümbolid: A, B, C ... (suured tähed) 2) loogiliste tehete sümbolid: ¬, &, , , 3) kirjavahemärgid: () Lausearvutuse süntaks aktsepteerib valemeid kujul: ¬A (A & B) (A B) (A B) (A B) Valemite välimised sulud väib ära jätta. Muid lausearvutuse valemeid (nt A¬, AB&, B(A), B(A), AB jne) ei ole. Lausearvutuse loogiliste tehete tõeväärtustabelid (vt ka Lisa) Eitus p ¬p t v v t
Diskreetse matemaatika elemendid 2013/2014 LAUSEARVUTUS. TÕESTUSED. 1. Lausearvutuse lausetele esitatavad tingimused. [1] o Välistatud kolmanda seadus. Iga lause on kas tõene või väär. o Mittevasturääkivuse seadus. Ükski lause ei saa olla nii tõene kui ka väär. o Nende nõuete põhjal kuuluvad vaadeldavate hulka ainult nii sugused laused, mis midagi väidavad, kusjuures sellel väitel on olemas ühene tõeväärtus. o . Välistatud kolmanda seaduse nõudel jäävad kõrvale kõik küsilaused ja paljud
Lausearvutus: Diskreetne matemaatika ei tegele pidevate funktsioonidega. Diskreetne mate ei tegele reaalarvudega. Verbaalne esitus on lingvistilise keele kasutamine info edastamiseks. Formaalne esitus on ilma lingivtilise keele kasutamise info edastamine, peamiselt sümbolite abil. Formaalne esitus peab olema üheselt mõistetav. Lausearvutus on loogilise mõtlemise matemaatiline mudel. Lausearvutuse lause on lause, millele saab omistada tõeväärtust(0,1). Tõeväärtuseid on kaks, 0-väär, 1-tõene. Lihtlause on lihtsaim lausearvutuse lause. Lausearvutuse lauseid tähistatakse suutre tähtedega A, B, C. Liitlause koosneb lihtlausetest ning neid siduvatest konstruktisoonidest ja sidesõnadest. Lausearvutuse loogikatehted on inversioon, konjunktsioon, disjunktsioon, implikatsioon, ekvivalents.
loogikatehted) ja 1 tehe viiest on rakendatav üksikule lausele ( unaarne Ü loogikatehe) T Lausearvutus on loogilise mõtlemise matemaatiline mudel. T Lausearvutuse lause võib olla iga verbaalne (ehk lingvistilises keeles verbaalne esitus formaalne tähistus väljendatud) väide, millele saame omistada tõeväärtuse — tõene või P eitus ( inversioon ) : __ vale. " mitte P "; " pole õige, et P " P Tõeväärtusi tähistame numbritega 0 ja 1.
Loogika hargnemist on eri allikates käsitletud erinevalt. Meie võtame aluseks S. Haacki ,,Loogika filosoofias" esitatu, mille eeskujul saab loogikat jaotada traditsiooniliseks, klassikaliseks ja mitteklassikaliseks.Ajalooliselt oli esimene loogika Aristotelese loogika, mis arenes edasi nn traditsiooniliseks loogikaks. Traditsiooniline loogika koosneb peamiselt aristotellikust süllogistikast ning sellega seotud väite- ja mõisteõpetusest. Traditsiooniline loogika on tänapäeval taandunud lausearvutuse ja predikaatarvutuse ees, mis on arvutuslikult võimsamad kui traditsiooniline loogika. Klassikaline loogika on lausearvutus ja predikaatarvutus. Mõneti lihtsustatult võib öelda, et traditsiooniline loogika on mõisteloogika ja klassikaline loogika on predikaatarvutus ehk predikaatloogika, kuna lausearvutus on esitatav predikaatarvutuse osana. Klassikalises loogikas on väljend lause sama tähendusega, mis propositsioon (väitlause sisu, mis pole seotud konkreetse keele või ütlemisviisiga)
allikates käsitletud erinevalt. Meie võtame aluseks S. Haacki ,,Loogika filosoofias" esitatu, mille eeskujul saab loogikat jaotada traditsiooniliseks, klassikaliseks ja mitteklassikaliseks. Ajalooliselt oli esimene loogika Aristotelese loogika, mis arenes edasi nn traditsiooniliseks loogikaks. Traditsiooniline loogika koosneb peamiselt aristotellikust süllogistikast ning sellega seotud väite- ja mõisteõpetusest. Traditsiooniline loogika on tänapäeval taandunud lausearvutuse ja predikaatarvutuse ees, mis on arvutuslikult võimsamad kui traditsiooniline loogika. Klassikaline loogika on lausearvutus ja predikaatarvutus. Mõneti lihtsustatult võib öelda, et traditsiooniline loogika on mõisteloogika ja klassikaline loogika on predikaatarvutus ehk predikaatloogika, kuna lausearvutus on esitatav predikaatarvutuse osana. Klassikalises loogikas on väljend lause sama tähendusega, mis propositsioon (väitlause sisu, mis pole seotud
Tehte tulemid kuuluvad võimalike argumentide hulka A. Tehte argumente nimetatakse operandideks. LOOGIKAALGEBRA TEHE on tõeväärtuste hulgal(tõene, väär) defineeritud tehe. Neid arve, millega tehet sooritatakse nimetatakse OPERANTIDEKS. Kui tehtes on kaks operanti, siis on tegemist BINAARSE tehtega. Kui tehtel on üks operant, nt ruutu tõstmise tehe, siis on see UNAARNE tehe. Lauseloogikas on kasutusel KAKS ALGEBRAT, mis kuuluvad BOOLE’I algebra klassi: tõeväärtuste algebra ja lausearvutuse algebra. Boole’i algebra lihtsat erijuhtu, mida esindab kahe kahe tõeväärtusega Boole’i algebra, nimetatakse ka loogikaalgebraks. Lausearvutuse Boole’i algebra kandvat hulka võiks nimetada FORMAALSETE LAUSETE hulgaks, need esinevad sümbolkujul, neil pole iseenesest ei tõeväärtust ega tavakeelset kuju. LAUSEARVUSTUSE TEHE on formaalsete lausete hulgal defineeritud tehe, mille tulemi kuju on üheselt määratud operandide ja tehtesümboliga. LAUSEARVUSTUSE TEHTED 1. EITUS 2
Induktsioon. Sokrates (470-399). Induktsioon ja üldiste tunnuste leidmine üksikutes mõistetes. Platon (427-347). Väitluskunsti ülesanne on vastuolude avastamine. ARISTOTELES (384-322) Loogika on tööriist kõikide teaduste jaoks. Võttis kasutusele muutujad, väite komponendid (1) kvantor, (2) subjekt, (3) koopula, (4) eitus, (5) predikaat. Süllogismid. Modaalsed väited. Stoikud: Zenon Kitionist (333-264) ja eriti Chrysippos (279-206). Lausearvutuse elemendid. Keskajal Boethius (480-525). Aristoteles ladina keelde. Skolastikud panevad aluse ka analüütilisele filosoofiale. Raimon Lull (1235-1315) Võtab kasutusele sümbolid. G. W. Leibnitz (1646-1716). Idee luua universaalne sümbolkeel, mida võib kontrolloda ka masinaga. Tegi palju matematilise loogika jaoks, kuid ei avaldanud. G. Boole (1815-64) Lausearvutus. Seda arendas A. de Morgan. (1806-1871). Gottlob Frege (1848-1925) Esimest järku predikaatarvutus.
2. ¬(x , x2 = 1) 3. x , ¬(x2 = 1) 4. x , x2 1 Iga reaalarvu x korral x2 1 Näide: Eitame lauset: ,,Iga reaalarvu x korral leidub reaalarv y nii, et x < y." 1. Antud juhul P(x, y) = ,,x < y" 2. ¬(x y , x < y) 3. x y , ¬(x < y) 4. x y , x y Leidub reaalarv x nii, et mis tahes reaalarvu y korral x y. 2. LOENG Lausearvutuse põhimõisted Loogika (kr. logiké techne mõtlemiskunst, logos sõna, mõiste, mõistus) on teadus õigest mõtlemisest, selle vormidest ja struktuuridest. Traditsioonilise loogika aluseks on mõtlemisseadused, mida kutsutakse ka loogika aksioomideks: 1. samasuse seadus 2. vasturääkivuste lubamatuse seadus 3. välistatud kolmanda seadus 4. küllaldase aluse seadus Matemaatiline loogika on loogika haru, milles loogikaprobleemide käsitlemiseks kasutatakse
Entümeem esitatakse tavaliselt liitlausena, milles mõni eeldus loetakse vaikimisi tõeks. Nt: Sa oled neonats, sest sa vihkad kommuniste. Varjatud eeldus (suurem): Kõik, kes vihkavad kommuniste, on neonatsid. Kõik, kes vihkavad kommuniste, on neonatsid. Sa vihkad kommuniste. Sa oled neonats. Epiheireem on süllogism, kus üks või mõlemad eeldused on entümeemid. ! 5/14 14. LAUSEARVUTUSE TEHTED. Vastavalt tehete järjekorrale: Eitus – tähistatakse märgiga ¬. Konjunktsioon – tähistatakse märgiga &. Disjunktsioon – tähistatakse märgiga ∨. Implikatsioon – tähistatakse märgiga →. Ekvivalents – tähistatakse märgiga . Antiekvivalents – tähistatakse märgiga ⊕. 15. LAUSEARVUTUSE VALEMITE KLASSIFITSEERIMINE. TÕESUSTABELID. 16. TEKSTI INTERPRETEERIMINE LAUSEARVUTUSE VALEMITEKS.
Entümeem esitatakse tavaliselt liitlausena, milles mõni eeldus loetakse vaikimisi tõeks. Nt: Sa oled neonats, sest sa vihkad kommuniste. Varjatud eeldus (suurem): Kõik, kes vihkavad kommuniste, on neonatsid. Kõik, kes vihkavad kommuniste, on neonatsid. Sa vihkad kommuniste. Sa oled neonats. Epiheireem on süllogism, kus üks või mõlemad eeldused on entümeemid. ! 5/14 14. LAUSEARVUTUSE TEHTED. Vastavalt tehete järjekorrale: Eitus tähistatakse märgiga ¬. Konjunktsioon tähistatakse märgiga &. Disjunktsioon tähistatakse märgiga . Implikatsioon tähistatakse märgiga . Ekvivalents tähistatakse märgiga . Antiekvivalents tähistatakse märgiga . 15. LAUSEARVUTUSE VALEMITE KLASSIFITSEERIMINE. TÕESUSTABELID. 16. TEKSTI INTERPRETEERIMINE LAUSEARVUTUSE VALEMITEKS. Teksti tõlkimisel loogika keelde peab järgima minimaalse interpretatsiooni printsiipi
ISA(u,z)) & EMA(v,u) & EMA(v,x) & ISA(w,u) & ISA(w,x) & ¬mees(x)) siin seega z on y-i ema või isa, u on vanaema või vanaisa ja x on viimase õde. (7% õigeid vastuseid) 2. Kui mu abikaasa mind petab, siis jätan ta maha või hakkan ka ise teda petma. Kui ma oma abikaasat petan, jätan ta varem või hiljem igal juhul maha. Kui abikaasa peakski mind petma, võin siiski talle andestada ja teda mitte maha jätta. Tõestada lausearvutuse tuletusreegleid kasutades järgmine arutluse kehtivus või vastuolulisus. Tähistame: Mu abikaasa petab mind - A Ma jätan ta maha -M Hakkan ka ise teda petma - I (1) A(MI) (2) IM (3) A¬M (4) A - eeldus (5) MI 1), 4), MP (6) ¬M 3), 4), MP (7) I 5), 6), DS (8) M 2), 7), MP (9) M&¬M 6), 8), conj - VASTUOLU (71% õigeid vastuseid) 3. Kontrollida, kas järgmised lausepaarid on loogiliselt ekvivalentsed:
1. Ekvivooksus – sama termi kasutatakse erinevates tähendustes 2. Üldise reegli kasutamine sobimatul erijuhul 3. Konteksti vahetus argumenteerimise käigus 4. Nõutakse jah/ei tüüpi vastust küsimusele, millele ei saa nii vastata . 5. Küsimuse tähendus ja vastus oleneb kontekstist • Väited koosnevad lihtlausetest, mis on omavahel seotud loogika seoste ehk tehetega (ja; või; ei; kui ..., siis ..., jne). • Lausearvutuse seoste korral määravad osalausete tõeväärtused täielikult kogu lause tõeväärtuse, osalausete konkreetne sisu ei ole aga tähtis. • Lausearvutuse tehteks nimetatakse niisugust lausetes kasutatavat seost, mille tõeväärtus on tema osalausete tõeväärtuste funktsioon (Boole’i funktsioon). Semantika – valemi tõeväärtuse määratlus téma alamvalemite töeväärtuste põhjal. 3 Predikaatarvutus 3
Lahenduskäik: http://pages.csam.montclair.edu/~benham/enclabs/index.html => Shift-click here to download the Excel workbook. => Paneme: First Prime: 137 ; Second Prime: 173 ; Public key: 7 Kelle poolt on loodud tuntuim tehisintellekti test, mis on tänini kasutusel? Vali üks: Alan Turing + Alonzo Church Claude Shannon Howard Aiken Milline XML keelte perekonna liige on ettenähtud XML info kasutajale mugavamaks esitamiseks? Vali üks: a. XPath b. XQuery c. XSD d. XSLT + e. DTD Millise lausearvutuse valemi implementeerib allolev skeem? * Vali üks: ((AvB)&(-C))v(C&B) ((A&B)v(-C))v(CvB) ((-AvB)&(C))&(CvB) +
Kui A ja B, siis A Ei ole tõsi, et A ja mitte A Modus ponens: Kui Ast järeldub B ja A on tõsi, siis on ka B tõsi. Näide: Iga anarhist on vabaabielu pooldaja Mõned valitseva partei liikmed on anarhistid --------------------------------------------- Mõned valitseva partei liikmed on vabaabielu pooldajad Näite jätk Iga x on y Mõni z on x ------------------- Mõni z on y Loogika - keel formaliseeritudkujul, kasutades kunstlikke formaalseid keeli Lausearvutuse keel Predikaatarvutuse keel Reeglid Samasusseadus ühegi lause sisu ei muutu arutluse käigus Vasturääkivusseadus ükski lause ei saa olla endaga vastuolus Välistatud kolmanda seadus iga lause on kas tõene või väär, kolmandat võimalust ei ole Küllaldase aluse seadus ühtli lauset ei saa pidada tõeseks või vääraks ilma küllaldase aluseta. Näide Maril on täna hea tuju Kui Maril on hea tuju, siis on Jüri õnnelik -------------------------
Aritmeetiline masin- 1640, ainult liitis ja lahutas, Kristlik filosoof Blaise Pascal Leibnizi arvuti 1671, Saksa filosoof Leibniz, arvuti: liitis, lahutas, korrutas, jagas Elektritelegraaf - Morse 1837 Loogika (lausearvutuse) alused 1847-1854 Perfolint - Wheatstone 1857 Frege loob kaasaegse predikaatarvutuse - 1879 Herman Hollerith perfokaartidega masin USA rahvaloenduse andmete töötlemiseks 1890, sellest firmast tekkis IBM Vaakumtoru - 1906, Lee Deforest Artikkel Turingi masinast: universaalsus, mittelahenduvus 1935-1937 Churchi lambda-arvutus, Churchi tees. - 1936,universaalsus, mittelahenduvus Z1 1936 , Konrad Zuse mehhaaniline arvuti
Neid ei saa jagada enam veelgi lihtsamateks lauseteks. Kuidas lausearvutuslauseid tavaliselt tähistatakse? Lausearvutus lauseid tähistame formaalselt suurtähtedega A,B,P,Q..... . Mis on liitlause?Kuidas ja millest neid moodustatakse? Lihtlausetest koostatakse kindlate sidesõnade ja loogiliste konstruktsioonide abil liitlauseid. Lihtlaused seotakse liitlauseks 5 loogikatehte abil, millest 4 on binaarsed, 1 on unaarne ja selleks on eitus. Millised on lausearvutuse loogikatehted? Nende tähistused ja verbaalsed tähendused? Verbaalne esitus: Formaalne tähistus: Eitus: Mitte P, pole õige, et P. ~P, on ka teisi alternatiive. Ühe alternatiivi kehtimise nõue: PvQ P või Q Tingimuste samaaegse kehtimise nõue: P &Q P ja Q Järeldumine: P->Q Kui P siis Q Samaväärsus: P<->Q P ainult siis, kui Q Millist tehet nimetatakse binaarseks
Leibniz 1671: arvuti liitis, lahutas, korrutas, jagas. Kirjutusmasina inglise patent, Henry Mill, 1714 Remington: 1874 (jalgpedaaliga!) Sholes’ klaviatuur ca 1874(kasutatakse tänapäeval) Dvoraki klaviatuur ca 1936(ei kasuta) Ca 1800, Jacquard Perfokaardid 1822: Difference Engine Charles Babbage esimene programeeritav arvuti Esimene programmeerija: Ada Lovelace Morse 1837: elektritelegraaf Wheatstone 1857: perfolint George Boole, de Morgan- Loogika (lausearvutuse) alused 1847-1854 Gottlob Frege 1879 predikaatarvutuse.Näide: Isa(Jaan,Mihkel). Isa(Jaan,Ants). Isa(Ants,Peeter). Iga x, y, z jaoks: Isa(x,y) & Isa(y,z) => Vanaisa(x,z). 1890 Herman Hollerith- perfokaartidega masin USA rahvaloenduse andmete töötlemiseks. Hollerith’i firmast tekkis IBM. 1906 Lee Deforest- vakuumne triood Hulgateooria Georg Cantor 1910-1913 Russell & Whitehead: massiivne loogikatraktaat Formalism:Hilbert
m.a elanud Lüüdia kuningas Kröösus uuris Delfi oraaklilt järele, kas tasub minna sõjakäigule Pärsia vastu. Oraakel ütles: ``kui alustad sõda Pärsiaga, hävitad võimsa kuningriigi''. Oraaklilt julgustust saanud Kröösus ründaski Pärsiat, kuid kaotas. Hävis nimelt tema enda kuningriik! Lihtsustatuse tõttu on formaalsed keeled harilike keeltega võrreldes palju vaesemad, ning võimaldavad edasi anda ainult väga piiratud ampluaad väiteid. Üks lihtsamaid formaalseid keeli on nn. lausearvutuse keel. Viimases saab väiteid moodustada lihtväiteid tähistavatest tähtedest loogilist tähendust omavaid sidesõnu (ja,või,ei,kui...siis) tähistavate sümbolite ( &, Ú, Ø, ) abil. Mainitud olulistel sidesõnadel endilgi ei ole harilikus keeles täpset tähendust. ``Või'' esineb sageli tähenduses ``kas see või teine''. Lause ``ta on punapäine või meessoost'' on harilikus keelekasutuses kohatu. Klassikalise loogika jaoks on
h näide: x1 x ¯2 w= x2x1 w x ¯1 x2 e Kõik 3 elementaarset loogikatehet on juba eelpool lausearvutuse juures t defineeritud ja loogikaalgebras kehtivad nad täpselt samal kujul. Asendades siin muutujate x1 ja x2 asemele mingid loogikaväärtused, t i väärtustuvad võrduse mõlema poole avaldised alati ühtemoodi 0-ks või u
LAUSEARVUTUS Diskreetne matemaatika ei tegele reaalarvudega ega pidevate funktsioonidega. Verbaalne esitus on mistahes info esitamine lingvistilise keele abil. Formaalne esitus on mistahes info esitamine ilma lingvistilise keele abita ehk esitus kokkulepitud sümbolite abil. Formaalne esitus peab olema üheselt tõlgendatav. Lausearvutus on loogilise mõtlemise matemaatiline mudel. Lausearvutuse lause võib olla iga verbaalne väide, millele saame omistada tõeväärtuse – tõene või vale. Lihtlause on lihtsaim võimalik lausearvutuslause. Lausearvutuslauseid tähistatakse formaalselt suurtähtedega: A, B, P, Q … Lihtlausetest koostatakse kindlate sidesõnade ja loog konstruktsioonide abil liitlauseid. Lausearvutuse lihtlauseid seotakse liitlauseteks 5 loogilise konstruktsiooni ehk loogikatehte abil. Binaarsed loogikatehted seovad kahte lauset (4 tk), unaarne loogikatehe
■ Vastus: Vale f. Milliste joonisel kujutatud loogikaahelate kosted on identsed? Ehk teisisõnu: milliste ahelate puhul saate sisendparameetrite samade kombinatsioonide korral väljundis ühesuguse väärtuse. ■ Siin tuleb samuti oma DME teadmisi kasutada ja koostada vastavalt nendele joonistele lausearvutuse valemeid ning vaadata, missugused on samaväärsed (pmst paberi peale kõige parem teha) ■ Igale variandile a,b,...f vastab üks lausearvutuse valem kujul (L1 mingi tehe L2)mingi tehe(L1 mingi tehe L2), kus L1 ja L2 ees võib olla ka eitus see on siis, kui see väike mullike on (kas L1 või L2) joone lõpus, mis sinna loogikaelementi läheb.
LAUSEARVUTUS Diskreetne matemaatika ei tegele reaalarvudega ega pidevate funktsioonidega. Verbaalne esitus on mistahes info esitamine lingvistilise keele abil. Formaalne esitus on mistahes info esitamine ilma lingvistilise keele abita ehk esitus kokkulepitud sümbolite abil. Formaalne esitus peab olema üheselt tõlgendatav. Lausearvutus on loogilise mõtlemise matemaatiline mudel. Lausearvutuse lause võib olla iga verbaalne väide, millele saame omistada tõeväärtuse – tõene või vale. Lihtlause on lihtsaim võimalik lausearvutuslause. Lausearvutuslauseid tähistatakse formaalselt suurtähtedega: A, B, P, Q … Lihtlausetest koostatakse kindlate sidesõnade ja loog konstruktsioonide abil liitlauseid. Lausearvutuse lihtlauseid seotakse liitlauseteks 5 loogilise konstruktsiooni ehk loogikatehte abil.
Ada 1974- MITS (omanik Ed Roberts) completes the first prototype Altair 8800 Lovelace microcomputer 1837 Morse: elektritelegraaf Altair was one of the first successfully sold personal computer kits for do-it- 1857 Wheatstone: perfolint yourself computing fans 1847-1854 Loogika (lausearvutuse) alused G. BOOLE, de MORGAN 1974 Xerox Alto, personal computer to be used for research, first serious 1879: Kontseptuaalne notatsioon ("Begriffsschrift"), loob kaasaegse machine to feature a modern user interface: windows, mouse, etc invented predikaatarvutuse - GOTTLOB FREGE by Engelbart in 1964
sonal computer kit! lor do-it_ 1857 Wheatstone; perfolint your*ll cmPuting fans 1 97-i - N{icro-Soft(Crlcs jn Allcn). IBM 5 l {X) (csirncnc "liiprkas '). 1847-1854 Loogika (lausearvutuse) alused- G. BOOLE, de MORGAN 1974 - Xerox Alto, personal computer to be used tor tesearch, first serioua 1 879 : Kiltseplua alre notafsioon ("8egriff6schrift"), loob kaasaeqse machire to tature a hodern usea intelface: wihdows, mouse, etc invented lt)76 - Applc Conrputcr(Jobs. Woznirk). vi
täismahus mõistis Babbage'i ideesid, lõi täisautomaatse arvutusmasina jaoks programmi. Oleks täisautomaatne arvutusmasin valmis ehitatud, siis tema programm oleks oleks olnud võimeline arvutama Bernoulli numbrite järjestust/jada. Tänu sellele tööle on Lovelace'le kingitud esimese arvutiprogrammeerija tiitel. 1979ndal aastal anti kaasaegsele programmkeelele tema auks nimi Ada. Morse 1837: elektritelegraaf, Wheatstone 1857: perfolint George Boole, de Morgan Loogika (lausearvutuse) alused 1847-1854 Matemaatilise algebra ideede kasutamine loogika jaoks: Loogika algebra:1*A = A, 0*A = 0, A+0 = A, A+1 = 1,A+B = B+A, A*B = B*A, A*A = A Enimkasutatud tehted on: & (ja e. konjunktsioon) V (või e. disjunktsioon) - (ei e. eitus) => (järeldus e. implikatsioon) == (samasus e. ekvivalents) A& B AV B -A A => B -------- -------- ---- -------- TTT TTT VT TTT
— Graafid LAUSEARVUTUS — Kombinatoorika: Kombinatsioonid, Variatsioonid, Permutatsioonid Lausearvutus on loogilise mõtlemise matemaatiline mudel. Lausearvutuse lause võib olla iga verbaalne (ehk lingvistilises keeles väljendatud) väide, millele saame omistada tõeväärtuse — tõene või vale. Tõeväärtusi tähistame numbritega 0 ja 1.
täiendava eelduse korral teostama arutelu üldiselt üksikule või osalisele. 22_fl_vi-x L8 SÜLLOGISMID LIITVÄIDETEGA Igasugune väide kujul Kui p, siis q kannab nimetust konditsionaal (ik conditional). Esimene väide on alus ehk antetsedent (ld. antecedens, ik antecedent) teine on tagajärg ehk konsekvent (ld consequens ik consequent). Lausearvutuse defineerisime implikatsiooni Kui p, siis q, valemina p q binaarse tehtena, mis annab tõese lause alati, välja arvatud juhtum, kui esimene osalause (p) on tõene ning teine (q) väär. Sellist implikatsiooni nimetatakse ka materiaalseks implikatsiooniks (ik material implication). Materiaalne implikatsioon on konditsionaali kõige väiksema tugevusega (nõudlikkusega) vorm. Väljaspool lausearvutust on kasutusel väga erinevaid konditsionaale: nt selline, mis
sioonilises loogikas, sest too polnud piisavalt formaliseeritud. Sest propositsioonide asemel otsustustest rääkides ning ebaolu- lisi psühholoogilisi küsimusi sisse tuues jättis traditsiooniline loo- gika mulje, et tegeleb mingil eriliselt lähedasel viisil mõtte toi- mimisega. Tegelikult aga tegeles ta hoopis klasside formaalse suhtega, mida näitab fakt, et kõik selle tuletusprintsiibid on vii- dud Boole'i klassi-arvutuse alla, mis omakorda kuulub Russelli ja Whiteheadi lausearvutuse alla. (Vt Menger s.a.: 9496; ning Lewis, Langford 1932: ptk v.) Nende süsteem, mis on üksik- asjalikult esitatud Principia Mathematica's (Russell, Whitehead 191013), teeb selgeks, et formaalloogika ei tegele inimeste vai- mu omadustega ja veel vähem materiaalsete objektide omadus- tega, vaid lihtsalt võimalusega kombineerida propositsioone loo- giliste partiklite abil analüütilisteks propositsioonideks ja nende analüütiliste propositsioonide vahelise formaalse suhte uurimi-
aastal kangastelgede juhtimiseks. Joseph Marie Jacquard täiustas märgatavalt seda töötamisviisi oma Jaquard'i kangasteljega. CHARLES BABBAGE 1822 1822: Difference Engine, jäi pooleli Idee: Analytical Engine Esimene programmeerija: Ada Lovelace Inglise matemaatik, filosoof, leiutaja ja mehaanikainsener, kellelt pärineb programmeeritava arvuti mõiste. On esimese mehaanilise automaatkalkulaatori (arvuti) loojaks ja seega pani ta aluse arvutite arenguloole. GEORGE BOOL DE MORGAN Loogika (lausearvutuse) alused 1847-1854 Matemaatilise algebra ideede kasutamine loogika jaoks: Loogika algebra: 1A = A, 0A = 0, A+0 = A, A+1 = 1 A+B = B+A, AB = BA, AA = A Enimkasutatud tehted on & (ja e. konjunktsioon) V (või e. disjunktsioon) - (ei e. eitus) => (järeldus e. implikatsioon) == (samasus e. ekvivalents) GOTTLOB FREGE 1879 loob kaasaegse predikaatarvutuse Näide: Isa(Jaan,Mihkel). Isa(Jaan,Ants). Isa(Ants,Peeter). Iga x, y, z jaoks: Isa(x,y) & Isa(y,z) => Vanaisa(x,z).
Ameerika patent: 1829 William Austin Burt Detroidis 1867, Christopher Latham Sholes, Carlos Glidden, Samual W. Soule leiutis: “Type-Writer“ Remington: 1874 (jalgpedaaliga!) Sholes’ klaviatuur ca 1874 (qwerty) Dvoraki klaviatuur ca 1936 Perfokaardid - ca 1800, Jacquard. Charles Babbage 1822: Difference Engine, jäi pooleli Idee: Analytical Engine esimene programmeerija: Ada Lovelace Telegraaf - Morse 1837: elektritelegraaf, Wheatstone 1857: perfolint George Boole, de Morgan Loogika (lausearvutuse) alused 1847-1854. Matemaatilise algebra ideede kasutamine loogika jaoks: Loogika algebra: 1A = A, 0A = 0, A+0 = A, A+1 = 1, A+B = B+A, AB = BA, AA = A Loogikatehted on funktsioonid tõeväärtustel T ja V. Enimkasutatud tehted on & (ja e. konjunktsioon) V (või e. disjunktsioon) - (ei e. eitus) => (järeldus e. implikatsioon) == (samasus e. ekvivalents) A& B AVB - A A => B -------- -------- ---- -------- TTT TTT VT TT T
Polünomiaalse keerukusega algoritmid: O(nd) Ülesanded, mille jaoks leidub polünomiaalse keerukusega algoritm, nim reaalselt lahenduvateks. Keskmine ja halvim keerukus. 34. NP ja NP-täielikud ülesanded. Ülesannete keerukuse klassid. Põhiline on polünomiaalse keerukusega ülesannete klass reaalselt lahenduvad. NP mittedeterministlikult polünomiaalne. Ülesanded, mis on lahendatavad mittedeterministlikul Turingi masinal polünomiaalse ajaga. Nt lausearvutuse valemis true leidmine. Seljakotiülesanne (leia max erinevaid asju seljakotti, nii, et ei ületataks kaalu). Graafis tee leidmine Hamiltoni meetodil. Graafis kõigi tippude läbimiseks lühima tee leidmine. NPC klass NP ülesannete grupid, mis on taandatavad teineteisele. Näiteks on kõik eelnevad ülesanded taandatavad seljekotiülesandele.
“Type-Writer“ Remington: 1874 (jalgpedaaliga!) Sholes’ klaviatuur ca 1874: Dvoraki klaviatuur ca 1936 Kirjutusmasin püssitehasest Perfokaardid ca 1800 Jacquard Charles Babbage 1822: Difference Engine, jäi pooleli Idee: Analytical Engine esimene programmeerija: Ada Lovelace Telegraaf Morse 1837: elektritelegraaf Wheatstone 1857: perfolint 1902-1910: teleprinter George Boole, de Morgan Loogika (lausearvutuse) alused 1847-1854 Matemaatilise algebra ideede kasutamine loogika jaoks: Loogika algebra: 1A = A, 0A = 0, A+0 = A, A+1 = 1 A+B = B+A, AB = BA, AA = A Loogikatehted on funktsioonid tõeväärtustel T ja V. Enimkasutatud tehted on & (ja e. konjunktsioon) V (või e. disjunktsioon) - (ei e. eitus) => (järeldus e. implikatsioon) == (samasus e. ekvivalents)
annaabi.ee 
