3813573796

6

4 KRATY I ALGEBRY BOOLE’A

Definicja 4.312. Algebra (B, +, •/ , 0,1) jest algebrą Boole’a, jeśli (B, +, •, 0,1) jest kratą Boole’a i dla każdego x G B, x' jest uzupełnieniem x.

Twierdzenie 4.313. (o reprezentacji dla skończonych algebr Boole’a)

Niech B będzie skończoną algebrą Boole’a. Przekształcenie

h : B P(A(B)); a ► {x G A(B) \ x < a} jest izomorfizmem algebr Boole’a.    m

Twierdzenie 4.314. Każda algebra Boole’a jest izomorficzna z pewną algebrą Boole ’a zbiorów.    ■

4.4 Wolne algebry Boole’a

Niech X = {rei,..., x_n} będzie niepustym zbiorem zmiennych. Zbiór T_n termów Boole ’owskich nad zbiorem X określamy następująco:

(a)    0,1 e T_n,

(b)    jeśli x £ X, to x E T_n,

(c)    jeśli p,q £ T_n, to również p + q € T_n, p ■ q € T_n, p' € T_n,

(d)    każdy term p(yi, ■. ■ ,yk) G T_n o zmiennych yi,...,yk € X można zbudować w skończonej liczbie kroków stosując (c).

W zbiorze T_n określamy operacje typu operacji algebr Boole’a: p+T_nq-=p + q, p-T_nq-=p-q, p'_Tn ■= p'-Algebrę (T_n, +, •/ , 0,1) nazywamy algebrą termów Boole ’owskich nad zbiorem X = {Xi,.

Każdy term Boole’owski p(x i,..., x_n) o zmiennych x\,...,x_n wyznacza w każdej algebrze Boole’a B funkcję Boole ’owską

f_p : Bⁿ —> B; (a\,... ,a_n) i—> p(ai,... ,u_n)-

Mówimy, że para (p, q) termów Boole’owskich tworzy równość spełnioną w algebrze Boole’a B, i piszemy wtedy p = q, jeśli w algebrze Boole’a B zachodzi f_p = f_q, tzn. jeśli przy każdym podstawieniu za zmienne w p i q dowolnych elementów algebry B otrzymamy równość.

Rozważymy algebrę (T_n, +, • / , 0,1) termów Boole’owskich nad zbiorem X = {24,... ,x_n}.