Mis on elementaarkonjuktsioon? Mis on elementaardisjunktsioon? Elementaarkonjuktsioon on ükskik algterm või algtermide konjuktsioon. Nt x1x2x3,x1. Elementaardisjunktsioon on üksik algterm või algtermide disjunktsioon nt x1 v x2 v x3,x1 Mis on DNK? Mis on KNK? DNK on üksik elementaarkonjuktsioon või elementaarkonjuktsioonide disjunktsioon KNK on üksik elementaardisjunktsioon või elementaardisjunktsioonide konjuktsioon. Mis on TDNK? Mis on TKNK? TDNK on DNK, kus iga elementaarkonjuktsioon sisaldab funktsiooni kõiki muutujaid xi TKNK on KNK, kus iga elementaardisjunktsioon sisaldab funktsiooni kõiki muutujaid xi Mis on loogikaavaldise keerukus? Loogikaavaldise f keerukus L(f) on tema kooseisus olevate algtermide arv. Vt näidet lk 167 keskel. Mis on MDNK? Mis on MKNK? MDNK ja MKNK on konkreetse funktsiooni väikseima keerukusega DNK või KNK. Millisest loogikafunktsiooni piirkonnast tuleneb DNK, millisest KNK?
MKNK: f K x1 x4 x3 x4 x1 x2 x1 x2 x3 x4 4. Täielik DNK (TDNK) 1-de piirkonnast 4-muutuja loogikafunktsioon ignoreerides määramatuspiirkonda (1-de piirkond): f ( x1...x4 ) = ∑(2,3,4,7,12,14)1 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 TDNK: 5. TDNK lihtsustamine loogikaalgebra põhiseoste abil 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
Teoreem 4. Valemid F ja G on samaväärsed parajasti siis, kui valem FG on samaselt tõene. Tõestus... 2 Lausearvutuse põhisamaväärsused. Valemite avaldamine etteantud tehete kaudu. 2 Tõestus SML õpikus lk 21 3 Valemite disjunktiivne ja konjunktiivne normaalkuju. Nende leidmise algoritmid. Def 7. Lvalemi F täielikuks TDNK nim valemiga F samaväärset valemit, mis kujutab endast erinevate täielike EKD 3 Valemi F TKNK nim valemiga F samaväärset valemit, mis kujutab endast erinevate täielike EDK. Kui valem F ei ole samaselt väär, siis tal leidub TDNK. Kui valem F ei ole samaselt tõene, siis tal leidub TKNK (Teoreem 5+Järeldus 1) 4 Täielikule disjunktiivsele normaalkujule viimise algoritmi sammud
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: ...
1. Sellele hulgale vastav funktsiooni taandatud disjunktiivne normaalkuju: TaDNK f(x1,x2,x3,x4) = x1 x 2 x 4 x1 x 3 x 2 x 3 x 3 x 4 2.4 Täieliku DNK leidmine Loogikafunktsiooni Täielik DNK on normaalkuju, milles iga elementaarkojunktsioon sisaldab loogikaf.-ni kõiki argumente (või nende inversioone). S.t iga elementaarkonjunktsiooni pikkus on võrdne f.-ni argumentide arvuga. Antud juhul 4-ga. Igal loogikafunktsioonil on täpselt üks TDNK. TDNK leidmise meetod: · võtan f.-ni ühtede piirkonna mingi kümnendnumbri · leian kümnendnubrile vastava kahendvektori · leian kahendvektorile vastava elementaarkonjunktsiooni · lisan elementaarkonjunktsiooni funktsiooni TDNK avaldisse · kordan eelmist nelja tegevust, kuni kõik ühtede piirkonna numbrid on läbitud ühtede piirkonna kümnenednumbrile kahendvektorile vastav
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 ...
Kuna lihtimplikandid A6 ja A7 sisaldavad määramatust ja ei osutunud valituks MDNK-sse, ei vali ka neid TaDNK-sse , et saadud avaldis oleks loogiliselt võrdne MDNK-ga. Sellele hulgale vastav funktsiooni taandatud DNK: TaDNK : f(x1, x2, x3, x4) = A1 A2 A3 A4 A5 A8 x1 x 2 x3 x1 x 2 x 4 x1 x3 x 4 x1 x 2 x 4 x1 x 2 x3 x3 x 4 TaDNK : f(x1, x2, x3, x4) = 2. Täielik DNK TDNK leidmine: võtan f.-ni ühtede piirkonna (koos määramatusega mida kasutati MDNK-s) kümnendnumbri ning leian kümnendnubrile vastava kahendvektori ja leian kahendvektorile vastava elementaarkonjunktsiooni ning lisan need funktsiooni TDNK avaldisse (0,1,2,5,6,7,9,13)1 ühtede piirkonna kümnenednumbrile vastav kahendvektorile vastav kümnendnumber kahendvektor elementaarkonjunktsioon
31. Mis on elementaardisjunktsioon? Elementaardisjunktsioon on algterm või algtermide disjunktsioon. 32. Mis on disjunktiivne normaalkuju (DNK)? DNK on elementaarkonjunktsioon või elementaarkonjunktsioonide disjunktsioon. 33. Mis on konjunktiivne normaalkuju (KNK)? KNK on elementaardisjunktsioon või elementaardisjunktsioonide konjunktsioon. 34. Esitada näitena avaldisi, mis on samaaegselt nii DNK kui ka KNK? , , ∨ 35. Mis on täielik disjunktiivne normaalkuju (TDNK)? TDNK on DNK, kus iga elementaarkonjunktsioon sisaldab kõiki funktsiooni muutujad. 36. Mis on täielik konjunktiivne normaalkuju (TKNK)? TKNK on KNK, kus iga elementaardisjunktsioon sisaldab kõiki funktsiooni muutujaid. 37. Mis on loogikaavaldise keerukus? Loogikaavaldise keerukus on temas sisalduvate algtermide arv. 38. Mis on minimaalne DNK (MDNK)? Mis on minimaalne KNK (MKNK)? MDNK (MKNK) on vähima keerukusega DNK (KNK) ehk sisaldab kõige vähem algterme. 39
4 4. Kirjutada oma funktsiooni 1-de piirkonnast välja täielik DNK (TDNK) (ignoreerides määramatuspiirkonda). TDNK: f (X1 X2 X3 X4) = X1' X2' X3' X4' v X1' X2' X3' X4 v X1' X2' X3 X4' v X1' X2 X3' X4 v X1 X2 X3' X4' v X1 X2 X3' X4 5. Lihtsustada loogikaalgebra põhiseoste abil eelnevalt leitud täielikku DNK-d lihtsaima DNK-ni, milleks see TDNK lihtsustub. Võrrelda lihtsustamisel saadud DNK-d eelnevalt (punktis 3) leitud MDNK-ga: -- kas nad on võrdsed? -- kui nad pole võrdsed, siis kumb nendest on väiksema keerukusega (ehk lihtsam) avaldis ja miks? f (X1 X2 X3 X4) = X1' X2' X3' X4' v X1' X2' X3' X4 v X1' X2' X3 X4' v X1' X2 X3' X4 v X1 X2 X3' X4' v X1 X2 X3' X4 = X1' X2' X4' (X3' v X3) v X1' X3' X4 (X2' v X2) v X1 X2 X3' (X4' v X4) = X1' X2' X4' v X1' X3' X4 v X1 X2 X3'
4 x 2-6 4 A1 8 x 4-5 1 x 2 5 x 4-6 2 x 6 x 8-9 1 A2 9 x 2-3 5-7 2 x 3 7 x 5-13 8 x 13 x 6-7 1 x 9-13 4 x Seega on taandatud DNK: Ehk taandatud DNK langeb kokku MDNK-ga. * Leian TDNK. Kirjutan TDNK eelnevalt leitud f1-e tõeväärtustabeli ühtede piirkonnast. 5. Leida vabaltvalitud viisil punktis 2 saadud MKNK-ga (loogiliselt) võrdne Täielik KNK. Teisendan punktis 2 saadud MKNK TKNK-ks. 6. Teha punktis 2 saadud MDNK-le Shannoni disjunktiivne arendus selle muutuja (muutujate) x i järgi, mida esineb MDNK-s kõige rohkem. Minu MDNK-s esinevad muutujad x1 ja x3 mõlemad 3 korda. Seega teen Shannoni disjunktiivse arenduse kahe muutuja järgi. =
..,w,*,+)=f(a,b,c,...,w,+,* )n 14. Loogikaavaldiste algebraline lihtsustamine 15. Funktsionaalselt täielikud süsteemid Loogika elementide süsteemi mis realiseerib kõikki kahe argumendi funktsioone nimetatakse funktsionaalselt täielikuks süsteemiks nt. NING, VÕI ja EI. Minimaalne funktsionaalselt täielik süsteem on selline millest ükskõik millise elemendi väljajätmine muudab süsteemi mittetäielikuks. Nt.VÕI EI või NING EI. 16. Täielik disjunktiivne normaalkuju e. TDNK DNK on loogika funktsiooni esitamine realiikmete disjunktsioonina (summana), kus liikmed on argumentide või argumentide inversioonide elementaarkonjunktsioonid (korrutised). Elementaarkonjunktsioonid on nt. 1 × 2 × 3 ; Elementaarkonjunktsioonid ei ole nt. X2*X3*X3; X1*X3; X3*X4*X5 TDNK puhul peavad kõik liikmed sisaldama funktsiooni kõikki argumente või nende inversioone. Kui algfunktsioon on antud tabelina siis saab TDNK otse tabelist välja kirjutada. 17
Tähistan leitud MDNK ja MKNK: f D = (x2 4) v ( 1 2x3) v (x3 4) f K = (x2 v x3)( 2 v 3)( 1 v 4) 4. Kirjutada oma funktsiooni 1-de piirkonnast välja täielik DNK (TDNK) (ignoreerides määramatuspiirkonda). fTDNK ( 1 2x3 4) v( 1 2x3x4) v ( 1x2 3 4) v (x1 2x3 4) 5. Lihtsustada loogikaalgebra põhiseoste abil eelnevalt leitud täielikku DNK-d lihtsaima DNK-ni, milleks see TDNK lihtsustub. Võrrelda lihtsustamisel saadud DNK-d eelnevalt (punktis 3) leitud MDNK-ga: — kas nad on võrdsed? — kui nad pole võrdsed, siis kumb nendest on väiksema keerukusega (ehk lihtsam) avaldis ja miks? fTDNK ( 1 2x3 4) v ( 1 2x3x4) v ( 1x2 3 4) v (x1 2x3 4) = 1 2x3( 4 v x4) v ( 1x2 3 4) v (x1 2x3 4) = ( 1 2x3) v ( 1x2 3 4) v (x1 2x3 4) Funktsioon edasi ei lihtsustu. Kontrollin Karnaugh kaardiga, ignoreerides
..................................................8 3. Leida MDNK (minimaalne DNK) ja MKNK (minimaalne KNK), mis sobiksid matriklinumbrist leitud osaliselt määratud 4-muutuja funktsiooni esitamiseks......8 4. Kirjutada oma funktsiooni 1-de piirkonnast välja täielik DNK (TDNK) (ignoreerides määramatuspiirkonda)...................................................................10 5. Lihtsustada loogikaalgebra põhiseoste abil eelnevalt leitud täielikku DNK-d lihtsaima DNK-ni, milleks see TDNK lihtsustub.....................................................11 5.1 Võrrelda lihtsustamisel saadud DNK-d eelnevalt (punktis 3) leitud MDNK-ga: .......................................................................................................................... 11 5.1.1 — kas nad on võrdsed?.........................................................................11 5.1.2 — kui nad pole võrdsed, siis kumb nendest on väiksema keerukusega
15 1111 x 1 x 2 x3 x4 TDNK (x1,x2,x3,x4) ¿ x´ 1 x´ 2 x´ 3 x 4 x´ 1 x 2 x3 x 4 x´ 1 x´ 2 x 3 x 4 x´ 1 x2 x´ 3 x 4 x 1 ´x2 x´ 3 x´ 4 x 1 x2 x´ 3 x´ 4 x 1 x2 x 3 x´ 4 x 1 x2 x 3 x 4 6. Täieliku KNK leidmine. Täielik KNK on KNK normaalkuju, milles iga elementaarfunktsioon sisaladab funktsiooni kõiki argumente. Selle leian samuti nagu eespool leidsin TDNK, kuid seekord võtan nullide piirkonna, leian elementaarkonjunktsiooni asemel elementaardisjunktsiooni ja asetan selle avaldisse. 0de pk. Kümnendnumbrile vastav Kahendvektorile vastav kahendvektor elementaardisjunktsioon 0 0000 x 1 x2 x3 x 4
Olgu vaatluse all komplekt lausemuutujaid 1, 2,..., n, lisades vajaduse järgi eitusi, moodustame literaalid 1, 2,..., n ning koostame valemi 1 & 2 & ... & n. Sellist valemit nimetatakse täielikuks elementaarkonjunktsiooniks. c. Lausearvutuse valemi täielikuks disjunktiivseks elementaarkonjunktsiooniks (TDNK) nimetatakse valemiga samaväärset valemit, mis kujutab endast erinevate täielike elementaarkonjunktsioonide disjunktsiooni. TDNK on tõene parajasti nendel väärtustustel, mis vastavad normaalkuju liikmetele. d. TDNK leidumine. Teoreem. Kui valem ei ole samaselt väär, siis tal leidub täielik disjunktiivne normaalkuju. e. Valemi TDNK jaoks on üheselt määratud seal esinevate täielike elementaarkonjunktsioonide hulk, see peab vastama esialgse valemi tõeväärtuse veerule. Seega on TDNK määratud ühesel kuni elementaarkonjunktsioonide järjestuse täpsuseni. f
ja disjunktsioonide sisse) Korrutada disjunktsioonid läbi (distributiivsuse seaduse abil) Kaotada samaselt väärad konjunktsioonid ja sama liikme mitmekordsed esinemised konjunktsioonides Lisada konjunktsioonidele puuduvad muutujad Korrastada valem (järjestada muutujad konjunktsioonides ja kaotada korduvad konjunktsioonid) o TDNK leidub igal kehtestataval valemil ja on üheselt määratud täielike elementaarkonjuktsioonide järjekorra täpsusega Lausearvutuse valemi F täielikuks konjuktiivseks normaalkujuks (TKNK) nimetatakse valemiga F samaväärset valemit, mis kujutab endast erinevate täielike elementaardisjunktsioonide konjuktsiooni o (X111 V ... V X n1n) & (X121 V ... V Xn2n) & ...& (X1m1 V ... V X nmn) on väär väärtustustel (¬11, ..., ¬1n), (¬21, ..., ¬2n), ..., (¬m1, .
Tallinna Tehnikaülikool Diskreetne Matemaatika KODUTÖÖ 164780 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 ...
MDNK'ga: x x x 2 x3 x 4 x1 x 2 x 4 f(x1,x2,x3,x4) = 1 2 x3x4 x1x2 00 01 11 10 00 1 1 1 1 01 0 0 0 0 11 0 1 1 0 10 1 0 0 0 4.2. Leian Täieliku DNK ehk TDNK Täielik DNK ehk TDNK on kõikide implikantide disjunktsioon ning võrdub antud juhul: x1 x 2 x3 x 4 x1 x 2 x3 x 4 x1 x 2 x3 x 4 x1 x 2 x3 x 4 x1 x 2 x3 x 4 x1 x 2 x3 x 4 f(x1,x2,x3,x4) = x1 x 2 x3 x 4 x3x4 x1x2 00 01 11 10 00 1 1 1 1 01 0 0 0 0
Küsimus 1 Õige - Hinne 1,00 / 1,00 Millised on loogikafunktsiooni võimalikud esitusviisid ? Vali üks või enam: osaline järjestussuhe Hasse diagramm tõeväärtustabel Grassmani valem Venni diagramm hulk loogikaavaldis numbriline kümnendesitus Küsimus 2 Õige - Hinne 3,00 / 3,00 vali mõlemasse lünka õiged valikud: Konjunktiivne Normaalkuju (KNK) on mis disjunktsioonide konjunktsioon saadakse tõeväärtustabeli 0de piirkonnast Küsimus 3 Õige - Hinne 1,00 / 1,00 kas järgnev väide on õige või vale? 4-mõõtmeline Boole'i ruum on kõikide 4-järguliste 2ndvektorite hulk. Vali üks: Tõene Väär Küsimus 4 Õige - Hinne 6,00 / 6,00 vali sobivad väljendid, mille korral lause on õige: Täielikult määratud loogikafunktsioon on kõikjal määratud ...
.............................................................................18 3.7.1. n-MOP loogika.................................................................................................19 3.7.2. Komplementaarne MOP-CMOS......................................................................19 4. Kombinatsioonseadmete süntees...................................................................................21 4.1. Loogikafunktsiooni täielik disjunktiivne normaalkuju ehk TDNK........................21 4.2. Täielik konjunktiivne normaalkuju TKNK.........................................................21 4.3. Loogikafunktsioonide lihtsustamine Karnaugh' kaartide meetodil....................22 5. Integraalsed trigerid.......................................................................................................23 5.1. NING-EI ja VÕI-EI................................................................................................ 23
.............................................................................18 3.7.1. n-MOP loogika.................................................................................................19 3.7.2. Komplementaarne MOP-CMOS......................................................................19 4. Kombinatsioonseadmete süntees...................................................................................21 4.1. Loogikafunktsiooni täielik disjunktiivne normaalkuju ehk TDNK........................21 4.2. Täielik konjunktiivne normaalkuju TKNK.........................................................21 4.3. Loogikafunktsioonide lihtsustamine Karnaugh’ kaartide meetodil....................22 5. Integraalsed trigerid.......................................................................................................23 5.1. NING-EI ja VÕI-EI................................................................................................23
KONTROLLKÜSIMUSTEGA TEST - loogikafunktsioonid 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 9 KONTROLLKÜSIMUSTEGA TEST - loogikafunktsioonid Review of attempt 4 Started on Friday, 2 December 2011, 04:46 PM Quiz navigation Completed on Friday, 2 December 2011, 04:55 PM 1 2 3 4 5 6 Time taken 8 mins 52 secs 7 8 9 10 11 12 Marks 31.00/31.00 Grade 100.00 out of a ma...
Tallinna Tehnikaülikool Diskreetne matemaatika KODUTÖÖ Tallinn 2011 1. Leida oma matriklinumbrile vastav 4-muutuja loogikafunktsioon. Matriklinumber: 112799 Matriklinumbri 16ndkuju: 1B89F 16ndarvu 8*3-ga korrutamisel tekib 8-järguline 16ndarv: 1B89F*3*3*3*3*3*3*3*3 = 2C1CA2FF Saadud 16ndarv sisaldab numbrimärke 1 2 A C F , kus 16ndnumbrid A C F omavad väärtusi: A = 10 C = 12 F = 15 Saadud 16ndarvu 8 järguväärtust 0 . . . 15 määravad loogikafunktsiooni 1-de piirkonna. (korduvaid järguväärtusi võib ignoreerida) Seega on 4-muutuja loogikafunktsiooni 1de piirkonnaks (numbrilises 10ndesituses): 2 12 1 10 15 (numbreid 2, C ja F (ehk 2, 12 ja 15) on arvus mitu – neid võib arvestada ühekordselt) 8-järgulise 16ndarvu jagamisel 11-ga tekib 7-järguline 16ndarv: 2C1CA2FF/11 = 29845D2 Saadud 16ndarv sisaldab numbrimärke 2 4 5 8 9 D , kus 16ndnumber D omab väärtust: D = 13 11-ga jagamisel tekkiva 16ndarv...
. . . on 7 implikanti : t Kuna kõik lihtimplikandid on Karnaugh' kaardil hästi näha, siis sobib kaart u {001} {011} {100} {101} {100 101} {001 011} {001 101} ka TaDNK leidmiseks. r v . . . . mida esitavad Karnaugh' kaardil sellised kontuurid : Igal loogikafunktsioonil on täpselt 1 TDNK ja täpselt 1 TaDNK. A x 2 x3 x 2 x3 Taandatud normaalkuju mõiste defineeritakse ainult DNK jaoks x 1 00 01 11 10 x 1 00 01 11 10 ehk Taandatud KNK "pole olemas" 0 0 1 1 0 0 0 1 1 0 t
Elementaarkonjunktsioon on üksik algterm või algtermide konjunktsioon. Elementaardisjunktsioon on üksik algterm või algtermide disjunktsioon. DNK (1-de pk) on üksik elementaarkonj. või elementaarkonj-de disjunktsioon. KNK (0-de pk) on ükskik elementaardisj. või elementaardisj-de konjunktsioon. Samaaegselt DNK ja KNK 𝑥1∨𝑥2∨𝑥3 𝑥1𝑥 ̅ 2𝑥3̅ 𝑥2̅ TDNK on DNK, kus iga elementaarkonj. sisaldab F-ni kõiki muutujaid 𝑥𝑖. TKNK on KNK, kus iga elementaardisj. sisaldab F-ni kõiki muutujaid 𝑥𝑖. MDNK/MKNK on konkreetse F-ni väikseima keerukusega DNK/KNK. Keerukus 𝑳(𝒇) on tema koosseisus olevate algtermide arv. Loogikaalgebra põhiseosed Seosed konstantidega 0̅=1 1̅=0 0∗1=0 0∨1=1 𝑥∗0=0 𝑥∗1=𝑥 𝑥∗𝑥̅=0 𝑥∨0=𝑥 𝑥∨1=1 𝑥∨𝑥̅=1 Idempotentsus 𝑥∗𝑥=𝑥 𝑥∨𝑥=𝑥
Seega loogikafunktsiooni taandatud disjunktiivne normaalkuju on võrdne saadud MDNK-ga: 5 f TaDNK =x1 x´ 2 ∨ x 4 =f MDNK 5.2 TÄIELIK DNK Täielik DNK on selline disjunktiivne normaalkuju, mille korral iga elementaarkonjunktsiooni pikkus on võrdne loogikafunktsiooni argumentide arvuga. Vaadates alamülesande 3.1 parempoolset Karnaugh’ kaarti, saame ühtede piirkonna järgi välja kirjutada TDNK. Selleks valime ühtede piirkonnast minimaalse suurusega kontuurid, s.t joonistame iga muutujate väärtuse “1” ümber kontuuri suurusega 1 ning kirjutame kaardi järgi välja täieliku disjunktiivse normaalkuju: f TDNK =´x 1 ´x 2 ´x 3 x 4 ∨ x´ 1 ´x2 x 3 x 4 ∨ ´x 1 x 2 x´ 3 x 4 ∨ ∨ ´x 1 x 2 x 3 x 4 ∨ x1 ´x 2 ´x 3 x´ 4 ∨ x 1 x´ 2 ´x3 x 4 ∨ x 1 ´x 2 x 3 ´x 4 ∨ ∨ x 1 ´x 2 x 3 x 4 ∨ x1 x 2 ´x 3 x 4 ∨ x 1 x 2 x3 x 4 ÜLESANNE 6 TÄIELIK KNK
MKNK leidmise /¯¯ ülesanne: ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ kontuuridevalik f K (0011) = 1 Leia Karnaugh' kaardi abil MDNK samale funktsioonile, mille f K (1110) = 1 TDNK lihtsustasime eelpool näites MDNK-ks x1 x 2 x 3 f ( x 1 x 2 x3 ) f ( x1 x2 x3) = x2 w x1 x3 w ¯1 x x ¯3 0 0 0 1 0 0 1 0 MDNK-ks saime sama tulemuse nagu enne TDNK teisendamisel Ü
5.1 TAANDATUD DNK Vaadates alamülesande 3.1 Karnaugh’ kaarti, näeme, et joonistatud kontuurid vastavad ühtlasi ka lihtimplikantidele.Leian taandatud DNK täielikult määratud Karnaugh’ kaardiga : 𝒇(xTaDNK(x1x2x3x4) = x2 x 3 v x1 x 3 v x1 x2 x4 v x 1 x 2 x3 x4 = 𝒇(xMDNK 5.2 TÄIELIK DNK Vaadates alamülesande 3.1 Karnaugh’ kaarti, saame ühtede piirkonna järgi välja kirjutada TDNK. 𝒇(xTDNK(x1x2x3x4) = x 1 x 2 x3 x4 v x 1 x2 x 3 x 4 v x 1 x2 x 3 x4 v x1 x 2 x 3 x 4 v x1 x 2 x 3 x4 v v x1 x2 x 3 x 4 v x1 x2 x 3 x4 v x1 x2 x3 x4 9 ÜLESANNE 6 TÄIELIK KNK Leida vabalt valitud viisil ülesandes 3 saadud MKNK-ga loogiliselt võrdne täielik KNK. 𝒇(xMKNK(x1x2x3x4) = (x1 v x2 v x3)(x1 v x 2 v x 3)(x 1 v x2 v x 3)(x 3 v x4) Teades, et saadud MKNK on loogiliselt võrdne saadud MDNK-ga, siis võime
Tallinna Tehnikaülikool Diskreetne Matemaatika KODUTÖÖ Peeter Sikk 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 _...
LAUSEARVUTUS Küsimus 1 Õige Hinne 1,00 / 1,00 otsusta, kas see väide on tõene või vale: "Tautoloogia" on lause, mille tõeväärtus on alati VALE. Tõene Väär Küsimus 2 Õige Hinne 1,00 / 1,00 Mida tähendab hüüumärgiga eksistentsikvantor? Vali üks: hüüumärk muudab kvantori tähenduse vastupidiseks hüüumärk täpsustab, et "leidub täpselt 1" hüüumärk rõhutab kvantori suurt tähtsust Küsimus 3 Õige Hinne 1,00 / 1,00 Kui loogikaavaldises pole sulgudega määratud tehete järjekorda, siis KONJUNKTSIOONi, DISJUNKTSIOONi ja INVERSIOONi leidumisel avaldises . . . Vastus 1 kõige esimesena tehakse loogikaavaldises INVERSIOON Vastus 2 ...selle järel järgmisena tehakse KONJUNKTSIOON Vastus 3 ...ja viimasena...
· Iga funktsioon on esitatav DNK ja KNK kujul, kuid mitte üheselt. · Täielik DNK (TDNK) on selline DNK, kus iga elemantaarkonjunktsiooni pikkus on n (s.o. iga elementaarkonjunktsioon sisaldab funktsiooni kõiki argumente). · Täielik KNK (TKNK) on selline KNK, kus iga elemantaardisjunktsiooni pikkus on n (s.o. iga elementaardisjunktsioon sisaldab funktsiooni kõiki argumente). · Igal funktsioonil on täpselt üks TDNK ja üks TKNK. Näiteid · x1x2 x1 x2 x3 = x1 x2 x3 x1 x2 x3 x1 x2 x3 Parempoolne valem on funktsiooni täielik DNK. · x1 x2 x1 x2 x3 = ( x1 x2 x3 )( x1 x2 x3 )( x1 x2 x3 )( x1 x2 x3 )( x1 x2 x3 ) Parempoolne valem on funktsiooni täielik KNK. · ( x1x2 ) ( x1 x3 ) = x1 x2 x3 Parempoolne valem on antud funktsiooni DNK, KNK, TKNK. Loogikafunktsiooni võib esitada ka nn. numbrilises ehk kümnendesitusvormis. Sel juhul
Iga funktsioon on esitatav DNK ja KNK kujul, kuid mitte üheselt. Täielik DNK (TDNK) on selline DNK, kus iga elemantaarkonjunktsiooni pikkus on n (s.o. iga elementaarkonjunktsioon sisaldab funktsiooni kõiki argumente). Täielik KNK (TKNK) on selline KNK, kus iga elemantaardisjunktsiooni pikkus on n (s.o. iga elementaardisjunktsioon sisaldab funktsiooni kõiki argumente). Igal funktsioonil on täpselt üks TDNK ja üks TKNK. Näiteid x1 x2 x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 Parempoolne valem on funktsiooni täielik DNK. 11 x1 x2 x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 Parempoolne valem on funktsiooni täielik KNK. x1x2 x1 x3 x1 x2 x3
Elementaardisjunktsioon on üksik algterm või algtermide disjunktsioon. DNK (1-de pk) on üksik elementaarkonj. või elementaarkonj-de disjunktsioon. KNK (0-de pk) on ükskik elementaardisj. või elementaardisj-de konjunktsioon. Samaaegselt DNK ja KNK 𝑥1 ∨ 𝑥2 ∨ 𝑥3 ̅̅̅𝑥 𝑥1 2 ̅̅̅ 𝑥3 ̅̅̅ 𝑥2 TDNK on DNK, kus iga elementaarkonj. sisaldab F-ni kõiki muutujaid 𝑥𝑖 . TKNK on KNK, kus iga elementaardisj. sisaldab F-ni kõiki muutujaid 𝑥𝑖 . MDNK/MKNK on konkreetse F-ni väikseima keerukusega DNK/KNK. Keerukus 𝑳(𝒇) on tema koosseisus olevate algtermide arv. Loogikaalgebra põhiseosed Seosed konstantidega 0̅ = 1 1̅ = 0 0 ∗ 1 = 0 0 ∨ 1 = 1 𝑥 ∗ 0 = 0 𝑥 ∗ 1 = 𝑥 𝑥 ∗ 𝑥̅ = 0 𝑥 ∨ 0 = 𝑥 𝑥 ∨ 1 = 1 𝑥 ∨ 𝑥̅ = 1
Tallinna Tehnikaülikool Diskreetne Matemaatika KODUTÖÖ 094231 Tallinn 2009 1. Ülesanne Matrikli number on: 094231 Matrikkel teisendatuna kuueteistkümmendsüsteemi saan tulemuseks 17017 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 ...
/¯¯ ülesanne: ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ 1 0 1 1 1 Leia Karnaugh' kaardi abil MDNK samale funktsioonile, mille TDNK lihtsustasime eelpool näites MDNK-ks MDNK : f ( x1 x 2 x 3 ) = x2 w x1 x3 w x¯1 x¯3 x 4 x5 x 4 x5 x 2 x3 00 01 11 10 x 2 x3 00 01 11 10
1 , F 2 , . . . , F n on tõesed, on ka F 1 & F 2 & . . . & F n tõene, mistõttu valem G on samuti tõene. Teoreemid järeldumise ja samaväärsuse taandamisest ühe valemi omaduse kontrollimisele o Samaväärus F ↔ G o Järeldumine F → G 7 6. Literaal, täielik elementaarkonjunktsioon, täielik disjunktiivne normaalkuju, nende tõesuspiirkondade kirjeldused. TDNK olemasolu ja ühesus. TDNK-le teisendamise algoritm, tema etappidel kasutatavad samaväärsused. [1] Literaal o DEF: Literaaliks nimetatakse lausemuutujat või selle eitust, literaale loetakse positiivseks või negatiivseks vastavalt selelle, kas ta on puhas lausemuutuja või koos eitusega. N: A, B, ¬C Täielik elementaalkonjuktsioon o DEF: Muutujate X1, X2…, Xn täielikuks elementaarkonjunktsiooniks nimetatakse literaalide konjunktsiooni L1&L2&,..., &Ln
x3x4 00 01 11 10 x1x2 00 0 0 0 1 01 1 0 0 1 11 0 1 1 1 10 1 1 1 0 Karnaugh' kaardile on kantud on 6 intervalli. Leian konstandid. Arvestan seejuures, et DNK sõltub 1de piirkonnast. Intervallidel: 100- x1 x 2 x3 1--1 x1x4 111- x1x2x3 -110 x2x3 x 4 10-0 x1 x2 x 4 0-10 x1 x3 x 4 Taandatud DNK f = x1x4 V x1x2x3 V x1 x 2 x3 V x2x3 x 4 V x1 x2 x 4 V x1 x3 x 4 2) Leian TDNK (täielik DNK) Täieliku DNK korral on igas funktsiooni liikmes kõik funktsiooni muutujad esitatud. Täieliku DNK leidmiseks MDNK-st kasutan kleepimisseaduseid st. kleebin puuduva muutuja liikmele. f = x1x2x3Vx1 x 2 x3 V x1 x2 x 4 V x1 x3 x 4 = x1 x 2 x3 x 4 V x1 x 2 x3 x4 V x1x2x3 x 4 V x1x2x3x4 V x1 x2 x3 x 4 V x1 x2x3 x 4 V x1 x 2 x3 x 4 V x1 x2x3 x 4 ÜLESANNE 5 Leida vabaltvalitul viisil punktis 2 saadud MKNK-ga loogiliselt võrdne Täielik KNK
0010 x1 x2 x3 x 4 0011 x1 x2 x3 x 4 0101 x1 x2 x3 x 4 1101 x1 x2 x3 x 4 1110 x1 x2 x3 x 4 1111 x1 x 2 x3 x 4 Leitud konstituentide järgi saan TDNK: f(x1,x2,x3,x4)= x1 x2 x3 x4 x1 x2 x3 x4 x1 x2 x3 x4 x1 x2 x3 x4 x1 x2 x3 x4 x1 x2 x3 x4 x1 x2 x3 x4 Taandatud DNK: Leian Karnaugh’ kaardi abil f(x1,x2,x3,x4)= ∑ (0, 2, 3, 5, 13, 14, 15)1 x3x4 11 00 01 10 x1x2 00
Tallinna Tehnikaülikool Diskreetne Matemaatika KAUGÕPE KODUTÖÖ 1. Leida oma matriklinumbrile vastav 4-muutuja loogikafunktsioon Matriklinumber: 184974 7-kohaline 16-nd süsteemi arv: 3C81C42 Ühtede piirkond: f(x1 x2 x3 x4) = (1,2,3,4,8,12)1 9-kohaline 16-nd süsteemi arv: 5111DDC6E Määramatuspiirkond: f(x1 x2 x3 x4) = (5,6,13,14)_ Nullide piirkond: 0,7,9,10,11,15 Minu funktsioon: f(x1 x2 x3 x4) = (1,2,3,4,8,12)1 (5,6,13,14)_ 2. Esitada oma loogikafunktsiooni tõeväärtustabel x1 x2 x3 x4 0000 0 0001 1 0010 1 0011 1 0100 1 0101 - ...
Tallinna Tehnikaülikool DISKREETNE MATEMAATIKA KODUTÖÖ Elena Borissov 155175IAPB IAPB11 1. Leida oma matriklinumbrile vastav 4-muuutuja loogikafunktsioon Esimene seitsmekohaline arv kalkulaatoris 32C2641 . Kümnendarvudena 3, 2, 12, 6, 4, 1 Järjekorras 1, 2, 3, 4, 6, 12 1de piirkond Esimene üheksakohaline arv kalkulaatoris 440274117 Järjekorras 0, 7 määramatus piirkond 5, 8, 9, 10, 11, 13, 14, 15 0de piirkond f(x1, x2, x3, x4)=∑(1, 2, 3, 4, 6, 12)1 (0, 7)_ 2. Tõeväärtustabel x1, x2, x3, x4 f 0000 - 0001 1 0010 1 0011 1 0100 ...
Leian täieliku DNK. Täielik DNK on funktsiooni ühtedeks avalduvate 2- ndvektorite disjunktsioon, kus igas elementaarkonjuktsioonis on kõik funktsiooni muutujad esindatud. x´ 1 x´2 x´3 x´4 V x´ 1 x 2 x´3 x´4 V x 1 x 2 x´3 x´ 4 V x´1 x 2 x´3 x 4 V x 1 x 2 x´3 x 4 V x´1 x´2 x 3 x 4 V V x´1 x´2 x 3 x´4 V x´1 x2 x 3 x´4 V x1 x´ 2 x 3 x´4 Võrdlen MDNK väärtustega: TDNK väärtused on MDNK-ga samad. 6. Leian MKNK järgi täieliku KNK. TKNK on funktsiooni nullideks avalduvate 2- ndvektorite konjunktsioon, kus igas elementaardisjuktsioonis on kõik funktsiooni muutujad esindatud. Kasutan selleks vasakul asuvat tõeväärtustabelit, mis on
Järgneval kolmel real on igal real avaldis, mis on samaaegselt nii DNK kui V1 = { 001, 010, 100, 110, 111 } ka KNK : DNK on seotud funktsiooni 1-de piirkonnaga ja x1 w x2 w x̄3 KNK on seotud 0-de piirkonnaga. x̄1 x2 x̄3 Funktsiooni 1-de piirkonnast saab välja kirjutada selle funktsiooni TDNK. x̄2 Vaatleme järgnevat 3-muutuja funktsiooni: x1 x2 x3 f ( x1 x2 x3 ) Täielik DNK ( TDNK ) on DNK, kus iga elementaarkonjunktsioon 0 0 0 0 Funktsiooni 1-de piirkonda kuulub sisaldab funktsiooni kõiki muutujaid xi
0011, 0100, 0111, 1100 , 1111, 1000, 1011, 1110} *Koostan DNK, kus iga elementaarkonjunktsioon omandab väärtuse 1 täpselt 1de piirkonna argumentvektoti korral. * xi = 0 siis ´x i ja kui xi=1 siis otseväärtus xi *Saadud elementaarkonjunktsiooni liidan või tehtega kokku DNKs TDNK: f(x1, x2, x3, x4) = ´x 1 ´x 2 ´x 3 ´x 4 v ´x 1
TÕESTUS: Kui on kehtestatav, siis väärtustusel, kus on tõene, on valem ¬ väär ja ei saa seetõttu olla samaselt tõene. Ümberpöördult, kui ¬ ei ole samaselt tõene, siis leidub väärtustus, kus ¬ on väär ja on järelikult tõene. 3. LOENG Järeldumine. Valemite teisendamine. TDNK Definitsioon F1 Fn Öeldakse, et valemitest , ... , järeldub valem , kui igal neis valemeis esinevate F1 Fn muutujate väärtustusel, millel , ... , on tõesed, on ka tõene. F1 Fn Asjaolu, et valemitest , ..
Digitaaltehnika konspekt 1 Sissejuhatus......................................................................................................................... 3 2 Arvusüsteemid..................................................................................................................... 4 2.1 Kahend-, kaheksand-, kuueteistkümnendarvude teisendamine kümnendarvudeks.......4 2.2 Teiste arvsüsteemide arvude murdosa teisendamine kümnendarvu murdosaks...........5 2.3 Ülesanne 1.................................................................................................................... 5 2.4 Ülesanne 1a.................................................................................................................. 6 2.5 Ülesanne 1b.................................................................................................................. 6 Kümnendarvu teisendamine kahend-, kaheksand-, kuueteis...
TALLINNA TEHNIKAÜLIKOOL ELEKTRIAJAMITE JA JÕUELEKTROONIKA INSTITUUT ROBOTITEHNIKA ÕPPETOOL MIKROPROTSESSORTEHNIKA TÕNU LEHTLA LEMBIT KULMAR Tallinn 1995 2 T Lehtla, L Kulmar. Mikroprotsessortehnika TTÜ Elektriajamite ja jõuelektroonika instituut. Tallinn, 1995. 141 lk Toimetanud Juhan Nurme Kujundanud Ann Gornischeff Autorid tänavad TTÜ arvutitehnika instituudi lektorit Toomas Konti ja sama instituudi dotsenti Vladimir Viiest raamatu käsikirjas tehtud paranduste ja täienduste eest. T Lehtla, L Kulmar, 1995 TTÜ elektriajamite ja jõuelektroonika instituut, 1995 Kopli 82, 10412 Tallinn Tel 620 3704, 620 3700. Faks 620 3701 ISBN 9985-69-006-0 TTÜ trükikoda. Koskla 2/9, Tallinn EE0109 Tel 552 106 3 Sisukord Saateks...