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.