Diskreetne matemaatika KODUTÖÖ SISUKORD SISUKORD..........................................................................................1 ÜLESANNE 1 LOOGIKAFUNKTSIOON......................................................3 ÜLESANNE 2 TÕEVÄÄRTUSTABEL..........................................................3 ÜLESANNE 3 MINIMAALSED NORMAALKUJUD........................................3 3.1 MDNK KARNAUGH’ KAARDIGA.......................................................................3 3.2 MKNK MCCLUSKEY MEETODIGA.....................................................................4 3.3 VÕRDLUS....................................................................................................... 5 ÜLESANNE 4 MKNK TEISENDAMINE DNK-KUJULE....................................5 ÜLESANNE 5 DISJUNKTIIVSED NORMAALKUJUD...................
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...
Referaat Johanna-Margret Kakko 2010 SISUKORD ANDMEBAASID. Informatsioon ja andmed. Andmebaaside põhifunktsioonid. Andmebaaside tüübid. Andmelaod ja andmeaidad. ANDMEBAASIDE PÕHIMÕISTED. Objektid, atribuudid, võtmed, indeksid. Seosed 1:1, 1:M, M:M. Atribuutide tüübid. Normaliseerimine, normaalkujud (3). Semantilised mudelid (UML). Andmebaaside käivitamine (installeerimine, avamine). Uue andmebaasi loomine (objektsüsteemi analüüs). Olemasoleva andmebaasi kopeerimine. TÖÖ TABELITEGA. Tabeli väljade lisamine, kustutamine, ümbernimetamine. Primaarne võti. Väline võti. Unikaalne entifikaator. Tabelite seostamine (relatsioonid). TÖÖ ANDMETEGA. Andmete sisestamine töökirjetega. SQL KEELE ALUSED. Standardid (syntaks). Loogilised operaatorid. ANDMEBAASIDE KASUTAJAD. Kasutajad.
1 0 1 1 0 1 1 0 0 1 1 1 0 1 - 1 1 1 0 0 1 1 1 1 1 ÜLESANNE 3 MINIMAALSED NORMAALKUJUD Leian MDNK ja MKNK, mis sobiksid matriklinumbrist leitud osaliselt määratud 4-muutuja funktsiooni esitamiseks. MDNK Karnaugh’ kaardiga ja MKNK McCluskey' meetodiga. 3 3.1 MDNK KARNAUGH’ KAARDIGA Leian MDNK Karnaugh kaardiga, sest matriklinumber on paarisarv. Funktsioon 𝒇(x(x1,x2,x3,x4) = ∑ ( 3, 5, 8, 12, 15 )1 ( 4, 9, 13 )_ x1x2/x3x4 00 01 11 10
i t u kolmas võimalik / sobiv t kontuuridevalik fD = x¯1 x3 w ¯2 x x ¯4 In s ükski 3st sobivast kontuuridevalikust pole ülejäänud kahe suhtes parem / vaatleme, milleks arvutuvad leitud normaalkujud määramatuspiirkonnas. pole eelistatud, kuna kõik nad kasutavad 3 tk 4-ruudulisi kontuure ehk Milleks arvutub leitud MDNK funktsiooni määramatuspiirkonnas ? kõik nad annavad sama keerukusega KNK Kirjutame MKNK välja esimesest kontuuridevalikust: f D (0011) = ? f D (1110) = ? x 3 x4
u x 1 x2 00 01 11 10 t i t fD = x¯1 x3 w x¯2 x¯4 00 1 0 1 In s vaatleme, milleks arvutuvad leitud normaalkujud määramatuspiirkonnas. 01 0 0 1 1 Milleks arvutub leitud MDNK funktsiooni määramatuspiirkonnas ? 11 0 0 0 f D (0011) = ? f D (1110) = ? 10 1 0 0 1
2 3* 2 — 3* 1 10 1 0 0 1 10 1 0 0 1 6 2—6 4 10 2 — 10 8 . . . . kuid nüüd leiame minimaalsed normaalkujud McCluskey' meetodiga 8 — 10 2 3 7 14* 3—7 4 MDNK leidmine: 4 6—7 1
— Hulgad: Hulgaalgebra (Cantori algebra), Hulgaaritmeetika (taastada). — Loogika: Lausearvutus, Predikaatarvutus, Tõestusmeetodid Mistahes formaalne esitus peab olema üheselt tõlgendatav! — Loogikaalgebra (Boole'i algebra) — Loogikafunktsioonid: minimeerimine, normaalkujud . . . — Algebralised struktuurid: "mitteformaalne" ≡ "verbaalne" (sünonüümid) Fundamentaalalgebrad: Võred, Rühmad, Ringid, Korpused — Vastavused ja Relatsioonid MATEMAATILINE LOOGIKA — Graafid LAUSEARVUTUS
ühel väärtustusel tõene Valemeid F ja G nimetatakse samaväärseteks, kui nende tõeväärtused on võrdsed igal neis valemeid esinevate muutujate väärtustusel Ü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 Lausearvutuse põhisamaväärsused eraldi lehel!! 2. NORMAALKUJUD Lausearvutuse valemi F täielikuks disjunktiivseks normaalkujuks (TDNK) nimetatakse valemiga F samaväärset valemit, mis kujutab endast erinevate täielike elementaarkonjuktsioonide disjunktsiooni o Täielik disjunktiivne normaalkuju on tõene parajasti nendel väärtustustel, mis vastavad normaalkuju liikmetele o X111 & ... & Xn1n X121 & ... & Xn2n ... X1m1 & ... & Xnmn on tõene väärtustustel (11, ..., 1n), (21, ..., 2n), ..., (m1, ..
võimalik andmete liiasust täielikult elimineerida ja seda pole ka sageli vaja. Mõistetest: Kasutan relatsioonilise mudeli mõisteid (relvar, relatsioon, atribuut, korteez). relvar relatsiooniline muutuja. Tutvustatavad disaini headuse kontrolli ja parandamise meetodid on rakendatavad ka SQL-andmebaaside korral. Tehke mõttes asendus: relvar tabel, relatsioon tabel, atribuut veerg, korteez rida. Normaalkujud: Relvar on mingil normaalkujul, kui see rahuldab kõiki selle normaalkujuga seotud tingimusi. Relvar, mis on normaalkujul N on ka kõigil madalamatel normaalkujudel. See ei pruugi olla kõrgematel normaalkujudel N+1, N+2 jne. Normaliseerimata andmed: 22. Esimene normaalkuju (teema 9) Relvar on normaliseeritud e. esimesel normaalkujul, kui selle iga legaalse väärtuse igas korteezis on iga atribuudi kohta täpselt üks väärtus, mis on selle atribuudi tüüpi.
x x x3 x2 x1 1 4 ( 1 2 ( x x x4 ) ) · Tõestada DeMorgani seadused 3 muutuja jaoks nii tõeväärtustabeliga kui ka valemiliselt. · Antud kolme muutuja nn. mazhoritaarfunktsioon: f ( x1 , x2 , x3 ) = x1x2 x2 x3 x1 x3 . Tõestada, et kehtivad järgmised võrdused: f ( x1 , x2 , x3 ) = x2 f ( x1 , x2 , x3 ) = f ( x1 , x2 , x3 ) Loogikafunktsioonide normaalkujud Loogikafunktsioon f(x1 , x2 ,..., xn ) võib olla esitatud erinevate valemite abil. 11 Näiteks f ( x1 , x2 ) = x1 x2 = x1 x2 x2 = ( x1 x2 x1 x2 x2 )( x2 x2 ) =............. · Loogikafunktsiooni kanoonilisi standardseid esitusvalemeid nimetatakse funktsiooni normaalkujudeks. · Disjunktiivne normaalkuju (DNK) on valem, mis koosneb elemantaarkonjunktsioonide disjunktsioonist.
x x 1 2 x4 Tõestada DeMorgani seadused 3 muutuja jaoks nii tõeväärtustabeliga kui ka valemiliselt. Antud kolme muutuja nn. mazhoritaarfunktsioon: f x1 , x2 , x3 x1x2 x2 x3 x1x3 . Tõestada, et kehtivad järgmised võrdused: f x1 , x2 , x3 x2 f x1 , x2 , x3 f x1 , x2 , x3 Loogikafunktsioonide normaalkujud Loogikafunktsioon f(x1 , x2 ,..., xn ) võib olla esitatud erinevate valemite abil. Näiteks f x1 , x2 x1 x2 x1 x2 x2 x1 x2 x1 x2 x2 x2 x2 ............. Loogikafunktsiooni kanoonilisi standardseid esitusvalemeid nimetatakse funktsiooni normaalkujudeks. Disjunktiivne normaalkuju (DNK) on valem, mis koosneb elemantaarkonjunktsioonide disjunktsioonist.
kõigi selliste mitteterminaalide A jaoks, mille korral B kuulus N A Ehk siis .. lisame uue grammatika produktsioonideks need, mille korral mitte-ahelproduktsioon B ei saa ahelproduktsiooniks Redutseeritud grammatika definitsioon: KV grammatikat G = (,N,P,S) nimetatakse redutseerituks, kui see ei sisalda tsükleid, -reegleid ja kasutuid sümboleid. Iga KV keele jaoks leidub genereeriv redutseeritud grammatika. 15. KV-grammatikate normaalkujud. Chomsky normaalkuju: KV-grammatika G = (,N,P,S) öeldakse olevat Chomsky normaalkujul, kui see sisldab produktsioone järgnevatel kujudel: A BC (kõik on mitteterminaalid) A b (b on terminaal, a mitteterminaal) S (S on lähtesümbol, mis ei esine ühegi produktsiooni paremas pooles) Iga KV grammatika evib Chomsky normaalkuju. Chomsky normaalkuju korral on sõna tuletuspuuks kahendpuu. Greibachi normaalkuju:
F ↔ G ≡ F & G ∨ ¬F & ¬G, F ↔G ≡ (F → G) & (G → F Valemite teisendamine samaväärsuste abil 6 Samaväärsuste kasutamine teisendustes seisneb valemi mingi osavalemi asendamises temaga samaväärsega. Nagu algebras, säilitab selline osavalemi asendamine ka siin samaväärsuse ka terve valemi jaoks. Peamised kujud, millele teisendatakse, on: ○ esitused kahe tehte kaudu ○ nn normaalkujud Teoreem piisavatest tehete komplektidest Iga lausearvutuse valemi jaoks leidub temaga samaväärne valem, mis ei sisalda muid tehtemärke kui: ○ ¬, & ○ ¬, ∨ ○ ¬, → Tõestus: kolm ülejäänud tehet saab avaldada antud komplekti kaudu 5. Järeldumine. Teoreemid järeldumise ja samaväärsuse taandamisest ühe valemi omaduste kontrollimisele. [1] Järeldumine o DEF: Ütleme, et valemitest F1 , F2 , . . . , Fn järeldub valem G, kui igal neis valemeis
(h) Kui sajab vihma, siis ei saja lund ja on suvi. (i) Kui on külm või sajab lund, siis ei saja vihma. (j) Suvel ei saja korraga vihma ja rahet. (k) Suvel sajab vihma või rahet, talvel lund. 4.0.2. Lugeda, kasutades samu tähistusi: (a) E F D; (b) D B & F A & E; (c) E & G & D C; (d) E & B G; (e) F & H & D A. 21_fl_i-v NORMAALKUJUD Mitmesugustel põhjustel (nt ülesannete lahendamine, teoreemide tõestamine, etteantud omadustega valemi otsimine) on kasulik viia laused ühesuguse välise kujuga vormi. Literaal on lausemuutuja (positiivne literaal nt B) või lausemuutuja eitus (negatiivne literaal nt ¬B). Mingile lausemuutujate hulga puhul saame koostada elementaarkonjunktsiooni ehk konjunkti (ehk lihtkonjunktsiooni), milles erinevad literaalid on omavahel seotud konjunktsiooni abil.
veergude A, B ja C vahel) tähendab seda, et veerus A olevale väärtusele vastab hulk väärtuseid veerus B ja hulk väärtuseid veerus C. Veerus B ja C olevad väärtused on üksteisest sõltumatud. Seda tähistatakse: A ->> B A ->> C Mitmeväärtuseline sõltuvus on mittetriviaalne, kui on täidetud mõlemad järgmised tingimused: 1) BA ; 2) AB R 34 NORMAALKUJUD: Tabel on normaliseerimata kujul, kui ta lahtrites on korduvaid andmeelemente. Esimene normaalkuju (1NF) Def. Tabel on esimesel normaalkujul, kui tema igas lahtris on atomaarne andmeelement ja ta ei sisalda korduvaid veergude gruppe. Tegevused: 1. Korduvate andme-elementide likvideerimine. 2. Veergude grupi põhjal uue tabeli loomine. 3. Liit-andme-elementide eemaldamine. Esimesel normaalkujul oleva tabel ei tohi sisaldada nn. massiive või teisi tabeleid.
.. , pn ühises tõeväärtustabelis pole ühtegi rida, milles need väited kõik tõesed oleksid. Kui väidetesüsteem on kooskõlaline, siis on olemas tõeväärtusjaotus, mille puhul on kõik väidetesüsteemi väited tõesed. Väidetesüsteemi uurimisel võib olla mõistlik neid esitada mõnel nn normaalkujul. 4 Mõnikord vaadeldakse väidete hulkade asemel väidete jadasid. See on tähtis siis, kui oluline on väidete esitamise järjekord, antud juhul seda ei vaadelda. 18 NORMAALKUJUD Mitmesugustel põhjustel, nt ülesannete lahendamine, teoreemide tõestamine, etteantud omadustega valemi otsimine, on kasulik viia laused ühesugusele välisele kujule. Teksti lühendamise huvides on mõistlik defineerida termin literaal, mis rakenduks nii lausemuutujale kui ka selle eitusele. Literaal on lausemuutuja (positiivne literaal, nt B) või lausemuutuja eitus (negatiivne literaal, nt ¬B). Mingi lausemuutujate hulga (väidetesüsteemi)
Kui väidetesüsteem on kooskõlaline, siis on olemas tõeväärtusjaotus, mille puhul on kõik väidetesüsteemi väited tõesed. Väidetesüsteemi uurimisel võib olla mõistlik neid esitada mõnel nn normaalkujul. 4 Mõnikord vaadeldakse väidete hulkade asemel väidete jadasid. See on tähtis siis, kui oluline on väidete esitamise järjekord, antud juhul seda ei vaadelda. 18 NORMAALKUJUD Mitmesugustel põhjustel, nt ülesannete lahendamine, teoreemide tõestamine, etteantud omadustega valemi otsimine, on kasulik viia laused ühesugusele välisele kujule. Teksti lühendamise huvides on mõistlik defineerida termin literaal, mis rakenduks nii lausemuutujale kui ka selle eitusele. Literaal on lausemuutuja (positiivne literaal, nt B) või lausemuutuja eitus (negatiivne literaal, nt ¬B). Mingi lausemuutujate hulga (väidetesüsteemi)
annaabi.ee 
