Priprave na vaje za predmet Osnove digitalnih vezij

(1)

Priprave na vaje za predmet Osnove digitalnih vezij

Miha Moˇskon

2017

Univerza v Ljubljani

Fakulteta za raˇcunalniˇstvo in informatiko

(2)

Kataloˇzni zapis o publikaciji (CIP) pripravili v Narodni in univerzitetni knjiˇznici v Ljubljani

COBISS.SI-ID=292687616 ISBN 978-961-6209-94-6 (pdf)

Elektronska izdaja knjige je na voljo na URL:

http://zalozba.fri.uni-lj.si/moskon2017.pdf

Recenzenta: doc. dr. Mira Trebar, prof. dr. Nikolaj Zimic Zaloˇznik: Zaloˇzba UL FRI, Ljubljana

Izdajatelj: UL Fakulteta za raˇcunalniˇstvo in informatiko, Ljubljana 1. izdaja, 2017

Urednik: prof. dr. Franc Solina

(3)

Kazalo

1 Priprava na 1. laboratorijske vaje 5

1.1 Boolova algebra in preklopne funkcije . . . 5

1.1.1 Postulati Boolove algebre . . . 5

1.1.2 Lastnosti Boolove algebre . . . 6

1.2 Podajanje preklopnih funkcij . . . 7

1.3 Osnovne preklopne funkcije . . . 7

1.3.1 Disjunkcija . . . 7

1.3.2 Konjunkcija . . . 7

1.3.3 Negacija . . . 8

1.3.4 Peircov operator . . . 9

1.3.5 Shefferjev operator . . . 9

1.3.6 Ekskluzivni ali . . . 10

1.3.7 Ekvivalenca . . . 10

1.3.8 Implikacija . . . 11

1.4 Analiti no reöevanje preklopnih funkcij . . . 11

2 Priprava na 2. laboratorijske vaje 13 2.1 Zapis preklopnih funkcij . . . 13

2.2 Analiti ni zapis in popolne normalne oblike zapisa preklopnih funkcij 13 2.2.1 Popolna disjunktivna normalna oblika (PDNO) . . . 13

2.2.2 Popolna konjunktivna normalna oblika (PKNO) . . . 14

2.2.3 Relaciji med makstermi in mintermi . . . 16

2.2.4 Pretvarjanje med PDNO in PKNO . . . 17

3 Priprava na 3. laboratorijske vaje 19 3.1 Zapis preklopnih funkcij z Veitchevim diagramom . . . 19

3.2 Funkcijsko poln sistem . . . 20

4 Priprava na 4. laboratorijske vaje 21 4.1 Zaprti razredi in preverjanje funkcijske polnosti sistema . . . 21

5 Priprava na 5. laboratorijske vaje 27 5.1 Minimalne oblike zapisa preklopnih funkcij . . . 27

iii

(4)

iv Kazalo

5.2 Veitchev postopek minimizacije . . . 28

5.2.1 Dolo anje minimalne normalne oblike z Veitchevim diagramom 30 6 Priprava na 6. laboratorijske vaje 35 6.1 Simetri ne preklopne funkcije . . . 35

6.2 Quineova metoda minimizacije . . . 36

6.2.1 Dolo anje MDNO . . . 36

6.2.2 Dolo anje MKNO . . . 37

7 Priprava na 7. laboratorijske vaje 39 7.1 Lo enje preklopnih funkcij . . . 39

7.2 Multiplekser . . . 40

7.3 Realizacija preklopnih funkcij z multiplekserji . . . 41

7.3.1 ätevilo vhodnih spremenljivk je enakoötevilu naslovnih vhodov multiplekserja . . . 42

7.3.2 ätevilo vhodnih spremenljivk je za 1 ve je odötevila naslovnih vhodov multiplekserja . . . 42

7.3.3 ätevilo vhodnih spremenljivk je za ve kot 1 ve je od ötevila naslovnih vhodov multiplekserja . . . 44

8 Priprava na 8. laboratorijske vaje 47 8.1 Sekven na vezja . . . 47

8.2 Sploöna pomnilna ena ba . . . 47

8.3 Enostavne pomnilne celice . . . 48

8.3.1 RS pomnilna celica (Reset Set) . . . 48

8.3.2 JK pomnilna celica (Jump Kill) . . . 49

8.3.3 T pomnilna celica (Trigger) . . . 50

8.3.4 D pomnilna celica (Delay) . . . 51

8.4 Realizacija sekven nih vezij s pomnilnimi celicami . . . 51

9 Priprava na 9. laboratorijske vaje 55 9.1 Moorov in Mealyjev kon ni avtomat . . . 55

9.2 Pretvorbe med avtomati . . . 59

10 Priprava na 10. laboratorijske vaje 63 10.1 Realizacija kon nih avtomatov s pomnilnimi celicami (Moorov avtomat) . . . 63

11 Priprava na 11. laboratorijske vaje 69 11.1 Realizacija kon nih avtomatov s pomnilnimi celicami (Mealyjev avtomat) . . . 69

12 Dodatna vaja 73

(5)

Kazalo v

12.1 Realizacija preprostega procesorja . . . 73

12.2 Osnovno delovanje procesorja . . . 73

12.2.1 Prevzem ukaza . . . 73

12.2.2 Izvedba ukaza . . . 74

12.3 Osnovna arhitektura procesorja . . . 74

12.3.1 Sploöno namenski registri . . . 74

12.3.2 Programskiötevec . . . 75

12.3.3 Ukazni register . . . 75

12.3.4 Kontrolna enota . . . 75

12.3.5 Aritmeti no logi na enota . . . 77

12.3.6 Ukazni pomnilnik . . . 78

12.3.7 Podatkovni pomnilnik . . . 78

12.3.8 Ostala kombinatorna logika . . . 78

12.4 Nabor ukazov . . . 78

12.4.1 Load A . . . 79

12.4.2 Load B . . . 79

12.4.3 Store A . . . 79

12.4.4 Add . . . 79

12.4.5 Sub . . . 79

12.5 Razlaga uporabljenih gradnikov . . . 79

12.5.1 Register . . . 79

12.5.2 Programskiötevec . . . 80

12.5.3 Seötevalnik . . . 81

12.5.4 Odötevalnik . . . 82

12.5.5 Read Only Memory (ROM) . . . 82

12.5.6 Random Access Memory (RAM) . . . 83

12.6 Realizacija opisanega procesorja . . . 83

12.7 Zgled delovanja procesorja . . . 84 A Slovensko-angleöki slovar osnovnih pojmov 87

Literatura 91

(6)

(7)

Predgovor

