Tablica Karnaugh – praktyczny przewodnik po minimalizacji funkcji logicznych

Tablica Karnaugh – praktyczny przewodnik po minimalizacji funkcji logicznych

Tablica Karnaugh to jedno z najważniejszych narzędzi wykorzystywanych w algebrze Boole’a, technice cyfrowej, elektronice i projektowaniu układów logicznych. Pozwala w przejrzysty sposób upraszczać funkcje logiczne, ograniczać liczbę bramek logicznych oraz tworzyć bardziej czytelne, tańsze i efektywne układy cyfrowe. Choć na pierwszy rzut oka może wydawać się tylko tabelą z zerami i jedynkami, w rzeczywistości jest bardzo sprytną metodą graficznej minimalizacji wyrażeń logicznych.

Dobrze opanowana tablica Karnaugh pozwala szybko przechodzić od tabeli prawdy do uproszczonej postaci funkcji logicznej. To szczególnie ważne w nauce elektroniki cyfrowej, informatyki technicznej, automatyki, mechatroniki oraz wszędzie tam, gdzie pojawiają się układy kombinacyjne. Dzięki niej można łatwiej projektować dekodery, multipleksery, układy sterowania, proste sterowniki, automaty cyfrowe i obwody zbudowane z bramek AND, OR, NOT, NAND czy NOR.

Spis treści

Czym jest tablica Karnaugh?

Tablica Karnaugh, nazywana także mapą Karnaugh lub mapą K, to graficzna metoda upraszczania funkcji logicznych. Jej zadaniem jest takie rozmieszczenie wartości funkcji, aby łatwo można było zauważyć sąsiadujące kombinacje wejść prowadzące do tego samego wyniku. Dzięki temu możliwe jest skracanie wyrażeń logicznych poprzez eliminowanie zmiennych, które w danej grupie przyjmują zarówno wartość 0, jak i 1.

Najprościej mówiąc, tablica Karnaugh jest uporządkowaną wersją tabeli prawdy. Zamiast wypisywać wszystkie kombinacje wejść w zwykłej kolejności binarnej, wartości funkcji umieszcza się w specjalnej siatce. Układ tej siatki sprawia, że sąsiednie pola różnią się tylko jedną zmienną. To właśnie ta właściwość pozwala łączyć pola w grupy i upraszczać funkcje logiczne.

Przykładowo, jeżeli funkcja logiczna zależy od trzech zmiennych: A, B i C, to ma osiem możliwych kombinacji wejściowych. Można je zapisać w klasycznej tabeli prawdy, ale można też umieścić w tablicy Karnaugh o ośmiu polach. Następnie jedynki w tablicy grupuje się tak, aby otrzymać prostszy wzór funkcji.

W praktyce tablica Karnaugh jest szczególnie przydatna dla funkcji mających:

  • 2 zmienne,
  • 3 zmienne,
  • 4 zmienne,
  • czasem 5 lub 6 zmiennych, choć wtedy metoda staje się mniej wygodna.

Dla większej liczby zmiennych częściej stosuje się metody algorytmiczne i narzędzia komputerowe.

Do czego służy tablica Karnaugh?

Głównym celem, dla którego stosowana jest tablica Karnaugh, jest minimalizacja funkcji logicznej. Minimalizacja oznacza przekształcenie funkcji do prostszej postaci, która daje dokładnie taki sam wynik dla wszystkich kombinacji wejściowych, ale wymaga mniejszej liczby działań logicznych lub bramek.

Tablica Karnaugh służy między innymi do:

  • upraszczania wyrażeń logicznych,
  • projektowania układów kombinacyjnych,
  • redukowania liczby bramek logicznych,
  • przechodzenia od tabeli prawdy do schematu logicznego,
  • znajdowania minimalnej postaci funkcji Boole’a,
  • wykorzystywania warunków nieokreślonych,
  • przygotowywania funkcji do realizacji za pomocą bramek NAND lub NOR,
  • analizy prostych układów cyfrowych.

W nauce techniki cyfrowej tablica Karnaugh jest często jednym z pierwszych narzędzi, które pokazują, że funkcję logiczną można zapisać na wiele sposobów. Dwa różne wyrażenia mogą opisywać dokładnie tę samą funkcję, ale jedno z nich może być znacznie prostsze i wygodniejsze do realizacji.

Przykład znaczenia uproszczenia

Załóżmy, że funkcja logiczna została zapisana jako:

F = A\’BC + AB\’C + ABC + ABC\’

Taki zapis można zrealizować przy pomocy bramek logicznych, ale niekoniecznie jest on najprostszy. Po zastosowaniu tablicy Karnaugh może się okazać, że funkcję da się zapisać krócej, na przykład jako:

F = AC + AB

Oznacza to mniej bramek, mniej połączeń i prostszy układ.

Dlaczego minimalizacja funkcji logicznych jest ważna?

Minimalizacja funkcji logicznych nie jest wyłącznie ćwiczeniem akademickim. Ma bezpośrednie znaczenie praktyczne. W elektronice cyfrowej każde uproszczenie może oznaczać mniejsze zużycie elementów, niższy koszt, większą niezawodność i mniejsze opóźnienia propagacji sygnału.

Mniej bramek logicznych

Im prostsze wyrażenie logiczne, tym mniej bramek trzeba użyć do jego realizacji. Jeżeli funkcja wymaga mniejszej liczby bramek AND, OR i NOT, cały układ staje się bardziej przejrzysty i tańszy.

W układach scalonych redukcja liczby bramek oznacza także mniejszą powierzchnię struktury krzemowej. W projektach dyskretnych oznacza mniej układów scalonych, mniej połączeń i mniejsze prawdopodobieństwo błędu montażowego.

Mniejsze opóźnienia

Każda bramka logiczna wprowadza pewne opóźnienie. Jeśli sygnał musi przejść przez wiele poziomów bramek, wynik pojawi się później. Uproszczenie funkcji może zmniejszyć liczbę poziomów logicznych, a tym samym poprawić szybkość działania układu.

To ważne szczególnie w systemach synchronicznych, gdzie czas propagacji musi mieścić się w określonych granicach między impulsami zegarowymi.

Mniejsze zużycie energii

Mniejsza liczba bramek może oznaczać niższe zużycie energii. W nowoczesnych układach cyfrowych pobór mocy zależy między innymi od przełączania pojemności wewnętrznych. Im mniej elementów musi się przełączać, tym bardziej energooszczędny może być układ.

Większa czytelność projektu

Prostsze wyrażenie logiczne jest łatwiejsze do analizy, testowania i dokumentowania. Dobrze zminimalizowana funkcja ułatwia zrozumienie, co rzeczywiście robi układ. Jest to ważne zarówno w edukacji, jak i w praktycznym projektowaniu urządzeń.

Podstawy algebry Boole’a potrzebne do pracy z tablicą Karnaugh

Aby dobrze zrozumieć, jak działa tablica Karnaugh, trzeba znać podstawowe operacje algebry Boole’a. Nie trzeba od razu opanowywać całej teorii, ale warto rozumieć znaczenie negacji, iloczynu logicznego i sumy logicznej.

Zmienna logiczna

Zmienna logiczna może przyjmować jedną z dwóch wartości:

  • 0 – fałsz, stan niski, brak sygnału,
  • 1 – prawda, stan wysoki, obecność sygnału.

W elektronice cyfrowej wartości te odpowiadają zwykle dwóm zakresom napięć. W teorii logicznej traktuje się je jako abstrakcyjne wartości prawdy.

Negacja logiczna NOT

Negacja odwraca wartość zmiennej. Jeśli A = 1, to A\’ = 0. Jeśli A = 0, to A\’ = 1.

Negację zapisuje się na różne sposoby:

  • A\’,
  • ¬A,
  • \\overline{A},
  • NOT A.

W artykule najczęściej używany będzie zapis z apostrofem, na przykład A\’.

Iloczyn logiczny AND

Iloczyn logiczny ma wartość 1 tylko wtedy, gdy wszystkie składniki mają wartość 1.

Przykład:

A · B = 1 tylko wtedy, gdy A = 1 i B = 1.

