Diskreetne matemaatika 1. Kodutöö (0)

Tallinna Tehnikaülikool
Diskreetne Matemaatika
KODUTÖÖ
***
15****IAPB
******
Detsember 2015
1. Minu matriklinumbrile (155423) vastav loogikafunktsioon oma numbrilises 10nd esituses:
f(x1, x2, x3, x4) = ∑ (2, 3, 7, 8, 9, 13)1 (1, 4, 5, 14, 15)_
2. Esitada oma loogikafunktsiooni tõeväärtustabel:
x1 x2 x3 x4
f
0 0 0 0
0
0 0 0 1

• 
  

0 0 1 0
1
0 0 1 1
1
0 1 0 0
0 1 0 1
0 1 1 0
0
0 1 1 1
1
1 0 0 0
1
1 0 0 1
1
1 0 1 0
0
1 0 1 1
0
1 1 0 0
0
1 1 0 1
1
1 1 1 0

• 
  

1 1 1 1
3. Leida MDNK (McClusky meetodil) ja MKNK (Karnaugh’ kaardiga ); tuvastada, kas leitud MDNK ja MKNK on teineteisega loogiliselt võrdsed või mitte.
MKNK leidmine:
MKNK: f(x1x2 x3x4) = (x1 V x3) ( x͞2 V x4) (x͞1 V x2 V x͞3)
MDNK leidmine:
Leian laiendatud 1-de piirkonna: ∑ (1*, 2, 3, 4*, 5*, 7, 8, 9, 13, 14*, 15*)1
Indeks
Laiendatud 1-de piirk.
M
2-sed intervallid
M
4-sed intervallid
M
1
0001*
0010
0100*
1000
X
X
X
X
00 – 1
0 – 01
– 011
001 –
010 –
100 –
X
X
X
A1
A2
A3
0 – – 1
– – 01
A5
A6
– 1 –1
A7
2
0011
0101*
1001
X
X
X
3
0111
1101
1110*
X
X
X
0 – 11
01 – 1
– 101
1 – 01
X
X
X
X
4
1111 *
X
– 111
11 – 1
111 –
X
X
A4
Koostan katmistabeli ja valin minimaalse arvu ridu (märgitud kollasega), mis koos katavad märgenditega kõik ilma tärnita veerud :
1*
0001
2
0010
3
0011
4*
0100
5*
0101
7
0111
8
1000
9
1001
13
1101
14*
1110
15*
1111
A1
X
X
A2
X
X
A3
X
X
A4
X
X
A5
X
X
X
X
A6
X
X
X
X
A7
X
X
X
X
f(x1x2 x3x4) = A1 v A2 v A7
MDNK: f(x1x2 x3x4) = x͞1 x͞2 x3 V x1 x͞2 x͞3 V x2 x4
MDNK ja MKNK pole omavahel loogiliselt võrdsed, sest määramatuspiirkonna tõttu on nende tõeväärtustabelid erinevad (MDNK puhul on ka määramatuspiirkond arvestatud 1-de piirkonda).
4. Teisendada punktis 3 leitud MKNK loogikaalgebra põhiseaduste abil DNK- kujule (ehk korrutada MKNK avaldises "sulud lahti" ja lihtsustada tekkiv DNK käsitsi). Võrrelda, kas saadud DNK ja MDNK langevad kokku.
f(x1x2 x3x4) = (x1 V x3) ( x͞2 V x4) (x͞1 V x2 V x͞3) = (x1x͞2 V x1x4 V x͞2 x3 V x3x4)(x͞1 V x2 V x͞3) =
= x͞1 x͞2 x3 V x͞1 x3x4 V x1x2x4 V x2x3x4 V x1x͞2 x͞3 V x1x͞3 x4
Leitud DNK ei lange kokku MDNK-ga. Kontrollin, kas nad on omavahel loogiliselt võrdsed – arvutan mõlemale tõeväärtustabelid:
x1 x2 x3 x4
fMDNK
fDNK
0 0 0 0
0
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
1
0
0 1 1 0
0
0
0 1 1 1
1
1
1 0 0 0
1
1
1 0 0 1
1
1
1 0 1 0
0
0
1 0 1 1
0
0
1 1 0 0
0
0
1 1 0 1
1
1
1 1 1 0
0
0
1 1 1 1
1
1
Avaldised pole ka loogiliselt võrdsed, sest nende tõeväärtustabelid ei ole täpselt samad. MDNK haarab suurema kontuuri moodustamise tõttu ühe määramatusepiirkonnas oleva vektori rohkem 1-de piirkonda, kui leitud DNK, mis koosneb ainult kahevektorilistest intervallidest.
5. Leida MDNK-ga loogiliselt võrdne Taandatud DNK ja Täielik DNK, näidates/selgitades mõlema jaoks ära ka nende leidmisviisi.
Täieliku DNK leidmine:
Kasutan kleepimisseadust: x1 = x1x͞2 V x1x2
f(x1x2 x3x4) = x͞1 x͞2 x3 V x1 x͞2 x͞3 V x2 x4 = x͞1 x͞2 x3x4 V x͞1 x͞2 x3x͞4 V x1x͞2 x͞3x4 V x1x͞2 x͞3 x͞4 V
V x1x2x4 V x͞1 x2 x4 =
= x͞1 x͞2 x3x4 V x͞1 x͞2 x3x͞4 V x1x͞2 x͞3x4 V x1x͞2 x͞3 x͞4 V x1x2 x3x4 V x1x2 x͞3 x4 V x͞1 x2 x3x4 V x͞1 x2 x͞3 x4
Taandatud DNK leidmine:
Selle leidmiseks koostan MDNK Karnaugh’ kaardi, millel märgin ära kõik lihtimplikandid, mis tervikuna ei sisaldu üheski teises ( mustaga märgitud MDNK lihtimplikandid ja punasega lisaks TaDNK jaoks vajalikud lihtimplikandid)
TaDNK: f(x1x2 x3x4) = x͞1 x͞2 x3 V x1x͞2 x͞3 V x2x4 V x͞1 x3x4 V x1x͞3 x4
6. Leida vabalt valitud viisil MKNK-ga võrdne Täielik KNK.
Selleks vaatan MKNK Karnaugh’ kaarti ja kirjutan 0-de piiskonna argumentvektorite järgi välja nende elementaardisjunktsioonid ja korrutan need JA- tehtega kokku KNK-ks:
TKNK: f(x1x2 x3x4) = (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)(x1 V V x͞2 V x͞3 V x4)(x͞1 V x͞2 V x3 V x4)(x͞1 V x͞2 V x͞3 V x4)(x͞1 V x2 V x͞3 V x͞4)(x͞1 V x2 V x͞3 V x4)
7. Teha MDNK-le Shannoni disjunktiivne arendus selle muutuja (te) järgi, mis esineb MDNK-s kõige rohkem => x2 järgi.
MDNK: f(x1x2 x3x4) = x͞1 x͞2 x3 V x1 x͞2 x͞3 V x2 x4
Shannoni disjunktiivne arendus: f(x1x2 x3x4) = x͞2∙f(x10 x3x4) V x2∙f(x11 x3x4) =
= x͞2 (x͞1 ∙1∙x3 V x1∙1∙x͞3 V 0∙x4) ∙ x2(x͞1 ∙0∙x3 V x1∙0∙x͞3 V 1∙x4) = x͞2 (x͞1 x3 V x1x͞3) ∙ x2(x4)
8. Teha MDNKle Shannoni disjunktiivne arendus 2he vabalt valitud muutuja järgi: x2x3 järgi.
MDNK: f(x1x2 x3x4) = x͞1 x͞2 x3 V x1 x͞2 x͞3 V x2 x4
f(x1x2 x3x4) = x2 x3(x111x4) x2 x͞3(x110x4) x͞2 x3(x101x4) x͞2 x͞3 (x100x4) =
= x2 x3(x͞1 ∙0∙1 V x1∙0∙0 V 1∙x4) ∙ x2 x͞3(x͞1 ∙0∙0 V x1∙0∙1 V 1∙x4) ∙ x͞2 x3(x͞1 ∙1∙1 V x1∙1∙0 V 0∙x4) ∙
∙ x͞2 x͞3(x͞1 ∙1∙0 V x1∙1∙1 V 0∙x4) = x2 x3(x4) ∙ x2 x͞3(x4) ∙ x͞2 x3(x͞1) ∙ x͞2 x͞3(x1)
9. Teha MDNK-le konjunktiivne Shannoni arendus vabalt valitud kahe muutuja järgi: x2 x3 järgi.
MDNK: f(x1x2 x3x4) = x͞1 x͞2 x3 V x1 x͞2 x͞3 V x2 x4
f(x1x2 x3x4) = [x2 V x3 V f(x100x4)] [x͞2 V x3 V f(x110x4)] [x2 V x͞3 V f(x101x4)] [x͞2 V x͞3 V f(x111x4)] =
= (x2 V x3 V x͞1∙1∙0 V x1∙1∙1 V 0∙x4) (x͞2 V x3 V x͞1∙0∙0 V x1∙0∙1 V 1∙x4) (x2 V x͞3 V x͞1∙1∙1 V x1∙1∙0 V
0∙x4) (x͞2 V x͞3 V x͞1∙0∙1 V x1∙0∙0 V 1∙x4) = (x2 V x3 V (x1)) (x͞2 V x3 V(x4)) (x2 V x͞3 V( x͞1 )) (x͞2 V x͞3 V (x4))
10. Leida MDNK-le tuletised muutujate x1, x2, x3 ja x4 järgi. Lihtsustada avaldis DNK-ks loogikaalgebra põhiseoste abil.
MDNK: f(x1x2 x3x4) = x͞1 x͞2 x3 V x1 x͞2 x͞3 V x2 x4
Muutuja x1 järgi:
= (x͞2 x3 V x2x4) ⊕ (x͞2 x͞3 V x2x4) =
(x͞2 x͞3 V x2x4) V (x͞2 x3 V x2x4)=
= [(x2 V x͞3 )(x͞2 V x͞4)] (x͞2 x͞3 V x2x4) V (x͞2 x3 V x2x4) [(x2 V x3)(x͞2 V x͞4)] =
= (x2x͞4 V x͞2x͞3 V x͞3x͞4) (x͞2 x͞3 V x2x4) V (x͞2 x3 V x2x4)(x2x͞4 V x͞2x3 V x3x͞4) =
= x͞2x͞3 V x͞2x͞3x͞4 V x͞2x3 V x͞2x3x͞4 = x͞2x͞3 V x͞2x3 = x͞2
Muutuja x2 järgi:
= (x1x3 V x1x3) ⊕ (x4) = (x͞4) (x͞1x3 V x1x͞3) V (x4)=
= (x͞4) (x͞1x3 V x1x͞3) V (x4)[(x1 V x͞3)(x͞1 V x3)] = x͞1x3x͞4 V x1x͞3x͞4V x1x3x4 V x͞1x͞3x4
Muutuja x3 järgi:
= (x͞1x͞2 V x2x4) ⊕ (x1x͞2 V x2x4) =
= (x1x͞2 V x2x4) V (x͞1x͞2 V x2x4) =
= [(x1 V x2)(x͞2 V x͞4)]( x1x͞2 V x2x4) V (x͞1x͞2 V x2x4) [(x͞1 V x2)(x͞2 V x͞4)] =
= x1x͞2 V x1x͞2x͞4 Vx͞1x͞2 V x͞1x͞2x͞4 = x1x͞2 V x͞1x͞2 = x͞2
Muutuja x4 järgi:
= (x͞1x͞2x3 V x1x͞2x͞3 V x2) ⊕ (x͞1x͞2x3 V x1x͞2x͞3) =
= (x͞1 x͞2x3 V x1x͞2 x͞3) V (x͞1 x͞2x3 V x1x͞2x͞3 V x2)=
= [(x1 V x2 V x͞3)(x͞1 V x2 V x3)(x͞2)](x͞1 x͞2x3 V x1x͞2 x͞3) V (x͞1 x͞2x3 V x1x͞2 x͞3)[(x1 V x2 V x͞3)(x͞1 V x2 V x3)]=
= (x1x͞2x3 V x͞1 x͞2 x͞3)(x͞1 x͞2x3 V x1x͞2 x͞3) V (x͞1 x͞2x3 V x1x͞2 x͞3)(x1x2 V x1x3 V x͞1x2 V x2x3 V x͞1 x͞3 V x2x͞3) =
= x1x͞2x3 V x1x2 V x1x2x3 V x͞1x2 V x2x3 V x͞1x2x͞3 V x2x͞3 = x1x3 V x2
11. Leida MDNK-ga loogiliselt võrdne Reed -Mulleri polünoom vabalt valitud meetodiga.
Leian Reed-Mulleri polünoomi Karnaugh kaardi abil. MDNK Karnaugh’ kaart:
1de piirkond on juba kaetud minimaalse arvu võimalikult suurte kontuuridega, niimoodi et iga „1“ on kaetud paaritu arvu kontuuridega. Seega kehtib võrdus: 0 V 0 V 1 = 0 ⊕ 0 ⊕ 1. Järelikult:
f(x1x2 x3x4) = x͞1 x͞2 x3 ⊕ x1 x͞2 x͞3 ⊕ x2 x4 = (x1 ⊕ 1)(x2 ⊕ 1)x3 ⊕ x1(x2 ⊕ 1)(x3 ⊕ 1) ⊕ x2x4 =
= x1x2x3 ⊕ x1x3 ⊕ x2x3 ⊕ x3 ⊕ x1x2x3 ⊕ x1x2 ⊕ x1x3 ⊕ x1 ⊕ x2x4 =
= x2x3 ⊕ x3 ⊕ x1x2 ⊕ x1 ⊕ x2x4