Pred vami je skripta priprav na laboratorijske vaje pri predmetu Osnove digitalnih vezij, ki se izvaja na 1. stopnji univerzitetnihötudijskih programov Ra unalniötvo in informatika in Ra unalniötvo in matematika na Fakulteti za ra unalniötvo in informatiko Univerze v Ljubljani. Skripta sluûi obveznim pripravam, ki jih morajo sluöatelji predmeta opraviti pred vsako laboratorijsko vajo. Vsaka priprava je sestavljena iz kratkega povzetka teoreti nih osnov in enega ali ve prakti nih zgledov. Na podlagi tako pridobljenega znanja lahkoötudent pristopi k reöevanju kviza, katerega oddaja je obvezna za pristop k naslednji laboratorijski vaji. Upam, da bo skripta sluûila svojemu namenu in boötudentom omogo ila laûje osvajanje znanja s podro ja osnov digitalnih vezij, ki ga v dolo eni meri potrebuje vsak ra unalni ar. Teoreti ne osnove lahkoötudenti najdejo v prosojnicah na spletni u ilnici in dodatni literaturi kot je [4] (v slovenskem jeziku) in [2] (v angleökem jeziku), dodatne vaje pa so na voljo v [1, 3].

doc. dr. Miha Moökon, 2017

1

(8)

(9)

Zahvala

Najprej bi se zahvalil svojim predhodnikom, tj. asistentom pri predmetu Preklopne strukture in sistemi, za zasnovo vaj, ki jih je evolucija ötudijskih programov pripeljala v stanje, v katerem so danes. Prav tako bi se rad zahvalil prof. dr.

Nikolaju Zimicu, za sodelovanje pri prenovi vaj po bolonjski reformi. Zahvaljujem se asistentoma Primoûu Pe arju in Domnu äoberlu, ki sta sodelovala pri nastajanju osnutka skripte, ki jo imate pred seboj. Zahvaljujem se tudi asistentoma Juretu Demöarju in Mattiji Petroniju za dolo ene popravke in dopolnitve tekom izvajanja vaj vötudijskih letih 2014/2015 in 2015/2016. Rad bi se zahvalil vsem sodelavcem Laboratorija za ra unalniöke strukture in sisteme, predvsem pa Miranu Koprivcu, za pomo pri izvajanju vaj in iskanju ter popravljanju napak. Za slednje bi se zahvalil tudi obema recenzentoma, prof. dr. Nikolaju Zimicu in doc. dr. Miri Trebar. Nenazadnje se zahvaljujem vsemötudentom za njihove kritike, pohvale in predloge glede izvajanja vaj pri predmetu Osnove digitalnih vezij.

3

(10)

(11)

1 Priprava na 1. laboratorijske vaje

1.1 Boolova algebra in preklopne funkcije

Preklopne (tudi logi ne) funkcije so funkcije nad preklopnimi (tudi logi nimi) spremenljivkami (spremenljivke, ki lahko zavzamejo vrednosti iz mnoûice {0,1}) in nad katerimi temelji procesiranje podatkov z uporabo digitalnih vezij. Preklopne funkcije (operatorji), elementi nad katerimi operirajo (operandi) in pravila po katerih operirajo so definirani z Boolovo algebro.

Boolovo algebro lahko definiramo kot troj ek {X, O, P}, kjer je X mnoûica elementov Boolove algebre (operandov), O mnoûica osnovnih funkcij (operatorjev), ki vsebuje disnjunkcijo (‚) in konjunkcijo (·), in P mnoûica postulatov oziroma pravil, ki so opisana v nadaljevanju.

1.1.1 Postulati Boolove algebre Zaprtost

P1:x, yœX;x‚y œX P1^ú:x, yœX;x·yœX Nevtralni element

P2:x,0œX;x‚0 =x P2^ú:x,1œX;x·1 =x Komutativnost

P3:x, y œX;x‚y=y‚x P3^ú:x, y œX;x·y=y·x

5

(12)

6 Poglavje 1 Priprava na 1. laboratorijske vaje

Distributivnost

P4:x, y, zœX;x‚(y·z) = (x‚y)·(x‚z) P4^ú:x, y, zœX;x·(y‚z) = (x·y)‚(x·z) Inverzni element

P5:’xœX,÷xœX;x‚x= 1 P5^ú:’xœX,÷xœX;x·x= 0 ätevilo elementov

P6:÷x, yœX;x”=y 1.1.2 Lastnosti Boolove algebre

Iz postulatov izhajajo dolo ene lastnosti, ki jih lahko uporabimo pri poenostavljanju logi nih izrazov. V nadaljevanju je naötetih nekaj bolj uporabnih lastnosti.

Idempotenca

x‚x‚· · ·‚x=x x·x· · · · ·x=x Absorpcija

x‚x·y=x x·(x‚y) =x Asociativnost

(x‚y)‚z=x‚(y‚z) =x‚y‚z (x·y)·z=x·(y·z) =x·y·z DeMorganovo pravilo

(x1‚x2‚· · ·‚xn) =x1·x2· · · · ·xn

(x1·x2· · · · ·xn) =x1‚x2‚· · ·‚xn

(13)

1.2 Podajanje preklopnih funkcij 7

1.2 Podajanje preklopnih funkcij

Vsako preklopno funkcijo lahko podamo na razli ne na ine, pri emer so osnovni na ini slede i:

• Logi ni izraz funkcijo podaja analiti no, tj. kot ena bo, v kateri nastopajo logi ne spremenljivke (operandi), ki so med seboj povezane preko preklopnih funkcij (operatorji).

• Logi na shema funkcijo podaja grafi no, tj. s shemo njene realizacije. Vhodi v shemo opisujejo vhodne spremenljivke, izhodi iz sheme pa izhodne. V shemi uporabljamo logi ne simbole, ki predstavljajo osnovne logi ne operatorje (opozorilo: v razli ni literaturi boste sre ali razli ne logi ne simbole).

• Pravilnostna tabela funkcijo podaja tabelari no, tj. podaja vse moûne kombi- nacije vhodnih vektorjev in funkcijske vrednosti pri posamezni kombinaciji.

Pri tem na levi strani tabele nastopajo vhodne (neodvisne) spremenljivke, ki dolo ajo vhodni vektor, na desni pa izhodne (odvisne) spremenljivke. Po- ljubno preklopno funkcijo z n vhodnimi spremenljivkami lahko opiöemo s pravilnostno tabelo, ki ima2ⁿ vrstic.

• Veitchevega diagramazaenkratöe ne bomo podrobneje obravnavali.

1.3 Osnovne preklopne funkcije

Boolova algebra definira osnovna logi na operatorja, tj. disjunkcijo (or) in konjunkcijo (and). Preko postulata Inverzni element vpeljemo öe negacijo (not).

