Boolova algebra PDF

BOOLOVA ALGEBRA N. Zimic 2-1 1 Boolova algebra Boolova algebra je tako kot drugi dedukativni matematični sistemi definirana z: – množico elementov, – množico operatorjev,...

BOOLOVA ALGEBRA N. Zimic 2-1 1 Boolova algebra Boolova algebra je tako kot drugi dedukativni matematični sistemi definirana z: – množico elementov, – množico operatorjev, – množico aksiomov oziroma postulatov. N. Zimic 2-2 2 1  Osnovne definicije Če je S množica in sta x in y elementa, potem velja zapis: – x  S, element x pripada množici S – y  S, element y ne pripada množici S Množico opišemo tako, da v zavitih oklepajih naštejemo elemente množice: – A = {1,2,3,4}, elementi množice A so števila 1,2,3 in 4 N. Zimic 2-3 3 Osnovne definicije (nad.) Binarni operator, ki je definiran nad množico S, je pravilo, ki vsakemu paru elementov iz S enolično priredi element, ki prav tako pripada množici S. N. Zimic 2-4 4 2  Postulati - splošno Postulati so osnovne predpostavke iz katerih je možno izpeljati vse zakone, teoreme in značilnosti matematičnega sistema. Postulati so osnovne postavke in jih ni mogoče dokazati. N. Zimic 2-5 5 Postulati - splošno (nad.) Postulati so: – Zaprtost – Zakon asociativnosti – Zakon komutativnosti – Element enote – Inverzni element – Zakon distributivnosti N. Zimic 2-6 6 3  Zaprtost Zaprtost. Množica S je zaprta glede na binarni operator, če za vsak par elementov iz množice S in pravila, ki ga definira operator, dobimo element, ki je prav tako element množice S Primer. Množica naravnih števil ℕ={1,2,3,…}, je zaprta glede na operator seštevanja (+), ker za vsak par naravnih števil obstaja vsota, ki je prav tako element množice naravnih števil N. Zimic 2-7 7 Zakon asociativnosti Zakon asociativnosti. Za binarni operator *, ki je definiran nad množico S, velja zakon asociativnosti, kadar je: (x * y) * z = x * (y * z) za vse elemente x, y, z  S N. Zimic 2-8 8 4  Zakon komutativnosti Zakon komutativnosti. Za binarni operator *, ki je definiran nad množico S, velja zakon komutativnosti, kadar je: x*y=y*x za vse pare elementov x, y  S N. Zimic 2-9 9 Nevtralni element Nevtralni element. Množica S ima nevtralni element za binarno operacijo *, kadar obstaja element e  S z lastnostjo: e*x=x*e=x za vsak x  S N. Zimic 2-10 10 5  Inverzni element Inverzni element. Element x  S ima inverzni element y  S, kadar je: x*y=y*x=e kjer je e nevtralni element v množici S za binarni operator *. N. Zimic 2-11 11 Zakon distributivnosti Če sta * in · binarna operatorja nad množico S, potem velja zakon distributivnosti, če: x * (y · z) = (x * y) · (x * z) N. Zimic 2-12 12 6  Aksiomi Boolove algebre Osnove Boolove algebre je postavil g. George Bool leta 1854 Leta 1938 je g. C. E. Shannon uvedel dvovrednostno algebro, imenovano preklopna algebra (switching algebra) Boolova algebra je algebraična struktura, definirana nad elementi množice X in nad binarnima operatorjema konjunkicje in disjunkcije, pri čemer morajo biti izpolnjeni naslednji postulati. N. Zimic 2-13 13 Postulati Zaprtost. – P1: x, y  X ; x y X – P1*: x, y  X ; xy X Nevtralni element. – P2: x ,0  X ; x 0  x – P2*: x ,1  X ; x1  x Komutativnost. – P3: x, y  X ; x y  y x – P3*: x, y  X ; xy  yx N. Zimic 2-14 14 7  Postulati (nad.) Distributivnost. – P4: x, y, z  X ; x ( y  z )  xy  xz – P4*: x, y, z  X ; x  ( yz )  ( x  y )( x  z ) Inverzni element. – P5: x  X , x; xx 1 – P5*: x  X ,  x; x x  0 Število elementov. – P6: Obstajata vsaj dva elementa x, y  X, tako da x  y N. Zimic 2-15 15 Pravila Idempotenca: – x  x ...  x  x – x x... x  x Absorbcija: – x  xy  x – x(x  y)  x Asociativnost: – (x  y)  z  x  ( y  z)  x  y  z – (x y) z  x ( y z)  x y z N. Zimic 2-16 16 8  Pravila (nad.) De Morganov izrek: – x  y ...  z  x y... z – x y... z  x  y ...  z N. Zimic 2-17 17 Primeri dokazov Primer: x x  x x x  ( x  x )1 postulat 2*  (x  x) (x  x ) 5  x x x 4*  x 0 5*  x 2 N. Zimic 2-18 18 9  Primeri dokazov (nad.) Primer: x x  x x x  (x x)  0 postulat 2  (x x)  (x x ) 5*  x (x  x) 4  x1 5  x 2* N. Zimic 2-19 19 Primeri dokazov (nad.) Primer: x x y  x x  x y  x1 x y postulat 2*  x (1  y ) 4  x ((1  y ) 1) 2*  x (( 1  y )( y  y )) 5  x (( y  1 )( y  y )) 3  x (y  1y) 4*  x ( y  y 1) 3*  x (y  y) 2*  x1 5  x 2* N. Zimic 2-20 20 10  Dualnost Postulati so sestavljeni iz dveh delov, originalnega in dualnega Dualnost dosežemo z zamenjavo logičnih vrednosti (0 z 1 in obratno) ter zamenjavo operatorjev konjunkcije in disjunkcije Dualni operator je definiran: f d ( x 1 , x 2 ,..., x n )  f ( x 1 , x 2 ,..., x n ) N. Zimic 2-21 21 Dualnost (nad.) Postulati in pravila (a ) x 0  x (b ) x1  x (a ) x x 1 (b ) x x  0 (a ) x x  x (b ) x x  x x  x (a ) x y  y x (b ) x y  y x (a ) x  ( y  z)  (x  y)  z (b ) x ( y z)  (x y) z (a ) x ( y  z)  x y  x z (b ) x  y z  ( x  y )( x  z ) (a ) (x  y)  x y (b ) (x y)  x  y (a ) x x y  x (b ) x (x  y)  x N. Zimic 2-22 22 11  PREKLOPNE FUNKCIJE IN PREKLOPNA VEZJA N. Zimic 3-1 1 Preklopne funkcije Preklopne spremenljivke (neodvisne spremenljivke): x 1 , x 2 ,..., x n x i  { 0 ,1}, i  1 , 2 ,..., n Preklopne funkcija (odvisna spremenljivka) nad n spremenljivkami: f ( x 1 , x 2 ,..., x n )  { 0 ,1} x1 x2 f ( x 1 , x 2 ,..., x n ) Primer:  Preklopna f ( x1 , x 2 , x 3 )  x1 x 2  x 3 xn funkcija N. Zimic 3-2 2 1  Logični simboli Konjunkcija Disjunkcija Negacija x1 x1 x 2 x1 x1  x 2 x2 x2 x x x1 , x 2 f ( x1 , x 2 ) x1 , x 2 f ( x1 , x 2 ) x x 0 0 0 0 0 0 0 1 0 1 0 0 1 1 1 0 1 0 0 1 0 1 1 1 1 1 1 1 N. Zimic 3-3 3 Primer logične sheme Logična funkcija: f ( x1 , x 2 , x 3 )  x1 x 2  x 3 x1 x 2 x1 x2 x1 x 2  x 3 x3 x3 N. Zimic 3-4 4 2  Pravilnostna tabela Leva stran predstavlja vhodne Vseh vhodnih vektorjev je 2n , vektorje: kjer je n število vhodnih w~  ( w , w ,..., w ) i 1i 2i ni spremenljivk kjer je wji j-ta cifra (z leve) v binarnem zapisu števila i. x 1 , x 2 ,..., x n f ( x 1 , x 2 ,..., x n ) Primer: ~ w f (w ~ ) 0 0 ~  ( 0 ,..., 0 ,1 ,1 ) ~ w f (w ~ ) w 3 1 1 Desna stran predstavlja vrednost   pri določenem vhodnem vektorju ~ w ~ f (w 2n 2 ) 2n 2 ~ w 2 n 1 f (w~ ) 2 n 1 N. Zimic 3-5 5 Pravilnostna tabela (nad.) Leva stran predstavlja vse x1 , x 2 , x 3 f ( x1 , x 2 , x 3 ) možne vhodne vektorje, od 0 0 0 f ( 0 ,0 ,0 )  0 vektorja 0 0 0 do vektorja 1 1 1 0 0 1 f ( 0 ,0 , 1)  0 Na desni strani so funkcijske 0 10 f ( 0 , 1, 0 )  1 vrednosti pri posameznem 0 1 1 f ( 0 , 1, 1)  1 vhodnem vektorju 1 0 0 f ( 1, 0 , 0 )  0 Primer funkcije: 1 0 1 f ( 1, 0 , 1 )  1 1 10 f ( 1, 1, 0 )  0 f ( x1 , x 2 , x 3 )  x1 x 2 x 3  x1 x 2 1 1 1 f ( 1, 1, 1 )  0 N. Zimic 3-6 6 3  Pravilnostna tabela (nad.) Logčna shema za prejšnji primer: f ( x1 , x 2 , x 3 )  x1 x 2 x 3  x1 x 2 x1 x1 x 2 x 3 x2 x3 x1 x 2 x 3  x1 x 2 x1 x2 x1 x 2 N. Zimic 3-7 7 Pravilnostna tabela (nad.) f ( x1 , x 2 , x 3 )  x1 x 2 x 3  x1 x 2 x1 , x 2 , x 3 x1 x 2 x 3 x1 x 2 f ( x1 , x 2 , x 3 ) 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 1 0 1 1 0 1 1 10 0 0 0 0 10 1 1 0 1 1 1 0 0 0 0 1 1 1 0 0 0 N. Zimic 3-8 8 4  Pravilnostna tabela (nad.) Primer pravilnostne tabele za x1 , x 2 , x 3 f1 f2 f3 f4 več funkcij: 0 0 0 0 0 0 0 f1 ( x1 , x 2 , x 3 )  x1 x 2 x 3 0 0 1 0 1 1 1 f 2 ( x1 , x 2 , x 3 )  x1  x 2 x 3 0 10 0 0 0 0 f 3 ( x1 , x 2 , x 3 )  0 1 1 0 0 1 1 1 0 0 0 1 1 1  x1 x 2 x 3  x1 x 2 x 3  x1 x 2 1 0 1 0 1 1 1 f 4 ( x1 , x 2 , x 3 )  x1 x 2  x1 x 3 1 10 1 1 0 0 1 1 1 0 1 0 0 N. Zimic 3-9 9 Mintermi in makstermi Če dve spremenljivki povezujemo s konjunkcijo in pri tem uporabimo še negacijo, dobimo: x y, x y, x y, x y Takšne konjunkcije imenujemo mintermi. Pri n spremenljivkah imamo 2n mintermov. Minterme označujemo s številkami od 0 do 2n-1: m 0 , m 1 ,..., m 2 n  1 N. Zimic 3-10 10 5  Mintermi in maks. (nad.) Splošna enačba minterma je: m i  x 1w 1 i x 2w 2 i... x nw ni i  0 ,1 ,..., 2 n  1  x, pri w  1 xw   x, pri w  0 Minterm m5 za tri spremenljivke: w 1 ,5 w w m 5  x1 x 2 2 ,5 x 3 3 ,5  x 11 x 20 x 31  x 1 x 2 x 3 N. Zimic 3-11 11 Mintermi in maks. (nad.) Podobno je definiran tudi maksterem: M 2 n 1 i  x 1w 1 i  x 2w 2 i ...  x nw n i i  0 , 1,..., 2 n  1 Maxterm M5 za tri spremenljivke w1 ,2 w w M 5  x1  x 2 2 , 2  x 3 3 , 2  x 10  x 21  x 30   x 11  x 20  x 31  x 1  x 2  x 3 N. Zimic 3-12 12 6  Mintermi in maks. (nad.) Lastnosti mintermov: 𝑚 𝑚 𝑚 𝑚 x1 , x 2 x1 x 2 x1 x 2 x1 x 2 x1 x 2 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 1 N. Zimic 3-13 13 Mintermi in maks. (nad.) Lastnosti makstermov: 𝑀 𝑀 𝑀 𝑀 x1 , x 2 x1  x 2 x1  x 2 x1  x 2 x1  x 2 0 0 0 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 1 1 1 0 N. Zimic 3-14 14 7  Mintermi in maks. (nad.) x1 , x 2 , x 3 mintermi makstermi 0 0 0 x1 x2 x3 m0 x1  x2  x3 M 7 0 0 1 x1 x2 x3 m1 x1  x2  x3 M 6 0 1 0 x1 x2 x3 m2 x1  x2  x3 M 5 0 1 1 x1 x2 x3 m3 x1  x2  x3 M 4 1 0 0 x1 x2 x3 m4 x1  x2  x3 M 3 1 0 1 x1 x2 x3 m5 x1  x2  x3 M 2 1 1 0 x1 x2 x3 m6 x1  x2  x3 M 1 1 1 1 x1 x2 x3 m7 x1  x2  x3 M 0 N. Zimic 3-15 15 Mintermi in maks. (nad.) Lastnosti mintermov in makstermov: mi  M 2 n 1 i M i  m 2 n 1 i mi  M 1 m i M 2 n 1 i  0 2 n 1 i n 2 1 2 n 1  mi  1 & M i  0 i0 i0 mi m j  0 i  j M i  M j 1 i  j N. Zimic 3-16 16 8  PDNO Popolna disjunktivna normalna oblika (PDNO): 2 n 1 f ( x 1 , x 2 ,..., x n )   m i fi i 0 fi je vrednost funkcije pri i-tem vhodnem vektorju Lastnosti: – funkcija je popolna: termi (na prvem nivoju) so sestavljeni iz vseh vhodnih spremenljivk – funkcija normalna: sestavljena iz dveh nivojev N. Zimic 3-17 17 PDNO (nad.) x1 , x 2 , x 3 m0 m1 m2 m3 m4 m5 m6 m7 f ( x1 , x 2 , x 3 ) 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 10 0 0 1 0 0 0 0 0 1 0 1 1 0 0 0 1 0 0 0 0 0 10 0 0 0 0 0 1 0 0 0 1 10 1 0 0 0 0 0 1 0 0 0 1 10 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 1 1 N. Zimic 3-18 18 9  PDNO (nad.) Primer zapisa funkcije v PDNO f ( x1 , x 2 , x 3 )  m 0 f 0  m 1 f1  m 2 f 2  m 3 f 3   m 4 f4  m 5 f5  m 6 f6  m 7 f7  m 0 0  m 11  m 2 1  m 3 0   m 41  m 5 0  m 6 0  m 71  m1  m 2  m 4  m 7  x1 x 2 x 3  x1 x 2 x 3  x1 x 2 x 3  x1 x 2 x 3 N. Zimic 3-19 19 PDNO (nad.) x1 m1 x2 x3 x1 m2 x2 x3 f ( x1 , x 2 , x 3 ) x1 m4 x2 x3 x1 m7 x2 x3 N. Zimic 3-20 20 10  PKNO Popolna konjuktinvna normalna oblika (PKNO): 2 n 1 f ( x 1 , x 2 ,..., x n )  & ( M 2 n 1 i  fi ) i0 fi je vrednost funkcije pri i-tem vhodnem vektorju Lasnosti: – funkcija je popolna: termi (na prvem nivoju) so sestavljeni iz vseh vhodnih spremenljivk – funkcija normalna: sestavljena iz dveh nivojev N. Zimic 3-21 21 PKNO (nad.) x1 , x 2 , x 3 M 7 M 6 M 5 M 4 M 3 M 2 M 1 M 0 f ( x1 , x 2 , x 3 ) 0 0 0 0 1 1 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1 1 1 1 0 10 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 0 10 0 1 1 1 1 0 1 1 1 1 10 1 1 1 1 1 1 0 1 1 0 1 10 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 0 1 N. Zimic 3-22 22 11  PKNO (nad.) Primer zapisa funkcije v PKNO f ( x1 , x 2 , x 3 )  ( M 7  f0 ) (M 6  f1 ) ( M 5  f2 ) (M 4  f3 ) (M 3  f4 ) (M 2  f5 ) (M 1  f6 ) (M 0  f7 )  (M 7  0) (M 6  1) ( M 5  1) ( M 4  0) (M 3  1) ( M 2  0) (M 1  0) (M 0  1)  M 7 M 4 M 2 M 1  ( x1  x 2  x 3 ) ( x1  x 2  x 3 ) ( x1  x 2  x 3 ) ( x1  x 2  x 3 ) N. Zimic 3-23 23 PKNO (nad.) x1 M x2 7 x3 x1 M x2 4 x3 f ( x1 , x 2 , x 3 ) x1 M x2 2 x3 x1 M x2 1 x3 N. Zimic 3-24 24 12  PDNO in PKNO Zapis PDNO: f ( x1 , x 2 , x 3 )  m 1  m 2  m 4  m 7   (1 , 2 , 4 , 7 ) Zapis PKNO: f ( x1 , x 2 , x 3 )  M 7 M 4 M 2 M 1  &( 7 , 4 , 2 ,1 ) N. Zimic 3-25 25 PDNO in PKNO (nad.) Pretvorba med oblikami zapisa f ( x 1 , x 2 , x 3 )   (1, 4 , 5 , 6 , 7 ) f ( x1 , x 2 , x 3 )   ( 0 , 2 , 3 )  m 0  m 2  m 3 f ( x1 , x 2 , x 3 )  ( m 0  m 2  m 3 )  m 0 m 2 m 3 f ( x1 , x 2 , x 3 )  M 7 M 5 M 4  & (7 , 5, 4 ) N. Zimic 3-26 26 13  Popolne normalne oblike x1 x1 x2 PDNO x2 PKNO &    xn xn x1 f ( x 1 , x 2 ,..., x n ) x1 f ( x 1 , x 2 ,..., x n ) x2 x2 &   &   xn xn   x1 x1 x2 x2 &    xn xn N. Zimic 3-27 27 Verižne oblike Disjunktivna verižna nenormalna oblika DVNNO xd xc xb xa f ( x 1 , x 2 ,..., x n ) &  &  Konjunktivna verižna nenormalna oblika KVNNO xd xc xb xa f ( x 1 , x 2 ,..., x n )  &  & N. Zimic 3-28 28 14  Drevesna nenormalna oblika Primer disjunktivne in konjunktivne drevesne nenormalne oblike (DDNNO, KDNNO) xa xa  & xb & f ( x 1 ,.., x n ) xb  f ( x 1 ,.., x n )  & xc  xc &  & xd & xd   & N. Zimic 3-29 29 Logične funkcije 2n Za n spremenljivk obstaja 2 logičnih funkcij Za dve neodvisni spremenljivki obstaja poleg operacij konjunkcije in disjunkcije še 14 drugih funkcij N. Zimic 3-30 30 15  Logične funkcije (nad.) Za dve neodvisni spremenljivki obstaja 16 funkcij: x1 x 2 f 0 f 1 f 2 f 3 f 4 f 5 f 6 f 7 f 8 f 9 f 10 f 11 f 12 f 13 f 14 f 15 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 N. Zimic 3-31 31 Logične funkcije (nad.) f0  0 konstanta 0 f1  x1  x 2 x1  x 2 Piercova povezava f 2  x1 x 2 x 2 x1 negacija implikacije f 3  x1 x1 negacija x1 f 4  x1 x 2 x1 x 2 negacija implikacije f5  x2 x2 negacija x2 f 6  x1 x 2  x1 x 2 x1 x 2 seštevanje po modulu 2 f 7  x1 x 2 x1  x 2 Shefferjeva povezava N. Zimic 3-32 32 16  Logične funkcije (nad.) f 8  x1 x 2 x1 x 2 koniunkcija f 9  x1 x 2  x1 x 2 x1  x 2 ekvivalenca f 10  x 2 x2 spremenljivka x2 f 11  x 1  x 2 x1 x 2 implikacija f 12  x 1 x1 spremenljivka x1 f 13  x 1  x 2 x 2 x1 implikacija f 14  x 1  x 2 x1  x 2 disjunkcija f 15  1 preklopna konstanta 1 N. Zimic 3-33 33 Logični simboli Shefferjev Pirceov operator operator x1 x1  x 2 x1 x1  x 2 x2 x2 x1 , x 2 f ( x1 , x 2 ) x1 , x 2 f ( x1 , x 2 ) 0 0 1 0 0 1 0 1 1 0 1 0 1 0 1 1 0 0 1 1 0 1 1 0 N. Zimic 3-34 34 17  Logični simboli Vsota po Ekvivalenca modulu 2 x1 x1 x 2 x1 x1  x 2 x2 x2 x1 , x 2 f ( x1 , x 2 ) x1 , x 2 f ( x1 , x 2 ) 0 0 0 0 0 1 0 1 1 0 1 0 1 0 1 1 0 0 1 1 0 1 1 1 N. Zimic 3-35 35 Različni standardi Obstaja vrsta simbolov za logična vezja – standarde za simbole so postavljale razne organizacije – nekatera podjetja so postavljala svoje standarde, ki so najpogosteje kombinacija standardov – na predavanjih bomo uporabljali standard, ki je uporabljen v učbeniku N. Zimic 3-36 36 18  Različni standardi (nad.) Primeri različnih standardov Konjunkcija Disjunkcija Negacija Gonilnik x1 x1 x2 x1 x 2 x2 x1  x 2 x1 x1 x1 x1 x1 x1 x2 x1 x 2 x2 x1  x 2 x1 x1 x1 x1 x1 x1 x2 & x1 x 2 x2 1 x1  x 2 x1 1 x1 x1 1 x1 N. Zimic 3-37 37 Različni standardi (nad.) Shefferjev op. Pircov op. Vsota po mod. 2 Ekvivalneca x1 x1 x1 x1 x2 x1 x 2 x2 x1  x 2 x2 x1 x 2 x2 x1  x 2 x1 x1 x1 x1 x2 x1 x 2 x2 x1  x 2 x2 x1 x 2 x2 x1  x 2 x1 x1 x1 x1 & x1 x 2 1 x1  x 2  x1 x 2  x1  x 2 x2 x2 x2 x2 N. Zimic 3-38 38 19  Logične sheme V logičnih shemah je preklopna funkcija predstavljena na grafični način Logične sheme so osnova za realizacijo preklopne funkcije Logične sheme poleg logičnih simbolov vsebujejo še dodatne informacije, ki so potrebne za fizično realizacijo (številke priključkov na integriranem vezju, oznako integriranega vezja,...) N. Zimic 3-39 39 Logične sheme (nad.) Primer: f ( x 1 , x 2 , x 3 , x 4 , x 5 , x 6 )  (( x 1  x 2 )  ( x 3 x 4 ) ) x 5 x 6 x1 x2 f ( x1 , x 2 , x 3 , x 4 , x 5 , x 6 ) x3 x4 x5 x6 N. Zimic 3-40 40 20  Realizacija preklopnih funkcij Preklopne funkcije realiziramo z elektronskimi vezji. Najpogosteje so to integrirana vezja. Pri realizaciji logično 0 in 1 običajno predstavimo z različnima nivojema eletrične napetosti. N. Zimic 3-41 41 Realizacija preklopnih funkcij (nad.) Primer električnih nivojev za integrirana vezja v tehnologiji CMOS. 5.0V Logična 1 3.5V Nedefinirana logična vrednost 1.5V Logična 0 0.0V N. Zimic 3-42 42 21  Realizacija preklopnih funkcij (nad.) Primer negatorja Področje vhodne napetosti za logično 0 5V Izhodna napetost kot funkcija vhodne napetosti Izhodna napetost Področje vhodne napetosti za logično 1 0 5V Vhodna napetost N. Zimic 3-43 43 Integrirana vezja Logični operatorji so realizirani v integriranih vezjih. Primer takega vezja je prikazan na sliki: 1 Vcc 14 Primer integriranega vezja 74LS00. 2 13 Številke označujejo številko 3 12 priključka. Priključke štejemo v 4 11 obratni smeri urnega kazalca. 5 10 Priključka št. 7 in 14 sta namenjena 6 9 za napajanje integriranega vezja. 7 Gnd 8 N. Zimic 3-44 44 22  Vennovi diagrami Grafični prikaz relacije med spremenljivkami x y xy xy xy xy N. Zimic 3-45 45 Vennovi diagrami Krog v Venovih diagramih omejuje spremenljivko. V prejšnjem primeru omejuje spremenljivko x oziroma y. Presek krivulj in tudi zunanjost krogov tvorijo funkcije: x y, x y, x y, x y N. Zimic 3-46 46 23  Veitchev diagram Veitchev diagram se uporablja za zapis funkcij Obsega 2n polj, kjer je n število neodvisnih spremenljivk Posebno primeren je pri minimizaciji logičnih funkcij Veitchev diagram izhaja iz Vennovih diagramov Na podoben način lahko zapišemo funkcijo tudi s pomočjo Karnaugovih diagramov N. Zimic 3-47 47 Veitchev diagram (nad.) Področja, ki jih pokriva neodvisna spremenljivka x1 x1 x2 x2 x4 x4 x1 x3 x1 x2 x3 x2 N. Zimic 3-48 48 24  Veitchev diagram (nad.) x1 x1 x2 x2 x4 x4 x3 x3 x3 x4 x3 x4 N. Zimic 3-49 49 Veitchev diagram (nad.) x1 Presečišče posameznih spremenljivk določa m 12 m 14 m6 m4 funkcijo polja. x2 m 13 m 15 m7 m5 x4 Vsako polje predstavlja m9 m 11 m3 m1 minterem m8 m 10 m2 m0 Na sliki je prikazan x1 x 2 x 3 x 4 x3 enajsti minterem N. Zimic 3-50 50 25  Veitchev diagram (nad.) f ( x 1 , x 2 , x 3 , x 4 )   ( 0 , 1, 2 , 3 , 4 , 5 , 6 , 7 , 1 1,1 3 ,1 5 ) f ( x1 , x 2 , x 3 , x 4 )  x1  x 2 x 4  x 3 x 4 x1 1 1 V polja vpisujemo x2 funkcijske vrednosti pri 1 1 1 1 x4 posameznem mintermu 1 1 1 1 1 Vpisujemo samo enice x3 N. Zimic 3-51 51 Veitchev diagram (nad.) Veitchev diagram za 1, 2 in 3 neodvisne spremenljivke x1 x1 x1 m1 x2 m3 m1 x2 m6 m7 m3 m2 m0 m2 m0 m4 m5 m1 m0 x3 N. Zimic 3-52 52 26  Veitchev diagram (nad.) Veitchev diagram za 5 neodvisnih spremenljivk x5 x1 x1 m 25 m 29 m 13 m9 m 24 m 28 m 12 m8 x2 m 27 m 31 m 15 m 11 m 26 m 30 m 14 m 10 x4 m 19 m 23 m7 m3 m 18 m 22 m6 m2 x1 x 2 x 3 x 4 x 5 m 17 m 21 m5 m1 m 16 m 20 m4 m0 x3 x3 N. Zimic 3-53 53 Ločenje Ločenje je poznano tudi kot Shanonov teorem f ( x 1 , x 2 , x 3 ,.., x n )  f ( 0 , x 2 , x 3 ,.., x n ) x 1  f (1 , x 2 , x 3 ,.., x n ) x 1 f ( x 1 , x 2 , x 3 ,.., x n )  ( f ( 0 , x 2 , x 3 ,.., x n )  x 1 ) ( f (1 , x 2 , x 3 ,.., x n )  x 1 ) Funkciji, ki sodelujeta pri ločenju imenujemo funkcijski ostanek f 0 ( x 2 , x 3 ,.., x n )  f ( 0 , x 2 , x 3 ,.., x n ) f 1 ( x 2 , x 3 ,.., x n )  f (1 , x 2 , x 3 ,.., x n ) N. Zimic 3-54 54 27  Ločenje (nad.) Primer ločenja: f ( x1 , x 2 , x 3 )  ( x1  x 2 )  x1 x 2 x 3 f (0 , x 2 , x3 )  (0  x2 )  0 x2 x3 f (1, x 2 , x 3 )  (1  x 2 )  1 x 2 x 3 f ( x 1 , x 2 , x 3 )  f ( 0 , x 2 , x 3 ) x 1  f (1, x 2 , x 3 ) x 1    ( 0  x 2 )  0 x 2 x 3  x 1   (1  x 2 )  1 x 2 x 3  x 1    x 2  x1   x 2  x 2 x 3  x1 N. Zimic 3-55 55 Ločenje (nad.) Postopek ločenja nad vsemi neodvisnimi spremenljivkami privede do PDNO ali PKNO. Primer za PDNO: f ( x 1 , x 2 , x 3 ,.., x n )  f ( 0 , x 2 , x 3 ,..., x n ) x 1  f (1 , x 2 , x 3 ,..., x n ) x 1  ( f ( 0 , 0 , x 3 ,..., x n ) x 2  f ( 0 ,1 , x 3 ,..., x n ) x 2 ) x 1   ( f (1 , 0 , x 3 ,..., x n ) x 2  f (1 ,1 , x 3 ,..., x n ) x 2 ) x 1  x 1 x 2... x n f ( 0 , 0 ,..., 0 )  x 1 x 2... x n f ( 0 , 0 ,..., 1)  ...  x 1 x 2... x n f (1, 1,..., 1)  m 0 f 0  m 1 f 1 ...  m 2 n  1 f 2 n  1 N. Zimic 3-56 56 28  Ločenje (nad.) Primer za PKNO f ( x 1 , x 2 , x 3 ,.., x n )  ( f ( 0 , x 2 , x 3 ,..., x n )  x 1 ) ( f (1 , x 2 , x 3 ,..., x n )  x 1 )  ( ( f ( 0 , 0 , x 3 ,..., x n )  x 2 ) ( f ( 0 ,1, x 3 ,..., x n )  x 2 ) )  x 1 )   ( ( f (1, 0 , x 3 ,..., x n )  x 2 ) ( f (1,1, x 3 ,..., x n )  x 2 ) )  x 1 )  ( x 1  x 2 ...  x n  f ( 0 , 0 ,..., 0 ) )   ( x 1  x 2 ...  x n  f ( 0 , 0 ,..., 1))   ( x 1  x 2 ...  x n  f (1, 1,..., 1) )  (M 2 n 1  f0 ) (M 2n 2  f 1 ) ...  ( M 0  f 2 n 1 ) N. Zimic 3-57 57 Dekompozicija preklopne funkcije Dekompozicija preklopne funkcije je postopek s katerim preklopno funkcijo razdelimo na dva dela. Na tak način funkcijo realiziramo z manjšim številom elementov in priključkov. Dekompozicija preklopne funkcije ni vedno možna. N. Zimic 3-58 58 29  Dekompozicija preklopne funkcije (nad.) Grafična predstavitev preklopne funkcije x1 x2 f ( x 1 , x 2 ,..., x n )  Preklopna xn funkcija N. Zimic 3-59 59 Dekompozicija preklopne funkcije (nad.) Grafična predstavitev dekompozicije preklopne funkcije x i1 x i2 h ( x i1 , x i 2 ,..., x i s ) Preklopna  x is funkcija h x i s 1 f ( x 1 , x 2 ,..., x n ) Preklopna  x in funkcija g N. Zimic 3-60 60 30  Dekompozicija preklopne funkcije (nad.) Funkcija ima dekompozitno značilnost, če velja: f ( x 1 , x 2 ,..., x n )  g ( h ( x i1 , x i 2 ,..., x i s ), x i s  1 ,..., x i n ) 1 s  n { x i1 , x i 2 ,..., x i s }  { x i s 1 , x i s  2 ,..., x i n }   { x i1 , x i 2 ,..., x i s }  { x i s  1 , x i s  2 ,..., x i n }  { x 1 , x 2 ,..., x n } N. Zimic 3-61 61 Preklopna diferenca Kdaj je funkcija odvisna od spremenljivke? f ( x1 , x2 ,..., 0,..., xn ) - funkcija, ko je xi enak 0 f ( x1 , x2 ,...,1,..., xn ) - funkcija, ko je xi enak 1 Funcija ni odvisna od spremeljivke xi, če velja: f ( x 1 , x 2 ,..., 0 ,..., x n )  f ( x 1 , x 2 ,...,1,..., x n ) N. Zimic 3-62 62 31  Preklopna diferenca (nad.) Preklopna (boolova) diferenca podaja odvisnost funkcije od vhodne spremenljivke 0, funkcija ni odvisna od spremenljivke x i df ( x1 , x2 ,..., xn )   1, funkcija je odvisna od spremenljivke x i dxi  g , funkcija je odvisna od x pod pogojem g  i df ( x 1 , x 2 ,..., x n )  f ( x 1 , x 2 ,..., 0 ,..., x n )  f ( x 1 , x 2 ,..., 1..., x n ) dx i N. Zimic 3-63 63 Preklopna diferenca (nad.) Primer: f ( x1 , x 2 , x 3 , x 4 )  x1  x 2 x 4  x 3 x 4 df ( x 1 , x 2 , x 3 , x 4 )  ( 0  x 2 x 4  x3 x 4 ) ( 1  x 2 x 4  x3 x 4 )  dx 1  1 ( x 2 x 4  x 3 x 4 )  x 2 x 4  x 3 x 4 Odvisnost lahko določimo tudi z minimizacijo preklopne funkcije. Če funkcija ni odvisna od vhodne spremenljivke, bo le ta pri minimizaciji odpadla. N. Zimic 3-64 64 32  Funkcijsko poln sistem N. Zimic 4-1 1 Funkcijsko poln sistem Funkcijsko poln sistem je množica funkcij, s katerimi lahko realiziramo katerokoli preklopno funkcijo Funkcijsko poln sistem, ki izhaja iz postulatov, predstavljajo: – konjunkcija, disjunkcija, negacija Funkcijsko polnost lahko ugotovimo s prevedbo nabora funkcij na znan funkcijsko poln sistem N. Zimic 4-2 2 1  Funkcijsko poln sist. (nad.) Primer preverjanja funkcijske polnosti sistema: nabor x1  x 2 x1 x 2 x  , &, x1  x 2 x1 x 2 x , x1  x 2 x1  x 2 x &, x1 x 2 x1 x 2 x  ( x1  x 2 )  ( x1  x 2 ) ( x1  x1 )  ( x 2  x 2 ) x  x  ( x1  x1 )  ( x 2  x 2 ) ( x1  x 2 )  ( x1  x 2 ) x  x N. Zimic 4-3 3 Funkcijsko polni sist. (nad.) Primer preverjanja funkcijske polnosti sistema: nabor x1  x 2 x1 x 2 x ,0 ( x1 0 ) x 2 ( x1 ( x 2 0 ) ) 0 x 0 ,, 0 x1  x 2 (( x 1  0 )  ( x 2  0 ))  0 x  0 N. Zimic 4-4 4 2  Zaprti razredi Množica M je podmnožica množice funkcij: M  P2 Funkcija f (x1,x2,..., xn) je element množice M: f ( x 1 , x 2 ,..., x n )  M Če s funkcijo f ne moremo realizirati nobene funkcije, ki ne bi bila vsebovana v množici M, je množica M zaprt razred. N. Zimic 4-5 5 Zaprti razredi (nad.) Na razpolago imamo funkciji konjunkcijo in disjunkcijo: f ( x 1 , x 2 )  x1 x 2  M g ( x1 , x 2 )  x1  x 2  M Z omenjenim naborom ne moremo realizirati funkcije: h (0, 0 )  1 N. Zimic 4-6 6 3  Zaprti razredi (nad.) Obstaja 5 osnovnih zaprtih razredov: – T0 - razred ohranjanja ničle – T1 - razred ohranjanja enice – S - razred sebidualnih funkcij – L - razred linearnih funkcij – M - razred popolnoma monotonih funkcij Množica P2 je tudi zaprt razred, ki je hkrati tudi univerzalna množica N. Zimic 4-7 7 Značilnost zaprtih razredov T0 -razred ohranjanja konstante 0 f ( x 1 , x 2 ,..., x n )  T 0 : f ( 0 , 0 ,..., 0 )  0 T1 -razred ohranjanja konstante 1 f ( x 1 , x 2 ,..., x n )  T 1 : f (1 ,1 ,..., 1 )  1 S - razred sebidualnih funkcij f ( x 1 , x 2 ,..., x n )  S : f ( x 1 , x 2 ,..., x n )  f ( x 1 , x 2 ,..., x n ) L - razred linearnih funkcij f ( x 1 , x 2 ,..., x n )  L : f ( x 1 , x 2 ,..., x n )  a 0  a 1 x 1  a 2 x 2 ...  a n x n N. Zimic 4-8 8 4  Značilnost zaprtih razredov (nad.) M - razred popolnoma monotonih funkcij f ( x 1 , x 2 ,..., x n )  M ~  w : w ~ f (w~ )  f (w ~ ) i j i j – vektorje primerjamo po bitnih mestih. Če se vektor razlikuje v več kot dveh bitnih mestih in pri tem prihaja do protislovja, potem relacije ne moremo določiti! ( 0 , 0 , 0 , 0 )  ( 0 , 0 ,1 , 0 ) ( 0 , 0 , 1, 1 )  ( 0 , 1, 1, 1 ) ( 1 , 1 , 0 , 0 ) ( 0 , 0 , 1 , 0 ) primerjava ni možna! N. Zimic 4-9 9 Zaprti razredi Funkcijski nabor je funkcijsko poln, če funkcije odpirajo zaprte razrede: F  { f 1 , f 2 ,..., f n } 1) f i  T0 fi  F 2) f i  T1 fi  F 3) fi  S fi  F 4) fi  L fi  F 5) fi  M fi  F N. Zimic 4-10 10 5  Zaprti razredi (nad.) Preverjanje funkcijske polnosti za nabor funkcij: F  {  , ,1} – Razred T0 0 0  0 0 0  0 1 0 – Razred T1 11  1 1 11 11 – Razred S x1  x 2  x1  x 2 x1 x 2  x1 x 2 1 1 N. Zimic 4-11 11 Zaprti razredi (nad.) – Razred L x1  x 2  a 0  a 1 x1 a 2 x 2 x1 x 2  a 0  a 1 x1 a 2 x 2 1  a0 – Razred M x 1  x 2  monotona x 1 x 2  monotona 1  monotona N. Zimic 4-12 12 6  Zaprti razredi (nad.) T0 T1 S L M x1  x 2      x1 x 2      1      Nabor funkcij F  {  , ,1} ni funkcijsko poln sistem, ker ne odpira razreda T1 N. Zimic 4-13 13 Shefferjev funkcijsko poln sistem Funkcijo lahko podamo v popolni Shefferjevi normalni obliki PSNO: 2 n 1 f ( x 1 , x 2 ,..., x n )   ( fi  si ) i0 Kjer je si Shefferjev minterm: s i  x 1w 1 i  x 2w 2 i ...  x nw ni i  0 ,1 ,..., 2 n  1 N. Zimic 4-14 14 7  Shefferjev funkcijsko poln sistem (nad.) Primer: f ( x1 , x 2 , x 3 , x 4 )  x 3  x1 x 2 x 4 f ( x1 , x 2 , x 3 , x 4 )  x 3  ( x1 x 2 x 4 )  x 3  ( x1  x 2  x 4 ) N. Zimic 4-15 15 Shefferjev funkcijsko poln sistem (nad.) Shema vezja za prejšnji primer: x1 x2 f ( x1 , x 2 , x 3 , x 4 ) x4 x3 N. Zimic 4-16 16 8  Pierceov funkcijsko poln sistem Funkcijo lahko podamo v popolni Piercevi normalni obliki PPNO: 2 n 1 f ( x 1 , x 2 ,..., x n )   ( f i  P2 n  1  i ) i0 Kjer je P2n-1-i Piercev maksterm: P2 n  1  i  x 1w 1 i  x 2w 2 i ...  x nw ni i  0 ,1 ,..., 2 n  1 N. Zimic 4-17 17 Pierceov funkcijsko poln sistem (nad.) Primer: f ( x1 , x 2 , x 3 , x 4 )  x 3  x1 x 2 x 4 f ( x1 , x 2 , x 3 , x 4 )  x 3  ( x1 x 2 x 4 )  x 3  ( x1  x 2  x 4 )  x 3  ( x1  x 2  x 4 ) N. Zimic 4-18 18 9  Pierceov funkcijsko poln sistem (nad.) Shema vezja za prejšnji primer: x1 f ( x1 , x 2 , x 3 , x 4 ) x2 x4 x3 N. Zimic 4-19 19 10  MINIMIZACIJA PREKLOPNIH FUNKCIJ N. Zimic 5-1 1 Glavni vsebovalnik Glavni vsebovalnik je konjunktivni izraz, ki je disjuktivno vsebovan v opazovani preklopni funkciji tako, da ne obstaja noben krajši konjunktivni izraz. Za minimalno disjunktivno normalno obliko moramo med glavnimi vsebovalniki izbrati samo tiste, ki so potrebni. Potrebni vsebovalniki vsebujejo vse minterme, ki sestavljajo preklopno funkcijo. N. Zimic 5-2 2 1  Sosednost Konjunkciji sta sosednji, če se razlikujeta samo po eni negaciji in imata isti nabor spremenljivk. Ista definicija velja tudi za minterme Primer sosednjih konjunkcij: x1 x 2 x 3 x 4 x1 x 2 x 4 x 5 x 6 x1 x 2 x 3 x 4 x1 x 2 x 4 x 5 x 6 N. Zimic 5-3 3 Sosednost (nad.) Sosednje konjunkcije lahko v preklopni funkciji opustimo na osnovi postulata P4*, P5 in P2* x1 x 2 x 4 x 5 x 6  x1 x 2 x 4 x 5 x 6  ( x 2  x 2 ) x1 x 4 x 5 x 6   x1 x 4 x 5 x 6 Večina postopkov za minimizacijo preklopnih funkcij temelji na sosednosti N. Zimic 5-4 4 2  Quinova metoda minimizacije Postopek – funkcijo zapišemo z mintermi – poiščemo sosednje konjunkcije – postopek iskanja konjunkcij ponavljamo, dokler le te obstajajo – poiščemo potrebne glavne vsebovalnike – iz potrebnih glavnih vsebovalnikov sestavimo minimalno obliko funkcije N. Zimic 5-5 5 Quinova metoda minimizacije (nad.) Primer: f ( x 1 , x 2 , x 3 , x 4 )   ( 0 ,1 , 2 , 8 ,10 ,11 ,14 ,15 ) n  4 n  3 n  2 x1 x2 x3 x4 x1 x 2 x 3 x2 x4 Na osnovi sosednosti x1 x2 x3 x4 x1 x 2 x 4 x1 x 3 iščemo glavne x1 x2 x3 x4 x2 x3 x4 x1 x2 x3 x4 x2 x3 x4 vsebovalnike x1 x2 x3 x4 x1 x 2 x 4 x1 x2 x3 x4 x1 x 2 x 3 x1 x2 x3 x4 x1 x 3 x 4 x1 x2 x3 x4 x1 x 3 x 4 x1 x 2 x 3 N. Zimic 5-6 6 3  Quinova metoda minimizacije (nad.) Iskanje potrebnih glavnih vsebovalnikov m0 m1 m2 m 8 m 10 m 11 m 14 m 15 x1 x 3     x2 x4     x1 x 2 x 3   Iz potrebnih vsebovalnikov sestavimo minimalno disjunktivno normalno obliko f ( x1 , x 2 , x 3 , x 4 )  x1 x 3  x 2 x 4  x1 x 2 x 3 N. Zimic 5-7 7 Quinova metoda minimizacije (nad.) Primer: f ( x 1 , x 2 , x 3 , x 4 )   (1 , 4 , 6 , 7 , 8 , 9 ,10 ,11 ,15 ) n  4 n  3 n  2 x1 x 2 x 3 x 4 x2 x3 x4 x1 x 2 x1 x 2 x 3 x 4 x1 x 2 x 4 x1 x 2 x 3 x 4 x1 x 2 x 3 x1 x 2 x 3 x 4 x1 x 3 x 4 x1 x 2 x 3 x 4 x2 x3 x4 x1 x 2 x 3 x 4 x1 x 2 x 3 x1 x 2 x 3 x 4 x1 x 2 x 4 x1 x 2 x 3 x 4 x1 x 2 x 4 x1 x 2 x 3 x 4 x1 x 2 x 3 N. Zimic 5-8 8 4  Quinova metoda minimizacije (nad.) Iskanje potrebnih glavnih vsebovalnikov m1 m4 m6 m7 m8 m 9 m 10 m 11 m 15 x1 x 2     x2 x3 x4   x1 x 2 x 4   x1 x 2 x 3   x1 x 3 x 4   x2 x3 x4   f ( x1 , x 2 , x 3 , x 4 )  x1 x 2  x 2 x 3 x 4  x1 x 2 x 4  x 2 x 3 x 4 N. Zimic 5-9 9 Veitchev postopek minimizacije Sosednji mintermi v veitchevem diagramu x1 m 12 m 14 m6 m4 sosednji mintermi so kar x2 m 13 m 15 m7 m5 sosedi v veitchevem x4 m9 m 11 m3 m1 diagramu m8 m 10 m2 m0 mintermi na robu x3 diagrama imajo sosede tudi N. Zimic na drugi strani 5-10 10 5  Veitchev postopek minimizacije (nad.) Sosednje konjunkcije v veitchevem diagramu x1 m 12 m 14 m6 m4 x2 m 13 m 15 m7 m5 x4 m9 m 11 m3 m1 m8 m 10 m2 m0 x3 N. Zimic 5-11 11 Veitchev postopek minimizacije (nad.) Sosednje konjunkcije v veitchovem diagramu x5 x1 x1 m 25 m 29 m 13 m9 m 24 m 28 m 12 m8 x2 m 27 m 31 m 15 m 11 m 26 m 30 m 14 m 10 x4 m 19 m 23 m7 m3 m 18 m 22 m6 m2 m 17 m 21 m5 m1 m 16 m 20 m4 m0 x3 x3 N. Zimic 5-12 12 6  Veitchev postopek minimizacije (nad.) Primer: f ( x 1 , x 2 , x 3 , x 4 )   ( 0 ,1 , 2 , 8 ,10 ,11 ,14 ,15 ) x1 x1 x 3 f ( x1 , x 2 , x 3 , x 4 )  1  x1 x 2 x 3  x 2 x 4  x1 x 3 x2 1 x4 1 1 1 1 1 1 x2 x4 x3 x1 x 2 x 3 N. Zimic 5-13 13 Veitchev postopek minimizacije (nad.) f ( x 1 , x 2 , x 3 , x 4 )   (1 , 4 , 6 , 7 , 8 , 9 ,10 ,11 ,15 ) Primer: x2 x3 x4 x1 x1 x 2 x 4 1 1 f ( x1 , x 2 , x 3 , x 4 )  x2 1 1  x1 x 2  x 2 x 3 x 4  x4  x 2 x 3 x 4  x1 x 2 x 4 1 1 1 1 1 x1 x 2 x3 x2 x3 x4 N. Zimic 5-14 14 7  Minimalna konjukntivna normalna oblika Do MKNO pridemo preko MDNO: – funkcijo negiramo – tako dobljeno funkcijo minimiziramo (MDNO) – rezultat ponovno negiramo – s pomočjo De Morganovega pravila jo pretvorimo v MKNO N. Zimic 5-15 15 Minimalna konjukntivna normalna oblika (nad.) Primer: f ( x 1 , x 2 , x 3 , x 4 )   ( 0 ,1 , 2 , 8 ,10 ,11 ,14 ,15 ) f ( x1 , x 2 , x 3 , x 4 ) : f ( x1 , x 2 , x 3 , x 4 ) : x1 x1 1 1 1 1 x2 x2 1 1 1 1 x4 x4 1 1 1 1 1 1 1 1 N. Zimic x3 x3 5-16 16 8  Minimalna konjukntivna normalna oblika (nad.) Negirana funkcija v MDNO: f ( x1 , x 2 , x 3 , x 4 )  x1 x 2  x 2 x 3  x1 x 3 x 4  x1 x 3 x 4 S pomočjo De Morganovega izreka pretvorimo v MKNO: f ( x1 , x 2 , x 3 , x 4 )  ( x1  x 2 ) ( x 2  x 3 ) ( x1  x 3  x 4 ) ( x1  x 3  x 4 ) N. Zimic 5-17 17 Minimalna konjukntivna normalna oblika (nad.) Primer: f ( x 1 , x 2 , x 3 , x 4 )   (1 , 4 , 6 , 7 , 8 , 9 ,10 ,11 ,15 ) f ( x1 , x 2 , x 3 , x 4 ) : f ( x1 , x 2 , x 3 , x 4 ) : x1 x1 1 1 1 1 x2 x2 1 1 1 1 x4 x4 1 1 1 1 1 1 1 1 N. Zimic x3 x3 5-18 18 9  Minimalna konjukntivna normalna oblika (nad.) Negirana funkcija v MDNO: f ( x1 , x 2 , x 3 , x 4 )  x1 x 2 x 4  x 2 x 3 x 4  x1 x 2 x 3  x1 x 2 x 4 S pomočjo De Morganovega izreka pretvorimo v MKNO: f ( x1 , x 2 , x 3 , x 4 )  ( x1  x 2  x 4 ) ( x 2  x 3  x 4 )   ( x1  x 2  x 3 ) ( x1  x 2  x 4 ) N. Zimic 5-19 19 Minimizacija nepopolnih funkcij Funkcija je lahko le delno definirana Pri nekaterih mintermih funkcija ni določena To nedefiniranost lahko pri mimimizaciji upoštevamo kot enico ali ničlo, odvisno od tega, kaj pripelje do ugodnejše minimizacije V Veitchevem diagramu označimo nedefinirana polja s črko X N. Zimic 5-20 20 10  Minimizacija nepopolnih funkcij (nad.) Funkcija: f ( x 1 , x 2 , x 3 , x 4 )   (1 , 3 , 7 ,11 ,15 ) Nedefinirane vrednosti: d ( x1 , x 2 , x 3 , x 4 )   ( 0 , 2 ,5 ) x1 x2 1 1 X x4 f ( x1 , x 2 , x 3 , x 4 )  x 3 x 4  x1 x 4 1 1 1 X X N. Zimic x3 5-21 21 Minimizacija nepopolnih funkcij (nad.) Obstaja tudi druga popolnoma enakovredna rešitev: x1 x2 1 1 X x4 f ( x1 , x 2 , x 3 , x 4 )  x 3 x 4  x1 x 2 1 1 1 X X x3 N. Zimic 5-22 22 11  Ostale pomembne preklopne funkcije N. Zimic 6-1 1 Variantnost preklopne funkcije Funkcija n neodvisnih vhodnih spremenljivk je invariantna na zamenjavo dveh spremenljivk, če velja: f ( x 1 , x 2 ,.., x i ,..., x j ,..., x n )  f ( x 1 , x 2 ,.., x j ,..., x i ,..., x n ) i  j Pri zamenjavi dveh neodvisnih spremenljivk med seboj, se funkcijska vrednost ne spremeni. Zamenjavo (transpozicijo) formalno zapišemo: ( i , j ) f ( x 1 , x 2 ,..., x n ) i  j N. Zimic 6-2 2 1  Simetrične funkcije Funkcija je popolno simetrična, če je invariantna za vse zamenjave: (1 , 2 ) f , (1 , 3 ) f ,..., (1 , n ) f Če je invariantna samo pri nekaterih zamenjavah, je funkcija delno simetrična Funkcija je popolnoma nesimetrična, če ne obstaja noben par spremenljivk, pri katerem bi bila funkcija invariantna N. Zimic 6-3 3 Simetrične funkcije (nad.) Simetričnost opazujemo tudi pri negaciji vhodnih spremenljivk. Nabor vhodnih spremenljivk, z upoštevanjem negacije, je: x w i  { x 1w 1 i , x 2w 2 i ,..., x nw n i } Če je funkcija simetrična pri i-tem naboru, takšen nabor imenujemo i-ti simetrijski nabor neodvisnih spremenljivk. Vseh naborov je 2n N. Zimic 6-4 4 2  Simetrične funkcije (nad.) Pri ugotavljanju simetričnosti funkcije moramo preverjati invariantnost funkcije pri vseh naborih spremenljivk (negacijah spremenljivk). Funkcijo pri i-tem naboru spremenljivk zapišemo: f ( x 1w 1 i , x 2w 2 i ,..., x nw ni ) N. Zimic 6-5 5 Popolnoma simetrične funkcije Potreben in zadosten pogoj, da je preklopna funkcija popolnoma simetrična je, da obstaja množica simetrijskih števil A={...,a,...}, kjer je a med 0 in n. Če ima a vhodnih spremenljivk vrednost 1, potem mora biti vrednost funkcije tudi 1. Popolnoma simetrično funkcijo zapišemo: f ( x 1 , x 2 ,..., x n )  f A ( x 1w1 i , x 2w 2 i ,..., x nw n i )  f A ( x w i ) N. Zimic 6-6 6 3  Popolnoma simetrične funkcije (nad.) Primer simetrične funkcije. Funkcija je po vrednosti 1, če sta nič ali dve vhodni spremenljivki po vrednosti 1 f { 0 , 2 } ( x1 , x 2 , x 3 )  x1 x 2 x 3  x1 x 2 x 3  x1 x 2 x 3  x1 x 2 x 3 nič spremenljivk dve spremenljivki po vrednosti ena po vrednosti ena N. Zimic 6-7 7 Popolnoma simetrične funkcije (nad.) Primer (nad.) f { 0 , 2 } ( x1 , x 2 , x 3 )  x1 , x 2 , x 3 f ( x1 , x 2 , x 3 )  x1 x 2 x 3  x1 x 2 x 3  x1 x 2 x 3  x1 x 2 x 3 0 0 0 1 0 0 1 0 x1 0 1 0 0 0 1 1 1 x2 1 0 1 0 10 0 0 1 10 1 1 0 1 0 1 1 0 1 x3 1 1 1 0 N. Zimic 6-8 8 4  Popolnoma simetrične funkcije (nad.) Poleg možice A obstaja tudi dopolnilna možica, tako da velja A  A' U A  A'  U  { 0 ,1 ,..., n } Množica U vsebuje vsa števila od 0 do n, kjer je n število neodvisnih vhodnih spremenljivk Pri možici U velja: f U ( x w i )  1 N. Zimic 6-9 9 Negacije pri simetričnih funkcijah Negacija simetrične funkcije je tudi simetrična funkcija: B  C M ( A )  A  {a | a  U  a  A} f A ( x 1w 1 i , x 2w 2 i ,..., x nw ni )  f B ( x 1w 1 i , x 2w 2 i ,..., x nw ni ) Negacija vhodnih spremenljivk: f A ( x 1w 1 i , x 2w 2 i ,..., x nw ni )  f B ( x 1w 1 i , x 2w 2 i ,..., x nw ni ) B  {b | b  n  a , a  A} N. Zimic 6-10 10 5  Negacije pri simetričnih funkcijah (nad.) Dualna funkcija je tudi simetrična funkcija: f A ( x 1w 1 i , x 2w 2 i ,..., x nw ni )  f B ( x 1w 1 i , x 2w 2 i ,..., x nw ni ) B  {b | b  n  a , a  A } N. Zimic 6-11 11 Negacije pri simetričnih funkcijah (nad.) Primeri: f { 0 , 2} ( x1 , x 2 , x 3 )  x1 x 2 x 3  x1 x 2 x 3  x1 x 2 x 3  x1 x 2 x 3 U  { 0 ,1 , 2 , 3 } n  3 f { 0 , 2 } ( x 1 , x 2 , x 3 )  f {1 , 3 } ( x 1 , x 2 , x 3 ) f { 0 , 2 } ( x 1 , x 2 , x 3 )  f {1 , 3 } ( x 1 , x 2 , x 3 ) f { 0 , 2 } ( x1 , x 2 , x 3 )  f { 0 , 2 } ( x1 , x 2 , x 3 ) N. Zimic 6-12 12 6  Konjunkcija in disjunkcija simetričnih funkcij Disjunkcija ohranja simetričnost: f C ( x 1w 1 i , x 2w 2 i ,..., x nw ni )  f A ( x 1w 1 i , x 2w 2 i ,..., x nw ni )  f B ( x 1w 1 i , x 2w 2 i ,..., x nw ni ) C  A B Konjunkcija ohranja simetričnost: f C ( x 1w 1 i , x 2w 2 i ,..., x nw ni )  f A ( x 1w 1 i , x 2w 2 i ,..., x nw ni ) f B ( x 1w 1 i , x 2w 2 i ,..., x nw ni ) C  A B N. Zimic 6-13 13 Konjunkcija in disjunkcija simetričnih funkcij (nad.) Primer: f { 2} ( x1 , x 2 )  x1 x 2 f {1} ( x 1 , x 2 )  x 1 x 2  x 1 x 2 Disjunkcija ohranja simetričnost: f {1 , 2 } ( x 1 , x 2 )  f { 2 } ( x 1 , x 2 )  f { 1} ( x 1 , x 2 ) f {1 , 2 } ( x 1 , x 2 )  x 1 x 2  x 1 x 2  x 1 x 2 N. Zimic 6-14 14 7  Konjunkcija in disjunkcija simetričnih funkcij (nad.) Primer: f {1} ( x 1 , x 2 )  x 1 x 2  x 1 x 2 f {1 , 2 } ( x 1 , x 2 )  x 1 x 2  x 1 x 2  x 1 x 2 Konjunkcija ohranja simetričnost: f {1} ( x 1 , x 2 )  f {1} ( x 1 , x 2 ) f { 1 , 2 } ( x 1 , x 2 ) f {1} ( x 1 , x 2 )  ( x 1 x 2  x 1 x 2 ) ( x 1 x 2  x 1 x 2  x 1 x 2 ) f {1} ( x 1 , x 2 )  x 1 x 2  x 1 x 2 N. Zimic 6-15 15 Ločenje simetričnih funkcij Ločenje simetričnih funkcij ohranja simetričnost: f C ( x 1w 1 i , x 2w 2 i ,..., x nw ni )  x j f A ( x 1w 1 i , x 2w 2 i ,..., x nw ni )   x j f B ( x 1w 1 i , x 2w 2 i ,..., x nw ni ) C  B  { d | d  a  1, a  A } N. Zimic 6-16 16 8  Ločenje simetričnih funkcij (nad.) Primer: f { 2 } ( x1 , x 2 , x 3 )  x1 x 2 x 3  x1 x 2 x 3  x1 x 2 x 3  x 3 ( x1 x 2  x1 x 2 )  x 3 ( x1 x 2 )  x 3 f {1} ( x 1 , x 2 )  x 3 f { 2 } ( x 1 , x 2 ) N. Zimic 6-17 17 Testiranje funkcij na simetričnost Funkcija je simetrična, če je invariantna pri transpozicijah: (1 , 2 ) f , (1 , 3 ) f ,..., (1 , n ) f Funkcijo pa je potrebno testirati na simetričnost pri vseh vhodnih naborih, ki jih je 2n: f ( x 1w 1 i , x 2w 2 i ,..., x nw ni ) Vseh testiranj je (n-1)·2n, vendar se to število lahko prepolovi, ker negacija ohranja simetričnost. N. Zimic 6-18 18 9  Testiranje funkcij na simetričnost (nad.) Funkcijo lahko testiramo tudi s pomočjo Veitchevega diagrama. Številke v posameznih kv