Metoda Karnaugh

Metoda Karnaugh (czyt. karno) – sposób minimalizacji funkcji boolowskich. Został odkryty w 1950 roku przez Maurice Karnaugha. 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 tablicą Karnaugh, wówczas znalezienie minimalnej formuły odbywa się na drodze intuicyjnej. W celu minimalizacji funkcji o większej liczbie wejść stosuje się z powodzeniem metody komputerowe, np. metodę Quine'a-McCluskeya.

Tablica Karnaugha

Indeksy kratek
Tablicę Karnaugha zaczynamy tworzyć przypisując część zmiennych binarnych wierszom, a część kolumnom. To, jak zostanie to zrobione, rzutuje potem na sposób indeksowania kratek. Dlatego, aby uniknąć pomyłek, pierwszą połowę zmiennych przypisuje się wierszom, a drugą - kolumnom. Aby łatwo korzystać z metody Karnaugha liczba zmiennych binarnych przypisanych wierszom i liczba zmiennych binarnych przypisana kolumnom powinna różnić się maksymalnie o 1.

Indeksy kratek tablicy Karnaugha tworzone są w następujący sposób:

1. Wiersze i kolumny numerujemy przy pomocy binarnego kodu Graya.

2. Wektorem odpowiadającym danej kratce jest wektor powstały po 'sklejeniu' binarnego numeru wiersza z binarnym numerem kolumny

Wartości w kratkach
Każda kratka tablicy odpowiada jednemu, konkretnemu wektorowi zmiennych binarnych. W kratkach zapisywane są wartości funkcji dla odpowiadających im wektorów. Przykład tablicy Karnaugh podany zostanie w następnym akapicie.

Metoda ta występuje w dwóch wersjach: dla postaci sumacyjnej oraz dla postaci iloczynowej. Poniżej omówiona jest metoda dla postaci sumacyjnej.

Postępujemy według następujących punktów:

1. Funkcję należy przedstawić w postaci kanonicznej lub tabelarycznej.

2. Tworzymy tabelę dla odpowiedniej ilości zmiennych

2 zmienne	3 zmienne	4 zmienne
	lub
5 zmiennych
lub

1. Wartości umieszczone z lewej strony i u góry oznaczają wartości podanych zmiennych

2. W kratki tabeli wpisujemy wartości funkcji ("0", "1" lub "-") zgodnie z postacią funkcji. Przykład: tabela Karnaugha

3. Dla funkcji F(abcd)=Σ{1,4,5,6,15,(7,9,10,14)}

4. 

5. Zakreślamy pola (grupy) w siatce tabeli zgodnie z następujacymi zasadami:

   • Pole jest kwadratem lub prostokątem o bokach będących potęgą 2, tzn. 1, 2, 4, 8,..

   • Pola obejmują kratki sąsiednie, kratki skrajne (pola mogą być "zawinięte" przez brzeg tablicy), oraz w tabeli dla 5 zmiennych symetryczne względem podwójnej linii.

   • Grupy muszą objąć wszystkie "1".

   • Grupy nie mogą obejmować "0".

   • Stany nieokreślone "-" mogą, ale nie muszą być zakreślane.

   • Grupy powinny być jak największe.

   • Ilość grup powinna być możliwie mała.

   • Grupy mogą na siebie zachodzić.

Przykład: zakreślanie pól w tablicy Karnaugha

Dla funkcji F(abcd)=Σ{1,4,5,6,15,(7,9,10,14)}

1. Odczytu funkcji wykonujemy według zasad:

   • Funkcja ma postać normalną sumy, tzn. suma implikantów prostych. W niektórych zastosowaniach wygodniej jest wypisać implikanty proste w postaci dwójkowej, np: 

abd- = (01-1)

• Jednemu polu odpowiada jeden implikant.

• Jeżeli zmienna przyjmuje dla danego pola wartość 1 to piszemy ją wprost.

• Jeżeli zmienna przyjmuje dla danego pola wartość 0 to piszemy ją z negacją.

• Jeżeli zmienna przyjmuje dla danego pola wartości 0 i 1 (zmienia wartość), to jej nie piszemy.

Przykład: odczytanie funkcji

Dla funkcji F(abcd)=Σ{1,4,5,6,15,(7,9,10,14)}

1. W razie potrzeby można dokonać dalszych przekształceń funkcji.

2. Schemat układu minimalnego (bez przekształceń). Przykład: schemat układu

Schemat układu realizującego funkcję:

F(abcd)=Σ{1,4,5,6,15,(7,9,10,14)}=

=ab+acd+bc-  --

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

Zestawienie zasadniczych twierdzeń algebry Boole’a