V nadaljevanju podajamo osnovne logi ne operatorje, s katerimi lahko zapiöemo poljubno preklopno funkcijo in so realizirani tudi znotraj druûine logi nih ipov 7400.

1.3.1 Disjunkcija

Disjunkcija (ALI, OR) vrne logi no 1, ko je na logi no 1 postavljena vsaj ena izmed njenih vhodnih spremenljivk. V logi nem izrazu jo ozna ujemo s simbolom

‚. Slika 1.1 podaja logi ni izraz (a), logi ni simbol (b) in pravilnostno tabelo (c) za disjunkcijo z dvema vhodnima spremenljivkama.

1.3.2 Konjunkcija

Konjunkcija (IN, AND) vrne logi no 1, ko so na logi no 1 postavljene vse vhodne spremenljivke. V logi nem izrazu jo ozna ujemo s simbolom · ali ·, v asih pa simbol celo izpustimo (podobno kot pri mnoûenju). Slika 1.2 podaja logi ni izraz

(14)

y=x1‚x2

x1 x2 y

0 0 0

0 1 1

1 0 1

1 1 1

(a) (b) (c)

Slika 1.1 Logi ni izraz (a), logi ni simbol (b) in pravilnostna tabela (c) za disjunkcijo z dvema vhodnima spremenljivkama.

(a), logi ni simbol (b) in pravilnostno tabelo (c) za konjunkcijo z dvema vhodnima spremenljivkama.

y=x1·x2 =x1x2

x1 x2 y

0 0 0

0 1 0

1 0 0

1 1 1

(a) (b) (c)

Slika 1.2 Logi ni izraz (a), logi ni simbol (b) in pravilnostna tabela (c) za konjunkcijo z dvema vhodnima spremenljivkama.

1.3.3 Negacija

Negacija (NE, NOT) invertira vhodno logi no spremenljivko. V logi nem izrazu jo ozna ujemo s rto nad vhodno spremenljivko. Slika 1.3 podaja logi ni izraz (a), logi ni simbol (b) in pravilnostno tabelo (c) za negacijo.

y=x

x y 0 11 0

(a) (b) (c)

Slika 1.3 Logi ni izraz (a), logi ni simbol (b) in pravilnostna tabela (c) za negacijo.

(15)

1.3 Osnovne preklopne funkcije 9

1.3.4 Peircov operator

Peircov operator (NE ALI, NOR) predstavlja invertirano (negirano) disjunkcijo.

Operator vrne logi no 1, ko so na logi no 0 postavljene vse vhodne spremenljivke.

V logi nem izrazu ga ozna ujemo s simbolom¿. Slika 1.4 podaja logi ni izraz (a), logi ni simbol (b) in pravilnostno tabelo (c) za Peircov operator z dvema vhodnima spremenljivkama.

y=x₁¿x₂= (x₁‚x₂)

x1 x2 y

0 0 1

0 1 0

1 0 0

1 1 0

(a) (b) (c)

Slika 1.4 Logi ni izraz (a), logi ni simbol (b) in pravilnostna tabela (c) za Peircov operator z dvema vhodnima spremenljivkama.

Opozorilo: asociativnost za Peircov operator ne velja: x₁ ¿x₂ ¿x₃”= (x₁ ¿x₂)¿ x₃”=x₁¿(x₂¿x₃)!

1.3.5 Shefferjev operator

Shefferjev operator (NE IN, NAND) predstavlja invertirano (negirano) konjunkcijo.

Operator vrne logi no 0, ko so na logi no 1 postavljene vse vhodne spremenljivke.

V logi nem izrazu ga ozna ujemo s simbolom ø. Slika 1.4 podaja logi ni izraz (a), logi ni simbol (b) in pravilnostno tabelo (c) za Shefferjev operator z dvema

vhodnima spremenljivkama.

y=x1øx2= (x1x2)

x₁ x₂ y

0 0 1

0 1 1

1 0 1

1 1 0

(a) (b) (c)

Slika 1.5 Logi ni izraz (a), logi ni simbol (b) in pravilnostna tabela (c) za Shefferjev operator z dvema vhodnima spremenljivkama.

Opozorilo: asociativnost za Shefferjev operator ne velja: x1øx2øx3”= (x1øx2)ø x3”=x1ø(x2øx3)!

(16)

1.3.6 Ekskluzivni ali

Ekskluzivni ali (XOR, tudi vsota po modulu 2) dveh vhodnih spremenljivk vrne logi no 1, ko logi no vrednost 1 ekskluzivno zavzema ena vhodna spremenljivka.

Pri ve vhodnih spremenljivkah funkcija vrne logi no 1, ko je na logi no vrednost 1 postavljenih liho ötevilo vhodnih spremenljivk, kar si lahko interpretiramo tudi kot vsota po modulu 2 (opozorilo: v Logisimu XOR privzeto ne deluje na tak na in – pod lastnostmi XOR vrat moramo nastaviti polje Multiple-Input Behavior na vrednost When an odd number are on). V logi nem izrazu ekskluzivni ALI ozna ujemo s simbolomÒaliü. Slika 1.6 podaja logi ni izraz (a), logi ni simbol (b) in pravilnostno tabelo (c) za ekskluzivni ali z dvema vhodnima spremenljivkama.

y =x1Òx2=x1x2‚x1x2

x₁ x₂ y

0 0 0

0 1 1

1 0 1

1 1 0

(a) (b) (c)

Slika 1.6 Logi ni izraz (a), logi ni simbol (b) in pravilnostna tabela (c) za ekskluzivni ali z dvema vhodnima spremenljivkama.

1.3.7 Ekvivalenca

Ekvivalenca (XNOR) dveh vhodnih spremenljivk vrne logi no 1, ko sta vhoda enaka in je tako enaka negiranemu ekskluzivnemu ali. Enakost pa ne velja za ve vhodnih spremenljivk. V logi nem izrazu ekvivalenco ozna ujemo s simbolom©.

Slika 1.7 podaja logi ni izraz (a), logi ni simbol (b) in pravilnostno tabelo (c) za ekvivalenco z dvema vhodnima spremenljivkama.

y=x₁©x₂=x₁x₂‚x₁x₂

x1 x2 y

0 0 1

0 1 0

1 0 0

1 1 1

(a) (b) (c)

Slika 1.7Logi ni izraz (a), logi ni simbol (b) in pravilnostna tabela (c) za ekvivalenco z dvema vhodnima spremenljivkama.

(17)

1.4 Analiti no reöevanje preklopnih funkcij 11

1.3.8 Implikacija

Implikacija (IMP) dveh vhodnih spremenljivk, tj. x1 æ x2 vrne logi no 0 le v primeru, da je operand na levi strani (tj. x1) enak 1, operator na desni strani (tj.

x2) pa enak 0. Implikacija nima elektronske implementacije znotraj druûine 7400.

