1
III. MINIMIZACIJA PREKIDA
Č
KIH FUNKCIJA
III.1
OSNOVNI
POJMOVI
III.2
ODRE
Đ
IVANJE MINIMALNIH DNF I KNF POMO
Ć
U
KARNAUGH-OVIH KARTI
2
III. MINIMIZACIJA PREKIDA
Č
KIH FUNKCIJA
III.1
OSNOVNI
POJMOVI
Minimizacija se naziva odre
đ
ivanje najprostijeg izme
đ
u više izraza kojima se u
jednoj klasi izraza može predstaviti prekida
č
ka funkcija. To može da bude, na
primer, klasa DNF izraza, klasa KNF izraza itd.
Za pore
đ
enje izraza služi neka veli
č
ina koja u najprostijem izrazu ima
minimalnu vrednost, kao, na primer, minimalan broj simbola promenljivih,
simbola operacija itd.
Najve
ć
i zna
č
aj ima minimizacija DNF i KNF izraza prekida
č
kih funkcija.
Najpre se daje definicija odre
đ
enih pojmova koji se koriste prakti
č
no u svim
metodama minimizacije DNF i KNF izraza prekida
č
kih funkcija.
4
III. MINIMIZACIJA PREKIDA
Č
KIH FUNKCIJA
III.1
OSNOVNI
POJMOVI
Za elementarni proizvod
h
2
1
i
i
i
x~
...
x~
x~
se kaže da je deo elementarnog proizvoda
k
2
1
j
j
j
x~
...
x~
x~
ako je
{
h
2
1
i
i
i
x~
,...,
x~
,
x~
}
pravi podskup skupa
{
k
2
1
j
j
j
x~
,...,
x~
,
x~
}
. Za
elementarnu sumu
h
2
1
i
i
i
x~
...
x~
x~
+
+
+
se kaže da je deo elementarne sume
k
2
1
j
j
j
x~
...
x~
x~
+
+
+
ako je
{
h
2
1
i
i
i
x~
,...,
x~
,
x~
}
pravi podskup skupa
{
k
2
1
j
j
j
x~
,...,
x~
,
x~
}
.
Za elementarni proizvod
k
2
1
j
j
j
x~
...
x~
x~
se kaže da predstavlja prostu implikantu
prekida
č
ke funkcije f(x
1
, x
2
, ..., x
n
) ako je implikanta prekida
č
ke funkcije f(x
1
,
x
2
, ..., x
n
) i ako nijedan njegov deo nije implikanta funkcije f(x
1
, x
2
, ..., x
n
). Za
elementarnu sumu
k
2
1
j
j
j
x~
...
x~
x~
+
+
+
se kaže da predstavlja prostu implicentu
prekida
č
ke funkcije f(x
1
, x
2
, ..., x
n
) ako je implicenta prekida
č
ke funkcije f(x
1
,
x
2
, ..., x
n
) i ako nijedan njegov deo nije implicenta funkcije f(x
1
, x
2
, ..., x
n
).
Svaki vektor na kojem prekida
č
ke funkcija ima vrednost 1 propada bar jednoj
prostoj implikanti i svaki vektor na kojem prekida
č
ke funkcija ima vrednost 0
propada bar jednoj prostoj implicenti.
Primer: U izrazu
f(x
1
, x
2
, x
3
, x
4
) =
4
3
2
1
x
x
x
x
+
4
3
2
1
x
x
x
x
+
4
3
2
1
x
x
x
x
+
4
3
2
1
x
x
x
x
+
+
4
3
2
1
x
x
x
x
+
4
3
2
1
x
x
x
x
+
4
3
2
1
x
x
x
x
potpuni proizvod
4
3
2
1
x
x
x
x
je implikanta ali ne prosta, jer elementarni proizvod
3
2
1
x
x
x
, koji predstavlja deo potpunog proizvoda
4
3
2
1
x
x
x
x
, je tako
đ
e implikanta.
Elementarni proizvod
3
2
1
x
x
x
je implikanta ali ne prosta, jer elementarni
proizvod
2
1
x
x
, koji predstavlja deo elementarnog proizvoda
3
2
1
x
x
x
, je tako
đ
e
implikanta. Tek je elementarni proizvod
2
1
x
x
prosta implikanta, jer nijedan
njegov deo nije više implikanta. Zato sada može da se piše
f(x
1
, x
2
, x
3
, x
4
) =
2
1
x
x
+
4
3
2
1
x
x
x
x
+
4
3
2
1
x
x
x
x
+
4
3
2
1
x
x
x
x
+
+
4
3
2
1
x
x
x
x
+
4
3
2
1
x
x
x
x
+
4
3
2
1
x
x
x
x
5
III. MINIMIZACIJA PREKIDA
Č
KIH FUNKCIJA
III.1
OSNOVNI
POJMOVI
Za elementarni proizvod i elementarnu sumu u DNF i KNF koristi se zajedni
č
ki
naziv
č
lan.
Za DNF ili KNF prekida
č
ke funkcije se kaže da je nepreopširan ako se nijedan
ć
lan iz nje ne može udaljiti ili zameniti nekim svojim delom a da tako dobijeni
izraz i dalje predstavlja posmatranu prekida
č
ku funkciju. U suprotnom DNF ili
KNF je preopširna.
Nepreopširna DNF mora predstavljati sumu prostih implikanti i nepreopširna
KNF mora predstavljati proizvod prostih implicenti.
Svaka minimalna DNF ili KNF je nepreopširna.
Primer: DNF
f(x
1
, x
2
, x
3
, x
4
) =
2
1
x
x
+
4
3
2
1
x
x
x
x
+
4
3
2
1
x
x
x
x
+
4
3
2
1
x
x
x
x
+
+
4
3
2
1
x
x
x
x
+
4
3
2
1
x
x
x
x
+
4
3
2
1
x
x
x
x
je preopširna jer se
č
lanovi
4
3
2
1
x
x
x
x
,
4
3
2
1
x
x
x
x
i
4
3
2
1
x
x
x
x
mogu ili zamenjivati
svojim delovima sve dok u njima ne ostane samo
2
1
x
x
ili se mogu i kompletno
izbaciti tako da ostane samo
f(x
1
, x
2
, x
3
, x
4
) =
2
1
x
x
+
4
3
2
1
x
x
x
x
+
4
3
2
1
x
x
x
x
+
4
3
2
1
x
x
x
x
.
I ovo je još uvek preopširna DNF jer se umesto
4
3
2
1
x
x
x
x
može staviti
3
2
1
x
x
x
tako da i
f(x
1
, x
2
, x
3
, x
4
) =
2
1
x
x
+
3
2
1
x
x
x
+
4
3
2
1
x
x
x
x
+
4
3
2
1
x
x
x
x
predstavlja DNF.
I ovo je još uvek preopširna DNF jer iz nje može izbaciti
4
3
2
1
x
x
x
x
tako da
f(x
1
, x
2
, x
3
, x
4
) =
2
1
x
x
+
3
2
1
x
x
x
+
4
3
2
1
x
x
x
x
predstavlja DNF.
Tek je sada dobijena nepreopširna DNF.
7
III. MINIMIZACIJA PREKIDA
Č
KIH FUNKCIJA
III.1
OSNOVNI
POJMOVI
Koriste se dva kriterijuma za odre
đ
ivanje minimalne DNF i KNF. U njima se
č
lan koji se sastoji samo od jednog slova naziva degenerisani
č
lan, dok se
č
lan
koji se sastoji od dva ili više slova naziva nedegenerisan
č
lan.
Prvi kriterijum:
Za DNF odnosno KNF prekida
č
ke funkcije se kaže da je minimalna ako ne
postoji druga DNF odnosno KNF te funkcije sa manje nedegenerisanih
č
lanova
ili sa istim brojem nedegenerisanih
č
lanova ali sa manje slova u tim
č
lanovima.
Drugi kriterijum:
Za DNF odnosno KNF prekida
č
ke funkcije se kaže da je minimalna ako ne
postoji druga DNF odnosno KNF te funkcije u kojoj je zbir slova u
nedegenerisanim
č
lanovima i broja
č
lanova manji.
