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 2m 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-

1

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 (2n 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)

2

b) Metoda tabeli Karnaugha.

p \ q

0

1

0

1

1

1

0

1

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.

p \ q

0

1

0

1

1

1

0

0

Wynik: Y = ~p

3

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.

p \ qr

00 01 11 10

0

0

0

1

0

1

0

1

1

1

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.

4

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.

p \ qr

00 10 11

0

1

0

1

0

1

0

0

0

1

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:

5

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.

p \ qr

00 01

11 10

0

0

1

1

1

1

0

1

0

1

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:

6

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.

p \ qr

00 10 11

01

0

0

0

0

0

1

0

1

1

0

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.

7