KARNAUGH' KAARDID Karnaugh' kaart on funktsiooni tõeväärtustabeli sihipärane topoloogiline ümberpaigutus tasandil või ruumis. T Ü Tõeväärtustabeli igale reale vastab kaardil üks ruut. T Karnaugh' kaartide topoloogia 2muutuja Karnaugh' kaart on tabel mõõtmetega 2 2 (või 1 4) ruutu ; 3muutuja Karnaugh' kaart on tabel mõõtmetega 2 4 = 8 ruutu ; 4muutuja Karnaugh' kaart on tabel mõõtmetega 4 4 = 16 ruutu ; e h n ik a t või i 6 - muutuja Karnaugh' kaart v ut Karnaugh' kaartide põhiomadused r
( 0-lle ei tohi valida 1-de kontuuridesse ) 2. Määramatuse ruute tohib seejuures kontuuridega katta, kuid ei pea katma. Ü Määramatusi katame kontuuridega ainult siis, kui see aitab kasvatada T Leida Karnaugh' kaardiga MDNK MKNK 4-muutuja funktsioonile: veelgi suuremaks mõnda niikuinii vajalikku kontuuri. T f ( x1 . . . x4 ) = ( 1, 4, 5, 9, 11, 12, 13, 15 ) 0 ( 3, 14 ) — 3. Kontuurid tohivad kattuda — peavad olema suurimad võimalikud. parim kontuuridevalik selle funktsiooni 1-de piirkonna jaoks:
A4 8 0 0 1 1 ( x 2 x3 x 4 ) A8 1,2 0 0 0 0 (x 1 x2 ) MDNK f ( x1 , x 2 , x3 , x 4 ) = x1 x 2 x1 x3 x 4 x 2 x3 x 4 3. 4. Täielik DNK f ( 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 x1 x 2 x3 x 4 x1 x 2 x3 x 4 Leidsin Karnaugh' kaarti järgi: x3x4 x1x2 00 01 11 10 00 1 1 1 1 01 11 1 10 1 1 Taandatud DNK f ( x1 , x 2 , x3 , x 4 ) = x1 x 2 x1 x3 x 4 x 2 x3 x 4 x 2 x3 x 4 Leidsin Karnaugh' kaarti järgi: x3x4
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. Tõeväärtustabeli igale reale vastab kaardil üks ruut. Millised on karnaugh kaardi põhiomadused? 2 põhiomadust: Kaardi iga ruudu naaberruutude arv võrdub kaardi muutujate arvuga. Suvalise kahe naaberruudu argumentvektorid on teineteise lähiskoodid. Milline on suurim karnaugh kaart? 6-muutuja karnaugh kaart, kuna 7 muutuja puhul pole 7.ndat naaberrutu ruumis enam kuhugi paigutada.
IASB Tallinn 2009 ÜLESANNE 1 Leida oma martiklinumbrile vastav 4-muutuja loogikafunktsioon f(x1, x2, x3, x4) = (2,4,8,9,14,15) (6,11,13) _ (järgnevalt kui funktsioon) 1 ÜLESANNE 2 Leida MDNK ja MKNK, mis sobiksid martiklinumbrist leitud osaliselt määratud 4-muutuja funktsiooni esitamiseks Kuna minu martiklinumber on paarisarvuline leian: MKNK Karnaugh' kaardiga ja MDNK McCluskey' meetodiga. 1) Leian MKNK Karnaugh' kaardiga MKNK leidmiseks joonestan Karnaugh' kaardi, kuhu kannan peale funktsiooni 1d, 0d ja määramatused. x3x400 01 11 10 x1x2 00 0 0 0 1 01 1 0 0 - 11 0 - 1 1 10 1 1 - 0 Tegu on osaliselt määratud funktsiooniga. Osaliselt määratud funktsiooni korral võime määramatuse asemele vabalt valida kas 0 või 1.
f(x1, x2, x3, x4) = ∑ (2, 3, 7, 8, 9, 13)1 (1, 4, 5, 14, 15)_ 2. Esitada oma loogikafunktsiooni tõeväärtustabel: x1 x2 x3 x4 f 0000 0 0001 - 0010 1 0011 1 0100 - 0101 - 0110 0 0111 1 1000 1 1001 1 1010 0 1011 0 1100 0 1101 1 1110 - 1111 - 3. Leida MDNK (McClusky meetodil) ja MKNK (Karnaugh’ kaardiga); tuvastada, kas leitud MDNK ja MKNK on teineteisega loogiliselt võrdsed või mitte. MKNK leidmine: 2 MKNK: f(x1x2 x3x4) = (x1 V x3) ( xx2 V x4) (xx1 V x2 V xx3) MDNK leidmine: Leian laiendatud 1-de piirkonna: ∑ (1*, 2, 3, 4*, 5*, 7, 8, 9, 13, 14*, 15*)1 Inde Laiendat M 2-sed M 4-sed M ks ud 1-de interval intervalli piirk
KODUTÖÖ 082800 MAHB11 Tallinn 2008 Ülesanne 1. Leida oma matriklinumbrile vastav 4-muutuja loogikafunktsioon. f( x1, x2, x3, x4 ) = (0,1,2,5,6,7,9)1 (11,13,14)- 1 1 0 1 0 1 1 1 0 - 0 - 0 1 - 0 Ülesanne 2. MKNK leidmine Karnaugh' kaardiga. MKNK: f(x1,x2, x3, x4)= (x 1 )( )( )( x3 x1 x 2 x2 x3 x 4 x2 x3 x 4 ) MDNK leidmine McCluskey meetodiga Ind Märge Ind. Nr.-d Vahe Märge Ind. Nr.-d Vahe Märge Nr. . 0 0 x 0-1 0-1 1 A1 1-2-2-3 1-5-9-13* 4,8 A8
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 2x2x2 1x1 3x3 1x4x4 Küsimus 5 Õige - Hinne 1,00 / 1,00 kas väide on õige või vale ?
Finish review Correct Loogikafunktsioonil konstant 1 puudub TÄIELIK KONJUNKTIIVNE Mark 1 out of 1 normaalkuju (TKNK) Question 2 kas järgnev väide on õige või vale? Correct Karnaugh' kaardi iga kontuur vastab mingile kindlale intervallile Mark 1 out of 1 Select one: True False Question 3 kas järgnev väide on õige või vale? Correct
teine tõeväärtustabel (2) on pöördimplikatsioon FUNKTSIOONIDE NORMAALKUJUDE MINIMEERIMINE Küsimus 1 Õige Hinne 1,00 / 1,00 kas järgnev väide on õige või vale? MDNKavaldises tohib kõik tehted disjunktsioon asendada alati tehtega summa mooduliga 2, kusjuures selliselt muudetud avaldis on esialgse MDNKavaldisega loogiliselt samaväärne Vali üks: Tõene Väär Küsimus 2 Õige Hinne 1,00 / 1,00 4muutuja loogikafunktsiooni Karnaugh' kaardil on . . . . . . kaheruudulise kontuuri Vastus 1 . . . 3 konstantset muutujat; ulatuses . . . . . . üheruudulise kontuuri Vastus 2 . . . 4 konstantset muutujat; ulatuses . . . . . . viieruudulise kontuuri Vastus 3 . . . pole sellise mõõduga kontuuri ! ulatuses . . . . .
Tallinna Tehnikaülikool Diskreetne Matemaatika KODUTÖÖ 1. Leida oma matriklinumbrile vastav 4- muutuja loogikafunktsioon. Loogikafunktsioon: f (x1, x2, x3, x4) = 1 (8, 9, 10)_ 2. Leida MDNK ja MKNK, mis sobiksid matriklinumbrist leitud osaliselt määratud 4- muutuja funktsiooni esitamiseks. MDNK Karnaugh' kaardiga f (x1, x2, x3, x4) = 1 (8, 9, 10)_ x3x4 00 01 11 10 x1x2 00 1 0 0 1 01 0 1 1 0 11 1 0 1 0 10 - - 0 - f (x1, x2, x3, x4) = MKNK McCluskey meetodiga Lihtimplikantide hulga leidmine Ind- Ind-
docstxt/14145076641836.txt
........................ 2 Kahendkoodid.................................................................................................................................................... 4 Loogikafunktsioonid ja loogikaavaldised ........................................................................................................... 5 Avaldiste teisendused........................................................................................................................................ 8 Karnaugh’ kaart ................................................................................................................................................. 9 McCluskey’ minimeerimismeetod ................................................................................................................... 10 Loogikaskeemid. Funktsioonide täielikud süsteemid. Teisendused baasidesse ............................................. 11 Jääkfunktsioon. Tuletis. Shannoni arendus. Funktsioonide klassid
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
Töö ülessanne ja soovitud funktsionaalsus: a. kirjeldada minimaalne funktsioon, mis antud sisendile annab soovitud väljundi b. teisendada funktsioon kasutamaks soovitud element baasi loogika elemente c. luua skeem Kaitsmine: a. olla valmis selgitama, kuidas ülessannet lahendasid b. kuidas lahendaksid sarnaseid probleeme. c. mõiste selgitused { disjunktiivne/konjunktiivne normaalkuju, karnaugh kaart, tundmatud muutujad Karnaugh kaardis, De Morgani seadused, jne } d. demonstratsioon korrektsusest {voo diagramm või loenduriga simuleerimine, ...} e. "Mis juhtub, kui ... ?" - tüüpi suvaline küsimus Kusjuures segmentindikaatori segmendid on markeeritud alljärgnevalt: Näide (segment a, nor baas) Segmentindikaatori segmendi a väärtused arvude 0 - 9 korral on {1, 0, 0, 0, 1, 1, 1, 0, 1, 1}, ning
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 -
𝑓12(𝑥1𝑥2)=𝑥1̅ 𝑒𝑠𝑖𝑚𝑒𝑠𝑒 𝑚𝑢𝑢𝑡𝑢𝑗𝑎 𝑖𝑚𝑝𝑙𝑖𝑘𝑎𝑡𝑠𝑖𝑜𝑜𝑛 𝑓13(𝑥1𝑥2)=𝑥1→𝑥2 𝑖𝑚𝑝𝑙𝑖𝑘𝑎𝑡𝑠𝑖𝑜𝑜𝑛 𝑓14(𝑥1𝑥2)=𝑥1𝑥2̅ 𝑘𝑜𝑛𝑗𝑢𝑛𝑘𝑡𝑠𝑖𝑜𝑜𝑛𝑖 𝑖𝑛𝑣𝑒𝑟𝑠𝑖𝑜𝑜𝑛 𝑓15(𝑥1𝑥2)=1 𝑘𝑜𝑛𝑠𝑡𝑎𝑛𝑡 1 KARNAUGH’ KAART Karnaugh’ kaart on F-ni tõeväärtustabeli sihipärane topoloogiline ümberpaigutus tasandil või ruumis. Põhiomadused: kaardi iga ruudu naaberruutude arv võrdub kaardi muutujate arvuga ; suvalise kahe naaberruudu argumentvekt. on teineteise lähiskoodid. 6-muutuja kaart on suurim Karnaugh’ kaart. 2-, 3- ja 4-muutuja kaardid on tasandilised, 5- ja 6-muutuja kaardid ruumilised. Karnaugh’ kaardil valitakse välja kindlate mõõtmetega ruutude
Diskreetne matemaatika KODUTÖÖ SISUKORD SISUKORD..........................................................................................1 ÜLESANNE 1 LOOGIKAFUNKTSIOON......................................................3 ÜLESANNE 2 TÕEVÄÄRTUSTABEL..........................................................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......................
Diskreetne Matemaatika Kodutöö Jago Niin 123835 IASB12 1. Leida oma matriklinumbrile vastav 4-muutuja loogikafunktsioon. Matrikli number on 123835. Saadud 8-kohaline 16-süsteemi arv on 10247E89. Määramispiirkonna leidmisel tuleb arv F31680. f(, , , ) = 2. Leida MDNK ja MKNK, mis sobiksid matriklinumbrist leitud osaliselt määratud 4-muutuja funktsiooni esitamiseks. Leian MDNK Karnaugh' kaardiga. f(, , , ) = x3x4 00 01 11 10 x1x2 00 1 1 - 1 01 1 0 1 - 11 0 0 - 1 10 1 1 0 0 MDNK: f(, , , ) = v v v MKNK McCluskey meetodiga f(, , , ) = Indek Nr Indeks Intervall Märge Intervall Märge s
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
McCluskey' minimeerimismeetod Sellise laiendatud 1-de piirkonna ( 0, 2, 6, 7, 8, 10, 3*, 14* ) 1 jaotame Ü Karnaugh' kaart on visuaalheuristiline minimeerimismeetod. lahtritesse vastavalt arvude indeksile (ehk alustame kleepimistabelit) : T ( vajalike kontuuride otsene vahetu väljavalimine pole algoritmina kirjeldatav ) index laiend. 1de pk. 2-sed interv. vahe 4-sed interv. vahe T Karnaugh' kaart on kuni 6-muutujaga loogikafunktsioonide jaoks; 0 0
𝑥1 𝑒𝑠𝑖𝑚𝑒𝑠𝑒 𝑚𝑢𝑢𝑡𝑢𝑗𝑎 𝑖𝑚𝑝𝑙𝑖𝑘𝑎𝑡𝑠𝑖𝑜𝑜𝑛 𝑓13 (𝑥1 𝑥2 ) = 𝑥1 → 𝑥2 𝑖𝑚𝑝𝑙𝑖𝑘𝑎𝑡𝑠𝑖𝑜𝑜𝑛 𝑓14 (𝑥1 𝑥2 ) = ̅̅̅̅̅̅ 𝑥1 𝑥2 𝑘𝑜𝑛𝑗𝑢𝑛𝑘𝑡𝑠𝑖𝑜𝑜𝑛𝑖 𝑖𝑛𝑣𝑒𝑟𝑠𝑖𝑜𝑜𝑛 𝑓15 (𝑥1 𝑥2 ) = 1 𝑘𝑜𝑛𝑠𝑡𝑎𝑛𝑡 1 OK KARNAUGH’ KAART Karnaugh’ kaart on F-ni tõeväärtustabeli sihipärane topoloogiline ümberpaigutus tasandil või ruumis. Põhiomadused: kaardi iga ruudu naaberruutude arv võrdub kaardi muutujate arvuga ; suvalise kahe naaberruudu argumentvekt. on teineteise lähiskoodid. 6-muutuja kaart on suurim Karnaugh’ kaart. 2-, 3- ja 4-muutuja kaardid on tasandilised, 5- ja 6-muutuja kaardid ruumilised. Karnaugh’ kaardil valitakse välja kindlate mõõtmetega ruutude gruppe, mida nim kontuurideks, iga kontuur vastab
Correct määramatuspiirkond selle funktsiooni 1de piirkonnale mille tulemusel Mark 3 out of 3 saadakse laiendatud 1de piirkond Question 3 kas väide on õige või vale: Correct Jääkfunktsioone ei saa leida Karnaugh' kaardi abil Mark 1 out of 1 Select one: True False Question 4 Kuidas nimetatakse sellist (n-1)muutuja funktsiooni, mis saadakse mingi n-muutuja
10ndesituses: f(x₁,x₂,x₃,x₄)=Σ(1,2,10,12,15)₁ (4,5,8,9,13)_ Π(0,3,6,7,11,14)ₒ LAHENDATAVAD ÜLESANDED 2. Leida MDNK ja MKNK, mis sobiksid matriklinumbrist leitud osaliselt määratud 4-muutuja funktsiooni esitamiseks. Osaliselt määratud 4-muutuja funktsioon: f(x₁,x₂,x₃,x₄)=Σ(1,2,10,12,15)₁ (4,5,8,9,13)_ Π(0,3,6,7,11,14)ₒ MDNK leidmine: Karnaugh’ kaart: x₃x₄ x₁x₂ 00 01 11 10 MDNK: 00 0 1 0 1 f (x ₁, x ₂, x ₃, x ₄ )=x ₂ x ₃ ˅ x ₃ x ₄ ˅ x ₁ x ₂ x ₄ ˅ x ₂ x ₃ x ₄ 01 _ _ 0 0 11 1 _ 1 0 10 _ _ 0 1 MKNK leidmine: Kleepimistabel:
1. Teisendatud kuju ühtede piirkond: 24AB1665>2,4,10,11,1,6,5 Teisendatud kuju määramatuse piirkond: 2282E7E> 8, 14, 7 f(X1X2X3X4)=(1,2,4,5,6,10.11)1(7,8,14)_ 2. MDNK Karnaugh' kaardiga! x3x4 x1x2 00 01 11 10 00 1 1 _ 01 1 1 1 _ 11 _ 10 1 1 MDNK f ( x1 x2 x3 x4 ) = x1 x2 x1 x3 x4 x1 x2 x3 x3 x4 McCluskey
Määramatuspiirkonna määramiseks saadud 16-nd arv on 2675BD7 Määramatuspiirkond on seega f(x1,x2,x3,x4) = (5,6,7,11) Seega on matriklinumbrile 104493 vastav 4-muutuja loogikafunktsioon oma numbrilises 10ndesituses: f(x1..x4) = (1,2,4,8,9,13)1 (5,6,7,11)_ 2. Leida MDNK ja MKNK, mis sobiksid matriklinumbrist leitud osaliselt määratud 4-muutuja funktsiooni esitamiseks. Kuna matriklinumber 104493 on paaritu, siis leian MDNK Karnaugh' kaardiga. Tegu on osaliselt määratud funktsiooniga. Osaliselt määratud funktsiooni korral võime määramatuse asemele vabalt valida kas 0 või 1. Kuna minimaalne disjunktiivkuju leitakse 1-de piirkonna kaudu, siis valin vastavad kontuurid. Seega on MDNK: · Nüüd leian MKNK McCluskey' meetodiga. Selleks kirjutan välja oma funktsiooni nullide piirkonna. f(x1..x4) = (0,3,10,12,14,15)0 (5,6,7,11)_
1 1 0 0 1 1 1 0 1 - 1 1 1 0 0 1 1 1 1 1 ÜLESANNE 3 MINIMAALSED NORMAALKUJUD Leian MDNK ja MKNK, mis sobiksid matriklinumbrist leitud osaliselt määratud 4-muutuja funktsiooni esitamiseks. MDNK Karnaugh’ kaardiga ja MKNK McCluskey' meetodiga. 3 3.1 MDNK KARNAUGH’ KAARDIGA Leian MDNK Karnaugh kaardiga, sest matriklinumber on paarisarv. Funktsioon 𝒇(x(x1,x2,x3,x4) = ∑ ( 3, 5, 8, 12, 15 )1 ( 4, 9, 13 )_ x1x2/x3x4 00 01 11 10 00 0 0 1 0
0 0 0 0 1 1 1 0 1 1 1 1 NOT(ei) xor 00-0 10-1 01-1 11-0 A Q 0 1 NOR(või-ei) 1 0 A B Q 0 0 1 0 1 0 1 0 0 1 1 0 NAND (ja-ei) A B Q 0 0 1 0 1 1 1 0 1 1 1 0 3. Karnaugh kaart, loogikafunktsiooni täielik disjunktiivne normaalkuju ja täielik konjunktiivne normaalkuju. Karnaugh kaart on graafiline abivahend kahendväärtusi sisaldava avalduse lahendamiseks. Tõeväärtustabelist võetud väärtused paigutatakse kaardile ja järjestatakse Gray koodi printsiibi kohaselt, s.o kõrvutiasetsevate tulpade või ridade puhul erineb vaid ühe muutuja väärtus. Seejärel moodustatakse tabelis olevatest tõestest väärtustest võimalikult suured grupid (kontuurid)
Tallinna Tehnikaülikool Arvutid I KAUGÕPE 1.kodutöö Jelizaveta Vavilkina Mat.nr. 124226 Rühm: IASB Ülesanne: Koostada vasakule nihutava paralleel laadimidega nihkeregistri loogikaskeem JK trigerite baasil. Esmane skeem näeb välja: Funktsiooni sõltuvus: J(i)=f(PL, di, qi-1, Ki ) Tõeväärtustabel J(i) väärus sõltub q(i) nihest ja K(i) väärtusest Karnaugh kaart vastavalt tõeväärtustabelile: J(i) = PL q(i-1) K(i) + PL d(i) q(i-1) + PL d(i) q(i) q(i-1) + + PL d(i) q(i) + PL q(i) q(i-1) + PL q(i) q(i-1) K(i) = = PL q(i-1) ( K(i) + d(i) + q(i) ) + PL q(i) (d(i) + K(i) + q(i-1) ) Skeem vastavalt valemile:
Yc= 3 210 + 3 210 + 3210 + 3210 + 3210 + 3210 + 3210 + 3210 + 3210 + 3210 + 3210 + 3210 Yd= 3210 + 3210 + 3210 + 3210 + 3210 + 3210 + 3210 + 3210 + 3210 + 3210 Ye= 3210+ 3210 + 3210 + 3210 + 3210 + 3210 + 3210 + 3210 + 3210 + 3210 Yf= 3210+ 321 0 + 3210 + 3210 + 3210 + 3210 + 3210 + 3210 + 3210 + 3210 + 3210 Yg= 3210 + 3210 + 321 0 + 3210 + 3210 + 3210 + 3210 + 3210 + 3210 + 3210 + 3210 + 3210 Karnaugh tabel Tuletatud funktsiooni lihtsustamine ehk loogikafunktsiooni minimeerimine. Loogiliste ühtede grupid: 1. Ühed peavad asuma üksteise kõrval, mitte diagonaaliti. 2. Grupid võivad koosneda 2-st, 4-st, 16-st jne ühest. 3. Grupp peab olema võimalikult suur ( valida alati kõige suurem grupp). 4. Üks võib kuuluda mitmesse gruppi. 5. Gruppide moodustamine kestab seni, kuni kõik loogilised nullid või ühed hakkavad kuuluma mingisse gruppi. Näide:
loogikamuutujat x i või tema inversiooni x̄ i või avaldise koosseisu kuuluvat konstanti 0 või 1. KARNAUGH' KAARDID x4 x5 x4 x5 x 2x 3 00 01 11 10 00 01 11 10
1010 0 1011 0 1100 1 1101 0 1110 0 1111 0 3. Leida MDNK ja MKNK, mis sobiksid matriklinumbrist leitud osaliselt määratud 4-muutuja funktsiooni esitamiseks. 1)MKNK Karnaugh' kaardiga f(x1, x2, x3, x4)=∑(1, 2, 3, 4, 6, 12)1 (0, 7)_ 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 X3,X4 00 01 11 10 X1,X 2 00 - 1 1 1 01 1 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 Karnaugh' kaardi järgi leitud MKNK on: 01 - 1 - 0 MKNK: f = (X1' v X2) (X3' v X4') (X2' v X3')
1. Loogika funktsiooni leidmine f(x1 ,x2 ,x3, x4 ) = (1,7,8,9,10,12,15)1 (5,11,13,14)- (0,2,3,4,6)0 2. MDNK ja MKNK leidmine MDNK Karnaugh' kaardiga x3x4 x1x2 00 01 11 10 00 0 1 0 0 01 0 - 1 0 11 1 - 1 - 10 1 1 - - MDNK: x1 x2 x4 x3 x4 2. MKNK McCluskey' meetodiga f(x1 ,x2 ,x3, x4 ) = (0,2,3,4,6)0 (5,11,13,14)- Ind. Nr. Märge Ind. Nr
1010 0 1011 - 1100 0 1101 1 1110 1 1111 1 3. Leida MDNK ja MKNK Kuna matriklinumber on paarituarvuline (155539), siis leian MKNK Karnaugh' kaardiga ja MDNK McCluskey' meetodiga. MKNK: Funktsiooni f(x1,x2,x3,x4) = Π(1, 6, 7, 8, 9, 10, 12) 0 (4, 11)_ Karnaugh’ kaart: x3x4 00 01 11 10 x1x2 1 1 1 00 0 - 1
.....................4 1.1 Funktsiooni arvutamine ...................................................................................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 ............................
Sisukord Sissejuhatus........................................................................................................... 3 Displei ja funktsionaalplokk.................................................................................... 4 Loogikafunktsioonide tuletamine............................................................................5 Loogikafunktsioonid............................................................................................ 5 Karnaugh tabel....................................................................................................... 6 Ya funktsiooni minimeerimine............................................................................. 7 Yb funktsiooni minimeerimine............................................................................. 7 Yc funktsiooni minimeerimine............................................................................. 7 Yd funktsiooni minimeerimine............................
1 0 1 1 0 1 1 0 0 - 1 1 0 1 1 1 1 1 0 - 1 1 1 1 0 loogikafunktsiooni tõeväärtustabel -----> 3. Leida MDNK ja MKNK, mis sobiksid matriklinumbrist leitud osaliselt määratud 4-muutuja funktsiooni esitamiseks. Kuna matriklinumber on paarituarvuline, siis leian MKNK Karnaugh’ kaardiga ning MDNK McCluskey’ meetodiga. MKNK MKNK: f ( x 1 x 2 x3 x 4 ) =¿ ( x1 v x4 )( ´x 1 v ´x 3 v ´x 4 ) 1,3, 4∗,5∗, 6∗, 7∗, 8∗, 9, 10,12∗, 13,14∗¿ 1 MDNK f ( x1 x 2 x 3 x 4 )=Σ ¿ inde laiend. 1de K 2-sed K? 4-sed K? x pk. ? interv. inter. 0 00-1 K 0--1 A
martiklinumbrist leitud osaliselt 0 0 0 1 0 määratud 4-muutuja funktsiooni 0 0 1 0 1 esitamiseks 0 0 1 1 - MDNK: 0 1 0 0 0 Karnaugh’ kaart 0 1 0 1 0 x1x2x3x4 00 01 11 10 0 1 1 0 - 00 - 0 - 1 0 1 1 1 1 01 0 0 1 -
x1 x 2 x3 f 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 Funktsiooni 1-de piirkonda kuulub 5 argumentvektorit V1=(000, 001, 010, 011, 111) f = x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 Funktsiooni 0-de piirkonda kuulub 3 argument vektorit V0=(100, 101, 110) f = ( x1 x2 x3 ) ( x1 x2 x3 ) ( x1 x2 x3 ) MKNK leidmiseks teeme Karnaugh kaardi ja katame 0-de piirkonna sinna peale: f = ( x1 x2 )( x1 x3 )
9 1 0 0 1 1 x 4 x 3 x 2 x1 ... ... ... ... ... ? ... fD = x 4 x 3 x 2 x 1 v x 4 x 3 x 2 x1 v x 4 x 3 x 2 x1 v x 4 x3 x 2 x1 v x 4 x3 x 2 x1 v x 4 x3 x 2 x 1 v x 4 x3 x 2 x1 v x 4 x 3 x 2 x 1 v x 4 x 3 x 2 x1 2. Loogikafunktsiooni minimeerimine Kasutan minimeerimiseks nelja muutuja loogikafunktsiooni Karnaugh' kaarti x2x1 x4x3 00 01 11 10 00 1 1 1 0 01 1 1 1 1 11 - - - - 10 1 1 - - fD = x 2 v x1 v x 4 x3 3. Funktsiooni realisatsioon loogikaskeemil 3
Tallinna Tehnikaülikool Diskreetne Matemaatika KODUTÖÖ TALLINN 2008 1. f( x1, x2, x3, x4 ) = (0, 2, 3, 4, 9, 12, 14)1(8, 11, 13)- 2. MKNK (Karnaugh) x1x2x3x 00 01 11 10 4 00 1 0 1 1 01 1 0 0 0 11 1 - 0 1 10 - 1 -0 0 MKNK: ()()() MDNK (McCluskey) Ind Nr. M Ind Nr-d. Vahe M Ind. Nr-d. V M . . 0 0 (0000) X 0-1 0-2 (00-0) 2 A 0-1-1- 0-4-8-12 (-- 4,8 A 1 2 00) 2
5 0 1 0 1 1 6 0 1 1 0 1 7 0 1 1 1 0 8 1 0 0 0 1 9 1 0 0 1 1 A 1 0 1 0 x B 1 0 1 1 x C 1 1 0 0 x D 1 1 0 1 x E 1 1 1 0 x F 1 1 1 1 x 2. Karnaugh' kaart xx 2 1 00 01 11 10 xx4 3 00 1 0 1 1 01 0 1 0 1 11 x x x x 10 1 1 x x MDNK: Y Y Y Y Y Y Y Y Y Y Y
Kõige enam on läbi töötatud loogikafunktsioonide täielike disjunktiivsete normaalkujude minimeerimismeetodid. Tavaliselt on eesmärgiks leida minimaalse pikkusega loogikafunktsiooni algebraline avaldis, milles on minimaalne arv sisendmuutujate tähiseid, näiteks minimaalne disjunktiivne normaalkuju ehk MDNK. Loogikafunktsioonide minimeerimiseks kasutatakse 1) vahetut lihtsustamist, 2) lihtsustamist Karnaugh kaardi abil, 3) Quine - Mc Cluskey meetodit, 4) Blake' i meetodit jms. Karnaugh kaart on loogikafunktsiooni tõeväärtustabeli ehk olekutabeli erikuju, mida kasutatakse funktsiooni minimeerimiseks. Karnaugh kaart on ruudu- või ristkülikukujuline lahterdatud tabel. Lahtrite arv sõltub funktsiooni sisendmuutujate (argumentide) arvust n ning vastab muutujate kombinatsioonide arvule 2n. Muutujad
1000 1 1001 0 1010 0 1011 0 1100 1 1101 - 1110 - 1111 0 2 3. Leida Karnaugh' kaardi abil MDNK ja MKNK, mis sobiksid matriklinumbrist leitud osaliselt määratud 4-muutuja funktsiooni esitamiseks MDNK Karnaugh' kaardiga: 0 0 1 1 0 1 1 0 0 0 1 1 1 0 0 1 - 0 - 1
0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 1 1 0 0 0 1 1 1 - 1 0 0 0 - 1 0 0 1 1 1 0 1 0 1 1 0 1 1 - 1 1 0 0 0 1 1 0 1 - 1 1 1 0 0 1 1 1 1 0 3) Leida MDNK ja MKNK, mis sobiksid selle esitamiseks MKNK Karnaugh' kaardiga f(x1 ... x4) = (2, 3, 4, 5, 9, 10)1 (7, 8, 11, 13)_ (0, 1, 6, 12, 14, 15)0 X1X2 X3X4 0 0 => x1=0 x2=0 x3=0 0 0 1 1 1 1 - 0 - 0 => x1=0 x2=1 x3=1 0 - 0 0
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
2. Loogikafunktsiooni tõeväärtustabel X1 X2 X3 X4 0 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1 1 1 0 1 0 0 - 0 1 0 1 0 0 1 1 0 0 0 1 1 1 - 1 0 0 0 0 1 0 0 1 1 1 0 1 0 1 1 0 1 1 0 1 1 0 0 1 1 1 0 1 0 1 1 1 0 - 1 1 1 1 0 2 3. MDNK ja MKNK leidmine MDNK Karnaugh' kaardiga 00 01 11 10 00 1 0 1 1 01 - 0 - 0 11 1 0 0 - 10 0 1 0 1 MDNK = f(x1...x4) = 1 2 4 v 1 2 3 v 2 3 4 v 1 2 3 4 v 1 2 3 4 MKNK McCluskey' meetodiga. Indeks Intervall M Indeks Intervallid M Indeks Intervallid M 0 - 0-1 - 0-1-1-2 -
1-de piirkond: 0,1,2,3,8,13 Viimaks jagan 11-ga: F30266 <- siit saab määramatuspiirkonna (mis pole juba ühtede piirkonnas) Määramatuspiirkond: 6,15 Seega oleks matriklinumbrile 123795 vastav 4-muutuja loogikafunktsioon oma numbrilises 10ndesituses: f(x1,x2,x3,x4) = (0,1,2,3,8,13)1 (6,15)_ f(x1,x2,x3,x4) = (4,5,7,9,10,11,12,14)0 (6,15)_ 2. Ülesanne 2.1 Leian Karnaugh' kaardi abil MDNK 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 x1 x2 x2 x3 x4 x1 x2 x4
2. Funktsiooni tõeväärtustabel Nr. x1x2x3x4 f 0 0000 1 1 0001 1 2 0010 - 3 0011 1 4 0100 - 5 0101 1 6 0110 0 7 0111 - 8 1000 0 9 1001 1 10 1010 0 11 1011 1 12 1100 0 13 1101 1 14 1110 0 15 1111 - 3. MDNK ja MKNK leidmine Matriklinumber on paaritu, seega MDNK leian Mcluskey meetodiga ja MKNK Karnaugh kaardiga MKNK leidmine: 6, 8,10, 12,14 ¿ ¿ ¿ 0( 2,4,7,15) ¿ f ( x 1 ... x 4 )= ¿ x3x4 x1x2 00 01 11 10 00 1 1 1 - 01 - 1 - 0 11 0 1 - 0
annaabi.ee 
