TECHNIKA CYFROWA I MIKROKOMPUTERY

WYKŁAD 5

27.03.2003

MINIMALIZACJA FUNKCJI LOGICZNYCH

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI LOGICZNYCH

Metody minimalizacji funkcji logicznych:
• metoda Quine’a-McCluskeya
• minimalizacja funkcji słabo określonych
• faktoryzacja
Minimalizacja zespołu funkcji przełączających

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI LOGICZNYCH

METODA QUINE’A McCLUSKEYA

Metoda ta jest używana, gdy stosowanie metod tablicowych 
staje się kłopotliwe. W celu znalezienia minimalnej 
alternatywnej postaci normalnej funkcji wykonać należy 
następujące czynności:
a) Przedstawione w postaci binarnej zespoły lub wartości 
zmiennych, dla których funkcja jest równa 1 lub nieokreślona 
należy wpisać w kolumnie porządkując je jednocześnie według 
liczy jedynej w zespole. U góry kolumny wpisuje się ciąg 
zawierający same zera (o ile należy do F

1

 lub F

-

), następnie 

grupę ciągów zawierających dokładnie jedną jedynkę, dwie 
jedynki itd. Ilość jedynek w liczbie binarnej nazywamy 
indeksem -w grupach znajdują się więc liczby o jednakowych 
indeksach. Poszczególne grupy należy pooddzielać liniami. 
Ciągi te dopowiadają pełnym iloczynom funkcji, przy czym 
literze x

i

’ odpowiada 0, a literze x

i

 odpowiada 1 

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI LOGICZNYCH

METODA QUINE’A McCLUSKEYA

b) należy porównać ze sobą kolejne ciągi jednej grupy ze 
wszystkimi ciągami następnej grupy, łącząc ze sobą ciągi 
różniące się jedną cyfrą binarną. W wyniku połączenia np. 1011 
z 1001 powstaje ciąg 10-1, który wpisuje się do następnej 
kolumny. Przy obu połączonych ciągach stawia się znaki 
świadczące o tym ,że nie są one prostymi implikantami (z tym , 
że porównuje się je dalej, tak aby znaleźć wszystkie możliwe 
połączenia). Łączenie to odpowiada przeprowadzeniu operacji 
niepełnego sklejania. Np. ciąg 1011 odpowiada implikantowi 
x

1

x

2

’x

3

x

4

, 1001 - x

1

x

2

’x

3

’x

4

. Mamy x

1

x

2

’x

3

x

4

+ x

1

x

2

’x

3

’x

4

= x

1

x

2

’x

4

+ 

x

1

x

2

’x

3

x

4

+ x

1

x

2

’x

3

’x

4

, przy czym x

1

x

2

’x

4

 odpowiada ciągowi 10-1, 

który wpisuje się do nowej kolumny, a sklejone już implikanty 
nadal można użyć do sklejania z innymi. Jeżeli któryś z ciągów 
nie da się połączyć z żadnym innym, to jest on prostym 
implikantem, co oznacza się gwiazdką. 

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI LOGICZNYCH

METODA QUINE’A McCLUSKEYA

c) W drugiej kolumnie wpisuje się wyniki wszystkich połączeń 
dokonanych w pierwszej kolumnie, przy czym wyniki połączeń 
1 u 2 oddziela się od wyników połączeń grupy 2 i 3 itd., 
tworząc nowe grupy. Następnie, analogiczny jak poprzednio, 
porównuje się ze sobą kolejne ciągi nowo utworzonych grup z 
ciągami grup następnych, łącząc ze sobą różniące się jedyną 
cyfrą (a więc mające kreski na tych samych pozycjach). 
Połączenie np. 10-1 z 00-1 daje -0-1. Wynik ten wpisuje się do 
trzeciej kolumny. Nie wolno łączyć ciągów mających kreski na 
różnych pozycjach, np. 10-1 i 1-01. Odpowiadające im 
implikanty  x

1

x

2

’x

4

 i  x

1

x

3

’x

4

 nie podlegają sklejaniu.

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI LOGICZNYCH

METODA QUINE’A McCLUSKEYA

d) Opisana procedura trwa dopóty, dopóki nie skończą się 
możliwości łączenia. W  wyniku otrzymuje się zbiór wszystkich 
prostych implikantów danej funkcji, które można zmienić na 
postać literową.

TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

PRZYKŁAD

