DISKMAT KODUTÖÖ 2015 (0)

Tallinna Tehnikaülikool
Diskreetne Matemaatika
KODUTÖÖ
142438
Sisukord

1)Martiklinumbrile vastav 4- muutuja loogikafunktsioon 3
2) Tõeväärtustabel 3
3)MDNK ja MKNK, mis sobiksid martiklinumbrist leitud osaliselt määratud 4- muutuja funktsiooni esitamiseks 3
4. Teisenda MKNK DNK kujule . 5
5. Leida vabaltvalitud viisil MDNK-ga loogiliselt võrdne Taandatud DNK ja Täielik DNK. 6
6.MKNK-ga võrdne Täielik KNK 7
7. Shannoni disjunktiivne arendus rohkeima muutuja järgi. 8
8. Shannoni disjunktiivne arendus 1 muutuja järgi. 8
9.Shannoni konjuktiivne arendus MDNK-le 2 muutuja järgi. 8
10. Tuletis kõigi nelja muutuja järgi. 8
10.1.x1 järgi: 9
10.2.x2 järgi: 9
10.3.x3 järgi: 9
10.4.x4 järgi: 9
11.MDNK Reed -Mulleri polünoom . 9

1)Martiklinumbrile vastav 4-muutuja loogikafunktsioon

142438  22C66  F36CA  6A7F86  2E97CAA  146268A6 8EB0DC8A  3E6D607C6
2E97CAA  (2,14,9,7,12,10,10)  (2,7,9,10,12,14) 
3E6D607C6  (3,14,6,13,6,0,7,12,6)  (0,3,6,13)
 (2,7,9,10,12,14) (0,3,6,13)  
f(x1…x4) = 

2)Tõeväärtustabel

f(x1…x4) = 
Tõeväärtustabel
x1
x2
x3
x4
f
0
0
0
0
0
0
0
1
0
0
0
1
0
1
0
0
1
1
0
1
0
0
0
0
1
0
1
0
0
1
1
0
0
1
1
1
1
1
0
0
0
0
1
0
0
1
1
1
0
1
0
1
1
0
1
1
0
1
1
0
0
1
1
1
0
1
1
1
1
0
1
1
1
1
1
0

3)MDNK ja MKNK, mis sobiksid martiklinumbrist leitud osaliselt määratud 4-muutuja funktsiooni esitamiseks

MDNK:
Karnaugh ’ kaart
x1x2\x3x4
00
01
11
10
00
0
1
01
0
0
1
11
1
0
1
10
0
1
0
1
MDNK  f = x̄1x̄2x̄4 v x̄1x3 v x1x2x̄4 v x1x̄3x4 v x3x̄4
McCluskey meetod
Indeks
Intervall
Indeks
Intervall
M
Indeks
Intervall
M
0
0000*
X
0-1
000-
0-00
-000
X
0-1-1-2
0-0-
A8
1
0001
0100
1000
X
X
1-2-2-3
X
A1
2-3-3-4
X
1-2
00-1
0-01
01-0
010-
A2
2
0011*
0110*
0101
X
X
X
A3
X
X
3
1011
1101 *
X
2-3
-011
-101
A4
X
A5
4
1111
x
3-4
1-11
11-1
A6
A7
1
4
5
8
11
15
A1
X
A2
X
A3
X
A4
X
A5
X
A6
X
X
A7
X
A8
X
X
X
A1 & A6 & A8
MKNK  f = (x1 v x3)(x2 v x3 v x4)(x̄1 v x̄3 v x̄4)
Koostan MDNK ja MKNK tõeväärtustabelid.
x1
x2
x3
x4
MDNK
MKNK
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
0
1
1
0
0
1
1
1
1
0
1
0
0
0
0
0
1
0
1
0
0
0
1
1
0
1
1
0
1
1
1
1
1
1
0
0
0
0
0
1
0
0
1
1
1
1
0
1
0
1
1
1
0
1
1
0
0
1
1
0
0
1
1
1
1
0
1
1
1
1
1
1
0
1
1
1
1
1
1
0
0
Tõeväärtustabelist selgub , et MDNK ja MKNK ei ole teineteisega loogiliselt võrdsed, sest funktsiooni minimeerimisel määrati nullide ja ühtede piirkonnad erinevalt.

