) A10 0 1 0 0 (x₁ ˅ x₂ (x₂ ˅ x ₃ ˅ x ₄ ) ( x ₂˅ x ₃˅ x ₄ )(x₁ ) ˅ x₂ ) 3. Teisendada punktis 2 leitud MKNK loogikaalgebra põhiseaduste abil DNK-kujule. f ( x ₁, x ₂, x ₃, x ₄)=¿ (x₁ ˅ x ₃ ˅ x₄)(x₂ ˅ x ₃ ˅ x ₄ )( x ₂ ˅ x ₃ ˅ x ₄ )(x₁ ˅ x ₂ )= = ( x ₁ x ₂ v x ₁ x ₃ v x ₁ x ₄ v x ₂ x ₃ v x ₃ x ₃ v x ₃ x ₄ v x ₂ x ₄ v x ₃ x ₄ v x ₄ x ₄)( x ₁ x ₂ v x ₁ x ₃ v x ₁ x ₄ v x ₂ x ₂ v x ₂ x ₃ v x ₂ x = 4. Leida vabaltvalitud viisil punktis 2 saadud MDNK-ga (loogiliselt)
f(x1x2 x3x4) = A1 v A2 v A7 MDNK: f(x1x2 x3x4) = xx1 xx2 x3 V x1 xx2 xx3 V x2 x4 3 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) ( xx2 V x4) (xx1 V x2 V xx3) = (x1xx2 V x1x4 V xx2 x3 V x3x4) (xx1 V x2 V xx3) = = xx1 xx2 x3 V xx1 x3x4 V x1x2x4 V x2x3x4 V x1xx2 xx3 V x1xx3 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
Valitud Lihtimplikandid x x x x Alles jääb 10nd arv 1 2 3 4 A2 15 1 1 1 1 x1x2x3 A4 9 1 0 0 1 x1 x 2 x3 A5 4 0 1 0 0 x1 x2 x 4 A6 2 0 0 1 0 x1 x3 x 4 MDNK - f(x1,x2,x3,x4) = x1x2x3Vx1 x 2 x3 V x1 x2 x 4 V x1 x3 x 4 ÜLESANNE 3 Teisendada ülesandes 2 leitud MKNK loogikaalgebra põhiseaduste abil DNK-kujule. Võrrelda saadud DNK-d ülesandes 2 leitud MDNK-ga 1 2 3 (x1V x 4 )&(x1Vx2Vx3)&( x 1 V x 2 Vx3)&( x 1 V x2V x 3 ) = x1 x 2 x3 Vx1x2x3V x1 x3 x 4 Vx2x3 x 4 V x1 x2 x 4 distributiivsus neeldumine 1. (x1V x 4 )&(x1Vx2Vx3) = x1Vx1x2Vx1 x3Vx1 x 4 Vx2 x 4 Vx3 x 4 = x1V x1 x 4 Vx1x3Vx2 x 4 Vx3 x 4 = x1Vx2 x 4 Vx3 x 4 vastuolu seadus 2
funktsioonis olid määramatuspiirkonnad ning optimaalsete MDNK ja MKNK leidmiseks kasutasid kumbki määramatuspiirkondi erinevalt. (Erinevused esinevadki ainult algse funktsiooni määramatuspiirkondades) 4. ( x´ 1 V x´4 ¿ ( x´ 2 V x´4 ¿( x2 V x 3 )( x´1 V x´2 V x´3 ¿ = Kuna ei tulnud sarnane MDNK-le, võrdlen väärtusi Antud loogikaavaldise väärtused ei ole MDNK-ga võrdsed, kuna leitud DNK on formuleeritud MKNK-st, mis ei ole MDNK-ga loogiliselt võrdne. 5. Leian taandatud DNK. Taandatud DNK moodustavad kõik funktsiooni lihtimplikandid, maksimaalsed 1-de piirkonna intervallid. x´ 1 x´4 V x 2 x´3 V x´1 x´2 x 3 V x´ 2 x 3 x´4 Taandatud DNK osutus samaks, mis on MDNK, need on loogiliselt võrdsed. Leian täieliku DNK. Täielik DNK on funktsiooni ühtedeks avalduvate 2-
Küsimus 1 Õige - Hinne 1,00 / 1,00 kas väide on õige või vale: Jääkfunktsioone ei saa leida Karnaugh' kaardi abil Vali üks: Tõene Väär Küsimus 2 Osaliselt õige - Hinne 0,75 / 1,00 vali kõik õiged väited: Vali üks või enam: Funktsioonil võib Taandatud DNK puududa, kuigi minimaalne DNK (MDNK) on sellel funktsioonil olemas - VALE Taandatud DNK-d on võimalik leida Karnaugh' kaardi abil Taandatud DNK ja minimaalne DNK (MDNK) võivad olla üks ja sama avaldis Taandatud DNK võib olla suurema keerukusega avaldis kui minimaalne DNK (MDNK) Taandatud DNK on funktsiooni kõikide implikantide disjunktsioon - VALE Taandatud DNK on funktsiooni kõikide lihtimplikantide disjunktsioon Funktsioonil võib olla mitu erinevat Taandatud DNK-d - VALE Taandatud DNK võib olla väiksema keerukusega avaldis kui minimaalne DNK (MDNK) - VALE Küsimus 3 Õige - Hinne 3,00 / 3,00
McCluskey' meetod on rakendatav suvalise muutujate arvuga funktsioonide minimeerimiseks McCluskey' meetodi kleepimisreeglid on MDNK leidmisel ja MKNK leidmisel erinevad McCluskey' meetodiga ei saa leida loogikafunktsiooni Taandatud DNK-d Question 8 Osaliselt määratud loogikafunktsioonile MKNK leidmisel McCluskey' meetodiga lisatakse Correct määramatuspiirkond selle funktsiooni 0de piirkonnale mille tulemusel Mark 3 out of 3 saadakse laiendatud 0de piirkond
A1 2 0 1 - 0 x1 x4 A2 8 - 1 1 0 x4 A3 4 1 - 0 1 x3 A5 2,8 - 0 - 1 x2 f (x1,x2,x3,x4) = (x1 x4)( x4)( x3 )(x2 ) 3. Teisendada punktis 2 leitud MKNK loogikaalgebra põhiseaduste abil DNK- kujule (ehk korrutada MKNK avaldises "sulud lahti" ja lihtsustada tekkiv DNK käsitsi). Võrrelda selle teisenduse tulemuseks olevat DNK-d punktis 2 leitud MDNK-ga -- kas MKNK-st teisendatud DNK on avaldisena) kokkulangev selle MDNK-avaldisega, mille andis punktis 2 kasutatud minimeerimismeetod? (Karnaugh' kaart või McCluskey' meetod) (x1 x4)( x4)( x3 )(x2 ) = = (x1 x4) x2 x2 x3 ) = =
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 00 01 11 10 x1x2 00 1 1 1 1
A5 x x Valin MKNK jaoks A1, A2, A4 ja A5. Impl Vahe A1 - 0 0 0 0 A2 2 1 1 - 0 A4 1,4 1 - 1 - A5 4,8 - - 1 1 Kirjutan välja MKNK: 3. Teisendada punktis 2 leitud MKNK loogikaalgebra põhiseaduste abil DNK- kujule. V =V = V = V = V Seega saadud DNK on: V Karnaugh' kaardiga leitud MDNK: Võrdlen saadud DNK punktis 2 leitud DNK-ga. Tegemist ei ole kokkulangeva avaldisega. Arvutan mõlemale tõeväärtustabelid. x1 x2 x3 x4 f1 f2 0 0 0 0 0 0 0 0 0 1 1 1
.........................................................3 ÜLESANNE 3 MINIMAALSED NORMAALKUJUD........................................3 3.1 MDNK KARNAUGH’ KAARDIGA.......................................................................3 3.2 MKNK MCCLUSKEY MEETODIGA.....................................................................4 3.3 VÕRDLUS....................................................................................................... 5 ÜLESANNE 4 MKNK TEISENDAMINE DNK-KUJULE....................................5 ÜLESANNE 5 DISJUNKTIIVSED NORMAALKUJUD.....................................5 5.1 TAANDATUD DNK........................................................................................... 5 5.2 TÄIELIK DNK.................................................................................................. 6 ÜLESANNE 6 TÄIELIK KNK....................................................................6
Paaritu arv puhul jääb järele üks, nagu konstant 1 puhul. Milline on tulemus muutuja x ja tema inversiooni kokkuliitmisel tehtega summa mooduliga 2? tulemuseks on konstant 1 Millal võib DNKs asendada kõik disjunktsioonitehted tehetega summa mooduliga 2? Kui disjunktsioonitehte operandidest on väärtusega 1 paaritu arv operande, siis võib sellises avaldises asendada kõik disjunktsioonitehted tehtega + Kuidas saab mittetäieliku DNK või KNK teisendada täielikuks? Saab teisendada täielikuks kasutades kleepimisseaduseid. Vt näiteid lk 186, kleepimisseadused leiab loogikaalgebra põhiseaduste teema alt. Kumb normaalkuju DNK või KNK on praktikas olulisem? DNK on olulisem. Millise põhiseose abil saab DNK teisendada KNK-ks? Sulgude lahtiliitmise abil. Karnaugh kaardid: Mis on Karnaugh´ kaart? Karnaugh kaart on funktsiooni tõeväärtustabeli sihipärane topoloogiline ümberpaigutus tasandil või ruumis
Loogikafunktsiooni implikant Lihtimplikant Taandatud DNK Taandatud DNK (TaDNK) on funktsiooni kõikide lihtimplikantide disjunktsioon. Mõistel IMPLIKANT pole mingit seost loogikatehtega implikatsioon. Eelmise näitefunktsiooni Taandatud DNK esitub Karnaugh' kaardil : Ü Loogikafunktsiooni implikandiks nimetatakse tema 1-de piirkonna x 2 x3 T mistahes intervalli ( ehk tema igat "ühtede intervalli" ). x 1 00 01 11 10 T
Reed-Mulleri polünoomi võib leida kolmel viisil, millest kõige eelistatum on Karnaugh' kaardi abil leidmine. Koostatakse spetsiaalne DNK, kus kõik tehted w tohib avaldises lihtviisiliselt asendada tehtega (ilma avaldise loogilist väärtust sellega muutmata) Sellise omadusega DNK saamiseks tuleb kaardil kõik 1-d katta suurimate 1 1 0 1 1 0
1-11 X 111- X Katteülesande lahendamine: i 0 2 5 6 1 15 1 A1 X X A2 X X A3 X A4 X X X X Siit saan välja kirjutada kaks minimaalset disjunktiivset normaalkuju: f 1 = A1 A3 A4 = x1 x 2 x1 x 4 x3 f 2 = A2 A3 A4 = x 2 x 4 x1 x 4 x 3 3. Teisendada punktis 2 leitud MKNK loogikaalgebra põhiseaduste abil DNK-kujule. f ( x1 ; x 2 ; x3 ; x 4 ) = ( x 2 x3 x 4 ) ( x1 x3 ) = x1 x 2 x1 x3 x1 x 4 x 2 x3 x3 x3 x 4 = x1 x 2 x1 x 4 x3 Selle teisenduse tulemuseks olev DNK langeb kokku punktis 2 leitud MDNK-ga 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 saab välja kirjutada punktis 2 koostatud McCluskey' minimeerimismeetodist
A6 x x Lihtimplikant Vahed x1 x2 x3 x4 A1 2,4 0 - - 0 x1 x 4 A2 1 0 0 1 - x1 x 2 x 3 MKNK ( x1 x4 )( x1 x2 x3 ) 3. MKNK teisendamine DNK kujule loogika põhiseaduste abil ( x1 x4 )( x1 x2 x3 ) = = x1 x1 x2 x1 x3 x1 x4 x2 x4 x3 x4 = = x1 x1 x3 x1 x4 x2 x4 x3 x4 = = x1 x1 x4 x2 x4 x3 x4 = x1 x2 x4 x3 x4 Tõeväärtustabelite põhjal selgus, et MKNK ja DNK on loogiliselt võrdsed! 4. Taandatud ja täieliku DNK leidmine Taandatud DNK x3x4 x1x2 00 01 11 10 00 0 1 0 0
mis saadakse tõeväärtustabeli Vasta 0de piirkonnast Küsimus 2 Õige Hinne 1,00 / 1,00 Millised on loogikafunktsiooni võimalikud esitusviisid ? Vali üks või enam: loogikaavaldis numbriline kümnendesitus tõeväärtustabel osaline järjestussuhe Venni diagramm Hasse diagramm hulk Grassmani valem Küsimus 3 Õige Hinne 1,00 / 1,00 Täielik DNK on selline DNK, kus . . . Vali üks: . . . tõeväärtustabeli kõikidel ridadel on funktsiooni väärtus "1" . . . igas elementaarkonjunktsioonis on olemas kõik selle funktsiooni muutujad . . . avaldises on 2 astmel n elementaarkonjunktsiooni (2, 4, 8, 16, ...) Küsimus 4 Õige Hinne 1,00 / 1,00 kas see väide on õige või vale: ? Loogikafunktsioonil on alati üksainus minimaalne disjunktiivne normaalkuju (MDNK) Vali üks: Tõene Väär Küsimus 5 Õige Hinne 1,00 / 1,00
MKNK: (X1,X2,X3,X4)= A1 A4 Lihtimpl. Vahed X1 X2 X3 X4 Konjunktsioon A1 1.8 - 0 0 - X2 X3 A4 2.4 1 - - 0 X1 X 4 MKNK: (X1,X2,X3,X4)= A1 A4=( X 2 X 3 )( X 1 X 4 ) 3. Teisendada punktis 2 leitud MKNK loogikaalgebra põhiseaduste abil DNK-kujule MKNK: (X1,X2,X3,X4)= A1 A4=( X 2 X 3 )( X 1 X 4 ) X X X 2 X 4 X1 X 3 X 3 X 4 ( X 2 X 3 )( X 1 X 4 )= 1 2 Ei ole kokkulangev MDNK avaldisega. X1 X2 X3 X4 X1X 2 X 2 X 4 X1X 3 X 3 X 4 X 2 X 3 X 4 X1X 3 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1
Vastavat argumentvektorit? (For real, kuidas see erineb eelmisest loogika poolest?...) Mis on algterm? Algterm on avaldise koosseisu kuuluva loogikamuutuja või selle inversioon või konstant 0 1 Mis on elementaarkonjuktsioon? Mis on elementaardisjunktsioon? Elementaarkonjuktsioon on ükskik algterm või algtermide konjuktsioon. Nt x1x2x3,x1. Elementaardisjunktsioon on üksik algterm või algtermide disjunktsioon nt x1 v x2 v x3,x1 Mis on DNK? Mis on KNK? DNK on üksik elementaarkonjuktsioon või elementaarkonjuktsioonide disjunktsioon KNK on üksik elementaardisjunktsioon või elementaardisjunktsioonide konjuktsioon. Mis on TDNK? Mis on TKNK? TDNK on DNK, kus iga elementaarkonjuktsioon sisaldab funktsiooni kõiki muutujaid xi TKNK on KNK, kus iga elementaardisjunktsioon sisaldab funktsiooni kõiki muutujaid xi Mis on loogikaavaldise keerukus? Loogikaavaldise f keerukus L(f) on tema kooseisus olevate algtermide arv. Vt näidet lk 167 keskel.
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..........
.................................4 1.2Funktsiooni tõeväärtustabel...............................................................................4 1.3Tähistusi.............................................................................................................4 2. Ülesannete lahendamine..................................................................................5 2.2MKNK leidmine Karnaugh' kaardiga..................................................................6 2.3 Taandatud DNK leidmine..................................................................................6 2.4 Täieliku DNK leidmine...................................................................................... 6 2.5Täieliku KNK leidmine........................................................................................7 2.6 Shannoni disjunktiivne arendus muutujatele x2x3x4 ....................................... 8 Vastused.........................................................................
0 1 1 1 0 1 0 0 0 0 1 0 0 1 - 1 0 1 0 1 1 0 1 1 0 1 1 0 0 - 1 1 0 1 0 1 1 1 0 - 1 1 1 1 - 3. Leida Karnaugh' kaardiga MDNK (minimaalne DNK) ja MKNK (minimaalne KNK), mis sobiksid matriklinumbrist leitud osaliselt määratud 4-muutuja funktsiooni esitamiseks. 1. Leian MDNK: 00 01 11 10 x1 x3 x2 x4 00 0 - 1 1 01 1 - 0 - 11 - 0 - -
7 0 1 1 1 1 1 8 1 0 0 0 1 1 9 1 0 0 1 1 1 1 1 0 1 0 1 1 0 1 1 0 1 1 0 0 1 1 1 1 0 0 1 1 2 1 1 1 0 1 1 1 3 1 1 1 1 0 1 1 4 1 1 1 1 1 0 0 5 Vastus: MDNK ja MKNK on loogiliselt võrdsed, sest nende tõeväärtustabelid on võrdsed 4. Teisendada punktis 3 leitud MKNK loogikaalgebra põhiseaduste abil DNK- x x x x MDNK DNK 1 2 3 4 kujule 0 0 0 0 0 0 0 DNK: 1 0 0 0 1 1 1 2 0 0 1 0 0 0 f ( x 1 x 2 x3 x 4 ) =¿ ( x1 v x4 )( ´x 1 v 3 0 0 1 1 1 1 4 0 1 0 0 0 0 ´x 3 v ´x 4 ) = ( x 1 ´x 1 v x 1 ´x 3 v x 1 ´x 4 v 5 0 1 0 1 1 1 x 4 ´x1 v x 4 ´x3 v x 4 ´x 4 ) =
— ehk tuleb vajutada järjest =-märki veel paar korda, kuni 16ndarv kasvab 9- kohaliseks:........................................................................................................... 7 2. Kirjutada välja oma matriklinumbrist leitud osaliselt määratud 4-muutuja loogikafunktsiooni tõeväärtustabel.........................................................................8 3. Leida MDNK (minimaalne DNK) ja MKNK (minimaalne KNK), mis sobiksid matriklinumbrist leitud osaliselt määratud 4-muutuja funktsiooni esitamiseks......8 4. Kirjutada oma funktsiooni 1-de piirkonnast välja täielik DNK (TDNK) (ignoreerides määramatuspiirkonda)...................................................................10 5. Lihtsustada loogikaalgebra põhiseoste abil eelnevalt leitud täielikku DNK-d lihtsaima DNK-ni, milleks see TDNK lihtsustub.....................................................11 5
f ( x1 , x2 , x3 ) = x2 f ( x1 , x2 , x3 ) = f ( x1 , x2 , x3 ) Loogikafunktsioonide normaalkujud Loogikafunktsioon f(x1 , x2 ,..., xn ) võib olla esitatud erinevate valemite abil. 11 Näiteks f ( x1 , x2 ) = x1 x2 = x1 x2 x2 = ( x1 x2 x1 x2 x2 )( x2 x2 ) =............. · Loogikafunktsiooni kanoonilisi standardseid esitusvalemeid nimetatakse funktsiooni normaalkujudeks. · Disjunktiivne normaalkuju (DNK) on valem, mis koosneb elemantaarkonjunktsioonide disjunktsioonist. · Elemantaarkonjunktsioon koosneb argumentide ja/või nende inversioonide konjunktsioonist. · Konjunktiivne normaalkuju (KNK) on valem, mis koosneb elemantaardisjunktsioonide konjunktsioonist. · Elemantaardisjunktsioon koosneb argumentide ja/või nende inversioonide disjunktsioonist. · Iga funktsioon on esitatav DNK ja KNK kujul, kuid mitte üheselt.
f x1 , x2 , x3 x2 f x1 , x2 , x3 f x1 , x2 , x3 Loogikafunktsioonide normaalkujud Loogikafunktsioon f(x1 , x2 ,..., xn ) võib olla esitatud erinevate valemite abil. Näiteks f x1 , x2 x1 x2 x1 x2 x2 x1 x2 x1 x2 x2 x2 x2 ............. Loogikafunktsiooni kanoonilisi standardseid esitusvalemeid nimetatakse funktsiooni normaalkujudeks. Disjunktiivne normaalkuju (DNK) on valem, mis koosneb elemantaarkonjunktsioonide disjunktsioonist. Elemantaarkonjunktsioon koosneb argumentide ja/või nende inversioonide konjunktsioonist. Konjunktiivne normaalkuju (KNK) on valem, mis koosneb elemantaardisjunktsioonide konjunktsioonist. Elemantaardisjunktsioon koosneb argumentide ja/või nende inversioonide disjunktsioonist. Iga funktsioon on esitatav DNK ja KNK kujul, kuid mitte üheselt.
MDNK ja MKNK leidmised on teineteisest sõltumatud ja nad võib leida 10 1 0 0 1 10 1 0 0 1 ükskõik kumbas järjekorras. Leiame esimesena MDNK konstantsed muutujad 1-de kontuurile vastav ! DNK saadakse alati loogikafunktsiooni 1de piirkonnast ! vaadeldavas kontuuris elementaarkonjunktsioon Kontuuride valimise reeglid x 3 x4 x1 x 2 00 01 11 10 x 3 x4 x1 x 2 00 01 11 10 f ( x1 x2 x3 x4 ) = ¯1 x2 x3
sisesta lünka õige sõna: on üksik algterm või algtermide disjunktsioon. Elementaardisjunktsioon Küsimus 6 Õige - Hinne 1,00 / 1,00 sisesta õige vastus arvuna: Mitu rida on 4-muutuja loogikafunktsiooni tõeväärtustabelis? Vastus: 16 Küsimus 7 Õige - Hinne 1,00 / 1,00 Mitu 2-muutuja loogikafunktsiooni on olemas ? (sisesta õige arv) Vastus: 16 Küsimus 8 Õige - Hinne 1,00 / 1,00 Täielik DNK on selline DNK, kus . . . Vali üks: . . . tõeväärtustabeli kõikidel ridadel on funktsiooni väärtus "1" . . . igas elementaarkonjunktsioonis on olemas kõik selle funktsiooni muutujad . . . avaldises on 2 astmel n elementaarkonjunktsiooni (2, 4, 8, 16, ...) Küsimus 9 Õige - Hinne 1,00 / 1,00 kas see väide on õige või vale: ? Loogikafunktsioonil on alati üksainus minimaalne disjunktiivne normaalkuju (MDNK) Vali üks: Tõene Väär Küsimus 10 Õige - Hinne 1,00 / 1,00
= (x x 1 2 )( x1 x 4 x 2 x 4 x1 x 2 x1 x3 x 2 x3 = ) = x1 x 2 x1 x 2 x1 x 2 x1 x3 x1 x 2 x 2 x3 x1 x 4 x1 x 2 x1 x 4 x1 x3 x1 x 4 x 2 x3 x 2 x 4 x1 x 2 x 2 x 4 x1 x3 x 2 x 4 x 2 x3 = = x1 x 2 x 4 x1 x3 x 4 x1 x 2 x3 x 4 Põhimõtteliselt on võrdne punktis 2 leitud MDNK-ga. Erinevus tuleb erinevalt määratud määramatuspiirkonnast. 4. Ülesanne 4.1 Taandatud DNK leidmine: x x x x1 x3 x 4 x1 x3 x 4 x1 x2 x4 x1 x2 x3 x4 MDNK: f(x1,x2,x3,x4) = 1 2 4 Taandatud DNK on funktsiooni kõigi lihtimplikantide disjunktsioon. Taandatud DNK võib sisaldada ka liiaseid liikmeid. x3x4 x1x2 00 01 11 10 0 00 0 1 -1-
1001 (9) X 01-1 A3 1010 (10) X -101 A4 10-1 X 1-01 A5 101- X 3 0111 (7) * X 1011 (11)* X 1101 (13)* X Taandatud DNK : f ( x 1 , x 2 , x 3 , x 4 )= x´1 x 2 x´3 V x´1 x 3 x 4 V x´1 x 2 x 4 V x 2 x´3 x 4 V x 1 x´3 x 4 V x´2 x 3 V x 1 A1 A2 A3 A4 A5 A6 A7 II ETAPP: 2 3 4 5 7* 8* 9 10 11* 13* 010
1. Mis on graafi värvimise ülesanne? Mis on kromaatiline arv? Joonistada mõni näide. Mis on kromaatiline arv 2 aluselisel graafil? Mis on täieliku graafi kromaatiline arv? 2. Hulgateooria mõiste sümmeetrilise vahe kohta. Taandada sümeetriline vahe cantori normaalkujuks. Kas see täielik normaalkuju on minimaalne? Taandatud? Täielik? Mis on sümmeetrilise vahe matemaatilises loogikas? 3. Avaldis (x1x2x3x4) = Mingi konjuktiivne funktsioon (ei mäleta) 1. Leida minimaalne DNK 2. Leida taandatud KNK 4. Funktsioon (x1x2x3) = E(0,2,5,6,7)1 1. Leida täielik KNK 2. Leida shannoni arendus DNK x2 järgi. 3. Leida tuletis x3 järgi. Jääk ära näidata minimaalsel kujul.
1 0 0 1 - 1 0 1 0 0 1 0 1 1 - 1 1 0 0 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 0 3. Leida MDNK (minimaalne DNK) ja MKNK (minimaalne KNK), mis sobiksid matriklinumbrist leitud osaliselt määratud 4- muutuja funktsiooni esitamiseks. 2 Paarisarvulise matriklinumbriga õpilased leiavad MKNK Karnaugh' kaardiga ja MDNK McCluskey' meetodiga. Leian MKNK Karnaugh' kaardiga Y X3 X4 00 01 11 10 00 1 1 1 0
A2 x x A3 x x A4 x x A5 x x Minimaalne disjunktiivne normaalkuju on f(x1,x2,x3,x4)= x1 x2 x4 x1 x2 x3 x2 x3 x4 x1 x2 x3 Leitud MDNK ja MKNK on loogiliselt võrdsed (nende tõeväärtustabelid on võrdsed). 4. MKNK teisendamine DNK-kujule ( x1 x2 )( x1 x2 x3 )( x2 x3 x4 )( x2 x3 x4 ) ( x1 x2 )( x1 x2 x3 )( x3 x2 x2 x4 x2 x3 x3 x3 x4 x4 x2 x3 x4 ) ( x1 x2 )( x1 x2 x3 x1 x2 x4 x1 x2 x3 x1 x3 x1 x3 x4 x1 x2 x4 x1 x3 x4 x2 x3 x2 x4 x2 x3 x2 x3 x4 x2 x3 x4 x2 x 3 x4 x2 x3 x4 )
A5 X X X MKNK on seega: f(x1,x2,x3,x4) = A1 v A2 v A3 v A5 ( f(x ,x ,x ,x ) = x1 x 2 x 4 x1 x 2 2 1 2 3 4 )( x x 4 x1 x3 )( )( ) 3. Teisendan punktis 2 leitud MKNK loogikaalgebra põhiseaduste abil DNK-kujule. ( )( )( f(x 1 , x 2 , x 3 , x 4 ) = x1 x 2 x 4 x1 x 2 x 2 x 4 x1 x3 = )( ) = ( x1 x1 x1 x 2 x1 x 2 x 2 x 2 x1 x 4 x 2 x 4 )( x1 x 2 x 2 x3 x1 x 4 x3 x 4 ) = = ( x1 x 2 x1 x 2 x1 x 4 x 2 x 4 )( x1 x 2 x 2 x3 x1 x 4 x3 x 4 ) = = x1 x 2 x1 x 2 x3 x1 x 2 x 4 x1 x 2 x3 x 4 x1 x 2 x3 x 4 x1 x 2 x3 x 4 x1 x 2 x 4 x 2 x3 x 4 =
6 0110 0 0 0 7 0111 - 1 1 8 1000 0 0 0 9 1001 1 1 1 10 1010 0 0 0 11 1011 1 1 1 12 1100 0 0 0 13 1101 1 1 1 14 1110 0 0 0 15 1111 - 1 1 MDNK ja MKNK on teineteisega loogiliselt võrdsed, kuna nende tõeväärtustabelid on samasugused. 4. MKNK teisendamine DNK-kujule f ( x 1 ... x 4 )=( x´3 v x 4 ) ( x´ 1 v x 4 ) =( x´1 x´3 v x´3 x 4 v x´1 x 4 v x 4 )= x´1 x´3 v x 4 MKNK-st käsitsi teisendatud DNK on kokkulangev punktis 3 saadud MDNK avaldisega. 5. Taandatud DNK ja Täieliku DNK leidmine Taandatud DNK on kõikide lihtimplikantide disjunktsioon, võib sisaldada liigseid liikmeid x3x4 x1x2 00 01 11 10
A8 x x x MDNK : f(x1, x2, x3, x4) = A2 A5 A8 x1 x2 x3 x4 A2 0 0 - 0 x1 x 2 x 4 A5 0 1 1 - x1 x 2 x 3 A8 - - 0 1 x3 x 4 MDNK : f(x1, x2, x3, x4) = x1 x 2 x 4 x1 x 2 x3 x3 x 4 Ülesanne 3. Teisendada punktis 2 leitud MKNK loogikaalgebra põhiseaduste abil DNK-kujule (x1 )( )( x3 x1 x2 x2 x3 x4 x2 x3 x4 = )( ) = x1 x2 x3 x1 x2 x4 x1 x2 x 3 x4 x1 x 2 x3 x1 x 2 x 3 x1 x 3 x4 x1 x 2 x 3 x4 x 2 x 3 x4 x1 x 2 x 4 x1 x 2 x 3 x 4 x 2 x 3 x 4 x1 x3 x 4 x1 x 2 x3 x 4 = = x1 x2 x4 x3 x4 x1 x2 x3 = MDNK Ülesanne 4 1. Leida vabaltvalitud viisil punktis 2 saadud MDNK-ga võrdne Taandatud DNK Taandatud DNK on funktsiooni kõigi lihtimplikantide disjunktsioon. Taandatud
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 x 2 v x 3)(x 1 v x2 v x 3)(x 3 v x4) = = x1 v x1 x 2 v x1 x 3 v x1 x2 v x2 x 3 v x1 x3 v x 2 x3 )( x 1 v x2 v x 3 )( x 3 v x4 ) = = (x1 x 1 v x1 x2 v x1 x 3 v x1 x 1 x 2 v x1 x 2 x 2 v x1 x 2 x 3 v x1 x 1 x 3 v x1 x2 x 3 v v x1 x 3 v x1 x 1 x2 v x1 x2 v x1 x2 x 3 v x 1 x2 x 3 v x2 x 3 v x1 x 1 x3 v x1 x2 x3 v
0 1 1 0 0 0 0 0 1 1 1 - 0 0 1 0 0 0 0 0 0 1 0 0 1 1 1 1 1 0 1 0 1 1 1 1 0 1 1 0 0 0 1 1 0 0 1 1 1 1 1 0 1 0 0 0 1 1 1 0 - 0 0 1 1 1 1 0 0 0 MDNK ja MKNK on loogiliselt võrdsed. 4 4. MKNK teisendamine DNK-kujule MKNK = (1v2v3v4) (1v3v4) (1v3v4) ( 2v4) ( 2v3) DNK = (1 v 2 v 3 v 4)( 1 v 3 v 4)( 1 v 3 v 4)( 2 v 4)( 2 v 3) = (1 1 v 1 3 v 1 4 v 2 1 v 2 3 v 2 4 v 3 1 v 3 3 v 3 4 v 4 1 v 4 3 v 4 4)( 1 v 3 v 4)( 2 v 4) = (1 3 v 1 3 3 v 1 3 4 v 1 4 v 1 1 2 v 1 2 3 v 1 2 4 v 1 2 3 v 2 3 3 v 2 3 4 v 2 4 1 v 2 4 3 v 2 4 v 1 3 1 v 1 3 3 v 1 3 4 v 1 3 v 3 3 v 3 4 v 1 3 4 v 3 4 3 v 3 4 v 1 1 4 v 1 4 3 v 1 4 4 v 1 3 4 v 3 3 4 v 3 4 4 v 0)( 2 v 4) = (1 3 v 1 4 v 1 2 3 v 2 4 v 3 4 v 1 4
MKNK : f ( x1 … x 4 )=Σ ¿ 15 ¿1 1 1 0 1 - 1 1 1 1 1 0 1 1 1 1 1 1 1 - 1 1 ( 1 2 4 ) ( 1 4 ) ( x1 V x´ 2 ) x V x V x x V x 4) MKNK = ´ ´ DNK = ( ´x 1 x 1 V ´x 1 ´x 4 V x2 x1 V x2 ´x 4 V x 4 x 1 V x 4 ´x 4 ) ( x1 V x´ 2 ) =¿ = ( ´x 1 x 1 V ´x 1 ´x 4 V x2 x1 V x2 ´x 4 V x 4 x 1 V x 4 ´x 4 ) ( x1 V x´ 2 ) = = ´x 1 x 1 x 1 V ´x 1 ´x 4 x 1 V x2 x 1 x 1 V x 2 ´x 4 x 1 V x 4 x 1 x1 V x 4 ´x 4 x 1 V V ´x 1 x 1 ´x 2 V ´x 1 ´x 4 ´x 2 V x 2 x 1 ´x 2 V x 2 ´x 4 ´x 2 V x 4 x1 ´x 2 V x 4 x´ 4 ´x 2 = = 0 V 0V x 2 x 1 V x 2 x´ 4 x 1 V x 4 x1 V 0 V V 0 V x´ 1 ´x 4 x´ 2 V 0 V 0 V x 4 x 1 x´ 2 V 0 =
A5 0 0 X Graaf 3.3 Minimaalne konjuktiivne normaalkuju on A(2,3,5) ( x1 x 4)( x 3 x´ 4 )( x´ 1 x 2 x´ 3) (x1,x2,x3,x4) = Minu poolt MKNK-st käsitsi teisendatud DNK ei ole võrdne MDNK-ga, kuna nende tõeväärtustabelid on erinevad. x1 x2 x3 x4 MDNK MKNK DNK 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1 1 1 1 1
Mark 3.00 out of tõeväärtustabeli 0de piirkonnast 3.00 Question 17 vali mõlemasse lünka õiged valikud: Correct Disjunktiivne Normaalkuju (DNK) on konjunktsioonide disjunktsioon mis saadakse Mark 3.00 out of tõeväärtustabeli 1de piirkonnast 3.00 Question 18 kas see väide on õige või vale: ? Correct Avaldis võib olla samaaegselt nii DNK kui ka KNK
Digitaalloogika ja digitaalsüsteemid KODUTÖÖ kaugõpe Tallinn 2015 Sisukord 1.Matriklinumbrile vastav 4-muutuja loogikafunktsioon.........................................3 2.Tõeväärtustabel................................................................................................... 3 3.Karnaugh’ kaardiga minimaalne DNK (MDNK) ja minimaalne KNK (MKNK)..........4 4.Täielik DNK (TDNK) 1-de piirkonnast....................................................................4 5.TDNK lihtsustamine loogikaalgebra põhiseoste abil............................................4 6.MDNK ja MKNK väärtused määramatuspiirkonnas...............................................5 7.MDNK minimaalseima keerukusega loogikaskeem (AND, OR, NOT)....................5 8.MKNK minimaalseima keerukusega loogikaskeem (AND, OR, NOT)..........
28. Mida esitab iga 10ndarv numbrilise 10ndesituse koosseisus? 10ndesituse koosseisus esitab 10ndarv arvule vastavat 2ndvektorit. 29. Mis on algterm? Algterm on loogikaavaldise koosseisu kuuluv muutuja või selle inversioon. 30. Mis on elementaarkonjunktsioon? Elementaarkonjunktsioon on algterm või algtermide konjunktsioon. 31. Mis on elementaardisjunktsioon? Elementaardisjunktsioon on algterm või algtermide disjunktsioon. 32. Mis on disjunktiivne normaalkuju (DNK)? DNK on elementaarkonjunktsioon või elementaarkonjunktsioonide disjunktsioon. 33. Mis on konjunktiivne normaalkuju (KNK)? KNK on elementaardisjunktsioon või elementaardisjunktsioonide konjunktsioon. 34. Esitada näitena avaldisi, mis on samaaegselt nii DNK kui ka KNK? , , ∨ 35. Mis on täielik disjunktiivne normaalkuju (TDNK)? TDNK on DNK, kus iga elementaarkonjunktsioon sisaldab kõiki funktsiooni muutujad. 36. Mis on täielik konjunktiivne normaalkuju (TKNK)
MDNK koosneb alati osadest või kõikidest Taandatud DNK Loogikaskeemide elemendid (loogikaelemendid) elementaarkonjunktsioonidest. Funktsiooni MDNK ja Taandatud DNK võivad olla võrdsed. Kahendkoode (ehk nende koosseisu kuuluvaid loogikaväärtusi 0 1 ) töötlevat elektriskeemi nimetatakse digitaalskeemiks. Iga digitaalseadme elementaarseteks koostisosadeks on loogikaelemendid,
MDNK ja MKNK leidmised on teineteisest sõltumatud ja nad võib leida Loogikafunktsiooni minimeerimine Karnaugh' kaardi abil ükskõik kumbas järjekorras. Loogikafunktsiooni minimeerimine on Karnaugh' kaardi põhiline Leiame esimesena MDNK rakendusvaldkond. ! DNK saadakse alati loogikafunktsiooni 1de piirkonnast ! Karnaugh' kaart on kõige eelistatum minimeerimisvahend, kuid ta on rakendatav ainult kuni 6-muutuja loogikafunktsioonide korral. Kontuuride valimise reeglid /¯¯ ülesanne: ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ 1
A1 X X A2 X X X X A3 X X X X A4 X X X X Et minimaalselt katta kõik tabeli veerud, valime A1, A2 ja A3 ehk f(x1,x2,x3,x4) = x2 xx 3 xx 4 ∨ xx 1 xx 2 ∨ xx 1 xx 4 4. Teisendada punktis 2 leitud MKNK loogikaalgebra põhiseaduste abil DNK-kujule MKNK: f(x1, x2, x3, x4)=( xx 1 ∨ x2) &( xx 2 ∨ x3 ∨ xx 4 ) &( xx 1 ∨ xx 2 ∨ xx 3 ) DNK: f(x1, x2, x3, x4)= (xx 1 xx 2 ∨ xx 1 x3 ∨ xx 1 xx 4 ∨ x2 x3 ∨ x2 xx 4 ) &( xx 1 ∨ xx 2 ∨ xx 3 )= xx 1 xx 2 ∨ xx 1 x3 ∨ xx 1 xx 4 ∨ xx 1 x2 x3 ∨ xx 1 x2 xx 4 ∨ xx 1 xx 2 ∨ xx 1 xx 2 x3 ∨ xx 1 xx 2 xx 4 ∨ xx 1 xx 2 xx 3 ∨ xx 1 xx 3 xx 4 ∨ x2 xx 3 xx 4 =
Funktsioon on täielikult määratud, kui ta määramatuspiirkond on jaotatud 1-de ja 0-de pk vahel. Kui määramatuspiirkonnas on n kahendvektorit, saab sellest 2𝑛 täielikult määratud funktsiooni. Algterm on avaldise koosseisu kuuluva loogikamuutuja 𝑥𝑖 või selle inversioon 𝑥𝑖̅ või konstant 0 1. Elementaarkonjunktsioon on üksik algterm või algtermide konjunktsioon. Elementaardisjunktsioon on üksik algterm või algtermide disjunktsioon. DNK (1-de pk) on üksik elementaarkonj. või elementaarkonj-de disjunktsioon. KNK (0-de pk) on ükskik elementaardisj. või elementaardisj-de konjunktsioon. Samaaegselt DNK ja KNK 𝑥1∨𝑥2∨𝑥3 𝑥1𝑥 ̅ 2𝑥3̅ 𝑥2̅ TDNK on DNK, kus iga elementaarkonj. sisaldab F-ni kõiki muutujaid 𝑥𝑖. TKNK on KNK, kus iga elementaardisj. sisaldab F-ni kõiki muutujaid 𝑥𝑖. MDNK/MKNK on konkreetse F-ni väikseima
võrdsed. All tabelis on näidatud määramatuspiirkondade väärtused kummagi kuju suhtes: MDNK MKNK 3 F D(0101) = 1 f k(0101) = 0 F D(0110) = 1 f k(0110) = 1 F D(1101) = 1 f k(1101) = 0 F D(1110) = 0 f k(1110) = 0 4 4. Teisendada punktis 3 leitud MKNK loogikaalgebra põhiseaduste abil DNK-kujule DNK = (x1 v x2 v x3 v x4) (x2 v x4) (x1 v x4) (x1 v x3) = (x1 x2 v x1 x4 v x2 x4 v x3 x2 v x3 x4 v x4 x2) (x1 x4) (x1 x3) = (x1 x2 x4 v x1 x4 v x2 x4 x1 v x2 x4 v x3 x2 x1 v x3 x2 x4 v x3 x4 x1 v x3 x4 v x4 x2 x1) (x1 v x3) = x1 x2 x4 x3 v x1 x4 x3 v x2 x4 x1 v x2 x4 x1 x3 v x2 x4 x3 v x3 x2 x1 v x3 x2 x4 x1 v x3 x4 x1 v x4 x2 x1 v x4 x2 x1 x3 = x1 x3 x4 v x1 x2 x4 v x2 x3 x4 v x1 x2 x3 v x1 x3 x4 v x1 x2 x4 0 0 11 1
6 12-14 (11- 2 A 0) 7 0 2 3 4 8 9 11 12 14 A X X 1 A X X X X 2 A X X 3 A X X 4 A X X 5 A X X 6 A X X 7 MDNK: 3. ()()()= 4. Taandatud DNK: x1x2x3x 00 01 11 0 4 00 1 0 1 1 01 1 0 0 0 11 1 - 0 1 10 -1 1 -1 0 Täielik DNK: x1x2x3x 00 01 11 10 4 00 1 0 1 1 01 1 0 0 0 11 1 - 0 1 10 -1 1 -1 0 5. Täielik KNK: x1x2x3x 00 01 11 10 4 00 1 0 1 1 01 1 0 0 0 11 1 - 0 1
´x x v x3x4 v x1x2 ´x v ´x ´x ´x v ´x ´x 2 3 4 1 2 4 3 4 5. Leida Taandatud DNK ja Täielik DNK MDNK = ( ´x 3 ´x 4 v x3x4 v ´x 1 ´x 2x3 v x1x2x3) 5.1 Täieliku DNK leidmine *Funktsiooni 1-de piirkonda kuulub 10 argumentvektorit: {0000, 0010, 0011, 0100, 0111, 1100 , 1111, 1000, 1011, 1110} *Koostan DNK, kus iga elementaarkonjunktsioon omandab väärtuse 1 täpselt 1de piirkonna argumentvektoti korral. * xi = 0 siis ´x i ja kui xi=1 siis otseväärtus xi
Küsimus 1 Õige - Hinne 1,00 / 1,00 kas väide on õige või vale ? Karnaugh' kaardi igale ruudule vastab üks konkreetne argumentvektor Vali üks: Tõene Väär Küsimus 2 Õige - Hinne 1,00 / 1,00 Mingi funktsiooni kõikide lihtimplikantide disjunktsioon on DNK taandatud Küsimus 3 Õige - Hinne 1,00 / 1,00 Karnaugh' kaardi üheruudulise kontuuri ulatuses . . . on konstantsed selle funktsiooni kõik muutujad Küsimus 4 Õige - Hinne 1,00 / 1,00 Millised järgnevad mõõdud (kaardiruudud x kaardiruudud x kaardiruudud) võivad olla Karnaugh' kaardi kontuuride mõõtudeks? (märgi kõik sobivad mõõdud) Vali üks või enam: 1x2x3 4x4x8 3x3x3 2x3x4 2x4x8 1x1x1 2x4x1
annaabi.ee 
