& ( 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 ) Lahendasin Karnaugh' järgi: x3x4 x1x2 00 01 11 10 00 01 0 0 0 0 11 0 0 0 10 0 0 6. MDNK Shannoni disjunktiivne arendus f(x 1 , x 2 , x 3 , x 4 ) = x1 x 2 x1 x3 x 4 x 2 x 3 x 4 = x1 x 2 x3 x 4 (1 0 0 0 0 0 1 1) x1 x 2 x 3 x 4 (0 1 1 0 0 1 1 1) x1 x 2 x 3 x 4 (0 0 1 1 0 0 0 1) x1 x 2 x3 x 4 (0 0 1 0 1 0 1 0) x1 x 2 x3 x 4 (1 1 0 0 0 1 1 1) x1 x 2 x 3 x 4 (0 1 1 1 0 1 0 1) x1 x 2 x 3 x 4 (0 0 1 1 1 0 0 0) x1 x 2 x3 x 4 (1 0 0 0 1 0 1 0) x1 x 2 x 3 x 4 (0 1 1 0 1 1 1 0) x1 x 2 x 3 x 4 (1 0 0 1 0 0 0 1) x1 x 2 x3 x 4 (1 1 0 1 0 1 0 1)
numbrilises 10nd esituses: 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
Tallinna Tehnikaülikool Diskreetne matemaatika KODUTÖÖ Kristjan Keskküla 093540 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
piirkonda, moodustavad funktsiooni määramatuspiirkonna. Seega on 4-muutuja loogikafunktsiooni määramatuspiirkonnaks(numbrilises 10ndesituses): 9 8 4 5 13 (2 määramatuspiirkonda ei kuulu, sest see kuulub juba 1-de piirkonda) Seega oleks matriklinumbrile 112799 vastav 4-muutuja loogikafunktsioon oma numbrilises 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
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) =
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 0-2 2 A2 1 1 x 2 x 1-2 1-5 4 x
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..............
Tallinna Tehnikaülikool 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
Matrikli number on 104493 Ühtede piirkonna määramiseks saadud 16-nd arv on 28DD194D Seega on ühtede piirkond f(x1,x2,x3,x4) = (1,2,4,8,9,13)1 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.
( 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:
1 0 0 1 - 1 0 1 0 0 1 0 1 1 - 1 1 0 0 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 0 3. Leida MDNK (minimaalne DNK) ja MKNK (minimaalne KNK), mis sobiksid matriklinumbrist leitud osaliselt määratud 4- muutuja funktsiooni esitamiseks. 2 Paarisarvulise matriklinumbriga õpilased leiavad MKNK Karnaugh' kaardiga ja MDNK McCluskey' meetodiga. Leian MKNK Karnaugh' kaardiga Y X3 X4 00 01 11 10 00 1 1 1
x ( TaDNK ) k 0 0 1 1 0 n i MDNK ja TaDNK võivad olla (osadel funktsioonidel) sama avaldis. h 1 1 1 0 0 Kui MDNK ja TaDNK on teineteisest erinevad avaldised, siis MDNK t e sisaldub TaDNK sees. i . . . . on 7 implikanti :
1 0 0 0 - 1 0 0 1 1 1 0 1 0 1 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?
TDNK: 4 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 x4 ) x1 x2 x3 x4 x1 x2 x3 x4 x1 x2 x4 ( x3 x3 ) x1 x2 x3 x1 x2 x3 x4 x1 x2 x3 x4 x1 x2 x4 f D x2 x3 x1 x3 x4 x1 x2 x3 x1 x2 x4 MDNK: f x1 x2 x3 x1 x2 x3 x4 x1 x2 x3 x4 x1 x2 x4 Lihtsustatud TDNK: Punktis 3 leitud MDNK ja lihtsustamisel saadud DNK ei ole võrdsed. MDNK on väiksema keerukusega, sest ta koosneb kolmest kolme sisendiga elemendist ja ühest kahe sisendiga elemendist, samas kui lihtsustamisel saadud DNK koosneb kahest nelja sisendiga elemendist ja kahest kolme sisendiga elemendist. 6
0 0 0 0 - 3)MDNK ja MKNK, mis sobiksid 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
1 0 1 1 0 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
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 Osaliselt määratud loogikafunktsioonile MDNK leidmisel McCluskey' meetodiga lisatakse selle funktsiooni mille tulemusel saadakse määramatuspiirkond 1de piirkonnale laiendatud 1de piirkond Küsimus 4 Õige - Hinne 1,00 / 1,00 Kuidas nimetatakse funktsiooni sellist implikanti, mis ei sisaldu (tervikuna) selle funktsiooni mitte üheski teises (suuremas) implikandis? (sisesta ühesõnaline vastus) Vastus: lihtimplikant
Karnaugh' kaardi iga kontuur vastab kahendvektorite mingile intervallile: Kaardi piirkondi võib tähistada vastavalt: x¯1 x1 x¯2 x2 .......... x¯n xn Piirkondade suurus Ü Iga piirkond on täpselt "pool kaarti" suur ehk tema koosseisu kuuluvad Leida Karnaugh' kaardiga MDNK MKNK 4-muutuja funktsioonile: T (suvalise kaardi korral) täpselt pooled kaardi kõikidest ruutudest. f ( x1 . . . x4 ) = ( 1, 4, 5, 9, 11, 12, 13, 15 ) 0 ( 3, 14 ) — T Piirkonnad kattuvad omavahel. Järgmisel joonisel on näidatud 3-muutuja kaardi kõik 6 piirkonda (igaühe suurus on 4 ruutu) ja
¿ f ( x 1 ... x 4 )= ¿ Nullide piirkond: 6, 8, 10, 12, 14 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 -
0 1 1 1 0 1 0 0 0 0 1 0 0 1 - 1 0 1 0 1 1 0 1 1 0 1 1 0 0 - 1 1 0 1 0 1 1 1 0 - 1 1 1 1 - 3. Leida Karnaugh' kaardiga MDNK (minimaalne DNK) ja MKNK (minimaalne KNK), mis sobiksid matriklinumbrist leitud osaliselt määratud 4-muutuja funktsiooni esitamiseks. 1. Leian MDNK: 00 01 11 10 x1 x3 x2 x4 00 0 - 1 1 01 1 - 0 - 11 - 0 - -
16ndarvu tuleb korrutada 7-ga veel niimitu korda, kuni arv kasvab 9-järguliseks — ehk tuleb vajutada järjest =-märki veel paar korda, kuni 16ndarv kasvab 9- kohaliseks:........................................................................................................... 7 2. Kirjutada välja oma matriklinumbrist leitud osaliselt määratud 4-muutuja loogikafunktsiooni tõeväärtustabel.........................................................................8 3. Leida MDNK (minimaalne DNK) ja MKNK (minimaalne KNK), mis sobiksid matriklinumbrist leitud osaliselt määratud 4-muutuja funktsiooni esitamiseks......8 4. Kirjutada oma funktsiooni 1-de piirkonnast välja täielik DNK (TDNK) (ignoreerides määramatuspiirkonda)...................................................................10 5. Lihtsustada loogikaalgebra põhiseoste abil eelnevalt leitud täielikku DNK-d lihtsaima DNK-ni, milleks see TDNK lihtsustub...................................................
MAHB-11 Tallinn 2009 1. Leida oma matriklinumbrile vastav 4-muutuja loogikafunktsioon. Matrikli number on 082784 Ühtede piirkonna määramiseks saadud 16-nd arv on 205FBF60 Ühtede piirkond on seega f(x1,x2,x3,x4) = (0,2,5,6,11,15) 1 Määramatuspiirkonna määramiseks saadud 16-nd arv on 1E783BA Määramatuspiirkond on seega f(x1,x2,x3,x4) =(1,3,7,8,10,14) 2. Leida selle funktsiooni MKNK Karnaugh' kaardiga ja MDNK McCluskey' meetodiga. MKNK: x3x4 x1x2 00 01 11 10 00 1 - - 1 01 0 1 - 1 11 0 0 1 - 10 - 0 1 -
implikatsioon konjunktsioon disjunktsioon ekvivalents Question 2 Osaliselt määratud loogikafunktsioonile MDNK leidmisel McCluskey' meetodiga lisatakse 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
a {& 1} 10 1 1 ik polünoomis ei sisaldu tehteid disjunktsioon ja inversioon n MDNK jaoks parimad kontuurid h Igal loogikafunktsioonil on täpselt üks Reed-Mulleri polünoom. e MDNK : f = ¯3 x x ¯4 w x1 x2 w ¯2 x 3 x4
6 0 1 1 0 0 7 0 1 1 1 1 8 1 0 0 0 1 9 1 0 0 1 0 10 1 0 1 0 0 11 1 0 1 1 0 12 1 1 0 0 1 13 1 1 0 1 0 14 1 1 1 0 1 15 1 1 1 1 1 Graaf 2.1 2 LAHENDATAVAD ÜLESANDED 3. Matrikli number on paarisarvuline. Leidmine MDNK Karnaugh kaardiga ja MKNK McCluskey meetodiga. MDNK leidmine Karnaugh kaardiga. Funktsiooni (x1,x2,x3,x4)= (3, 7, 8, 12, 14, 15) (1, 2, 4, 5)_ x3x4 x1x2 00 01 11 10 00 0 - 1 - 01 - - 1 0 11 1 0 1 1 10 1 0 0 0
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
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
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
0 0 0 1 0 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
0 0 0 1 0 ( 2,3,4,6,10,12 )1 ( 0,5,9,13 )-¿ 0 0 1 0 1 2. f ( x1 , x2 , x3 , x 4 ) = ¿ 0 0 1 1 1 0 1 0 0 1 0 1 0 1 -- 0 1 1 0 1 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 1 0 1 -- 1 1 1 0 0 1 1 1 1 0 3. MDNK : ´x 3 x 2 x´ 1 ´x2 x 3 ´x 2 x 3 x´ 4 ´x 1 x´ 4 Karnaugh-iga MDNK McCluskey' meetodiga: A3 on üleliigne kuna teised katavad juba selle piirkonnad ära. Jäävad A2, A2, A4, A5 ehk: 1--1; -1-1; -00-; 111-, millest saame järgmise MKNK ( x´ 1 V x´4 ¿ ( x´ 2 V x´4 ¿ ( x 2 V x 3 )( x´1 V x´2 V x´3 ¿ Võrdlen MDNK ja MKNK tõeväärtustabeleid: MDNK ja MKNK tõeväärtustabelid on kohati erinevad, kuna esialgses
0 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1 1 - 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 0 1 1 1 0 1 0 0 0 0 1 0 0 1 1 1 0 1 0 - 1 0 1 1 1 1 1 0 0 - 1 1 0 1 - 1 1 1 0 1 1 1 1 1 - 3) MDNK Karnaugh’ kaardi abil: x3 x1 x4 00 01 11 10 x2 00 1 0 - 1 01 0 0 0 0 11 - - - 1 10 0 1 1 - MDNK ¿ f ( x 1 … x 4 )=´x 1 ´x 2 x´ 4 V x 1 x 4 V x 1 x3 MKNK McCluskey meetodi abil: Indeks Intervall Märge Indeks Intervallid Märge Indeks Intervall Märge
1000 0 1001 0 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
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
1001 0 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
0 1 0 0 1 0 1 0 1 0 0 1 1 0 0 0 1 1 1 1 1 0 0 0 - 1 0 0 1 0 1 0 1 0 0 1 0 1 1 1 1 1 0 0 - 1 1 0 1 0 1 1 1 0 1 1 1 1 1 - 3. Leida MDNK ja MKNK: MDNK - Karnaugh´kaardiga ja MKNK McCluskey meetodiga. 1). MDNK? f(x1, x2, x3, x4) = 1 0 1 1 (0,2,3,4,7,11,14)1(8,12,15)_ 1 0 1 0 00 01 11 10 - 0 - 1 00 - 0 1 0 01
Loogikafunktsiooni minimeerimine on tema esitamine minimaalse keerukusega normaalkujul, kas MDNK või MKNK. Kuidas kasutatakse karnaugh kaarti funktsiooni minimeerimisel? 4 etappi: Paigutatakse funktsiooni tõeväärtustabel karnaugh kaardile Katta kaardil kõik 1-d (MDNK) või kõik -d(MKNK) võimalikult väikse arvu ja võimalikult suurte kontuuridega. Leida iga valitud kontuuri jaoks tema ulatuses konstantsed muutujad xi Kirjutada kontuuride konstantsete muutujate järgi välja MDNK elementaarkonjuktsioonid või MKNK elementaardisjunktsioonid. Milline loogikafunktsioon on nõrgalt määratud? Suure määramatuspiirkonnaga osaliselt määratud funktsioone nimetatakse nõrgalt määratud loogikafunktsioonideks. Millised intervallid on ortogonaalsed? Intervallid on ortogonaalsed, kui nad ei oma ühisosa. 2 intervalli on ortogonaalsed, kui ei leidu sellist kahendvektorit, mis kuuluks samaaegselt mõlemasse intervalli. Mis on ortogonaalsustehe? Millele teda rakendatakse?
00 1 - - 1 01 0 1 - 1 11 0 0 - 1 10 0 1 1 0 F ( X 1 ; X 2 ; X 3 ; X 4 )=( X´ 2 V X 3 V X 4 ) ∧( X´ 1 V X´ 2 V X 3 )∧( X´ 1 V X 2 V X 4 ) 3.2 MDNK McCluskey meetod F ( X 1 ; X 2; X 3 ; X 4 )=∑ (0 ; 2 ; 5 ; 6 ; 9 ;11 ; 14 )1 (1; 3; 7; 15)_ 2. 4. INDEK 1. K INTERVAL K INTERVAL K S PIIRKOND
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.1 Lihtimplikantide hulga leidmine implikant konjunktsioon, mis vastab funktsiooni ühtede intervallile ind nr mrg. ind. nr.-d vahe mrg. ind. nr.-d vahe mrg 1 1* x 1-2 1*-5 4 x 1-2-2-3 1*-9-5-13* 4,8 A2 4 x 1*-9 8 x 4-5-12-13* 1,8 A3
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
121055 IASB 13 Tallinn 2012 1. Leida oma matriklinumbrile vastav 4-muutuja loogikafunktsioon. Matrikli number 10. süsteemis: 121055 Matrikli number 16. Süsteemis: 8-kohaline arv: 2F572B3F 4-muutuja loogikafunktsiooni 1de piirkond: 2, 15, 5, 7, 11, 3 2F572B3F/11=2C8E46D Määramatuspiirkond: 12, 8, 14, 4, 6, 13 (x1...x4) = (2, 3, 5, 7, 11, 15)1 (4, 6, 8, 12, 13, 14)_ 2. Leida MDNK ja MKNK, mis sobiksid matriklinumbrist leitud osaliselt määratud 4- muutuja funktsiooni esitamiseks. X3,X4 00 01 11 10 X1,X2 00 0 0 1 1 01 - 1 1 - 11 - - 1 - 10 - 0 1 0 __ (X1,X2,X3,X4)=( X2 X3 X4 X1 X3) - MDNK Index Number Märge Index Nr.d Vahe M Index Nr
0 1 1 1 1 1 0 0 0 0 1 0 0 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 1 Tallinna Tehnikaülikool 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 · Jah on küll ja seda näitab MDNK 2. · f ( x1 x2 x3 ) = x1 x3 x2 x3 x1 x3 x1 x2 Lihtsaim loogikaskeem on: f = x1 x3 · f on kahe muutujaga funktsioon. · JA-EI skeem f = x1 x3 = f = x1 x3 = x1 x3 · VÕI-EI skeem f = x1 x3 = x1 x3 · x1 x3 = x1 x3 = x1 x3 = ( x1 ( x3 1)) 1 = x1 x3 x1 1 · f ei ole nulli säilitatav. · 1 1 0 = 0 1 , f ei ole lineaarne. 3.
i t 14* ut 4 r v 10ndmodifikatsiooni esimese kleepimissammu kleepimisreeglid: Leida McCluskey' meetodiga MDNK ja MKNK eelnevalt A 1. kleepida saab ainult naaberlahtrite arve Karnaugh' kaardi abil minimeeritud osaliselt määratud funktsioonile: 2. kleebitavate arvude väärtuste vahe peab olema 2n (1 2 4 8 16 32 . . . ) f ( x1 ..
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,
Tallinna Tehnikaülikool Diskreetne Matemaatika KAUGÕPE 3.arvestustöö Tallinna Tehnikaülikool Lk.231-232 ülesanded · f ( x1 ....x 4 ) = (3,4,7,12,14)1 (0,5,6,8,15)_ Ühtede piirkond: MDNK: f ( x1 ....x 4 ) = x 2 x 4 x1 x3 x 4 Nullide piirkond: MKNK: f ( x1 ....x 4 ) = ( x1 x 2 )( x 2 x 4 )( x3 x 4 ) MKNK: f ( x1 ....x 4 ) = ( x1 x 4 )( x 2 x 4 )( x3 x 4 ) MKNK: f ( x1 ....x 4 ) = ( x1 x 4 )( x 2 x 4 )( x 2 x3 ) · f ( x1 ....x5 ) = (0,1,4,9,25,28)1 (5,13)_ Ühtede piirkond MDNK: f ( x1 ....x5 ) = x1 x 2 x 4 x 2 x3 x 4 x5 x1 x 2 x3 x 4 x5
Antud kuueteistkümmendarv kaheksakohalisena oleks 24D9BD77 1-de piirkond on mul seega: 2 4 7 9 11 13 Jagades kaheksakohaline kuueteistkümmendarv 11'ga saan tulemuseks 22AED07 Määramatuspiirkond on mul seega: 0 10 14 Seega oleks matriklinumbrile 094231 vastav 4-muutuja loogikafunktsioon oma numbrilises 10ndesituses: f(x1,x2,x3,x4) = (2, 4, 7, 9, 11, 13)1 (0, 10, 14)_ f(x1,x2,x3,x4) = (1, 3, 5, 6, 8, 12, 15)0 (0, 10, 14)_ 2. Ülesanne 2.1 MDNK Karnaugh' kaardiga: x3x4 x1x2 00 01 11 10 0 00 0 1 -1- 01 0 0 1 1 11 0 - 0 1
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 1 2 (0010) X 0-4 (0-00) 4 X 4 (0100) X 0-8 (-000) 8 X 8 (1000) X 1-2 2-3 (001-) 1 A
vali kõik õiged väited: Vali üks või enam: McCluskey' meetodiga ei saa leida loogikafunktsiooni Taandatud DNKd McCluskey' meetodi kleepimistabelis tohib kleepida ainult naaberlahtrite sisu McCluskey' minimeerimismeetod on algoritmiline meetod, mida saab realiseerida arvutiprogrammina McCluskey' meetod on rakendatav nii 10ndarvudele kui ka intervallidele McCluskey' meetod on rakendatav suvalise muutujate arvuga funktsioonide minimeerimiseks McCluskey' meetodi kleepimisreeglid on MDNK leidmisel ja MKNK leidmisel erinevad Küsimus 3 Õige Hinne 3,00 / 3,00 Osaliselt määratud loogikafunktsioonile MDNK leidmisel McCluskey' meetodiga lisatakse Vasta selle funktsiooni Vasta mille tulemusel määramatuspiirkond 1de piirkonnale saadakse laiendatud Vasta 1de piirkond Küsimus 4 Õige Hinne 1,00 / 1,00
4-muutuja loogikafunktisooni määramatuspiirkond: 1, 8, 12, 15 4-muutuja loogikafunktisooni 0de piirkond: 0, 2, 9, 10, 13 2. f(x1x2x3x4) = ∑(3, 4, 5, 6, 7, 11, 14)1 (1, 8, 12, 15)_ x1x2x3 f x4 0000 0 0001 - 0010 0 0011 1 0100 1 0101 1 0110 1 0111 1 1000 - 1001 0 1010 0 1011 1 1100 - 1101 0 1110 1 1111 - 3. MDNK leidmine Karnaugh´ kaariga: 00 01 11 10 00 0 − 1 0 01 1 1 1 1 11 − 0 − 1 10 − 0 1 0 MDNK: f(x1x2x3x4) = ´x 1 x 2 v x 3 x 4 v x 2 ´x 4
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 ? Karnaugh' kaardi igal ruudul on täpselt 1 naaberruut Vali üks: ...
KONTROLLKÜSIMUSTEGA TEST - funktsioonide normaalkujude mi... file:///C:/Users/CPU/Desktop/Diskmati_TESTID_moodle__'s_-_100%... Diskreetne Matemaatika You are logged in as Alger Abna (Logout) Home My courses IAY0010 Topic 10 KONTROLLKÜSIMUSTEGA TEST - funktsioonide normaalkujude minimeerimine Review of attempt 3 Started on Thursday, 1 December 2011, 06:17 PM Quiz navigation Completed on Thursday, 1 December 2011, 06:23 PM 1 2 3 4 5 6 Time taken 5 mins 36 secs 7 8 9 10 11 12 Marks 22.00/22.00 ...