Diskreetne matemaatika - konspekt (0)

 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 
on rakendatav üksikule lausele (1 tk – eitus). Loogiline korrutamine ehk 
konjunktsioon ehk JA-tehe. Loogiline liitmine ehk disjunktsioon ehk VÕI-
tehe. Ekvivalents on seotud implikatsiooniga ehk 𝑷↔𝑸 on nagu 𝑃→𝑄 ja 
samal ajal ka 𝑄→𝑃. Tehted inversioon, konjunktsioon ja disjunktsioon on 
elementaarsed loogikatehted – nad pole avaldatavad mingite teiste lihtsamate 
loogikatehete kaudu, kuna nad ise ongi „lihtsaimad“ tehted. Nii liht- kui ka 
liitlausete formaalseid esitusi nim lausearvutusvalemiteks -> Def – Lihtlause 
formaalne tähis (nt: A) ja üksik tõeväärtuskonstant 0 1 on valem. Kui A on valem, 
siis valemid on ka 𝐴̅ ja (A). Kui A ja B on valemid, siis on valemid ka 
𝐴∧𝐵,𝐴∨𝐵,𝐴→𝐵,𝐴↔𝐵 . Loogikatehete prioriteet: inversioon, konjunktsioon,  disjunktsioon, implikatsioon, ekvivalents. Samaselt tõene ehk tautoloogia on 
lause, mis omandab tõeväärtuse 1 koostislausete mistahes 
väärtuskombinatsiooni korral (nt: 𝐴∨𝐴̅). Samaselt väär ehk vastuolu on lause,
mis omandab tõeväärtuse 0 koostislausete mistahes väärtuskombinatsiooni 
korral (nt: 𝐴∧𝐴̅). Samaselt tõesed laused võib kõikjal asendada konstandiga 1, 
samaselt väärad konstandiga 0. Predikaat on lause (valem), mis sisaldab ühte 
või enamat muutujat. Kui predikaadi muutujad asendada mingite konkreetsete 
väärtustega lubatud väärtustehulgast, siis predikaat omandab tõeväärtuse 
(muutub lauseks). Predikaate tähistatakse suurtähtedega, predikaatmuutujaid 
väiketähtedega. Ühekohaline predikaat ehk omadus on ühe muutujaga. 
Määramispiirkond näitab, milliseid väärtusi predikaatmuutuja võib omandada. 
Predikaatlause P(x) on täidetav ehk kehtestatav, kui ta on tõene ainult osade 
muutujaväärtuste x korral (ehk tõene osas oma määramispiirkonnas) ; samaselt 
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. Hulka esitatakse tema elementide täieliku loeteluna { 𝑎 𝑏 𝑐 },  osalise loeteluna { … ,−1 ,0 ,1 ,… }, üldise avaldise kaudu { 𝑛 |(𝑛>1899)∧(𝑛<2000) }. 


Hulgad on võrdsed, kui nad koosnevad samadest elementidest { 1 3 5 }. Elemendi e  kuulumist hulka V tähistatakse 𝑒∈𝑉, mittekuulumist 𝑒∉𝑉. Hulk A on hulga B osahulk 𝐴⊂𝐵 kui  hulga A iga element on samal ajal ka hulga B elemendiks : ∀𝑥(𝑥∈𝐴→𝑥∈𝐵). Iga hulk on iseenda  osahulgaks 𝐴⊂𝐴. Kui 2 hulka on teineteise osahulkadeks, siis on nad võrdsed:  (𝐴⊂𝐵∧𝐵⊂𝐴)↔𝐴≡𝐵 . Venni diagramme kasutatakse hulkade illustratiivseks graafiliseks  esitamiseks, kus hulki esitatakse ringjoontega, mille sees võivad olla näidatud hulgaelemendid. 2  hulka – 4 pk ; 3 hulka – 8 pk ; 4 hulka – 16 pk. Universaalhulga I mood. elemendid, mis kuuluvad  vaadeldavasse hulka ja elemendid, mis ei kuulu vaadeldavasse hulka. Universaalhulk võeti kasutusele  hulka mittekuuluvate elementide esitamiseks. Hulka A mittekuuluvad elemendid mood. hulga A  täiendi 𝐴̅. Tühi hulk on elementideta hulk. Tühi hulk ∅ on iga hulga osahulgaks ∀𝐴(∅⊂𝐴). Mingi  hulga A astmehulgaks 2𝐴 ehk 𝑃(𝐴) nim selle hulga kõikide osahulkade hulka. n-elemendise hulga  astmeh-s on 2𝑛 elementi. Hulk on lõplik, kui ta sisaldab kindla arvu elemente. Lõpmatu hulk sisaldab lõpmatult palju elemente. Hulk on loenduv, kui tema elementidele saab hakata vastavaks seadma  naturaalarve { 0 1 2 3…}. Iga lõplik hulk on alati loenduv. Täisarvud Z lõpmatu/loenduv, reaalarvud  R lõpmatu/mitteloenduv. Hulgaaritmeetilised tehted: täiend – (unaarne), ühend ∪, ühisosa ∩, vahe \,  sümmeetriline vahe Δ. Kui 𝐴∩𝐵=∅, siis hulgad A ja B on mittelõikuvad. Lõpliku hulga A  võimsuseks |A| nim tema elementide arvu. Grassmanni valemid eistavad hulkade ühisosa või ühendi  elementide arvu. Duaalsetes hulgaavaldistes asenduvad ∩/∪, ∪/∩, ∅/𝐼, 𝐼/∅ nt 𝐴̅∩(𝐵∪𝐶) ja  𝐴̅∪(𝐵∩𝐶) . Hulgaavaldise Cantori normaalkuju (CNK) on ühendite ühisosa või ühisosade ühend.  Täielik Cantori normaalkuju (TCNK) on selline ühisosade ühend (ühendite ühisosa), kus igas  ühisosa(ühendi)tehtes osalevad operandidena kõik avaldises leiduvad hulgad. Kahe hulga ristkorrutis 𝐴𝑥𝐵  on järjestatud paaride <𝑎,𝑏> hulk, kus paari esimene element on esimeseks teguriks olevast  hulgast ja paari teine element on teiseks teguriks olevast hulgast : 𝐴𝑥𝐵. Hulkade otseruut on hulga otsekorrutis iseendaga 𝐴𝑥𝐴=𝐴.  Järjestatud paare, kolmikuid, nelikuid … jne nim korteežideks. ARVUSÜSTEEMID 
Kõik olulised arvusüsteemid on positsioonilised ehk arvu numbrid asuvad 
ettenähtud asukohtadel (arvujärkudes 𝑎𝑖). Tuntuim mittepositsiooniline 
arvusüsteem on rooma numbrite süsteem märkidega I V X L C D M. Igal 
positsioonilisel arvusüsteemil on täisarvuline alus p, näitab süsteemi (nt 
kümnend). Igal järgul 𝑎𝑖 on kaal 𝑝𝑖 , mille saame arvusüsteemi alust p arvujärgu
𝑎𝑖  indeksiga i astendades : 𝑝𝑖=𝑝𝑖. Koma näitab, kus lähevad täisarvulised  järgukaalud üle murdarvulisteks. Suurema kaaluga järke nim kõrgemateks 
järkudeks, väiksema kaaluga madalamateks. Täisosa madalaima järgu kaal on 
kõikides arvusüsteemides 1, kuna suvaline arv astmel 0 võrdub 1-ga. Igas järgus
𝑎𝑖  saab olla p erinevat järguväärtust. Järgu väärtus on selles arvujärgus asuva  numbri väärtus. Arv koosneb numbritest. Iga aluse p korral avaldub arvu 


