A4 x A5 x x A6 x x x x A7 x x x x Lihtimplikantide A1, A3, A5 ja A7 järgi saab välja kirjutada lõpuni määratud loogikafunktsiooni minimaalse konjunktiivse normaalkuju: 𝒇(xMKNK (x1x2x3x4) = A1 v A3 v A5 v A7 = (x1 v x2 v x3)(x1 v x 2 v x 3)(x 1 v x2 v x 3) Ʌ Ʌ (x 3 v x4) 6 3.3 VÕRDLUS Tuvastan, kas leitud MDNK ja MKNK on teineteisega loogiliselt võrdsed või mitte.Selleks koostame kummagi loogikafunktsiooni jaoks tõeväärtustabelid ning võrdleme neid. 𝒇(xMKNK(x1x2x3x4) = (x1 v x2 v x3)(x1 v x 2 v x 3)(x 1 v x2 v x 3)(x 3 v x4) 𝒇(xMDNK(x1x2x3x4) = x2 x 3 v x1 x 3 v x1 x2 x4 v x 1 x 2 x3 x4
x1 x2 x1 x2 x2 = x2 x2 = 1 x2 (x1 x2 )( x2 x3 )= (x1 x2 x2 x2 )( x2 x3 )= (x1 x2 x2 )( x2 x3 )= x2 ( x2 x3 )= x2 x2 x2 x3 = 0 x2 x3 = x2 x3 (x1 x2 )(x1 x3 x2 )= (x1 x2 x1 x2 )( x1 x3 x2 )= (x1 x2 x1 x2 )( x1 x3 x2 )= x1 x2 x1 x1 x2 x3 x1 x2 x2 x1 x2 x1 x1 x2 x3 x1 x2 x2 = x1 x2 x1 x2 x3 0 0 x1 x2 x3 x1 x2 = x1 x2 x1 x2 3.Lihtsustada etteantud loogikaavaldis DNK-ks põhiseoste ja tehete asendusseoaste abil: (x1x2x3x4 x3x4 x1x3 )(x1 x4 )(x1 x4 )= (x1x2x3x4 x3x4 x1x3 )(x1 x4 )(x1 x4 )= =(x1x2x3x4 x3x4 x1x3 )(0 x4x1 x1x4 0)= x3x4x1 x1x3x4 = x1x3x4 x1 x4 x3 (x1 x2)(x1x2 x4 )= x1 x4 x3 (x2 x1 )(x1 x2 x4 )= x1 x4 x3 x2x1 (x1 x2 x4 )= = x1 x4 x1 x2 x3 x1 x2 x2 x1 x2 x1 x1 x2 x1 x4 x4 x3 x4 x2 x4 x1 x4 =x1 x2 x4 x1 x2 x3 x3 x4 x2 x4 x1 x4 x1 x1 x2 ( x1 x3 ) x1 x1 x2 x3 x4 x1 = x1 ( x1 x3 ) x1 x1 x2 x3 x4 x1 = (x1 x1x1 x1 x3 x1 x2 x3 x4 ) x1 = =(x1 x1 x1 x3 x1 x2 x3 x4 )x1 =(x1 x1 x2 x3 x4 )x1 = x1 x1 x1 x1 x2 x3 x4 =00=0
Tallinna Tehnikaülikool Diskreetne Matemaatika KODUTÖÖ 164780 1. Matriklinumber: 164780 Matriklinumber 16ndsüsteemis: 283AC 7-kohaline arv: 35E6B74 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
2011 Diskreetne Matemaatika Eksam 1. Mis on graafi värvimise ülesanne? Mis on kromaatiline arv? Joonistada mõni näide. Mis on kromaatiline arv 2 aluselisel graafil? Mis on täieliku graafi kromaatiline arv? 2. Hulgateooria mõiste sümmeetrilise vahe kohta. Taandada sümeetriline vahe cantori normaalkujuks. Kas see täielik normaalkuju on minimaalne? Taandatud? Täielik? Mis on sümmeetrilise vahe matemaatilises loogikas? 3. Avaldis (x1x2x3x4) = Mingi konjuktiivne funktsioon (ei mäleta) 1. Leida minimaalne DNK 2. Leida taandatud KNK 4. Funktsioon (x1x2x3) = E(0,2,5,6,7)1 1. Leida täielik KNK 2. Leida shannoni arendus DNK x2 järgi. 3. Leida tuletis x3 järgi. Jääk ära näidata minimaalsel kujul.
Karnaugh' kaardiga saadud MDNK f = x1x2x3Vx1 x 2 x3 V x1 x2 x 4 V x1 x3 x 4 MKNK-st teisendatud MDNK f1 = x1 x 2 x3 V x1x2x3V x1 x3 x 4 Vx2x3 x 4 V x1 x2 x 4 Võrdlen MKNK-st lihtsustatud DNK ja McCluskey' meetodiga saadud MDNK tõeväärtustabeleid, et teada saada kas disjunktsioonkuju avaldised on loogiselt võrdsed. 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
määratud 4-muutuja funktsiooni esitamiseks. 1. Leian MDNK: 00 01 11 10 x1 x3 x2 x4 00 0 - 1 1 01 1 - 0 - 11 - 0 - - 10 0 - 0 1 MDNK: f(x1x2x3x4) = (x2 4) v ( 1 2x3) v (x3 4) 2. Leian MKNK 00 01 11 10 x1 x3 x2 x4 00 0 - 1 1 01 1 - 0 - 11 - 0 - - 10 0 - 0 1
1-de piirkond: 0, 1, 3, 5, 9, 11, 13 Määramatuspiirkonna leidmiseks saadud 16ndarv: 4 7F03 425B Määramatuspiirkond: 2, 4, 7, 15 Matriklile 164139 vastav 4-muutuja loogikafunktsioon oma numbrilises 10ndesituses: 0,1,3,5,9,11,13 ¿ ¿ ¿ 1(2,4,7,15) ¿ f ( x 1 ... x 4 )= ¿ Nullide piirkond: 6, 8, 10, 12, 14 2. Funktsiooni tõeväärtustabel Nr. x1x2x3x4 f 0 0000 1 1 0001 1 2 0010 - 3 0011 1 4 0100 - 5 0101 1 6 0110 0 7 0111 - 8 1000 0 9 1001 1 10 1010 0 11 1011 1 12 1100 0 13 1101 1 14 1110 0 15 1111 - 3. MDNK ja MKNK leidmine Matriklinumber on paaritu, seega MDNK leian Mcluskey meetodiga ja MKNK Karnaugh kaardiga MKNK leidmine: 6, 8,10, 12,14
1. Teisendatud kuju ühtede piirkond: 183BCC10>1,8,3,11,12,0 Teisendatud kuju määramatuse piirkond: 16CEDE2> 6,14,13,2 f(X1X2X3X4)=(0,1,3,8,11,12)1(2,6,13,14)_ 2. x3x4 x1x2 00 01 11 10 00 - 01 0 0 0 - 11 - 0 - 10 0 0 MKNK
1. Teisendatud kuju ühtede piirkond: 24AB1665>2,4,10,11,1,6,5 Teisendatud kuju määramatuse piirkond: 2282E7E> 8, 14, 7 f(X1X2X3X4)=(1,2,4,5,6,10.11)1(7,8,14)_ 2. MDNK Karnaugh' kaardiga! x3x4 x1x2 00 01 11 10 00 1 1 _ 01 1 1 1 _ 11 _ 10 1 1 MDNK f ( x1 x2 x3 x4 ) = x1 x2 x1 x3 x4 x1 x2 x3 x3 x4 McCluskey
2 3 x ( x 1 1)( x 2 1)x3 ¿ 4 x 1¿ x 1) x 1 ¿ 2 3 x 4 *Korrutan sulud lahti f = x3x4 x3 x4 1 x1x2x3 x1x2x3x4 x1x2x3 x1x3x4 x1x3 x2x3x4 x2x3 x3x4 x3 x1x2x3x4 x1x2x3 x 1 x 3 x 4 x 1 x 3 = x 4 x 2
MKNK: f = (X1' v X2) (X3' v X4') (X2' v X3') 11 1 1 0 0 10 - - 0 0 Leian MDNK McCluskey' meetodiga Minu funktioon on: f ( x1 x2 x3 x4 ) = ( 0,1,2,5,12,13) 1 ( 4,6,9,11) _ McCluskey' meetodit kasutades tuleb määramatuspiirkonda ka arvestada ja seetõttu viin ma määramatuspiirkonna ühtede piirkonda. Määramatuspiirond laiendatud ühtede f ( x1x2x3x4) = ( 0,1 2,5,12,13,4*,6*,9*,1 *) 1 piirkonnas on tähistatud tärnidega: Kleepimistabel Index 1- de pk 2- sed Vahe 4- sed Vahe 0 0 01 1 0 1 4 5 A1 1, 4 1 1 02 2 0 2 4 6 A2 2, 4 2 04 4 ...
0 1 0 0 0 1 1 1 0 0 1 1 0 1 1 11 1 1 0 0 10 1 1 0 0 0 0 f(x1x2x3x4) = x1 x2 x4 x1 x3 x4 x2 x3 x1 x3 x4 x1 x2 x3 x4 = (x1 1) (x2 1)x4 (x1 1)x3 (x4 1) x2(x3 1) x1(x3 1)(x4 1) x1(x2 1) (x3 1) (x4 1) = x4(x1 x2 x1 x2 1) x3 (x1 x4 x1 x4 1) x2 x3 x2 x1(x3 x4 x3 x4 1) x1(x2 x3 x2 x3 1) (x4 1) = x4 x1 x2 x4 x1 x4 x2 x4 x3 x1 x4 x3 x1 x3 x4 x3 x2 x3 x2 x1 x3 x4 x1 x3 x1 x4 x1 (x1 x2 x3 x1 x2 x1 x3 x1) (x4 1) = x4 x1 x2 x4 x1 x4 x2 x4 x3 x4 x3 x2 x3 x2 x1 x1 x2 x3 x4 x1 x2 x4 x1 x3 x4 x1 x4 x1 x2 x3 x1 x2 x1 x3 x1 1 =
DNK: f = xx 1xx 2xx 3xx 4 v xx 1x3 v x1x2xx 3 v x1xx 2xx 3x4 v x1x3xx 4 Reed-Mulleri polünoom: f = xx 1xx 2xx 3xx 4 v xx 1x3 v x1x2xx 3 v x1xx 2xx 3x4 v x1x3xx 4 = (x1 1)(x2 1)(x3 1)(x4 1) (x1 1)x3 x1x2(x3 1) x1(x2 1) (x3 1)x4 x1x3(x4 1) = (x1x2 x1 x2 1) ( x3x4 x3 x4 1) x1x3 x3 x1x2x3 x1x2 x1x4(x2x3 x2 x3 1) x1x3x4 x1x3 = x1x2x3x4 x1x2x3 x1x2x4 x1x2 x1x3x4 x1x3 x1x4 x1 x2x3x4 x2x3 x2x4 x2 x3x4 x3 x4 1 x1x3 x3 x1x2x3 x1x2 x1x4x2x3 x1x4x2 x1x4x3 x1x4 x1x3x4 x1x3 = x1 x2x3x4 x2x3 x2x4 x2 x3x4 x4 1 x1x3x4 x1x3 10
Milline on bitijada multiplekseri väljundis? V: 10101101 Vaata eelmist joonist 5) Milline joonisel kujutatud dekoodri väljunditest on aktiivne (1), kui sisendis x1 on väärtus 0 ja sisendis x2 on väärtus 1 V: B 6) Millisel joonisel on kujutatud sellele (binaar)algebralisele tehtele vastav loogikaahel? V: B 7) Millisel joonisel on kujutatud sellele (binaar)algebralisele tehtele vastav loogikaahel? V: E 8) Joonisel kujutatud prioriteedikoodri sisendisse antakse signaal x1x2x3x4 = 0010. Milline on signaal (f1f2) koodri väljundis? V: 1 9) Millised allpoolnimetatud loogikalülituste kogumid on algebralises mõttes täielikud? V: {NING; VÕI; EI}, {NING-EI}, {EI-EGA} 3.test Järjendloogikaahelad 1) Millistel joonistel on kujutatud D-trigeri loogikaskeem? V: B, E 2) Millistel joonistel on kujutatud T-trigeri loogikaskeem? V: C 3) Joonisel kujutatud trigeri sisenditesse antakse alljärgnevad signaalid. a0 = 11111000 a1 = 01010101
X3X4 2,5142605106 X1X2X3 7,3475809864 X1X3X4 3,4729028416 X1X2X4 4,1457010814 X2X3X4 4,2014352048 X1X2X3X4 4,9987527278 SUMMARY OUTPUT Regression Statistics Multiple R 0,5624358723 R Square 0,3163341104 Adjusted R Square 0,2069475681 Standard Error 549,78545375 Observations 30 ANOVA
annaabi.ee 
