Loogikafunktsiooni implikant Lihtimplikant Taandatud DNK Taandatud DNK (TaDNK) on funktsiooni kõikide lihtimplikantide disjunktsioon. Mõistel IMPLIKANT pole mingit seost loogikatehtega implikatsioon. Eelmise näitefunktsiooni Taandatud DNK esitub Karnaugh' kaardil : Ü Loogikafunktsiooni implikandiks nimetatakse tema 1-de piirkonna
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: 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
= 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.-ni ühtede piirkonna (koos määramatusega mida kasutati
KNK konjunktiivne normaalkuju täielik disjunktiivne / konjunktiivne TDNK/TKNK normaalkuju minimaalne disjunktiivne / MDNK/MDNK konjunktiivne normaalkuju taandatud disjunktiivne / TaDNK/TaKNK konjunktiivne normaalkuju 2. Ülesannete lahendamine 2.1 MDNK leidmine McCluskey meetodiga 2.1.1 Lihtimplikantide hulga leidmine implikant konjunktsioon, mis vastab funktsiooni ühtede intervallile ind nr mrg. ind. nr.-d vahe mrg. ind. nr.-d vahe mrg 1 1* x 1-2 1*-5 4 x 1-2-2-3 1*-9-5-13* 4,8 A2
Täieliku DNK jaoks võtan MDNK tõeväärtustabelist kõik ühtede piirkonnad. Täielik DNK: f ( x 1 x 2 x3 x 4 ) =¿ ´x 1 ´x 2 ´x 3 x 4 v ´x 1 ´x 2 x 3 x 4 v ´x 1 x 2 ´x 3 x 4 v ´x 1 x 2 x 3 x 4 v x 1 ´x 2 ´x 3 x´ 4 v x 1 ´x 2 ´x 3 x 4 v v x 1 ´x 2 x 3 x´ 4 v x 1 x 2 ´x 3 x´ 4 v x 1 x 2 x 3 x 4 MDNK TaDNK Täielik DNK x 1 x 2 ´x 3 x 4 x 1 x 2 x 3 x´ 4 v 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1
MKNK: : f(x1x2x3x4) = ( x 2 v x 3 )( x 2 v x 4 )( ´x 1 v x 3 ) 4. 5. MDNK-ga loogiliselt võrdne Taandatud DNK (TaDNK) ja Täielik DNK (TDNK) TaDNK 00 01 11 10 00 0 0 1 0 01 1 1 1 1 11 1 0 1 1 10 0 0 1 0 TaDNK: f(x1x2x3x4) = ´x 1
4 4. MKNK teisendamine DNK-kujule. ( x 1 x 4 )( x´ 1 x2 x´ 3 ) ( x 3 x´ 4 ) = ( x 1 ´x 1 x 1 x2 x 1 ´x 3 ´x 1 x 4 x 2 x 4 ´x 3 x 4 ) (x 3 x´ 3 ) = = x´ 1 x 4 x 4 x 2 x3 x4 x 1 x 2 x´ 4 x1 x´ 3 x´ 4 4 5. Taandatud DNK ja Täieliku DNK leidmine. MDNK (x1,x2,x3,x4) = x´ 1 x 4 x 1 ´x3 x´ 4 x 1 x2 x´ 3 TaDNK leidmine: x3x4 x1x2 00 01 11 10 00 0 1 1 0 01 0 1 1 0 11 1 0 1 1 10 1 0 0 0 TADNK (x1,x2,x3,x4) x´ 1 x 4 x 1 x2 x´ 4 x 2 x3 x 3 x2 x´ 3 x 4 , TDNK leidmine: Täielik DNK on DNK normaalkuju, milles iga elmentaarfunktsioon sisaldab funktsiooni kõiki argumente
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
1 1 0 0 - 0 1 1 1 0 1 15 ¿-1 1 1 1 1 1 0 1 1 1 1 1 1 1 0,-2,9, 11, 12,13, 14, 1 1 DNK : f ( x 1 … x 4 )=Σ ¿ 5) Leian taandatud DNK McCluskey’ meetodiga. TaDNK on kõigi lihtimplikantide disjunktsioon. L. 1de 2sed Vahe Märg Ind. Märge Ind. Ind. 4sed impl. Märge pk. impl. e
/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
x3x4 11 00 01 10 x1x2 00 1 1 1 01 1 11 1 1 1 10 Leitud kontuurid moodustavad TaDNK f(x1,x2,x3,x4)= x1 x2 x4 x1 x2 x3 x2 x3 x4 x1 x2 x4 x1 x2 x3 6. Täielik KNK 0de piirkonda kuuluvad vektorid (0001, 0110, 0111, 1000, 1001, 1010, 1100, 0100, 1011). Seega täielik KNK on f(x1,x2,x3,x4)= ( x1 x2 x3 x4 )( x1 x2 x3 x4 ) ( x1 x2 x3 x4 )( x1 x2 x3 x4 ) ( x1 x2 x3 x4 )( x1 x2 x3 x4 )
0 0 11 1 0 1 0 0 0 1 1 1 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
5.1 TAANDATUD DNK Taandatud DNK on funktsiooni kõikide lihtimplikantide disjunktsioon. Lihtimplikant ehk maksimaalne implikant on selline, mis tervikuna ei sisaldu üheski suuremas ühtede intervallis. Vaadates alamülesande 3.1 parempoolset Karnaugh’ kaarti, näeme, et joonistatud kontuurid vastavad ühtlasi ka lihtimplikantidele. Seega loogikafunktsiooni taandatud disjunktiivne normaalkuju on võrdne saadud MDNK-ga: 5 f TaDNK =x1 x´ 2 ∨ x 4 =f MDNK 5.2 TÄIELIK DNK Täielik DNK on selline disjunktiivne normaalkuju, mille korral iga elementaarkonjunktsiooni pikkus on võrdne loogikafunktsiooni argumentide arvuga. Vaadates alamülesande 3.1 parempoolset Karnaugh’ kaarti, saame ühtede piirkonna järgi välja kirjutada TDNK. Selleks valime ühtede piirkonnast minimaalse suurusega kontuurid, s.t joonistame iga muutujate väärtuse “1” ümber kontuuri suurusega 1 ning kirjutame kaardi
5. Leida vabaltvalitud viisil punktis 3 saadud MDNK-ga (loogiliselt) võrdne Taandatud DNK ja Täielik DNK Taandatud DNK leiame Karnaugh' kaardi ühtede piirkonna abil X3,X4 00 01 11 10 X1,X 2 00 - 1 1 1 01 1 0 - 1 11 1 0 0 0 10 0 0 0 0 TaDNK = x1 xx 2 x4 ∨ x2 xx 3 xx 4 ∨ xx 1x3 xx 4 ∨ xx 1 xx 2 x3 ∨ xx 1 xx 2 x4 Täieliku DNK leiab iga argumentvektori konstituentide või- tehtega liitmise teel. X3,X4 00 01 11 10 X1,X 2 00 - 1 1 1 01 1 0 - 1 11 1 0 0 0 10 0 0 0 0
1 0 1 0 1 1 1 1 0 1 1 0 0 0 1 1 0 0 1 1 1 1 1 0 1 0 0 0 1 1 1 0 - 0 1 1 1 1 1 0 0 0 5 5. Taandatud DNK ja täieliku DNK leidmine Leiame taandatud DNK Karnaugh' kaardi abil. 00 01 11 10 00 1 0 1 1 01 - 0 - 0 11 1 0 0 - 10 0 1 0 1 TaDNK = f(x1...x4) = 1 2 4 v 1 3 4 v 2 3 4 v 1 2 3 v 2 3 4 v 1 2 3 4 Täieliku DNK leiame ka Karnaugh' kaardi abil. 00 01 11 10 00 1 0 1 1 01 1 0 0 0 11 1 0 0 0 10 0 1 0 1 Täielik DNK = f(x1...x4) = 1 2 3 4 v 1 2 3 4 v 1 2 3 4 v 1 2 3 4 v 1 2 3 4 v 1 2 3 4 v 1 2 3 4 6 6. Täieliku KNK leidmine MKNK= f(x1...x4) = (1v2v3v4) (1v3v4) (1v3v4) ( 2v4) ( 2v3)
annaabi.ee 