W zapisie funkcji logicznych znak mnożenia często się pomija:

AB oznacza to samo co A · B.

Suma logiczna OR

Suma logiczna ma wartość 1 wtedy, gdy przynajmniej jeden składnik ma wartość 1.

Przykład:

A + B = 1, gdy A = 1 lub B = 1, lub obie zmienne są równe 1.

Prawa algebry Boole’a

Tablica Karnaugh wykorzystuje graficznie prawa algebry Boole’a. Jednym z najważniejszych jest zależność:

AB + AB\’ = A

Dlaczego? Ponieważ:

AB + AB\’ = A(B + B\’)

A ponieważ:

B + B\’ = 1

to:

A(B + B\’) = A · 1 = A

To właśnie ten mechanizm stoi za grupowaniem pól w tablicy Karnaugh. Jeśli dwie sąsiednie komórki różnią się tylko jedną zmienną, to ta zmienna może zostać usunięta z uproszczonego wyrażenia.

Jak wygląda tablica Karnaugh?

Tablica Karnaugh jest prostokątną lub kwadratową siatką pól. Każde pole odpowiada jednej kombinacji wartości zmiennych wejściowych. Liczba pól zależy od liczby zmiennych funkcji.

Dla funkcji o liczbie zmiennych n liczba pól wynosi:

2ⁿ

Oznacza to, że:

  • dla 2 zmiennych są 4 pola,
  • dla 3 zmiennych jest 8 pól,
  • dla 4 zmiennych jest 16 pól,
  • dla 5 zmiennych są 32 pola,
  • dla 6 zmiennych są 64 pola.

Najczęściej w praktyce edukacyjnej wykorzystuje się tablice dla 2, 3 i 4 zmiennych. Są one jeszcze na tyle czytelne, że można łatwo zauważać grupy jedynek lub zer.

Pola tablicy

Każde pole tablicy odpowiada jednemu mintermowi, czyli jednej konkretnej kombinacji zmiennych. Jeśli funkcja dla tej kombinacji ma wartość 1, w polu wpisuje się 1. Jeśli ma wartość 0, wpisuje się 0. Jeśli wartość może być dowolna, często wpisuje się X, oznaczające warunek nieokreślony.

Sąsiedztwo pól

Najważniejszą cechą tablicy Karnaugh jest to, że sąsiednie pola różnią się tylko jedną zmienną. Sąsiedztwo dotyczy pól położonych obok siebie poziomo lub pionowo. Co ważne, krawędzie tablicy również traktuje się jako sąsiadujące. Oznacza to, że lewa krawędź sąsiaduje z prawą, a górna z dolną.

Ta zasada bywa początkowo zaskakująca, ale jest kluczowa. Tablica Karnaugh jest jak powierzchnia zawinięta logicznie w taki sposób, że przeciwległe krawędzie stykają się ze sobą.

Kod Graya w tablicy Karnaugh

W klasycznej tabeli prawdy kombinacje binarne często zapisuje się w kolejności:

  • 00,
  • 01,
  • 10,

W tablicy Karnaugh używa się innego porządku, zwanego kodem Graya. Dla dwóch bitów typowa kolejność to:

  • 00,
  • 01,
  • 11,

Dlaczego nie jest to zwykła kolejność binarna? Ponieważ w kodzie Graya kolejne kombinacje różnią się tylko jednym bitem. Dzięki temu sąsiednie pola tablicy Karnaugh różnią się tylko jedną zmienną, a to umożliwia poprawne grupowanie.

Przykład różnicy

W zwykłej kolejności binarnej przejście z 01 do 10 zmienia dwa bity naraz. To nie jest dobre dla tablic Karnaugh, ponieważ sąsiednie pola muszą różnić się tylko jedną zmienną.

W kodzie Graya kolejność 00, 01, 11, 10 działa poprawnie:

  • 00 i 01 różnią się jednym bitem,
  • 01 i 11 różnią się jednym bitem,
  • 11 i 10 różnią się jednym bitem,
  • 10 i 00 również różnią się jednym bitem, jeśli uwzględnimy zawijanie krawędzi.

To właśnie dlatego w tablicach Karnaugh nagłówki wierszy i kolumn często mają pozornie nietypową kolejność.

Tablica Karnaugh dla dwóch zmiennych

Tablica Karnaugh dla dwóch zmiennych ma cztery pola. Jest najprostsza i dobrze pokazuje podstawową ideę metody.

Dla funkcji zależnej od zmiennych A i B można ją zapisać tak:

A \\ B010F(0,0)F(0,1)1F(1,0)F(1,1)

Każde pole odpowiada jednej kombinacji:

  • A = 0, B = 0,
  • A = 0, B = 1,
  • A = 1, B = 0,
  • A = 1, B = 1.

Przykład dla dwóch zmiennych

Załóżmy, że funkcja F ma wartość 1 dla kombinacji:

  • A = 0, B = 1,
  • A = 1, B = 1.

Tablica wygląda tak:

A \\ B01001101

Jedynek jest dwie i znajdują się w jednej kolumnie. W obu przypadkach zmienna B ma wartość 1, natomiast A zmienia się z 0 na 1. Skoro A zmienia się w obrębie grupy, można ją usunąć.

Uproszczona funkcja to:

F = B

To bardzo prosty przykład pokazujący, dlaczego grupowanie działa. Funkcja nie zależy od A, ponieważ dla B = 1 wynik zawsze jest równy 1.

Tablica Karnaugh dla trzech zmiennych

Tablica Karnaugh dla trzech zmiennych ma osiem pól. Najczęściej jedna zmienna opisuje wiersze, a dwie zmienne opisują kolumny w kodzie Graya.

Dla zmiennych A, B i C można przyjąć układ:

A \\ BC0001111001

Kolumny są opisane jako BC w kolejności:

  • 00,
  • 01,
  • 11,

Nie jest to przypadek. Kolejność ta zapewnia, że sąsiednie kolumny różnią się tylko jedną zmienną.

Przykład dla trzech zmiennych

Załóżmy, że funkcja F(A, B, C) ma wartość 1 dla mintermów:

m(1, 3, 5, 7)

W zapisie binarnym:

  • m1 = 001,
  • m3 = 011,
  • m5 = 101,
  • m7 = 111.

Widzimy, że we wszystkich przypadkach C = 1. Zmienne A i B mogą przyjmować różne wartości. Tablica Karnaugh wygląda tak:

A \\ BC000111100011010110

Można utworzyć grupę czterech jedynek w kolumnach 01 i 11, obejmującą oba wiersze. W tej grupie:

  • A zmienia się,
  • B zmienia się,
  • C pozostaje równe 1.

Uproszczona funkcja to:

F = C

To przykład bardzo dużego uproszczenia. Funkcja trzech zmiennych okazała się zależeć tylko od jednej zmiennej.

Zawijanie krawędzi w tablicy dla trzech zmiennych

Załóżmy teraz, że jedynki znajdują się w kolumnach 00 i 10. W zwykłym spojrzeniu na tabelę są one po przeciwnych stronach, ale w tablicy Karnaugh te kolumny są sąsiadami. Wynika to z kodu Graya i zasady zawijania.

Przykład:

A \\ BC000111100100111001

Kolumny 00 i 10 są sąsiadujące przez krawędź. Można więc utworzyć grupę czterech jedynek. W tej grupie:

  • A zmienia się,
  • C zmienia się,
  • B pozostaje równe 0.

Uproszczona funkcja:

F = B\’

To jeden z przykładów, który najlepiej pokazuje, że tablica Karnaugh nie jest zwykłą tabelą, lecz mapą logicznego sąsiedztwa.

Tablica Karnaugh dla czterech zmiennych

Tablica Karnaugh dla czterech zmiennych ma szesnaście pól. Najczęściej dwie zmienne opisują wiersze, a dwie zmienne opisują kolumny. Zarówno wiersze, jak i kolumny są zapisane w kodzie Graya.

Dla zmiennych A, B, C i D typowy układ wygląda tak:

AB \\ CD0001111000011110

Kolejność wierszy to:

  • 00,
  • 01,
  • 11,

