2014-01-10
1
1
Architektura Systemów Komputerowych
Wykład 2
Algebra Boole’a, operatory i bramki logiczne.
Logika Boole’a
działania Boolowskie to działania na obiektach, które
mogą przyjmować tylko dwie wartości: PRAWDA lub
FAŁSZ (1 i 0). Ponieważ budowa komputera oparta jest
głównie na systemie binarnym, algebra Boole’a jest
naturalnym sposobem przetwarzania informacji cyfrowej.
wyrażenie boolowskie składa się z jednej lub więcej
zmiennych (argumentów) oraz operatorów
funkcja boolowska składa się z danych wejściowych a
wynik funkcji przyjmuje jeden z dwu stanów: 0 lub 1
Operatory logiczne - proste
AND (i) – koniunkcja, iloczyn logiczny
OR (lub) – alternatywa lub suma logiczna
NOT (nie) – negacja
Operatory boolowskie można charakteryzować
przy pomocy tablicy prawdy lub przy pomocy
działania na dwóch zbiorach
X
Y
Operator AND, iloczyn logiczny
x
y
xy
1
1
1
1
0
0
0
1
0
0
0
0
Obie zmienne muszą być prawdziwe aby
zaistniała prawda
xy
y
x
y
x
y
x
∧
∧
∩
•
X
Y
2014-01-10
2
Operator OR, suma logiczna
Przynajmniej jeden argument musi być
prawdziwy aby zaistniała prawda
x
y
x+y
1
1
1
1
0
1
0
1
1
0
0
0
xy
y
x
y
x
y
x
∨
∨
∪
+
X
Y
Operator NOT - zaprzeczenie
jest to przeciwieństwo
x
NOT x
1
0
0
1
x
x
¬
X
Operatory złożone
XOR - różnica symetryczna, suma rozłączna
NAND – zaprzeczenie iloczynu
NOR – zaprzeczenie sumy
XNOR – zaprzeczenie różnicy symetrycznej
Operator XOR
x
y
xy
1
1
0
1
0
1
0
1
1
0
0
0
X
Y
jeżeli oba argumenty są takie same to wynikiem jest
fałsz
y
x
⊕
2014-01-10
3
Operator NAND
Oznacza działanie: NOT x
•y
NOT AND
x
y
xy
NOT xy
1
1
1
0
1
0
0
1
0
1
0
1
0
0
0
1
X
Y
xy
y
x
y
x
y
x
∨
∨
∪
+
Operator NOR
Oznacza działanie: NOT x
+y
NOT OR
x
y
x+y
NOT x+y
1
1
1
0
1
0
1
0
0
1
1
0
0
0
0
1
xy
y
x
y
x
y
x
∨
∨
∪
+
X
Y
Operator XNOR
Zarówno X i Y ale NIE X lub Y
jeżeli oba argumenty są takie same to wynikiem jest
prawda
x
y
x+y
NOT x+y
1
1
1
1
1
0
1
0
0
1
1
0
0
0
0
1
X
Y
y
x
⊕
Zalety stosowania operatorów złożonych
są szybsze niż stosowanie kilku operatorów prostych
operatory prostsze i złożone wyczerpują cały zakres
możliwych stanów wyjściowych dla dwóch zmiennych o
dowolnych wartościach
x
y
AND
OR
NOT
XOR
NAND NOR
XNOR
1
1
1
1
0
1
0
0
0
1
0
0
1
0
0
1
0
1
0
1
0
1
1
0
1
0
1
0
0
0
0
1
1
1
1
0
2014-01-10
4
Aksjomaty algebry Boole’a i prawa de Morgana
1. Przemienność
2. Łączność
3. Rozdzielczość
4. Tożsamość
5. Komplementarność
A
B
B
A
A
B
B
A
+
=
+
⋅
=
⋅
C)
(B
A
C
B)
(A
C)
(B
A
C
B)
(A
+
+
=
+
+
⋅
⋅
=
⋅
⋅
BC
A
C)
B)(A
(A
C
A
B
A
C)
A(B
+
=
+
+
⋅
+
⋅
=
+
A
A
A
A
A
A
1
1
A
A
1
A
A
0
A
0
0
A
=
+
=
⋅
=
+
=
⋅
=
+
=
⋅
1
A
A
0
A
A
=
+
=
⋅
B
A
B
A
B
A
B
A
+
=
⋅
⋅
=
+
Prawa de Morgana
FUNKCJE BOOLE’OWSKIE
Istnieją cztery sposoby przedstawienia tych funkcji:
• tablica prawdy
• postać kanoniczna funkcji
• dziesiętny zapis funkcji
• mapa Karnaugha
)
x
x
)(x
x
x
x
)(
x
x
(x
y
lub
x
x
x
x
x
x
x
x
x
x
x
x
y
2
1
0
2
1
0
2
1
0
2
1
0
2
1
0
2
1
0
2
1
0
+
+
+
+
+
+
=
+
+
+
=
(
)
(
)
∏
∑
=
=
0,4,3
y
lub
1,2,5,6,7
y
X
0
X
1
X
2
f
0
0
0
0
0
1
1
0
0
1
2
0
1
0
1
3
1
1
0
0
4
0
0
1
0
5
1
0
1
1
6
0
1
1
1
7
1
1
1
1
∏
∑
- wskazanie na postać alternatywną
- wskazanie na postać koniunkcyjną
1.
2.
3.
4.
X
2
X
0
X
1
0
1
0
0
0
0
0
1
1
1
1
1
0
1
1
0
1
1
Algebra Boole'a
Algebra Boole'a jest to struktura matematyczna złożona z
uniwersum X, trzech funkcji: działań binarnych +, * i
działania unarnego ~ oraz wyróżnionych elementów 0, 1
spełniających następujące aksjomaty:
Podstawowe aksjomaty Algebry
Boola
Tożsamość
koniunkcja
alternatywa
el. neutralny
1x=x
0+x=x
własność 0 i 1
0x=0
1+x=1
idempotentność
xx=x
x+x=x
uzupełnienie
x¬x=0
x+ ¬x=1
przemienność
xy=yx
x+y=y+x
podwójne zaprzeczenie
¬ ¬ x=x
prawo De Morgana
¬(xy)= ¬x+ ¬y
¬(x+y)= ¬(xy)
Łączność
(xy)z=x(yz)
x+(y+z)=(x+y)+z
Rozdzielność
x+yz=(x+y)(x+y) x(y+z)=xy+xz
Adsorpcja
x(x+y)=x
x+xy=x
UWAGA:
¬(xy) ≠ ¬x¬y
2014-01-10
5
przykłady algebry Boola
Algebra zbiorów. X jest w tym przypadku jakimś ciałem zbiorów.
Działanie + jest to suma zbiorów, * - przekrój zbiorów, a ~ -
dopełnienie. 0 to zbiór pusty, a 1 - cały zbiór X
Rachunek zdań. X to w tym przypadku zbiór formuł logicznych,
działanie * to koniunkcja, + - alternatywa, zaś ~ - negacja. Wreszcie
1 to formuła zawsze prawdziwa, a 0 - zawsze fałszywa (tak
naprawdę elementami X nie są same formuły logiczne, a klasy
abstrakcji ze względu na relację: formuła f jest równoważna formule
g, jeśli dla tych samych podstawień zmiennych ich wartość logiczna
jest taka sama).
Podstawowe działania logiczne i
ich własności
Bramki logiczne
element konstrukcyjny maszyn i mechanizmów (dziś zazwyczaj: układ
scalony, choć podobne funkcje można zrealizować również za pomocą
innych rozwiązań technicznych, np. hydrauliki czy pneumatyki), realizujący
fizycznie pewną prostą funkcję logiczną, której argumenty (zmienne
logiczne) oraz sama funkcja mogą przybierać jedną z dwóch wartości, np. 0
lub 1
Podstawowymi elementami logicznymi, stosowanymi powszechnie w
budowie układów logicznych, są elementy realizujące funkcje logiczne:
sumy (alternatywy), iloczynu (koniunkcji) i negacji. Są to odpowiednio
bramki OR, AND i NOT. Za pomocą dwóch takich bramek (np. OR i NOT
lub AND i NOT) można zbudować układ, realizujący dowolną funkcję
logiczną.
Wzory bramek
x
y
xy
x
y
x+y
x
y
x+y
x
x
x
y
xy
x
y
x+y
x
y
x+y
AND
OR
NOT
NAND
NOR
XOR
XNOR
2014-01-10
6
Zestawienie układów logicznych
Układy logiczne
Układy logiczne można podzielić (w zależności od
przyjętego kryterium) na:
•układy kombinacyjne
•układy sekwencyjne
Układ kombinacyjny to taki układ cyfrowy, w którym stan
wejść jednoznacznie określa stan wyjść układu.
Układem sekwencyjnym nazywamy taki układ cyfrowy, w
którym stan wyjść zależy od stanu wejść oraz od
poprzednich stanów układu.
Układy logiczne
•układy asynchroniczne
•układy synchroniczne
Układem asynchronicznym nazywamy taki układ cyfrowy,
dla którego w dowolnym momencie jego działania stan
wejść oddziaływuje na stan wyjść.
Układem synchronicznym nazywamy taki układ cyfrowy,
dla którego stan wejść wpływa na stan wyjść w pewnych
określonych odcinkach czasu zwanych czasem czynnym,
natomiast w pozostałych odcinkach czasu zwanych
czasem martwym stan wejść nie wpływa na stan wyjść..
Podział układów logicznych
Układy kombinacyjne:
– sumatory
– komparatory
– dekodery, kodery, transkodery
– multipleksery, demultipleksery
– .....
• układy matrycowe
• ........
• układy zbudowane z bramek
• bloki kombinacyjne
Układy sekwencyjne:
• przerzutniki
• rejestry
• liczniki
• .....
2014-01-10
7
Informacja cyfrowa
Zmienna binarna – zmienna o wartościach 1 i 0
Wektor informacji cyfrowej (w.i.c.) – wektor o
elementach binarnych, np.: 0111
Informacja cyfrowa – informacja przedstawiona
za pomocą ciągu wektorów informacji cyfrowej
Adresowanie wektora informacji cyfrowej-
wzajemnie jednoznaczne przypisanie każdemu
wektorowi innego w.i.c. zwanego adresem
Reprezentacja czasowa w.i.c.
Bitowo-równoległa – wszystkie bity wektor są dostępne
jednocześnie (na równoległych liniach magistrali lub w
rejestrze)
Bitowo-szeregowa – poszczególne bity pojawiają się na
tej samej linii lub w tym samym przerzutniku, w kolejnych
„okienkach czasu”
Przerzutniki
Posiada co najmniej dwa wejścia i z reguły dwa wyjścia
we
jś
c
ia
pr
ogr
a
m
uj
ą
ce
we
jś
ci
a
infor
m
a
c
yjne
wejście
zegarowe
wy
jś
ci
a
Przerzutniki są podstawowymi elementami układów
sekwencyjnych, których zasadniczym zadaniem jest
pamiętanie jednego bitu informacji.