1

Mateusz Macięga

Informatyka

Grupa 11

MINIMALIZACJA FUNKCJI LOGICZNYCH

Funkcja logiczna może być w ogólnym przypadku przedstawiona za pomocą wielu

różnych

mniej

lub

bardziej

skomplikowanych

funkcji

logicznych.

Zagadnienie

minimalizacji polega na wyznaczeniu dla danej funkcji tej formuły, która jest najprostsza.
Zagadnienie to formułuje się też inaczej – dla danej funkcji logicznej należy wyznaczyć
możliwą najprostszą funkcję równoważną.
Minimalizacja funkcji logicznej wiąże się z porównaniem stopnia skomplikowania funkcji.

Metody minimalizacji funkcji logicznych można podzielić na dwie grupy. Do pierwszej
grupy należą metody przekształceń algebraicznych. Metody te nie są zbyt przydatne w
praktyce. Do drugiej grupy należą metody algorytmiczne.
Podstawową rzeczą jest stworzenie tabeli prawdy, z której korzystamy niezależnie od
wybranego przez nas sposobu.

Metoda Karnaugha:
Metoda ta polega na zastosowaniu tablic Karnaugha. Tablica taka – kwadratowa lub
prostokątna – dla m zmiennych składa się z 2

m

ponumerowanych kratek. W każdej kratce

jest wpisany numer kombinacji odpowiadający kratce (np. w prawym, dolnym rogu) oraz
wartość funkcji 0, 1 albo symbol – lub x, jeżeli wartość funkcji jest nieokreślona.

Każda kratka tablicy Karnaugha odpowiada kombinacji (wektorowi) zmiennych. Można
więc powiedzieć że kombinacja tych zmiennych tworzy adres kratki. Kratki są
ponumerowane, przy czym jak już pokazano numer (i) jest liczbą dziesiętną
odpowiadającą kombinacji zmiennych (wektorowi zerojedynkowemu) traktowanej jako
liczba dwójkowa. W poszczególnych kratkach są wpisane – obok numerów – wartości
funkcji (tj. 0 lub 1) przyjmowane przez funkcję dla tej kombinacji, symbol – lub x, jeżeli
funkcja nie jest określona. Można też powiedzieć, że kratka o numerze i zawierająca 1
odpowiada iloczynowi pełnemu Pi w kanonicznej postaci sumy dla danej funkcji.
Natomiast kratka o numerze i zawierająca 0 odpowiada sumie pełnej Si w kanonicznej
postaci iloczynu.

Po wpisaniu wartości funkcji do tablicy przystępujemy do analizy. Jeśli w dwóch
sąsiednich kratkach wypełnionej tablicy Karnaugh znajdują się jednakowe symbole
(logiczne 0 lub logiczne 1), to odpowiadające tym kratkom wyrażenia można skleić, co
odpowiada usunięciu litery, która w ramach sklejanej grupy zmienia wartość. Takie
sąsiednie kratki tablicy, tworzące pary, łączy się linią oznaczającą możliwość sklejenia.
Przykładowe pary dla tablic trzech i czterech zmiennych zamieszczam poniżej oraz w
późniejszych przykładach.

Gdy łączonymi elementami są jedynki to funkcja nasza ma postać sumy iloczynów, więc
rezultat upraszczania będzie iloczynem, w którym symbolowi 1 odpowiada zmienna A, a
symbolowi 0 jej negacja czyli A . Jeżeli natomiast łączonymi elementami są zera to
funkcja przyjmie postać iloczynu sum, a rezultat minimalizacji będzie sumą, w której
symbolowi 1 będzie odpowiadała negacja zmiennej B , symbolowi 0 sama zmienna.