Kolejność kolumn jest taka sama. Dzięki temu każde sąsiednie pole różni się dokładnie jedną zmienną.

Przykład tablicy Karnaugh dla czterech zmiennych

Załóżmy, że funkcja F(A, B, C, D) ma wartość 1 dla mintermów:

m(0, 1, 4, 5, 8, 9, 12, 13)

W zapisie binarnym są to:

  • 0000,
  • 0001,
  • 0100,
  • 0101,
  • 1000,
  • 1001,
  • 1100,

W każdej z tych kombinacji zmienna C = 0, natomiast A, B i D zmieniają się. Tablica Karnaugh:

AB \\ CD00011110001100011100111100101100

Można utworzyć grupę ośmiu jedynek obejmującą dwie kolumny: CD = 00 i CD = 01. W tej grupie:

  • A zmienia się,
  • B zmienia się,
  • D zmienia się,
  • C pozostaje równe 0.

Uproszczona funkcja:

F = C\’

Przykład z kilkoma grupami

Nie każda funkcja redukuje się do jednej zmiennej. Często trzeba utworzyć kilka grup.

Załóżmy, że tablica ma postać:

AB \\ CD00011110001100011100110011100011

Możemy utworzyć dwie grupy po cztery jedynki.

Pierwsza grupa:

AB \\ CD000100110111

W tej grupie:

  • A = 0,
  • C = 0,
  • B i D zmieniają się.

Składnik:

A\’C\’

Druga grupa:

AB \\ CD111011111011

W tej grupie:

  • A = 1,
  • C = 1,
  • B i D zmieniają się.

Składnik:

AC

Uproszczona funkcja:

F = A\’C\’ + AC

To funkcja równoważności logicznej między A i C, niezależna od B i D.

Zasady grupowania jedynek w tablicy Karnaugh

Najważniejszym etapem pracy z tablicą Karnaugh jest grupowanie jedynek. Od poprawnego grupowania zależy, czy uzyskana funkcja będzie rzeczywiście uproszczona.

Grupy muszą mieć rozmiar będący potęgą dwójki

W tablicy Karnaugh wolno tworzyć grupy zawierające:

  • 1 pole,
  • 2 pola,
  • 4 pola,
  • 8 pól,
  • 16 pól,
  • ewentualnie więcej w większych tablicach.

Nie wolno tworzyć grup po 3, 5, 6, 7, 10 czy 12 pól, nawet jeśli wydają się wizualnie wygodne.

Dlaczego? Ponieważ uproszczenia wynikają z eliminowania zmiennych parami, czwórkami, ósemkami i tak dalej. Tylko grupy o rozmiarach będących potęgą dwójki odpowiadają poprawnym przekształceniom algebry Boole’a.

Grupy powinny być jak największe

Im większa grupa, tym więcej zmiennych można wyeliminować. Dlatego zawsze warto szukać największych możliwych grup.

Ogólna zasada:

większa grupa oznacza prostszy składnik funkcji.

Dla funkcji czterech zmiennych:

  • grupa 1 pola daje składnik z 4 zmiennymi,
  • grupa 2 pól daje składnik z 3 zmiennymi,
  • grupa 4 pól daje składnik z 2 zmiennymi,
  • grupa 8 pól daje składnik z 1 zmienną,
  • grupa 16 pól daje funkcję równą 1.

Grupy mogą się nakładać

W tablicy Karnaugh wolno używać tej samej jedynki w więcej niż jednej grupie. Jest to nie tylko dozwolone, ale czasem konieczne, aby uzyskać najlepsze uproszczenie.

Początkujący często myślą, że każde pole można wykorzystać tylko raz. To błąd. Jeśli nakładanie grup pozwala utworzyć większe grupy i uprościć wyrażenie, należy z tego korzystać.

Każda jedynka musi być pokryta

Jeżeli minimalizujemy funkcję w postaci sumy iloczynów, każda jedynka w tablicy musi zostać objęta przynajmniej jedną grupą. Nie można pominąć jedynki, ponieważ oznaczałoby to, że uproszczona funkcja nie będzie równa 1 dla tej kombinacji wejściowej.

Nie trzeba grupować zer przy postaci SOP

Jeżeli tworzymy funkcję w postaci sumy iloczynów, grupujemy jedynki. Zera nie muszą być grupowane. Są one po prostu miejscami, dla których funkcja ma wartość 0.

Jeżeli natomiast chcemy uzyskać postać iloczynu sum, wtedy grupujemy zera.

Grupy mogą przechodzić przez krawędzie

Krawędzie tablicy Karnaugh są traktowane jako sąsiadujące. To oznacza, że można tworzyć grupy:

  • obejmujące lewą i prawą krawędź,
  • obejmujące górną i dolną krawędź,
  • obejmujące cztery narożniki tablicy.

To jedna z najważniejszych zasad, o której łatwo zapomnieć.

Grupy powinny być prostokątne

Grupy w tablicy Karnaugh muszą tworzyć prostokąty lub kwadraty. Nie wolno tworzyć grup w kształcie litery L, T, krzyża ani innych nieregularnych figur.

Dopuszczalne są prostokąty zawijające się przez krawędzie, nawet jeśli na papierze wyglądają na rozdzielone.

Minimalizacja funkcji logicznej krok po kroku

Aby poprawnie zastosować tablicę Karnaugh, warto trzymać się uporządkowanego schematu działania. Dzięki temu zmniejsza się ryzyko błędów.

Krok 1: Określ liczbę zmiennych

Najpierw trzeba sprawdzić, od ilu zmiennych zależy funkcja. Liczba zmiennych decyduje o rozmiarze tablicy.

Przykładowo:

  • F(A, B) wymaga tablicy 2-zmiennowej,
  • F(A, B, C) wymaga tablicy 3-zmiennowej,
  • F(A, B, C, D) wymaga tablicy 4-zmiennowej.

Krok 2: Przygotuj układ tablicy

Następnie należy narysować tablicę z nagłówkami w kodzie Graya. To bardzo ważne, ponieważ błędna kolejność nagłówków prowadzi do błędnego grupowania.

Dla czterech zmiennych standardowy układ to:

AB \\ CD0001111000011110

Krok 3: Wpisz wartości funkcji

W pola tablicy wpisuje się wartości funkcji na podstawie tabeli prawdy, listy mintermów lub podanego wyrażenia logicznego.

Jeżeli funkcja jest podana jako suma mintermów, jedynki wpisuje się w polach odpowiadających numerom mintermów.

Przykład:

F(A,B,C,D) = Σm(0, 2, 5, 7, 8, 10, 13, 15)

Oznacza to, że w polach o numerach 0, 2, 5, 7, 8, 10, 13 i 15 należy wpisać 1. W pozostałych polach wpisuje się 0, chyba że podano warunki nieokreślone.

Krok 4: Znajdź największe grupy

Po wpisaniu wartości należy wyszukać największe możliwe grupy jedynek. Najpierw warto szukać grup 16, potem 8, potem 4, 2 i na końcu pojedynczych pól.

Nie zawsze największa widoczna grupa daje całkowicie minimalne rozwiązanie, ale w większości prostych przypadków strategia tworzenia dużych grup jest właściwa.

Krok 5: Zapisz składnik dla każdej grupy

Dla każdej grupy trzeba ustalić, które zmienne pozostają stałe. Zmienne, które zmieniają się w obrębie grupy, usuwa się.

Jeśli zmienna w całej grupie ma wartość 1, zapisuje się ją bez negacji. Jeśli w całej grupie ma wartość 0, zapisuje się ją z negacją.

Przykład:

  • A = 1 w całej grupie → zapisujemy A,
  • B = 0 w całej grupie → zapisujemy B\’,
  • C zmienia się → pomijamy C,
  • D zmienia się → pomijamy D.

Krok 6: Zsumuj składniki

Jeżeli grupujemy jedynki, końcowa funkcja ma postać sumy składników iloczynowych.

Przykład:

F = A\’C + BD + AB\’

Każdy składnik odpowiada jednej grupie. Suma logiczna oznacza, że funkcja przyjmuje wartość 1, gdy spełniony jest przynajmniej jeden z warunków opisanych przez grupy.