Prav tako operator nima logi nega simbola. Slika 1.8 podaja logi ni izraz (a), in pravilnostno tabelo (b) za implikacijo.

y=x1 æx2=x1‚x2

x1 x2 y

0 0 1

0 1 1

1 0 0

1 1 1

(a) (b)

Slika 1.8 Logi ni izraz (a) in pravilnostna tabela (b) za implikacijo.

Opozorilo: komutativnost za implikacijo ali ne velja: x₁æx₂”=x₂ æx₁!

1.4 Analiti no reöevanje preklopnih funkcij

Pri analiti nemu reöevanju preklopnih funkcij preko postulatov in lastnosti Boolove algebre funkcijo podano z logi nim izrazom preoblikujemo v ûeleno obliko. Kadar ûelimo dolo eno lastnost formalno dokazati, se moramo pri spreminjanju oblike analiti nega izraza striktno drûati postulatov Boolove algebre, pri emer uporabimo le en postulat naenkrat, pri vsakem koraku izpeljave pa pripiöemo postulat, ki smo ga uporabili.

Zgled 1 Z uporabo postulatov dokaûi enakost x‚x=x!

Reöitev 1

x‚x= (x‚x)·1 (P2^ú)

=(x‚x)·(x‚x) (P5)

=x‚(x·x) (P4^ú)

=x‚0 (P5^ú)

=x (P2)

Navadno pri poenostavljanju izrazov korake izpuö amo in nad izrazom neposredno uporabljamo lastnosti, ki sledijo iz postulatov. e naloga od nas eksplicitno ne zahteva uporabe postulatov, jo reöujemo na tak na in. Ker so postulati in lastnosti

(18)

definirani nad osnovnimi logi nimi operatorji (konjunkcija, disjunkcija in negacija), vse funkcije v izrazu najprej izrazimo s temi.

Zgled 2 Poenostavi izraz x2æ¹(x1‚x3) (x1‚x3)²! Reöitev 2

x2æ(x1‚x3) (x1‚x3)

=x₂‚(x₁‚x₃) (x₁‚x₃)

=x2‚(x1‚x3)‚(x1‚x3)

=x2‚x1x3‚x1x3

=x2‚(x1‚x1)x3

=x₂‚x₃

(19)

2 Priprava na 2. laboratorijske vaje

2.1 Zapis preklopnih funkcij

Analiti ni zapis podajamo z logi nim izrazom oziroma logi no ena bo. Pogosto se uporabljajo tri posebne oblike analiti nega zapisa, in sicer normalna, popolna in minimalna. Preklopna funkcija je podana v normalni obliki, e je sestavljena iz najve dveh nivojev logi nih operatorjev. Oblika je popolna, e na prvem nivoju logi nih operatorjev v vseh izrazih nastopajo vse vhodne spremenljivke. Minimalna oblika je najkrajöa moûna oblika zapisa preklopne funkcije.

2.2 Analiti ni zapis in popolne normalne oblike zapisa pre- klopnih funkcij

Pogledali si bomo popolno disjunktivno normalno obliko (PDNO) in popolno konjunktivno normalno obliko (PKNO) zapisa preklopne funkcije.

2.2.1 Popolna disjunktivna normalna oblika (PDNO)

• Disjunktivna: operator 2. nivoja je disjunkcija (‚).

• f(x₁, x₂, ..., xn) =‚²i=0ⁿ^≠1mif(w˛i)

• f(w˛i) ... vrednost funkcije prii-tem vhodnem vektorju (vrstici)

• minterm je konjunktiven izraz - vse vhodne spremenljivke so povezane preko konjunkcije

• mi ... minterm i; mi=x^w₁^1,i·x^w₂^2,i·...·x^wn^n,i;i= 0,1,2, ...,2ⁿ≠1

• x^w =

I x, w= 1 x, w= 0

• wj,i...j-ti bit binarnega zapisaötevila i

• PDNO lahko zapiöemo v krajöi obliki kot f(x1, x2, ..., xn) =‚ⁿ(i1, i2, ..., ik), kjeri1, i2, ..., ik dolo ajo indekse mintermov, ki nastopajo v PDNO.

13

(20)

Recept: pri dolo anju PDNO disjunktivno veûemo tiste minterme, pri katerih je funkcijska vrednost 1. Pri tem sei-ti minterm nanaöa na funkcijsko vrednostf(w˛i) (glej tabelo 2.1).

x₁ x₂ x₃ f(x₁,x₂,x₃) minterm 0 0 0 f(w˛0) m0

0 0 1 f(w˛1) m1

0 1 0 f(w˛2) m2

0 1 1 f(w˛3) m3

1 0 0 f(w˛4) m4

1 0 1 f(w˛5) m5

1 1 0 f(w˛6) m6

1 1 1 f(w˛7) m7

Tabela 2.1 Primer pravilnostne tabele in zaporedja mintermov za preklopno funkcijo treh vhodnih spremenljivk.

Zgled 3 Zapiöi minterm 9, pri 4-ih vhodnih spremenljivkah:

Reöitev 3 Velja torej:

• n= 4,

• i= 9[10]= 1001[2],

• m9=x¹₁x⁰₂x⁰₃x¹₄ =x1x2x3x4.

2.2.2 Popolna konjunktivna normalna oblika (PKNO)

• Konjunktivna: operator 2. nivoja je konjunkcija (&).

• f(x1, x2, ..., xn) = &²_i=0ⁿ^≠1(M2ⁿ≠1≠i‚f(w˛i))

• maksterm je disjunktiven izraz - vhodne spremenljivke so povezane preko disjunkcije

• M₂ⁿ_≠1≠i ... maksterm 2ⁿ≠1≠i; M₂ⁿ_≠1≠i = x^w₁^1,i ‚x^w₂^2,i ‚...‚x^wn^n,i;i = 0,1,2, ...,2ⁿ≠1

• PKNO lahko zapiöemo v krajöi obliki: f(x1, x2, ..., xn) = &ⁿ(im, im≠1, ..., i1), kjerim, im≠1, ..., i1 dolo ajo indekse makstermov, ki nastopajo v PKNO.

Recept: pri dolo anju PKNO konjunktivno veûemo tiste maksterme, pri katerih je funkcijska vrednost 0. Pri tem se (2ⁿ≠1≠i)-ti maksterm nanaöa na funkcijsko vrednostf(w˛i) (glej tabelo 2.2).

(21)

2.2 Analiti ni zapis in popolne normalne oblike zapisa preklopnih funkcij 15 x1 x2 x3 f(x1,x2,x3) maksterm

0 0 0 f(w˛₀) M₇ 0 0 1 f(w˛₁) M₆ 0 1 0 f(w˛₂) M₅ 0 1 1 f(w˛3) M4

