Teisendatud kuju määramatuse piirkond: 16CEDE2> 6,14,13,2 f(X1X2X3X4)=(0,1,3,8,11,12)1(2,6,13,14)_ 2. x3x4 x1x2 00 01 11 10 00 - 01 0 0 0 - 11 - 0 - 10 0 0 MKNK f ( x1 x 2 x3 x 4 ) = ( x3 x 4 ) & ( x1 x 2 ) & ( x 2 x3 ) & ( x1 x 3 x 4 ) McCluskey f(x1 ,x2 ,x3, x4 ) = (0,1,3,8,11,12)1(2,6,13,14)- Ind. Nr. Märge Ind. Nr.-d Vahe Märge Ind. Nr.-d Vahe Märge 0 0 X 0-1 0-1 1 X 0-1-1-2 0-1-2-3 1,2 A8 1 1 X 0-2 2 X 2 X 0-8 8 A1
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
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
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
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
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) =
Diskreetse Matemaatika 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. .
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 0
( 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:
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........................................................................................... 5 5.2 TÄIELIK DNK.....
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 Tallinna Tehnikaülikool Nullide piirkond: MKNK: f ( x1 ....x5 ) = x 4 ( x1 x 2 )( x3 x5 )( x1 x 2 x5 )( x1 x3 x5 ) · f ( x1 ...
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
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.
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
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
— 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.....................................................11 5
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 - -
¿ 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 -
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? x pk
Tallinna Tehnikaülikool Diskreetne Matemaatika KODUTÖÖ 142438 Sisukord 1)Martiklinumbrile vastav 4-muutuja loogikafunktsioon.............................................3 2)Tõeväärtustabel............................................................................................................3 3)MDNK ja MKNK, mis sobiksid martiklinumbrist leitud osaliselt määratud 4- muutuja funktsiooni esitamiseks...................................................................................3 4. Teisenda MKNK DNK kujule.......................................................................................5 5. Leida vabaltvalitud viisil MDNK-ga loogiliselt võrdne Taandatud DNK ja Täielik DNK......................................................................................................................
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 -
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.d Vah M
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
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 ..
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
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 MDNK: f(x1,x2,x3,x4) = 2.2 Leian McCluskey meetodiga MKNK: f(x1,x2,x3,x4) = (4,5,7,9,10,11,12,14)0 (6,15)_ Index Intervall Index Intervall Märge Index Intervall Märge Index Intervall Märge 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 0 - 0-1 - 0-1-1-2 - 1 0001 (1) x 1-2 00-1* x 1-2-2-3 0--1* A3 0100 (4) x 0-01 x 01-- A4
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 funktsioonis olid määramatuspiirkonnad ning optimaalsete MDNK ja MKNK leidmiseks kasutasid kumbki määramatuspiirkondi erinevalt. (Erinevused esinevadki ainult algse funktsiooni määramatuspiirkondades) 4. ( x´ 1 V x´4 ¿ ( x´ 2 V x´4 ¿( x2 V x 3 )( x´1 V x´2 V x´3 ¿ =
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
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
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 -
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
muutuja asendamisel konstandiga 0 või 1 ? (sisesta ühesõnaline vastus) Vastus: jääkfunktsioon Küsimus 13 Osaliselt õige - Hinne 0,75 / 1,00 vali kõik õiged väited: Vali üks või enam: McCluskey' meetod on rakendatav suvalise muutujate arvuga funktsioonide minimeerimiseks McCluskey' minimeerimismeetod on algoritmiline meetod, mida saab realiseerida arvutiprogrammina McCluskey' meetodi kleepimisreeglid on MDNK leidmisel ja MKNK leidmisel erinevad McCluskey' meetodi kleepimistabelis tohib kleepida ainult naaberlahtrite sisu McCluskey' meetodiga ei saa leida loogikafunktsiooni Taandatud DNK-d - VALE McCluskey' meetod on rakendatav nii 10ndarvudele kui ka intervallidele Küsimus 14 Õige - Hinne 1,00 / 1,00 Konjunktiivne Shannoni arendus kõigi muutujate järgi annab funktsiooni täieliku KNK Küsimus 15 Õige - Hinne 3,00 / 3,00
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
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
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
Karnaugh kaardi iga kontuur vastab kahendvektori mingile intervallile. Mitu erinevat muutujaväärtuste piirkonda leidub n muutuja karnaugh kaardil? N muutuja kaardil on 2n omavahel kattuvat piirkonda. Milleks karnaugh kaarti kõige enam kasutatakse? Loogikafunktsioonide minimeerimiseks, kuid ta on rakendatav kuni 6-muutuja loogikafunktsiooni korral. Mis on funktsiooni minimeerimine? 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?
ut i x 3 x4 v x 1 x2 00 01 11 10 r Leida MDNK MKNK Reed-Mulleri polünoom järgneval A kaardil esitatud 4-muutuja funktsioonile : 00 1 1 x 3 x4 01 1 x 1 x2 00 01 11 10 u t
McCluskey' meetodi kleepimistabelis tohib kleepida ainult naaberlahtrite sisu McCluskey' meetod on rakendatav suvalise muutujate arvuga funktsioonide minimeerimiseks McCluskey' meetodi kleepimisreeglid on MDNK leidmisel ja MKNK leidmisel erinevad McCluskey' meetodiga ei saa leida loogikafunktsiooni Taandatud DNK-d Question 8 Osaliselt määratud loogikafunktsioonile MKNK leidmisel McCluskey' meetodiga lisatakse Correct määramatuspiirkond selle funktsiooni 0de piirkonnale mille tulemusel
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? DNK saadakse 1-de piirkonnast, KNK 0-de piirkonnast. Kuidas kirjutatakse funktsiooni tõeväärtustabelist välja TDNK või TKNK? TDNK vastavalt 1-de piirkonnast, KNK 0-de piirkonnast. TDNK puhul kirjutad välja terve vastava argumentvektori, sellisel kujul nagu ta on, nt 111=x1x2x3 v ......
1 0 0 0 1 1 0 0 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 0 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 · Ei ole monotoonne. 4. Neljas · MDNK: f = x1 x 2 x3 MKNK: f = ( x1 x3 )( x2 x3 ) Tallinna Tehnikaülikool x1 x 2 x3 = x1 x 2 x3 x1 x 2 x3 = x1 ( x 2 1)( x3 1) x1 ( x 2 1) ( x3 1) = x1 ( x 2 x3 x 2 x3 1) x1 x 2 x1 x3 1 = · x1 x 2 x3 x1 x 2 x1 x3 x1 x1 x 2 x1 x3 1 = x1 x 2 x3 x1 x3 x3 1 · DNK: x3 x1 x 2 x3 = x3 x1 x 2 x3 · MDNK: x1 x 2 x3 = x1 x 2 x3 = x1 x 2 x3 = (( x 2 1) x1 1) x3 1 = ( x1 x 2 x1 1) x3 1 = x1 x 2 x3 x1 x3 x3 1
2.1.2 Katteülesande lahendamine impl. 1 4 5 8 9 10 12 13 A1 x x A2 x x x x A3 x x x x A4 x x x x MDNK f(x1,x2,x3,x4) = x1 x 2 x 4 x 2 x 3 x 3 x 4 2.2 MKNK leidmine Karnaugh' kaardiga F.-ni f(x1,x2,x3,x4) = (0,2,3,6,7,11,14,15) 0 (1,13) Karnaugh' kaart x3x4 x1x2 00 01 11 10 00 0 - 0 0 01 1 1 0 0 11 1 - 0 0
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 𝑥∗𝑥=𝑥 𝑥∨𝑥=𝑥 DeMorgani seadused 𝑥∨𝑦̅̅=𝑥̅∧𝑦̅ 𝑥𝑦̅̅=𝑥̅∨𝑦̅ Neeldumine 𝑥∨𝑥𝑦=𝑥 𝑥∨𝑥̅𝑦=𝑥∨𝑦
1 1 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 0 1 1 1 1 1 1 1 - 1 1 ÜLESANNE 3 3.1 MKNK Karnaugh' kaart F ( X 1 ; X 2 ; X 3 ; X 4 )=∑ (0 ; 2; 5 ; 6 ; 9 ; 11 ; 14)1 (1 ; 3 ; 7 ; 15)¿ 00 01 11 10 00 1 - - 1 01 0 1 - 1 11 0 0 - 1
4 1111 X 0 3 7* 8* 9 12 13 14* 15 A1 X X A2 X X A3 X X A4 X X X X A5 X X X X A1 x2 x3 x4 A2 x1 x3 x4 A4 x1 x3 A5 x1 x2 MKNK f ( x1 , x2 , x3 , x4 ) = ( x2 x3 x4 ) & ( x1 x3 x4 ) & ( x1 x3 ) & ( x1 x2 ) 3. f ( x1 , x 2 , x3 , x 4 ) = ( x 2 x3 x 4 ) & ( x1 x3 x4 ) & ( x1 x3 ) & ( x1 x 2 ) = = ( x1 x 2 x 2 x3 x 2 x 4 x1 x3 x3 x 4 x1 x 4 x 4 x3 ) & & ( x1 x3 x 2 ) = ( x1 x1 x2 x1 x2 x3 x1 x2 x 4 x1 x1 x3 x1 x3 x 4 x1 x1 x 4 x1 x4 x3 x1 x 2 x3 x 2 x 2 x3 x3 x 2 x 2 x4 x3 x2 x1 x3 x3 x 2 x3 x 4 x3 x 2 x1 x4 x3 x2 x4 x3 x3 x2 ) =
-1- 01 0 0 1 1 11 0 - 0 1 10 0 1 - 1 MDNK: x1 x 2 x 4 x1 x3 x 4 x1 x3 x 4 x1 x 2 x 4 x1 x 2 x3 x 4 f(x1,x2,x3,x4) = 2.2 MKNK McCluskey' meetodiga: Index Intervall Märge Index Intervall Märge Index Intervall Märge -11- A1 0 1111 X 0-1 111- X 0-1-1-2 1-1- A2 11-- A3
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 MKNK McCluskey´ meetodiga: Indeks Intervall K? Intervall K? Intervall K? 0 0000 X 000- X -00- A1 0001* X 00-0 X -0-0 A2 1 0010 X -000 X 1000* X -001 X 1-0- A3
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 𝑥∗𝑥 =𝑥 𝑥∨𝑥 =𝑥 ̅̅̅̅̅̅̅
2 0 1 0 1 0 3 0 1 1 1 0 4 1 0 0 0 1 5 1 0 1 1 0 6 1 1 0 0 1 7 1 1 1 0 1 · Minimaalse keerukusega DNK-d (KNK-d) nimetatakse minimaalseks DNK-ks (KNK-ks). Lühenditena vastvalt MDNK ja MKNK. Ülesanne (x1 ) ( x2 x3 ) ( x1 x2 ) 12 Leida antud loogikafunktsiooni MDNK, MKNK, TDNK, TKNK. Minimeerimine normaalkujude klassis Boole'i ruum {0,1}n all mõistame järgnevas kõikvõimalike kahendvektorite (x1 ,x2 ,...,xn ) hulka. Hüperkuupi (n-mõõtmelist kuupi) esitame kui graafi, mille iga tipp vastab üks-üheselt ruumi {0,1}n ühele vektorile ja 2 tippu on omavahel seotud, kui vastavad vektorid on
2 0 1 0 1 0 3 0 1 1 1 0 4 1 0 0 0 1 5 1 0 1 1 0 6 1 1 0 0 1 7 1 1 1 0 1 Minimaalse keerukusega DNK-d (KNK-d) nimetatakse minimaalseks DNK-ks (KNK-ks). Lühenditena vastvalt MDNK ja MKNK. Ülesanne x x 1 2 x3 x1 x2 Leida antud loogikafunktsiooni MDNK, MKNK, TDNK, TKNK. Minimeerimine normaalkujude klassis Boole'i ruum {0,1}n all mõistame järgnevas kõikvõimalike kahendvektorite (x1 ,x2 ,...,xn ) hulka. Hüperkuupi (n-mõõtmelist kuupi) esitame kui graafi, mille iga tipp vastab üks-üheselt ruumi {0,1}n ühele vektorile ja 2 tippu on omavahel seotud, kui vastavad vektorid on ortogonaalsed (s.o
annaabi.ee 