väärtus 𝑵=..+𝑎1𝑝1+𝑎0𝑝0+𝑎−1𝑝−1+. . Täisosa ees ja murdosa järel asuvad 0-d ei
mõjuta arvu väärtust (000123.45000). Arvu tüvenumbrid on arvu numbrid 
alates kõrgeimast mittenullisest numbrist kuni madalaima mittenullise numbrini. 
Väärtuse leidmine ja 10ndsüsteemi teisendamine on sünonüümid. Indeks 
näitab süsteemikuuluvust. Kahendsüsteem on lihtsaim võimalik positsiooniline 
arvusüsteem. Arvusüsteemi aluse muutmisega kaasneb ka järgukaalude muutus,
mis kahendsüsteemis on arvu 10 astmete asemel arvu 2 astmed. 10-2 2-ga 
jagamine, jagamise jäägid (0 ja 1) on 2ndarvu järkude väärtusteks (nt 
3710=1001012 ).  2-8 grupeerida 3 alates madalamast ja asendada kolmik (nt 00𝟏|𝟎𝟏𝟏|𝟎𝟏𝟎|𝟏𝟎𝟎|
𝟏𝟏𝟏2=132478 )  2-16 grupeerida 4, lisa vajadusel ette 0-lle (nt 000𝟏|𝟎𝟏𝟏𝟎|𝟏𝟎𝟏𝟎|𝟎𝟏𝟏𝟏2=16𝐴716 
Kõige olulisemad on 2-, 8-, 10- ja 16- süsteemid. 16ndsüsteemis 10-A, 11-B, 12-C,
13-D, 14-E, 15-F. Arvutimälus hoitakse andmeid baitides, mis on 8-järgulised 
kahendkoodid. 16ndsüsteem võimaldab esitada baitide sisu palju kompaktsemalt
võrreldes nende „vahetu“ esitamisega kahendkujul. Kahendvektor (n-järguline) 
on kahendnumbritega 0 ja 1 esitatud loogikaväärtuste ühemõõtmeline jada 
pikkusega n. Vektori pikkus on tema 2ndjärkude arv. Lähisvektorid on võrdse 
pikkusega kahendvektorid, mis erinevad teineteisest ainult ühes kahendjärgus. 
Intervall on võrdse pikkusega kahendvektorite hulk võimsusega 2𝑛 (𝑛∈𝑁) , 
milles iga hulgaelemendi jaoks leidub samas hulgas täpselt 𝑛 lähisvektorit (nt < ). Suvaline üksik 2ndvektor { 00111 } moodustab ka intervalli, kuna hulgas on 20 elementi ja 2ndvektor omab hulgas 0 lähisvektorit. Intervalli 
olulisteks järkudeks on tema vektorite need 2ndjärgud, mille väärtus on 
kõikidel vektoritel kogu intervalli ulatuses konstantne. Intervalli kompaktseks 
esituseks sobib kasutada intervallli vektoresitust sümbolitest 0 1 - , kus 
olulised järgud on tähistatud 0 1 ja mitteolulised –. n-mõõtmeline Boole’i ruum
on kõikvõimalike n-järguliste 2ndvektorite hulk { 0,1 }𝑛 võimsusega 2𝑛 : | <𝑛=2𝑛 . Erinevate pikkustega 2ndvektorid ei saa olla võrreldavad.  LOOGIKAALGEBRA 
Loogikaalgebra on Boole’i algebra lihtsaim erijuht, kus alushulgaks on kõigest 
kaheelemendiline hulk {0 1}. Loogikaalgebra ({0 1} ; - ; ∧ ; ∨) koosneb 
loogikaväärtuste hulgast {0 1 }, millel on defineeritud 3 elementaarset 
loogikatehet: unaarne tehe inversioon ja binaarsed tehted konjunktsioon ja 
disjunktsioon. Muutuja 𝑥 või 𝑥𝑖 on loogikamuutuja kui ta saab omandada 
väärtusi ainult hulgast {0 1} 𝑥𝑖∈{𝑥1 𝑥2 ..𝑥𝑛}. Numbrimärkidega 0 ja 1 esitatud 
loogikaväärtusi nim ka „konstant 0“ ja „konstant 1“. Loogikaavaldis on 
loogikamuutujaid 𝑥𝑖, konstante 0 1 ja tehtemärke sisaldav kooslus, mis tema 
muutujate 𝑥𝑖 väärtustamisel omandab samuti loogikaväärtuse 0 või 1. 
Def: loogikamuutuja 𝑥𝑖 ja konstandid 0 1 on loogikaavaldised; kui 𝐴 on 
loogikaavaldis, siis on avaldised ka 𝐴̅ ja (𝐴); kui A ja B on loogikaavaldised, siis 
on avaldised ka 𝐴∨∧→↔⊕𝐵; tehtemärgi puudumine operandide vahel on 
samaväärne konjunktsiooniga. Kaks loogikaavaldist on loogiliselt võrdsed, kui 
nad mõlemad omandavad muutujate samade väärtuskombinatsioonide korral 
sama loogikaväärtuse 0 või 1. Duaalne kuju saadakse, kui asendada ∧/∨ ja 1/0.
Hulgaalgebra ja loogikaalgebra seos: ∩/∧ , ∪/∨ , ∅/0 , 𝐼/1. Asendusseosed 
asendavad mitteelementaarseid loogikatehteid (impl, ekviv, summa mod 2) 
elementaarsete loogikatehete (inv, dis, konj) kaudu. 
n-muutuja loogikafunktsioon 𝑓(𝑥1𝑥2..𝑥𝑛) on vastavus n-muutuja Boole’i ruumist {0,1}𝑛  loogikaväärtuste hulka { 0,1 }: 𝑓(𝑥1𝑥2..𝑥𝑛)𝑛→{0,1}. Argumentvektor on n-järguline 


kahendvektor 𝑥1𝑥2..𝑥𝑛∈{0,1}. Tõeväärtustabel näitab funktsiooni ühest vastavust lähtehulgast  sihthulka. Funktsiooni 1-de piirkonna 𝑉1⊂{0 1}𝑛 mood. need argumentvektorid 𝑥1𝑥2..𝑥𝑛∈𝑉1  mille korral 𝑓(𝑥1𝑥2..𝑥𝑛)=1. Funktsiooni 0-de piirkonna 𝑉0⊂{0 1}𝑛 −..−. n-muutuja loogikaFni  mingi muutuja 𝑥𝑖 on mitteoluline muutuja, kui talle omistatav loogikaväärtus ei mõjuta kuidagi F-ni  väärtust. Mitteoluliste muutujatega F-n on alati teisendatav kujule, kus mitteolulised muutujad  puuduvad. LoogikaF on osaliselt määratud, kui tema lähtehulgaks olevas Boole’i ruumis leidub  selliseid argumentvektoreid 𝑥1𝑥2..𝑥𝑛∈{0,1}𝑛 mille jaoks pole rangelt määratud, kumba  loogikaväärtuse 0 või 1 funktsioon nende korral omandama peab. Sellised argumentvektorid  moodustavad F-ni määramatuspiirkonna 𝑉−⊂{0 1}𝑛. Piirkondade ühend 𝑉0∪𝑉1∪𝑉−𝑛  Funktsioon on täielikult määratud, kui ta määramatuspiirkond on jaotatud 1-de ja 0-de pk vahel. Kui  määramatuspiirkonnas on n kahendvektorit, saab sellest 2𝑛 täielikult määratud funktsiooni. Algterm  on avaldise koosseisu kuuluva loogikamuutuja 𝑥𝑖 või selle inversioon 𝑥𝑖̅ või konstant 0 1.  Elementaarkonjunktsioon on üksik algterm või algtermide konjunktsioon.  Elementaardisjunktsioon on üksik algterm või algtermide disjunktsioon. DNK (1-de pk) on üksik  elementaarkonj. või elementaarkonj-de disjunktsioon. KNK (0-de pk) on ükskik elementaardisj. või  elementaardisj-de konjunktsioon. Samaaegselt DNK ja KNK 𝑥1∨𝑥2∨𝑥3 𝑥1̅̅̅𝑥2𝑥3̅̅̅ 𝑥2̅̅̅ TDNK on  DNK, kus iga elementaarkonj. sisaldab F-ni kõiki muutujaid 𝑥𝑖. TKNK on KNK, kus iga  elementaardisj. sisaldab F-ni kõiki muutujaid 𝑥𝑖. MDNK/MKNK on konkreetse F-ni väikseima  keerukusega DNK/KNK. Keerukus 𝑳(𝒇) on tema koosseisus olevate algtermide arv. Loogikaalgebra põhiseosed 
Seosed konstantidega 0̅=1 1̅=0 0∗1=0 0∨1=1 𝑥∗0=0 𝑥∗1=𝑥 𝑥∗𝑥̅=0 
𝑥∨0=𝑥 𝑥∨1=1 𝑥∨𝑥̅=1 
Idempotentsus 𝑥∗𝑥=𝑥 𝑥∨𝑥=𝑥 
DeMorgani seadused 𝑥∨𝑦̅̅̅̅̅̅̅=𝑥̅∧𝑦̅ 𝑥𝑦̅̅̅=𝑥̅∨𝑦̅ 
Neeldumine 𝑥∨𝑥𝑦=𝑥 𝑥∨𝑥̅𝑦=𝑥∨𝑦 
Distributiivsus 𝑥(𝑦∨𝑧)=𝑥𝑦∨𝑥𝑧 𝑥∨(𝑦𝑧)=(𝑥∨𝑦)(𝑥∨𝑧) 
Kleepimine 𝑥=𝑥𝑦∨𝑥𝑦̅ 𝑥=(𝑥∨𝑦)(𝑥∨𝑦̅) 
Asendusseosed 𝑥→𝑦=𝑥̅∨𝑦 𝑥↔𝑦=(𝑥→𝑦)(𝑦→𝑥)=𝑥̅𝑦̅∨𝑥𝑦 𝑥⊕𝑦=𝑥̅𝑦∨𝑥𝑦̅ 
0↔0=1 1↔1=1 0↔1=0 𝑥⊕𝑥=0 𝑥⊕1=𝑥̅ 𝑥⊕0=𝑥 𝑥⊕𝑥̅=1 0⊕1=1 1⊕1=0 1⊕1⊕1=1  0⊕0=0 1→0=0 1→1=1 0→1=1 0→0=1 LOOGIKAFUNKTSIOONID 
1-muutuja loogikafunktsioone on 4. Ainus oluline 1-muutuja funktsioon on 
inversioon 𝑓(𝑥)=𝑥̅. 0-muutuja loogikafunktsioon ei sõltu funktsiooni muutujast x. 
2-muutuja loogikafunktsioone on 16. 2-muutuja loogikafunktsioonid sõltuvad kõik
oma mõlemast muutujast va. esimene ja teine. Disjunktsiooni inversiooni 
esitatakse märgiga ↓ (Pierce’i nool) 𝑥1∨𝑥2̅̅̅̅̅̅̅̅̅=𝑥1↓𝑥2 . Konjunktsiooni inversiooni 
esitatakse märgiga | (Shefferi kriips) 𝑥1𝑥2̅̅̅̅̅̅=𝑥1|𝑥2 . 3-muutuja loogikafunktsioone 
on 256. ⊕ nimetus „summa mooduliga 2“ tuleneb sellest, et F-ni väärtus osutub 


muutujaväärtuste kõigi nelja kombinatsiooni korral võrdseks muutujate 
aritmeetilise summaga, millele on rakendatud moodulit 2: 
(0+0)𝑚𝑜𝑑2)=0𝑚𝑜𝑑2=0 ;(0+1)𝑚𝑜𝑑2=1𝑚𝑜𝑑2=1 ;(1+0)𝑚𝑜𝑑2=1𝑚𝑜𝑑2=1 ;
(1+1)𝑚𝑜𝑑2=2𝑚𝑜𝑑2=0  . Summa mooduliga 2 on ekvivalentsi inversioon.  Omadused 𝑥⊕𝑥=0 𝑥⊕1=𝑥̅ 𝑥⊕0=𝑥 𝑥⊕𝑥̅=1 0⊕1=1 1⊕1=0 1⊕1⊕1=1 
DNK/KNK saab TDNK/TKNK kleepimisseadusega nt 𝑥1=𝑥1𝑥2∨𝑥1𝑥2̅̅̅ nt 𝑥1=(𝑥1∨𝑥2̅̅̅)
(𝑥1∨𝑥2) 
DNK saab KNK-ks sulgude lahtikorrutamise/lahtiliitmise abil. 
𝑓0(𝑥1𝑥2)=0 𝑘𝑜𝑛𝑠𝑡𝑎𝑛𝑡 0 
𝑓1(𝑥1𝑥2)=𝑥1𝑥2 𝑘𝑜𝑛𝑗𝑢𝑛𝑘𝑡𝑠𝑖𝑜𝑜𝑛 
𝑓2(𝑥1𝑥2)=𝑥1→𝑥2̅̅̅̅̅̅̅̅̅̅ 𝑖𝑚𝑝𝑙𝑖𝑘𝑎𝑡𝑠𝑖𝑜𝑜𝑛𝑖 𝑖𝑛𝑣𝑒𝑟𝑠𝑖𝑜𝑜𝑛 
𝑓3(𝑥1𝑥2)=𝑥1 𝑒𝑠𝑖𝑚𝑒𝑛𝑒 𝑚𝑢𝑢𝑡𝑢𝑗𝑎 
𝑓4(𝑥1𝑥2)=𝑥2→𝑥1̅̅̅̅̅̅̅̅̅̅ 𝑝öö𝑟𝑑𝑖𝑚𝑝𝑙𝑖𝑘𝑎𝑡𝑠𝑖𝑜𝑜𝑛𝑖 𝑖𝑛𝑣𝑒𝑟𝑠𝑖𝑜𝑜𝑛 
𝑓5(𝑥1𝑥2)=𝑥2 𝑡𝑒𝑖𝑛𝑒 𝑚𝑢𝑢𝑡𝑢𝑗𝑎 
𝑓6(𝑥1𝑥2)=𝑥1↔𝑥2̅̅̅̅̅̅̅̅̅̅ 𝑒𝑘𝑣𝑖𝑣𝑎𝑙𝑒𝑛𝑡𝑠𝑖 𝑖𝑛𝑣𝑒𝑟𝑠𝑖𝑜𝑜𝑛 
𝑓6(𝑥1𝑥2)=𝑥1⊕𝑥2 "𝑠𝑢𝑚𝑚𝑎 𝑚𝑜𝑜𝑑𝑢𝑙𝑖𝑔𝑎 2" "𝑣ä𝑙𝑖𝑠𝑡𝑎𝑣 𝑉Õ𝐼" 
𝑓7(𝑥1𝑥2)=𝑥1∨𝑥2 𝑑𝑖𝑠𝑗𝑢𝑛𝑘𝑡𝑠𝑖𝑜𝑜𝑛 
𝑓8(𝑥1𝑥2)=𝑥1∨𝑥2̅̅̅̅̅̅̅̅̅ 𝑑𝑖𝑠𝑗𝑢𝑛𝑘𝑡𝑠𝑖𝑜𝑜𝑛𝑖 𝑖𝑛𝑣𝑒𝑟𝑠𝑖𝑜𝑜𝑛 
𝑓9(𝑥1𝑥2)=𝑥1↔𝑥2 𝑒𝑘𝑣𝑖𝑣𝑎𝑙𝑒𝑛𝑡𝑠 
𝑓10(𝑥1𝑥2)=𝑥2̅̅̅ 𝑡𝑒𝑖𝑠𝑒 𝑚𝑢𝑢𝑡𝑗𝑎 𝑖𝑛𝑣𝑒𝑟𝑠𝑖𝑜𝑜𝑛 
𝑓11(𝑥1𝑥2)=𝑥2→𝑥1 𝑝öö𝑟𝑑𝑖𝑚𝑝𝑙𝑖𝑘𝑎𝑡𝑠𝑖𝑜𝑜𝑛 
𝑓12(𝑥1𝑥2)=𝑥1̅̅̅ 𝑒𝑠𝑖𝑚𝑒𝑠𝑒 𝑚𝑢𝑢𝑡𝑢𝑗𝑎 𝑖𝑚𝑝𝑙𝑖𝑘𝑎𝑡𝑠𝑖𝑜𝑜𝑛 
𝑓13(𝑥1𝑥2)=𝑥1→𝑥2 𝑖𝑚𝑝𝑙𝑖𝑘𝑎𝑡𝑠𝑖𝑜𝑜𝑛 
𝑓14(𝑥1𝑥2)=𝑥1𝑥2̅̅̅̅̅̅ 𝑘𝑜𝑛𝑗𝑢𝑛𝑘𝑡𝑠𝑖𝑜𝑜𝑛𝑖 𝑖𝑛𝑣𝑒𝑟𝑠𝑖𝑜𝑜𝑛 
𝑓15(𝑥1𝑥2)=1 𝑘𝑜𝑛𝑠𝑡𝑎𝑛𝑡 1 KARNAUGH’ KAART 
Karnaugh’ kaart on F-ni tõeväärtustabeli sihipärane topoloogiline 
ümberpaigutus tasandil või ruumis. Põhiomadused: kaardi iga ruudu 
naaberruutude arv võrdub kaardi muutujate arvuga ; suvalise kahe naaberruudu 
argumentvekt. on teineteise lähiskoodid. 6-muutuja kaart on suurim Karnaugh’ 
kaart. 2-, 3- ja 4-muutuja kaardid on tasandilised, 5- ja 6-muutuja kaardid 
ruumilised. Karnaugh’ kaardil valitakse välja kindlate mõõtmetega ruutude 
gruppe, mida nim kontuurideks, iga kontuur vastab 2ndvektorite mingile 
intervallile. 
Võimalikud suurused : 1x1, 1x2, 1x4, 2x2, 2x4, 4x4 1x1x1, 1x1x2, 1x1x4, 1x2x1, 
1x2x2 … 4x4x4 
n-muutuja kaardil on 2n omavahel kattuvat piirkonda. Karnaugh’ kaarti 
kasutatakse kõige enam loogikaF-de minimeerimiseks. LoogikaF-ni 
minimeerimine on tema esitamine minimaalse keerukusega normaalkujul – 
MDNK/MKNK. 
Minimeerimine Karnaugh’ kaardiga: tõeväärtustabel kaardile ; katta 1-d/0-d 
väikse arvu/suurte kontuuridega ; leida iga kontuuri jaoks const muutujad ; 
kirjuta elementaarkonj./elementaardisj. 
Nõrgalt määratud F on suure määramatuspiirkonnaga osaliselt määratud F. 
Intervallid on ortogonaalsed, kui nad ei oma ühisosa (mittelõikuvad 
2ndvektorite hulgad). Implikant on loogika-ni 1-de piirkonna intervall. 
Lihtimplikant on maksimaalne implikant, mis ei sisaldu tervikuna üheksi teises 
selle F-ni implikandis. Taandatud DNK on F-ni kõigi lihtimplikantide 
disjunktsioon. Igal F-nil on vaid 1 TaDNK. MDNK koosneb alati osadest/kõikidest 
TaDNK elementaarkonjunktsioonidest. 