Minimalizacja całkowicie określonej funkcji czterech 
zmiennych:
y=f(x

1

,x

2

,x

3

,x

4

)=(4, 7, 9, 10, 12, 13, 14, 15)

Funkcja ta jest równa 1 dla następujących zespołów 
zmiennych: 0100, 0111, 1001, 1010, 1100, 1101, 1110, 1111.
Po uporządkowaniu tych ciągów otrzymuje się tablicę:

TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

PRZYKŁAD

KOLUMNA 1

KOLUMNA 2

KOLUMNA 3

0100  V
1001  V
1010  V
1100  V
0111  V
1101  V
1110  V
1111  V

-100  



1-01  

1-10  



110-  V
11-0  V

-111  



11-1  V
111-  V

11--  



TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

PRZYKŁAD

Stosując do niej opisaną powyżej procedurę dostaje się 
następujące proste implikanty:
-100

=

x

2

x

3

’x

4

’

1-01

=

 x

1

x

3

’x

4

1-10

=

 x

1

x

3

x

4

’

-111

=

 x

2

x

3

x

4

11--

=

 x

1

x

2

TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

PRZYKŁAD

0100

1001

1010

1100

0111

1101

1110

1111

-100

x

2

x

3

’x

4

’

V

V

1-01

x

2

x

3

’x

4

V

V

1-10

x

1

x

3

x

4

V

V

-111

x

2

x

3

x

4

V

V

11--

x

1

x

2

V

V

V

V

TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

PRZYKŁAD

Dla znalezienia postaci końcowych funkcji należy się posłużyć 
tablicą Quine’a. Wiersze tej tablicy odpowiadają prostym 
implikantom, a kolumny zespołom wartości zmiennych, dla 
których funkcja jest równa 1 - a więc jedynkom funkcji. Znaki w 
tablicy pokazują jakie jedynki funkcji pokrył dany implikant. Ze 
zbioru wszystkich prostych implikantów należy wybrać te, 
które są niezbędne do pokrycia wszystkich jedynek funkcji, a 
więc wszystkich kolumn tablicy. Jeżeli w którejś z kolumn 
znajduje się tylko jeden znak V - to odpowiadający mu 
implikant jest niezbędny (zasadniczy prosty implikant). W 
rozpatrywanym przykładzie końcowa funkcja będzie 
następująca:
y= x

2

x

3

’x

4

’+x

1

x

3

’x

4

+x

1

x

3

x

4

’+x

2

x

3

x

4

Postać ta jest jednocześnie postacią minimalną.

TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

Zbiór wszystkich zasadniczych prostych implikantów 
nazywamy jądrem funkcji. W przykładzie jądro stanowią 
wszystkie implikanty wchodzące do minimalnej APN funkcji. 
Jeżeli tak nie jest, czyli jeżeli zasadnicze proste implikanty nie 
pokryją wszystkich funkcji , to spośród pozostałych 
implikantów należy wybrać minimalną liczbę implikantów, 
które realizują to pokrycie. Przed tym tablicę można uprościć 
wykreślając wiersze odpowiadające implikantom zasadniczym 
oraz wszystkie kolumny pokryte przez te implikanty. 

TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

PRZYKŁAD

W tablicy jądro funkcji stanowi 
tylko implikant F pokrywający 
jedynki b, c, g, h. Tak więc wiersz 
F i kolumny b, c, g, h można 
wykreślić z tablicy. Otrzymamy 
następującą tablicę.

a b c d e

f

g h

A V

V

B V

V

C

V V

D

V V

E

V

V

F

V V

V V

TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

PRZYKŁAD

Do tej tablicy można zastosować 
metodę Petricka poszukiwania 
minimalnego pokrycia. Metoda ta 
opiera się na następującym 
rozumowaniu:
dla pokrycia jedynki a potrzebny 
jest implikant A lub B, dla 
pokrycia d potrzebny jest 
implikant A lub C, dla pokrycia e - 
implikant D lub E i wreszczie dla 
pokrycia f - implikant B lub D. W 
celu znalezienia minimlanergo 
pokrycia możemy napisac 
równanie Boole’a:
(A+B)(A+C)(D+E)(B+D)=1

a d e

f

A V V

B V

V

C

V

D

V V

E

V

TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

PRZYKŁAD

