Mapa Karnaugha — przewodnik po upraszczaniu K-map

Mapa Karnaugha, czyli K-map, to siatka używana do upraszczania wyrażenia boolowskiego bez wykonywania tak dużej liczby przekształceń algebraicznych ręcznie. Umieszcza się na niej wartości wyjściowe z tabeli prawdy, grupuje sąsiednie $1$ i zapisuje jeden prostszy składnik dla każdej grupy.

Warunek ma znaczenie: mapy Karnaugha są najbardziej praktyczne dla małych funkcji, zwykle z dwiema, trzema lub czterema zmiennymi. Gdy liczba zmiennych rośnie, mapa staje się trudniejsza do odczytania i zwykle lepiej sprawdzają się inne metody.

Co pokazuje mapa Karnaugha

K-map zawiera te same informacje co tabela prawdy, ale układa komórki w kolejności kodu Graya zamiast zwykłego porządku binarnego. Dzięki temu sąsiednie komórki różnią się dokładnie jedną zmienną.

Ta różnica jednej zmiennej jest kluczowa. Jeśli dwie sąsiednie komórki mają wartość $1$, zmienna, która się zmienia, może zniknąć z uproszczonego składnika.

Jak grupowanie usuwa zmienne

Ta wizualna reguła wynika z tożsamości algebry Boole’a, takich jak

$$XY + X\overline{Y} = X$$

Te dwa składniki różnią się tylko w $Y$, więc $Y$ się redukuje, a wspólna część $X$ pozostaje. K-map pozwala dostrzec ten wzorzec redukcji bezpośrednio na siatce.

Przykład mapy Karnaugha

Załóżmy, że

$$F(A,B,C) = \sum m(1,3,4,5,7)$$

To oznacza, że $F=1$ dla mintermów $1$, $3$, $4$, $5$ i $7$.

Dla K-map z $3$ zmiennymi użyj $A$ dla wierszy oraz $BC$ dla kolumn w kolejności kodu Graya $00$, $01$, $11$, $10$:

$$\begin{array}{c|cccc} A \backslash BC & 00 & 01 & 11 & 10 \\ \hline 0 & 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 0 \end{array}$$

Zacznij od największej poprawnej grupy. Cztery $1$ w dwóch środkowych kolumnach tworzą jedną grupę. W tych czterech komórkach $C=1$ pozostaje stałe, podczas gdy $A$ i $B$ się zmieniają, więc ta grupa upraszcza się do

$$C$$

Jedna $1$ nadal nie jest pokryta: minterm $4$, czyli $(A,B,C)=(1,0,0)$. Połącz go w parę z sąsiednim mintermem $5$, czyli $(1,0,1)$.

W tej parze $A=1$ i $B=0$ pozostają stałe, podczas gdy $C$ się zmienia, więc para upraszcza się do

$$A\overline{B}$$

Zatem uproszczone wyrażenie ma postać

$$F(A,B,C) = C + A\overline{B}$$

To krótsze wyrażenie jest równoważne oryginalnej liście mintermów.

Zasady poprawnych grup w K-map

Używaj grup o rozmiarach będących potęgami dwójki: $1$, $2$, $4$, $8$ i tak dalej.

Twórz największe poprawne grupy, jakie się da. Większe grupy zwykle eliminują więcej zmiennych.

Pamiętaj, że mapa „zawija się” na krawędziach. Lewa i prawa krawędź są sąsiednie, podobnie jak górna i dolna.

Komórki po przekątnej nie są sąsiednie.

Nakładanie się grup jest dozwolone, jeśli pomaga utworzyć większe lub prostsze grupowanie.

Typowe błędy w mapach Karnaugha

Używanie zwykłego porządku binarnego

Jeśli oznaczysz wiersze lub kolumny jako $00$, $01$, $10$, $11$, sąsiedztwo będzie błędne. K-map musi używać kolejności kodu Graya, aby sąsiednie komórki różniły się tylko jednym bitem.

Tworzenie grup po trzy

Grupa z trzech komórek nigdy nie jest poprawna. Jej rozmiar musi być potęgą dwójki.

Pomijanie sąsiedztwa przez zawijanie krawędzi

Niektóre z najlepszych uproszczeń wykorzystują komórki leżące na przeciwnych krawędziach mapy. Jeśli zapomnisz o zasadzie zawijania, twoja odpowiedź często będzie dłuższa, niż powinna.

Wymuszanie, by każda $1$ należała dokładnie do jednej grupy

To nie jest żadna reguła. Ponowne użycie komórki może być najlepszym sposobem na utworzenie większej grupy i uzyskanie krótszego wyrażenia końcowego.

Kiedy używa się mapy Karnaugha

Mapy Karnaugha są powszechne w logice cyfrowej i na wstępnych kursach inżynierii komputerowej, ponieważ zamieniają upraszczanie wyrażeń boolowskich w proces wizualny. Są szczególnie przydatne wtedy, gdy chcesz uzyskać prostsze wyrażenie w postaci sumy iloczynów przed narysowaniem lub implementacją układu logicznego.

Są też dobre do budowania intuicji. Nawet jeśli większe projekty obsługuje oprogramowanie, nauka K-map ułatwia zrozumienie, dlaczego pewne składniki boolowskie można łączyć, a innych nie.

Spróbuj podobnego zadania

Spróbuj samodzielnie uprościć $F(A,B,C)=\sum m(0,2,4,6,7)$. Narysuj mapę, najpierw utwórz największe poprawne grupy, a potem zostaw tylko te zmienne, które pozostają stałe w każdej grupie.

Jeśli chcesz pójść o krok dalej, spróbuj wersji z wartościami don't-care i używaj ich tylko wtedy, gdy pomagają utworzyć większą poprawną grupę.