Minimalizacja funkcji logicznych polega na upraszczaniu wyrażeń logicznych, tak aby zawierały jak najmniejszą liczbę tylko niezbędnych argumentów oraz operacji logicznych. Zadanie to ma podstawowe znaczenie dla techniki cyfrowej, gdzie funkcje urządzenia realizowane są za pomocą tzw. bramek logicznych (układów wykonujących podstawowe operacje logiczne). Jest chyba jasne, iż prostsze wyrażenie oznacza mniejszą złożoność układu elektronicznego, a co za tym idzie mniejszy koszt wykonania (szczególnie w dużych seriach i nie na potrzeby wojska), większą niezawodność (mniej elementów, które mogą przestać działać) oraz zwykle szybsze działanie (mniej uzależnień powoduje szybszą stabilizację sieci logicznej).

Zadanie minimalizacji można wykonać na kilka sposobów. Jednym z nich jest zastosowanie Algebry Boole'a do wykonania odpowiednich przekształceń i redukcji.

Zadanie jest następujące: zaprojektować minimalną funkcję logiczną zadaną poniższą tabelką stanów:

Funkcja przyjmuje wartość 1 dla a, b, c = 010, 011, 100 i 101. Tworzymy odpowiednie wyrażenie logiczne wykorzystując alternatywę, koniunkcję i negację:

f ( a, b, c ) = ( ¬ a ∧ b ∧ ¬ c ) ∨ ( ¬ a ∧ b ∧ c  ) ∨ ( a ∧ ¬ b ∧ ¬ c  ) ∨ ( a ∧ ¬ b ∧ c  )

Upraszczamy wyrażenie wykorzystując rozdzielność:

f ( a, b, c ) =  ¬ a ∧ ( b ∧ ¬ c ∨ b ∧ c  ) ∨a ∧ ( ¬ b ∧ ¬ c  ∨ ¬ b ∧ c  ) f ( a, b, c ) =  ¬ a ∧ ( b ∧ ( ¬ c ∨ c  )) ∨a ∧ ( ¬ b ∧ ( ¬ c  ∨ c  ))

wykorzystując:

¬ c  ∨ c = 1  b ∧ 1 = b ¬ b ∧ 1 = ¬ b

otrzymujemy:

f ( a, b, c ) =  ¬ a ∧ ( b ∧ 1 ) ∨a ∧ ( ¬ b ∧ 1) f ( a, b, c ) = ( ¬ a ∧ b ) ∨( a ∧ ¬ b )

Dzięki przekształceniom udało nam się sprowadzić początkowe wyrażenie:

f ( a, b, c ) = ( ¬ a ∧ b ∧ ¬ c ) ∨ ( ¬ a ∧ b ∧ c  ) ∨ ( a ∧ ¬ b ∧ ¬ c  ) ∨ ( a ∧ ¬ b ∧ c  )

do wyrażenia:

f ( a, b, c ) = ( ¬ a ∧ b ) ∨( a ∧ ¬ b ) f ( a, b, c ) = a ⊕ b

Wyrażenie końcowe jest dużo prostsze i nie zawiera argumentu c (mówimy, iż wartość funkcji nie zależy od tego argumentu). Dokonaliśmy minimalizacji funkcji. Taki sposób postępowania jest oczywiście poprawny, jednakże wymaga przeprowadzania uciążliwych transformacji logicznych. Na szczęście istnieje prostszy sposób zwany metodą map Karnaugha.

Mapy Karnaugha zostały wynalezione w roku 1953 przez Maurice'a Karnaugha, który był inżynierem telekomunikacyjnym w Bell Labs. Można je stosować do rozwiązywania problemów logicznych zawierających do 6 zmiennych. Pokażemy konstrukcję krok po kroku mapy Karnaugha oraz sposoby jej wykorzystania do minimalizacji funkcji logicznych.

Na początek rozważymy problem złożony z dwóch zmiennych. Funkcję logiczną f ( a, b ) zadajemy najczęściej tabelką wartości (tabelka ta wynika z potrzeb użycia danej funkcji - stąd określamy wymagane wartości funkcji dla poszczególnych argumentów).

Argumenty funkcji dzielimy na dwie grupy - będą służyły jako współrzędne elementów mapy Karnaugha. Ponieważ są tylko dwa argumenty a i b, to w jednej grupie będzie argument a, a w drugiej będzie argument b :

Współrzędne wyznaczają prostokątne obszary (zaznaczone na żółto). W obszarach tych umieszczamy wartości minimalizowanej funkcji. Otrzymujemy poniższą mapę Karnaugha:

Teraz na mapie Karnaugha grupujemy razem ze sobą obszary zawierające wartość funkcji równą 1. Grupowany obszar musi mieć rozmiary (ilość objętych kolumn i wierszy mapy) będące potęgami liczby dwa, zatem powinien obejmować 1, 2, 4 itd. kolumny lub wiersze. Zawsze staramy się zaznaczyć obszary maksymalne. W naszym przypadku na mapie można zaznaczyć dwa obszary A i B :

W obszarze A argument b zmienia się z 0 na 1. Skoro tak, to nie ma on wpływu na wartość funkcji f ( a, b ) w tym obszarze. Zatem dla obszaru A mamy:

Argument a musi być zanegowany, ponieważ obszar A leży w części mapy, dla której współrzędna a = 0.

W obszarze B jest odwrotnie - zmienia się argument a z 0 na 1. Zatem argument a nie ma wpływu na wartość funkcji w B. Wpływ ma jedynie argument b.

Ponieważ obszary A i B pokrywają wszystkie wartości 1, zatem:

---

Teraz bardziej skomplikowany przykład (z początku artykułu). Funkcja trójargumentowa zadana tabelką:

Rozdzielamy argumenty na dwie grupy: ab oraz c (można również rozdzielić na a i bc – zmieni się tylko orientacja mapy z pionowej na poziomą). Współrzędne na mapie Karnaugha są zawsze zapisywane w kodzie Graya.

W pola mapy wstawiamy wartości funkcji zgodnie z tabelką i otrzymujemy mapę Karnaugha:

Na mapie zaznaczamy obszary o wartości funkcji równej 1. Tutaj są tylko dwa takie obszary A i B :

Dla każdego obszaru uwzględniamy tylko te współrzędne, które w obszarze się nie zmieniają - w obu przypadkach rugujemy c, ponieważ zmienia się z 0 na 1.

i ostatecznie:

Doszliśmy do identycznych rezultatów jak na początku rozdziału. Tylko tutaj nie musieliśmy wykonywać żadnych przekształceń logicznych. To wielka zaleta map Karnaugha - funkcję otrzymujemy już w postaci zminimalizowanej.

---

Mamy funkcję czteroargumentową f ( a, b, c, d ) zadaną gotową mapą Karnaugha. Dokonać minimalizacji tej funkcji:

Cztery narożne obszary można połączyć w jeden obszar poprzez naprzeciwległe krawędzie - mapa Karnaugha łączy się na krawędziach - warto o tym fakcie pamiętać.

Obszar A jest zależny tylko od parametrów b i d, ponieważ nie zmieniają one swoich wartości w tym obszarze. Obszar B jest również zależny od tych samych parametrów:

Z map Karnaugha będziemy intensywnie korzystać przy projektowaniu sieci logicznych.