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) võrdne Taandatud DNK ja Täielik DNK, näidates (selgitades) mõlema jaoks ära ka nende leidmisviisi. MDNK: f ( x ₁, x ₂, x ₃, x ₄ )=x ₂ x ₃ ˅ x ₃ x ₄ ˅ x ₁ x ₂ x ₄ ˅ x ₂ x ₃ x ₄ Taandatud DNK leidmine: Taandatud disjunktiivne normaalkuju on funktsiooni kõigi lihtimplikantide disjunktsioon. Karnaugh’ kaart: x₃x₄ x₁x₂ 00 01 11 10 Taantatud DNK:
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 0000 0 0 0001 0 0
x 4 V x 2 x3 x 4 = x1 x 2 Vx1x3V x 1 x2 x 4 Vx3 x 4 3. (x1 x 2 Vx1x3V x 1 x2 x 4 Vx3 x 4 )( x 1 V x2V x 3 ) = x1 x 2 x 3 V x1x2x3V x 1 x3 x 4 Vx2x3 x 4 V x 1 x2 x 4 V x 1 x2 x 4 x 3 = x1 x 2 x 3 V x1x2x3V x 1 x3 x 4 Vx2x3 x 4 V x 1 x2 x 4 Karnaugh' kaardiga saadud MDNK f = x1x2x3Vx1 x 2 x3 V x1 x2 x 4 V x1 x3 x 4 MKNK-st teisendatud MDNK f1 = x1 x 2 x3 V x1x2x3V x1 x3 x 4 Vx2x3 x 4 V x1 x2 x 4 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
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
11.2012 19:38 KONTROLLKÜSIMUSTEGA TEST - loogikaavaldiste erikujud file:///C:/Users/CPU/Desktop/Diskmati_TESTID_moodle__'s_-_100%... Question 12 vali kõik õiged väited: Correct Mark 1 out of 1 Select one or more: Taandatud DNK ja minimaalne DNK (MDNK) võivad olla üks ja sama avaldis Taandatud DNK-d on võimalik leida Karnaugh' kaardi abil Taandatud DNK on funktsiooni kõikide lihtimplikantide disjunktsioon Taandatud DNK on funktsiooni kõikide implikantide disjunktsioon
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 ) = = Saadud avaldus on kokkulangev punktis 2 saadud MDNK- ga (f (x1, x2, x3, x4) = ). 4
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 01 1 0 1 1 11 0 0 1 1 10 1 1 0 0
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 0 0 1 0 1 1
......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 ÜLESANNE 7 SHANNONI DISJUNKTIIVNE ARENDUS KOLME MUUTUJA JÄRGI..................................................................................................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 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. Sel juhul võrdub taandatud disjunktiivne normaalkuju lihtimplikantide disjunktsiooniga. Taandatud DNK: f ( x1 ; x 2 ; x3 ; x 4 ) = x1 x 2 x 2 x 4 x1 x 4 x3
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
1 0 1 1 1 1 1 1 0 0 0 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 Mitte võrdsus on tingitud määramatusest. 4. Leida vabaltvalitud viisil punktis 2 saadud MDNK-ga (loogiliselt) võrdne Taandatud DNK ja Täielik DNK Taandatud DNK: Taandatud DNK on funktsiooni kõigi lihtimplikantide disjunktsioon. Taandatud DNK võib sisaldada ka liiased liikmeid. X3,X4 00 01 11 10 X1,X2 00 0 0 1 1 01 - 1 1 - 11 - - 1 - 10 - 0 1 0 X1X 3 X 4 X1 X 2 X 3 X 3 X 4 Taandatud DNK: (X1,X2,X3,X4) =
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.
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..........................................................................
01 1 - 0 - 11 - 0 - - 10 0 - 0 1 MKNK: f(x1x2x3x4) = (x2 v x3)( 2 v 3)( 1 v 4) Tähistan leitud MDNK ja MKNK: f D = (x2 4) v ( 1 2x3) v (x3 4) f K = (x2 v x3)( 2 v 3)( 1 v 4) 4. Kirjutada oma funktsiooni 1-de piirkonnast välja täielik DNK (TDNK) (ignoreerides määramatuspiirkonda). fTDNK ( 1 2x3 4) v( 1 2x3x4) v ( 1x2 3 4) v (x1 2x3 4) 5. Lihtsustada loogikaalgebra põhiseoste abil eelnevalt leitud täielikku DNK-d lihtsaima DNK-ni, milleks see TDNK lihtsustub. Võrrelda lihtsustamisel saadud DNK-d eelnevalt (punktis 3) leitud MDNK-ga: — kas nad on võrdsed? — kui nad pole võrdsed, siis kumb nendest on väiksema keerukusega (ehk lihtsam) avaldis ja miks?
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 ) =
...................................................................................... 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.1 Võrrelda lihtsustamisel saadud DNK-d eelnevalt (punktis 3) leitud MDNK-ga: ......................................................................................................................
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. · Täielik DNK (TDNK) on selline DNK, kus iga elemantaarkonjunktsiooni pikkus on n (s.o. iga elementaarkonjunktsioon sisaldab funktsiooni kõiki argumente). · Täielik KNK (TKNK) on selline KNK, kus iga elemantaardisjunktsiooni pikkus on n (s.o. iga elementaardisjunktsioon sisaldab funktsiooni kõiki argumente). · Igal funktsioonil on täpselt üks TDNK ja üks TKNK. Näiteid · x1x2 x1 x2 x3 = x1 x2 x3 x1 x2 x3 x1 x2 x3
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. Täielik DNK (TDNK) on selline DNK, kus iga elemantaarkonjunktsiooni pikkus on n (s.o. iga elementaarkonjunktsioon sisaldab funktsiooni kõiki argumente). Täielik KNK (TKNK) on selline KNK, kus iga elemantaardisjunktsiooni pikkus on n (s.o. iga elementaardisjunktsioon sisaldab funktsiooni kõiki argumente). Igal funktsioonil on täpselt üks TDNK ja üks TKNK. Näiteid x1 x2 x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 Parempoolne valem on funktsiooni täielik DNK.
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
= x1 x1 x1 x 2 x1 x 4 x 2 x 4 x1 x 2 x1 x3 x 2 x3 x3 x3 = ) = (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.
A2 0 0 0 0 X1' * X4' ( A2-ga kaasnes vahe 2, 4 ) A4 0 1 0 0 X2 * X3' ( A3-ga kaasnes vahe 1, 8 ) McCluskey' meetodi järgi leitud MDNK on: MDNK: f = X1' X3' v X1' X4' v X2 X3' 4 4. Kirjutada oma funktsiooni 1-de piirkonnast välja täielik DNK (TDNK) (ignoreerides määramatuspiirkonda). TDNK: f (X1 X2 X3 X4) = X1' X2' X3' X4' v X1' X2' X3' X4 v X1' X2' X3 X4' v X1' X2 X3' X4 v X1 X2 X3' X4' v X1 X2 X3' X4 5. Lihtsustada loogikaalgebra põhiseoste abil eelnevalt leitud täielikku DNK-d lihtsaima DNK-ni, milleks see TDNK lihtsustub. Võrrelda lihtsustamisel saadud DNK-d eelnevalt (punktis 3) leitud MDNK-ga: -- kas nad on võrdsed?
x1 x2 x3 x1 x2 x4 x1 x2 x3 x1 x2 x3 x4 x1 x2 x3 x4 x1 x2 x3 x4 x1 x2 x3 x4 x1 x2 x3 x1 x2 x3 x4 x1 x2 x4 x1 x2 x3 x4 x2 x3 x4 x1 x2 x3 x1 x2 x3 x4 x1 x2 x4 x1 x2 x3 x4 x2 x3 x4 x1 x2 x3 x4 x1 x2 x3 x1 x2 x3 x4 x1 x2 x4 x1 x2 x3 x4 x1 x2 x3 x4 x1 x2 x3 x1 x2 x4 x2 x3 x4 x1 x2 x3 x1 x2 x4 x1 x2 x3 x4 MKNKst teisendatud DNK ei ole kokkulangev MDNK avaldisega, kuid sisaldab endas MDNKs olevaid avaldisi. DNK ja MDNK ei ole ka loogiliselt võrdsed, mõlema tõeväärtustabeli välja arvutamisel selgus, et erinevus on vektoris 1010. Teisendatud DNK avaldises on rohkem liikmeid, mis muudavad tõeväärtustabelid erinevaks. 5. Taandatud DNK ja Täieliku DNK leidmine. Täielik DNK: Punktis 2 esitatud tõeväärtustabeli järgi kuulub funktsiooni 1de piirkonda 7
1010 0 0 1011 0 0 1100 0 0 1101 1 1 1110 0 0 1111 1 0 Selgitus: Kuna MKNK määras määramispiirkonnas funktsiooni väärtuse kohal 1111, 0'ks ning 2. ülesandes leitud MDNK aga 1'ks, siis oleme leidnud vastuolu, ning MKNK lahtikorrutatult ei saagi võrduda MDNK'ga, kuna määramispiirkonnad määrati lõpuni erinevalt. 4. Leian vabalt valitud viisil punktis 2 saadud MDNK-ga (loogiliselt) võrdse Taandatud DNK ja Täieliku DNK. x3x4 x1x2 00 01 11 10 00 1 1 1 1 01 0 0 0 0 11 0 1 1 0 10 1 0 0 0 4.1. Leian Taandatud DNK Taandatud DNK on kõikide lihtimplikantide disjunktsioon ning antud juhul võrdne MDNK'ga: x x x 2 x3 x 4 x1 x 2 x 4
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 00 1 1 1 -
Ü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 DNK võib sisaldada ka liiased liikmeid. Funktisooni lihtimplikantide hulga leidsin McCluskey meetodiga ülesandes 2. Kuna lihtimplikandid A6 ja A7 sisaldavad määramatust ja ei osutunud valituks MDNK-sse, ei vali ka neid TaDNK-sse , et saadud avaldis oleks loogiliselt võrdne MDNK-ga. Sellele hulgale vastav funktsiooni taandatud DNK:
= x1 x2 x 3 v x1 x 3 v x1 x 2 x 3 v x1 x2 x 3 v x 1 x2 x 3 v x2 x 3 v x1 x2 x3 x 3 v x 1 x 2 x3 x 3 v v x1 x2 x4 v x1 x2 x4 v x1 x 3 x4 v x1 x 2 x 3 x4 v x1 x2 x 3 x4 v x 1 x2 x 3 x4 v x2 x 3 x4 v v x1 x2 x3 x4 v x 1 x 2 x3 x4 = x2 x 3 v x1 x2 x4 v x1 x 3 v x1 x2 x 3 v x1 x 2 x 3 v x1 x2 x 3 v v x 1 x2 x 3 v x1 x 3 x4 v x1 x 2 x 3 x4 v x1 x2 x 3 x4 v x 1 x2 x 3 x4 v x2 x 3 x4 v x1 x2 x3 x4 = = x2 x 3 v x1 x 3 v x1 x2 x4 v x 1 x 2 x3 x4 = 𝒇(xMDNK MKNK-st teisendatud DNK on avaldisena kokkulangev ülesandes 3 leitud MDNK-ga. 8 ÜLESANNE 5 DISJUNKTIIVSED NORMAALKUJUD Leida vabalt valitud viisil ülesandes 3 saadud MDNK-ga võrdne Taandatud DNK ja Täielik DNK, selgitades mõlema jaoks ära ka nende leidmisviisi. 𝒇(xMDNK(x1x2x3x4) = x2 x 3 v x1 x 3 v x1 x2 x4 v x 1 x 2 x3 x4 5.1 TAANDATUD DNK Vaadates alamülesande 3
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 3)( 2 v 4)= = 1 2 3 v 1 3 4 v 1 2 4 v 1 4 v 1 2 2 3 v 1 2 3 4 v 2 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 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 Mark 1.00 out of 1.00 Select one: True False Question 19 Milliseid 2-muutuja loogikafunktsioone esitavad need tõeväärtustabelid ? Correct
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
1 1 0 1 0 0 1 1 1 0 0 0 1 1 1 1 0 0 Tõeväärtustabelid ei ole võrdsed, kuna koht f7 asub määramatuspiirkonnas. McCluskey tabelis oli antud liige välja jäetud ja teisendamise teel leitud DNK-s sisse arvestatud. 5. Leida vabaltvalitud viisil punktis 3 saadud MDNK-ga (loogiliselt) võrdne Taandatud DNK ja Täielik DNK Taandatud DNK leiame Karnaugh' kaardi ühtede piirkonna abil X3,X4 00 01 11 10 X1,X 2 00 - 1 1 1 01 1 0 - 1 11 1 0 0 0 10 0 0 0 0 TaDNK = x1 xx 2 x4 ∨ x2 xx 3 xx 4 ∨ xx 1x3 xx 4 ∨ xx 1 xx 2 x3 ∨ xx 1 xx 2 x4
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 
Sisene Facebook'ga
Sisene Google'ga
Sisene LinkedIn'ga
