Technika cyfrowa
Wykład IV
Minimalizacja funkcji logicznych
Piotr Kawalec Wykład IV - 1
Technika cyfrowa
Plan wykładu
Podstawowe pojęcia
Postacie normalne funkcji logicznych
Minimalizacja metodą przekształceń
wyrażeń logicznych
Minimalizacja funkcji logicznych
metodą tablic Karnaugh a
Piotr Kawalec Wykład IV - 2
Technika cyfrowa
Minimalizacja funkcji logicznych
Def. Minimalizacją formalną funkcji przełączających
nazywamy proces poszukiwania takiej ich postaci
aby funkcje te, odwzorowując zadane zależności
logiczne, zawierały najmniejszą liczbę literałów
Literał - afirmacja lub negacja zmiennej
Elementarny iloczyn - iloczyn dowolnej liczby
różnych literałów danej funkcji
Elementarna suma - suma dowolnej liczby różnych
literałów danej funkcji
Piotr Kawalec Wykład IV - 3
Technika cyfrowa
Podstawowe pojęcia
Postacią normalną sumy (PNS) - nazywamy sumę
różnych elementarnych iloczynów
Postacią normalną iloczynu (PNI) - nazywamy
iloczyn różnych elementarnych sum
Implikantem - danej funkcji przełączającej nazywamy
funkcję tych samych argumentów o następującej
własności: dla wszystkich zespołów wartości
argumentów dla których implikant jest równy
jedności, również dana funkcja jest równa jedności
Piotr Kawalec Wykład IV - 4
Technika cyfrowa
Podstawowe pojęcia
Implicentem - danej funkcji przełączającej nazywamy
funkcję tych samych argumentów o następującej
własności: dla wszystkich zespołów wartości
argumentów dla których implicent jest równy zeru,
również dana funkcja jest równa zeru
Prosty implikant (implicent)- jest to implikant
(implicent) będący iloczynem (sumą) elementarnym,
który zmniejszony o dowolny literał przestaje być
implikantem (implicentem)
Piotr Kawalec Wykład IV - 5
Technika cyfrowa
Podstawowe pojęcia
Minimalizacja funkcji logicznej polega na
przedstawieniu jej w postaci normalnej, zawierającej
możliwie najmniejszą liczbę literałów.
Można wykazać że minimalną będzie postać funkcji
zawierająca wyłącznie proste implikanty (implicenty)
funkcji
Suma (iloczyn) wszystkich prostych implikantów
(implicentów) danej funkcji nazywana jest jej postacią
skróconą
Piotr Kawalec Wykład IV - 6
Technika cyfrowa
Podstawowe pojęcia
Minimalne postacie normalne uzyskuje się z postaci
skróconych przez rugowanie zbędnych prostych
implikantów (implicentów)
Wszystkie metody minimalizacji wykorzystują reguły
sklejania Ax + Ax = A
(B + x)(B + x) = B
Dwa elementarne iloczyny (elementarne sumy) można
skleić, gdy mają taką samą ilość literałów i różnią się
negacją jednego literału). Elementarny iloczyn
(elementarna suma) może być sklejany wielokrotnie
Piotr Kawalec Wykład IV - 7
Technika cyfrowa
Minimalizacja metodą przekształcania
wyrażeń (minimalizacja analityczna)
Przykład - zminimalizować funkcję
y= f(x3, x , x1) = Ł(0,2,6,7)
2
Wady metody:
pracochłonność
uzyskana postać może nie być postacią
minimalną
Piotr Kawalec Wykład IV - 8
Technika cyfrowa
Minimalizacja metodą tablic Karnaugh a
Metoda graficzna maksymalnie do 6 zmiennych
Opis wartości zmiennych w tablicy w kodzie Gray a !!!
Proste implikanty (implicenty) na tablicy wyznacza się
łącząc ze sobą sąsiednie jedynki (zera) w grupy
zawierające 2k klatek
Grupy obejmujące jedynki funkcji (proste implikanty)
opisywane są iloczynem elementarnym literałów nie
zmieniających się w ramach grupy
Piotr Kawalec Wykład IV - 9
Technika cyfrowa
Minimalizacja metodą tablic Karnaugh a
Literały o wartości 1 wchodzą do iloczynu
elementarnego w postaci afirmacji, natomiast literały
o wartości 0 - w postaci negacji
Grupy obejmujące zera funkcji (proste implicenty)
opisywane są sumą elementarną literałów nie
zmieniających się w ramach grupy
Literały o wartości 1 wchodzą do sumy elementarnej
w postaci negacji, natomiast literały o wartości 0 -
w postaci afirmacji
Piotr Kawalec Wykład IV - 10
Technika cyfrowa
Minimalizacja metodą tablic Karnaugh a
Zasady doboru grup:
należy utworzyć grupy obejmujące wszystkie
jedynki lub wszystkie zera funkcji
ilość utworzonych grup powinna być jak
najmniejsza, aby liczba implikantów
(implicentów) była jak najmniejsza
Piotr Kawalec Wykład IV - 11
Technika cyfrowa
Minimalizacja metodą tablic Karnaugh a
Zasady doboru grup:
ilość jedynek (zer) w grupie powinna być jak
największa (2k) aby odpowiadające im
implikanty (implicenty) zawierały jak
najmniejszą liczbę literałów
każdą jedynkę (zero) można umieścić w
dowolnej liczbie grup, jeśli pozwoli to na
powiększenie tych grup
klatki zawierające wartości nieokreślone
funkcji mogą wchodzić do dowolnych grup
Piotr Kawalec Wykład IV - 12
Technika cyfrowa
Minimalizacja metodą tablic Karnaugh a
Przykłady minimalizacji funkcji
funkcja trzech zmiennych
y= f(x3, x2, x1) = Ł(3,4,5,6,7)
funkcja czterech zmiennych
y= f(x4, x3, x , x1) = Ł[0,1,5,8,9,10,13,15,(2)]
2
funkcja pięciu zmiennych
Piotr Kawalec Wykład IV - 13
Technika cyfrowa
Minimalizacja metodą tablic Karnaugh a
Przykłady minimalizacji funkcji
funkcja pięciu zmiennych
Wyznaczyć minimalną postać funkcji
realizowanej przez układ wykrywający wśród
liczb z zakresu [0 - 21] liczby podzielne przez 3
lub 4
Piotr Kawalec Wykład IV - 14