Diskreetne matemaatika kodutöö (1)

Tallina Tehnikaülikool Diskreetne Matemaatika KODUTÖÖ


1. Leida oma matriklinumbrile vastav 
loogikafunktsioon
1-de piirkond: 1, 3, 9, 10, 13 Määramatuspiirkond: 4, 5, 6, 7, 8, 12, 14 0-de piirkond: 2, 11, 15 179159   3A9AD11  4E856E1C7 −¿ 4, 5, 6,7, 8,12, 14 ¿ ¿ 0, 2, 11,15 ¿ 0 ¿ 1, 3, 9,10, 13 ¿ 1 Π ¿ f ( x1 …x4 )=Σ ¿   2. Esitada loogikafunktsiooni tõeväärtustabel -----> 3. Leida     MDNK     ja     MKNK    , mis sobiksid  matriklinumbrist leitud osaliselt määratud 
4-muutuja funktsiooni esitamiseks.
Kuna matriklinumber on paarituarvuline, siis leian MKNK Karnaugh’ 
kaardiga ning MDNK McCluskey’ meetodiga. MKNK x 1 x2 x3 x4 f 0  0  0  0 0 0  0  0  1 1 0  0  1  0 0 0  0  1  1 1 0  1  0  0 - 0  1  0  1 - 0  1  1  0 - 0  1  1  1 - 1  0  0  0 - 1  0  0  1 1 1  0  1  0 1 1  0  1  1 0 1  1  0  0 - 1  1  0  1 1 1  1  1  0 - 1  1  1  1 0


MKNK:  f (x1 x2 x3 x4)=¿ (  x1  v  x4  ) (  ´x1  v  ´x3v ´x4  )


MDNK  1,3, 4∗,5∗, 6∗, 7∗, 8∗, 9, 10,12∗, 13,14∗¿ 1 f (x1 x2 x3 x4 )=Σ ¿ inde
x laiend. 1de 
pk. K
? 2-sed 
interv. K? 4-sed  inter. K? 0 00-1
-001
0-01
010-
01-0
-100
100-
10-0
1-00 K
K
K
K
K
K
K
K
K 0--1
--01
01--
-10-
-1-0
1-0-
1--0 A
1
A
2
A
3
A
4
A
5
A
6
A
7 1 0001
0100*
1000* K
K
K 2 0011
1001
1010
0101*
0110*
1100* K
K
K
K
K
K 0-11
1-01
1-10
-101
01-1
011-
-110
110-
11-0 K
K
K
K
K
K
K
K
K 3 1101
0111*
1110* K
K
K 4 1 3 4* 5* 6* 7* 8* 9 10 12 * 13 14 * A1 1 1 1 1 A2 1 1 1 1 A3 1 1 1 1 A4 1 1 1 1 A5 1 1 1 1


A6 1 1 1 1 A7 1 1 1 1 f =¿  (A1)(A2)(A7) MDNK  f (x1 x2 x3 x4)  =  ´x1x4  v ´x3x4  v  x1´x4


Kontrollin tõeväärtustabeliga kas MDNK ja 
MKNK on omavahel loogiliselt võrdsed või ei MDNK:  f (x1 x2 x3 x4)  =  ´x1 x4  v ´x3x4  v x 1 ´x4 MKNK:  f (x1x2 x3 x4)=¿ (  x1  v  x4  ) ( ´ x 1  v  ´x3v ´x4  ) Vastus: MDNK ja MKNK on loogiliselt võrdsed, sest 
nende tõeväärtustabelid on võrdsed x 1 x2 x3 x4 MDNK MKNK 0 0  0  0  0 0 0 1 0  0  0  1 1 1 2 0  0  1  0 0 0 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 7 0  1  1  1 1 1 8 1  0  0  0 1 1 9 1  0  0  1 1 1 1
0 1  0  1  0 1 1 1
1 1  0  1  1 0 0 1
2 1  1  0  0 1 1 1
3 1  1  0  1 1 1 1
4 1  1  1  0 1 1 1
5 1  1  1  1 0 0


4. Teisendada punktis 3 leitud     MKNK  loogikaalgebra põhiseaduste abil     DNK- kujule
DNK: f (x1 x2 x3 x4)=¿ (  x1  v  x4  ) (  ´x1  v ´ x 3 v ´x4  ) = ( x1 ´x1  v  x1 ´x3  v  x1 ´x4  v x 4 ´x1  v  x4 ´x3  v  x4 ´x4 ) = = ( x1 ´x3  v  x1 ´x4  v  ´x1 x4  v  ´x3 x4 )  Uurin kas MKNK’st teisendatud DNK 
on kokkulangev MDNK’ga MDNK ja DNK on omavahel loogiliselt võrdsed sest nende 
tõeväärtustabelid on võrdsed x 1 x2 x3 x4 MDNK DNK 0 0  0  0  0 0 0 1 0  0  0  1 1 1 2 0  0  1  0 0 0 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 7 0  1  1  1 1 1 8 1  0  0  0 1 1 9 1  0  0  1 1 1 1
0 1  0  1  0 1 1 1
1 1  0  1  1 0 0 1
2 1  1  0  0 1 1 1
3 1  1  0  1 1 1 1
4 1  1  1  0 1 1 1
5 1  1  1  1 0 0


