F1-37

© J. Kalisz, J. Pasierbiński, WAT, 2007

Metody minimalizacji

•

„Ręczne” przekształcanie wyrażeń

z zastosowaniem praw

algebry Boole’a:

Stosuje się tylko do prostych wyrażeń boolowskich – należy

dostrzec możliwość redukcji.

•

„Ręczna” metoda graficzna 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”

.

Na przykład, 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.

1

Y

ABC

ABC

AB(C

C)

AB

AB

=

+

=

+

=

⋅ =