Kui MDNK ja TaDNK on teineteisest erinevad avaldised, siis MDNK t e sisaldub TaDNK sees. i . . . . on 7 implikanti : t Kuna kõik lihtimplikandid on Karnaugh' kaardil hästi näha, siis sobib kaart u {001} {011} {100} {101} {100 101} {001 011} {001 101} ka TaDNK leidmiseks. r v . . . . mida esitavad Karnaugh' kaardil sellised kontuurid : Igal loogikafunktsioonil on täpselt 1 TDNK ja täpselt 1 TaDNK. A
Sellest saame MKNK jaoks x 1 V x2V x 3 MKNK - f(x1, x2, x3, x4) = (x1Vx2Vx3)&( x1V x 4 )&( x 1 V x 2 Vx3)&( x 1 V x2V x 3 ) 2) Leian MDNK McCluskey' meetodiga MDNK leidmiseks leian funktsiooni 1de elementide kahendvektorid ja paigutan need indeksi (1de arv kahendvektoris) põhjal tabelisse. MDNK saaamiseks lähtun funktsiooni 1de piirkonnast. Määramatused märgin tärniga (*). Välja jätan vahed, mis ei vasta 2-astmele. (2n) Leian lihtimplikandid ehk sellised intervallid, mida ei ole suurimas implikantide intervallis. Tähistan implikandid A tähega. 1-de 2-sed 4-sed Indeks Vahe Vahe pk. intervallid intervallid 2 2-6* A6 4 9-11*-13*-15 2,4 A1
Kasutan kleepimisseadust: x1 = x1xx2 V x1x2 f(x1x2 x3x4) = xx1 xx2 x3 V x1 xx2 xx3 V x2 x4 = xx1 xx2 x3x4 V xx1 xx2 x3xx4 V x1xx2 xx3x4 V x1xx2 xx3 xx4 V 4 V x1x2x4 V xx1 x2 x4 = = xx1 xx2 x3x4 V xx1 xx2 x3xx4 V x1xx2 xx3x4 V x1xx2 xx3 xx4 V x1x2 x3x4 V x1x2 xx3 x4 V xx1 x2 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:
A6 x MKNK: f(, , , ) = (v v )( v v )( v v ) 3.Teisendada punktis 2 leitud MKNK loogikaalgebra põhiseaduste abil DNK-kujule 4. Leida vabaltvalitud viisil punktis 2 saadud MDNK-ga (loogiliselt) võrdne Taandatud DNK ja Täielik DNK, näidates (selgitades) mõlema jaoks ära ka nende leidmisviisi. Taandatud DNK leidmine MDNK: f(, , , ) = v v v Taandatud DNK on kõigi lihtimplikantide disjunktsioon. Kõik lihtimplikandid ehk maksimaalsed ühtede intervallid on märgitud Karnaugh' kaardil kontuuridena. x3x4 00 01 11 10 x1x2 00 1 1 1 1 01 1 0 1 1 11 0 0 1 1 10 1 1 0 0 Taandatud DNK: f(, , , ) = v v v v Täieliku DNK leidmine Täieliku DKN saab Karnaugh' kaardilt, kirjutades välja kõik ühtede intervallid. x3x4 00 01 11 10 x1x2
6* X 6-7* 1 X 10 X 6-14 8 X 12 X 10-11 1 X 3 7* X 10-14 4 X 11* X 12-14 2 A2 14 X 3-4 7-15 8 X 4 15 X 11-15 4 X 14-15 1 X Lahendan katteülesande: Lihtimplikandid 0 3 10 12 14 15 A1 x A2 x x A3 x x A4 x x x A5 x x Valin MKNK jaoks A1, A2, A4 ja A5. Impl Vahe
näidates (selgitades) mõlema jaoks ära ka nende leidmisviisi. Taandatud DNK leidmine f (x1, x2, x3, x4) = Karnaugh' kaart: x3x4 00 01 11 10 x1x2 00 1 0 0 1 01 0 1 1 0 11 1 0 1 0 10 1 0 0 1 Taandatud DNK on kõigi lihtimplikantide disjunktsioon. Kõik lihtimplikandid ehk maksimaalsed ühtede intervallid on märgitud Karnaugh' kaardil kontuuridena. Seega taandatud DNK on võrdne minimaalse DNK-ga. Taandatud DNK: f (x1, x2, x3, x4) = Täieliku DNK leidmine Karnaugh' kaart: x3x4 00 01 11 10 x1x2 00 1 0 0 1 01 0 1 1 0 11 1 0 1 0 10 1 0 0 1
x1 x 2 x 4 x1 x 2 x 3 x 4 x 2 x 3 x 4 x1 x3 x 4 x1 x 2 x3 x 4 = = x1 x2 x4 x3 x4 x1 x2 x3 = MDNK Ülesanne 4 1. Leida vabaltvalitud viisil punktis 2 saadud MDNK-ga võrdne Taandatud DNK Taandatud DNK on funktsiooni kõigi lihtimplikantide disjunktsioon. Taandatud DNK võib sisaldada ka liiased liikmeid. Funktisooni lihtimplikantide hulga leidsin McCluskey meetodiga ülesandes 2. Kuna lihtimplikandid A6 ja A7 sisaldavad määramatust ja ei osutunud valituks MDNK-sse, ei vali ka neid TaDNK-sse , et saadud avaldis oleks loogiliselt võrdne MDNK-ga. Sellele hulgale vastav funktsiooni taandatud DNK: TaDNK : f(x1, x2, x3, x4) = A1 A2 A3 A4 A5 A8 x1 x 2 x3 x1 x 2 x 4 x1 x3 x 4 x1 x 2 x 4 x1 x 2 x3 x3 x 4 TaDNK : f(x1, x2, x3, x4) = 2. Täielik DNK TDNK leidmine: võtan f
Maksimaalsed ühtede intevallid: {3,7},{0,1,2,3}. Intervalle võime esitada baasis {0,1,-} Näiteks: {1} 001 x1 x2 x3 {0,1,2,3} 0-- x1 {3,7} -11 x2x3 · Konjunktsiooni, mis vastab ühtede intervallile nimetatakse funktsiooni implikandiks. · Konjunktsiooni, mis vastab maksimaalsele ühtede intervallile nimetatakse funktsiooni lihtimplikandiks. · Kõigi lihtimplikantide disjunktsioon esiatb funktsiooni taandatud DNK. Näit. f(x1 ,x2 ,x3 ) = (1,3,6,7)1 Lihtimplikandid: {1,3} 0-1 {3,7} -11 {6,7} 11- Taandatud DNK: x1 x3 x2 x3 x1 x2 · Taandatud DNK võib sisaldada liiaseid liikmeid. Eelmises näites esitatud funktsiooni MDNK on järgnev: x1 x3 x1 x2 . Kõik eelpool esitatu võib olla interpreteeritud nullide piirkonna ja vastavalt KNK jaoks (maksimaalne nullide intervall, taandatud KNK jne.) Ülesanded · Antud funktsioon f(x1 ,x2 ,x3 ) = x1 x2 x3 Esitada funktsioon TDNK, MDNK ja taandatud DNK kujul.
Intervalle võime esitada baasis {0,1,-} Näiteks: {1} 001 x1 x2 x3 {0,1,2,3} 0-- x1 {3,7} -11 x2x3 Konjunktsiooni, mis vastab ühtede intervallile nimetatakse funktsiooni implikandiks. Konjunktsiooni, mis vastab maksimaalsele ühtede intervallile nimetatakse funktsiooni lihtimplikandiks. Kõigi lihtimplikantide disjunktsioon esiatb funktsiooni taandatud DNK. Näit. f(x1 ,x2 ,x3 ) = (1,3,6,7)1 Lihtimplikandid: {1,3} 0-1 {3,7} -11 {6,7} 11- Taandatud DNK: x1 x3 x2 x3 x1 x2 Taandatud DNK võib sisaldada liiaseid liikmeid. Eelmises näites esitatud funktsiooni MDNK on järgnev: x1 x3 x1 x2 . Kõik eelpool esitatu võib olla interpreteeritud nullide piirkonna ja vastavalt KNK jaoks (maksimaalne nullide intervall, taandatud KNK jne.) Ülesanded Antud funktsioon f(x1 ,x2 ,x3 ) = x1 x2 x3
11-1 X Lihtimplikant 0 1 2* 3 4* 5 7 9 11 13 15* A1 X X X X A2 X X X X A3 X X X X X X X X MDNK jaoks valitud lihtimplikandid: A2 ja A3 f ( x 1 ... x 4 )= x´1 x´3 v x 4 Seega, MDNK = Tuvastan, kas MDNK ja MKNK on teineteisega loogiliselt võrdsed, kasutades tõeväärtustabelit Nr. x1x2x3x4 f MDNK MKNK 0 0000 1 1 1 1 0001 1 1 1 2 0010 - 0 0 3 0011 1 1 1 4 0100 - 1 1 5 0101 1 1 1 6 0110 0 0 0
v 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1 2 0 0 1 0 0 0 0 Taandatud DNK jaoks leian 3 0 0 1 1 1 1 1 karnaugh kaardilt lihtimplikandid 4 0 1 0 0 0 0 0 5 0 1 0 1 1 1 1 TaDNK: f ( x 1 x 2 x3 x 4 ) = ´x 1 x 4 v 6 0 1 1 0 0 0 0 ´x 3 x 4 v x 1 ´x 4 v x 1 ´x 3 7 0 1 1 1 1 1 1
(Erinevused esinevadki ainult algse funktsiooni määramatuspiirkondades) 4. ( x´ 1 V x´4 ¿ ( x´ 2 V x´4 ¿( x2 V x 3 )( x´1 V x´2 V x´3 ¿ = Kuna ei tulnud sarnane MDNK-le, võrdlen väärtusi Antud loogikaavaldise väärtused ei ole MDNK-ga võrdsed, kuna leitud DNK on formuleeritud MKNK-st, mis ei ole MDNK-ga loogiliselt võrdne. 5. Leian taandatud DNK. Taandatud DNK moodustavad kõik funktsiooni lihtimplikandid, maksimaalsed 1-de piirkonna intervallid. x´ 1 x´4 V x 2 x´3 V x´1 x´2 x 3 V x´ 2 x 3 x´4 Taandatud DNK osutus samaks, mis on MDNK, need on loogiliselt võrdsed. Leian täieliku DNK. Täielik DNK on funktsiooni ühtedeks avalduvate 2- ndvektorite disjunktsioon, kus igas elementaarkonjuktsioonis on kõik funktsiooni muutujad esindatud.
edasi proovime kleepimist jätkata ehk 4-seid gruppe kokkukleepida 8-steks . . . A2 1 1 1 1 valitud kuid rohkem ei õnnestu kleepida — pole isegi kandidaate. A3 1 1 1 1 Sellega on kleepimistabel valminud. tekkinud suurimad 1-de intervallid ( lihtimplikandid ) MDNK on seega tekkimas 2-liikmeline : f = A1 w A2 Valminud kleepimistabelis märgistame ära suurimad grupid (suurimad ühtede intervallid) — grupid mis ei sisaldu tervikuna üheski teises grupis esindajate tabel siin kleepimistabelis : lahendisse valitud iga intervalli (siin: A1 A2 ) koosseisust :
f(1000) = 0 v 0 v 0 v 0 v 0 v 0 v 0 v 0 v 1 v 0=1 f(1011) = 0 v 0 v 0 v 0 v 0 v 1 v 0 v 0 v 0 v 0= 1 f(1110) = 0 v 0 v 0 v 0 v 0 v 0 v 1 v 0 v 0 v 0= 1 *Saadud DNK on täielik, kuna iga tema elementaarkonjunktsioon sisaldab kõiki nelja funktsiooni muutujat. 5.2 Taandatud DNK 1 0 1 1 1 0 1 0 1 0 1 1 1 0 1 0 *Otsin kõik lihtimplikandid (mis ei sisaldu mõnes teises funktsiooni implikandis) Taandatud DNK: f(x1, x2, x3, x4) = ´x 3 ´x 4 v x 3 x
0 0 Kleepimisel moodustunud korduvaid intervalle võib ignoreerida ehk jätta 1 1 kleepimistabelisse üldse märkimata. (1-5-3-7 on juba olemas: 1-3-5-7) 2 3 5 5. Moodustunud lõplikus kleepimistabelis märgistada kõik lihtimplikandid: 6 index 1de pk 2-sed vahe 4-sed vahe 3 7 0 0 0 - 1 A2 1 1-3-5-7 A1 2,4 2. "Kleepida" naabersektsioonide arve kokku "kahesteks" intervallideks
a 0 1 1 1 & abc 1 b Joonis 1.7. Funktsiooni Karnaugh 1 c kaart Joonis 1.8. Funktsioonile vastav loogikalülitus 28 Quine - Mc Cluskey meetodi kohaselt määratakse kõigepealt esmased ehk lihtimplikandid ning seejärel eraldatakse neist olulised lihtimplikandid. Minimeerimise tulemusena saadakse funktsiooni minimaalne disjunktiivne või konjunktiivne normaalkuju. 29 1.3. Funktsionaalsed loogikalülitused 1.3.1. Trigerid Triger (flip-flop) on kahe stabiilse olekuga loogikalülitus. Ühte olekutest tähistatakse numbriga 1, teist numbriga 0. Trigeri olek vastab tema väljundsignaalile. Sõltuvalt
annaabi.ee 
