Diskreetse Matemaatika kodune (2012) (4)

Tallinna Tehnikaülikool
Diskreetne Matemaatika
Kodutöö
Jago Niin
123835
IASB12
1. Leida oma matriklinumbrile vastav 4- muutuja loogikafunktsioon.
Matrikli number on 123835.
Saadud 8- kohaline 16-süsteemi arv on 10247E89.
Määramispiirkonna leidmisel tuleb arv F31680.
f(, , , ) =
2. Leida MDNK ja MKNK, mis sobiksid matriklinumbrist leitud osaliselt määratud 4-muutuja funktsiooni esitamiseks.
Leian MDNK Karnaugh ' kaardiga.
f(, , , ) =
x3x4
x1x2
00
01
11
10
00
1
1
1
01
1
0
1
11
0
0
1
10
1
1
0
0
MDNK: f(, , , ) =
v
v
v
MKNK – McCluskey meetodiga
f(, , , ) =
Indeks
Nr
Intervall
Märge
Indeks
Intervall
Märge
2
3
*0011
x
-011
A1
5
0101
x
2-3
-101
A2
6
*0110
x
110-
A3
10
1010
x
101-
A4
12
1100
x
3-4
1-11
A5
3
11
1011
x
11-1
A6
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
A5
x
A6
x
MKNK: f(, , , ) = (v
v )( v
v )( v v )
3.Teisendada punktis 2 leitud MKNK loogikaalgebra põhiseaduste abil DNK- kujule
4. Leida vabaltvalitud viisil punktis 2 saadud MDNK-ga (loogiliselt) võrdne Taandatud DNK ja Täielik DNK, näidates (selgitades) mõlema jaoks ära ka nende leidmisviisi.
Taandatud DNK leidmine
MDNK: f(, , , ) =
v
v
v
Taandatud DNK on kõigi lihtimplikantide disjunktsioon. Kõik lihtimplikandid ehk maksimaalsed ühtede intervallid on märgitud Karnaugh’ kaardil kontuuridena.
x3x4
x1x2
00
01
11
10
00
1
1
1
1
01
1
0
1
1
11
0
0
1
1
10
1
1
0
0
Taandatud DNK:
f(, , , ) =
v
v
v
v
Täieliku DNK leidmine
Täieliku DKN saab Karnaugh’ kaardilt , kirjutades välja kõik ühtede intervallid.
x3x4
x1x2
00
01
11
10
00
1
1
1
1
01
1
0
1
1
11
0
0
1
1
10
1
1
0
0
Täielik DNK:
f(, , , ) =
v
v
v
v
v
v
v
v
v
v
v
v
5. Leida vabaltvalitud viisil punktis 2 saadud MKNK-ga (loogiliselt) võrdne Täielik KNK.
MKNK: f(, , , ) = (v
v )( v
v )( v v )
x3x4
x1x2
00
01
11
10
00
1
1
1
1
01
1
0
1
1
11
0
0
1
1
10
1
1
0
0
Täielik KNK:
f(, , , ) = ( v
v
v )( v
v
v )( v
v
v )&
& ( v
v
v )( v
v
v )
6. Teha punktis 2 saadud MDNK-le Shannoni disjunktiivne arendus selle muutuja (muutujate)
järgi, mida esineb MDNK-s kõige rohkem.
Muutuja
x1
x2
x3
x4
Sagedus
2
2
3
1
MDNK: f(, , , ) =
v
v
v
Muutujate esinemissagedus:
Shannoni disjunktiivne arendus
järgi:
f(, , , ) = & f(, , 0, ) v =
= () v ( v
v
v )
7. Teha punktis 2 saadud MDNK-le Shannoni disjunktiivne arendus vabaltvalitud 2he muutuja järgi.
MDNK: f(, , , ) =
v
v
v
Shannoni disjunktiivne arendus
ja
järgi:
f(, , , ) =
& f (0, 0, x3, x4) v
& f (0, 1, x3, x4) v
v
& f (1, 0, x3, x4) v
& f (1, 1, x3, x4) =
() v ( v ) v () v () =
( v v) v ( v
v ) v () v ()
8. Teha punktis 2 saadud MDNK-le Shannoni konjunktiivne arendus vabaltvalitud 2he muutuja järgi.
MDNK: f(, , , ) =
v
v
v
Shannoni konjuktiivne arendus
ja
järgi:
f(, , , ) = ( v
v f (1, 1, x3, x4))( v v f (1, 0, x3, x4)) &
& ( v
v f (0, 1, x3, x4))( v
v f (0, 0, x3, x4)) =
= ( v
v ())( v v ())( v
v ( v ))( v
v ())
9. Leida ja esitada punktis 2 saadud MDNK-ga loogiliselt võrdne Reed -Mulleri polünoom.
MDNK: f(, , , ) =
v
v
v
Reed-Mulleri polünoomi saab Karnaugh’ kaardilt mittekattuvate kontuuridega kaetud 1-de piirkondade välja kirjutamisel ja saadud DNKs kõik disjunktsioonid -ga asendades (ning silmas pidades seda, et
= x ).
x3x4
x1x2
00
01
11
10
00
1
1
1
1
01
1
0
1
1
11
0
0
1
1
10
1
1
0
0
Saadud DNK:
f(, , , ) =
v
v
v
Reed-Mulleri polünoom:
f(, , , ) =