Podczas minimalizacji tą metodą należy przestrzegać kilku ważnych zasad:
1. Gdy nie zależy nam konkretnej postaci funkcji minimalizowanej (koniunkcyjnej lub
dysjunkcyjnej powinniśmy zdecydować się na łączenie tych elementów, które dadzą
nam prostsze rozwiązanie (liczebna przewaga jednych elementów nad drugimi).
2. Wśród wybranych symboli (0 albo 1) poszukuje się możliwości utworzenia
największej grupy (lub kilku grup) np. 8-kratowej, a gdy takiej nie znajdziemy to 4-

2

kratowej itd. Wybrane symbole leżące poza wydzielonymi grupami łączy się w
mniejsze grupy z możliwością wykorzystania kratek już wcześniej użytych w innej
grupie (jeśli pomoże to w uzyskaniu grupy o większej liczbie elementów). Symbole
nie dające się pogrupować zaznaczamy jako grupy jednoelementowe
(„jednokratkowe”).
3. Jeżeli istnieją w tablicy grupy, których składowe należą już do innych grup taką grupę
usuwamy w celu uzyskania najprostszej postaci funkcji (pozostawiamy jedynie grupy
niezbędne).
4. Gdy istnieje większa liczba możliwości połączeń w grupy to wybieramy tą, która
będzie najprostsza (będzie uzależniona od minimalnej liczby zmiennych
wejściowych).
5. Liczba pól wchodzących w skład grupy musi być potęgą liczby dwa (2

n

gdzie n to

liczba naturalna). W przeciwnym razie nie można opisać danej grupy za pomocą
jednego iloczynu (bądź sumy - gdy zakreślamy zera).
6. Każde dwa łączone pola muszą być swoimi geometrycznymi sąsiadami (musza być
rozdzielone od siebie linią podziału kratek lub krawędzią tablicy). Inaczej wygląda to
w przypadku tablic większej ilości zmiennych gdzie można łączyć nie tylko takie pola.
Wtedy obowiązuje zasada, że dwa łączone elementy musza się różnić co najwyżej
jednym bitem w kodzie Gray’a (kod dwójkowy, który charakteryzuje się tym, że dwa
kolejne słowa kodowe różnią się tylko stanem jednego bitu).
7. Łączone pola muszą być prostokątami (lub w szczególności kwadratami – muszą
posiadać co najmniej jedną oś symetrii).
8. W przypadku gdy funkcja jest nie w pełni określona (dla pewnych wartości przyjmuje
wartości dowolne) postępujemy podobnie pamiętając, iż znaki nieokreśloności
możemy łączyć z zerami lub jedynkami.

Metoda tablic Karnaugh jest przydatna dla funkcji logicznych nie więcej niż 5-6
zmiennych.

Zadanie 1
Zaprojektuj dwuwejściowy układ logiczny realizujący działanie określone następującą
tabelą prawdy.

p

q

Y

0

0

1

0

1

1

1

0

0

1

1

1

a)

Według tabeli prawdy.

Y = (~p AND ~q) OR (~p AND q) OR (p AND q)

3

b)

Metoda tabeli Karnaugha.

Wynik: Y = q OR ~p

Opis: Grupuję jedynki. Powstają dwie grupy. Z grupy pierwszej (czerwonej) otrzymuję
„q”, ponieważ nie ulega on zmianie i ma wartość 1. Z grupy drugiej (niebieskiej) uzyskuję
„~p” gdyż nie zmienia się i ma wartość 0.


Zadanie 2
Zaprojektuj dwuwejściowy układ logiczny realizujący działanie określone następującą
tabelą prawdy:

p

q

Y

0

0

1

0

1

1

1

0

0

1

1

0

Metoda tabeli Karnaugha

.

Wynik: Y = ~p

p \ q

0

1

0

1

1

1

0

1

p \ q

1

0

1

1

0

0

1

0

4

Opis: Grupuję jedynkami. Otrzymuję jedną grupę, z której otrzymuję „~p”, ponieważ „p”
nie zmienia swojej wartości, która wynosi 0.


Zadanie 3
Zbuduj trzywejściowy układ, który przyjmuje wartość 1 wówczas, gdy co najmniej dwa
spośród wejść przyjmują wartość jeden.

p

q

r

Y

0

0

0

0

0

0

1

0

0

1

0

0

0

1

1

1

1

0

0

0

1

0

1

1

1

1

0

1

1

1

1

1

Metoda tabeli Karnaugha.

Wynik: Y = (q AND p) OR (q AND r) OR (p AND r)

Opis: Grupuję jedynkami, dzięki czemu otrzymuję 3 grupy. Z pierwszej (różowej) grupy
uzyskuję „q AND r”, ponieważ „q” i „r” nie ulegają zmianie i mają wartość 1, z drugiej
(czerwonej) grupy otrzymuję „q AND r” – nie zmieniają się, wartość 1. Z ostatniej
trzeciej (niebieskiej) grupy otrzymuję „p AND r” z tego samego powodu co w dwóch
poprzednich grupach.