MCCLUSKEY’ MEETOD 
McCluskey’ meetod on rakendatav suvalise loogikamuutujate arvu korral. Sellel 
on 2 põhietappi: loogikafunktsiooni kõigi lihtimplikantide leidmine ; minimaalse 
katte leidmine (lihtimplikantide hulga minimeerimine). McCluskey’ meetodis on 
arvu indeks 1-de arv selle arvu kahendkujus. 
2 modifikatsiooni: intervallmeetod ja numbriline meetod 
McCluskey ja Karnaugh sarnasused: 1) Lähiskoodid sattuvad indeksite järgi 
grupeerides naabersektsioonidesse, seega McCluskey meetod kleebib kokku 
samu koode, mis Karnaugh kontuurid 2) intervallide kasvatamine kleepides on 
samaväärne kontuuride suurendamisega Karnaugh kaardil. 
McCluske
y 
meetod 
lisab 
KOGU 
määram
atuspiirk
onna 1-
dele 
(MDNK) 
või 0-
dele 
(MKNK) 
𝑓(𝑥1𝑥2𝑥
3)  𝐼𝑛𝑑𝑒𝑘𝑠  0000 0  0000 0011 1  0011 0102  0102  0113  1004  1004 2  0113 1015  1015  1106  1106  1117 3  1117 SHANNONI ARENDUSED 
Kui asendada n-muutuja F-ni avaldises osad tema muutujad konstantidega 0 või 
1, siis selliselt saadavat lihtsamat loogikaF-ni nim n-muutuja F-ni 
jääkfunktsiooniks. n-muutuja F-ni tuletis on (n-1)-muutuja F-n, kus puudub see
muutuja 𝑥𝑖, mille järgi tuletis võeti. On olemas disj/konj arendus ja need on 
osalised/täielikud. Täieliku arenduse puhul väärtustuvad jääkF-nid 
konstantideks 0/1. 2-muutuja F-n on lineaarne, kui 𝑓(00)⊕𝑓(01)⊕𝑓(10)=𝑓(11) LOOGIKAFUNKTSIOONIDE KLASSID
0-lli säilitav –kui ta kõikide muutujate väärtustamisel 0-ks väärtustub F-n ise ka 
0-ks 𝐾⊂𝐾0
1-te säilitav – kui ta kõikide muutujate väärtustamisel 1-ks väärtustub F-n ise ka 
1-ks 𝐾⊂𝐾1
Pööratav – kui ta oma kõikide muutujate väärtuste inverteerimisel iverteerub ka 
ise 𝐾𝑝⊂𝐾𝑝 𝑓(𝑥1…𝑥4) 𝐼𝑛𝑑𝑒𝑘𝑠  00000 0  00000 00011 1  00011 00102  00102  00113  01004  01004  10008  01015 2  00113 01106  01015  01117  01106  10008  10019  10019  101010  101010  110012  10111
1  3  01117 110012  101111  110113  110113  111014  111014  11111
5  4  11111
5 


