1. Sissejuhatus: 1.1. Mis on loogiline programmeerimine? l Programmeerimise paradigma l loogiline (LP) l funktsionaalne (FP) l jt Fookus: MIDA ARVUTADA l LP ja FP on deklaratiivsed programmeerimisstiilid; l LP põhineb loogika printsiipidel ja kasutab automaattõestamise protseduure (resolutsioon, unifitseerimine); l LP keel on Prolog, kuid LP ≠ Prolog; 1.1. Mis on loogiline programmeerimine? (2) l LP sobib tehisintellekti rakenduste programmeerimiseks: l loomuliku keele analüüs ( DCG grammatikareeglid) l ekspertsüsteemid (otsingu- ja järeldusreeglid) l kujundituvastus (tuvastusreeglid) l kitsendustega planeerimine (logistika, marsruudi otsimine) l rekursiivsete funktsioonide püsipunkti arvutus l jne l LP ei sobi: l Kiired numbrilised arvutused (n. maatriksarvutused, võrrandid) l OOP (kuigi on toetatud mõnes prologis) l kasu...
x2 x = xx2 , st (x, x) R. · Relatsioon on sümmeetriline, sest kui x2 y = xy 2 , siis ka y 2x = yx2 (need kaks võrdust on teineteisega samaväärsed), st kui (x, y) R, siis ka (y, x) R. · Relatsioon on transitiivne, sest kui x2 y = xy 2 ja y 2z = yz 2 , siis nende võrduste korrutamisel saame x2 y 3z = xy 3 z 2 , millest võime järeldada, et x2 z = xz 2 , sest y 3 on eelduse kohaselt positiivne täisarv (st nullist erinev). Järelikult on ka transitiivsuse tingimus täidetud: kui (x, y) R ja (y, z) R, siis ka (x, z) R. Seega see relatsioon on ekvivalents. Materjal õpikus. Lk 9092 (ekvivalentsirelatsioon). Lk 9495, ülesanded 510, 1924. Kontrolltöö lahendused Diskreetsed struktuurid 3. variant Ülesanne 1. Kirjanduskriitikute kongressil tuleb kritiseerimisele 7 novelli, 7 romaani, 7 luulekogumikku ja 7 naljakogumikku. Selleks, et Toomas saaks
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
Eitusega võivad kaasneda sekundaarsed modifikatsioonid: · sõnajärje muutused · aspekti ja aja neutraliseerumine eitavad lauses (nt komi keeles) · objektikäände muutus (nt vene ja eesti keeles: mul on raamat_ vs mul ei ole raamatut). Nt maungi k on eitus võimalik ainult irreaalsete verbivormidega. 32. Valents ehk verbi ühildumine kui palju verb enda külge liita saab. Verbid on kas intransitiivsed (sihitiseta), transitiivsed (sihiline), ditransitiivne. Otsest seost valentsi ja transitiivsuse vahel pole. Intransitiivsed on 1-valentsed tüüpiliselt, transitiivsed üldiselt 2- ja ditransitiivsed 3- valentsed. Ilmastikuverbid ei kuulu tüüpilistesse rühmadesse, tihti peetakse neid 0-valentseteks. Valentsi saab grammatiliste operatsioonide abil suurendada ja vähendada. Jooksma-verb ise on 1-valentne, aga kuna ma saan idee poolest kirjutada jooksma+soola (tähendus: ,,jooksen poodi soola järele"), siis kas ma siis muutsin verbi 2-valentseks? See ei pruugi nii olla
põhjus, mis omakorda halvendab turu kui majandusmehhanismi toimimist. Näide informatsiooni ebasümmeetriast: kindlustusturg (elukindlustus). Kindlustuse ostjal palju rohkem informatsiooni oma tervise ja sellega seotud riskide kohta kui müüjal (kindlustusfirmal). Situatsiooni tasakaalustamisek on võimalikud samuti mitmesugused meetmed (arstlik kontroll jne). 28.Avage hääletamisparadoksi olemus. Millest sõltub hääletamistulemus? Loogikast on tuntud transitiivsuse omadus, mille kohaselt sellest, et kui a on suurem kui b ja b on suurem kui c, järeldub, et a on ka suurem kui c. Politiiliste valikute puhul aga transitiivsuse omadus ei pruugi kehtida. Kujutame olukorda, kus I valija eelistus kolme variandi vahel on järjekorras A, B ja C. II valija järjekord variantide osas on C, B ja A ning III valijal B,C ja A. Antud juhul võidab variant B varianti A 2:1, variant B võidab samuti varianti C häältega 2:1 ning ka C võidab A-d 2:1. Seega saame
Seega A C. 4. Oletame väite vastaselt, et leidub mittetühi hulk A nii, et A. Definitsiooni kohaselt peab siis leiduma element x hulgast , mis ei kuulu hulka A. See on aga võimatu, sest hulgas ei leidu ühtegi elementi. Seega A iga hulga A korral. Lause Tühi hulk on üheselt määratud. TÕESTUS Olgu 1 ja 2 kaks tühja hulka. Peame näitama, et 1 = 2. Kuna 1 on tühihulk siis transitiivsuse omaduse tõttu 1 2. Samuti selle sama omaduse tõttu 2 1. Ja Antisümmeetrilisuse omaduse põhjal need tühjad hulgad on võrdsed ehk see näitab ära, et tühjad hulgad on üheselt määratud. Pärisosahulk Definitsioon Hulka A nimetatakse hulga B pärisosahulgaks ja kirjutatakse A B, kui hulk A on hulga B osahulk ja A B. Näide: 1. Kui S = {4, 5, 7} ja T = {3, 4, 5, 6, 7}, siis S T. 2
transitiivne. Elemendiga a (A element) ekvivalentsete elementide hulka nimetatakse a ekvivalentsiklassiks (hulgal A). Elemendiga a ekvivalentsete elementide hulka tähistatakse [a] = {b | aRb}, kus R on ekvivalentsiseos. Teoreem 1: Ekvivalentsiseos R hulgal A. Iga elemendipaari a ja b korral kehtib seos [a] = [b] või [a] ühisosa [b] on tühihulk. Tõestus: Kuna R on sümmeetriline ja transitiivne, näitame, et kui aRb ja suvaline element [a]-st on z, siis sümmeetria tõttu bRa ja aRz transitiivsuse järgi bRz ehk siis z kuulub [b]. Siit nähtub, et [b] on alamhulgaks [a]-le. Analoogselt tõestame, et [a] on alamhulgaks [b]-le. Kui not(aRb), eeldame vastuväiteliselt, et eksisteerib y, mis kuulub korraga nii [a] kui [b]. ehk aRy ja bRy. Sümmeetria tõttu yRb, millest transitiivuse alusel aRb, mis on vasutolus esialgse väitega. Voila! Relatsiooni aste: R on seos hulgal A. R aste Rk on (aR1b = aRb; aR2b, kui aRcRb)
Kompositsiooni definitsiooni põhjal (x, z) ∈ Rk ◦ Rl = Rk+l ning järelikult (x,z) ∈ ∪∞i=1Ri. Olgu nüüd S mingi transitiivne relatsioon, mis sisaldab relatsiooni R. Valime suvalise paari (x, y) ∈ ∪∞ i=1Ri. Sel juhul (x, y) ∈ Rk mingi k > 1 korral ning teoreemi 6 põhjal leiduvad elemendid z0, . . . , zk nii, et z0 = x, zk = y ja iga i = 0, . . . , k−1 korral (zi, zi+1) ∈ R. Ent siis ka (zi, zi+1) ∈ S ning relatsiooni S transitiivsuse tõttu (x, y) ∈ S. Järelikult kehtib ∪∞ i=1Ri ⊆ S. Et vaadeldav relatsioon ∪∞ i=1Ri sisaldab ka relatsiooni R, siis rahuldab ta kõiki transitiivse sulundi tingimusi ja peab seega võrduma relatsiooniga R+. Transitiivse ja refleksiivse-transitiivse sulundi avaldiste seos ahelatega relatsiooni graafis +¿ o ( x , y ) ∈R¿ tähendab, et leidub suunatud ahel tipust x tippu y. 28
- Väärtuse ignoreerimine – kui alternatiividel on sama tõenäosusega sarnased tulemid peaks tulemse kaslikkust otsustamisel mitte arvestama - Järjepidevus – inimeste eelistus peaks alati kuuluma riskile kui suurepärase tulemuse saavutamise tõenäosus on piisavalt kõrge võrreldes kindla peale saavutatava rahuldava tulemusega - Invariantsus – otsustamist ei mõjuta alternatiivide esitamise viis Kuidas inimesed tegelikult valivad? - Transitiivsuse eiramine – sageli tuuakse alternatiivide kaalumisel sisse kolmas muutuja mis esmapilgul võiks olla sekundaarne, ent teatud juhtudel võib primaarse tunnuse erinevuse jätta tahaplaanile - Otsustamisel ignoreeritakse väärtuste erinevust – inimesed ei võta otsustamisel alati arvesse mõlemat – sündmuse väärtust ja sündmuse tõenäosust - Inimeste eelistused ja väärtus mida nad valikutele omistavad muutuvad sõltuvalt
Kuna punkt x ∈ X on u ¨hendatav iseenda- ga konstantse teega (l(t) = x iga t ∈ I korral), siis (x; x) ∈ σ ja σ on refleksiivne. Kui (x; y) ∈ σ, siis leidub punkte x ja y u¨hendav tee l : I −→ X, l(0) = x, l(1) = y. Aga tee r : I −→ X, mis on defineeritud v˜ordusega r(t) = l(1 − t), t ∈ I, ¨hendab siis punkte y ja x, st (y; x) ∈ σ ja seos σ on s¨ u ummeet- riline. Seose σ transitiivsuse n¨aitamiseks eeldame, et (x; y) ∈ σ, (y; z) ∈ σ (8.19) ja n¨aitame, et (x; z) ∈ σ. Seose (8.19) p˜ohjal leiduvad teed l ja r nii, et l(0) = x, l(1) = y, r(0) = y, r(1) = z. 96 8 SIDUSUS Defineerime kujutuse s : I −→ X reegliga 1 s(t) = l(2t), kui 0 ≤ t ≤ , 2
numbers, натуральные числа). Järgnevalt viime naturaalarvude hulka sisse liitmise ja korrutamise. See toimub rekursiivselt: nõuame, et a+1 = S(a) ja a+S(b) = S(a+b), kus a, b ∈ N. Korrutamine: a·1 = a ja a·S(b) = a+(a·b). Kontroll näitab, et liitmine ja korrutamine on assotsiatiivsed, kommutatiivsed ning on seotud distributiivsuse võrdustega. Defineerime veel, et a < b ⇔ ∃c ∈ N : a+c = b. Saadud seos < rahuldab trihhotoomia, transitiivsuse, liitmise ja korrutamise monotoonsuse nõudeid. Märkus. Sageli defineeritakse hoopis 0 = ∅ ning viiakse läbi ülaltoodud konstruktsioon, tulemuseks saadakse N = {0, 1, 2, . . .}. Nüüd koostame täisarvude hulga. Defineerime selleks hulgas N × N järgmise seose: (a, b) ∼ (c, d) ⇔ a + d = b + c. Kontroll näitab, et seos ∼ on ekvivalentsusseos; faktorhulka N × N/ ∼ tähistame tähega Z ja tema elemente nimetame täisarvudeks (integers, целые числа).
annaabi.ee 
