Wykład 3

Układy elektroniczne

1

Minimalizacja funkcji 
boolowskich

Minimalizacja funkcji boolowskich  - polega na 

znalezieniu dla danej funkcji formuły minimalnej, 
która jest jak najmniej skomplikowana. Przy 
porównywaniu stopnia skomplikowania reguł 
wprowadza się pojęcie współczynnika 
skomplikowania.

Dla funkcji boolowskiej zapisanej przy pomocy 

kanonicznej postaci sumy, współczynnik 
skomplikowania jest równy sumie liczby mnożeń i 
sumie liczby dodawań.

W syntezie logicznej, minimalizację funkcji 

boolowskich stosuje się w celu zredukowania 
liczby potrzebnych zasobów (bramek logicznych, 
bloków bramek) do realizacji danej funkcji. 

2

Metody minimalizacji funkcji 
boolowskich

Tradycyjne:

1.

 metoda Karnaugh, 

2.

metoda Quine'a-McCluskeya, 

3.

metoda iteracyjnego konsensusu

4.

metoda Espresso (oparta na algorytmie 
ekspansji) 

Do syntezy logicznej:

1.

dekompozycja funkcji boolowskich

2.

redukcja argumentów

3

Algorytm metody Karnaugh

1.

Zapis funkcji w formie tabeli Karnaugh, używając 
kodu Greya.

2.

Zaznaczenie (możliwie największych) skupisk 
jedynek i wartości nieustalonych 

(zakładając realizację 

przy użyciu bramek NAND). 

Skupiska mogą się pokrywać. 

3.

Wybór możliwie najmniejszej liczby skupisk 
takich, by wszystkie jedynki były tam zawarte.

4.

Zapis funkcji zminimalizowanej w postaci 
kanonicznego iloczynu..

4

Realizacja postaci 
kanonicznych

5

?

?

Kanoniczna postać sumy 
(suma iloczynów)

Kanoniczna postać iloczynu
(iloczyn sum)

Metoda Quine’a-
McCluskeya

6

Metoda Quine’a-
McCluskeya

 Cechy:



Dużo łatwiejsza do zaimplementowania jako algorytm 
komputerowy od metody Karnaugha



znajduje minimalną postać dysjunkcyjną (sumę 
iloczynów)



Użyteczna w minimalizacji manualnej do około 6 
zmiennych wejściowych, jednak bardziej pracochłonna 
(dla prostych funkcji) od metody Karnaugh

7

Algorytm metody Quine’a-McCluskeya

1.

Wypisujemy w jednej kolumnie wektory wejściowe odpowiadające jedynkom 
oraz wartościom nieustalonym.

2.

Grupujemy te wektory rosnąco według ilości jedynek w wektorze.

3.

Porównujemy wektory o o k-tej liczbie jedynek z wektorami o k+1 liczbie 
jedynek i łączymy te które różnią się tylko jednym bitem (np. 0100 oraz 0101), 
i zapisujemy wynikowe wektory (postaci np. 010*). Plusem oznaczamy 
„połączone” wektory.

4.

Analogicznie tworzymy następne tabele dopóki występują możliwości łączenia.

5.

Wypisujemy nieoznaczone plusem implikanty jako wiersze tabeli, kolumny 
tabeli to wartości dziesiętne „jedynek”. Na przecięciach w tabeli oznaczmy 
„kółkami” związek między implikantem i wektorem wejściowym – „kółkiem 
pełnym” dla implikantów bez wartości nieustalonych, a „kółkiem pustym” dla 
implikantów zawierających w sobie wartości nieustalone.

6.

Znajdujemy kolumny z jednym „kołem pełnym” i oznaczamy cały wiersz 
odpowiedniego implikantu. Jeżeli są nieoznaczone kolumny to powtarzamy dla 
kolumn z dwoma (itd.) „kołami pełnymi”. Gdy skończą się kółka pełne 
analogicznie postępujemy z „kółkami pustymi”.

<przykład>

8

Metoda iteracyjnego 
konsensusu

9

Metoda iteracyjnego 
konsensusu

Metoda to rozpoczyna się od implikantów funkcji (mogą to 

być dowolne implikanty, w szczególności iloczyny zupełne).

Metoda iteracyjnego konsensusu to iteracyjne wykonanie 

następujących kroków:

1.

Usuń z postaci dysjunkcyjnej wszystkie pokryte implikanty

2.

Wygeneruj wszystkie (niepuste i różne od 0) konsensusy z 
par iloczynów. Dodaj je do postaci dysjunkcyjnej. Przejdź 
do kroku 1.

Algorytm kończy się w momencie, gdy nie możemy 

wygenerować nowych konsensusów, ponieważ uzyskane 
iloczyny to implikanty proste.

10