F1-17 Algebra Boole'a 1

F1-17

Algebra Boole’a 1

• Algebra: układ przedmiotów < A, f 1, f 2, …, fn >

A – niepusty zbiór

f 1, f 2, …, fn – 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 =

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)

F1-17