Krok 7: Sprawdź wynik

Na końcu warto sprawdzić, czy uproszczona funkcja rzeczywiście daje wartość 1 dla wszystkich pól, które miały być jedynkami, oraz nie daje wartości 1 tam, gdzie w tablicy były zera.

W prostych zadaniach można to zrobić mentalnie. W bardziej złożonych warto przygotować tabelę prawdy i porównać wyniki.

Przykład pełnej minimalizacji funkcji z tablicą Karnaugh

Rozważmy funkcję czterech zmiennych:

F(A,B,C,D) = Σm(0, 1, 2, 3, 8, 9, 10, 11)

Oznacza to, że funkcja przyjmuje wartość 1 dla mintermów:

  • 0,
  • 1,
  • 2,
  • 3,
  • 8,
  • 9,
  • 10,

Krok 1: Zapis mintermów binarnie

Dla czterech zmiennych A, B, C, D numery mintermów odpowiadają kombinacjom binarnym:

  • m0 = 0000,
  • m1 = 0001,
  • m2 = 0010,
  • m3 = 0011,
  • m8 = 1000,
  • m9 = 1001,
  • m10 = 1010,
  • m11 = 1011.

Widzimy, że we wszystkich tych przypadkach zmienna B = 0. Pozostałe zmienne mogą się zmieniać.

Krok 2: Wpisanie do tablicy

AB \\ CD00011110001111010000110000101111

Krok 3: Grupowanie

Mamy dwie jedynkowe krawędzie: górny wiersz i dolny wiersz. W tablicy Karnaugh górny i dolny wiersz są sąsiadami, ponieważ tablica zawija się przez krawędzie. Można więc utworzyć jedną grupę ośmiu pól obejmującą wiersze AB = 00 i AB = 10 oraz wszystkie kolumny.

W tej grupie:

  • A zmienia się,
  • B pozostaje równe 0,
  • C zmienia się,
  • D zmienia się.

Zostaje tylko:

B\’

Wynik końcowy

F = B\’

To bardzo elegancki przykład pokazujący, że tablica Karnaugh pozwala zauważyć uproszczenia, które w zwykłej tabeli prawdy nie zawsze są oczywiste.

Postać sumy iloczynów i iloczynu sum

Tablica Karnaugh może służyć do uzyskiwania dwóch podstawowych postaci funkcji logicznej:

  • SOP, czyli suma iloczynów,
  • POS, czyli iloczyn sum.

Obie postaci opisują tę samą funkcję, ale prowadzą do innej realizacji układowej.

Suma iloczynów, czyli SOP

SOP pochodzi od angielskiego Sum of Products. W tej postaci funkcja jest sumą składników, z których każdy jest iloczynem zmiennych lub ich negacji.

Przykład:

F = A\’B + AC + BCD\’

W tablicy Karnaugh postać SOP uzyskuje się przez grupowanie jedynek.

Kiedy używać SOP?

Postać SOP jest naturalna, gdy funkcja jest podana jako suma mintermów. Jest też wygodna do realizacji za pomocą bramek AND-OR lub po odpowiednim przekształceniu za pomocą bramek NAND.

Iloczyn sum, czyli POS

POS pochodzi od angielskiego Product of Sums. W tej postaci funkcja jest iloczynem składników, z których każdy jest sumą zmiennych lub ich negacji.

Przykład:

F = (A + B\’)(C + D)(A\’ + C\’)

W tablicy Karnaugh postać POS uzyskuje się przez grupowanie zer.

Kiedy używać POS?

Postać POS jest wygodna, gdy funkcja jest podana jako iloczyn makstermów albo gdy łatwiej jest grupować zera niż jedynki. Może być także korzystna przy realizacji funkcji za pomocą bramek OR-AND lub NOR.

Grupowanie zer w tablicy Karnaugh

Choć wiele osób uczy się głównie grupowania jedynek, tablica Karnaugh pozwala również grupować zera. Wtedy otrzymuje się funkcję w postaci iloczynu sum.

Zasada grupowania zer

Zasady są podobne jak przy grupowaniu jedynek:

  • grupy muszą mieć rozmiar 1, 2, 4, 8, 16,
  • grupy powinny być jak największe,
  • grupy mogą się nakładać,
  • każda wartość 0 musi być pokryta,
  • grupy mogą przechodzić przez krawędzie,
  • grupy muszą mieć kształt prostokąta.

Różnica polega na tym, że z grup zer tworzy się składniki sumacyjne, a następnie mnoży się je logicznie.

Jak zapisywać składnik dla grupy zer?

Przy grupowaniu zer zasada zapisu zmiennych jest odwrotna niż przy grupowaniu jedynek.

Dla grupowania zer:

  • jeśli zmienna ma w całej grupie wartość 0, zapisuje się ją bez negacji,
  • jeśli zmienna ma w całej grupie wartość 1, zapisuje się ją z negacją,
  • jeśli zmienna się zmienia, pomija się ją.

Przykład: jeśli w grupie zer A = 0, B = 1, a C i D się zmieniają, składnik sumacyjny to:

(A + B\’)

Dlaczego tak? Ponieważ taki nawias ma wartość 0 dokładnie wtedy, gdy A = 0 i B = 1. A funkcja w postaci POS ma być równa 0 dla grupowanych pól.

Przykład grupowania zer

Załóżmy, że funkcja ma następującą tablicę:

AB \\ CD00011110001100011100111111101111

Zera tworzą grupę czterech pól w dwóch pierwszych wierszach i dwóch ostatnich kolumnach.

W tej grupie:

  • A = 0,
  • C = 1,
  • B zmienia się,
  • D zmienia się.

Dla POS zapisujemy:

  • A = 0 → A,
  • C = 1 → C\’.

Składnik:

(A + C\’)

Ponieważ tylko jedna grupa zer pokrywa wszystkie zera, funkcja wynosi:

F = A + C\’

Warunki nieokreślone w tablicy Karnaugh

W praktycznych zadaniach często pojawiają się tak zwane warunki nieokreślone, oznaczane jako X, d, dc albo don’t care. Są to kombinacje wejściowe, dla których wartość funkcji nie ma znaczenia.

Może to wynikać z tego, że dana kombinacja nigdy nie występuje w rzeczywistym układzie albo że zarówno 0, jak i 1 prowadzą do akceptowalnego działania.

Jak używać warunków nieokreślonych?

Warunki nieokreślone można traktować jako 1 albo jako 0, w zależności od tego, co daje prostszą funkcję.

Jeśli grupujemy jedynki, można dołączyć X do grupy jedynek, jeżeli pozwala to utworzyć większą grupę. Nie trzeba jednak obejmować wszystkich X. Warunki nieokreślone są opcjonalne.

Jeśli grupujemy zera, można dołączyć X do grup zer, jeżeli pomaga to uzyskać prostszą postać POS.

Przykład użycia X

Załóżmy, że w tablicy czterech zmiennych mamy jedynki w polach:

m(0, 1, 2, 3)

oraz warunki nieokreślone:

d(8, 9, 10, 11)

Bez warunków nieokreślonych funkcja mogłaby uprościć się do:

A\’B\’

Ale jeśli potraktujemy pola 8, 9, 10 i 11 jako jedynki pomocnicze, możemy utworzyć grupę ośmiu pól, dla której B = 0. Wtedy funkcja upraszcza się do:

B\’

To lepszy wynik, ponieważ zawiera tylko jedną zmienną.

Ważna zasada

Warunków nieokreślonych używa się tylko wtedy, gdy pomagają uprościć funkcję. Nie trzeba ich pokrywać, nie trzeba ich grupować i nie trzeba ich uwzględniać, jeśli nie dają korzyści.

Implicanty, implicanty pierwsze i implicanty istotne

W bardziej formalnym opisie tablic Karnaugh pojawiają się pojęcia implicantów. Warto je znać, ponieważ pomagają zrozumieć, jak wybierać grupy.

Implicant

Implicant to składnik logiczny, który pokrywa pewną grupę jedynek funkcji. W tablicy Karnaugh każda poprawna grupa jedynek odpowiada pewnemu implicantowi.