1 0 0 f(w˛4) M3

1 0 1 f(w˛5) M2

1 1 0 f(w˛6) M1

1 1 1 f(w˛7) M0

Tabela 2.2 Primer pravilnostne tabele in zaporedja makstermov za preklopno funkcijo treh vhodnih spremenljivk.

Zgled 4 Zapiöi maksterm 9 pri 4-ih vhodnih spremenljivkah.

Reöitev 4 Velja torej:

• n= 4,

• 2ⁿ≠1≠i= 15≠9 = 6,

• 2ⁿ≠1≠i= 6[10] = 0110[2],

• M₉=x⁰₁‚x¹₂‚x¹₃‚x⁰₄=x₁‚x₂‚x₃‚x₄.

Zgled 5 Podano funkcijo pretvori v popolno disjunktivno normalno obliko na dva na ina:

• s pomo jo pravilnostne tabele,

• analiti no z razöiritvijo.

Reöitev 5 Funkcija:

f(x₁, x₂, x₃) =x₁‚x₁x₂‚x₂x₃ je ûe zapisana v disjunktivni normalni obliki, ki pa ni popolna.

Pretvorba s pomo jo pravilnostne tabele

Zapiöimo pravilnostno tabelo, s pomo jo katere lahko zapiöemo PDNO, tako da prepiöemo tiste minterme, pri katerih je vrednost funkcije enaka 1.

e izpiöemo samo indekse teh mintermov, dobimo skrajöano obliko PDNO:

f(x1, x2, x3) =‚³(0,4,5,6,7).

(22)

x1 x2 x3 f(x1,x2,x3) minterm maksterm

0 0 0 1 m₀ M₇

0 0 1 0 m₁ M₆

0 1 0 0 m₂ M₅

0 1 1 0 m3 M4

1 0 0 1 m4 M3

1 0 1 1 m5 M2

1 1 0 1 m6 M1

1 1 1 1 m7 M0

Tabela 2.3 Pravilnostna tabela funkcijef(x₁, x₂, x₃) =x₁‚x₁x₂‚x₂x₃. Zapiöimo PDNO öe v eksplicitni obliki:

f(x₁, x₂, x₃) =x₁x₂x₃‚x₁x₂x₃‚x₁x₂x₃‚x₁x₂x₃‚x₁x₂x₃. Analiti na pretvorba z razöiritvijo

Funkcijo razöirimo v popolno (na prvem nivoju morajo nastopati vse vhodne spre- menljivke):

x1‚x1x2‚x2x3

=x1(x2‚x2)(x3‚x3)‚x1x2(x3‚x3)‚(x1‚x1)x2x3

=x1x2x3‚x1x2x3‚x1x2x3‚x1x2x3‚x1x2x3‚x1x2x3‚x1x2x3‚x1x2x3

=x1x2x3‚x1x2x3‚x1x2x3‚x1x2x3‚x1x2x3

=‚³(7,6,5,4,0)

=‚³(0,4,5,6,7)

2.2.3 Relaciji med makstermi in mintermi

Med mintermi in makstermi zaradi DeMorganovega pravila veljata slede i relaciji:

• mi=M₂ⁿ_≠1≠i,

• Mi=m2ⁿ≠1≠i.

Relaciji lahko uporabimo pri pretvarjanju funkcije iz PDNO v PKNO in obratno.

Pri podanem zapisu najprej pogledamo kateri termi manjkajo:

• e je funkcija podana v PDNO, izpiöemo manjkajo e minterme - v pravilnostni tabeli so soleûni z enicami.

• e je funkcija podana v PKNO, izpiöemo manjkajo e maksterme - v pravilnostni tabeli so soleûni z ni lami.

(23)

2.2 Analiti ni zapis in popolne normalne oblike zapisa preklopnih funkcij 17 S tem smo dobili pozicije termov, ki nastopajo v iskani obliki zapisa preklopne funkcije. Indekse iskanih termov dobimo tako, da nad izpisanimi mintermi oziroma makstermi uporabimo zgoraj navedeni relaciji.

2.2.4 Pretvarjanje med PDNO in PKNO Dva moûna na ina reöevanja:

1. zapiöemo pravilnostno tabelo in iz nje razberemo reöitev, 2. z upoötevanjem relacij med mintermi in makstermi.

Zgled 6 Funkcijo podano v PDNO pretvori v PKNO:

• s pomo jo pravilnostne tabele,

• z upoötevanjem relacij med mintermi in makstermi.

Reöitev 6 Demonstrirajmo oba na ina pretvorbe.

Pretvorba iz PDNO v PKNO: s pomo jo pravilnostne tabele Glej tabelo v prejönjem zgledu!

Prepiöemo maksterme, pri katerih je vrednost funkcije enaka 0.

PKNO:&³(6,5,4) Eksplicitna PKNO:

PKNO:(x₁‚x₂‚x₃)(x₁‚x₂‚x₃)(x₁‚x₂‚x₃).

Pretvorba iz PDNO v PKNO: z upoötevanjem relacij med mintermi in makstermi

Pretvorimo ‚³(0,4,5,6,7) v PKNO:

1. zapiöemo manjkajo e minterme: m₁, m₂, m₃. 2. izra unamo indekse makstermov: M6, M5, M4. 3. reöitev: &³(6,5,4).

Na podoben na in, bi lahko pretvarjali tudi iz PKNO v PDNO.

(24)

(25)

3 Priprava na 3. laboratorijske vaje

3.1 Zapis preklopnih funkcij z Veitchevim diagramom

Veitchevi diagrami igrajo pomembno vlogo pri minimizaciji preklopnih funkcij.

Veitchev diagram prinvhodnih spremenljivkah je sestavljen iz 2ⁿ polj, pri emer posamezno polje vsebuje funkcijsko vrednost pri posameznem mintermu. Postopek zapisovanja Veitchevega diagrama je razmeroma preprost, in sicer izhajamo iz diagrama za eno spremenljivko (glej sliko 3.1(a)). Diagram za dve spremenljivki dobimo tako, da podvojimo diagram za eno spremenljivko. Ozna iti je potrebno tudi pokritja, in sicer tako, da posamezna spremenljivka pokriva polovico Veitchevega diagrama. Pokritja lahko izbiramo na razli ne na ine. V sploönem dobimo diagram za nspremenljivk tako, da podvojimo diagram zan≠1spremenljivk in na novo dodani del pokrijemo z dodano spremenljivko.

m₁ m₀

x m

3m

1

x₁

m₂m₀

x₂ m₆ m₇

m₄ m₅ x₂ m₃ m₂

m₁ m₀

x₃ x₁

(a) (b) (c)

m₁₂m₁₄ x1