Po wymnożeniu i zastosowaniu prawa pochłaniania otrzymuje 
się:
AD+ABE+BCD+BCE=1
Wyznaczono w ten sposób wszystkie pokrycia funkcji prostymi 
implikantami (do każdego wchodzi oczywiście również funkcja 
F), czyli mamy wyznaczone wszystkie postacie końcowe 
funkcji. Jak widać minimalną będzie postać zawierająca 
implikanty A, C i F.
y=F+A+C

TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

Jeżeli po wykreśleniu kolumn i wierszy tablicy pokryć 
odpowiadających jądru funkcji tablica ma dalej duże wymiary, 
można ją jeszcze uprościć stosując reguły dominacji kolumn i 
wierszy. Wiersz a

i

 dominuje nad wierszem a

j

 (a

i

a

j

) wtedy i 

tylko wtedy, gdy wiersz a

i

 pokrywa wszystkie kolumny, które 

pokrywa wiersz a

j

. Wiersz a

i

 nazywamy dominującym, 

natomiast wiersz a

j

 nazywamy zdominowanym.

Analogicznie kolumna b

i

 dominuje nad kolumną b

j

 wtedy i tylko 

wtedy, gdy b

i

 jest pokrywana przez te wszystkie wiersze przez, 

które jest pokrywana kolumna b

j.

 

TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

a

b

c

d

e

F

g

h

i

j

k

l

A

V

V

V

V

V

V

V

B

V

V

V

V

V

V

V

C

V

V

V

V

D

V

V

V

V

V

E

V

V

V

V

V

V

F

V

V

V

G

V

V

V

H

V

V

V

V

V

V

V

I

V

V

V

V

TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

Rozpatrzmy tablicę przedstawioną na poprzednim slajdzie. Nie 
ma w niej implikantów (wierszy) zasadniczych. Bezpośrednie 
zastosowanie metody Petricka byłoby bardzo pracochłonne. 
Można uprościć tablicę:
aj, bc, ek, fd, gk, lhc,
oraz
AC, BF, EG, HI,
Można więc wykreślić z tablicy dominujące kolumny a, b, e, f, 
g, h, l oraz zdominowane wiersze C, F, G, I 

TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

Wyniku uzyskano tablicę. Brak w 
tej tablicy wtórnych implikantów 
zasadniczych, ale można 
wykreślić wiersz D (AD). 

Otrzymamy w ten sposób tablicę 
z wtórnym zasadniczym 
implikantem A pokrywającym 
kolumnę j. Stosując dalej metodę 
Petricka otrzymamy funkcję:
(B+H)(B+E)(E+H)=BH+BE+HE
Istnieją zatem trzy minimalne 
pokrycia ABE, ABH, AHE.

c

d

i

j

k

A

V

V

B

V

V

V

D

V

E

V

V

H

V

V

c

i

j

k

A

V

B

V

V

E

V

V

H

V

V

TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

Minimalizacja metodą Quine’a McCluskeya może być również 
przeprowadzona na zespołach wartości zmiennych 
przedstawionych w postaci liczby dziesiętnych. Kolejne punkty 
algorytmu będą wówczas następujące:
a) Odpowiedniki dziesiętne zespołów wartości zmiennych, dla 
których funkcja jest równa jedności bądź nieokreślona, dzieli 
się na grupy o jednakowych indeksach.
b) Łączy się ze sobą dwie liczby z sąsiednich grup, różniące się 
o potęgę dwójki, przy czym liczba należąca do grupy o 
mniejszym indeksie musi być mniejsza. Należy więc kolejne 
liczby jednej grupy porównać z wszystkimi większymi od nich 
liczbami sąsiedniej grupy. W przypadku, gdy porównywane 
liczby różnią się o 1,2,4,8...itd., a więc dadzą się połączyć, 
zapisuje się je w następnej kolumnie (mniejsza na początku), a 
obok w nawiasie różnicę  

TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

c) W drugim etapie porównuje się pierwsze liczby w wierszach 
sąsiednich grup nowo utworzonej kolumny, w sposób 
analogiczny jak poprzednio. Wiersze, w których liczby w 
nawiasach są jednakowe, a pierwsze liczby różnią się o potęgę 
dwójki, można połączyć ze sobą i umieścić w trzeciej kolumnie. 
Obok w nawiasach umieszcza się różnice wpisane w nawiasach 
poprzedniej kolumnie oraz różnice pierwszych licz połączonych 
wierszy. Podbnie jak poprzednio liczby w każdym wierszu 
muszą być uporządkowane co do wielkosci, a więc np.. 
Wynikiem połaczenia 12,14 (2) i 13,15(2)będzie 12,13,14,15,
(1,2)
d) Opisana procedura trwa tak długo, aż skończą się 
możliwości łączenia.

TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

PRZYKŁAD

f(x

1

, x

2

, x

3

, x

4

)=(4,7,9,10,12,13,14,15)

Realizację kolejnych kroków przedstawiono w tablicy. 
Gwiazdkami oznaczone są otrzymane proste implikanty. 
Wpisuje się je do tablicy Quine’a, przy czym wypełnienie 
tablicy jest bardzo łatwe - znaki V należy postawić w 
miejscach, gdzie numer kolumny wchodzi do wyrażenia 
opisującego wiersz (przed nawiasem).

TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

PRZYKŁAD

IDNEKS

KOLUMNA 1

KOLUMNA 2

KOLUMNA 3

1

2

3

4

4  V

9 V

10 V
12 V

7 V

13 V
14 V
15 V

4, 12 (8) *
9, 13 (4) *

10, 14 (4) *

12,13 (1) V
12,14 (2) V

7,15 (8) *

13,15 (2) V
14,15 (1) V

12,13,14,15,(1,2) 

*

TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

PRZYKŁAD

4 9 10 12 7 13 14 15

4, 12 (8)

V

V

9, 13 (4)

V

V

10, 14 (4)

V

V

7, 15 (8)

V

V

12,13,14,15 (1,2)

V

V

V

V

TECHNIKA CYFROWA I MIKROKOMPUTERY

METODA QUINE’A McCLUSKEYA

PRZYKŁAD

Postać minimalna funkcji jest następująca:
y=4,12 (8) +9,13 (4) + 10,14 (4) + 7,15 (8)
Dla zakodowania wyniku należy zamienić pierwszą liczbę 
każdego implikantu na liczbę bierną i skreślić bity, których 
wagi odpowiadają liczbom podanym w nawiasach.
Y=100+101+110+111
Nieskreślonym bitom odpowiadają afirmacje (1) lub negacje (0) 
zmiennych, a więc ostatecznie:
y=x

2

x

3

’x

4

’+ x

2

x

3

’x

4

+ x

2

x

3

x

4

’+ x

2

x

3

x

4

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI SŁABO OKREŚLONYCH

W wielu praktycznych zagadnieniach występują funkcje wielu 
zmiennych, określone jedynie dla niewielkiej liczby zespołów 
wartości zmiennych. Wypisywanie wszystkich zespołów 
wartości zmiennych, dla których funkcja jest nieokreślona (F

-

), 

niezbędne w metodzie Quine’a-McCluskeya, nie ma wówczas 
sensu. W tym, przypadku generuje się proste implikanty 
funkcji porównując zespoły wartości zmiennych, dla których 
funkcja jest równa jedności (jedynki funkcji), z zespołami 
wartości zmiennych, dla których funkcja jest równa zeru 
(zerami funkcji).

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI SŁABO OKREŚLONYCH 

PRZYKŁAD

Weźmy funkcję czterech zmiennych określoną następująco:
F

1

={0, 2, 3, 14}, F

0

-{10, 11, 15}

W postaci zero-jedynkowej zbiory te przedstawiają się następująco:

0000
0010 1010

F

1

=

0111   F

0

=

1011

1110  1111

Porównując oba zbiory widać, że wszystkie elementy F

0

 (zera 

funkcji) zaczynają się od 1, a pierwsze trzy elementy F

1

 zaczynają 

się od 0.Wystarczy więc wziąć taki implikant, który dla x

1

=0 będzie 

róny 1, a pokryte zostaną pierwsze trzy jedynki funkcji, a nie 
pokryte żadne z zer. Takim implikantem jest oczywiście x

1

’. Ostatni 

element F

1

 różni się od wszystkich elementów F

0

 tym, że wystepuje 

w nim kombinacja x

2

=1, x

4

=0. Rozumując jak wyżej stwierdzimy, że 

odpowiednim implikantem jest x

2

x

4

’ czyli y = x

1

’+x

2

x

4

’ 

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI SŁABO OKREŚLONYCH