5. Leida vabaltvalitud viisil   punktis 3 
saadud MDNK-ga (loogiliselt) võrdne 
Taandatud DNK ja Täielik DNK
Täieliku DNK jaoks võtan MDNK tõeväärtustabelist kõik ühtede piirkonnad. Täielik DNK: f ( x1 x2 x3 x4)=¿   ´x1´x2´x3x4  v  ´x1´x2x3x4  v  ´x1x2´x3x4  v  ´x1x2x3x4  v x 1 ´x2 ´x3 ´ x 4 v x1 ´x2 ´x3 x4 v  v  x1 ´x2 x3 ´x4  v  x1 x2 ´x3 ´x4  v x 1 x2 ´x3 x4  v  x1 x2 x3 ´x4 Taandatud DNK jaoks leian 
karnaugh kaardilt lihtimplikandid TaDNK:  f (x1x2 x3 x4)  =  ´x1x4  v ´ x 3 x4  v  x1´x4  v  x1 ´x3 Vastus: TaDNK ja Täielik DNK on tõepoolest MDNK 
tõeväärtustabeliga võrdsed x 1 x2 x3 x4 MDNK TaDNK Täielik DNK 0 0  0  0  0 0 0 0 1 0  0  0  1 1 1 1 2 0  0  1  0 0 0 0 3 0  0  1  1 1 1 1 4 0  1  0  0 0 0 0 5 0  1  0  1 1 1 1 6 0  1  1  0 0 0 0 7 0  1  1  1 1 1 1 8 1  0  0  0 1 1 1 9 1  0  0  1 1 1 1 1
0 1  0  1  0 1 1 1 1
1 1  0  1  1 0 0 0 1
2 1  1  0  0 1 1 1 1
3 1  1  0  1 1 1 1 1
4 1  1  1  0 1 1 1 1
5 1  1  1  1 0 0 0


6.     Leida vabaltvalitud viisil      punktis 3  saadud MKNK-ga (loogiliselt)     võrdne     Täielik  KNK    . Leian täieliku KNK kasutades MKNK 
tõeväärtustabeli nullide piirkonda: Täielik KNK: f (x1 x2 x3 x4)  = ( x1 v x2 v x3 v x4¿ ( x 1 v x2 v ´ x 3 v x4 )( x1 v ´x2 v x3 vx4 )( x 1 v ´ x 2 v ´ x 3 v x4 ) ´ x ¿ ¿ ¿ ) ´ x ¿ ¿ ¿ )   x 1 x2 x3 x4 MKNK Täielik KNK 0 0  0  0  0 0 0 1 0  0  0  1 1 1 2 0  0  1  0 0 0 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 7 0  1  1  1 1 1 8 1  0  0  0 1 1 9 1  0  0  1 1 1 1
0 1  0  1  0 1 1 1
1 1  0  1  1 0 0 1
2 1  1  0  0 1 1 1
3 1  1  0  1 1 1 1
4 1  1  1  0 1 1 1
5 1  1  1  1 0 0


