Piotr Kawalec
Wykład III - 1
Wykład III
Logika układów cyfrowych
Synteza układów
kombinacyjnych
Technika cyfrowa
Piotr Kawalec
Wykład III - 1
Wykład III
Logika układów cyfrowych
Synteza układów
kombinacyjnych
Technika cyfrowa
Piotr Kawalec
Wykład III - 2
Technika cyfrowa
LOGIKA UKŁ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
a
+
b
B
a
+
b = b
+
a
a
•
(b
+
c) = a
•
b
+
a
•
c
a
+
o
= a
1
a
•
b
B
a
•
b
= b
•
a
a
+
b
•
c = (a
+
b)
•
(a
+
c)
a
•
i
= a
2
3
4
a
B
a
B
a
+
a =
i
a
•
a =
o
5
Piotr Kawalec
Wykład III - 4
Technika cyfrowa
Twierdzenia algebry Boole’a
a
+
(b
+
c) = (a
+
b)
+
c
a
+
a
•
b = a
a
•
(b
+
c) = a
•
b
+
a
•
c
a
+
a = a
a
+
i
=
i
a
+
b = a
•
b
o
=
i
1
a
•
(b
•
c) = (a
•
b)
•
c
a
•
(a
+
b)
= a
a
+
b
•
c = (a
+
b)
•
(a
+
c)
a
•
a
= a
a
•
o
=
o
a
•
b = a
+
b
i
=
o
2
3
4
5
6
7
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
wykorzystując aksjomaty
a
•
a = a
•
a
+
0
= a
•
a
+
a
•
a =a
•
(a
+
a ) = a
• 1
= a
metodą zero - jedynkową
a aa
0 0
1 1
4
4
5
3
5
4
Piotr Kawalec
Wykład III - 7
Technika cyfrowa
Funkcje i formuły boolowskie
Def.
Funkcją boolowską f
n
zmiennych
binarnych
x
1
, . . . x
n
nazywamy odwzorowanie zbioru
{0,1}x
. . .
x{0,1}
= {0,1}
n
w zbiór {0,1}
Można udowodnić że istnieje
2
różnych funkcji logicznych
n
zmiennych
dla n=1 istnieją 4 rożne funkcje, dla n=2 jest 16
funkcji
n
2
Piotr Kawalec
Wykład III - 8
Technika cyfrowa
Funkcje logiczne dwóch zmiennych
x
1
x
2
0 0 1 1
0 1 0 1
Nazwa funkcji
Zapis funkcji
+, –
Uwagi
f
0
0 0 0 0
stała 0
0
f. zdegenerowana
f
1
0 0 0 1
iloczyn log. (AND)
x
1
x
2
f
2
0 0 1 0
iloczyn z zakazem dla x
2
x
1
– x
2
= x
1
x
2
f
3
0 0 1 1
zmienna x
1
x
1
f. częściowo zdegen.
f
4
0 1 0 0
iloczyn z zakazem dla x
1
x
2
– x
1
= x
1
x
2
f
5
0 1 0 1
zmienna x
2
x
2
f. częściowo zdegen.
f
6
0 1 1 0
albo, (ExOR)
x
1
+ x
2
= x
1
x
2
+ x
1
x
2
f
7
0 1 1 1
suma log. (lub, OR)
x
1
+ x
2
f
8
1 0 0 0
negacja sumy (NOR)
x
1
x
2
= x
1
+ x
2
f
9
1 0 0 1
równoważność
x
1
x
2
= x
1
x
2
+ x
1
x
2
f
10
1 0 1 0
negacja x
2
(NOT)
x
2
f. częściowo zdegen.
f
11
1 0 1 1
implikacja x
1
przez x
2
x
2
x
1
= x
1
+ x
2
f
12
1 1 0 0
negacja x
1
(NOT)
x
1
f. częściowo zdegen.
f
13
1 1 0 1
implikacja x
2
przez x
1
x
1
x
2
=
x
1
+ x
2
f
14
1 1 1 0
negacja iloczynu (NAND)
x
1
/ x
2
= x
1
x
2
f
15
1 1 1 1
stała 1
1
f. zdegenerowana
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 UKŁ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 UKŁADÓW
KOMBINACYJNYCH
Układ
kombinacyjny
x
1
x
n
.
.
.
.
.
.
y
1
y
m
y
i
= f
i
(x
1
, . . . X
n
)
Piotr Kawalec
Wykład III -
13
Technika cyfrowa
Sposoby opisu działania układów
opis słowny
Zaprojektować układ o 3 wejściach i jednym
wyjściu wykrywający gdy na wejściu pojawi się
nieparzysta liczba jedynek
tablica wartości funkcji -
podstawowy
sposób
opisu układów kombinacyjnych
wykresy czasowe
Piotr Kawalec
Wykład III -
14
Technika cyfrowa
Kanoniczne postacie funkcji
logicznych
kanoniczna postać sumy
y
i
= f
i
(x
1
, . . . X
n
) =
f(a) K
a
kanoniczna postać iloczynu
y
i
= f
i
(x
1
, . . . X
n
) =
(
f(b) + D
b
)
2
n
-1
a= 0
2
n
-1
b= 0
Piotr Kawalec
Wykład III -
15
Technika cyfrowa
Kanoniczne postacie funkcji logicznych
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 -
16
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
y=(1,2,4,7)
y=(0,3,5,6)
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