Aby znaleźć minimalną postać normalna funkcji trzeba znaleźć 
wszystkie proste implikanty funkcji. Algorytm postępowania 
zostanie wyjaśniony na przykładzie funkcji pięciu zmiennych 
f(x

1

, x

2

, x

3

, x

4

, x

5

) zadanej następująco F

1

={3, 12, 13, 16, 25, 

29}, F

0

={1, 10, 21, 28}

czyli

00011
01100

00001

F

1

=

01101

F

0

=

01010

10000

10101

11001

11100

11101

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI SŁABO OKREŚLONYCH

a) Należy zbudować tablicę, której wiersze odpowiadają 
elementom F

0

, a kolumny elementom F

1

 Porównując teraz 

kolejno elementy F

1

 ze wszystkimi elementami F

0

 i wypisując 

zmienne, wartością których różnią się te elementy, przy czym 
jeżeli w elemencie z F

1

 zmienna mała wartość 1 to wypisujemy 

jej afirmację, a jeżeli mała wartość 0 - to negację. Ten punkt 
algorytmu przedstawia tabela: 

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI SŁABO OKREŚLONYCH

00011

01100

01101

10000

11001

11101

00001

x

4

x

2

x

3

 x

5

’

x

2

x

3

x

1

x

5

’

x

1

x

2

x

1

x

2

x

3

01010

x

2

’x

5

x

3

x

4

’

x

3

x

4

’x

5

x

1

x

2

’x

4

’

x

1

x

4

’x

5

x

1

 x

3

x

4

’x

5

10101

x

1

’x

3

’x

4

x

1

’x

2

x

5

’

x

1

’x

2

x

3

’x

5

’

x

2

x

3

’

x

2

11100

x

1

’x

2

’x

3

’x

4

x

5

x

1

’

x

1

’x

5

x

2

’x

3

’

’x

3

x

5

x

5

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI SŁABO OKREŚLONYCH 

PRZYKŁAD

b) Dla każdej jedynki zespołu wartości zmiennych z F

1

 znajduje 

się generowane przez nią proste implikanty, tworząc wyrażenia, 
będące iloczynem sum wszystkich liter, odróżniających daną 
jedynkę od wszystkich zer z F

0

. Np. dla zespołu 00011 tworzymy 

wyrażenie:

x

4

(x

2

’+x

5

)(x

1

’+x

3

’+x

4

)(x

1

’+x

2

’+x

3

’+x

4

+x

5

)=1.

Uzasadnienie powyższego postępowania jest następujące: aby 
pokryć jedynkę 00011 i nie pokryć żadnego zera funkcji, należy 
utworzyć implikant, do którego wchodzi x

4

, bo odróżnia on 

jedynkę od zera 00001, x

2

’ lub x

5

 - aby odróżnić od zera 01010 

x

1

’ lub x

3

’ lub x

4

 itd. Po wymnożeniu powyższego wyrażenia 

otrzymuje się wszystkie proste implikanty, pokrywające jedynkę 
00011. Łatwo zauważyć, że w rozpatrywanym wyrażeniu x

4

 

pochłania

 

(x

1

’+x

3

’+x

4

) oraz (x

1

’+x

2

’+x

3

’+x

4

+x

5

) wystarczy 

więc mnożyć: x

4

(x

2

’+x

5

)= x

4

x

2

’+x

4

x

5

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI SŁABO OKREŚLONYCH 

PRZYKŁAD

Podobnie mamy dla następujących jedynek funkcji:
(

x

2

+x

3

+x

5

’)(x

3

+x

4

’)(x

1

’+x

2

+x

5

’)x

1

’= x

1

’

(

x

2

+x

3

+x

5

’)(x

3

+x

4

’)=

x

1

’

(

x

2 

x

3 

+ x

2 

x

4

’+x

3 

x

3

+x

3

x

4

’+ x

5

’x

3

+x

5

’x

4

’)=

x

1

’

(

x

3

[x

2

+x

4

’+x

5

’+ 1]+x

4

’[x

2

+x

5

’])= x

1

’

(

x

3

+

x

4

’[x

2

+x

5

’])=

x

1

’x

3

+

x

1

’x

4

’x

2

+x

1

’x

4

’x

5

’

