X1' X3' X4 (X2' v X2) v X1 X2 X3' (X4' v X4) = X1' X2' X4' v X1' X3' X4 v X1 X2 X3' Lihtsustamisel saadud DNK on: f = X1' X2' X4' v X1' X3' X4 v X1 X2 X3' Kui võrrelda saadud DNK- d punktis 3 saadud MDNK- ga, siis nad pole võrdsed. Punktis 3 saadud MDNK on väiksema keerukusega, kuna seal on MDNK leidmisel kaasa haaratud määramatuspiirkond. 6. Leida ja näidata, milleks (0 või 1) väärtustuvad (punktis 3) leitud MDNK ja MKNK määramatuspiirkonna kõikide argumentvektorite korral. Otsustada, kas leitud MDNK ja MKNK on teineteisega võrdsed või mitte. Tõeväärtustabelis leian MDNK ja MKNK väärtused ainult määramatuspiirkonna kõikide argumentvektorite alusel. Tabeli all on näidatud arvutused. X1 X2 X3 X4 Y MDNK MKNK 0 0 0 0 1 0 0 0 1 1 0 0 1 0 1
Loogikavalemi keerukus: loogikavalemi koosseisus olevate algtermide arv Loogikavalemi sügavus: kõige pikem tehete ahel, mis tuleb läbida, et saada loogikafunktsiooni väärtus, pmst aeg, mis funktsiooni lahendmiseks kulub Mitteoluline muutuja: muutuja, millele omistatud loogikaväärtus ei muuda kuidagi funktsiooni väärtust Tõeväärtustabel: loogikafunktsiooni esitusviis, mis loetleb esitatava funktsiooni väärtused tabelisse korrastatuna kõikide argumentvektorite puhul Funktsiooni normaalkujude minimeerimine Disjunktiivne normaalkuju (DNK): elementaarkonjunktsioonide disjunktsioon Konjunktiivne normaalkuju (KNK): elementaardisjunktsioonide konjunktsioon Täielik DNK: DNK, kus iga elementaarkonjunktsioon sisaldab funktsiooni kõiki argumente Täielik KNK: KNK, kus iga elementaardisjunktsioon sisaldab funktsiooni kõiki argumente Loogikafunktsioonide erikujulised avaldised Boole'i ruum: kõikvõimalike kahendvektorite hulk
..................................................................... 11 5.1.1 — kas nad on võrdsed?.........................................................................11 5.1.2 — kui nad pole võrdsed, siis kumb nendest on väiksema keerukusega (ehk lihtsam) avaldis ja miks?........................................................................11 6. Leida ja näidata, milleks (0 või 1) väärtustuvad (punktis 3) leitud MDNK ja MKNK määramatuspiirkonna kõikide argumentvektorite korral............................11 6.1 Otsustada (hinnata), kas leitud MDNK ja MKNK on teineteisega võrdsed või mitte.................................................................................................................. 12 2 7. Realiseerida (punktis 3) MDNK-na saadud loogikafunktsioon minimaalseima
Vastavuse Diagramm 4-muutuja loogikafunktsiooni tõeväärtustabel on seega 16-realine. tõeväärtustabel , mis on vastavusdiagrammi 2-muutuja funktsioonile reorganiseeritud erikuju ja sisaldab seega Funktsiooni muutujate (ehk argumentide) arvu suurenemisel ühevõrra funktsiooni argumentvektorite arv kahekordistub. Argumentvektor x1 x2 . . . xn ∈ { 0, 1 } on loogikamuutujate n Funktsioon võib omandada määramatuspiirkonda kuuluvate "väärtustekomplekt", mis esitab funktsiooni igale üksikule muutujale x1 , argumentvektorite x1 x2 . . . xn ∈ V — korral ükskõik kumba x2 , . . . xn omistatavat väärtust 0 või 1
x3x4 V xx1 x2 xx3 x4 Taandatud DNK leidmine: Selle leidmiseks koostan MDNK Karnaugh’ kaardi, millel märgin ära kõik lihtimplikandid, mis tervikuna ei sisaldu üheski teises (mustaga märgitud MDNK lihtimplikandid ja punasega lisaks TaDNK jaoks vajalikud lihtimplikandid) TaDNK: f(x1x2 x3x4) = xx1 xx2 x3 V x1xx2 xx3 V x2x4 V xx1 x3x4 V x1xx3 x4 6. Leida vabalt valitud viisil MKNK-ga võrdne Täielik KNK. Selleks vaatan MKNK Karnaugh’kaarti ja kirjutan 0-de piiskonna argumentvektorite järgi välja nende elementaardisjunktsioonid ja korrutan need JA-tehtega kokku KNK-ks: TKNK: f(x1x2 x3x4) = (x1 V x2 V x3 V x4)(x1 V x2 V x3 V xx4)(x1 V xx2 V x3 V x4) (x1 V xx2 V x3 V xx4)(x1 V V xx2 V xx3 V x4)(xx1 V xx2 V x3 V x4)(xx1 V xx2 V xx3 V x4)(xx1 V x2 V xx3 V xx4)(xx1 V x2 V xx3 V x4) 7. Teha MDNK-le Shannoni disjunktiivne arendus selle muutuja(te) järgi, mis esineb MDNK-s kõige rohkem => x2 järgi. MDNK: f(x1x2 x3x4) = xx1 xx2 x3 V x1 xx2 xx3 V x2 x4
01 1 - 0 - 11 - 0 - - 10 0 - 0 1 Tulemus tuleb sama: fTDNK = ( 1 2x3) v ( 1x2 3 4) v (x1 2x3 4) MDNK ja DNK ei ole võrdsed. MDNK on lihtsam, kuna DNK leidmisel ei arvestatud määramatuspiirkonnaga. 6. Leida ja näidata, milleks (0 või 1) väärtustuvad (punktis 3) leitud MDNK ja MKNK määramatuspiirkonna kõikide argumentvektorite korral. Otsustada (hinnata), kas leitud MDNK ja MKNK on teineteisega võrdsed või mitte. X1 X2 X3 X4 fD fK 1 0001 0 0 5 0101 0 1 6 0110 1 0 9 1001 0 0 12 1100 1 1 14 1110 1 0 15 1111 0 0 Antud tabelist selgub, et leitud MDNK ja MKNK ei ole teineteisega võrdsed. 7. Realiseerida (punktis 3) MDNK-na saadud loogikafunktsioon
12. Mis on n-muutuja loogikafunktsioon? N-muutuja loogikafunktsioon on vastavus n- muutuja Boole’i ruumist loogikaväärtuste hulka {0, 1}. 13. Mis on argumentvektor ja mida ta esitab? Argumentvektor ehk kahendvektor esitab funktsiooni igale üksikule muutujale omistatavat väärtust 0 või 1. 14. Mida näitab loogikafunktsiooni tõeväärtustabel? Tõeväärtustabel esitab funktsiooni väärtused tabelisse korrastatuna kõikide argumentvektorite korral. Tõeväärtustabel on loogikafunktsiooni vahetuim esitus. 15. Mis on funktsiooni 1-de piirkond? Mis on 0-de piirkond? Kuidas neid tähistatakse? 1-de piirkond näitab, milliste argumentvektorite korral omandab loogikafunktsioon väärtuse 1 ning 0-de piirkond näitab, milliste argumentvektorite korral omandab loogikafunktsioon väärtuse 0. 1-de piirkonda tähistatakse suure kreeka tähe „sigma“-ga ( ) ning 0-de piirkonda tähistatakse
0 0 1 - 0 - 1 11 1 - 0 - 1 1 0 0 0 0 5 TaDNK = f(x1 x2 x3 x4) = x2 x3 v x2 x4 v x1 x3 x4 v x1 x3 x4 v x1 x2 x4 v x1 x2 x3 v x1 x3 x4 Täielik DNK leiame funktsiooni ühtede piirkonna argumentvektorite vastavate konstituentide kokku liitmise teel VÕI-tehtega: 6 ARGUMENTVEKTOR KONSTITUENT 0001 x1 x2 x3 x4 0011 x1 x2 x3 x4 0010 x1 x2 x3 x4 0100 x1 x2 x3 x4
5 - muutuja Karnaugh' kaart 7muutuja kaarti ei eksisteeri, sest 3mõõtmelise ruumi võimalused on 6muutuja kaardiga ammendatud ehk ruudu 7ndat naabrit pole ruumis enam 6muutuja Karnaugh' kaart on tabel mõõtmetega 4 4 4 = 64 ruutu ; kuhugi paigutada. Argumentvektorite paiknemine kaardi ruutudes x4 x5 00 x4 x5 00 Kaardi igale ruudule vastab loogikafunktsiooni üks argumentvektor x 2 x3 01 11 10
-nide klass sisaldab korteezhide kodeerimise ja dekodeerimise f.-ne cm,c1m, cmm, siis selle klassi iga m-kohalise f.- ni f jaoks leidub samasse klassi kuulub ühekohaline esindaja ühe muutuja f.-n, nii, et iga esialgse f.-ni argumentvektori korral kehtib: f(x1,..xn) = g(cm(x1,..,xn)) Tõestus: Iga n = cm jaoks kehtib seos g(n) = f(c1m,..,cmm) Ühekohaliste esindajate leidmiseks peame sisse tooma 4 operaatorit: Kõik peab kehtia kõigi argumentvektorite korral Liitmisoperaator: h(x) = f(x) + g(x) h=fog Kompositsioonioperaator: h(x) = g(f(x)) f=f*g Pööramisoperaator: h(x) = z[f(z) - x] h = f-1 Lahutamistehe on määratud, kui f(z)>= x Iteratsioonioperaator: h(x) = f(f(...f(0)...)) rekursiivne pöördumine kuni nullini. h = if 28. Arvutatavate funktsioonide klassi universaalne funktsioon. k+1-kohalist f.-ni U nimetatakse f.-nide klassi alamklassi (klassi F k-argumendiga klassid) Fk universaalseks f.-niks, kui:
annaabi.ee 