Przykład: grupa czterech pól, dla której A = 1 i C = 0, daje implicant:

AC\’

Implicant pierwszy

Implicant pierwszy to taka grupa, której nie da się już powiększyć bez objęcia pola, które nie powinno być objęte. Innymi słowy, jest to maksymalna możliwa grupa jedynek w danym miejscu.

W praktyce podczas minimalizacji warto szukać właśnie implicantów pierwszych, ponieważ dają one najlepsze uproszczenia.

Implicant istotny

Implicant istotny to taki implicant pierwszy, który pokrywa przynajmniej jedną jedynkę niepokrytą przez żaden inny implicant pierwszy. Taki składnik musi znaleźć się w minimalnej funkcji, ponieważ bez niego dana jedynka zostałaby pominięta.

W prostych zadaniach nie trzeba używać formalnego nazewnictwa, ale w bardziej zaawansowanych problemach pomaga ono systematycznie wybierać grupy.

Tablica Karnaugh a hazardy logiczne

Tablica Karnaugh może być używana nie tylko do minimalizacji funkcji, ale także do analizy pewnych problemów czasowych w układach logicznych. Jednym z nich są hazardy logiczne.

Czym jest hazard logiczny?

Hazard logiczny to krótkotrwały, niepożądany impuls na wyjściu układu, który może pojawić się mimo tego, że z punktu widzenia idealnej logiki wyjście nie powinno się zmienić. Wynika to z opóźnień propagacji sygnałów przez różne ścieżki bramek.

W rzeczywistych układach bramki nie przełączają się natychmiast. Jeśli dwa sygnały dochodzą do bramki różnymi drogami, mogą pojawić się chwilowe niespójności.

Jak tablica Karnaugh pomaga wykrywać hazard?

W przypadku funkcji w postaci sumy iloczynów hazard statyczny może wystąpić, gdy dwie sąsiednie jedynki są pokryte różnymi grupami, ale nie ma grupy obejmującej je razem. Dodanie nadmiarowej grupy może usunąć hazard, choć formalnie funkcja minimalna byłaby krótsza.

To pokazuje, że najkrótsza postać logiczna nie zawsze jest najlepsza pod względem działania czasowego. W niektórych układach celowo dodaje się składniki nadmiarowe, aby poprawić odporność na zakłócenia przejściowe.

Tablica Karnaugh dla pięciu zmiennych

Tablice Karnaugh dla pięciu zmiennych są możliwe, ale mniej wygodne. Funkcja pięciu zmiennych ma 32 kombinacje wejściowe, więc tablica musi mieć 32 pola.

Najczęściej przedstawia się ją jako dwie tablice czterozmiennowe:

  • jedna dla piątej zmiennej równej 0,
  • druga dla piątej zmiennej równej 1.

Sąsiedztwo między tablicami

W tablicy pięciozmiennowej pola w tych samych pozycjach w obu tablicach są sąsiadami, ponieważ różnią się tylko piątą zmienną. Oznacza to, że można tworzyć grupy obejmujące pola z obu tablic.

Przykładowo, jeśli w jednej tablicy i drugiej tablicy znajduje się taka sama grupa czterech jedynek, można połączyć je w grupę ośmiu pól i wyeliminować piątą zmienną.

Czy warto używać tablic Karnaugh dla pięciu zmiennych?

Do celów edukacyjnych tak, ponieważ pozwalają zrozumieć uogólnienie metody. W praktyce jednak dla pięciu i większej liczby zmiennych wygodniejsze są narzędzia komputerowe albo metoda Quine’a-McCluskeya.

Tablica Karnaugh dla sześciu zmiennych

Dla sześciu zmiennych funkcja ma 64 pola. Można ją reprezentować jako cztery tablice czterozmiennowe albo jako bardziej złożoną mapę wielowymiarową. W praktyce ręczne grupowanie staje się trudne i podatne na błędy.

W tablicy sześciu zmiennych nadal obowiązują te same zasady:

  • grupy mają rozmiary będące potęgami dwójki,
  • pola sąsiadujące różnią się jedną zmienną,
  • można grupować przez krawędzie,
  • można korzystać z warunków nieokreślonych,
  • grupy powinny być jak największe.

Problem polega na tym, że wizualne wykrywanie wszystkich możliwych grup jest znacznie trudniejsze. Dlatego w większych projektach wykorzystuje się algorytmy i programy do syntezy logicznej.

Tablica Karnaugh a metoda Quine’a-McCluskeya

Tablica Karnaugh jest metodą graficzną. Działa świetnie dla niewielkiej liczby zmiennych, ale staje się niewygodna dla bardziej złożonych funkcji. Alternatywą jest metoda Quine’a-McCluskeya, czyli metoda tablicowa.

Różnice między metodami

Tablica Karnaugh:

  • jest graficzna,
  • jest intuicyjna,
  • świetnie nadaje się do nauki,
  • dobrze działa dla 2–4 zmiennych,
  • dla 5–6 zmiennych jest możliwa, ale mniej wygodna,
  • dla większej liczby zmiennych staje się niepraktyczna.

Metoda Quine’a-McCluskeya:

  • jest algorytmiczna,
  • nadaje się do implementacji komputerowej,
  • lepiej radzi sobie z większą liczbą zmiennych,
  • jest bardziej systematyczna,
  • wymaga więcej formalnych obliczeń.

Kiedy wybrać tablicę Karnaugh?

Tablica Karnaugh jest najlepsza, gdy:

  • funkcja ma niewiele zmiennych,
  • zależy nam na szybkim ręcznym uproszczeniu,
  • uczymy się techniki cyfrowej,
  • chcemy wizualnie zrozumieć minimalizację,
  • funkcja pochodzi z małej tabeli prawdy.

Kiedy wybrać metodę algorytmiczną?

Metody algorytmiczne są lepsze, gdy:

  • funkcja ma wiele zmiennych,
  • liczba mintermów jest duża,
  • trzeba mieć pewność znalezienia optimum,
  • funkcja jest częścią większego projektu cyfrowego,
  • minimalizację wykonuje narzędzie EDA.

Tablica Karnaugh w projektowaniu bramek logicznych

Jednym z najczęstszych zastosowań tablic Karnaugh jest projektowanie układów z bramek logicznych. Po uproszczeniu funkcji można bezpośrednio przejść do schematu.

Realizacja w bramkach AND, OR, NOT

Jeżeli funkcja jest w postaci SOP, można ją zrealizować przy pomocy:

  • bramek NOT do uzyskania negacji zmiennych,
  • bramek AND do utworzenia składników iloczynowych,
  • bramki OR do zsumowania składników.

Przykład:

F = A\’B + CD

Realizacja wymaga:

  • negacji A,
  • bramki AND dla A\’B,
  • bramki AND dla CD,
  • bramki OR łączącej oba wyniki.

Realizacja w bramkach NAND

Bramki NAND są bardzo uniwersalne. Każdą funkcję logiczną można zrealizować wyłącznie za pomocą bramek NAND. Postać SOP łatwo przekształcić do realizacji NAND-NAND.

Dla funkcji:

F = AB + CD

Można użyć prawa de Morgana:

F = ((AB)\’ · (CD)\’)\’

To oznacza, że najpierw tworzymy NAND dla AB i CD, a następnie ich wyniki podajemy na kolejną bramkę NAND.

Realizacja w bramkach NOR

Analogicznie, każdą funkcję można zrealizować za pomocą bramek NOR. Postać POS jest szczególnie wygodna do realizacji NOR-NOR.

Dla funkcji:

F = (A + B)(C + D)

Można zapisać:

F = ((A + B)\’ + (C + D)\’)\’

co odpowiada strukturze NOR-NOR.

Zastosowania tablic Karnaugh w praktyce

Choć obecnie wiele układów cyfrowych projektuje się za pomocą języków opisu sprzętu i narzędzi automatycznej syntezy, tablica Karnaugh nadal ma duże znaczenie edukacyjne i praktyczne.

Projektowanie prostych układów sterowania