p \ qr

00 01 11 10

0

0

0

0

1

0

1

1

1

1

5

Zadanie 4
Zaprojektuj trzywejściowy układ logiczny realizujący działanie określone następującą
tabelą prawdy:

p

q

r

Y

0

0

0

1

0

0

1

0

0

1

0

0

0

1

1

1

1

0

0

0

1

0

1

1

1

1

0

0

1

1

1

0

Metoda tabeli Karnaugha.

Wynik: Y = (~q OR r) AND (~p OR r) AND (~p OR ~q) AND (p OR q OR ~r)

Opis: Grupuję zerami. Otrzymuję cztery grupy. Z pierwszej (czerwonej) grupy uzyskuję
„~q OR r”, gdyż nie zmieniają się, „q” ma wartość „1” stąd negacja, a „r” wartość 0.
Z drugiej (niebieskiej) grupy dostaję „~p OR r” – „p” ma wartość 1, a „r” wartość 0. W
trzeciej (różowej) grupie zmianie nie ulegają dwie zmienne „p” i „q”, obie mają wartość 1.
Natomiast w ostatniej grupie żadna ze zmiennych nie zmienia się – „p” i „q” mają
wartość 0, a „r” wartość 1.

Zadanie 5
Zaprojektuj trzywejściowy układ logiczny realizujący działanie określone następującą
tabelą prawdy:

p \ qr

00 10 11

0

1

1

1

0

1

0

0

0

0

6

p

q

r

Y

0

0

0

0

0

0

1

1

0

1

0

1

0

1

1

1

1

0

0

0

1

0

1

1

1

1

0

1

1

1

1

0

Metoda tabeli Karnaugha.

Wynik: F = (~q AND r) OR (q AND ~r) OR (~p AND q)



















Opis: Grupuję jedynkami w wyniku, czego uzyskuję trzy grupy. W pierwszej (czerwonej)
grupie nie zmieniają się zmiennej „q” i „r” – pierwsza ma wartość 0, druga wartość 1. Z
drugiej grupy mam negację „r” (wartość 0) i „q”. W ostatniej (różowej) grupie nie
zmienia się „p” (wartość 0) i „q” (wartość 1).

Zadanie 6
Zaprojektuj trzywejściowy układ logiczny realizujący działanie określone następującą
tabelą prawdy:

p \ qr

00 01

0

0

1

1

1

1

0

1

1

0

10

11

7

p

q

r

Y

0

0

0

0

0

0

1

0

0

1

0

0

0

1

1

0

1

0

0

0

1

0

1

0

1

1

0

1

1

1

1

1

Metoda tabeli Karnaugha.

Wynik: F = p AND q

Opis: Grupuję jedynkami. Otrzymuję jedną grupę, gdzie nie zmienia się “p” i “q” – mają
one wartość 1. Stąd „p AND q”.


Wnioski:
Najwygodniejszą metodą minimalizacji funkcji niedużej liczby zmiennych (maksymalnie 6
zmiennych) jest skorzystanie z tablicy Karnaugha. Dzięki temu, że opis wartości
zmiennych w tablicy Karnaugha dokonany jest w kodzie Graya, ciągi wartości zmiennych
opisujących klatki tablicy leżące obok siebie, różnią się tylko na jednej pozycji, czyli
odpowiednie pełne iloczyny (sumy) są sąsiednie. Za pomocą tabeli Karnaugha możliwe
jest szybkie znalezienie odpowiedniej formuły opisującej układ. Rzadko kiedy się zdarza
aby formuła odczytana z tablic była optymalna. Podczas tworzenia tabeli ważnym jest
odpowiednie zakreślanie grup, tak aby było każda z nich była maksymalnie duża, a
zarazem liczba grup była jak najmniejsza.
Tworzenie grup zawierających w sobie inne grupy jest bezcelowe. W zależności od układu
należy rozważyć użycie postaci dysjunkcyjnej lub koniunkcyjnej, zależności od tego, która
da prostszy (bardziej optymalny) układ.

p \ qr

00 10 11

0

0

1

0

1

0

1

0

0

0

01