F1-17 Algebra Boole'a 1.pdf

F1-17

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}

+ - dodawanie logiczne , np. a + b (czyt. ‘ a plus b ’)

⋅ - mnożenie logiczne , np. a ⋅ b , ab (czyt. ‘ ab ’)

', ¯ , / - negacja logiczna , np. a' lub

lub / a (czyt. ‘nie a’)

• Reguły dualne 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 ( ł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)