Tablice Karnaugh doskonale sprawdzają się przy projektowaniu prostych układów sterowania. Przykładowo można zaprojektować układ, który włącza alarm tylko dla określonych kombinacji czujników.

Jeśli mamy trzy wejścia:

  • A – czujnik drzwi,
  • B – czujnik ruchu,
  • C – tryb uzbrojenia alarmu,

to można utworzyć tabelę prawdy, a następnie uprościć funkcję alarmu za pomocą tablicy Karnaugh.

Dekodery i kodery

Tablice Karnaugh mogą być używane do projektowania dekoderów, czyli układów zamieniających kod binarny na określone sygnały wyjściowe. Przykładem jest dekoder kodu BCD na wyświetlacz siedmiosegmentowy.

Dla każdego segmentu wyświetlacza można zbudować osobną funkcję logiczną, a następnie uprościć ją za pomocą tablicy Karnaugh. Warunki nieokreślone dla kodów 10–15 w BCD mogą dodatkowo uprościć projekt.

Multipleksery i demultipleksery

Funkcje logiczne opisujące pracę multiplekserów również można analizować i upraszczać za pomocą tablic Karnaugh. Choć standardowe multipleksery są zwykle gotowymi blokami, metoda ta pomaga zrozumieć ich działanie.

Układy porównujące

Proste komparatory cyfrowe, które porównują dwie liczby binarne, można opisać funkcjami logicznymi. Tablica Karnaugh pomaga znaleźć uproszczone wyrażenia dla sygnałów typu:

  • A = B,
  • A > B,
  • A < B.

Automatyka i logika przekaźnikowa

Tablica Karnaugh może być przydatna również w automatyce. Jeżeli sterownik ma reagować na kombinacje stanów czujników, przycisków i warunków bezpieczeństwa, można najpierw opisać logikę w formie tabeli prawdy, a potem uprościć ją.

Choć w praktyce sterowniki PLC programuje się często językami drabinkowymi lub blokowymi, zrozumienie minimalizacji logicznej pomaga tworzyć bardziej przejrzyste programy sterujące.

Przykład praktyczny: układ alarmowy

Rozważmy prosty układ alarmowy z trzema wejściami:

  • A – system uzbrojony,
  • B – wykryto ruch,
  • C – otwarte drzwi.

Chcemy, aby alarm F włączył się, gdy system jest uzbrojony oraz wystąpi ruch lub otwarcie drzwi.

Warunek logiczny można od razu zapisać jako:

F = A(B + C)

Ale załóżmy, że zaczynamy od tabeli prawdy.

ABCF00000010010001101000101111011111

Jedynki występują dla mintermów:

m(5, 6, 7)

Tablica Karnaugh:

A \\ BC000111100000010111

Można utworzyć dwie grupy po dwie jedynki:

Pierwsza grupa obejmuje pola BC = 01 i 11 przy A = 1. W tej grupie:

  • A = 1,
  • C = 1,
  • B zmienia się.

Składnik:

AC

Druga grupa obejmuje pola BC = 11 i 10 przy A = 1. W tej grupie:

  • A = 1,
  • B = 1,
  • C zmienia się.

Składnik:

AB

Funkcja:

F = AC + AB

Po wyłączeniu A przed nawias:

F = A(C + B)

czyli:

F = A(B + C)

Tablica Karnaugh prowadzi więc do logicznego i prostego wyniku.

Przykład praktyczny: wyświetlacz siedmiosegmentowy

Jednym z klasycznych zastosowań tablic Karnaugh jest projektowanie sterowania wyświetlaczem siedmiosegmentowym. Taki wyświetlacz ma siedem segmentów, które oznacza się zwykle literami:

  • a,
  • b,
  • c,
  • d,
  • e,
  • f,
  • g.

Wejściem może być liczba w kodzie BCD, czyli cztery bity reprezentujące cyfry od 0 do 9. Dla każdej cyfry trzeba określić, które segmenty mają świecić.

Dlaczego tablica Karnaugh jest tu przydatna?

Kod BCD wykorzystuje tylko kombinacje od 0000 do 1001. Kombinacje od 1010 do 1111 nie odpowiadają poprawnym cyfrom dziesiętnym. Można więc potraktować je jako warunki nieokreślone.

Dzięki temu funkcje sterujące poszczególnymi segmentami można często znacznie uprościć.

Osobna funkcja dla każdego segmentu

Dla segmentu a tworzy się osobną funkcję logiczną. Dla segmentu b kolejną, i tak dalej. Każdą z tych funkcji można rozpisać w tablicy Karnaugh czterech zmiennych i zminimalizować.

W praktyce gotowe dekodery BCD na wyświetlacz siedmiosegmentowy są dostępne jako układy scalone, ale zrozumienie tej procedury jest bardzo cenne edukacyjnie.

Tablica Karnaugh w kontekście tabeli prawdy

Tabela prawdy i tablica Karnaugh opisują tę samą funkcję, ale robią to w inny sposób.

Tabela prawdy

Tabela prawdy jest pełnym zestawieniem wszystkich kombinacji wejściowych i odpowiadających im wartości wyjściowych. Jest bardzo systematyczna i jednoznaczna.

Jej zalety:

  • pokazuje wszystkie przypadki,
  • jest łatwa do zrozumienia,
  • dobrze nadaje się do definiowania funkcji.

Jej wady:

  • nie pokazuje łatwo zależności sąsiednich kombinacji,
  • nie ułatwia bezpośrednio minimalizacji,
  • przy wielu zmiennych staje się długa.

Tablica Karnaugh

Tablica Karnaugh jest przekształconą tabelą prawdy, w której kombinacje są rozmieszczone tak, aby ułatwić grupowanie.

Jej zalety:

  • ułatwia minimalizację,
  • pokazuje sąsiedztwo logiczne,
  • pozwala szybko zauważyć uproszczenia,
  • dobrze działa dla małych funkcji.

Jej wady:

  • wymaga znajomości kodu Graya,
  • łatwo popełnić błąd przy wpisywaniu wartości,
  • jest mniej wygodna dla dużej liczby zmiennych.

Jak przejść z tabeli prawdy do tablicy Karnaugh?

Przejście z tabeli prawdy do tablicy Karnaugh wymaga uważności. Najczęstszy błąd polega na wpisywaniu wartości w złe pola, zwłaszcza przy czterech zmiennych.

Procedura

Najbezpieczniej wykonać następujące kroki:

  1. Ustal kolejność zmiennych, na przykład A, B, C, D.
  2. Przygotuj tablicę Karnaugh z nagłówkami w kodzie Graya.
  3. Dla każdej kombinacji z tabeli prawdy odczytaj numer mintermu lub wartości zmiennych.
  4. Znajdź odpowiadające pole w tablicy.
  5. Wpisz wartość funkcji.
  6. Sprawdź, czy liczba jedynek w tablicy zgadza się z liczbą jedynek w tabeli prawdy.

Przykład numeracji mintermów

Dla zmiennych A, B, C, D numer mintermu odpowiada liczbie binarnej ABCD.

Przykłady:

  • ABCD = 0000 → m0,
  • ABCD = 0001 → m1,
  • ABCD = 0010 → m2,
  • ABCD = 0011 → m3,
  • ABCD = 0100 → m4,
  • ABCD = 1111 → m15.

W tablicy Karnaugh trzeba jednak pamiętać, że wiersze i kolumny nie idą w zwykłej kolejności 00, 01, 10, 11, lecz w kolejności 00, 01, 11, 10.

Jak przejść z wyrażenia logicznego do tablicy Karnaugh?

Czasami funkcja nie jest podana jako tabela prawdy, lecz jako wyrażenie logiczne. Wtedy można ją przenieść do tablicy Karnaugh na dwa sposoby.

Metoda przez tabelę prawdy

Najbardziej systematyczna metoda polega na utworzeniu tabeli prawdy. Dla każdej kombinacji wejść obliczamy wartość funkcji, a następnie wpisujemy ją do tablicy Karnaugh.

Ta metoda jest wolniejsza, ale bezpieczna.

Metoda przez mintermy

Jeśli funkcja jest w postaci sumy iloczynów, można bezpośrednio zaznaczać pola odpowiadające składnikom.

