F1-36

© J. Kalisz, WAT, 2008

Metody minimalizacji

•

Odręczne przekształcanie

fb

. Np.

Stosuje się tylko do prostych wyrażeń boolowskich – należy
dostrzec możliwość redukcji.

l

l

Y

ABC

ABC

AB(C

C)

AB

AB

1

=

+

=

+

=

⋅ =

•

Metoda siatek Karnaugh

Stosuje się do funkcji o małej liczbie zmiennych

(3, 4 – teoretycznie 5, 6).

•

Metoda algorytmiczna Quine’a – McCluskeya.

Systematyczne porównywanie mintermów różniących się
stanem jednej zmiennej, w celu jej wyeliminowania.

Stosuje się w komputerowych programach minimalizacji dla
funkcji do 10 – 12 zmiennych.

Wada:

forma minimalizowana musi być przedstawiona w

postaci sumy mintermów (kanoniczna forma sumacyjna) –

metoda „oparta na mintermach”

.

Przy minimalizacji form o

n

zmiennych term dwuliterowy

musiałby być przekształcony do sumy 2

n

- 2

mintermów.

Np.

n

= 20 ► 2

18

mintermów.

•

Metoda algorytmiczna

Espresso

– heurystyczna,

„oparta na kostkach”

przetwarzanych bezpośrednio.

Dostępne są

bezpłatne programy uniwersyteckie.