Metoda Karnaugha

Metoda Karnaugha (wym. spolszczona ), metoda Karnaugh (wym. ang. ) – sposób minimalizacji funkcji boolowskich. Został wynaleziony w 1950 roku przez Maurice'a Karnaugh. W ogólnym przypadku znalezienie formuły minimalnej dla zadanej funkcji boolowskiej jest bardzo skomplikowanym problemem. Jednak jeśli funkcja ma małą liczbę zmiennych (do sześciu) i zostanie zapisana w specjalnej tablicy zwanej mapą lub siatką Karnaugha, wówczas znalezienie minimalnej formuły odbywa się na drodze intuicyjnej. W celu minimalizacji funkcji o większej liczbie wejść stosuje się metody komputerowe, na przykład metodę Quine’a-McCluskeya.

Indeksy kratek 
W siatce Karnaugha część zmiennych binarnych przypisana jest wierszom, a część kolumnom. Indeksy i kolumny numerowane są przy pomocy kodu Graya. Wektorem odpowiadającym danej kratce jest wektor powstały po „sklejeniu” binarnego numeru wiersza z binarnym numerem kolumny.

Dzięki zastosowaniu kodu Graya możliwe jest znalezienie w wizualny sposób pól sąsiednich logicznie, czyli różniących się wartością dokładnie jednej zmiennej. Przy większej liczbie zmiennych staje się to jednak trudniejsze.

Minimalizacja funkcji logicznych 

W celu minimalizacji funkcji logicznych należy wypełnić mapę Karnaugha wartościami (1 lub 0) odpowiadającymi wartościom funkcji dla wartości argumentów opisujących dane pole w tablicy. Następnie grupuje się pola o wybranej wartości (1 aby uzyskać funkcję minimalną w postaci sumy, 0 dla postaci iloczynu). Grupy muszą mieć kształt prostokąta o długościach boków będących potęgami dwójki (przy czym może on przechodzić przez krawędź tablicy, a dla liczby zmiennych powyżej 4 nie musi być spójny, a jedynie łączyć pola sąsiednie logicznie). W celu uzyskania postaci minimalnej, grupy powinny być możliwie największe. Jedno pole może należeć do wielu grup.

W każdej uzyskanej grupie część wartości zmiennych będzie wspólna dla wszystkich pól i to z nich powstaje wyrażenie odpowiadające danej grupie. Jeżeli pogrupowane zostały jedynki, wyrażenie dla pojedynczej grupy będzie miało postać iloczynu zmiennych, które, jeżeli w danej grupie przyjmują wartość 1, będą występowały w postaci prostej, jeżeli 0 – w postaci zanegowanej (zmienne przyjmujące w danej grupie różne wartości są pomijane); funkcja końcowa będzie sumą tych iloczynów. Jeżeli utworzono grupy zer, wyrażenie dla danej grupy będzie sumą zmiennych w postaci zanegowanej, jeżeli w danej grupie mają wartość 1, prostej, jeśli 0; wynik będzie iloczynem takich sum. Tak więc im grupa jest większa, od tym mniejszej liczby zmiennych zależy.

Sklejanie „na skos” 
Gdy istnieją grupy jednoelementowe, które stykają się ze sobą rogami (nie mogą zostać sklejone w konwencjonalny sposób), jest możliwość zminimalizowania funkcji za pomocą funktorów XOR i XNOR.

Stany nieokreślone 
Jeżeli dana funkcja logiczna dla danej kombinacji wartości argumentów nie jest określona (tzn. wartość, jaką przyjmie dla niej funkcja, nie jest istotna), odpowiednie pole może (ale nie musi) zostać wcielone do którejś z grup w celu jej powiększenia.

Zobacz też 
 algorytm ekspansji
 implikant funkcji boolowskiej
 metoda Espresso

Przypisy

Bibliografia 
 

Funkcje boolowskie