(x

2

+x

3

)(x

3

+x

4

’+x

5

)(x

1

’+x

2

)(x

1

’+x

5

)=(x

3

+x

2 

x

4

’+ x

2 

x

5

)(x

1

’x

1

’+ x

1

’x

5 

+x

2

x

1

’+x

2

x

5

)=(x

3

+x

2 

x

4

’+ x

2 

x

5

)(x

1

’[1+ x

5 

+x

2

]+x

2

x

5

)=

(x

3

+x

2 

x

4

’+ x

2 

x

5

)(x

1

’+x

2

x

5

)=x

2

x

5

+

 

x

1

’x

3

+x

1

’x

2

x

4

’

(x

1

+x

5

’)(x

1

+x

2

’+x

4

’)(x

3

’+x

5

’)(x

2

’+x

3

’)=(x

1

+x

2

’x

5

’+x

5

’x

4

’)(x

3

’+x

2

’x

5

’)=

 x

2

’x

5

’+x

1

x

3

’+x

3

’x

4

’x

5

’

(x

1

+x

2

)(x

1

+x

4

’+x

5

)(x

2

+x

3

’)(x

3

’+x

5

)=(x

1

+x

2

x

4

’+x

2

x

5

)(x

3

’+x

2

x

5

)=

x

2

x

5

+x

1

x

3

’

 

+x

2

x

3

’x

4

’

(x

1

+x

2

+x

3

)(x

3

+x

4

’+x

5

)x

2

x

5

=x

2

x

5

 

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI SŁABO OKREŚLONYCH 

PRZYKŁAD

Otrzymaliśmy wszystkie proste implikanty funkcji. W celu 
znalezienia minimalnego pokrycia tworzymy tablicę 
implikantów identyczną jak w metodzie Quine’a McCluskeya.

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI SŁABO OKREŚLONYCH 

PRZYKŁAD

00011

01100

01101

10000

11001

11101

x

2

’x

4

V

x

4

x

5

V

x

1

’x

3

V

V

x

1

’x

2

x

4

’

V

V

x

1

’x

4

’x

5

’

V

x

2

x

5

V

V

V

x

2

’x

5

’

V

x

1

x

3

’

V

V

x

3

’x

4

’x

5

’

V

x

2

x

3

’x

4

’

V

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI SŁABO OKREŚLONYCH 

PRZYKŁAD

Po wykreśleniu wiersza x

2

x

5

 

(zasadniczy) i pokrytych przez 
niego kolumn oraz po 
zastosowaniu praw dominacji 
wierszy i kolumn. Otrzymano 
tablicę. Jedno z minimalnych 
pokryć daje rozwiązanie:
f=x

2

x

5

+x

4

x

5

+x

1

’x

3

+x

1

x

3

’

Podany algorytm zapewnia 
minimalną postać funkcji, ale jest 
dość pracochłonny. Podany 
zostanie algorytm na znalezienie 
quasi-optymalnej wprost z 
tablicy.

00011

01100

10000

x

2

’x

4

V

x

4

x

5

V

x

1

’x

3

V

x

1

’x

2

x

4

’

V

x

1

x

3

’

V

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI SŁABO OKREŚLONYCH

a) Wpisując dla każdej kolumny minimalne zbiory zmiennych, 
których podzbiory występują w każdym wierszu. W ten sposób 
otrzymuje się minimalne proste implikanty pokrywające 
odpowiednią jedynkę, a nie pokrywające zer

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI SŁABO OKREŚLONYCH

00011

01100

01101

10000

11001

11101

00001

x

4

x

2

x

3

 x

5

’

x

2

x

3

x

1

x

5

’

x

1

x

2

x

1

x

2

x

3

01010

x

2

’x

5

x

3

x

4

’

x

3

x

4

’x

5

x

1

x

2

’x

4

’

x

1

x

4

’x

5

x

1

 x

3

x

4

’x

5

10101

x

1

’x

3

’x

4

x

1

’x

2

x

5

’

x

1

’x

2

x

3

’x

5

’

x

2

x

3

’

x

2

11100

x

1

’x

2

’x

3

’x

4

x

5

x

1

’

x

1

’x

5

x

2

’x

3

’

’x

3

x

5

x

5

x

4

x

5

, x

2

’x

4

x

1

’x

3

x

1

’x

3

,

 

x

2

x

5

x

1

x

3

’,

x

2

’x

5

’

x

2

x

5

,

x

1

x

3

’

x

2

x

5

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI SŁABO OKREŚLONYCH

