F1-17
© J. Kalisz, WAT 2007
Algebra Boole’a 1
•
Algebra:
układ przedmiotów
< A
, f
1
, f
2
, …, f
n
>
A
– niepusty zbiór
f
1
, f
2
, …, f
n
– m-argumentowe operacje w A
m
= 2 : operacja
binarna
, np. sumowanie zbiorów
m
= 1 : operacja
unarna
, np. dopełnienie zbioru
m
= 0 :
stały element
w
A
•
Algebra Boole’a sygnałów binarnych
:
< B
, +,
⋅, ¯ >
gdzie
B
= {0,1}
+
- operacja dodawania
logicznego
, np. a + b
⋅ - operacja mnożenia
logicznego
, np. a
⋅b, ab
¯ - operacja negacji
logicznej
, np.
a
(lub /a lub a')
•
Reguły algebry Boole’a
dla zmiennych boolowskich
1. x + x = x,
x
⋅x = x
(idempotentność)
2. x + y = y + x,
x
⋅y = y⋅x
(przemienność)
3. x + (y + z) = (x + y) + z,
(łączność)
x
⋅(y⋅z) = (x⋅y)⋅z
4. x + (y
⋅z) = (x + y) ⋅(x + z), (rozdzielność)
x
⋅(y + z) = (x⋅y) + (x⋅z)
5. x + (x
⋅y) = x,
x
⋅(x + y) = x (pochłanianie)
6. x + 0 = x, x
⋅1 = x
(własności stałych)
7. x + 1 = 1,
x
⋅0 = 0
(c.d. własności stałych)
8. x + x =
1,
x
⋅ x = 0
(własności negacji)
9. x = x (podwójna
negacja)
10.
+ = ⋅
x
y
x y
,
⋅
x y
= x +
y
(prawa De Morgana)
Zasada dualności
: f(X, +,
⋅, 0, 1) ↔ f(X, ⋅, +, 1,0)
