Technika cyfrowa
Wykład III
Logika układów cyfrowych
Funkcje logiczne
Piotr Kawalec Wykład III - 1
Technika cyfrowa
Plan wykładu
Algebra Boole a
Aksjomaty algebry Boole a
Twierdzenia algebry Boole a
Funkcje i formuły boolowskie
Systemy funkcjonalnie pełne
Kanoniczne postacie funkcji logicznych
Piotr Kawalec Wykład III - 2
Technika cyfrowa
LOGIKA UKA
ADÓW CYFROWYCH
Algebra Boole a
Aksjomatyczna definicja algebry Boole a
Algebrą Boole a nazywamy system algebraiczny
< B, +," ,  , o, i >
w którym:
B - jest zbiorem;
+, " - operacje dwuargumentowe określone w zbiorze B;
 - operacja jednoargumentowa określona w zbiorze B;
o oraz i - wyróżnione elementy zbioru B
Piotr Kawalec Wykład III - 3
Technika cyfrowa
Aksjomaty algebry Boole a
'" a,b,c " B
1
a + b " B a " b " B
2
a + b = b + a a " b = b " a
3
a" (b + c) = a" b + a" c a + b" c = (a + b)" (a + c)
a + o = a a " i = a
4
'" a " B (" a " B
5
a + a = i a " a = o
Piotr Kawalec Wykład III - 4
Technika cyfrowa
Twierdzenia algebry Boole a
a" (b" c) = (a" b)" c
1
a + (b + c) = (a + b) + c
2
a + a " b = a
a" (a + b) = a
3
a" (b + c) = a" b + a" c
a + b" c = (a + b)" (a + c)
4
a + a = a
a" a= a
5
a + i = i
a" o = o
6
a + b = a " b
a" b = a + b
7
o = i
i = o
8
a = a
Piotr Kawalec Wykład III - 5
Technika cyfrowa
Dwuelementowa algebra Boole a
Zbiór B { 0, 1} ; elementy wyróżnione o = 0; i = 1
Operacje +, " ,  , definiujemy następująco:
a b a + b a " b a
0 0 0 0 1
0 1 1 0 1
1 0 1 0 0
1 1 1 1 0
+ - suma logiczna; " - iloczyn logiczny;  - negacja
Piotr Kawalec Wykład III - 6
Technika cyfrowa
Dowodzenie twierdzeń w algebrze Boole a
W dwuelementowej algebrze Boole a twierdzenia
mogą być dowodzone
na podstawie aksjomatów;
metodą zero - jedynkową L = P
Przykład Udowodnić twierdzenie a " a= a
4
wykorzystując aksjomaty
a " a = a" a + 0 = a" a + a" a =a" (a + a ) = a " 1= a
4 5 3 5 4
metodą zero - jedynkową
a aa
0 0
1 1
Piotr Kawalec Wykład III - 7
Technika cyfrowa
Funkcje i formuły boolowskie
Def. Funkcją boolowską f n zmiennych binarnych
x1, . . . xn nazywamy odwzorowanie zbioru
{0,1}x. . . x{0,1} = {0,1}n w zbiór {0,1}
Można udowodnić że istnieje
n
2
2
różnych funkcji logicznych n zmiennych
dla n=1 istnieją 4 rożne funkcje, dla n=2 jest 16 funkcji
Piotr Kawalec Wykład III - 8
Technika cyfrowa
Funkcje logiczne dwóch zmiennych
x1
0 0 1 1 Zapis funkcji Uwagi
Nazwa funkcji
x2
0 1 0 1
+, " 
stała 0
f0 f. zdegenerowana
0 0 0 0 0
f1 iloczyn log. (AND)
0 0 0 1 x1 x2
"
iloczyn z zakazem dla x2
f2
0 0 1 0
x1  x2 x1
= " x2
x1
zmienna f. częściowo zdegen.
f3 x1
0 0 1 1
iloczyn z zakazem dla x1
f4 0 1 0 0
x2  x1 x1
= " x2
f. częściowo zdegen.
x2
zmienna
f5 x2
0 1 0 1
albo, (ExOR) x1 x2 = x1x2 + x1x2
+
f6
0 1 1 0
suma log. (lub, OR) x1 + x2
f7
0 1 1 1
negacja sumy (NOR)
f8 x1 x2 = x1 + x2
1 0 0 0 �!
równoważność
f9 1 0 0 1
x1 x2 = x1x2 + x1x2
"
f. częściowo zdegen.
x2
f10 negacja (NOT) x2
1 0 1 0
x1 x2
implikacja przez
x2 x1 = x1 + x2
f11
1 0 1 1
x1
negacja (NOT) x1
f. częściowo zdegen.
f12
1 1 0 0
x2 x1
implikacja przez
f13 x1 x2 x1 + x2
1 1 0 1 =
f14 1 1 1 0 negacja iloczynu (NAND)
x1 / x2 x1
= " x2
stała 1 f. zdegenerowana
f15
1 1 1 1 1
Piotr Kawalec Wykład III - 9
Technika cyfrowa
Systemy funkcjonalnie pełne
Def. Zbiór operacji takich, że każda funkcja logiczna
może być przedstawiona przy pomocy argumentów
stałych 0 i 1 oraz tych operacji nazywamy
systemem funkcjonalnie pełnym (SFP)
Funkcje logiczne sumy, iloczynu i negacji tworzą
podstawowy system funkcjonalnie pełny
Sprawdzenie czy jakiś system jest SFP polega na
próbie wyrażenia przy pomocy badanych operatorów
operacji negacji, sumy i iloczynu
Piotr Kawalec Wykład III - 10
Technika cyfrowa
Systemy funkcjonalnie pełne
Spośród 16 funkcji dwóch zmiennych tylko dwie,
każda niezależnie tworzą system funkcjonalnie
pełny.
Są to funkcje:
NAND
NOR
Wykazać że funkcja NAND oraz NOR tworzy SFP
Piotr Kawalec Wykład III - 11
Technika cyfrowa
SYNTEZA UKA
ADÓW KOMBINACYJNYCH
Def. Syntezą układów kombinacyjnych nazywamy
zespół czynności, które na podstawie założeń
dotyczących działania układów doprowadzają
do schematu logicznego układu, przy czym
schemat ten powinien zawierać tylko elementy
przewidzianego typu i spełniać pewne
wymagania optymalności.
Piotr Kawalec Wykład III - 12
Technika cyfrowa
SYNTEZA UKA
ADÓW KOMBINACYJNYCH
y1
x1
.
.
Układ
.
.
.
.
kombinacyjny
xn ym
yi = fi(x1, . . . Xn)
Piotr Kawalec Wykład III - 13
Technika cyfrowa
Sposoby opisu działania układów
opis słowny
1. Zaprojektować układ o 3 wejściach i jednym wyjściu wykrywający
gdy na wejściu pojawi się nieparzysta liczba jedynek
2. Zaprojektować układ nadzorujący pracę 8 urządzeń. Układ ma
sygnalizować gdy żądanie obsługi zgłaszają urządzenia o adresach
0, 2,6,7
cechy opisu:
wyjściowa forma opisu;
nie nadaje się do analitycznych przekształceń
mało przejrzysty przy opisie złożonych
algorytmów działania układów
Piotr Kawalec Wykład III - 14
Technika cyfrowa
Sposoby opisu działania układów
wykresy czasowe
W postaci graficznej przedstawiają zależność
sygnałów wyjściowych od zmiennych wejściowych
cechy opisu:
wyjściowa forma opisu;
nie nadaje się do analitycznych przekształceń
stosowany zwykle przy zdejmowaniu
charakterystyk układów
Piotr Kawalec Wykład III - 15
Technika cyfrowa
Sposoby opisu działania układów
tablica wartości funkcji
Zawiera 2n wierszy i n plus m kolumn,
gdzie n - liczba zmiennych wejściowych,
m - liczba zmiennych wyjściowych.
cechy opisu:
podstawowa forma opisu układów
kombinacyjnych;
pozwala wyznaczyć analityczną postać funkcji
logicznych realizowanych przez układ.
Piotr Kawalec Wykład III - 16
Technika cyfrowa
Kanoniczne postacie funkcji logicznych
kanoniczna postać sumy (KPS)
2n -1
yi = fi(x1, . . . Xn) = Ł f(a) Ka
a= 0
kanoniczna postać iloczynu (KPI)
2n -1
yi = fi(x1, . . . Xn) =  (f(b) + Db)
b= 0
Piotr Kawalec Wykład III - 17
Technika cyfrowa
Wyznaczanie KPS i KPI z tablicy prawdy
kanoniczną postać sumy można otrzymać
bezpośrednio z tablicy wartości funkcji rozpatrując
tylko te wiersze dla których y=1, przy czym
zmienna o wartości 1 wchodzi do iloczynu w
postaci afirmacji, a zmienna o wartości 0 - w
postaci negacji
kanoniczną postać iloczynu można otrzymać
bezpośrednio z tablicy wartości funkcji rozpatrując
tylko te wiersze dla których y=0, przy czym
zmienna o wartości 1 wchodzi do sumy w postaci
negacji, a zmienna o wartości 0 - w postaci
afirmacji
Piotr Kawalec Wykład III - 18
Technika cyfrowa
Kanoniczne postacie funkcji logicznych
Postaci kanoniczne funkcji zwykle zapisuje
się jako zbiór dziesiętnych indeksów
poprzedzonych odpowiednim symbolem
Np. kanoniczne postacie funkcji zadanych słownie
będą następujące
1. y=Ł(1,2,4,7) y= (0,3,5,6)
2. y=Ł(0,2,6,7) y= (1,3,4,5)
Jeśli dla pewnych ciągów argumentów funkcja jest
nieokreślona, to odpowiadające im indeksy zapisuje
się w nawiasie w obu postaciach kanonicznych
funkcji
Piotr Kawalec Wykład III - 19