Monotoonne – kui argumentvektori suurenemisel F-ni väärtus ei vähene 
𝐾𝑚 <⊂𝐾𝑚
Lineaarne – kui ta on esitatav kujul 𝑐0⊕𝑐1𝑥1⊕𝑐2𝑥2⊕…⊕𝑐𝑛𝑥𝑛, kus iga const 
𝑐𝑖∈{0 1} 𝐾𝑙 𝑐0,𝑐1…𝑐𝑛∈{0 
1}⊂𝐾𝑙 SÜSTEEMID 
Süsteemi täielikkuse kriteerium on täidetud, kui süsteem sisaldab 
1) Vähemalt ühte 0-lli mittesäilitavat funktsiooni 
2) vähemalt ühte 1-te mittesäilitavat funktsiooni 
3) vähemalt ühte mittepööratavat funktsiooni 
4) vähemalt ühte mittemonotoonset funktsiooni 
5) vähemalt ühte mittelineaarset funktsiooni 
Baas on minimaalne täielik loogikafunktsioonide süsteem. <  VÕI-EI baas (Pierce’i baas)   JA-EI baas (Shefferi baas)  <  implikatiivne baas  < < <  implikatiivne baas   Boole’i konjunktiivne baas   Boole’i disjunktiivne baas  < < < < < <  Žegalkini e. Reed-Mulleri baas  Loogikafunktsioonide süsteem on nõrgalt täielik, kui ta sisaldab ühte 
mittemonotoonset ja ühte mittelineaarset F-ni ja konstantfunktsiooni 𝑓0 või 𝑓15 
lisamisel osutub täielikuks (nt süsteem {& ⊕} on nõrgalt täielik, sest & on 
mittelineaarne ja ⊕ on mittemonotoonne, 𝑓0-ga lisandub mittepööratav) 
Reed-Mulleri baas on loogikatehete süsteem, kuhu kuuluvad tehted {&⊕1} ja ta
on täielik. Baas on ta, kuna suvalise tema liikme väljajätmisel süsteemiks kaoks 
selle täielikkus. 𝑥̅=𝑥⊕1 𝑥1∨𝑥2=𝑥1̅̅̅ 𝑥2̅̅̅̅̅̅̅̅̅̅=(𝑥1⊕1)(𝑥2⊕1)⊕1????=𝑥1𝑥2⊕𝑥1⊕𝑥2 
Reed-Mulleri polünoom Karnaugh’ kaardil 1-de piirkonnas võtta mittelõikuvad 
kontuurid 
JA-EI topeltinversioon DNK-le ja DeMorgan alumisele inversioonijoonele 
VÕI-EI topeltinversioon KNK-le ja DeMorgan alumisele inversioonijoonele <: 𝑥̅=𝑥→0 𝑥1∨𝑥2=𝑥1̅̅̅→𝑥2=(𝑥1→0)→𝑥2 𝑥1𝑥2=(𝑥1→(𝑥2→0))→0 < 𝑥1∨𝑥2=𝑥1̅̅̅→𝑥2 𝑥1𝑥2=𝑥1→𝑥2̅̅̅̅̅̅̅̅̅̅̅̅̅ < 𝑥̅=𝑥→(𝑥⊕𝑥) 𝑥1∨𝑥2=𝑥1→(𝑥1⊕𝑥1)→𝑥2 
𝑥1𝑥2=(𝑥1→(𝑥2→(𝑥1⊕𝑥1)))→(𝑥1⊕𝑥1)