m₁₃m₁₅ x₂ m₆ m₄

m₇ m₅ m₉m₁₁

m₈m₁₀ m₃ m₁

m₂ m₀

x₃

x₄

m₂₅m₂₉ x1

m₂₇m₃₁ x₂ m₁₃ m₉

m₁₅m₁₁ m₁₉m₂₃

m₁₇m₂₁ m₇ m₃

m₅ m₁

x₃

m₂₄m₂₈ x1

m₂₆m₃₀ m₁₂m₈

m₁₄m₁₀ m₁₈m₂₂

m₁₆m₂₀ m₆ m₂

m₄ m₀

x₃

x₄

x₅

(d) (e)

Slika 3.1 Slika (a) prikazuje Veitchev diagram za eno vhodno spremenljivko, slika (b) za dve, slika (c) za tri, slika (d) zaötiri, slika (e) pa za pet.

19

(26)

Zgled 7 Funkcijo f(x₁, x₂, x₃, x₄) = ‚⁴(5,7,9,11,13,15) zapiöi v Veitchev dia- gram.

Reöitev 7 V polja, ki se nanaöajo na minterme, pri katerih je funkcijska vrednost enaka 1, vpiöemo enice, ostala polja pa pustimo prazna (glej sliko 3.2).

1 1 x₂

1 1 1 1

x₃

x4

x₁

Slika 3.2 Veitchev diagram funkcijef(x1, x₂, x₃, x₄) =‚⁴(5,7,9,11,13,15).

3.2 Funkcijsko poln sistem

Funkcijsko poln sistem je nabor logi nih funkcij, s katerimi lahko izrazimo katerokoli logi no funkcijo. Iz definicije Boolove algebre sledi, da je{‚,·,¬} funkcijsko poln sistem (operator¬ predstavlja negacijo).

Funkcijsko polnost ugotavljamo na dva na ina:

• s pretvorbo na nek znan funkcijsko poln sistem,

• s preverjanjem pripadnosti osnovnim zaprtim razredom.

Zgled 8 S pretvorbo na negacijo, konjunkcijo in disjunkcijo pokaûi, da je Shefferjev operator funkcijsko poln sistem.

Reöitev 8 S Shefferjevim operatorjem izrazimo negacijo.

x=xx=xøx

S Shefferjevim operatorjem izrazimo konjunkcijo.

x₁x₂=x₁x₂=x₁øx₂= (x₁øx₂)ø(x₁øx₂)

S Shefferjevim operatorjem izrazimo disjunkcijo.

x₁‚x₂=x₁‚x₂=x₁x₂= (x₁øx₁)ø(x₂øx₂) Podobno bi se dalo pokazati za Peircov operator.

(27)

4 Priprava na 4. laboratorijske vaje

4.1 Zaprti razredi in preverjanje funkcijske polnosti sis- tema

Funkcijo polnost nabora logi nih funkcij lahko preverjamo s pripadnostjo nabora osnovnim zaprtim razredom logi nih funkcij (Postov teorem). Osnovni zaprti razredi so slede i:

• T₀ – razred preklopnih funkcij, ki ohranjajo ni lo (f(0,0, . . . ,0) = 0)

• T1 – razred preklopnih funkcij, ki ohranjajo enico (f(1,1, . . . ,1) = 1)

• S – razred sebidualnih funkcij (f(x₁, x₂, . . . , xn) =f(x₁, x₂, . . . , xn))

• L– razred linearnih funkcij (f(x1, x2, ..., xn)œL, f(x1, x2, ..., xn) =

=a0Òa1x2Ò...Òanxn)

• M – razred monotonih funkcij (f(x1, x2, ..., xn)œM,’i, j :

˛

wi<w˛j æf(w˛i)Æf(w˛j))

e nabor odpira vse osnovne razrede, je poln. Nabor odpira nek osnovni razred, e vsaj ena izmed funkcij v podanem naboru ne pripada izbranemu razredu.

Zgled 9 S pomo jo zaprtih razredov preveri funkcijsko polnost nabora {‚,æ,1}.

Reöitev 9 Cilj: Pri vsakem osnovnem razredu ûelimo najti vsaj eno funkcijo iz podanega nabora, ki temu razredu ne pripada.

1. Razred T₀:

• ‚:f(0,0) = 0‚0 = 0; pripada razredu.

• 1 : 1”= 0; ne pripada razredu.

2. Razred T₁:

• ‚:f(1,1) = 1‚1 = 1; pripada razredu.

21

(28)

• æ:f(1,1) = 1æ1 = 1; pripada razredu.

• 1 : 1 = 1; pripada razredu

Nabor{‚,æ,1} ne odpira razredaT₁, torej nabor ni poln. Vseeno nadaljujmo s postopkom.

3. Razred S:

Pripadnost lahko dokazujemo na dva na ina:

• analiti no: ali veljaf(x1, x2, ..., xn) =f(x1, x2, ..., xn),

• tabelari no: ali velja f(w˛i)”=f(w˛₂ⁿ_≠1≠i).

Postopek:

• 1 : (analiti no)

1 = 1

0 = 1 protislovje Funkcija ne pripada razredu S. Vseeno nadaljujmo.

• ‚: (analiti no)

f(x1, x2) =f(x1, x2)

x1‚x2=x1‚x2 (desno stran dopolnimo do PDNO) x1x2=x1(x2‚x2)‚x2(x1‚x1)

x1x2=x1x2‚x1x2‚x1x2‚x1x2

x1x2=x1x2‚x1x2‚x1x2

‚²(3)”=‚²(1,2,3) æ ‚œ/S

• æ: (tabelari no)

x₁ x₂ x₁æx₂

0 0 1

0 1 1

1 0 0

1 1 1

f(w0) =f(w3) – funkcija ne pripadaS.

(29)

4.1 Zaprti razredi in preverjanje funkcijske polnosti sistema 23 4. Razred L:

Funkcijaf(x₁, x₂, . . . , xn) spada v razred linearnih funkcij, e jo lahko zapi- öemo kot

f(x1, x2, . . . , xn) =a0Òa1x1Òa2x2Ò· · ·Òanxn. Pripadnost lahko preverjamo:

• analiti no,

• z Veitchevim diagramom.

Analiti no preverjanje:

• predpostavimo, da funkcija f(x1, x2, . . . , xn) spada v razred linearnih funkcij,

• dolo imo koeficiente a0, a1,· · · , an,

• preverimo, e se dobljena funkcijaa0Òa1x1Òa2x2Ò· · ·Òanxn ujema s podano funkcijo f(x1, x2, . . . , xn).

Postopek:

• ‚:

Predpostavimo, da je disjunkcija linearna funkcija, tedaj jo lahko zapi- öemo kot:

