Diskreetse matemaatika kodutöö 2009 (0)

Tallinna Tehnikaülikool
Diskreetne matemaatika
KODUTÖÖ
Kristjan Keskküla
093540
IASB
Tallinn 2009
ÜLESANNE 1
Leida oma martiklinumbrile vastav 4- muutuja loogikafunktsioon
f(x1, x2, x3, x4) =
(järgnevalt kui funktsioon)
ÜLESANNE 2
Leida MDNK ja MKNK, mis sobiksid martiklinumbrist leitud osaliselt määratud 4-muutuja funktsiooni esitamiseks
Kuna minu martiklinumber on paarisarvuline leian:
MKNK Karnaugh ’ kaardiga ja MDNK McCluskey’ meetodiga.
1) Leian MKNK Karnaugh’ kaardiga
M 01
00
11
10
KNK leidmiseks joonestan Karnaugh’ kaardi, kuhu kannan peale funktsiooni 1d, 0d ja määramatused.
x3x4
x1x2
0 01
00
10
0
0
1
1
0
0
0 11
1
1
1
1
0
Tegu on osaliselt määratud funktsiooniga. Osaliselt määratud funktsiooni korral võime määramatuse asemele vabalt valida kas 0 või 1.
Kuna minimaalne konjuktiivkuju leitakse 0-de piirkonna kaudu, siis valin vastavad kontuurid.
(4)
(3)
(2)
(1)
01
00
11
10
01
00
11
10
Saan 4 kontuuri, mille järgi saame leida intervallid (1), (2), (3) ja (4). Intervallides leiame konstantsed muutujad.
(1) intervalli (000-) konstantsed muutujad – x1 = 0, x2 = 0, x3 = 0
Sellest saame MKNK jaoks x1Vx2Vx3
(2) intervalli (0--1) konstantsed muutujad - x1 = 0, x4 = 1
Sellest saame MKNK jaoks x1V
(3) intervalli (110-) konstantsed muutujad - x1 = 1, x2 = 1, x3 = 0
Sellest saame MKNK jaoks VVx3
(4) intervalli (101-) konstantsed muutujad - x1 = 1, x2 = 0, x3 = 1
Sellest saame MKNK jaoks V x2V
MKNK - f(x1, x2, x3, x4) = (x1Vx2Vx3)&( x1V)&(VVx3)&( V x2V)
2) Leian MDNK McCluskey’ meetodiga
MDNK leidmiseks leian funktsiooni 1de elementide kahendvektorid ja paigutan need indeksi (1de arv kahendvektoris) põhjal tabelisse. MDNK saaamiseks lähtun funktsiooni 1de piirkonnast . Määramatused märgin tärniga (*). Välja jätan vahed , mis ei vasta 2- astmele . (2n)
Leian lihtimplikandid ehk sellised intervallid, mida ei ole suurimas implikantide intervallis. Tähistan implikandid A tähega.
Indeks
1-de pk.
2-sed intervallid
Vahe
4-sed intervallid
Vahe
1
2
4
8
2-6* A6
4-6 A5
8-9 A4
4
2
1
9-11*-13*-15
9-13*-11*-15
2,4 A1
4,2 A1
2
6*
9
6*-14 A3
9-11*
9-13*
8
2
4
3
11*
13*
14
11*-15
13*-15
14-15 A2
4
2
1
4
15
Tabelist saame 6 lihtimplikanti. Kanname lihtimplikandid lihtimplikantide tabelisse.
Lihtimplikandid
2
4
6*
8
9
11*
13*
14
15
A1
1
1
1
1
A2
1
1
A3
1
1
A4
1
1
A5
1
1
A6
1
1
Katan ilma tärnita veerud (1de piirkonna) vähemalt ühe valitud reaga (lihtimplikandiga). Määramatused võib katmisel välja jätta.
Valin A2, A4, A5, A6. Minimaalne disjunktsioonkuju tuleb 4-ja elementaarkonjuktsiooniga.
f = A2 V A4 V A5 V A6
Võtan lihtimplikantide koosseisust suvalise argumentvektori ja loobun 2ndarvu nendest järkudest, mille kaal võrdub vahega.
Lihtimplikandid
Valitud
10nd arv
x1
x2
x3
x4
Alles jääb
A2
15
1
1
1
1
x1x2x3
A4
9
1
0
0
1
x1
A5
4
0
1
0
0
x2
A6
2
0
0
1
0
x3
MDNK - f(x1,x2,x3,x4) = x1x2x3Vx1Vx2Vx3
ÜLESANNE 3
T 1
3
2
eisendada ülesandes 2 leitud MKNK loogikaalgebra põhiseaduste abil DNK- kujule . Võrrelda saadud DNK-d ülesandes 2 leitud MDNK-ga
( neeldumine
distributiivsus
x1V)&(x1Vx2Vx3)&(VVx3)&( V x2V) = x1Vx1x2x3Vx3Vx2x3Vx2
1. (x1V)&(x1Vx2Vx3) = x1Vx1x2Vx1 x3Vx1Vx2Vx3 =
x1V x1Vx1x3Vx2Vx3= x1Vx2Vx3
vastuolu seadus
2. (x1Vx2Vx3)&(VVx3) = x1Vx1Vx1x3Vx2V x2 x3V x3V x3= x1Vx1x3Vx2Vx3
3. (x1Vx1x3Vx2Vx3)(V x2V) = x1V x1x2x3V x3Vx2x3Vx2Vx2= x1V x1x2x3V x3Vx2x3Vx2
Karnaugh’ kaardiga saadud MDNK f = x1x2x3Vx1Vx2Vx3
MKNK-st teisendatud MDNK f1 = x1V x1x2x3Vx3Vx2x3Vx2
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
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 01
00
11
10
) Leian taandatud DNK
Kannan Karnaugh’ kaardile funktsiooni elemendid ning väärtustan määramatused 1-ga. Taandatud disjunktiivkuju leidmiseks peavad kõik 1de kontuurid olema üksteisega ühendatud.
x3x4
x1x2
0 01
00
11
10
0
0
1
1
0
0
1
0
1
1
1
1
1
1
0
Karnaugh’ kaardile on kantud on 6 intervalli. Leian konstandid. Arvestan seejuures, et DNK sõltub 1de piirkonnast.
Intervallidel:
100- x1
1--1 x1x4
111- x1x2x3
-110 x2x3
10-0 x2
0-10 x3
Taandatud DNK
f = x1x4 V x1x2x3 V x1 V x2x3 V x2 V x3
2) Leian TDNK (täielik DNK)
Täieliku DNK korral on igas funktsiooni liikmes kõik funktsiooni muutujad esitatud. Täieliku DNK leidmiseks MDNK-st kasutan kleepimisseaduseid – st. kleebin puuduva muutuja liikmele.
f = x1x2x3Vx1Vx2Vx3 = x1V x1x4 V x1x2x3V x1x2x3x4 Vx2Vx2x3Vx3Vx2x3
ÜLESANNE 5
Leida vabaltvalitul viisil punktis 2 saadud MKNK-ga loogiliselt võrdne Täielik KNK
(x1Vx2Vx3)&( x1V)&(VVx3)&( V x2V) = (x1Vx2Vx3Vx4)&
&(x1Vx2Vx3V)&(VVx3Vx4)&(VVx3V)&(V x2VVx4)
&(V x2VV)&(x1VVx3)&(x1VV) = (x1Vx2Vx3Vx4)&
&(x1Vx2Vx3V)&(VVx3Vx4)&(VVx3V)&(V x2VVx4) &
&(V x2VV)&(x1Vx2V x3V)& (x1VVx3V)&(x1Vx2VV)
&(x1VVV)
TKNK
f(x1,x2,x3,x4) = (x1Vx2Vx3Vx4)&(x1Vx2Vx3V)&(VVx3Vx4)&(VVx3V)
&(V x2VVx4)&(V x2VV)&(x1Vx2V x3V)& (x1VVx3V)
&(x1Vx2VV)&(x1VVV)
ÜLESANNE 6
Teha punktis 2 saadud MDNK-le Shannoni disjunktiivne arendus muutuja xi järgi, mida esineb MDNK-s kõige rohkem
MDNK f = x1x2x3Vx1Vx2Vx3
Kõige rohkem esineb MDNK-s x1 muutujat. Teen Shannoni disjunktiivse arenduse x1 järgi.
f = x1x2x3Vx1Vx2Vx3=  f(0  x2x3V0 × V1 × x2V1 × x3) V
x1 × f(1  x2x3V1 × V0 × x2V0 × x3) =  f(x3Vx2) V x1 × f(V x2x3)
ÜLESANNE 7
Teha punktis 2 saadud MDNK-le Shannoni disjunktiivne arendus vabaltvalitud 2he muutuja järgi.
MDNK f = x1x2x3Vx1Vx2Vx3
Valin muutujad x3 ja x4. Teen Shannoni disjunktiivse arenduse x3x4 järgi.
f = x3x4 × f(1 × x1x2 V 0 × x2 V 0 × x1 V 0 × 1 × ) V x3 × f(1 × x1x2 V 0 × x1V 1 × x2 V 1 × 1 × ) V x4 × f(0× x1x2 V 1 × x1V 0 × x2 V 0 × 0 × ) V
× f(0× x1x2 V 1 × x1V 1 × x2 V 0 × 1 × ) =
x3x4(x1x2) V x3( x1x2 V x2 V ) Vx4(x1) V ( x1V x2)
ÜLESANNE 8
Teha punktis 2 saadud MDNK-le Shannoni konjunktiivne arendus vabaltvalitud 2he muutuja järgi
MDNK f = x1x2x3Vx1Vx2Vx3
Valin muutujateks x3 ja x4. Teen konjuktiivse shannoni arenduse x3x4 järgi.
f = [x3 V x4 V (1 × x1x2 V 0 × x2 V 0 × x1 V 0 × 1 × )]&
&[x3 V V (1 × x1x2 V 0 × x1V 1 × x2 V 1 × 1 × )]&[V x4 V (0× x1x2 V 1 × x1V 0 × x2 V 0 × 0 × )] & [ V
V (0× x1x2 V 1 × x1V 1 × x2 V 0 × 1 × )] =
(x3V x4V x1x2) &(x3VV x1x2 V x2 V )&( V x4 V x1)&(VV x1Vx2)
ÜLESANNE 9
Leida ja esitatada punktis 2 saadud MDNK-ga loogiliselt võrdne Reed-Mulleri polünoom.
Reed-Mulleri polünoomi leidmiseks kasutan Karnaugh’ kaarti . Karnaugh’ kaardi täitmiseks kasutan samasid andmeid, kui MDNK leidmiseks. (määran määramatused võrdselt).
01
00
11
10
x3x4
x1x2
0 01
00
11
10
0
0
1
1
0
0
1
0
0
1
1
1
1
0
0
Leian konstandid.
1) Intervall 100- konstandid x1=1 x2=0 x3=0
x1
2) Intervall 111- konstandid x1=1 x2=1 x3=1
x1x2x3
3) Intervall 01-0 konstadid x1=0 x2=1 x4=0
x2
4) Intervall 0010 konstandid x1=0 x2=0 x3=1 x4=0
x3
Asendadame disjunktsioonid  (moodul 2 summa) ja inversioonid Å + 1-ga . Võime asendada disjunktsioonid, kuna kõik „1”-d on katetud paaritu arvu kontuuridega.
x1 V x1x2x3 V x2
V x3 = x1 Å x1x2x3 Å x2
Å x3 =
x1(x2 Å 1)(x3 Å 1) Å x1x2x3 Å (x1 Å 1)x2(x4 Å 1) Å (x2 Å 1) (x2 Å 1)x3(x2 Å 1) =
(x1x2 Å x1) (x3 Å 1) Å x1x2x3 Å (x1x2 Å x2) (x4 Å 1) Å (x1x3 Å x3) (x2 Å 1) (x4 Å 1) =
x1x2x3 Å x1x2 Å x1x3 Å x1 Å x1x2x3 Å x1x2x4 Å x1x2 Å x2x4 Å x2 Å (x1x2x3 Å x1x3 Å x2x3 Å x3) (x4 Å 1) = x1x2x3x4 Å x1x2x3 Å x1x3x4 Å x2x3x4 Å x2x3 Å x3x4 Å x1x2x4 Å x2x4 Å x1 Å x2 Å x3