Diskreetne matemaatika (0)

Tallinna Tehnikaülikool 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 𝒇(x 1 ,x2,x3,x4 ) = ∑ ( 3, 5, 8, 12, 15 )1 ( 4, 9, 13 )_  (x 𝒇(x 1 ,x2,x3,x4 ) = ∏ ( 0, 1, 2, 6, 7, 10, 11, 14 )0 2


ÜLESANNE 2 TÕEVÄÄRTUSTABEL Esitada oma loogikafunktsiooni tõeväärtustabel. x1 x2 x3 x4 f 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 - 0 1 0 1 1 0 1 1 0 0 0 1 1 1 0 1 0 0 0 1 1 0 0 1 - 1 0 1 0 0 1 0 1 1 0 1 1 0 0 1 1 1 0 1 - 1 1 1 0 0 1 1 1 1 1 ÜLESANNE 3 MINIMAALSED NORMAALKUJUD Leian MDNK ja MKNK, mis sobiksid matriklinumbrist leitud osaliselt määratud 4-muutuja
funktsiooni esitamiseks. MDNK Karnaugh’ kaardiga ja MKNK McCluskey' meetodiga. 3


3.1 MDNK KARNAUGH’ KAARDIGA Leian MDNK Karnaugh kaardiga, sest matriklinumber on paarisarv.
Funktsioon  (x 𝒇(x 1 ,x2,x3,x4 ) = ∑ ( 3, 5, 8, 12, 15 )1 ( 4, 9, 13 )_  x1x2/x3x4 00 01 11 10 00 0 0 1 0 01 x 1 0 0 11 1/1 x/x/x 1 0 10 1 x 0 0 𝒇(xMDNK  = x2 x3     v     x1 x3     v     x1 x2 x4     v     x1 x2 x3 x4   4


3.2 MKNK MCCLUSKEY MEETODIGA Leian MKNK McCluskey meetodiga: (x 𝒇(x 1 ,x2,x3,x4 ) = ∏ ( 0, 1, 2, 6, 7, 10, 11, 14 )0 Indeks 0-intervall M 0 0000 K 1 0001 K 0010 K 0100* K 2 0110 K 1001* K 1010 K 3 0111 K 1011 K 1101* K 1110 K Indeks 0-intervall M 0-1 000- A1 00-0 K 0-00 K 1-2 -001 A2 0-10 K -010 K 01-0 K 2-3 011- A3 -110 K 10-0 A4 1-01* * 101- A5 1-10 k Indeks 0-intervall M 2 0--0 A6 2-3 --10 A7 5


Edasine ülesanne seisneb loogikafunktsiooni lõpuni määramises. Katta on vaja kogu loogika-funktsiooni nullide piirkond. 0 1 2 4 6 7 9 10 11 13 14 A1 x x A2 x A3 x x 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  x2  v  x3)(x1  v  x2  v  x3) Ʌ Ʌ (x3 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  x2  v  x3)(x1  v  x2  v  x3)(x3 v  x4) 𝒇(xMDNK (x1x2x3x4)  = x2 x3     v     x1 x3     v     x1 x2 x4     v     x1 x2 x3 x4   Et kontrollida, kas saadud minimaalsed normaalkujud on teineteisega loogiliselt võrdsed või mitte, teeme tõeväärtustabeli, kus võrdleme kummagi funktsiooni väärtusi. x1x2x3x4 𝒇(xMDNK 𝒇(xMKNK x1x2x3x4 𝒇(xMDNK 𝒇(xMKNK 0000 0 0 1000 1 1 0001 0 0 1001 1 1 0010 0 0 1010 0 0 0011 1 1 1011 0 0 0100 1 1 1100 1 1 0101 1 1 1101 1 1 0110 0 0 1110 0 0 0111 0 0 1111 1 1 Seega saadud MDNK on loogiliselt võrdne saadud MKNK-ga. ÜLESANNE 4 MKNK TEISENDAMINE DNK-KUJULE Teisendada ülesandes 3 leitud MKNK loogikaalgebra põhiseaduste abil DNK-kujule. 7


 𝒇(xMKNK  (x1x2x3x4) = (x1  v  x2  v  x3)(x1  v  x2  v  x3)(x1  v  x2  v  x3)(x3 v  x4)  = = x1 v x1 x2 v x1 x3  v x1 x2 v x2 x3 v x1 x3 v x2 x3 )( x1 v x2 v x3 )( x3 v x4 ) = = (x1 x1 v x1 x2 v x1 x3 v x1 x1 x2 v x1 x2 x2 v x1 x2 x3 v x1 x1 x3 v x1 x2 x3 v v x1 x3 v x1 x1 x2 v x1 x2 v x1 x2 x3 v x1 x2 x3 v x2 x3 v x1 x1 x3 v x1 x2 x3 v  v x1 x3 x3 v x1 x2 x3 v x2 x2 x3 v 0 )( x3 v x4 ) = x1 x2 v x1 x3 v x1 x2 x3 v x1 x2 x3 v v x1 x3 v x1 x2 v x1 x2 x3 v x1 x2 x3 v x2 x3 v x1 x2 x 3 v x1 x2 x3 ) ( x3 v x4 ) =  = x1 x2 x3 v x1 x3 v x1 x2 x3 v x1 x2 x3 v x1 x2 x3 v x2 x3 v x1 x2 x3 x3 v x1 x2 x3 x3 v v x1 x2 x4 v  x1 x2 x4 v x1 x3 x4 v x1 x2 x3 x4 v x1 x2 x3 x4 v x1 x2 x3 x4 v x2 x3 x4 v  v x1 x2 x3 x4 v x1 x2 x3 x4 = x2 x3 v x1 x2 x4 v x1 x3 v x1 x2 x3 v x1 x2 x3 v x1 x2 x3 v v x1 x2 x3 v x1 x3 x4 v x1 x2 x3 x4 v x1 x2 x3 x4 v x1 x2 x3 x4 v x2 x3 x4 v x1 x2 x3 x4 = = x2 x3 v x1 x3 v x1 x2 x4 v x1 x2 x3 x4  = 𝒇(xMDNK MKNK-st teisendatud DNK on avaldisena kokkulangev ülesandes 3 leitud MDNK-ga. 8


ÜLESANNE 5 DISJUNKTIIVSED NORMAALKUJUD  Leida vabalt valitud viisil ülesandes 3 saadud MDNK-ga võrdne Taandatud DNK ja  Täielik DNK, selgitades mõlema jaoks ära ka nende leidmisviisi. 𝒇(xMDNK (x1x2x3x4)  = x2 x3     v     x1 x3     v     x1 x2 x4     v     x1 x2 x3 x4   5.1 TAANDATUD DNK Vaadates alamülesande 3.1 Karnaugh’ kaarti, näeme, et joonistatud kontuurid vastavad ühtlasi ka lihtimplikantidele.Leian taandatud DNK täielikult määratud Karnaugh’  kaardiga : 𝒇(xTaDNK (x1x2x3x4) =  x2 x3     v     x1 x3     v     x1 x2 x4     v     x1 x2 x3 x4  =  𝒇(xMDNK   5.2 TÄIELIK DNK Vaadates alamülesande 3.1 Karnaugh’ kaarti, saame ühtede piirkonna järgi välja  kirjutada TDNK. 𝒇(xTDNK (x1x2x3x4) =  x1 x2 x3 x4 v x1 x2 x3 x4 v x1 x2 x3 x4 v x1 x2 x3 x4 v x1 x2 x3 x4 v  v x1 x2 x3 x4 v x1 x2 x3 x4 v x1 x2 x3 x4  9


ÜLESANNE 6 TÄIELIK KNK Leida vabalt valitud viisil ülesandes 3 saadud MKNK-ga loogiliselt võrdne täielik KNK. 𝒇(xMKNK (x1x2x3x4) = (x1  v  x2  v  x3)(x1  v  x2  v  x3)(x1  v  x2  v  x3)(x3 v  x4) Teades, et saadud MKNK on loogiliselt võrdne saadud MDNK-ga, siis võime ka täieliku KNK leidmisel kasutada alamülesande 3.1 Karnaugh’ kaarti.  𝒇(xTKNK (x1x2x3x4) = x1 x2 x3 x4 v x1 x2 x3 x4 v x1 x2 x3 x4 v x1 x2 x3 x4 v x1 x2 x3 x4 v v x1 x2 x3 x4  v x1 x2 x3 x4 v x1 x2 x3 x4 10


ÜLESANNE 7 SHANNONI DISJUNKTIIVNE ARENDUS KOLME  MUUTUJA JÄRGI Teha ülesandes 3 saadud MDNK-le Shannoni disjunktiivne arendus nende muutujate xi järgi, mida esineb MDNK-s kõige rohkem. Kui MDNK-s pole ükski muutuja kõigi ülejäänud kolme suhtes esinemise poolest ülekaalus, siis teha disjunktiivne arendus mitme muutuja järgi: nende kahe või kolme muutuja järgi, mida leidub MDNK-s omavahel võrdselt ja ülejäänutest rohkem. 𝒇(xMDNK(x1x2x3x4)   = x2 x3     v     x1 x3     v     x1 x2 x4     v     x1 x2 x3 x4   Teeme sellele avaldisele Shannoni disjunktiivse arenduse muutujate x1 x2 x3 järgi: x1 x2 x3 𝒇(xMDNK(0,0,0,x4) v x1 x2 x3 𝒇(xMDNK(0,0,1,x4) v x1 x2 x3 𝒇(xMDNK(0,1,0,x4) v  v x1 x2 x3 𝒇(xMDNK(0,1,1,x4) v x1 x2 x3 𝒇(xMDNK(1,0,0,x4) v x1 x2 x3 𝒇(xMDNK(1,0,1,x4) v v x1 x2 x3 𝒇(xMDNK(1,1,0,x4) v x1 x2 x3 𝒇(xMDNK(1,1,1,x4) =  = x1 x2 x3 (0 Ʌ 1 V 0 Ʌ 1 V 0 Ʌ 0 Ʌ x4 V 1 Ʌ 1 Ʌ 0 Ʌ x4) v v  x1 x2 x3 (0 Ʌ 0 V 0 Ʌ 0 V 0 Ʌ 0 Ʌ x4 V 1 Ʌ 1 Ʌ 1 Ʌ x4) v v x1 x2 x3 (1 Ʌ 1 V 0 Ʌ 1 V 0 Ʌ 1 Ʌ x4 V 1 Ʌ 0 Ʌ 0 Ʌ x4) v v x1 x2 x3 (1 Ʌ 0 V 0 Ʌ 0 V 0 Ʌ 1 Ʌ x4 V 1 Ʌ 0 Ʌ 1 Ʌ x4) v v x1 x2 x3 (0 Ʌ 1 V 1 Ʌ 1 V 1 Ʌ 0 Ʌ x4 V 0 Ʌ 1 Ʌ 0 Ʌ x4) v v x1 x2 x3 (0 Ʌ 0 V 1 Ʌ 0 V 1 Ʌ 0 Ʌ x4 V 0 Ʌ 1 Ʌ 1 Ʌ x4) v v x1 x2 x3 (1 Ʌ 1 V 1 Ʌ 1 V 1 Ʌ 1 Ʌ x4 V 0 Ʌ 0 Ʌ 0 Ʌ x4) v v x1 x2 x3 (1 Ʌ 0 V 1 Ʌ 0 V 1 Ʌ 1 Ʌ x4 V 0 Ʌ 0 Ʌ 1 Ʌ x4) =  = x1 x2 x3 (0) v x1 x2 x3 ( x4 ) v x1 x2 x3 (1) v x1 x2 x3 (0) v  v x1 x2 x3 (1) v x1 x2 x3 (0) v x1 x2 x3 (1) v x1 x2 x3 (x4) =  = x1 x2 x3 ( x4 ) v x1 x2 x3 (1) v x1 x2 x3 (1) v x1 x2 x3 (1) v x1 x2 x3 (x4)  11


ÜLESANNE 8 SHANNONI DISJUNKTIIVNE ARENDUS      KAHE MUUTUJA JÄRGI Teha ülesandes 3 saadud MDNK-le Shannoni disjunktiivne arendus vabalt valitud kahe muutuja järgi, milleks on x1 ja x2. 𝒇(xMDNK (x1x2x3x4)  = x2 x3     v     x1 x3     v     x1 x2 x4     v     x1 x2 x3 x4   Teeme sellele avaldisele Shannoni disjunktiivse arenduse valitud mootujate järgi x1 x2 𝒇(xMDNK(0,0,x3,x4) v x1 x2 𝒇(xMDNK(0,1,x3,x4) v v x1 x2 𝒇(xMDNK(1,0,x3,x4) v x1 x2 𝒇(xMDNK(1,1,x3,x4) =  = x1 x2 (0 V 0 V 0 V x3x4) v x1 x2 (x3 V 0 V 0 V 0) v v x1 x2 (0 V x3 V 0 V 0) v x1 x2 (x3 V x3 V x4 V 0) =  = x1 x2 (x3x4) v x1 x2 (x3) v x1 x2 (x3) v x1 x2 (x3 V x4) 12


9. Jääkfunktsioonid 𝒇(xMDNK (x1x2x3x4)  = x2 x3     v     x1 x3     v     x1 x2 x4     v     x1 x2 x3 x4   1) Leida MDNK-na saadud loogikafunktsioonile tema jääkfunktsioon muutuja x2 = 0  korral ja esitada see tõeväärtustabelina. x1x2x3x4 𝒇(x 0000 0 0001 0 0010 0 0011 1 1000 1 1001 1 1010 0 1011 0 13


2) Leida MDNK-na saadud loogikafunktsioonile tema jääkfunktsioon muutuja x4 = 1  korral ja esitada see MDNK-na.  x1 x2 \ x3 x4 01 11 00 0 1 01 1 0 11 1 / 1 / 1 1 10 1 0 𝒇(xMDNK (x1,x2,x3,1) = x2 x3 v x1 x3 v x1 x2 v x1 x2 x3 14


3) Leida MDNK-na saadud loogikafunktsioonile tema jääkfunktsioon muutuja x1 = 0 korral ja esitada see tõeväärtustabelina.  x1x2x3x4 𝒇(x 0000 0 0001 0 0010 0 0011 1 0100 1 0101 1 0110 0 0111 0 15


4) Leida MDNK-na saadud loogikafunktsioonile tema jääkfunktsioon muutuja x3 = 0 korral ja esitada see TDNK-na. x1 x2 \ x3 x4 00 01 00 0 0 01 1 1 11 1 / 1 1 / 1 10 1 1 𝒇(xMDNK (x1,x2,0,x4) = x1 x2 x4 v x1 x2 x4 v x1 x2 x4 v x1 x2 x4 v x1 x2 x4 v x1 x2 x4  16


ÜLESANNE 10 TULETISED Leida ja esitada ülesandes 3 saadud MDNK jaoks tema tuletised iga muutuja järgi. Tuletisteks olevad avaldised lihtsustada DNK-ks loogikaalgebra põhiseoste abil. Kõikide jääkfunktsioonide leidmine peab olema ära näidatud.  𝒇(xMDNK (x1x2x3x4)  = x2 x3     v     x1 x3     v     x1 x2 x4     v     x1 x2 x3 x4   Tuletis x2 järgi: ∂ 𝒇 MDNK ∂(x 2)  = 𝒇(xMDNK(x1,0,x3,x4) ⊕ 𝒇(xMDNK(x1,1,x3,x4) = = ( 0 Ʌ x3 V x1 Ʌ x3 V x1 Ʌ 0 Ʌ x4 V x1 Ʌ 1 Ʌ x3 Ʌ x4 ) ⊕ ⊕ ( 1 Ʌ x3 V x1 Ʌ x3 V x1 Ʌ 1 Ʌ x4 V x1 Ʌ 0 Ʌ x3 Ʌ x4) = = ( 0 V x1 x3 V 0 V x1 x3 x4  ) ⊕ ( x3 V x1 x3 V x4 V 0) =  = ( x1 x3 V x1 x3 x4  ) ⊕ ( x1 v x3 v x4) Lihtsustus DNK-ks, teades, et a ⊕ b = a bv a b ( x1 x3 v x1 x3 x4  ) ⊕ ( x1 v x3 v x4) = !( x1 x3 v x1 x3 x4 )*( x1 v x3 v x4) v  V ( x1 x3 v x1 x3 x4 )* !( x1 v x3 v x4) = x1 x3 v x1 x3 x4 v x3 x4 v 0 =  = x1 x3 v x1 x3 x4 v x3 x4 Tuletis x4 järgi: ∂ 𝒇 MDNK ∂(x 4)  = 𝒇(xMDNK(x1,x2,x3,0) ⊕ 𝒇(xMDNK(x1,x2,x3,1) = =  ( x2 Ʌ x3 V x1 Ʌ x3 V x1 Ʌ x2 Ʌ 0 V x1 Ʌ x2 Ʌ x3 Ʌ  0) ⊕ ⊕ ( x2 Ʌ x3 V x1 Ʌ x3 V x1 Ʌ x2 Ʌ 1 V x1 Ʌ x2 Ʌ x3 Ʌ 1) = = (x2 x3 v x1 x3  ) ⊕ (x2 x3 v x1 x3 v x1 x2 x4 v x1 x2 x3 x4 )  17


Lihtsustus DNK-ks, teades, et a ⊕ b = a bv a b (x2 x3 v x1 x3 ) ⊕ (x2 x3 v x1 x3 v x1 x2 x4 v x1 x2 x3 x4 )  =  = ! (x2 x3 v x1 x3 )(x2 x3 v x1 x3 v x1 x2 x4 v x1 x2 x3 x4 ) v  v (x2 x3 v x1 x3 ) *!(x2 x3 v x1 x3 v x1 x2 x4 v x1 x2 x3 x4 ) = (x1 x2 x3 + x1 x2 x3 x4) v  v (x1 x2 x3 + x2 x3 x4 )  = x1 x2 + x1 x3 x4 + x2 x3 x4 18


ÜLESANNE 11 REED-MULLERI POLÜNOOM Leida ja esitada ülesandes 3 saadud MDNK-ga loogiliselt võrdne Reed- Mulleri polünoom. 𝒇(xMDNK (x1x2x3x4)  = x2 x3     v     x1 x3     v     x1 x2 x4     v     x1 x2 x3 x4   Leiame MDNK-le Reed-Mulleri polünoomi, teades, et a∨b=ab ab ja c=c ⊕ 1 : 𝒇(xMDNK (x1x2x3x4)  = x2 x3 v x1 x3 v x1 x2 x4 v x1 x2 x3 x4   = = x2 (x3  ⊕ 1) ⊕ x1 (x3 ⊕ 1) ⊕ x1 x2 x4 ⊕ (x1 ⊕ 1) (x2 ⊕ 1) x3 x4 = X2 x3  ⊕ x2 ⊕ x1 x3 ⊕ x1 ⊕ x1 x2 x4 ⊕ (x1 ⊕ 1)(x2 x3 x4 ⊕ x3 x4)= = X2 x3  ⊕ x2 ⊕ x1 x3 ⊕ x1 ⊕ x1 x2 x4 ⊕ x1 x2 x3 x4 ⊕ x1 x3 x4 ⊕ x2 x3 x4 ⊕ x3 x4  19