4. Teisenda MKNK DNK kujule.

MKNK: f = (x1 v x3)(x2 v x3 v x4)(x̄1 v x̄3 v x̄4)
Teisendus DNK kujule:
f = (x1 v x3)(x2 v x3 v x4)(x̄1 v x̄3 v x̄4) = (x1x2 v x1x3 v x1x4 v x2x3 v x3x3 v x3x4)(x̄1 v x̄3 v x̄4) = x1x2x̄1 v x1x2x̄3 v x1x2x̄4 v x1x3x̄1 v x1x3x̄3 v x1x3x̄4 v x1x4x̄1 v x1x4x̄3 v x1x4x̄4 v x2x3x̄1 v x2x3x̄3 v x2x3x̄4 v x3x̄1 v x3x̄3 v x3x̄4 v x3x4x̄1 v x3x4x̄3 v x3x4x̄4 = x1x2x̄3 v x1x2x̄4 v x1x4x̄3 v x̄1x3 v x3x̄4
Saadud DNK: f = x1x2x̄3 v x1x2x̄4 v x1x4x̄3 v x̄1x3 v x3x̄4
Eelnevalt saadud MDNK: f = x̄1x̄2x̄4 v x̄1x3 v x1x2x̄4 v x1x̄3x4 v x3x̄4
Saadud DNK ei ole kokkulangev MDNK’ga:
Seega koostan tõeväärtustabeli.
x1
x2
x3
x4
MDNK
DNK
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
0
1
1
0
0
1
1
1
1
0
1
0
0
0
0
0
1
0
1
0
0
0
1
1
0
1
1
0
1
1
1
1
1
1
0
0
0
0
0
1
0
0
1
1
1
1
0
1
0
1
1
1
0
1
1
0
0
1
1
0
0
1
1
1
1
0
1
1
1
1
1
1
0
1
1
1
1
1
1
0
0
Tõeväärtustabelist selgub, et MDNK ja saadud DNK ei ole loogiliselt võrdsed.
DNK ja MDNK ei ole loogiliselt võrdsed, sest MKNK (millest teisendati DNK) nullide ja ühtede piirkond määrati MDNK omast erinevalt.

5. Leida vabaltvalitud viisil MDNK-ga loogiliselt võrdne Taandatud DNK ja Täielik DNK.

Leian
MDNK  f = x̄1x̄2x̄4 v x̄1x3 v x1x2x̄4 v x1x̄3x4 v x3x̄4
Koostan MDNK-st Karnaugh’ kaardi.
Karnaugh’ kaart
x1x2\x3x4
00
01
11
10
00
1
0
1
1
01
0
0
1
1
11
1
1
0
1
10
0
1
0
1
x1
x2
x3
x4
MDNK
0
0
0
0
1
0
0
0
1
0
0
0
1
0
1
0
0
1
1
1
0
1
0
0
0
0
1
0
1
0
0
1
1
0
1
0
1
1
1
1
1
0
0
0
0
1
0
0
1
1
1
0
1
0
1
1
0
1
1
0
1
1
0
0
1
1
1
0
1
1
1
1
1
0
1
1
1
1
1
0
Taandatud DNK (Karnaugh’ kaardi abil):
f = x̄1x̄2x̄4 v x̄1x3 v x1x2x̄4 v x1x̄3x4 v x3x̄4 v x1x2x̄3
Koostan tõeväärtustabeli abil täieliku DNK:
f = (x̄1 x̄2 x̄3 x̄4) v (x̄1 x̄2 x3 x̄4) v (x̄1 x̄2 x3 x4) v (x̄1 x2 x3 x̄4) v (x̄1 x2 x3 x4) v (x1 x̄2 x̄3 x4) v (x1 x̄2 x3 x̄4) v (x1 x2 x̄3 x̄4) v (x1 x2 x̄3 x4) v (x1 x2 x3 x̄4)

6.MKNK-ga võrdne Täielik KNK