f(x1, x2)L=x1‚x2=a0Òa1x1Òa2x2

f(0,0)L=a₀Òa₁0Òa₂0 =a₀= 0Ò0 = 0 (a₀ = 0) f(0,1)L= 0Òa₁0Òa₂1 =a₂= 0Ò1 = 1 (a₂ = 1) f(1,0)L= 0Òa₁1Òa₂0 =a₁= 1Ò0 = 1 (a₁ = 1) f(x1, x2)L= 0Ò1x1Ò1x2=x1Òx2

Preverimo za vse preostale vhodne vektorje (v primeru protislovja posto- pek ustavimo):

f(1,1) = 1‚1 = 1

f(1,1)L=x₁Òx₂= 1Ò1 = 0 Protislovje. Funkcija ne pripada razredu.

Preverjanje z Veitchevim diagramom:

• Preklopna funkcija spada v razred L, e pri primerjavi pokritij velja popolna enakost ali popolna razli nost vrednosti funkcije.

(30)

Postopek:

• ‚:

Preverimo pokritja:

– x1x2: x1x2 (popolnoma razli na),

– x₁:x₁ (niti popolnoma razli na niti popolnoma enaka).

Funkcija ne pripada razredu.

5. Razred M: Funkcija pripada M, e pri vseh vhodnih vektorjih velja, da je pri manjöem vektorju vrednost funkcije manjöa ali enaka vrednosti pri ve jem vektorju. Relacija je manjöi je definirana na slede i na in:

• Za vhodna vektorja wi in wj velja wi < wj, e za vsako mesto k velja wk,iÆwk,j. Primer: (1,0,0,1,0,1,0,0)<(1,1,0,1,0,1,0,1).

Pri preverjanju pripadnosti je dovolj, da preverimo le sosedne vhodne vektorje.

Vhodna vektorja sta sosedna, e se razlikujeta le na enem mestu. Primer:

(1,0,0,1,0) in (1,0,1,1,0).

Postopek:

• æ:

x₁ x₂ x₁æx₂

0 0 1

0 1 1

1 0 0

1 1 1

Preverjamo samo sosedne vektorje. Sosedni vhodni vektorji so (w0, w1), (w0, w2), (w1, w3) in (w2, w3). Hitro najdemo protislovje, in sicerw0<

w2, f(w0)> f(w2). Funkcija torej ne pripadaM.

Zgled 10 Analiti no preveri ali preklopna funkcijaf(x1, x2, x3, x4) = &⁴(0,1,6,8,9,14) pripada razredu linearnih funkcij.

(31)

4.1 Zaprti razredi in preverjanje funkcijske polnosti sistema 25

x1 x2 x3 x4 f(x1, x2, x3, x4) f(x1, x2, x3, x4)L

0 0 0 0 1 1

0 0 0 1 0 0

0 0 1 0 1 1

0 0 1 1 1 0

0 1 0 0 1 1

0 1 0 1 1 0

0 1 1 0 0 1

0 1 1 1 0 0

1 0 0 0 1 1

1 0 0 1 0 0

1 0 1 0 1 1

1 0 1 1 1 0

1 1 0 0 1 1

1 1 0 1 1 0

1 1 1 0 0 1

1 1 1 1 0 0

Reöitev 10 Postopek:

Predpostavimo, da dana funkcija pripada razredu linearnih funkcij, tedaj jo lahko zapiöemo kot:

f(x1, x2, x3, x4)L=a0Òa1x1Òa2x2Òa3x3Òa4x4

f(0,0,0,0)L=a₀Òa₁0Òa₂0Òa₃0Òa₄0 = 1 (a₀= 1)

f(0,0,0,1)L= 1Òa₁0Òa₂0Òa₃0Òa₄1 = 1Òa₄= 0 (a₄= 1) f(0,0,1,0)L= 1Òa₁0Òa₂0Òa₃1Òa₄0 = 1Òa₃= 1 (a₃= 0) f(0,1,0,0)L= 1Òa10Òa21Òa30Òa40 = 1Òa2= 1 (a2= 0) f(1,0,0,0)L= 1Òa11Òa20Òa30Òa40 = 1Òa1= 1 (a1= 0) f(x1, x2, x3, x4)L= 1Ò0x1Ò0x2Ò0x3Ò1x4= 1Òx4=x4

Preverimo za vse preostale vhodne vektorje (v primeru protislovja postopek usta- vimo):

f(0,0,1,1) = 1

f(0,0,1,1)L= 1Ò1 = 0 Protislovje. Funkcija ne pripada razredu.

(32)

(33)

5 Priprava na 5. laboratorijske vaje

5.1 Minimalne oblike zapisa preklopnih funkcij

Minimalna oblika zapisa preklopne funkcije podaja najkrajöi moûen zapis te funkcije.

Poznamo ve minimalnih oblik zapisa. Pogledali si bomo slede e:

• minimalna disjunktivna normalna oblika (MDNO): dolo a najkraöo disjunktivno normalno obliko zapisa preklopne funkcije,

• minimalna konjunktivna normalna oblika (MKNO): dolo a najkraöo konjunktivno normalno obliko zapisa preklopne funkcije,

• minimalna normalna oblika (MNO): dolo a nakrajöo normalno obliko zapisa preklopne funkcije.

Pri dolo anju minimalne disjunktivne normalne oblike (MDNO) izhajamo iz iska- nja glavnih vsebovalnikov. Glavni vsebovalnik predstavlja najkrajöi konjunktivni izraz, ki je skupen podmnoûici mintermov, ki sestavljajo PDNO podane funkcije.

Najmanjöa mnoûica glavnih vsebovalnikov, ki skupaj pokrijejo celotno mnoûico mintermov v PDNO, predstavlja minimalno disjunktivno normalno obliko.

Pri dolo anju minimalne konjunktivne normalne oblike (MKNO) izhajamo iz dolo- anja MDNO negirane funkcije, ki jo z uporabo DeMorganovega pravila pripeljemo do konjunktivne oblike.

Pri dolo anju minimalne normalne oblike (MNO) upoötevamo dejstvo, da MNO predstavlja krajöo izmed MDNO in MKNO.

Glavne vsebovalnike iö emo na podlagisosednosti med konjunktivni izrazi. Dva konjunktivna izraza sta sosedna, e se razlikujeta po natanko eni negaciji:

• izraza x^w₁¹ ·x^w₂²·...·x^w_iⁱ·...·x^w_nⁿ inx^w₁¹·x^w₂²·...·x^w_iⁱ·...·x^w_nⁿ sta sosedna, ker se razlikujeta le po negaciji nad vhodno spremenljivko z indeksomi.

V sploönem velja, da ima izraz, ki vsebuje n vhodnih spremenljivk, n sosednih izrazov.

27