b) Jeżeli w wypisanych zbiorach są zbiory o mniejszej ilości liter 
niż pozostałe, należy sprawdzić czy nie można ich zastąpić 
innymi zbiorami spośród wypisanych. W naszym przypadku 
wszystkie minimalne zbiory są dwuliterowe, więc nie 
realizujemy tego punktu

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA FUNKCJI SŁABO OKREŚLONYCH

c) Należy wypisać funkcję tak dobierając implikanty, aby było 
ich możliwie mało i aby występowały one we wszystkich 
kolumnach. U nas możliwych jest kilka rozwiązań np. 
Y=x

4

x

5

+x

1

’x

3

+x

1

x

3

’+x

2

x

5

Zamiast x

4

x

5

 można napisać x

2

’x

4

, a zamiast x

1

x

3

’ można 

napisać x

2

’x

5

’.

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA ZESPOŁU FUNKCJI 

PRZAŁĄCZAJĄCYCH

Przy minimalizacji zespołu funkcji przełączających, 
przedstawionych w postaci normalnej należy dążyć do 
minimalizacji sumarycznej liczby liter, przez wprowadzenie jak 
największej liczby wspólnych iloczynów (sum) elementarnych 
przy czym, jeżeli ten sam iloczyn (suma) wchodzi w skłąd kilku 
postaci normalnych, to tworzące go litery liczone są tylko raz. 
Postać normalna poszczególnych funkcji może więc zawierać 
nie tylko proste implikanty (implicenty) tych samych funkcji, 
ale i proste implikanty wszystkich iloczynów (sum) funkcji. Np. 
w celu zminimalizowania APN zespołu trzech funkcji y

1

, y

2

, y

3

 

należy znaleźć proste implikanty tych funkcji, jak również 
implikanty iloczynów y

1

y

2

, y

1

y

3

, y

2

y

3

 oraz y

1

y

2

y

3

. Można to 

zrobić posługując się tablicami Karnaugha, bądź też 
zmodyfikowana metodą Quine’a McCluskeya.

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA ZESPOŁU FUNKCJI ...

PRZYKŁAD

Zminimalizować zespół trzech funkcji czterech zmiennych:
y

1

=f

r

(x

1

, x

2

, x

3

, x

4

)=(2, 5, 6, 13, 14) 

y

2

=f

s

(x

1

, x

2

, x

3

, x

4

)=(5, 7, 13, 14)

y

3

=f

t

(x

1

, x

2

, x

3

, x

4

)=(2, 6, 7, 13, 15)

Liczby reprezentujące jedynki funkcji łączy się w grupy zgodnie 
z ich indeksami, przy czy, w nawiasie zaznacza się np. 
symbolami literowymi do jakich funkcji dany iloczyn należy

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA ZESPOŁU FUNKCJI ...

PRZYKŁAD

KOLUMNA 1

KOLUMNA 2

2 (r,t)  V

5 (r,s)  V

6 (r,t)  V

7 (s,t) 



13 (r,s,t) 



14 (r,s)  



15 (t)  V

2,6 (4,r,t) 



5,7 (2,s) 



5,13 (8,r,s) 



6,7 (1,t) 



6,14 (8,r) 



7,15 (8,t) 



13,15 (2,t) 



TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA ZESPOŁU FUNKCJI ...

PRZYKŁAD

Procedura łączenia opiera się na tych samych zasadach jak przy 
minimalizacji jednej funkcji z dodatkowymi regułami:

– można łączyć tylko te wyrażenia, które mają choć jeden wspólny 

symbol funkcji

– przy powstałym w wyniku połączenia wyrażeniu wpisujemy tylko 

te wspolne symbole funkcji, np. z połączenia 5(r,s) z 7(s,t) 
otrzymujemy 5,7(2,s)

– znak V stawiamy tylko w przypadku jeżeli łączymy dwa wyrażenia 