MKNK  f = (x1 v x3)(x2 v x3 v x4)(x̄1 v x̄3 v x̄4)
Koostan MKNK põhjal tõeväärtustabeli.
x1
x2
x3
x4
Output
0
0
0
0
0
0
0
0
1
0
0
0
1
0
1
0
0
1
1
1
0
1
0
0
0
0
1
0
1
0
0
1
1
0
1
0
1
1
1
1
1
0
0
0
0
1
0
0
1
1
1
0
1
0
1
1
0
1
1
0
1
1
0
0
1
1
1
0
1
1
1
1
1
0
1
1
1
1
1
0
Loon tõeväärtustabeli põhjal täieliku KNK:
f = (x1 v x2 v x3 v x4) (x1 v x2 v x3 v x̄4) (x1 v x̄2 v x3 v x4) (x1 v x̄2 v x3 v x̄4) (x̄1 v x2 v x3 v x4) (x̄1 v x2 v x̄3 v x̄4) (x̄1 v x̄2 v x̄3 v x̄4)

7.Shannoni disjunktiivne arendus rohkeima muutuja järgi.

MDNK: f = x̄1x̄2x̄4 v x̄1x3 v x1x2x̄4 v x1x̄3x4 v x3x̄4
Kõige rohkem esineb MDNK-s muutujaid x1 ja x4, mõlemaid 4 korda.
Koostan Shannoni disjunktiivse arenduse x1 ja x4 järgi.
f = x̄1x̄2x̄4 v x̄1x3 v x1x2x̄4 v x1x̄3x4 v x3x̄4 = x̄1x̄4(1x̄21 v 1x3 v 0x21 v 0x̄30 v x31) v x̄1x4(1x̄20 v 1x3 v 0x20 v 0x̄31 v x30) v x1x̄4(0x̄21 v 0x3 v 1x21 v 1x̄30 v x31) v x1x4(0x̄20 v 0x3 v 1x20 v 1x̄31 v x30) = x̄1x̄4(x̄2 v x3 v x3) v x̄1x4(x3) v x1x̄4(x2 v x3) v x1x4(x̄3) = x̄1x̄4(x̄2 v x3) v x̄1x4(x3) v x1x̄4(x2 v x3) v x1x4(x̄3)

8. Shannoni disjunktiivne arendus 1 muutuja järgi.

MDNK: f = x̄1x̄2x̄4 v x̄1x3 v x1x2x̄4 v x1x̄3x4 v x3x̄4
Kuna punktis 7, koostasin arenduse 2 muutuja järgi, koostan seekord arenduse 1 muutuja järgi, milleks valin muutuja x2.
f = x̄1x̄2x̄4 v x̄1x3 v x1x2x̄4 v x1x̄3x4 v x3x̄4 = x2(x̄10x̄4 v x̄1x3 v x11x̄4 v x1x̄3x4 v x3x̄4) v x̄2(x̄11x̄4 v x̄1x3 v x10x̄4 v x1x̄3x4 v x3x̄4) = x2(x̄1x3 v x1x̄4 v x1x̄3x4 v x3x̄4) v x̄2(x̄1x̄4 v x̄1x3 v x1x̄3x4 v x3x̄4)

9.Shannoni konjuktiivne arendus MDNK-le 2 muutuja järgi.

MDNK: f = x̄1x̄2x̄4 v x̄1x3 v x1x2x̄4 v x1x̄3x4 v x3x̄4
Valin muutujad x2 ja x3.
f = x̄1x̄2x̄4 v x̄1x3 v x1x2x̄4 v x1x̄3x4 v x3x̄4 = [x2 v x3 v (x̄11x̄4 v x̄10 v x10x̄4 v x11x4 v 0x̄)] [x2 v x̄3 v (x̄11x̄4 v x̄11 v x10x̄4 v x10x4 v 1x̄4)] [x̄2 v x3 v (x̄10x̄4 v x̄10 v x11x̄4 v x11x4 v 0x̄4)] [x̄2 v x̄3 v (x̄10x̄4 v x̄11 v x11x̄4 v x10x4 v 1x̄4)] = [x2 v x3 v (x̄1x̄4 v x1x4)] [x2 v x̄3 v (x̄1x̄4 v x̄1 v x̄4)] [x̄2 v x3 v (x1x̄4 v x1x4)] [x̄2 v x̄3 v (x̄1 v x1x̄4 v x̄4)] = [x2 v x3 v (x̄1x̄4 v x1x4)] [x2 v x̄3 v ( x̄1 v x̄4)] [x̄2 v x3 v (x1)] [x̄2 v x̄3 v (x̄1 v x̄4)]

