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)

F1-17

© J. Kalisz, WAT 2007