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. Mis on MDNK? Mis on MKNK? MDNK ja MKNK on konkreetse funktsiooni väikseima keerukusega DNK või KNK. Millisest loogikafunktsiooni piirkonnast tuleneb DNK, millisest KNK?
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).....................7 9
Teoreem 4. Valemid F ja G on samaväärsed parajasti siis, kui valem FG on samaselt tõene. Tõestus... 2 Lausearvutuse põhisamaväärsused. Valemite avaldamine etteantud tehete kaudu. 2 Tõestus SML õpikus lk 21 3 Valemite disjunktiivne ja konjunktiivne normaalkuju. Nende leidmise algoritmid. Def 7. Lvalemi F täielikuks TDNK nim valemiga F samaväärset valemit, mis kujutab endast erinevate täielike EKD 3 Valemi F TKNK nim valemiga F samaväärset valemit, mis kujutab endast erinevate täielike EDK. Kui valem F ei ole samaselt väär, siis tal leidub TDNK. Kui valem F ei ole samaselt tõene, siis tal leidub TKNK (Teoreem 5+Järeldus 1) 4 Täielikule disjunktiivsele normaalkujule viimise algoritmi sammud
(märgi kõik sobivad mõõdud) Vali üks või enam: 1x2x3 4x4x8 3x3x3 2x3x4 2x4x8 1x1x1 2x4x1 2x2x2 1x1 3x3 1x4x4 Küsimus 5 Õige - Hinne 1,00 / 1,00 kas väide on õige või vale ? Karnaugh' kaardi igal ruudul on täpselt 1 naaberruut Vali üks: Tõene Väär Küsimus 6 Õige - Hinne 1,00 / 1,00 vali õige: Loogikafunktsioonil puudub TÄIELIK DISJUNKTIIVNE normaalkuju (TDNK) konstant 0 Küsimus 7 Õige - Hinne 2,00 / 2,00 Milline on kontuuride valimise kriteerium (reegel) minimaalse normaalkuju leidmisel ? Vajalikud kaardiruudud tuleb katta võimalikult väikse arvu võimalikult suurte kontuuridega Küsimus 8 Õige - Hinne 1,00 / 1,00 kas järgnev väide on õige või vale? Karnaugh' kaardi iga kontuur vastab mingile kindlale intervallile Vali üks:
inversioon x disjunktsioon v konjunktsioon & või " " lihtimplikant AX (X=1..n) DNK disjunktiivne normaalkuju KNK konjunktiivne normaalkuju täielik disjunktiivne / konjunktiivne TDNK/TKNK normaalkuju minimaalne disjunktiivne / MDNK/MDNK konjunktiivne normaalkuju taandatud disjunktiivne / TaDNK/TaKNK konjunktiivne normaalkuju 2. Ülesannete lahendamine 2.1 MDNK leidmine McCluskey meetodiga 2.1
Mark 1 out of 1 Select one: True False Question 3 kas järgnev väide on õige või vale? Correct TDNK-avaldises tohib kõik tehted disjunktsioon asendada alati tehtega summa mooduliga Mark 1 out of 1 2, kusjuures selliselt muudetud avaldis on esialgse TDNK-avaldisega loogiliselt samaväärne Select one: True False
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: TaDNK : f(x1, x2, x3, x4) = A1 A2 A3 A4 A5 A8 x1 x 2 x3 x1 x 2 x 4 x1 x3 x 4 x1 x 2 x 4 x1 x 2 x3 x3 x 4 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
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)? TKNK on KNK, kus iga elementaardisjunktsioon sisaldab kõiki funktsiooni muutujaid. 37. Mis on loogikaavaldise keerukus? Loogikaavaldise keerukus on temas sisalduvate algtermide arv. 38. Mis on minimaalne DNK (MDNK)? Mis on minimaalne KNK (MKNK)? MDNK (MKNK) on vähima keerukusega DNK (KNK) ehk sisaldab kõige vähem algterme. 39
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? -- kui nad pole võrdsed, siis kumb nendest on väiksema keerukusega (ehk lihtsam) avaldis ja miks?
4 x 2-6 4 A1 8 x 4-5 1 x 2 5 x 4-6 2 x 6 x 8-9 1 A2 9 x 2-3 5-7 2 x 3 7 x 5-13 8 x 13 x 6-7 1 x 9-13 4 x Seega on taandatud DNK: Ehk taandatud DNK langeb kokku MDNK-ga. * Leian TDNK. Kirjutan TDNK eelnevalt leitud f1-e tõeväärtustabeli ühtede piirkonnast. 5. Leida vabaltvalitud viisil punktis 2 saadud MKNK-ga (loogiliselt) võrdne Täielik KNK. Teisendan punktis 2 saadud MKNK TKNK-ks. 6. Teha punktis 2 saadud MDNK-le Shannoni disjunktiivne arendus selle muutuja (muutujate) x i järgi, mida esineb MDNK-s kõige rohkem. Minu MDNK-s esinevad muutujad x1 ja x3 mõlemad 3 korda. Seega teen Shannoni disjunktiivse arenduse kahe muutuja järgi.
..,w,*,+)=f(a,b,c,...,w,+,* )n 14. Loogikaavaldiste algebraline lihtsustamine 15. Funktsionaalselt täielikud süsteemid Loogika elementide süsteemi mis realiseerib kõikki kahe argumendi funktsioone nimetatakse funktsionaalselt täielikuks süsteemiks nt. NING, VÕI ja EI. Minimaalne funktsionaalselt täielik süsteem on selline millest ükskõik millise elemendi väljajätmine muudab süsteemi mittetäielikuks. Nt.VÕI EI või NING EI. 16. Täielik disjunktiivne normaalkuju e. TDNK DNK on loogika funktsiooni esitamine realiikmete disjunktsioonina (summana), kus liikmed on argumentide või argumentide inversioonide elementaarkonjunktsioonid (korrutised). Elementaarkonjunktsioonid on nt. 1 × 2 × 3 ; Elementaarkonjunktsioonid ei ole nt. X2*X3*X3; X1*X3; X3*X4*X5 TDNK puhul peavad kõik liikmed sisaldama funktsiooni kõikki argumente või nende inversioone. Kui algfunktsioon on antud tabelina siis saab TDNK otse tabelist välja kirjutada. 17
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 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: .........................................................................................................................
5. Taandatud DNK ja Täieliku DNK leidmine. MDNK (x1,x2,x3,x4) = x´ 1 x 4 x 1 ´x3 x´ 4 x 1 x2 x´ 3 TaDNK leidmine: x3x4 x1x2 00 01 11 10 00 0 1 1 0 01 0 1 1 0 11 1 0 1 1 10 1 0 0 0 TADNK (x1,x2,x3,x4) x´ 1 x 4 x 1 x2 x´ 4 x 2 x3 x 3 x2 x´ 3 x 4 , TDNK leidmine: Täielik DNK on DNK normaalkuju, milles iga elmentaarfunktsioon sisaldab funktsiooni kõiki argumente. Selle leidmiseks võtan kõik ühtede piirkonna kümnendnumbrid, leian neile vastavad kahendvektorid ja leian kahendvektoritele vastavad elementaarkonjunktsioonid ning lisan nad avaldisse. 1de pk. Kümnendnumbrile Kahendvektorile vastav vastav kahendvektor elementaarkonjunktsioo
b.i. Tõestus. https://moodle.ut.ee/mod/url/view.php?id=78717 lk 20. 6) a. Lausemuutujat või selle eitust nimetatakse literaaliks. b. Olgu vaatluse all komplekt lausemuutujaid 1, 2,..., n, lisades vajaduse järgi eitusi, moodustame literaalid 1, 2,..., n ning koostame valemi 1 & 2 & ... & n. Sellist valemit nimetatakse täielikuks elementaarkonjunktsiooniks. c. Lausearvutuse valemi täielikuks disjunktiivseks elementaarkonjunktsiooniks (TDNK) nimetatakse valemiga samaväärset valemit, mis kujutab endast erinevate täielike elementaarkonjunktsioonide disjunktsiooni. TDNK on tõene parajasti nendel väärtustustel, mis vastavad normaalkuju liikmetele. d. TDNK leidumine. Teoreem. Kui valem ei ole samaselt väär, siis tal leidub täielik disjunktiivne normaalkuju. e. Valemi TDNK jaoks on üheselt määratud seal esinevate täielike
Valemeid F ja G nimetatakse samaväärseteks, kui nende tõeväärtused on võrdsed igal neis valemeid esinevate muutujate väärtustusel Ütleme, et valemitest F1, F2, ..., Fn järeldub valem G, kui igal neis valemeis esinevate muutujate väärtustusel, millel F1, F2, ..., Fn on tõesed, on ka G tõene Lausearvutuse põhisamaväärsused eraldi lehel!! 2. NORMAALKUJUD Lausearvutuse valemi F täielikuks disjunktiivseks normaalkujuks (TDNK) nimetatakse valemiga F samaväärset valemit, mis kujutab endast erinevate täielike elementaarkonjuktsioonide disjunktsiooni o Täielik disjunktiivne normaalkuju on tõene parajasti nendel väärtustustel, mis vastavad normaalkuju liikmetele o X111 & ... & Xn1n X121 & ... & Xn2n ... X1m1 & ... & Xnmn on tõene väärtustustel (11, ..., 1n), (21, ..., 2n), ..., (m1, ..., mn) ja väär kõigil ülejäänud väärtustustel
MKNK: : f(x1x2x3x4) = ( x 2 v x 3 )( x 2 v x 4 )( ´x 1 v x 3 ) 4. 5. MDNK-ga loogiliselt võrdne Taandatud DNK (TaDNK) ja Täielik DNK (TDNK) TaDNK 00 01 11 10 00 0 0 1 0 01 1 1 1 1 11 1 0 1 1 10 0 0 1 0 TaDNK: f(x1x2x3x4) = ´x 1
MDNK'ga: x x x 2 x3 x 4 x1 x 2 x 4 f(x1,x2,x3,x4) = 1 2 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.2. Leian Täieliku DNK ehk TDNK Täielik DNK ehk TDNK on kõikide implikantide disjunktsioon ning võrdub antud juhul: x1 x 2 x3 x 4 x1 x 2 x3 x 4 x1 x 2 x3 x 4 x1 x 2 x3 x 4 x1 x 2 x3 x 4 x1 x 2 x3 x 4 f(x1,x2,x3,x4) = x1 x 2 x3 x 4 x3x4 x1x2 00 01 11 10 00 1 1 1 1 01 0 0 0 0
Küsimus 1 Õige - Hinne 1,00 / 1,00 Millised on loogikafunktsiooni võimalikud esitusviisid ? Vali üks või enam: osaline järjestussuhe Hasse diagramm tõeväärtustabel Grassmani valem Venni diagramm hulk loogikaavaldis numbriline kümnendesitus Küsimus 2 Õige - Hinne 3,00 / 3,00 vali mõlemasse lünka õiged valikud: Konjunktiivne Normaalkuju (KNK) on mis disjunktsioonide konjunktsioon saadakse tõeväärtustabeli 0de piirkonnast Küsimus 3 Õige - Hinne 1,00 / 1,00 kas järgnev väide on õige või vale? 4-mõõtmeline Boole'i ruum on kõikide 4-järguliste 2ndvektorite hulk. Vali üks: Tõene Väär Küsimus 4 Õige - Hinne 6,00 / 6,00 vali sobivad väljendid, mille korral lause on õige: Täielikult määratud loogikafunktsioon on kõikjal määratud ...
............................................................................18 3.7.1. n-MOP loogika.................................................................................................19 3.7.2. Komplementaarne MOP-CMOS......................................................................19 4. Kombinatsioonseadmete süntees...................................................................................21 4.1. Loogikafunktsiooni täielik disjunktiivne normaalkuju ehk TDNK........................21 4.2. Täielik konjunktiivne normaalkuju TKNK.........................................................21 4.3. Loogikafunktsioonide lihtsustamine Karnaugh' kaartide meetodil....................22 5. Integraalsed trigerid.......................................................................................................23 5.1. NING-EI ja VÕI-EI................................................................................................ 23
............................................................................18 3.7.1. n-MOP loogika.................................................................................................19 3.7.2. Komplementaarne MOP-CMOS......................................................................19 4. Kombinatsioonseadmete süntees...................................................................................21 4.1. Loogikafunktsiooni täielik disjunktiivne normaalkuju ehk TDNK........................21 4.2. Täielik konjunktiivne normaalkuju TKNK.........................................................21 4.3. Loogikafunktsioonide lihtsustamine Karnaugh’ kaartide meetodil....................22 5. Integraalsed trigerid.......................................................................................................23 5.1. NING-EI ja VÕI-EI................................................................................................23
Mark 6.00 out of 6.00 vastavus Question 4 kas see väide on õige või vale: ? Correct Loogikafunktsioonil võib olla mitu erinevat täielikku disjunktiivset normaalkuju (TDNK) Mark 1.00 out of 1.00 Select one: True False Question 5 Millised on loogikafunktsiooni võimalikud esitusviisid ?
disjunktsioon. Karnaugh’ kaart: x₃x₄ x₁x₂ 00 01 11 10 Taantatud DNK: 00 0 1 0 1 01 _ _ 0 0 11 1 _ 1 0 10 _ _ 0 1 f ( x ₁, x ₂, x ₃, x ₄)=x ₂ x ₃˅ x ₃ x ₄˅ x ₁ x ₂ x ₄˅ x ₂ x ₃ x ₄ ˅ x ₁ x ₃ f(x₁,x₂,x₃x₄ f(x₁,x₂,x₃x₄ TDNK leidmine: ) ) 0000 0 Täielikult määratud 0001 1 Karnaugh’ kaart: Tõeväärtustabel: 0010 1 x₃x₄ 0011 0 00 01 11 10 0100 1 x₁x₂ 00 0 1 0 10101 1 0110 0 01 1 1 0 00111 0 1000 0
. . . on 7 implikanti : t Kuna kõik lihtimplikandid on Karnaugh' kaardil hästi näha, siis sobib kaart u {001} {011} {100} {101} {100 101} {001 011} {001 101} ka TaDNK leidmiseks. r v . . . . mida esitavad Karnaugh' kaardil sellised kontuurid : Igal loogikafunktsioonil on täpselt 1 TDNK ja täpselt 1 TaDNK. A x 2 x3 x 2 x3 Taandatud normaalkuju mõiste defineeritakse ainult DNK jaoks x 1 00 01 11 10 x 1 00 01 11 10 ehk Taandatud KNK "pole olemas" 0 0 1 1 0 0 0 1 1 0 t
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 keerukusega DNK/KNK. Keerukus 𝑳(𝒇) on tema koosseisus olevate algtermide arv. Loogikaalgebra põhiseosed Seosed konstantidega 0̅=1 1̅=0 0∗1=0 0∨1=1 𝑥∗0=0 𝑥∗1=𝑥 𝑥∗𝑥̅=0 𝑥∨0=𝑥 𝑥∨1=1 𝑥∨𝑥̅=1 Idempotentsus 𝑥∗𝑥=𝑥 𝑥∨𝑥=𝑥
Seega loogikafunktsiooni taandatud disjunktiivne normaalkuju on võrdne saadud MDNK-ga: 5 f TaDNK =x1 x´ 2 ∨ x 4 =f MDNK 5.2 TÄIELIK DNK Täielik DNK on selline disjunktiivne normaalkuju, mille korral iga elementaarkonjunktsiooni pikkus on võrdne loogikafunktsiooni argumentide arvuga. Vaadates alamülesande 3.1 parempoolset Karnaugh’ kaarti, saame ühtede piirkonna järgi välja kirjutada TDNK. Selleks valime ühtede piirkonnast minimaalse suurusega kontuurid, s.t joonistame iga muutujate väärtuse “1” ümber kontuuri suurusega 1 ning kirjutame kaardi järgi välja täieliku disjunktiivse normaalkuju: f TDNK =´x 1 ´x 2 ´x 3 x 4 ∨ x´ 1 ´x2 x 3 x 4 ∨ ´x 1 x 2 x´ 3 x 4 ∨ ∨ ´x 1 x 2 x 3 x 4 ∨ x1 ´x 2 ´x 3 x´ 4 ∨ x 1 x´ 2 ´x3 x 4 ∨ x 1 ´x 2 x 3 ´x 4 ∨ ∨ x 1 ´x 2 x 3 x 4 ∨ x1 x 2 ´x 3 x 4 ∨ x 1 x 2 x3 x 4 ÜLESANNE 6 TÄIELIK KNK
MKNK leidmise /¯¯ ülesanne: ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ kontuuridevalik f K (0011) = 1 Leia Karnaugh' kaardi abil MDNK samale funktsioonile, mille f K (1110) = 1 TDNK lihtsustasime eelpool näites MDNK-ks x1 x 2 x 3 f ( x 1 x 2 x3 ) f ( x1 x2 x3) = x2 w x1 x3 w ¯1 x x ¯3 0 0 0 1 0 0 1 0 MDNK-ks saime sama tulemuse nagu enne TDNK teisendamisel Ü
5.1 TAANDATUD DNK Vaadates alamülesande 3.1 Karnaugh’ kaarti, näeme, et joonistatud kontuurid vastavad ühtlasi ka lihtimplikantidele.Leian taandatud DNK täielikult määratud Karnaugh’ kaardiga : 𝒇(xTaDNK(x1x2x3x4) = x2 x 3 v x1 x 3 v x1 x2 x4 v x 1 x 2 x3 x4 = 𝒇(xMDNK 5.2 TÄIELIK DNK Vaadates alamülesande 3.1 Karnaugh’ kaarti, saame ühtede piirkonna järgi välja kirjutada TDNK. 𝒇(xTDNK(x1x2x3x4) = x 1 x 2 x3 x4 v x 1 x2 x 3 x 4 v x 1 x2 x 3 x4 v x1 x 2 x 3 x 4 v x1 x 2 x 3 x4 v v x1 x2 x 3 x 4 v x1 x2 x 3 x4 v x1 x2 x3 x4 9 ÜLESANNE 6 TÄIELIK KNK Leida vabalt valitud viisil ülesandes 3 saadud MKNK-ga loogiliselt võrdne täielik KNK. 𝒇(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) Teades, et saadud MKNK on loogiliselt võrdne saadud MDNK-ga, siis võime
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 15 1111 X1X 2 X 3 X 4 TDNK: X1 X 2 X 3 X 4 X1 X 2 X 3 X 4 X1X 2 X 3 X 4 X1X 2 X 3 X 4 X1 X 2 X 3 X 4 (X1,X2,X3,X4)= V V v v v X1X 2 X 3 X 4 5. Leida vabaltvalitud viisil punktis 2 saadud MKNK-ga (loogiliselt) võrdne Täielik KNK Täieliku KNK leidmise meetod: nullide piirkonna kümnenednumbrile vastav kahendvektorile vastav
sisesta lahtrisse õige vastus küsimusele: Kuidas nimetatakse kahendvektorite (kindlate omadustega) hulka, kus on 1 või 2 või 4 või 8 või 16 jne kahendvektorit ja mille vektoresitus koosneb sümbolitest 0 1 -- (näiteks: 00-- 1 1---- 01 ) Vastus: intervall Küsimus 11 Õige Hinne 1,00 / 1,00 kas see väide on õige või vale: ? Loogikafunktsioonil võib olla mitu erinevat täielikku disjunktiivset normaalkuju (TDNK) Vali üks: Tõene Väär Küsimus 12 Õige Hinne 1,00 / 1,00 kas see väide on õige või vale: ? Avaldis võib olla samaaegselt nii DNK kui ka KNK Vali üks: Tõene Väär Küsimus 13 Õige Hinne 1,00 / 1,00 täida lünk õige sõnaga: Kui loogikafunktsiooni mingi muutuja ei mõjuta loogikafunktsiooni väärtust mitte kunagi, siis selline muutuja on Vasta muutuja mitteoluline
· 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 Parempoolne valem on funktsiooni täielik DNK.
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.
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 keerukusega DNK/KNK. Keerukus 𝑳(𝒇) on tema koosseisus olevate algtermide arv. Loogikaalgebra põhiseosed Seosed konstantidega 0̅ = 1 1̅ = 0 0 ∗ 1 = 0 0 ∨ 1 = 1 𝑥 ∗ 0 = 0 𝑥 ∗ 1 = 𝑥 𝑥 ∗ 𝑥̅ = 0 𝑥 ∨ 0 = 𝑥 𝑥 ∨ 1 = 1 𝑥 ∨ 𝑥̅ = 1
11 0 - 0 1 10 0 1 - 1 x1 x 2 x 4 x1 x3 x 4 x1 x3 x 4 x1 x 2 x 4 x1 x 2 x3 x 4 Taandatud DNK: f(x1,x2,x3,x4) = Taandatud DNK ja punktis 2 leitud MDNK on võrdsed. 4.2 Täieliku DNK (TDNK) leidmine: x3x4 x1x2 00 01 11 10 00 0 0 1 -1- 01 0 1 0 1 11 0 - 0 1 10 0 1 - 1
/¯¯ ülesanne: ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ 1 0 1 1 1 Leia Karnaugh' kaardi abil MDNK samale funktsioonile, mille TDNK lihtsustasime eelpool näites MDNK-ks MDNK : f ( x1 x 2 x 3 ) = x2 w x1 x3 w x¯1 x¯3 x 4 x5 x 4 x5 x 2 x3 00 01 11 10 x 2 x3 00 01 11 10
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 o DEF: Muutujate X1, X2…, Xn täielikuks elementaarkonjunktsiooniks nimetatakse literaalide konjunktsiooni L1&L2&,..., &Ln Täielik disjunktiivne normaalkuju
x3x4 00 01 11 10 x1x2 00 0 0 0 1 01 1 0 0 1 11 0 1 1 1 10 1 1 1 0 Karnaugh' kaardile on kantud on 6 intervalli. Leian konstandid. Arvestan seejuures, et DNK sõltub 1de piirkonnast. Intervallidel: 100- x1 x 2 x3 1--1 x1x4 111- x1x2x3 -110 x2x3 x 4 10-0 x1 x2 x 4 0-10 x1 x3 x 4 Taandatud DNK f = x1x4 V x1x2x3 V x1 x 2 x3 V x2x3 x 4 V x1 x2 x 4 V x1 x3 x 4 2) Leian TDNK (täielik DNK) Täieliku DNK korral on igas funktsiooni liikmes kõik funktsiooni muutujad esitatud. Täieliku DNK leidmiseks MDNK-st kasutan kleepimisseaduseid st. kleebin puuduva muutuja liikmele. f = x1x2x3Vx1 x 2 x3 V x1 x2 x 4 V x1 x3 x 4 = x1 x 2 x3 x 4 V x1 x 2 x3 x4 V x1x2x3 x 4 V x1x2x3x4 V x1 x2 x3 x 4 V x1 x2x3 x 4 V x1 x 2 x3 x 4 V x1 x2x3 x 4 ÜLESANNE 5 Leida vabaltvalitul viisil punktis 2 saadud MKNK-ga loogiliselt võrdne Täielik KNK
0010 x1 x2 x3 x 4 0011 x1 x2 x3 x 4 0101 x1 x2 x3 x 4 1101 x1 x2 x3 x 4 1110 x1 x2 x3 x 4 1111 x1 x 2 x3 x 4 Leitud konstituentide järgi saan TDNK: f(x1,x2,x3,x4)= x1 x2 x3 x4 x1 x2 x3 x4 x1 x2 x3 x4 x1 x2 x3 x4 x1 x2 x3 x4 x1 x2 x3 x4 x1 x2 x3 x4 Taandatud DNK: Leian Karnaugh’ kaardi abil f(x1,x2,x3,x4)= ∑ (0, 2, 3, 5, 13, 14, 15)1 x3x4 11 00 01 10 x1x2 00
0101 x1 x2 x3 x4 0110 x1 x2 x3 x4 1100 x1x2 x3 x4 1101 x1 x2 x3 x4 1110 x1 x2 x3 x4 1000 x1 x2 x3 x4 TDNK = 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 v x1x2 x3 x4 v x1 x2 x3 x4 v x1 x2 x3 x4 v x1 x2 x3 x4 6. Leida vabaltvalitud viisil punktis 3 saadud MKNK-ga (loogiliselt) võrdne Täielik KNK Täieliku KNK leiame vastupidiselt TDNK'le funktsiooni nullide piirkonnast, kusjuures xi = 0 annab otseväärtuse xi ja xi = 1 annab inversiooni xi. ARGUMENTVEKTOR KONSTITUENT
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 Täieliku DNK leiab iga argumentvektori konstituentide või- tehtega liitmise teel. 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 TDNK = xx 1 xx 2 xx 3 x4 ∨ xx 1 xx 2 x3 x4 ∨ xx 1 xx 2 x3 xx 4 ∨ xx 1 x2 xx 3 xx 4 ∨ xx 1 x2 x3 xx 4 ∨ x1 x2 xx 3 xx 4 6. Leida vabaltvalitud viisil punktis 3 saadud MKNK-ga (loogiliselt) võrdne Täielik KNK. MKNK leidsime Karnaugh kaardi abil nullide piirkonnast. Täieliku KNK saamiseks Karnaugh' kaardist kirjutame välja kõik nullide piirkonna 1-sed kontuurid, ehk X3,X4 00 01 11 10 X1,X 2
Leian täieliku DNK. Täielik DNK on funktsiooni ühtedeks avalduvate 2- ndvektorite disjunktsioon, kus igas elementaarkonjuktsioonis on kõik funktsiooni muutujad esindatud. x´ 1 x´2 x´3 x´4 V x´ 1 x 2 x´3 x´4 V x 1 x 2 x´3 x´ 4 V x´1 x 2 x´3 x 4 V x 1 x 2 x´3 x 4 V x´1 x´2 x 3 x 4 V V x´1 x´2 x 3 x´4 V x´1 x2 x 3 x´4 V x1 x´ 2 x 3 x´4 Võrdlen MDNK väärtustega: TDNK väärtused on MDNK-ga samad. 6. Leian MKNK järgi täieliku KNK. TKNK on funktsiooni nullideks avalduvate 2- ndvektorite konjunktsioon, kus igas elementaardisjuktsioonis on kõik funktsiooni muutujad esindatud. Kasutan selleks vasakul asuvat tõeväärtustabelit, mis on
Järgneval kolmel real on igal real avaldis, mis on samaaegselt nii DNK kui V1 = { 001, 010, 100, 110, 111 } ka KNK : DNK on seotud funktsiooni 1-de piirkonnaga ja x1 w x2 w x̄3 KNK on seotud 0-de piirkonnaga. x̄1 x2 x̄3 Funktsiooni 1-de piirkonnast saab välja kirjutada selle funktsiooni TDNK. x̄2 Vaatleme järgnevat 3-muutuja funktsiooni: x1 x2 x3 f ( x1 x2 x3 ) Täielik DNK ( TDNK ) on DNK, kus iga elementaarkonjunktsioon 0 0 0 0 Funktsiooni 1-de piirkonda kuulub sisaldab funktsiooni kõiki muutujaid xi
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 ´x 3 ´x 4 v ´x 1
TÕESTUS: Kui on kehtestatav, siis väärtustusel, kus on tõene, on valem ¬ väär ja ei saa seetõttu olla samaselt tõene. Ümberpöördult, kui ¬ ei ole samaselt tõene, siis leidub väärtustus, kus ¬ on väär ja on järelikult tõene. 3. LOENG Järeldumine. Valemite teisendamine. TDNK Definitsioon F1 Fn Öeldakse, et valemitest , ... , järeldub valem , kui igal neis valemeis esinevate F1 Fn muutujate väärtustusel, millel , ... , on tõesed, on ka tõene. F1 Fn Asjaolu, et valemitest , ..
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. Kui loogiline üks on mitmes sisendid, siis kõik vastavad dioodid avanevad ja väljundis on üks
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 funktsioone kindlate kriteeriumide järgi minimeerida. Kõige enam on läbi töötatud
annaabi.ee 