10. Tuletis kõigi nelja muutuja järgi.

MDNK: f = x̄1x̄2x̄4 v x̄1x3 v x1x2x̄4 v x1x̄3x4 v x3x̄4

10.1.x1 järgi:

f = f(0,x2,x3,x4)  f(1,x2,x3,x4) = (1x̄2x̄4 v 1x3 v 0x2x̄4 v 0x̄3x4 v x3x̄4)  (0x̄2x̄4 v 0x3 v 1x2x̄4 v 1x̄3x4 v x3x̄4) = (x̄2x̄4 v x3 v x3x̄4)  (x2x̄4 v x̄3x4 v x3x̄4) = (x̄2x̄4 v x3)  (x2x̄4 v x̄3x4 v x3x̄4) = (x̄2x̄4 v x3) (x2x̄4 v x̄3x4 v x3x̄4) v (x̄2x̄4 v x3) (x2x̄4 v x̄3x4 v x3x̄4) = (x̄2x̄4 x3) (x2x̄4 v x̄3x4 v x3x̄4) v (x̄2x̄4 v x3) (x2x̄4 x̄3x4 x3x̄4) = ((x2 v x4) x3) (x2x̄4 v x̄3x4 v x3x̄4) v (x̄2x̄4 v x3) (x̄2 v x4) (x3 v x̄4) (x̄3 v x4) = x2x3x̄4 v (x̄2x̄4 v x̄2x3 v x3x4) (x3x4 v x̄3x̄4) = x2x3x̄4 v x̄2x̄3x̄4 v x3x4

10.2.x2 järgi:

f = f(x1,0,x3,x4)  f(x1,1,x3,x4) = (x̄11x̄4 v x̄1x3 v x10x̄4 v x1x̄3x4 v x3x̄4)  (x̄10x̄4 v x̄1x3 v x11x̄4 v x1x̄3x4 v x3x̄4) = (x̄1x̄4 v x̄1x3 v x1x̄3x4 v x3x̄4)  (x̄1x3 v x1x̄4 v x1x̄3x4 v x3x̄4) = (x̄1x̄4 v x̄1x3 v x1x̄3x4 v x3x̄4) (x̄1x3 v x1x̄4 v x1x̄3x4 v x3x̄4) v (x̄1x̄4 v x̄1x3 v x1x̄3x4 v x3x̄4) (x̄1x3 v x1x̄4 v x1x̄3x4 v x3x̄4) = (x̄1x̄4 x̄1x3 x1x̄3x4 x3x̄4) (x̄1x3 v x1x̄4 v x1x̄3x4 v x3x̄4) v (x̄1x̄4 v x̄1x3 v x1x̄3x4 v x3x̄4) (x̄1x3 x1x̄4 x1x̄3x4 x3x̄4) = ((x1 v x4) (x1 v x̄3) (x̄1 v x3 v x̄4) (x̄3 v x4)) (x̄1x3 v x1x̄4 v x1x̄3x4 v x3x̄4) v (x̄1x̄4 v x̄1x3 v x1x̄3x4 v x3x̄4) ((x1 v x̄3) (x̄1 v x4) (x̄1 v x3 v x̄4) (x̄3 v x4)) = ((x1 v x̄3x4)(x̄1x̄3 v x̄1x4 v x3x4 v x̄3x̄4))(x̄1x3 v x1x̄4 v x1x̄3x4 v x3x̄4) v (x̄1x̄4 v x̄1x3 v x1x̄3x4 v x3x̄4) ((x1x4 v x̄1x̄3 v x̄3x4)(x̄1x̄3 v x̄1x4 v x3x4 v x̄3x̄4)) = (x1x3x4 v x1x̄3x̄4 v x̄1x̄3x4)(x̄1x3 v x1x̄4 v x1x̄3x4 v x3x̄4) v (x̄1x̄4 v x̄1x3 v x1x̄3x4 v x3x̄4)(x1x3x4 v x̄1x̄3 v x̄1x̄3x4 v x̄1x̄3x̄4) = x1x̄3x̄4 v x̄1x̄3x̄4

