Leidsid 33 sarnast õppematerjali, mis on seotud failiga "Diskreetne Matemaatika kodutöö". Need materjalid aitavad sul teemat sügavamalt mõista.
muutuja, xxxx, indek, märg, tõeväärtustabel, 0101, 0111, 1001, 1011, 1101, 1111, shannoni, matriklinumber, 1010, karnaugh, lihtimplikant, disjunktiivne, diskreetne, matemaatika, määramiseks, loogikafunktsioon, mcluskey, kaardiga, laiend, teisendamine, kujule, lihtimplikantide, disjunktsioon, sisaldada, konjunktiivne, tuletis, reed****** Detsember 2015 1. Minu matriklinumbrile (155423) vastav loogikafunktsioon oma 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:
Diskreetne matemaatika KODUTÖÖ Mina Ise 132456 IADB?? Tallinn 2019 ÜLESANNE 1 LOOGIKAFUNKTSIOON Leian oma matriklinumbrile vastav 4-muutuja loogikafunktsioon Matriklinumbri 5 viimast numbrit: 93656 Matriklinumber kuueteistkümnendsüsteemis: 2F478 Seitsmekohaline arv: 3F58CC8 Üheksakohaline arv: 54DFF9FF8 Ühtede piirkond: 3, 5, 8, 12 ( C16 ), 15 ( F16 )/ 0011, 0101, 1000, 1100, 1111 Määramatuspiirkond : 4, 9, 13 ( D16 ) / 0100, 1001, 1101 0-de piirkond : 0, 1, 2, 6, 7, 10 ( A16 ), 11 ( B16 ), 14 ( E16 ) / 0000, 0001, 0010, 0110, 0111, 1010, 1011, 1110 𝒇(x(x1,x2,x3,x4) = ∑ ( 3, 5, 8, 12, 15 )1 ( 4, 9, 13 )_ 𝒇(x(x1,x2,x3,x4) = ∏ ( 0, 1, 2, 6, 7, 10, 11, 14 )0 2 ÜLESANNE 2 TÕEVÄÄRTUSTABEL Esitada oma loogikafunktsiooni tõeväärtustabel.
tõeväärtustabeleid, et teada saada kas disjunktsioonkuju avaldised on loogiselt võrdsed. Loogiliselt võrdsed funktsioonid väljastavad iga argumentvektori korral võrdsed väärtused. x1x2x3x4 Funktsioon f Funktsioon f1 0000 1 1 0001 1 1 0010 0 0 0011 0 0 0100 0 0 0101 0 0 0110 1 1 0111 1 1 1000 0 0 1001 1 1 1010 0 0 1011 1 1 1100 0 0 1101 1 1 1110 0 0 1111 0 0 Tabelist selgub, et funktsioon f ja funktsioon f1 on loogiliselt võrdsed. ÜLESANNE 4 Leida vabaltvalitud viisil punktis 2 saadud MDNK-ga loogiliselt võrdne Taandatud DNK ja Täielik DNK 1) Leian taandatud DNK Kannan Karnaugh' kaardile funktsiooni elemendid ning väärtustan määramatused 1-ga.
10 1 1 0 0 MDNK: f(, , , ) = v v v MKNK McCluskey meetodiga f(, , , ) = Indek Nr Indeks Intervall Märge Intervall Märge s 3 *0011 x -011 A1 5 0101 x 2-3 -101 A2 2 6 *0110 x 110- A3 10 1010 x 101- A4 12 1100 x 3-4 1-11 A5 11 1011 x 11-1 A6 3 13 1101 x 4 15 *1111 x Lihtimplikantide hulga minimeerimine: 5 10 11 12 13 A1 x
-1-0 A3 3-4 -100 X 01-1 X 0101 X 011- X 0110* X 10-1 A1 2-3-3-4 -11- A4 2 1001 X 2-3 101- X 1-1- A5 1010 X -110 X 1100 X 1-10 X 11-0 X 0111 X 3 1011 X 1110 X -111 X 3-4 1-11 X
0-00 X 1 0001 X 0-01 X --01 A3 0010 0-10 X 0100 -001 X -010 X 010- X 01-0 X 2 0101 X -101 X 0110 X 10-1 A 1001 X 1-01 4 1010 X 101- X A 5 3 1011 X 1101 X 4 Graaf 3.2 3 Lihtimplikantide hulga minimeerimine.
0 - - - - - - 1 0001 X 0-01 X --01 A3 -001 X 2 0101 X -101 X 0110 A1 1-01 X 1001 X 1010 A2 3 1101 X 4 - - - - - - 1 5 6 9 10 13 A1 X A2 X
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 11 1 1 1 0 1001 1 10 0 1 0 11010 1 1011 0 1100 1 1101 1 1110 0 1111 1 V¹={0001,0010,0100,0101,1001,1010,1100,1101,1111} (kõik välja kirjutada)
....................................................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 ....................................... 8 Vastused................................................................................................................8 1. Funktsiooni leidmine 1.1 Funktsiooni arvutamine Matrikli number on 010636 Pärast selle teisendamist kuueteistkümnendsüsteemi 'Windows Calculatoris' saan tulemuseks arvu 298C Leian funktsiooni ühtede piirkonna ja määramatuspiirkonna:
0010 1 0011 1 0100 - 0101 1 0110 0 0111 0 1000 0 1001 0 1010 0 1011 - 1100 0 1101 1 1110 1 1111 1 3. Leida MDNK ja MKNK
1000* X 1-2 00-1* X 0-1- X 0-01 X -01- X 2 0011* X 001- X --10 X 0101 X 0-10 X 2-3-3-4 --11 X 0110 X -010 X -11- X 1010* X 10-0* X 1-1- X 3 0111* X 2-3 0-11* X 1011 X -011X X 1110* X 01-1 X 011- X 4 1111 X -110 X 101- X 1-10 X 3-4 -111 X 1-11 X 111- X Katteülesande lahendamine: i 0 2 5 6 1 15 1 A1 X X A2 X X A3 X
0100 (4) X -010 X 2-3 10-- A7 1000 (8) * X 010- A1 100- X 10-0 X 2 0011 (3) X 2-3 0-11 A2 0101 (5) X -011 X 1001 (9) X 01-1 A3 1010 (10) X -101 A4 10-1 X 1-01 A5 101- X 3 0111 (7) * X 1011 (11)* X 1101 (13)* X
M Ind 2-sed intervallid M Ind 4-sed d intervallid 0 0000 X 0-1 -000 A1 0-1-1-2 1 1 0 0 0* X 1-2 100- X 1-2 1 - 0 - A4 1-00 X 2-3 2 0011 X 2-3 0-11 A2 2-3-3-4 1 1 - - A5 1001 X 1-00 X 1 1 1 0* X 11-0 X 110- X 3 0 1 1 1* X 3-4 -111 A3 1101 X 11-1 X 1 1 1 0* X 111- X 4 1111 X 0 3 7* 8* 9 12 13 14* 15 A1 X X
MDNK ja DNK ei ole võrdsed. MDNK on lihtsam, kuna DNK leidmisel ei arvestatud määramatuspiirkonnaga. 6. Leida ja näidata, milleks (0 või 1) väärtustuvad (punktis 3) leitud MDNK ja MKNK määramatuspiirkonna kõikide argumentvektorite korral. Otsustada (hinnata), kas leitud MDNK ja MKNK on teineteisega võrdsed või mitte. X1 X2 X3 X4 fD fK 1 0001 0 0 5 0101 0 1 6 0110 1 0 9 1001 0 0 12 1100 1 1 14 1110 1 0 15 1111 0 0 Antud tabelist selgub, et leitud MDNK ja MKNK ei ole teineteisega võrdsed. 7. Realiseerida (punktis 3) MDNK-na saadud loogikafunktsioon minimaalseima keerukusega loogikaskeemina, kasutades vabaltvalitud loogikaelemente AND OR ja NOT. Esmalt lihtsustan veidi loogikafunktsiooni tuues 4 sulgude ette: fD = (x2 4) v ( 1 2x3) v (x3 4) 4(x2 v x3) v ( 1 2x3).
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
...... 5 ÜLESANNE 4 MKNK TEISENDAMINE DNK-KUJULE....................................5 ÜLESANNE 5 DISJUNKTIIVSED NORMAALKUJUD.....................................5 5.1 TAANDATUD DNK........................................................................................... 5 5.2 TÄIELIK DNK.................................................................................................. 6 ÜLESANNE 6 TÄIELIK KNK....................................................................6 ÜLESANNE 7 SHANNONI DISJUNKTIIVNE ARENDUS KOLME MUUTUJA JÄRGI..................................................................................................6 ..........................................................................................................7 ÜLESANNE 8 SHANNONI DISJUNKTIIVNE ARENDUS KAHE MUUTUJA JÄRGI7 ÜLESANNE 9 SHANNONI KONJUNKTIIVNE ARENDUS...............................7 ÜLESANNE 10 TULETISED.....................................................................8
1-00 K A 5 A 6 A 7 2 0011 K 0-11 K 1001 K 1-01 K 1010 K 1-10 K 0101* K -101 K 0110* K 01-1 K 1100* K 011- K 3 1101 K -110 K 0111* K 110- K 1110* K 11-0 K 4 1 3 4* 5* 6* 7* 8* 9 10 12 13 14
Kontuuride valiku reegel tasub sõnastada lihtsustatud kujule: 01 0100 0101 0111 0110 a kõik 1-d tuleb katta (võimalikult suurte) mittelõikuvate kontuuridega k 11 1100 1101 1111 1110 (misjuhul saavad kõik 1-d olema kontuuridega kaetud 1-kordselt) h n i Katame antud kaardil kõik 1-d mittelõikuvate kontuuridega : 10 1000 1001 1011 1010 t e x 3 x4 x 3 x4 i
0001 1 0010 1 0011 1 0100 1 0101 0 0110 1 0111 - 1000 0 1001 0 1010 0 1011 0 1100 1 1101 0 1110 0 1111 0 3. Leida MDNK ja MKNK, mis sobiksid matriklinumbrist
A4 1, 4 1 - 1 - x1 x3 Täieliku DNK saab välja kirjutada eelnevalt leitud MDNK tõeväärtustabeli ühtede piirkonnast. f ( x 1 … x 4 )=¿ xx 1 xx 2 xx 3 xx 4 V xx 1 xx 2 x3 xx 4 v x 1 xx 2 xx 3 x 4 V x 1 xx 2 x 3 xx 4 V x 1 xx 2 x 3 x 4 V x 1 x 2 xx 3 x 4 V x 1 x 2 x3 xx 4 V x1 x 2 x 3 x 6) MKNK = ( ´x 1 V x 2 V x 4 ) ( x 1 V ´x 4 ) ( x1 V ´x2 ) x 3 on mitteoluline muutuja. f ( x 1 , x 2 , x 4 )=( ´x 1 V x 2 V x 4 ) ( x 1 V ´x 4 ) ( x 1 V ´x 2) = = ( ´x 1 V x 2 V x 4 ) ( x 1 V x´ 2 ) ( x 1 V ´x 2 V x´ 4 ) ( x 1 V x 2 V x´ 4 ) = = ( ´x 1 V x 2 V x 4 ) ( x 1 V ´x2 V x´ 4 )( x1 V x´ 2 V x 4 )( x 1 V x 2 V x´ 4 ) ´x 1 ´x 2 ´x 4 V x1 x 4 V x 1 x 3 7) MDNK = Kõige rohkem x 1 , seega Shannoni arendus x 1 järgi avaldisele f =´x 1 ´x 2 ´x 4 V x1 x 4 V x 1 x 3
1. Matriklinumber: 164780 Matriklinumber 16ndsüsteemis: 283AC 7-kohaline arv: 35E6B74 4-muutuja loogikafunktisooni 1de piirkond: 3, 4, 5, 6, 7, 11, 14 9-kohaline arv: 48381F86C 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
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 2 - muutuja 3 - muutuja 4 - muutuja Karnaugh' kaart Karnaugh' kaart Karnaugh' kaart A Karnaugh' kaardil on 2 põhiomadust.
...3 4. Teisenda MKNK DNK kujule.......................................................................................5 5. Leida vabaltvalitud viisil MDNK-ga loogiliselt võrdne Taandatud DNK ja Täielik DNK...................................................................................................................................6 6.MKNK-ga võrdne Täielik KNK......................................................................................7 7.Shannoni disjunktiivne arendus rohkeima muutuja järgi........................................8 8. Shannoni disjunktiivne arendus 1 muutuja järgi.....................................................8 9.Shannoni konjuktiivne arendus MDNK-le 2 muutuja järgi.......................................8 10.Tuletis kõigi nelja muutuja järgi................................................................................8 10.1.x1 järgi:................................................................................................................
1000 A1 01-0 x 2 0101 x 2-3 01-1 x 2-3-3-4 -1-1 A5 0110 x -101 -11- A6 011- x -110 3 0111* x 3-4 -111 1011 x 1-11 3 1101 x 11-1 1110* x 111- 4 1111 x 0001 0100 0101 0110 0111 1000 1011 1101 1110 1111 1 4* 5 6 7* 8 11 13 14* 15 A1 0
Tallinna Tehnikaülikool Diskreetne Matemaatika KODUTÖÖ ÜLESANNE 1 Leida martiklinumbrile vastav 4 – muutuja loogikafunktsioon. F ( X 1 ; X 2 ; X 3 ; X 4 )=∑ (0 ; 2; 5 ; 6 ; 9 ; 11 ; 14)1 (1 ; 3 ;7 ; 15)¿ (4 ; 8 ; 10 ; 12 ; 13)0 ÜLESANNE 2 MDN MKN X1 X2 X3 X4 F K K
0001 1 0010 1 0011 1 0100 1 0101 - 0110 - 0111 0 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
4 00 1 0 1 1 01 1 0 0 0 11 1 - 0 1 10 -1 1 -1 0 Täielik DNK: x1x2x3x 00 01 11 10 4 00 1 0 1 1 01 1 0 0 0 11 1 - 0 1 10 -1 1 -1 0 5. Täielik KNK: x1x2x3x 00 01 11 10 4 00 1 0 1 1 01 1 0 0 0 11 1 - 0 1 10 - 1 -0 0 6. Shannoni disjunktiivne arendus (x1x2x4 järgi) = = 7. Shannoni disjunktiivne arendus (1 muutuja järgi) = 8. Shannoni konjunktiivne arendus (järgi) & & =[ 9. Reed-Mulleri polünoom
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 -110 X 1110* 1 X 1-2 1-10* X 1-2-2-3 1--0 A4 11-0 X 0011 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. = 7. Teha punktis 2 saadud MDNK-le Shannoni disjunktiivne arendus vabaltvalitud 2he muutuja järgi. Kui punktis 6 juba tehti Shannoni disj. arendus just 2 muutuja järgi, siis tuleb siin teha MDNK arendus 1 muutuja järgi, valides selle ühe muutuja vabalt.
avaldisse (0,1,2,5,6,7,9,13)1 ühtede piirkonna kümnenednumbrile vastav kahendvektorile vastav kümnendnumber kahendvektor elementaarkonjunktsioon 0 0000 x1 x 2 x 3 x 4 1 0001 x1 x 2 x 3 x4 2 0010 x 1 x 2 x3 x 4 5 0101 x1 x2 x 3 x4 6 0110 x 1 x 2 x3 x 4 7 0111 x1 x 2 x3 x 4 9 1001 x1 x 2 x 3 x 4 13 1101 x1 x 2 x 3 x 4
0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 f(x1 , x2 , x3 )= x1 x2x3 x1 x2 x3 x1x2 x3 x1x2x3 Erinevate loogikafunktsioonide f(x1 ,x2 ,...xn) arv K on 2 2 n . n=1 K=4 n=2 K=16 n=3 K=256 n=4 K=65536 n=5 K=4,3 · 109 Järgnevalt tutvume kõikvõimalike kahe muutuja funktsioonidega f(x1 , x2 ). x1 x2 f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 Tabelis on kirjeldatud järgnevad funktsioonid:
1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 f(x1 , x2 , x3 )= x1 x2x3 x1 x2 x3 x1x2 x3 x1x2x3 n Erinevate loogikafunktsioonide f(x1 ,x2 ,...xn) arv K on 2 2 . n=1 K=4 n=2 K=16 n=3 K=256 8 n=4 K=65536 n=5 K=4,3 109 Järgnevalt tutvume kõikvõimalike kahe muutuja funktsioonidega f(x1 , x2 ). x1 x2 f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 Tabelis on kirjeldatud järgnevad funktsioonid: f0 - konstant "0"
t i t 10 1 1 1 In s Kontrollida Karnaugh' kaardiga ühe varasema teisendusülesande tulemuseks saadud DNK-avaldise minimaalsust: analüüsitava DNK tõeväärtustabel kaardil f ( x1 . . . x4 ) = x1 x¯2 x¯4 w x1 x¯2 x3 w x3 x4 w x2 x4 w ¯x1 x4 mitme kontuuriga õnnestub katta kõik 1-de ruudud optimaalseimal viisil ? Kas see DNK on MDNK ? kanname 4-muutuja kaardile need 1-de kontuurid, millest tuleneks antud DNK x1 x¯2 x¯4 w x1 x¯2 x3 w x3 x4 w x2 x4 w ¯x1 x4
annaabi.ee 