o takich samych symbolach literowych (wtedy znak V stawiamy 
przy obu łączonych wyrażeniach, np. Przy łączeniu 2(r,t) z 6(r,t) 
lub gdy łączymy wyrażenia, z których jedno ma symbole literowe 
będące podzbiorem drugiego (wtedy znak stawiamy tylko przy 
pierwszym, np. 5(r,s) z 13(r,s,t)

Prostymi implikantami będą oczywiście wszystkie te wyrażenia, 
które nie oznaczono znakiem V. Buduje się następnie tablicę 
Quine;a i szuka się minimalnego pokrycia według znanych reguł.

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA ZESPOŁU FUNKCJI ...

PRZYKŁAD

Y

1

=f

r

Y

2

=f

s

Y

3

=f

t

2

5

6

13 14

5

7

13 14

2

6

7

13 15

2,6 (4,r,t)

V

V

V

V

5,13 (8,r,s)

V

V

V

V

13(r,s,t)

V

V

V

5,6(3,s)

V

V

6,14(8,r)

V

V

6,7(1,t)

V

V

7(s,t)

V

V

14(r,s)

V

V

7,15(8,t)

V

V

13,15(2,t)

V

V

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA ZESPOŁU FUNKCJI ...

PRZYKŁAD

Analiza tablicy prowadzi do wniosku, że do pokrycia wszystkich 
jedynek funkcji prócz zasadniczych prostych implikantów 
2,6(4,r,t); 5,13(8,r,s) i 14(r,s) potrzebne są implikanty 7(s,t); 
13,15(2,t) a więc:
y

1

= x

1

’x

3

x

4

’+ x

2

x

3

’x

4

+ x

1

x

2

x

3

x

4

’

y

2

= x

2

x

3

’x

4

+ x

1

’x

2

x

3

x

4

+ x

1

x

2

x

3

x

4

’

y

3

=x

1

’x

3

x

4

+ x

1

’x

2

x

3

x

4

+ x

1

x

2

x

4

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA ZESPOŁU FUNKCJI ...

PRZYKŁAD

Przy niewielkiej liczbie zmiennych, dla zespołów zawierających 
2 lub 3 funkcje wyznaczenia prostych implikantów zespołu 
prościej dokonywać jest na tablicach Karnaugha.Tablice 
Karnaugha dla rozpatrywanych poprzednio funkcji  oraz ich 
iloczynów przedstawiono na następnym slajdzie.

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA ZESPOŁU FUNKCJI ...

PRZYKŁAD

x

3

x

4

 x

1

x

2

00 01 11 10

00

0 0 0 1

01

0 1 0 1

11

0 1 0 1

10

0 0 0 0

x

3

x

4

 x

1

x

2

00 01 11 10

00

0 0 0 0

01

0 1 1 0

11

0 1 0 1

10

0 0 0 0

x

3

x

4

 x

1

x

2

00 01 11 10

00

0 0 0 1

01

0 1 1 1

11

0 1 0 0

10

0 0 0 0

0 0 0 0

0 1 0 0
0 1 0 1
0 0 0 0

0 0 0 1

0 0 0 1
0 1 0 0
0 0 0 0

0 0 0 0

0 0 1 0
0 1 0 0
0 0 0 0

0 0 0 0

0 0 0 0
0 1 0 0
0 0 0 0

y

1

y

2

y

1

y

3

y

2

y

3

y

1

y

2

y

3

y

1

y

2

y

3

TECHNIKA CYFROWA I MIKROKOMPUTERY

MINIMALIZACJA ZESPOŁU FUNKCJI ...

PRZYKŁAD

Iloczyn dwu funkcji zawiera odpowiedniki dziesiętne pełnych 
ilozynów, wspólne dla obu funkcji. Otrzymane proste implikant 
funkcji y

1

, y

2

, y

3

, y

1

y

2

, y

1

y

3

, y

2

y

3

, y

1

y

2

y

3

 wpisuje się do tablicy 

Quine’a. Dalsze postępowanie jest identyczne jak w metodzie 
Quine’a-McCluskeya. 

TECHNIKA CYFROWA I MIKROKOMPUTERY

FAKTORYZACJA

Dalsze, w stosunku do postaci normalnej, zmniejszenie liczby 
liter w wyrażeniu opisującym daną funkcję osiągnąć można 
przez tzw. faktoryzację. Polega ona w najprostszym przypadku 
na wyciągnięciu przed nawias wspólnego czynnika (w 
przypadku normalnej postaci sumy) lub na częściowym 
wymnożeniu (w przypadku normalnej postaci iloczynu) zgodnie 
ze wzorami:
AB+AC=A(B+C)
(A+B)(A+C)=A+BC

y=(x

1

+x

2

)(x

1

+x

3

)(x

3

+x

4

)(x

2

’+x

4

)=(x

1

+x

2

x

3

)(x

4

+x

2

’x

3

)