7. Teha punktis 3 saadud MDNK’le Shannoni
disjunktiivne arendus selle muutuja 
(muutujate) Xi järgi, mida esineb MDNK’s 
kõige rohkem MDNK  f (x1x2 x3 x4)  =  ´x1x4  v ´x3 x4  v  x1´x4 f =¿   ´x4f ( x1x2x30¿  v  x4f (x1x2x31)  = f =¿   ´ x 1∗0 ´ x 4 ¿  v  ´x3∗0  v  x1∗1¿  v  ´ x 1∗1 x 4 ¿  v  ´x3∗1  v  x1∗0¿  = f =¿   ´ x 1 ´ x 4 ¿ ) v  x4 ( ´x1  v  ´x3 ) 8.     Teha punktis 3 saadud MDNK-le 
Shannoni     disjunktiivne     arendus  vabaltvalitud     2hemuutuja järgi. Teen arenduse  x1x4  muutujate järgi: f =´x 1 ´x4 f ( 0 x2x30¿  v  ´x1x4 f (0 x2x3 1)  v  x1´x4 f (1 x2x30)  v  x1 x4f (1 x2x31) = 0 f =´x1 ´x4 ¿ ) v  ¿ ´ x1 x4 ¿ 1 v  ´x3 ) v  ¿ x1 ´x4 ¿ 1) v  ´ x 3 x 1 x4 ¿ ) 9.     Teha punktis 3 saadud MDNK-le 
Shannoni     konjunktiivne     arendus  vabaltvalitud     2hemuutuja järgi. Teen arenduse  x1x4  muutujate järgi: x 1 v x4 v f f =¿ ( 0 x2x30¿ ] [ x1 v ´x4 v f (0 x2x31) ] [ ´x1v x4 v f (1 x2x30) ] ´ x 1 v ´x4 v f (1 x2 x3 1 ) ¿ ] = = [ x1v x4 v 0 ] [ x1v ´x4 v(1v ´x3) ] [ ´x1v x4 v 1¿[ ´x1v ´x4v ´x3]




10. 
Leida ja esitada punktis 3 saadud MDNK jaoks 
tema     tuletis     muutuja     x1     järgi. MDNK  f (x1x2 x3 x4)  =  ´x1x4  v ´x3 x4  v  x1´x4 δ f ( x1 x2 x3 x4) δ x 1  =  f (0 x2x3 x4)f (1 x2 x3x4) = ( ´x3x4  v  ´x4 )  ⨁  ( x4  v ´ x 3 x4 ) = =  ´ (´ x 3 x4 v ´ x 4 )( x4 v ´ x 3 x4 ) v ( ´x3x4  v  ´x4 ) ´ ( x 4 v ´x3 x4 )  =  = ´ ´ x 3 x4 x4 ¿ ) x4 v ( ´x3 ´x4 ¿(´x4 ´ ´ x 3 x4 )  =  =   x3x4  v  ´ x 3 ´ x 4 ¿ )( ´x4v x3 ¿  =  x3 x4  v  ´x3 ´x4 ´x4  v  ´x3 ´x4 x3 Leida ja esitada punktis 3 saadud MDNK jaoks 
tema     tuletis     muutuja     x3     järgi. δ f ( x1 x2 x3 x4) δ x 3  =  f (x1x20 x4)f (x1x21 x4) =  ( ´x1 x4  v  x1´x4 ¿   ⨁   ´x1x4  v x4  v  x1 ´x4  =  =  ´ ( ´ x 1 x4 v x1 ´x4 ) ´ x 1 x4  v x4  v  x1´x4  v ( ´x1x4  v  x1´x4 ¿ ´ ´ x 1 x4 v x 4 v x1 ´ x 4  = = ( ´ ´ x 1 x4    ´ x 1 ´x4 ) ´x1 x4  v x4  v  x1´x4  v ( ´x1 x4  v  x1 ´x4¿( ´ ´ x 1 x4 ) ( ´ x 1 ´ x 4 ´ x4 ¿¿ ) =  = ( x1  v  ´x4 )( ´x1x4  v x4  v  x1´x4 ) v ( ´x1x4  v  x 1 x 1 ´ x 4 ¿ ¿  v  ´x4 )( ´ x 4 )( ´x1  v  x4¿  = =  x 1 ¿  v  x 4  v  x1x4  v  x1  v  ´x4  v  ´x1  v  ´x4 ) v ( ´x1´x4 ¿ ( x1v x4 v  x1  v  ´x4  v  x4  v  ´x4¿  =


=  ´x4  v ( ´x1´x4 ¿ ( x1 ) =  ´x4  v  x1  v  ´x4  =  x1  v  ´x4


11.      Leida ja esitada punktis 3 saadud 
MDNK-ga loogiliselt võrdne     Reed-Mulleri  polünoom.
Leian Reed-Mulleri polünoomi Karnaugh kaardi abiga. f =x 1 ´ x 3 x4   ⊕   ´x1 x4   ⊕   x1 ´x4  =  x 3 ⊕ x 1 ¿ 1) x4   ⊕   x 1 ⊕ ¿ 1) x4⊕ x 4 ⊕ x 1 ¿ 1) =  =  x1 x3x4 ⊕ x1x4 ⊕   x1x4 ⊕ x4⊕ x1 x4⊕ x1   =  x1 x3x4 ⊕ x1x4 ⊕ x4⊕x1 Leitud polünoom on korrektne MDNK Karnaugh kaardi suhtes. x 1 x2 x3 x4 MDNK Polünoom 0 0  0  0  0 0 0 1 0  0  0  1 1 1 2 0  0  1  0 0 0 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 7 0  1  1  1 1 1 8 1  0  0  0 1 1 9 1  0  0  1 1 1 1
0 1  0  1  0 1 1 1
1 1  0  1  1 0 0 1
2 1  1  0  0 1 1 1
3 1  1  0  1 1 1 1
4 1  1  1  0 1 1 1
5 1  1  1  1 0 0