DNK – suvalised elementaarkonjunktsioonide disjunktsioonid 
Saadakse funktsiooni 1-de piirkonnast. 
KNK – suvalised elementaardisjunktsioonide konjunktsioonid 
Saadakse funktsiooni 0-de piirkonnast 
TDNK – kõik elementaarkonjunktsioonid sisaldavad kõiki muutujaid 
Kõik 1-de piirkonda kuuluvad argumentvektorid (tõeväärtustabelis) 
TKNK – kõik elementaardisjunktsioonid sisaldavad kõiki muutujaid 
Kõik 0-de piirkonda kuuluvad argumentvektorid (tõeväärtustabelis) 
Muutujaväärtused inverteeritud (0 annab x, 1 annab x inversiooni) 
MDNK – väikseima keerukusega DNK 
Karnaugh’ kaardil võimalikult suured kontuurid ümber 1-de (1, 2, 4, 8) 
Osaliselt määratud funktsioonis võtta kaasa võimalikult palju kriipse 
MKNK – väikseima keerukusega KNK 
Karnaugh’ kaardil võimalikult suured kontuurid ümber 0-de (1, 2, 4, 8) 
Kõik muutujaväärtused on inverteeritud (0 annab x, 1 annab x inversiooni) 
Osaliselt määratud funktsioonis võtta kaasa võimalikult palju kriipse 
TaDNK – kõigi lihtimplikantide disjunktsioon 
Karnaugh’ kaardil MDNK kontuuride ühendamine kontuuridega, mis EI OLE 
TÄIESTI teiste sees 
TaKNK – kõigi lihtimplikantide disjunktsioon 
Karnaugh’ kaardil MKNK kontuuride ühendamine kontuuridega, mis EI OLE 
TÄIESTI teiste sees 
Reed-Mulleri polünoom - Karnaugh’ kaardil 1-de piirkonnas võtta 
mittelõikuvad kontuurid (paaritult) 
Shannoni disj arendus – nt 𝑥(𝑥 1 𝑥) 𝑉 𝑥̅(𝑥 0 𝑥) 
Shannoni konj arendus – nt [𝑥 𝑉 (𝑥 0 𝑥)]∗[𝑥̅ 𝑉 ( 𝑥 1 𝑥)]