Przykład:

F = A\’B + AC

Dla składnika A\’B:

  • A = 0,
  • B = 1,
  • pozostałe zmienne mogą być dowolne.

Zaznaczamy więc wszystkie pola, w których A = 0 i B = 1.

Dla składnika AC:

  • A = 1,
  • C = 1,
  • pozostałe zmienne mogą być dowolne.

Zaznaczamy wszystkie pola, w których A = 1 i C = 1.

Po zaznaczeniu pól otrzymujemy tablicę funkcji.

Jak odczytać funkcję z tablicy Karnaugh?

Odczytanie funkcji z tablicy Karnaugh polega na przekształceniu grup w składniki logiczne.

Dla jedynek

Jeśli grupujemy jedynki:

  • zmienna stała równa 1 zostaje bez negacji,
  • zmienna stała równa 0 zostaje z negacją,
  • zmienna zmieniająca się zostaje usunięta,
  • składniki łączymy znakiem OR, czyli plusem.

Przykład:

Grupa ma A = 1, B = 0, C zmienne, D zmienne.

Składnik:

AB\’

Dla zer

Jeśli grupujemy zera:

  • zmienna stała równa 0 zostaje bez negacji,
  • zmienna stała równa 1 zostaje z negacją,
  • zmienna zmieniająca się zostaje usunięta,
  • składniki zapisujemy jako nawiasy sumacyjne,
  • nawiasy mnożymy logicznie.

Przykład:

Grupa zer ma A = 0, B = 1, C zmienne, D zmienne.

Składnik:

(A + B\’)

Minimalna postać a najprostsza realizacja układowa

Warto pamiętać, że minimalna postać funkcji logicznej nie zawsze oznacza najłatwiejszą realizację w konkretnych warunkach. Czasami układ z pozornie większą liczbą składników może być wygodniejszy, jeśli korzystamy z określonego typu bramek.

Dostępność bramek

Jeśli w projekcie mamy tylko bramki NAND, funkcja w postaci SOP może być bardzo wygodna. Jeśli mamy tylko bramki NOR, często korzystniejsza jest postać POS.

Liczba wejść bramek

W praktycznych układach scalonych bramki mają ograniczoną liczbę wejść. Nawet jeśli funkcja teoretycznie ma jeden składnik z wieloma zmiennymi, może wymagać kilku bramek połączonych kaskadowo. To może zwiększyć opóźnienie i złożoność.

Opóźnienia i hazardy

Jak wspomniano wcześniej, czasem warto dodać składnik nadmiarowy, aby uniknąć hazardu. Wtedy funkcja nie jest minimalna w sensie liczby literałów, ale może być lepsza w działaniu rzeczywistego układu.

Najczęstsze błędy przy używaniu tablic Karnaugh

Tablica Karnaugh jest narzędziem intuicyjnym, ale wymaga przestrzegania kilku zasad. Poniżej znajdują się najczęstsze błędy, które prowadzą do złych wyników.

Błędna kolejność kolumn lub wierszy

Najczęstszy błąd to użycie kolejności binarnej:

00, 01, 10, 11

zamiast kodu Graya:

00, 01, 11, 10

Taki błąd całkowicie psuje sąsiedztwo pól i prowadzi do niepoprawnej minimalizacji.

Grupowanie pól po przekątnej

Pola stykające się tylko narożnikami nie są sąsiadami. Nie wolno łączyć jedynek po przekątnej. Sąsiedztwo dotyczy tylko pól poziomo i pionowo, z uwzględnieniem zawijania krawędzi.

Tworzenie grup o złym rozmiarze

Nie wolno tworzyć grup po 3, 6 czy 12 pól. Grupy muszą mieć rozmiar będący potęgą dwójki.

Zapominanie o zawijaniu krawędzi

Wielu początkujących pomija możliwość łączenia pól z lewej i prawej krawędzi albo z górnej i dolnej. Przez to otrzymują dłuższe wyrażenia niż trzeba.

Niepotrzebne małe grupy

Jeżeli można utworzyć grupę czterech jedynek, nie należy zastępować jej dwiema grupami po dwie, chyba że istnieje szczególny powód. Większe grupy dają prostsze składniki.

Pomijanie jedynek

Każda jedynka musi być objęta przynajmniej jedną grupą. Pominięcie pola oznacza, że funkcja po minimalizacji nie będzie zgodna z oryginałem.

Obowiązkowe używanie wszystkich X

Warunki nieokreślone nie muszą być użyte. Używa się ich tylko wtedy, gdy pomagają utworzyć większą grupę. Traktowanie każdego X jako obowiązkowej jedynki jest błędem.

Złe odczytywanie zmiennych z grupy

Po utworzeniu grupy należy dokładnie sprawdzić, które zmienne są stałe. Zmienna, która zmienia się w obrębie grupy, musi zostać usunięta. Pozostawienie jej w składniku prowadzi do zbyt szczegółowej, a czasem błędnej funkcji.

Dobre praktyki przy rozwiązywaniu zadań z tablic Karnaugh

Aby sprawnie korzystać z tablic Karnaugh, warto stosować kilka praktycznych zasad.

Zawsze podpisuj zmienne

Nie zostawiaj tablicy bez opisanych wierszy i kolumn. Brak podpisów bardzo łatwo prowadzi do błędów przy odczytywaniu grup.

Zaznaczaj grupy różnymi obwódkami

Jeśli rysujesz tablicę na papierze, zaznaczaj grupy różnymi liniami lub kolorami. Dzięki temu łatwiej zobaczyć, czy każda jedynka została pokryta.

Szukaj grup przez krawędzie

Po znalezieniu oczywistych grup w środku tablicy zawsze sprawdź krawędzie i narożniki. Tam często ukrywają się największe uproszczenia.

Zaczynaj od największych grup

Najpierw szukaj grup o największym możliwym rozmiarze. Dopiero potem zajmuj się mniejszymi grupami i pojedynczymi jedynkami.

Sprawdzaj wynik przez podstawienie

Po uzyskaniu uproszczonej funkcji sprawdź kilka kombinacji wejść, szczególnie te, które leżą na granicach grup. To pozwala szybko wykryć błędy.

Tablica Karnaugh w nauce elektroniki cyfrowej

Dla uczniów i studentów tablica Karnaugh jest jednym z najważniejszych tematów w technice cyfrowej. Łączy teorię algebry Boole’a z praktycznym projektowaniem układów.

Dlaczego warto ją opanować?

Opanowanie tablic Karnaugh pomaga zrozumieć:

  • czym jest funkcja logiczna,
  • jak działa tabela prawdy,
  • jak upraszcza się wyrażenia Boole’a,
  • jak projektuje się układy kombinacyjne,
  • dlaczego kolejność kodu Graya jest ważna,
  • jak przechodzi się od teorii do bramek logicznych.

Nawet jeśli w pracy zawodowej korzysta się z narzędzi automatycznych, zrozumienie podstaw minimalizacji logicznej pozwala lepiej diagnozować problemy i projektować bardziej świadomie.

Tablica Karnaugh w informatyce

Tablica Karnaugh kojarzy się głównie z elektroniką, ale jej znaczenie wykracza poza projektowanie fizycznych układów. Funkcje logiczne są również podstawą informatyki, programowania, baz danych i warunków decyzyjnych.

Upraszczanie warunków logicznych

W programowaniu często spotyka się złożone warunki logiczne. Choć programiści rzadko rysują tablice Karnaugh, sama idea minimalizacji może pomóc uprościć instrukcje warunkowe.

Przykład:

if ((A && B) || (A && !B)) {
    ...
}

Ten warunek można uprościć do:

if (A) {
    ...
}

To dokładnie ta sama zasada, którą wizualnie pokazuje tablica Karnaugh.

Optymalizacja logiki decyzyjnej

W systemach regułowych, konfiguratorach, walidatorach i prostych silnikach decyzyjnych złożone warunki można analizować podobnie jak funkcje logiczne. Minimalizacja pomaga uniknąć powtarzania tych samych warunków i zwiększa czytelność kodu.

Tablica Karnaugh w automatyce i mechatronice

W automatyce często pojawiają się układy, które reagują na kombinacje stanów wejściowych. Mogą to być czujniki, przyciski, krańcówki, blokady bezpieczeństwa lub sygnały ze sterownika.

Przykład logiki maszyny

Maszyna może uruchomić napęd tylko wtedy, gdy:

  • drzwi są zamknięte,
  • osłona jest założona,
  • wciśnięto przycisk start,
  • nie ma sygnału awarii.

Taki warunek można zapisać logicznie, uprościć i zaimplementować w sterowniku lub układzie przekaźnikowym. Tablica Karnaugh pomaga szczególnie wtedy, gdy warunków jest kilka i nie wszystkie kombinacje są dozwolone.

Warunki niedozwolone jako don’t care

W automatyce niektóre kombinacje wejść mogą nigdy nie wystąpić. Na przykład dwa czujniki mogą być mechanicznie wykluczające się. Takie przypadki można potraktować jako warunki nieokreślone, co ułatwia uproszczenie logiki.

Jak ćwiczyć tablice Karnaugh?

Najlepszym sposobem nauki jest rozwiązywanie wielu przykładów, zaczynając od prostych funkcji dwuzmiennych i stopniowo przechodząc do czterech zmiennych.

Proponowana kolejność nauki

Warto ćwiczyć w takiej kolejności:

  1. Tablice dla dwóch zmiennych.
  2. Tablice dla trzech zmiennych bez zawijania.
  3. Tablice dla trzech zmiennych z zawijaniem.
  4. Tablice dla czterech zmiennych.
  5. Grupowanie przez krawędzie.
  6. Grupowanie narożników.
  7. Warunki nieokreślone.
  8. Grupowanie zer i postać POS.
  9. Zadania praktyczne z tabel prawdy.
  10. Realizacja funkcji za pomocą bramek.

Co sprawdzać po każdym zadaniu?

Po każdym rozwiązaniu warto odpowiedzieć sobie na pytania:

  • Czy nagłówki są w kodzie Graya?
  • Czy każda jedynka została pokryta?
  • Czy grupy mają rozmiar będący potęgą dwójki?
  • Czy nie połączono pól po przekątnej?
  • Czy wykorzystano możliwość zawijania?
  • Czy warunki X użyto tylko wtedy, gdy pomagają?
  • Czy odczytane składniki zawierają tylko stałe zmienne?

Krótka ściąga z tablic Karnaugh

Poniżej znajduje się praktyczne podsumowanie zasad, które warto zapamiętać podczas pracy z tablicami Karnaugh.

Najważniejsze zasady

  • Tablica Karnaugh służy do minimalizacji funkcji logicznych.
  • Sąsiednie pola różnią się tylko jedną zmienną.
  • Wiersze i kolumny opisuje się w kodzie Graya.
  • Dla SOP grupuje się jedynki.
  • Dla POS grupuje się zera.
  • Grupy muszą mieć rozmiary 1, 2, 4, 8, 16.
  • Grupy powinny być jak największe.
  • Grupy mogą się nakładać.
  • Krawędzie tablicy są sąsiadujące.
  • Pola po przekątnej nie są sąsiadami.
  • Warunki nieokreślone można wykorzystać, ale nie trzeba.
  • Zmienna zmieniająca się w grupie znika z wyrażenia.
  • Zmienna stała w grupie pozostaje w wyrażeniu.

Jak zapamiętać odczyt grup?

Dla grupowania jedynek:

  • stałe 1 → zmienna bez negacji,
  • stałe 0 → zmienna z negacją.

Dla grupowania zer:

  • stałe 0 → zmienna bez negacji,
  • stałe 1 → zmienna z negacją.

To prosta różnica, ale bardzo ważna.

FAQ

Co to jest tablica Karnaugh?

Tablica Karnaugh to graficzna metoda minimalizacji funkcji logicznych. Pozwala uprościć wyrażenie logiczne przez grupowanie sąsiednich jedynek lub zer w specjalnie uporządkowanej tabeli. Dzięki temu można otrzymać krótszą postać funkcji i łatwiej zaprojektować układ logiczny.

Do czego służy tablica Karnaugh?

Tablica Karnaugh służy do upraszczania funkcji logicznych, projektowania układów kombinacyjnych, redukcji liczby bramek logicznych i przechodzenia od tabeli prawdy do praktycznego schematu cyfrowego.

Dlaczego w tablicy Karnaugh używa się kodu Graya?

Kod Graya zapewnia, że sąsiednie pola różnią się tylko jedną zmienną. To warunek konieczny poprawnego grupowania pól i eliminowania zmiennych z wyrażenia logicznego.

Ile pól ma tablica Karnaugh dla czterech zmiennych?

Tablica Karnaugh dla czterech zmiennych ma 16 pól, ponieważ liczba kombinacji wejściowych wynosi 2⁴ = 16.

Czy w tablicy Karnaugh można łączyć pola po przekątnej?

Nie. Pola po przekątnej nie są sąsiadami. Można łączyć tylko pola sąsiadujące poziomo lub pionowo, z uwzględnieniem zawijania krawędzi.

Czy grupy w tablicy Karnaugh mogą się nakładać?

Tak. Grupy mogą się nakładać, jeśli prowadzi to do prostszego wyrażenia. To często pomaga uzyskać większe grupy i krótszą postać funkcji.

Jakie rozmiary mogą mieć grupy w tablicy Karnaugh?

Grupy mogą mieć rozmiary będące potęgami dwójki: 1, 2, 4, 8, 16 i tak dalej. Nie wolno tworzyć grup po 3, 5, 6 czy 7 pól.

Czy trzeba wykorzystać wszystkie warunki nieokreślone?

Nie. Warunki nieokreślone wykorzystuje się tylko wtedy, gdy pomagają uprościć funkcję. Można je potraktować jako 1, jako 0 albo pominąć, zależnie od potrzeb minimalizacji.

Czym różni się grupowanie jedynek od grupowania zer?

Grupowanie jedynek prowadzi do postaci SOP, czyli sumy iloczynów. Grupowanie zer prowadzi do postaci POS, czyli iloczynu sum. Obie metody mogą opisywać tę samą funkcję, ale dają inną formę zapisu.

Czy tablica Karnaugh nadaje się dla pięciu zmiennych?

Tak, ale staje się mniej wygodna. Dla pięciu zmiennych używa się zwykle dwóch tablic czterozmiennowych. Dla większej liczby zmiennych częściej stosuje się metody algorytmiczne lub narzędzia komputerowe.

Co oznacza minterm w tablicy Karnaugh?

Minterm to jedna konkretna kombinacja wartości zmiennych wejściowych, dla której funkcja może przyjmować wartość 1. W zapisie funkcji jako sumy mintermów podaje się numery tych kombinacji, dla których funkcja jest równa 1.

Co oznacza maksterm?

Maksterm to składnik związany z kombinacją wejść, dla której funkcja przyjmuje wartość 0. Makstermy są wykorzystywane przy zapisie funkcji w postaci iloczynu sum.

Jak sprawdzić, czy wynik z tablicy Karnaugh jest poprawny?

Najlepiej porównać uproszczoną funkcję z pierwotną tabelą prawdy. Dla każdej kombinacji wejść wynik powinien być taki sam jak w oryginalnej funkcji, z wyjątkiem warunków nieokreślonych, gdzie wynik może być dowolny.

Czy tablica Karnaugh zawsze daje najprostszą funkcję?

Dla małej liczby zmiennych i poprawnego grupowania tablica Karnaugh pozwala znaleźć bardzo prostą, często minimalną postać funkcji. Przy większej liczbie zmiennych metoda staje się mniej wygodna i łatwiej przeoczyć optymalne grupowanie.

Czy tablica Karnaugh jest jeszcze używana?

Tak. Jest powszechnie używana w edukacji technicznej i nadal przydaje się przy projektowaniu prostych układów logicznych. W dużych projektach cyfrowych minimalizację wykonują narzędzia komputerowe, ale znajomość tablic Karnaugh pomaga zrozumieć, jak działa synteza logiczna.