10.3.x3 järgi:

f = f(x1,x2,0,x4)  f(x1,x2,1,x4) = (x̄1x̄2x̄4 v x̄10 v x1x2x̄4 v x11x4 v 0x̄4)  (x̄1x̄2x̄4 v x̄11 v x1x2x̄4 v x10x4 v 1x̄4) = (x̄1x̄2x̄4 v x1x2x̄4 v x1x4)  (x̄1x̄2x̄4 v x̄1 v x1x2x̄4 v x̄4) = (x̄1x̄2x̄4 v x1x2x̄4 v x1x4)  (x̄1 v x̄4) = (x̄1x̄2x̄4 v x1x2x̄4 v x1x4) (x̄1 v x̄4) v (x̄1x̄2x̄4 v x1x2x̄4 v x1x4) (x̄1 v x̄4) = ((x̄1x̄2x̄4) (x1x2x̄4) (x1x4)) (x̄1 v x̄4) v (x̄1x̄2x̄4 v x1x2x̄4 v x1x4) (x1x4) = ((x1 v x2 v x4) (x̄1 v x̄2 v x4) (x̄1 v x̄4)) (x̄1 v x̄4) v (x̄1x̄2x̄4 v x1x2x̄4 v x1x4) (x1x4) = (x1x̄2 v x̄1x2 v x4)(x̄1 v x̄4) v x1x4 = x1x̄2x̄4 v x̄1x2 v x̄1x2x̄4 v x̄1x4 v x1x4 = x1x̄2x̄4 v x̄1x2 v x̄1x4 v x1x4

10.4.x4 järgi:

f = f(x1,x2,x3,0)  f(x1,x2,x3,1) = (x̄1x̄21 v x̄1x3 v x1x21 v x1x̄30 v x31)  (x̄1x̄20 v x̄1x3 v x1x20 v x1x̄31 v x30) = (x̄1x̄2 v x̄1x3 v x1x2 v x3)  (x̄1x3 v x1x̄3) = (x̄1x̄2 v x1x2 v x3)  (x̄1x3 v x1x̄3) = (x̄1x̄2 v x1x2 v x3) (x̄1x3 v x1x̄3) v (x̄1x̄2 v x1x2 v x3) (x̄1x3 v x1x̄3) = ((x̄1x̄2) (x1x2) (x3)) (x̄1x3 v x1x̄3) v (x̄1x̄2 v x1x2 v x3) ((x̄1x3) (x1x̄3)) = ((x1 v x2) (x̄1 v x̄2) (x̄3)) (x̄1x3 v x1x̄3) v (x̄1x̄2 v x1x2 v x3) ((x1 v x̄3) (x̄1 v x3)) = ((x1x̄2 v x̄1x2) x̄3) (x̄1x3 v x1x̄3) v (x̄1x̄2 v x1x2 v x3) (x1x3 v x̄1x̄3) = (x1x̄2x̄3 v x̄1x2x̄3)(x̄1x3 v x1x̄3) v x̄1x̄2x̄3 v x1x2x3 v x1x3 = x1x̄2x̄3 v x̄1x̄2x̄3 v x1x3

11.MDNK Reed-Mulleri polünoom.

MDNK: f = x̄1x̄2x̄4 v x̄1x3 v x1x2x̄4 v x1x̄3x4 v x3x̄4
MDNK’ Karnaugh’ kaart
x1x2\x3x4
00
01
11
10
00
1
0
1
1
01
0
0
1
1
11
1
1
0
1
10
0
1
0
1
DNK: f = x̄1x̄2x̄3x̄4 v x̄1x3 v x1x2x̄3 v x1x̄2x̄3x4 v x1x3x̄4
Reed-Mulleri polünoom:
f = x̄1x̄2x̄3x̄4 v x̄1x3 v x1x2x̄3 v x1x̄2x̄3x4 v x1x3x̄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