Document Outline

• Hulk on koosvaadeldavate hulgaelementide kogum. Hulk koosneb hulgaelementidest. Hulka tähistatakse suurtähtedega A B C D. Hulka esitatakse tema elementide tä, ü. Hulgad on võ. Elemendi e kuulumist hulka V tähistatakse 𝑒∈𝑉, mittekuulumist 𝑒∉𝑉. Hulk A on hulga B osahulk 𝐴⊂𝐵 kui hulga A iga element on samal ajal ka hulga B elemendiks : ∀𝑥(𝑥∈𝐴→𝑥∈𝐵). Iga hulk on iseenda osahulgaks 𝐴⊂𝐴. Kui 2 hulka on teineteise osahulkadeks, siis on nad võrdsed: (𝐴⊂𝐵∧𝐵⊂𝐴)↔𝐴≡𝐵. Venni diagramme kasutatakse hulkade illustratiivseks graafiliseks esitamiseks, kus hulki esitatakse ringjoontega, mille sees võivad olla näidatud hulgaelemendid. 2 hulka – 4 pk ; 3 hulka – 8 pk ; 4 hulka – 16 pk. Universaalhulga I mood. elemendid, mis kuuluvad vaadeldavasse hulka ja elemendid, mis ei kuulu vaadeldavasse hulka. Universaalhulk võeti kasutusele hulka mittekuuluvate elementide esitamiseks. Hulka A mittekuuluvad elemendid mood. hulga A täiendi 𝐴̅. Tühi hulk on elementideta hulk. Tühi hulk ∅ on iga hulga osahulgaks ∀𝐴(∅⊂𝐴). Mingi hulga A astmehulgaks 2𝐴 ehk 𝑃(𝐴) nim selle hulga kõikide osahulkade hulka. n-elemendise hulga astmeh-s on 2𝑛 elementi. Hulk on lõplik, kui ta sisaldab kindla arvu elemente. Lõpmatu hulk sisaldab lõ. Iga lõplik hulk on alati loenduv. Täisarvud Z lõpmatu/loenduv, reaalarvud R lõpmatu/mitteloenduv. Hulgaaritmeetilised tehted: täiend – (unaarne), ühend ∪, ühisosa ∩, vahe , sümmeetriline vahe Δ. Kui 𝐴∩𝐵=∅, siis hulgad A ja B on mittelõikuvad. Lõpliku hulga A võimsuseks |A| nim tema elementide arvu. Grassmanni valemid eistavad hulkade ühisosa või ühendi elementide arvu. Duaalsetes hulgaavaldistes asenduvad ∩/∪, ∪/∩, ∅/𝐼, 𝐼/∅ nt 𝐴̅∩(𝐵∪𝐶) ja 𝐴̅∪(𝐵∩𝐶). Hulgaavaldise Cantori normaalkuju (CNK) on ühendite ühisosa või ühisosade ühend. Täielik Cantori normaalkuju (TCNK) on selline ühisosade ühend (ühendite ühisosa), kus igas ühisosa(ühendi)tehtes osalevad operandidena kõik avaldises leiduvad hulgad. Kahe hulga ristkorrutis 𝐴𝑥𝐵 on järjestatud paaride <𝑎,𝑏> hulk, kus paari esimene element on esimeseks teguriks olevast hulgast ja paari teine element on teiseks teguriks olevast hulgast : 𝐴𝑥𝐵. Hulkade otseruut on hulga otsekorrutis iseendaga 𝐴𝑥𝐴=𝐴. Järjestatud paare, kolmikuid, nelikuid … jne nim korteežideks.
• n-muutuja loogikafunktsioon 𝑓(𝑥1𝑥2..𝑥𝑛) on vastavus n-muutuja Boole’𝑛 loogikavää: 𝑓(𝑥1𝑥2..𝑥𝑛)𝑛→{0,1}. Argumentvektor on n-järguline kahendvektor 𝑥1𝑥2..𝑥𝑛∈{0,1}. Tõeväärtustabel näitab funktsiooni ühest vastavust lähtehulgast sihthulka. Funktsiooni 1-de piirkonna 𝑉1⊂{0 1}𝑛 mood. need argumentvektorid 𝑥1𝑥2..𝑥𝑛∈𝑉1 mille korral 𝑓(𝑥1𝑥2..𝑥𝑛)=1. Funktsiooni 0-de piirkonna 𝑉0⊂{0 1}𝑛 −..−. n-muutuja loogikaFni mingi muutuja 𝑥𝑖 on mitteoluline muutuja, kui talle omistatav loogikaväärtus ei mõjuta kuidagi F-ni väärtust. Mitteoluliste muutujatega F-n on alati teisendatav kujule, kus mitteolulised muutujad puuduvad. LoogikaF on osaliselt määratud, kui tema lähtehulgaks olevas Boole’i ruumis leidub selliseid argumentvektoreid 𝑥1𝑥2..𝑥𝑛∈{0,1}𝑛 mille jaoks pole rangelt määratud, kumba loogikaväärtuse 0 või 1 funktsioon nende korral omandama peab. Sellised argumentvektorid moodustavad F-ni määramatuspiirkonna 𝑉−⊂{0 1}𝑛. Piirkondade ühend 𝑉0∪𝑉1∪𝑉−𝑛 Funktsioon on täielikult määratud, kui ta määramatuspiirkond on jaotatud 1-de ja 0-de pk vahel. Kui määramatuspiirkonnas on n kahendvektorit, saab sellest 2𝑛 täielikult määratud funktsiooni. Algterm on avaldise koosseisu kuuluva loogikamuutuja 𝑥𝑖 või selle inversioon 𝑥𝑖̅ või konstant 0 1. Elementaarkonjunktsioon on üksik algterm või algtermide konjunktsioon. Elementaardisjunktsioon on üksik algterm või algtermide disjunktsioon. DNK (1-de pk) on üksik elementaarkonj. või elementaarkonj-de disjunktsioon. KNK (0-de pk) on ükskik elementaardisj. või elementaardisj-de konjunktsioon. Samaaegselt DNK ja KNK 𝑥1∨𝑥2∨𝑥3 𝑥1̅̅̅𝑥2𝑥3̅̅̅ 𝑥2̅̅̅ TDNK on DNK, kus iga elementaarkonj. sisaldab F-ni kõiki muutujaid 𝑥𝑖. TKNK on KNK, kus iga elementaardisj. sisaldab F-ni kõiki muutujaid 𝑥𝑖. MDNK/MKNK on konkreetse F-ni väikseima keerukusega DNK/KNK. Keerukus 𝑳(𝒇) on tema koosseisus olevate algtermide arv.
• 0↔0=1 1↔1=1 0↔1=0 𝑥⊕𝑥=0 𝑥⊕1=𝑥̅ 𝑥⊕0=𝑥 𝑥⊕𝑥̅=1 0⊕1=1 1⊕1=0 1⊕1⊕1=1 0⊕0=0 1→0=0 1→1=1 0→1=1 0→0=1
• 𝑓15(𝑥1𝑥2)=1 𝑘𝑜𝑛𝑠𝑡𝑎𝑛𝑡 1