(34)

Zgled 11 Zapiöi vse izraze, ki so sosedni izrazux₁x₂x₄.

Reöitev 11 V sosednih izrazih nastopajo enake spremenljivke kot v izhodiö nem izrazu. Od izhodiö nega izraza se sosedni razlikujejo po natanko eni negaciji. Sosedni izrazi so torej:

• x₁x₂x₄,

• x1x2x4 in

• x₁x₂x₄.

Glavni vsebovalnik dveh sosednih izrazov dolo imo z upoötevanjem lastnosti, da je disjunkcija dveh termov, ki se razlikujeta natanko po negaciji nad eno spremenljivko, neodvisna od vrednosti te spremenljivke. Glavni vsebovalnik dveh sosednih izrazov x^w₁¹·x^w₂²·...·x^w_i≠1ⁱ^≠1·x^w_iⁱ·x^w_i+1ⁱ⁺¹·...·x^w_nⁿ in x^w₁¹·x^w₂²·...·x^w_i≠1ⁱ^≠1·x^w_iⁱ·x^w_i+1ⁱ⁺¹·...·x^w_nⁿ je torej izrazx^w₁¹·x^w₂²·...·x^w_i≠1ⁱ^≠¹·x^w_i+1ⁱ⁺¹·...·x^w_nⁿ.

Zgled 12 Dolo i glavni vsebovalnik izrazovx₁x₂x₃x₄ in x₁x₂x₃x₄.

Reöitev 12 Izraza se razlikujeta le po negaciji nad spremenljivko x1. Disjunkcija med izrazoma je torej neodvisna od vrednosti te spremenljivke, zato je njun glavni vsebovalnik x2x3x4.

5.2 Veitchev postopek minimizacije

Veitchev postopek minimizacije izkoriö a lastnosti Veitchevega diagrama. Sosednost mintermov je namre neposredno povezana s sosednostjo celic v diagramu. Pri celicah, ki se nahajajo na robovih diagrama se sosednost prenaöa na zrcalno stran (glej sliko 5.1).

Zgled 13 V Veitchevem diagramu za 4 spremenljivke ozna i izraze, ki so sosednji izrazu m₁₄‚m₁₅.

Reöitev 13 Izraz zapiöimo v razöirjeni obliki:

m₁₄‚m₁₅=x₁x₂x₃x₄‚x₁x₂x₃x₄ =x₁x₂x₃ Sosedni izrazi so torej:

• x1x2x3=x1x2x3x4‚x1x2x3x4=m6‚m7

(35)

5.2 Veitchev postopek minimizacije 29

x

x₁

x₂

x₃ x1

(a) (b) (c)

x1

x₂

x₃

x₄

(d) (e)

Slika 5.1Slika (a) prikazuje sosednost v Veitchevem diagramu za 1 vhodno spremenljivko, slika (b) za 2, slika (c) za 3, slika (d) za 4, slika (e) pa za 5.

• x1x2x3=x1x2x3x4‚x1x2x3x4=m12‚m13

• x1x2x3=x1x2x3x4‚x1x2x3x4=m10‚m11

Veitchev diagram z ozna emi sosednimi izrazi prikazuje slika 5.2.

x1

x₂

x₃

x₄

Slika 5.2 Izrazi, ki so sosedni izrazum₁₄‚m₁₅.

Zgled 14 V Veitchevem diagramu za 5 spremenljivk ozna i izraze, ki so sosednji izrazu m₂₂‚m₃₀.

Reöitev 14 Izraz zapiöimo v razöirjeni obliki:

m₂₂‚m₃₀=x₁x₂x₃x₄x₅‚x₁x₂x₃x₄x₅=x₁x₃x₄x₅ Sosedni izrazi so torej:

(36)

• x₁x₃x₄x₅

• x1x3x4x5

• x₁x₃x₄x₅

Veitchev diagram z ozna emi sosednimi izrazi prikazuje slika 5.3.

x1

x₂

x₃

x1

x₃

x₄

x₅

Slika 5.3 Izrazi, ki so sosedni izrazum₂₂‚m₃₀.

5.2.1 Dolo anje minimalne normalne oblike z Veitchevim diagramom Za minimalno normalno obliko (MNO) velja, da predstavlja krajöo izmed minimalne disjunktivne normalne oblike (MDNO) in minimalne konjunktivne normalne oblike (MKNO). Za dolo itev MNO moramo torej najprej dolo iti MDNO in MKNO.

Dolo anje minimalne disjunktivne normalne oblike z Veitchevim diagramom

Postopek dolo anja je slede :

1. Funkcijo predstavimo z Veitchevim diagramom.

2. Poiö emo glavne vsebovalnike, tako da med seboj zdruûujemo im ve jeötevilo sosednih mintermov, pri katerih je funkcijska vrednost enaka 1. Zdruûujemo lahko 1,2,4,8,16,... mintermov. Iö emo najmanjöi nabor pokritij, s katerim pokrijemo vse enice. V vsakem koraku poskuöamo dobiti im ve je pokritje, saj s tem izlo imo ve jeötevilo vhodnih spremenljivk.

3. Zapiöemo MDNO na podlagi glavnih vsebovalnikov.

(37)

5.2 Veitchev postopek minimizacije 31 Dolo anje minimalne konjunktivne normalne oblike z Veitchevim diagramom

1. Negirano funkcijo predstavimo z Veitchevim diagramom.

2. Poiö emo MDNO negirane funkcije.

3. Negiramo MDNO negirane funkcije, s imer dobimo izhodiö no funkcijo.

4. Z upoötevanjem DeMorganovega pravila funkcijo prevedemo v MKNO.

Dolo anje minimalne normalne oblike

1. Dolo imoötevilo operatorjev (logi nih vrat) in operandov (vhodov) za MDNO in za MKNO posebej. Negacij neötejemo.

2. Minimalna oblika je tista, ki ima manjöe ötevilo operatorjev. e je öte- vilo operatorjev pri obeh enako, je minimalna tista, ki ima manjöe ötevilo operandov.

Zgled 15 Za funkcijo f(x₁, x₂, x₃, x₄) =‚⁴(0,4,8,9,10,11,12)dolo i minimalno normalno obliko.

Reöitev 15 Najprej dolo imo MDNO:

1. Nariöemo Veitchev diagram funkcije in ozna imo glavne vsebovalnike (Slika 5.4).

x₁

x₂

x₃

x₄ 1 1

1 1 1

1 1

Slika 5.4 Glavni vsebovalniki funkcije‚⁴(0,4,8,9,10,11,12).

2. Izpiöemo glavne vsebovalnike in s tem MDNO:

f(x₁, x₂, x₃, x₄) =x₁x₂‚x₃x₄ Potem dolo imo MKNO: