Solver Tablicy Karnaugha (K-Map)

Upraszczanie funkcji boolowskiej za pomocą tablicy Karnaugha

Tablica Karnaugha pozwala przedstawić funkcję boolowską w taki sposób, aby kombinacje różniące się tylko jedną zmienną znalazły się obok siebie. Dzięki temu łatwiej zauważyć, które zmienne można usunąć z końcowego wyrażenia.

Solver obsługuje 2, 3, 4 i 5 zmiennych. Funkcję można wprowadzić przez K-Map, tabelę prawdy, wyrażenie boolowskie, mintermy albo makstermy.

Wszystkie sposoby wprowadzania opisują tę samą funkcję. Zmiana wartości w jednym miejscu aktualizuje pozostałe widoki.

Wartości 0, 1 oraz X

Każde pole może mieć wartość:

• 1 — funkcja jest prawdziwa dla danej kombinacji;
• 0 — funkcja jest fałszywa;
• X — stan nieistotny.

Stan X można wykorzystać, jeśli pozwala utworzyć większą grupę i uprościć wyrażenie. Jeżeli nie daje korzyści, może pozostać niewykorzystany.

Od tabeli prawdy do tablicy Karnaugha

Tabela prawdy pokazuje wszystkie możliwe kombinacje zmiennych wejściowych i odpowiadające im wartości funkcji.

K-Map przedstawia te same dane w układzie zgodnym z kodem Graya. Sąsiednie pola różnią się dzięki temu tylko jedną zmienną.

Przykład:

A'B'

A'B

Zmienia się wyłącznie B.

Po połączeniu obu przypadków otrzymujemy:

A'

Zmienna, która zmienia się wewnątrz grupy, nie musi występować w uproszczonym termie.

Ta sama zasada działa dla grup 4, 8 i większej liczby pól.

Mintermy, makstermy i wyrażenia boolowskie

Jeśli zadanie podaje indeksy, nie trzeba ręcznie ustawiać każdej komórki.

Zapis:

Σm(1,3,5,7)

określa mintermy, czyli kombinacje, dla których funkcja ma wartość 1.

Zapis:

ΠM(0,2,4,6)

określa makstermy odpowiadające wartości 0.

Można również rozpocząć od wyrażenia boolowskiego. Solver oblicza jego wartości i tworzy odpowiadającą mu tabelę prawdy oraz tablicę Karnaugha.

Pozwala to szybko porównać kilka sposobów zapisu tej samej funkcji.

Jak tworzone są grupy K-Map

Poprawne grupy mają liczbę pól będącą potęgą liczby dwa:

1, 2, 4, 8, 16

Większa prawidłowa grupa zwykle oznacza mniej literałów w otrzymanym termie.

Trzeba też pamiętać, że przeciwległe krawędzie tablicy są ze sobą sąsiadujące.

Lewa krawędź może łączyć się z prawą, a górna z dolną. Dlatego cztery narożniki mogą tworzyć jedną poprawną grupę.

Grupy mogą się nakładać, jeżeli pozwala to uzyskać prostszą postać funkcji.

Solver zaznacza użyte grupy, dzięki czemu można porównać wynik algebraiczny z układem pól na tablicy.

SOP i POS

W postaci SOP (Sum of Products) podstawą uproszczenia są wartości 1.

Przykładowy wynik:

A'B + BC

W POS (Product of Sums) wykorzystuje się wartości 0.

Na przykład:

(A + B')(B + C)

Ta sama funkcja może mieć krótszą postać SOP albo POS. Zależy to od rozmieszczenia zer i jedynek.

Jeżeli zadanie nie wymaga określonej postaci, warto sprawdzić oba wyniki.

Quine-McCluskey i Petrick's Method

Ręczne grupowanie jest wygodne przy prostych funkcjach, ale przy większej liczbie zmiennych może istnieć kilka poprawnych pokryć.

Solver korzysta z Quine-McCluskey, aby systematycznie tworzyć i porównywać implikanty.

Implikant, którego nie można już powiększyć, jest implikantem pierwszym.

Niektóre z nich są istotne, ponieważ pokrywają wymagany minterm, którego nie pokrywa żaden inny implikant pierwszy.

Jeśli po wybraniu takich przypadków pozostaje kilka sposobów zakończenia pokrycia, Petrick's Method pozwala przeanalizować pozostałe kombinacje.

Jest to szczególnie pomocne wtedy, gdy kilka grup na tablicy wygląda równie dobrze.

Tablice Karnaugha dla 2–5 zmiennych

Tablica dla 2 zmiennych ma 4 pola.

Przy 3 zmiennych pojawia się 8 pól i łatwiej zauważyć sąsiedztwo między przeciwnymi krawędziami.

4-zmienna tablica Karnaugha ma 16 pól i jest często używana w zadaniach z techniki cyfrowej.

Dla 5 zmiennych funkcja ma 32 kombinacje wejść. Liczba możliwych grup rośnie, szczególnie gdy pojawiają się stany nieistotne.

Niezależnie od liczby zmiennych solver utrzymuje synchronizację między K-Map, tabelą prawdy i pozostałymi sposobami wprowadzania funkcji.

Układ logiczny i eksport PDF

Uproszczone wyrażenie można również wyświetlić jako układ logiczny.

Pozwala to zobaczyć, jak wynik SOP lub POS przekłada się na bramki AND, OR oraz NOT.

Można także porównać liczbę termów, literałów i bramek.

Pełne rozwiązanie można zapisać jako PDF razem z tablicą Karnaugha, grupami, kolejnymi krokami i schematem układu.