2011 Diskreetne Matemaatika Eksam 1. Mis on graafi värvimise ülesanne? Mis on kromaatiline arv? Joonistada mõni näide. Mis on kromaatiline arv 2 aluselisel graafil? Mis on täieliku graafi kromaatiline arv? 2. Hulgateooria mõiste sümmeetrilise vahe kohta. Taandada sümeetriline vahe cantori normaalkujuks. Kas see täielik normaalkuju on minimaalne? Taandatud? Täielik? Mis on sümmeetrilise vahe matemaatilises loogikas? 3. Avaldis (x1x2x3x4) = Mingi konjuktiivne funktsioon (ei mäleta) 1. Leida minimaalne DNK 2. Leida taandatud KNK 4. Funktsioon (x1x2x3) = E(0,2,5,6,7)1 1. Leida täielik KNK 2. Leida shannoni arendus DNK x2 järgi. 3. Leida tuletis x3 järgi. Jääk ära näidata minimaalsel kujul.
Mitme hulga diagramm on suurim Venni diagramm, mis osutub piisavalt ülevaatlikuks ja kasutuskõlblikuks? 4 Millised järgnevad võrdused on korrektsed Grassmanni valemid? Kolmas (3) Neljas (4) Millised tehted võivad sisalduda hulgaavaldise Cantori normaalkujus? Ühend, täiend, ühisosa Mis on (lõpliku) hulga võimsus? Hulgas sisalduvate elementide arv Misnimelise reegli/seaduse abil saab mittetäieliku Cantori normaalkuju teisendada täielikuks Cantori normaalkujuks ? - Kleepimisseadus Kui sulgudega pole määratud teisiti, siis milline on hulgatehete prioriteet avaldises? Kõigepealt TÄIEND Seejärel ÜHISOSA Kolmandana ÜHEND Verbaalne nimetus igale hulgale. Esimene hulkade ühisosa Teine hulkade võimsuste summa Kolmas element kuulub hulka Neljas hulkade summeetriline vahe Viies - hulkade lahutamine(Vahe) Kuues ühendi täiend Seitsmes ühisosa täiend Kaheksas - otsekorrutis ehk ristkorrutis
Küsimus 1 Õige / Hinne 1,00 / 1,00 Millised järgnevad võrdused on korrektsed Grassmanni valemid ? Vali üks või enam: 1. 2. 3. 4. 5. 6. Küsimus 2 Õige / Hinne 1,00 / 1,00 Misnimelise reegli/seaduse abil saab mittetäieliku Cantori normaalkuju teisendada täielikuks Cantori normaalkujuks ? ( sisesta ühesõnaline vastus ) Vastus: kleepimisseadus Küsimus 3 Õige / Hinne 1,00 / 1,00 Mitme hulga diagramm on suurim Venni diagramm, mis osutub piisavalt ülevaatlikuks ja kasutuskõlblikuks ? ( sisesta number või sõna ) Vastus: 4 Küsimus 4 Õige / Hinne 1,00 / 1,00 Kui sulgudega pole määratud teisiti, siis milline on hulgatehete prioriteet avaldises ? kõigepealt teostatakse hulgaavaldises TÄIEND ..
Alustatud esmaspäev, 21. detsember 2020, 13.53 Olek Lõpetatud Lõpetatud esmaspäev, 21. detsember 2020, 14.03 Aega kulus 10 min 45 sekundit Hindepunktid 13,00/13,00 Hinne 100,00, maksimaalne 100,00 Küsimus 1 Õige Hindepunkte 1,00/1,00 Misnimelise reegli/seaduse abil saab mittetäieliku Cantori normaalkuju teisendada täielikuks Cantori normaalkujuks ? ( sisesta ühesõnaline vastus ) Vastus: kleepimisseadus Küsimus 2 Õige Hindepunkte 1,00/1,00 Millise hulgatehte tulemus on hulgaelementide järjestatud paaride hulk ? ( sisesta ühesõnaline vastus ) Vastus: ristkorrutis Küsimus 3 Õige Hindepunkte 1,00/1,00
.. 4. vasakpoolne avaldis võrdub ... Küsimus 8 Misnimelise reegli/seaduse abil saab Õige mittetäieliku Cantori normaalkuju teisendada Mark 1 out of 1 täielikuks Cantori normaalkujuks ? ( sisesta ühesõnaline vastus ) Vastus: kleepimisseadus Küsimus 9 millised järgnevad võrdused kehtivad alati ? Õige Mark 1 out of 1 Vali üks või enam: 1.
järeldub valem F. Teoreem. Valemid F ja G on samaväärsed parajasti siis, kui valem FG on samaselt tõene. Literaal on lausemuutuja või tema eitus. Positiivne literaal on puhas lausemuutuja. Negatiivne literaal on eitusega lausemuutuja. Täielik elementaarkonjuktsioon on literaalidest L1,L2,...,Ln koostatud valem L1&L2&...&Ln. Täielik disjunktiivne normaalkuju Lausearvutuse valemi F täielikuks disjunktiivseks normaalkujuks nimetatakse valemiga F samaväärset valemit, mis kujutab endast erinevate täielike elementaarkonjuktsioonide disjunktsiooni. Täielik elementaardisjunktsioon on literaalidest L1,L2,...,Ln koostatud valem L1vL2v...vLn. Täielik konjuktiivne normaalkuju - Lausearvutuse valemi F täielikuks konjuktiivseks normaalkujuks nimetatakse valemiga F samaväärset valemit, mis kujutab endast erinevate täielike elementaardisjunkttsioonide konjuktsiooni. Hulgateooria alusmõisted: 1
ü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, ..., mn) ja väär kõigil ülejäänud väärtustustel
LITERAAL on lausemuutuja(pos) või lausemuutuja eitus(neg). Mingi lausemuutuja hulga puhul saame koostada ELEMENTAARKONJUNKTSIOONI ehk konjunkti( ehk lihtkonjunktsiooni), milles erinevad literaalid on omavahel seotud konjunktsiooni abil. Sama hulga puhul saame koostada ka ELEMENTAARDISJUNKTSIOONI ehk disjunkti, milles erinevad literaalid on omavahel seotud disjunktsiooni abil. Valemi F DISJUNKTIIVSEKS NORMAALKUJUKS nimetatakse valemiga F samaväärset valemit, mis kujutab endast erinevate lihtkonjunktsioonide disjunktsiooni. Nt A1 & B1... v A2 & B2... v ... PREDIKAATLOOGIKA Hulgal M määratud ühekohaline predikaat ehk UNAARNE PREDIKAAT Px on kujutus(funktsioon), mis seab igale hulga M elemendile(indiviidile) x vastavusse ühe kindla tõeväärtuse tõene(1) või väär(0). Hulka M, mille predikaat on määratud, nimetatakse selle predikaadi BAASHULGAKS(domain).
milles argumendid on omavahel seotud kas ainult disjunktsiooni- või ainult konjunktsioonitehtega. Boole'i funktsiooni standardesituseks on tema normaalkuju. Loogikafunktsiooni normaalkuju koosneb elementaarkonjunktsioonidest (konjunktsioonitehte abil seotud otsestest või inverteeritud muutujatest, kus iga muutuja esineb vaid üks kord). Kui loogikafunktsioon on esitatud elementaarkonjunktsioonide disjunktsioonina, nimetatakse esitusviisi funktsiooni disjunktiivseks normaalkujuks (DNK). Vähem kasutatakse loogikafunktsiooni konjunktiivset normaalkuju (KNK), mil funktsioon esitatakse elementaardisjunktsioonide konjunktsioonina. Kui funktsiooni disjunktiivse normaalkuju iga elementaarkonjunktsioon sisaldab kõiki muutujaid, nimetatakse funktsiooni esitusviisi tema täielikuks disjunktiivseks normaalkujuks (TDNK). Täielikku disjunktiivset normaalkuju on hõlpus leida loogikafunktsiooni oleku- ehk tõeväärtustabelist. 4 Loogikaelemendid Dioodelement VÕI
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. Sama hulga puhul saame koostada ka elementaardisjunktsiooni ehk disjunkti, milles erinevad literaalid on omavahel seotud disjunktsiooni abil. Valemi F disjunktiivseks normaalkujuks nimetatakse valemiga F samaväärset valemit, mis kujutad endast erinevate lihtkonjunktsioonide disjunktsiooni. Nt A1&B1& ... A2&B2& ... Valemi F konjunktiivseks normaalkujuks nimetatakse valemiga F samaväärset valemit, mis kujutad endast erinevate disjunktide konjunktsiooni. Nt (A1 B1 ...) & (A2 B2 ...) & ... ETTEANTUD TÕEVÄÄRTUSEGA LAUSED Disjunktiivne normaalkuju võimaldab lihtsaimal viisil esitada etteantud tõeväärtus- tabeliga lause
[1] Literaal o DEF: Literaaliks nimetatakse lausemuutujat või selle eitust, literaale loetakse positiivseks või negatiivseks vastavalt selelle, kas ta on puhas lausemuutuja või koos eitusega. N: A, B, ¬C Täielik elementaalkonjuktsioon o DEF: Muutujate X1, X2…, Xn täielikuks elementaarkonjunktsiooniks nimetatakse literaalide konjunktsiooni L1&L2&,..., &Ln Täielik disjunktiivne normaalkuju o DEF: Lausearvutuse valemi F täielikuks disjunktiivseks normaalkujuks (TDNK) nimetatakse valemiga F samaväärset valemit, mis kujutab endast erinevate täielike elementaarkonjunktsioonide disjunktsiooni. Tõestuspiirkondade kirjeldused TDNK olemasolu ja ühesus Teoreem. Kui valem F ei ole samaselt väär, siis tal leidub täielikdisjunktiivne normaalkuju. Järeldus. Kui valem F ei ole samaselt tõene, siis tal leidub täielikkonjunktiivne normaalkuju. Tõestus
1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 Boole'i funktsiooni standardesituseks on tema normaalkuju. Loogikafunktsiooni normaalkuju koosneb elementaarkonjunktsioonidest (konjunktsioonitehte abil seotud otsestest või inverteeritud muutujatest, kus iga muutuja esineb vaid üks kord). Kui loogikafunktsioon on esitatud elementaarkonjunktsioonide disjunktsioonina, nimetatakse esitusviisi funktsiooni disjunktiivseks normaalkujuks (DNK). Vähem kasutatakse loogikafunktsiooni konjunktiivset normaalkuju (KNK), mil funktsioon esitatakse elementaardisjunktsioonide konjunktsioonina. Kui funktsiooni disjunktiivse normaalkuju iga elementaarkonjunktsioon sisaldab kõiki muutujaid, nimetatakse funktsiooni esitusviisi tema täielikuks disjunktiivseks normaalkujuks (TDNK). Täielikku disjunktiivset normaalkuju on hõlpus leida loogikafunktsiooni oleku- ehk tõeväärtustabelist. 1.2.3
Literaal on lausemuutuja (positiivne literaal, nt B) või lausemuutuja eitus (negatiivne literaal, nt ¬B). Mingi lausemuutujate hulga (väidetesüsteemi) puhul saame koostada elementaarkonjunktsiooni ehk konjunkti (ehk lihtkonjunktsiooni), milles erinevad literaalid on omavahel seotud konjunktsiooni abil. Sama hulga puhul saame koostada ka elementaardisjunktsiooni ehk disjunkti, milles erinevad literaalid on omavahel seotud disjunktsiooni abil. D7.10.1. Valemi F disjunktiivseks normaalkujuks nimetatakse valemiga F samaväärset valemit, mis kujutab endast erinevate lihtkonjunktsioonide disjunktsiooni. Nt A1 & B1& … & E1 ∨ A2 & B2 & … & E2 ∨ … . D7.10.2. Valemi F konjunktiivseks normaalkujuks nimetatakse valemiga F samaväärset valemit, mis kujutab endast erinevate disjunktide konjunktsiooni. Nt (A1 ∨ B1 ∨ … ∨ E1) & (A2 ∨ B2 ∨ …∨ E2) & … . Normaalkujudel on kasulikke omadusi, mis võimaldavad mitmesuguste ülesannete lahendamist
Literaal on lausemuutuja (positiivne literaal, nt B) või lausemuutuja eitus (negatiivne literaal, nt ¬B). Mingi lausemuutujate hulga (väidetesüsteemi) puhul saame koostada elementaarkonjunktsiooni ehk konjunkti (ehk lihtkonjunktsiooni), milles erinevad literaalid on omavahel seotud konjunktsiooni abil. Sama hulga puhul saame koostada ka elementaardisjunktsiooni ehk disjunkti, milles erinevad literaalid on omavahel seotud disjunktsiooni abil. D7.10.1. Valemi F disjunktiivseks normaalkujuks nimetatakse valemiga F samaväärset valemit, mis kujutab endast erinevate lihtkonjunktsioonide disjunktsiooni. Nt A1 & B1 & ... & E1 A2 & B2 & ... & E2 ... . D7.10.2. Valemi F konjunktiivseks normaalkujuks nimetatakse valemiga F samaväärset valemit, mis kujutab endast erinevate disjunktide konjunktsiooni. Nt (A1 B1 ... E1) & (A2 B2 ... E2) & ... . Normaalkujudel on kasulikke omadusi, mis võimaldavad mitmesuguste ülesannete lahendamist
annaabi.ee 
