ü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 x w ¯2 x
konstantne 10 1 0 0 1 10 1 0 0 1 10 1 0 0 1 10 1 0 0 1 konstantsed muutujad 1-de kontuurile vastav vaadeldavas kontuuris elementaarkonjunktsioon ebaoptimaalsem kontuuridevalik . . . selle kontuurivalikuga oleks 1de katmiseks esindajaks valitud selline täielikult määratud funktsioon
TaDNK : f(x1, x2, x3, x4) = 2. Täielik DNK TDNK leidmine: võtan f.-ni ühtede piirkonna (koos määramatusega mida kasutati MDNK-s) kümnendnumbri ning leian kümnendnubrile vastava kahendvektori ja leian kahendvektorile vastava elementaarkonjunktsiooni ning lisan need funktsiooni TDNK avaldisse (0,1,2,5,6,7,9,13)1 ühtede piirkonna kümnenednumbrile vastav kahendvektorile vastav kümnendnumber kahendvektor elementaarkonjunktsioon 0 0000 x1 x 2 x 3 x 4 1 0001 x1 x 2 x 3 x4 2 0010 x 1 x 2 x3 x 4 5 0101 x1 x2 x 3 x4 6 0110 x 1 x 2 x3 x 4 7 0111 x1 x 2 x3 x 4
Loogikamuutuja: muutuja, mis saab omandada ainult väärtusi 0 või 1 Loogikafunktsioonid Algterm: avaldise koosseisu kuuluv loogikamuutuja, selle inversioon või konstant 1 või konstant 0 Argumentvektor: loogikamuutujate komplekt, mis esitab funktsiooni igale üksikule muutujale omistatavat väärtust 1 või 0. Muutujate väärtustamisel omandab ka loogikafunktsioon väärtuse Elementaardisjunktsioon: üksik algterm või algtermide disjunktsioon Elementaarkonjunktsioon: üksik algterm või algtermide konjunktsioon Loogikavalemi keerukus: loogikavalemi koosseisus olevate algtermide arv Loogikavalemi sügavus: kõige pikem tehete ahel, mis tuleb läbida, et saada loogikafunktsiooni väärtus, pmst aeg, mis funktsiooni lahendmiseks kulub Mitteoluline muutuja: muutuja, millele omistatud loogikaväärtus ei muuda kuidagi funktsiooni väärtust Tõeväärtustabel: loogikafunktsiooni esitusviis, mis loetleb esitatava funktsiooni väärtused
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 sisesta lünka õige sõna: on üksik algterm või algtermide konjunktsioon. Elementaarkonjunktsioon Küsimus 11 Õige - Hinne 1,00 / 1,00 Määramatuspiirkonna moodustavad sellised argumentvektorid, mille korral loogikafunktsioon ... Vali üks: ei omanda väärtust võib omandada ükskõik kumba loogikaväärtuse 0 või 1 omandab samaaegselt mõlemad loogikaväärtused 0 ja 1 Küsimus 12 Õige - Hinne 1,00 / 1,00 sisesta õige vastus arvuna: Kui osaliselt määratud loogikafunktsiooni määramatuspiirkonnas on 4
Mark 1.00 out of 1.00 Select one: True False Question 10 sisesta lünka õige sõna: Correct Mark 1.00 out of elementaarkonjunktsioon on üksik algterm või algtermide konjunktsioon. 1.00 Question 11 täida lünk õige sõnaga: Correct Kui loogikafunktsiooni mingi muutuja ei mõjuta loogikafunktsiooni väärtust mitte kunagi, siis Mark 1.00 out of selline muutuja on mitteoluline muutuja
27. Kuidas koostatakse loogikafunktsioonide numbriline 10ndesitus? Numbriline 10ndesitus on tõeväärtustabeli kompaktne üherealine esitus, kus 2ndvektorid on asendatud vastavate 10ndarvudega. 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
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 Loogikafunktsiooni Täielik DNK on normaalkuju, milles iga elementaarkojunktsioon sisaldab loogikaf.-ni kõiki argumente (või nende inversioone). ühtede piirkonna kümnenednumbrile kahendvektorile vastav kümnendnumber vastav kahendvektor elementaarkonjunktsioon 0 0000 x1 x 2 x 3 x 4 2 0010 x1 x 2 x3 x 4 5 0101 x1 x 2 x 3 x 4 6 0110 x1 x 2 x 3 x 4
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) = Täielik DNK leidmine: Ühtede piirkonna Kümnenednumbrile vastav Kahendvektorile vastav kümnendnumber kahendvektor elementaarkonjunktsioon 2 0010 X1 X 2 X 3 X 4 3 0011 X1 X 2 X 3 X 4 5 0101 X1X 2 X 3 X 4 7 0111 X1X 2 X 3 X 4 11 1011 X1 X 2 X 3 X 4
1 1 1 1 0 0 Tõeväärtustabelist on selgelt näha, et antud funktsioonid ei ole loogiliselt võrdsed, sest määramatuspiirkond on lõpuni määratud erinevalt. 4. Taandatud DNK(s.o McCluskey' meetodi esimese etapi tulemus e. kõikide lihtimplikantide disjunktsioon): f x1 , x 2 , x3 , x4 x1 x3 x 4 x 2 x3 x 4 x1 x 2 x3 x 2 x 4 x1 x 2 x3 x1 x 2 x 4 x1 x 3 x 4 Täielik DNK(iga elementaarkonjunktsioon sisaldab funktsiooni kõiki argumente e. Karnaugh' kaardil näeks see välja midagi sellist): f x1 , x 2 , x3 , x 4 x 1 x 2 x3 x 4 x 1 x 2 x 3 x 4 x1 x 2 x 3 x 4 x 1 x 2 x 3 x 4 x1 x 2 x 3 x 4 x1 x 2 x 3 x 4 x1 x 2 x 3 x 4 x 1 x 2 x 3 x 4 x 1 x 2 x3 x 4 x3x4 x1x2 00 01 11 10 00 0 1 1 1
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 *Saadud elementaarkonjunktsiooni liidan või tehtega kokku DNKs TDNK: f(x1, x2, x3, x4) = ´x 1 ´x 2
-ni ühtede piirkonna mingi kümnendnumbri · leian kümnendnubrile vastava kahendvektori · leian kahendvektorile vastava elementaarkonjunktsiooni · lisan elementaarkonjunktsiooni funktsiooni TDNK avaldisse · kordan eelmist nelja tegevust, kuni kõik ühtede piirkonna numbrid on läbitud ühtede piirkonna kümnenednumbrile kahendvektorile vastav kümnendnumber vastav kahendvektor elementaarkonjunktsioon 4 0100 x1 x2 x 3 x 4 5 0101 x1 x2 x 3 x4 8 1000 x1 x 2 x 3 x 4 9 1001 x1 x 2 x 3 x 4 10 1010 x1 x 2 x3 x 4
Seejärel moodustatakse tabelis olevatest tõestest väärtustest võimalikult suured grupid (kontuurid) suurusega 2n (1, 2, 4, 8, ...). Kontuuride põhjal leitakse avaldise lihtsustatud kuju. Karnaugh kaarti kasutatakse DNK, KNK ja nende minimaalsete, täielike ja taandatud kujusid. Karnaugh kaardi kasutamine ei ole otstarbekas, kui muutujaid rohkem kui 4, sest kaart muutub mitmetasandiliseks. Täielik disjunktiivne normaalkuju on DNK, kus iga elementaarkonjunktsioon sisaldab funktsiooni kõiki elemente. Täielik konjunktiivne normaalkuju on KNK, kus iga elementaardisjunktsioon sisaldab funktsiooni kõiki elemente. 4. Kombinatsioonskeemi ülesande lahendamine Karnaugh kaardi abil. http://www.diskmat.ee/kkaartmnk.pdf <- Meeldetuletus karnaugh kaartide kohapealt. 5. Duaalsuse printsiip. Kui võrrelda tõesuse tabelit, mis vastavad tehtele NING ja VÕI, siis on kerge märgata, et kui tehe NING määravates tingimustes kõik vahelduvate ja funktsiooni
esitatava funktsiooni väärtused tabelisse korrastatuna kõikide argumendiväärtuste kombinatsioonide (ehk argumentvektorite) korral, Algterm on avaldise koosseisu kuuluv loogikamuutuja xi või selle alustades argumentvektorist 000. . .0 ja lõpetades argumentvektoriga inversioon x̄i või konstant 0 1 . 111. . .1 . Eelpool leiduvad juba näited 2-muutuja funktsiooni ja 3-muutuja funktsiooni tõeväärtustabelitest. Elementaarkonjunktsioon on üksik algterm või algtermide konjunktsioon. n-muutuja loogikafunktsiooni muutujatele x1 x2 . . . xn saab väärtusi Järgneval real on näitena toodud 5 elementaarkonjunktsiooni: 0 ja 1 omistada 2n erineval viisil. Samapalju peab olema ridu ka tema x1 x̄2 x2 x̄4 x̄5 x̄1 x̄1 x3 x̄4 x6 x1 x̄3 x6 x̄5 x2 tõeväärtustabelis. Seega tõeväärtustabeli suurus kasvab muutujate arvu
Vasta Vasta ühene vastavus Küsimus 15 Õige Hinne 1,00 / 1,00 sisesta lünka sobiv sõna: Loogikafunktsiooni argumendiks olev kahendvektor on Vasta argumentvektor Küsimus 16 Õige Hinne 1,00 / 1,00 sisesta lünka õige sõna: Vasta on üksik algterm või algtermide konjunktsioon. elementaarkonjunktsioon Küsimus 17 Õige Hinne 3,00 / 3,00 vali mõlemasse lünka õiged valikud: Disjunktiivne Normaalkuju (DNK) on Vasta konjunktsioonide disjunktsioon mis saadakse tõeväärtustabeli Vasta 1de piirkonnast Küsimus 18 Õige Hinne 1,00 / 1,00 sisesta lünka õige sõna: Vasta on üksik algterm või algtermide disjunktsioon.
Sellised argumentvektorid moodustavad F-ni määramatuspiirkonna 𝑉−⊂{0 1}𝑛. Piirkondade ühend 𝑉0∪𝑉1∪𝑉−={0 1}𝑛 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 𝑥𝑖
seotud otsestest või inverteeritud muutujatest, kus iga muutuja esineb vaid üks kord). Kui loogikafunktsioon on esitatud elementaarkonjunktsioonide disjunktsioonina, nimetatakse esitusviisi funktsiooni disjunktiivseks normaalkujuks (DNK). Vähem kasutatakse loogikafunktsiooni konjunktiivset normaalkuju (KNK), mil funktsioon esitatakse elementaardisjunktsioonide konjunktsioonina. Kui funktsiooni disjunktiivse normaalkuju iga elementaarkonjunktsioon sisaldab kõiki muutujaid, nimetatakse funktsiooni esitusviisi tema täielikuks disjunktiivseks normaalkujuks (TDNK). Täielikku disjunktiivset normaalkuju on hõlpus leida loogikafunktsiooni oleku- ehk tõeväärtustabelist. 4 Loogikaelemendid Dioodelement VÕI Kui ühes sisendis on loogiline üks, siis vastav diood avaneb ning vool läbib avanenud dioodi ja takistit R1. Takistil tekib kõrge pinge ehk loogiline üks. Pinge on selline, et ülejäänud dioodid on suletud
Sellised argumentvektorid moodustavad F-ni määramatuspiirkonna 𝑉 − ⊂ {0 1}𝑛 . Piirkondade ühend 𝑉 0 ∪ 𝑉 1 ∪ 𝑉 − = {0 1}𝑛 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 ̅̅̅
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 Parempoolne valem on funktsiooni täielik DNK. · x1 x2 x1 x2 x3 = ( x1 x2 x3 )( x1 x2 x3 )( x1 x2 x3 )( x1 x2 x3 )( x1 x2 x3 )
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. 11
Ümberpöördult, kui valem F 1 & F 2 & . . . & F n → G on samaselt tõene, siis igal väärtustusel, millel valemid F 1 , F 2 , . . . , F n on tõesed, on ka F 1 & F 2 & . . . & F n tõene, mistõttu valem G on samuti tõene. Teoreemid järeldumise ja samaväärsuse taandamisest ühe valemi omaduse kontrollimisele o Samaväärus F ↔ G o Järeldumine F → G 7 6. Literaal, täielik elementaarkonjunktsioon, täielik disjunktiivne normaalkuju, nende tõesuspiirkondade kirjeldused. TDNK olemasolu ja ühesus. TDNK-le teisendamise algoritm, tema etappidel kasutatavad samaväärsused. [1] Literaal o DEF: Literaaliks nimetatakse lausemuutujat või selle eitust, literaale loetakse positiivseks või negatiivseks vastavalt selelle, kas ta on puhas lausemuutuja või koos eitusega. N: A, B, ¬C Täielik elementaalkonjuktsioon
otsestest või inverteeritud muutujatest, kus iga muutuja esineb vaid üks kord). Kui loogikafunktsioon on esitatud elementaarkonjunktsioonide disjunktsioonina, nimetatakse esitusviisi funktsiooni disjunktiivseks normaalkujuks (DNK). Vähem kasutatakse loogikafunktsiooni konjunktiivset normaalkuju (KNK), mil funktsioon esitatakse elementaardisjunktsioonide konjunktsioonina. Kui funktsiooni disjunktiivse normaalkuju iga elementaarkonjunktsioon sisaldab kõiki muutujaid, nimetatakse funktsiooni esitusviisi tema täielikuks disjunktiivseks normaalkujuks (TDNK). Täielikku disjunktiivset normaalkuju on hõlpus leida loogikafunktsiooni oleku- ehk tõeväärtustabelist. 1.2.3. Loogikalülituste süntees ja minimeerimine Loogikalülituste konstrueerimisel on oluline lülitust võimalikult lihtsustada, mis vähendab lülituse hinda ja koostamise töömahtu. Seepärast tuleb juba loogikalülituste sünteesil
annaabi.ee 
