Leidsid 33 sarnast õppematerjali, mis on seotud failiga "Reed - Mulleri POLÜNOOM". Need materjalid aitavad sul teemat sügavamalt mõista.
polünoom, avaldise, reed, tehte, asendada, 1111, konjunktsioon, inversioon, paarisarv, keerukus, disjunktsioon, eelistatum, tehtega, katta, kujule, 0101, 0111, 1101, 1001, 1011, 1010, valikuvõimalus, tehet, ruudud, loogikaavaldise, erikuju, sulud, sulge, muutuja, karnaugh, tehted, omadusega, suurimate, koguarv, katame, puha, kumba, lihtsamat 0 1 3 2 16 17 19 18 48 49 51 50 32 33 35 34 i 1100 1101 1111 1110 00 000000 000001 000011 000010 010000 010001 110000 100000 100001 3-muutuja Karnaugh' kaart t 8 9 11 10 01 4 5 7 6 20 21 23 22 52 53 55 54 36 37 39 38 u
a teine võimalik / sobiv k kontuuridevalik i kontuuridevalik n MKNK keerukus on kontuuride arvust ja nende suurusest tulenevalt : e h f ( x1 x2 x3 x4 ) = (x w x )(x w x )(x w x) t x 3 x4 i x 1 x2 00 01 11 10 ut MKNK: 00 1 0 1
Detsember 2015 1. Minu matriklinumbrile (155423) vastav loogikafunktsioon oma numbrilises 10nd esituses: f(x1, x2, x3, x4) = ∑ (2, 3, 7, 8, 9, 13)1 (1, 4, 5, 14, 15)_ 2. Esitada oma loogikafunktsiooni tõeväärtustabel: x1 x2 x3 x4 f 0000 0 0001 - 0010 1 0011 1 0100 - 0101 - 0110 0 0111 1 1000 1 1001 1 1010 0 1011 0 1100 0 1101 1 1110 - 1111 - 3. Leida MDNK (McClusky meetodil) ja MKNK (Karnaugh’ kaardiga); tuvastada, kas leitud MDNK ja MKNK on teineteisega loogiliselt võrdsed või mitte. MKNK leidmine: 2 MKNK: f(x1x2 x3x4) = (x1 V x3) ( xx2 V x4) (xx1 V x2 V xx3) MDNK leidmine: Leian laiendatud 1-de piirkonna: ∑ (1*, 2, 3, 4*, 5*, 7, 8, 9, 13, 14*, 15*)1
Diskreetne matemaatika KODUTÖÖ Mina Ise 132456 IADB?? Tallinn 2019 ÜLESANNE 1 LOOGIKAFUNKTSIOON Leian oma matriklinumbrile vastav 4-muutuja loogikafunktsioon Matriklinumbri 5 viimast numbrit: 93656 Matriklinumber kuueteistkümnendsüsteemis: 2F478 Seitsmekohaline arv: 3F58CC8 Üheksakohaline arv: 54DFF9FF8 Ühtede piirkond: 3, 5, 8, 12 ( C16 ), 15 ( F16 )/ 0011, 0101, 1000, 1100, 1111 Määramatuspiirkond : 4, 9, 13 ( D16 ) / 0100, 1001, 1101 0-de piirkond : 0, 1, 2, 6, 7, 10 ( A16 ), 11 ( B16 ), 14 ( E16 ) / 0000, 0001, 0010, 0110, 0111, 1010, 1011, 1110 𝒇(x(x1,x2,x3,x4) = ∑ ( 3, 5, 8, 12, 15 )1 ( 4, 9, 13 )_ 𝒇(x(x1,x2,x3,x4) = ∏ ( 0, 1, 2, 6, 7, 10, 11, 14 )0 2 ÜLESANNE 2 TÕEVÄÄRTUSTABEL Esitada oma loogikafunktsiooni tõeväärtustabel.
0100 - 0101 1 0110 0 0111 0 1000 0 1001 0 1010 0 1011 - 1100 0 1101 1 1110 1 1111 1 3. Leida MDNK ja MKNK Kuna matriklinumber on paarituarvuline (155539), siis leian MKNK Karnaugh' kaardiga ja MDNK McCluskey' meetodiga. MKNK:
Loogiliselt võrdsed funktsioonid väljastavad iga argumentvektori korral võrdsed väärtused. x1x2x3x4 Funktsioon f Funktsioon f1 0000 1 1 0001 1 1 0010 0 0 0011 0 0 0100 0 0 0101 0 0 0110 1 1 0111 1 1 1000 0 0 1001 1 1 1010 0 0 1011 1 1 1100 0 0 1101 1 1 1110 0 0 1111 0 0 Tabelist selgub, et funktsioon f ja funktsioon f1 on loogiliselt võrdsed. ÜLESANNE 4 Leida vabaltvalitud viisil punktis 2 saadud MDNK-ga loogiliselt võrdne Taandatud DNK ja Täielik DNK 1) Leian taandatud DNK Kannan Karnaugh' kaardile funktsiooni elemendid ning väärtustan määramatused 1-ga.
0110* X 10-1 A1 2-3-3-4 -11- A4 2 1001 X 2-3 101- X 1-1- A5 1010 X -110 X 1100 X 1-10 X 11-0 X 0111 X 3 1011 X 1110 X -111 X 3-4 1-11 X 111- X 4 1111* X 4 5 7 9 10 11 12 14 A1 X X A2 X X X
0011 1 0100 1 0101 0 0110 1 0111 - 1000 0 1001 0 1010 0 1011 0 1100 1 1101 0 1110 0 1111 0 3. Leida MDNK ja MKNK, mis sobiksid matriklinumbrist leitud osaliselt määratud 4-muutuja funktsiooni esitamiseks. 1)MKNK Karnaugh' kaardiga f(x1, x2, x3, x4)=∑(1, 2, 3, 4, 6, 12)1 (0, 7)_ X3,X4
δ ( f MDNK ) =f MDNK ( x 1 , x 2 , x 3 , 0 ) ⨁ f MDNK ( x 1 , x 2 , x 3 ,1 )=¿ δ ( x4 ) ¿ ( x 1 ∧ x´2 ∨ 0 ) ⨁ ( x 1 ∧ x´2 ∨1 )=( x1 x´ 2) ⨁ (1) Lihtsustus DNK-ks: ( x 1 x´2 ) ⨁ (1 ) =( x 1´x´2 )= x´1 ∨ x´2 = x´1 ∨ x 2 8 ÜLESANNE 11 REED-MULLERI POLÜNOOM Leida ja esitada ülesandes 3 saadud MDNK-ga loogiliselt võrdne Reed- Mulleri polünoom. Saime f MDNK =x 1 x´2 ∨ x 4 . Reed-Mulleri polünoom on loogikaavaldis süsteemis {∧ 1}. Leiame MDNK-le Reed-Mulleri polünoomi, teades, et a ∨b=ab ab ja c´ =c 1 : x 1 x´2 ∨ x 4 =¿ ¿ x1 ´x 2 x 4 ⨁ x 1 ´x 2 ⨁ x 4 =¿ ¿ x1 ( x 2 ⨁ 1) x 4 ⨁ x 1 (x 2 ⨁1) ⨁ x 4 =¿ ¿ x1 x 2 x 4 ⨁ x 1 x 4 ⨁ x1 x 2 ⨁ x 1 ⨁ x 4 9
Intervall Märge s 3 *0011 x -011 A1 5 0101 x 2-3 -101 A2 2 6 *0110 x 110- A3 10 1010 x 101- A4 12 1100 x 3-4 1-11 A5 11 1011 x 11-1 A6 3 13 1101 x 4 15 *1111 x Lihtimplikantide hulga minimeerimine: 5 10 11 12 13 A1 x A2 x x A3 x x A4 x x
0100 -001 X -010 X 010- X 01-0 X 2 0101 X -101 X 0110 X 10-1 A 1001 X 1-01 4 1010 X 101- X A 5 3 1011 X 1101 X 4 Graaf 3.2 3 Lihtimplikantide hulga minimeerimine. 0 1* 2* 4* 5* 6 9 10 11 13 A1 0 0 0 0
8 0010 x1 x 2 x 3 x 4 10 1000 x 1 x 2 x3 x 4 11 0110 x1 x 2 x 3 x 4 12 1100 x 1 x 2 x3 x 4 14 1110 x1 x 2 x 3 x4 15 1111 x1 x 2 x 3 x 4 TKNK: f(x1,x2,x3,x4) = ( x1 x 2 x 3 x 4 )( x1 x 2 x3 x 4 )( x1 x 2 x 3 x 4 )( x 1 x 2 x3 x 4 ) ( x1 x 2 x 3 x 4 )( x 1 x 2 x3 x 4 )( x 1 x 2 x 3 x 4 )( x 1 x 2 x 3 x 4 ) Ülesanne 6 Teha punktis 2 saadud MDNK-le Shannoni disjunktiivne arendus selle muutuja (muutujate) x i järgi, mida esineb MDNK-s kõige rohkem. MDNK : f(x1, x2, x3, x4) = x1 x 2 x 4 x1 x 2 x3 x3 x 4
2 0011 X 2-3 0-11 A2 2-3-3-4 1 1 - - A5 1001 X 1-00 X 1 1 1 0* X 11-0 X 110- X 3 0 1 1 1* X 3-4 -111 A3 1101 X 11-1 X 1 1 1 0* X 111- X 4 1111 X 0 3 7* 8* 9 12 13 14* 15 A1 X X A2 X X A3 X X A4 X X X X A5 X X X X A1 x2 x3 x4 A2 x1 x3 x4 A4 x1 x3 A5 x1 x2
1000* X 1-2 00-1* X 0-1- X 0-01 X -01- X 2 0011* X 001- X --10 X 0101 X 0-10 X 2-3-3-4 --11 X 0110 X -010 X -11- X 1010* X 10-0* X 1-1- X 3 0111* X 2-3 0-11* X 1011 X -011X X 1110* X 01-1 X 011- X 4 1111 X -110 X 101- X 1-10 X 3-4 -111 X 1-11 X 111- X Katteülesande lahendamine: i 0 2 5 6 1 15 1 A1 X X A2 X X A3 X
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 x 2 x3 T mistahes intervalli ( ehk tema igat "ühtede intervalli" ). x 1 00 01 11 10 T ( meenutame : intervall on kindlate omadustega 2ndvektorite hulk ) /¯¯ näide: ¯¯¯¯¯¯¯¯¯¯¯¯¯¯�
2 3 4 1 2 4 3 4 5. Leida Taandatud DNK ja Täielik DNK MDNK = ( ´x 3 ´x 4 v x3x4 v ´x 1 ´x 2x3 v x1x2x3) 5.1 Täieliku DNK leidmine *Funktsiooni 1-de piirkonda kuulub 10 argumentvektorit: {0000, 0010, 0011, 0100, 0111, 1100 , 1111, 1000, 1011, 1110} *Koostan DNK, kus iga elementaarkonjunktsioon omandab väärtuse 1 täpselt 1de piirkonna argumentvektoti korral. * xi = 0 siis ´x i ja kui xi=1 siis otseväärtus xi *Saadud elementaarkonjunktsiooni liidan või tehtega kokku DNKs TDNK: f(x1, x2, x3, x4) = ´x 1 ´x
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 minimaalseima keerukusega loogikaskeemina, kasutades vabaltvalitud loogikaelemente AND OR ja NOT. Esmalt lihtsustan veidi loogikafunktsiooni tuues 4 sulgude ette: fD = (x2 4) v ( 1 2x3) v (x3 4) 4(x2 v x3) v ( 1 2x3). Loogikaskeemi modelleerin Circuit Simulatoris.
2 0010 X1 X 2 X 3 X 4 3 0011 X1 X 2 X 3 X 4 5 0101 X1X 2 X 3 X 4 7 0111 X1X 2 X 3 X 4 11 1011 X1 X 2 X 3 X 4 15 1111 X1X 2 X 3 X 4 TDNK: X1 X 2 X 3 X 4 X1 X 2 X 3 X 4 X1X 2 X 3 X 4 X1X 2 X 3 X 4 X1 X 2 X 3 X 4 (X1,X2,X3,X4)= V V v v v X1X 2 X 3 X 4 5. Leida vabaltvalitud viisil punktis 2 saadud MKNK-ga (loogiliselt) võrdne Täielik KNK
¿ ´x 1 V ´x2 V (0∗0∗´x 4 V 1∗x 4 V 1∗x 3 ) ¿¿ = [x 1 V x 2 V ( ´x 4 ) ]∧[ x 1 V ´x 2 V ( 0 ) ] ∧[ ´x1 V x2 V ( x3 V x 4 ) ]∧[ ´x1 V x´ 2 V ( x 3 V x 4 ) ] ⊕ 10) 1-de ruudud katta mittelõikuvate kontuuridega, annab DNK, kus V võib asendada . a) x1 00 01 11 10 x2 00 1 0 - 1 01 0 0 0 0 11 - - - 1 10 0 1 1 - DNK = ´x 1 ´x 2 ´x 4 V x1 ´x3 x 4 V x 1 x3 f ( x 1 … x 4 )=´x 1 x´ 2 x´ 4 V x 1 ´x 3 x 4 V x 1 x 3=¿ x ¿(¿¿ 1 ⨁ 1)( x 2 ⨁ 1)( x 4 ⨁ ( x3 ⨁
10 0 1 - 1 MDNK: x1 x 2 x 4 x1 x3 x 4 x1 x3 x 4 x1 x 2 x 4 x1 x 2 x3 x 4 f(x1,x2,x3,x4) = 2.2 MKNK McCluskey' meetodiga: Index Intervall Märge Index Intervall Märge Index Intervall Märge -11- A1 0 1111 X 0-1 111- X 0-1-1-2 1-1- A2 11-- A3 -110 X 1110* 1 X 1-2 1-10* X 1-2-2-3 1--0 A4 11-0 X 0011 X
10.2.x2 järgi:............................................................................................................................................9 10.3.x3 järgi:............................................................................................................................................9 10.4.x4 järgi:............................................................................................................................................9 11.MDNK Reed-Mulleri polünoom..................................................................................9 1)Martiklinumbrile vastav 4-muutuja loogikafunktsioon 142438 22C66 F36CA 6A7F86 2E97CAA 146268A6 8EB0DC8A 3E6D607C6 2E97CAA (2,14,9,7,12,10,10) (2,7,9,10,12,14) 3E6D607C6 (3,14,6,13,6,0,7,12,6) (0,3,6,13) (2,7,9,10,12,14) (0,3,6,13)
0011 1 0100 1 0101 - 0110 - 0111 0 1000 1 1001 0 1010 0 1011 0 1100 1 1101 - 1110 - 1111 0 2 3. Leida Karnaugh' kaardi abil MDNK ja MKNK, mis sobiksid matriklinumbrist leitud osaliselt määratud 4-muutuja funktsiooni esitamiseks MDNK Karnaugh' kaardiga: 0 0 1 1
11 1 0 1 1 0 12 1 1 0 0 1 13 1 1 0 1 - 14 1 1 1 0 0 15 1 1 1 1 0 1.3 Tähistusi tähistatav tähistus inversioon x disjunktsioon v konjunktsioon & või " " lihtimplikant AX (X=1..n) DNK disjunktiivne normaalkuju KNK konjunktiivne normaalkuju täielik disjunktiivne / konjunktiivne TDNK/TKNK
f =x 1 ´x 3 x 4 ⊕ ´x 1 x 4 ⊕ x 1 ´x 4 = x ⊕ x4 ⊕ x 1 ¿ 1) 4 ¿ 1) x4 ⊕ 1) = x1 ¿ x 1 x 2 x 3 x 4 MDNK Polünoom 0 0 0 0 0 0 0 = x1 x3 x4 ⊕ x1 x4 ⊕ x1 x4 ⊕ x4 ⊕ x1 x 4 ⊕ x1 1 0 0 0 1 1 1 2 0 0 1 0 0 0 = x1 x3 x4 ⊕ x1 x4 ⊕ x4 ⊕ x1 3 0 0 1 1 1 1 4 0 1 0 0 0 0 5 0 1 0 1 1 1 6 0 1 1 0 0 0
0101 (5) X -011 X 1001 (9) X 01-1 A3 1010 (10) X -101 A4 10-1 X 1-01 A5 101- X 3 0111 (7) * X 1011 (11)* X 1101 (13)* X Taandatud DNK : f ( x 1 , x 2 , x 3 , x 4 )= x´1 x 2 x´3 V x´1 x 3 x 4 V x´1 x 2 x 4 V x 2 x´3 x 4 V x 1 x´3 x 4 V x´2 x 3 V x 1 A1 A2 A3 A4 A5 A6 A7 II ETAPP: 2 3 4 5 7* 8* 9 10 11* 13*
f3 - argumendi x1 väärtus f4 - pöördimplikatsiooni eitus x2 x1 f5 - argumendi x2 väärtus f6 - argumentide summa mooduliga 2, (x1 + x2 )mod2 ehk x1 x2 f7 - disjunktsioon, loogiline liitmine, "või"-funktsioon, x1 x2 ehk x1 + x2 f8 - Pierce'i nool, Pierce'i funktsioon, "või-ei"-funktsioon, x1 x2 ehk x1 x2 f9 - ekvivalentsi- ehk samaväärsusfunktsioon, x1 x2 ehk x1 x2 f10 - argumendi inversioon x2 f11 - pöördimplikatsioon x2 x1 f12 - argumendi inversioon x1 f13 - implikatsioon x1 x2 f14 - Shefferi kriips, Shefferi funktsioon, x1 & x2 ehk x1 | x2 f15 - konstant 1 Enamkasutatavate tehete prioriteet (tähtsus), mis määrab sulgude kasutamise vajaduse loogikaavaldistes: , & , , , Loogika põhiseadused Idempotentsusseadused x&x=x xx=x Kommutatiivsusseadused x1 & x2 = x2 & x1 x1 x2 = x2 x1
· f2 - implikatsiooni eitus x1 x2 · f3 - argumendi x1 väärtus · f4 - pöördimplikatsiooni eitus x2 x1 · f5 - argumendi x2 väärtus · f6 - argumentide summa mooduliga 2, (x1 + x2 )mod2 ehk x1 x2 · f7 - disjunktsioon, loogiline liitmine, "või"-funktsioon, x1 x2 ehk x1 + x2 · f8 - Pierce'i nool, Pierce'i funktsioon, "või-ei"-funktsioon, x1 x2 ehk x1 | x2 · f9 - ekvivalentsi- ehk samaväärsusfunktsioon, x1 x2 ehk x1 x2 · f10 - argumendi inversioon x2 · f11 - pöördimplikatsioon x2 x1 · f12 - argumendi inversioon x1 · f13 - implikatsioon x1 x2 9 · f14 - Shefferi kriips, Shefferi funktsioon, x1 & x2 ehk x1 x2 · f15 - konstant 1 Enamkasutatavate tehete prioriteet (tähtsus), mis määrab sulgude kasutamise vajaduse loogikaavaldistes: , & , , , Loogika põhiseadused · Idempotentsusseadused x&x=x xx=x · Kommutatiivsusseadused x1 & x2 = x2 & x1
4-muutuja loogikafunktisooni 1de piirkond: 3, 4, 5, 6, 7, 11, 14 9-kohaline arv: 48381F86C 4-muutuja loogikafunktisooni määramatuspiirkond: 1, 8, 12, 15 4-muutuja loogikafunktisooni 0de piirkond: 0, 2, 9, 10, 13 2. f(x1x2x3x4) = ∑(3, 4, 5, 6, 7, 11, 14)1 (1, 8, 12, 15)_ x1x2x3 f x4 0000 0 0001 - 0010 0 0011 1 0100 1 0101 1 0110 1 0111 1 1000 - 1001 0 1010 0 1011 1 1100 - 1101 0 1110 1 1111 - 3. MDNK leidmine Karnaugh´ kaariga: 00 01 11 10 00 0 − 1 0 01 1 1 1 1 11 − 0 − 1 10 − 0 1 0 MDNK: f(x1x2x3x4) = ´x 1 x 2 v x 3 x 4 v x 2
1000 A1 01-0 x 2 0101 x 2-3 01-1 x 2-3-3-4 -1-1 A5 0110 x -101 -11- A6 011- x -110 3 0111* x 3-4 -111 1011 x 1-11 3 1101 x 11-1 1110* x 111- 4 1111 x 0001 0100 0101 0110 0111 1000 1011 1101 1110 1111 1 4* 5 6 7* 8 11 13 14* 15 A1 0
loogikatehe) VÕI-tehte märgina kasutatakse ka sümbolit + (+ ≡ ∨) LOOGIKATEHTED lausearvutuses ülesanded: Olgu antud järgnevad lihtlaused (väited): S — on suvi tehtemärk tehte nimi ja selgitus O — väljas on soe ¯¯ loogiline eitus e. inversioon V — vihma sajab P — väljas on pime ∧ loogiline korrutamine e. konjunktsioon e. JA-tehe
McCluskey' minimeerimismeetod Sellise laiendatud 1-de piirkonna ( 0, 2, 6, 7, 8, 10, 3*, 14* ) 1 jaotame Ü Karnaugh' kaart on visuaalheuristiline minimeerimismeetod. lahtritesse vastavalt arvude indeksile (ehk alustame kleepimistabelit) : T ( vajalike kontuuride otsene vahetu väljavalimine pole algoritmina kirjeldatav ) index laiend. 1de pk. 2-sed interv. vahe 4-sed interv. vahe T Karnaugh' kaart on kuni 6-muutujaga loogikafunktsioonide jaoks; 0 0 McCluskey' meetodis ei ole muutujate arv piiratud. 1 2 McCluskey' meetod on algoritm. Seega saab teda teostada arvutiprogrammina. 8 McCluskey' meetodist on olemas intervallmodifikatsioon ja 10ndmodifikatsioon. Järgnev näide esit
Tallinna Tehnikaülikool Diskreetne Matemaatika KODUTÖÖ TALLINN 2008 1. f( x1, x2, x3, x4 ) = (0, 2, 3, 4, 9, 12, 14)1(8, 11, 13)- 2. MKNK (Karnaugh) x1x2x3x 00 01 11 10 4 00 1 0 1 1 01 1 0 0 0 11 1 - 0 1 10 - 1 -0 0 MKNK: ()()() MDNK (McCluskey) Ind Nr. M Ind Nr-d. Vahe M Ind. Nr-d. V M . . 0 0 (0000) X 0-1 0-2 (00-0) 2 A 0-1-1- 0-4-8-12 (-- 4,8 A 1 2 00) 2 1 2 (0010) X 0-4 (0-00) 4 X 4 (0100) X 0-8 (-000) 8 X 8 (1000) X 1-2 2-3 (001-) 1 A 3 2 3 (0011) X 4-12 (-100) 8 X 9 (100
(2) (3) (7) (6) x1 x3 x4 x2 , | - | 0. : K , . 1010 0101 1000 1111 1111 1010 1011 1101 1110 0111 1-1- -1-1 10-0 : ( x 2 x 4 )( x1 x3 )( x1 x2 x4 ) 2) : M 0 M - x1 x2 x3 x4 1 0 0 0 (8) 1 0 1 0 (10) x1 x2 x3 x4 1 0 1 1 (11) M0 = 0 1 0 1 (5) 0 1 1 1 (7 )
annaabi.ee 
