3813573797

7

4 KRATY I ALGEBRY BOOLE’A

Lemat 4.41. Relacja = określona na zbiorze T_n następująco:

(p = q) :<*=> (p = q jest równością spełnioną we wszystkich algebrach Boole’a) jest kongruencją algebry T_n .

Stwierdzenie 4.42. Algebra T_n/ = jest algebrą Boole’a.

Twierdzenie 4.43. Niechp(y\,... ,yk) będzie termem Boole’owskim o zmiennych yi, ■ ■ ■ ,yk £ {xi, • ■ •,x_n} dla 1 < k < n. Wtedy istnieje taka dodatnia liczba naturalna s, że

0)    p{yi,--,Vk) =    + .. . + x‘₁-¹

jest równością spełnioną przez wszystkie algebry Boole’a. Przy tym, Sij G

{0,1}, xP = Xj, jeśli £ij = 1 oraz xP = x'j, jeśli £ij = 0.    ■

Wyrażenie po prawej stronie (*) nazywamy dysjunktywno-normalną postacią termu p(yi, ■ ■ ■, yk)- Każdy (różny od zera) element algebry ilorazowej T_nf = można reprezentować przez term w postaci dyzjunktywno-normalnej.

Przykład 4.44. Postać dysjunktywno-normalną termu xy' w T3 można otrzymać następująco:

xy' = xy'(z + z') = xy'z + xy'z'.    ■

Twierdzenie 4.45. Niech p,q G T_n. Następujące warunki są równoważne.

(a)    Równość p = q jest spełniona w każdej algebrze Boole ’a.

(b)    Termy p i q mają te same postacie dysjunktywno-normalne.

(c)    Równość p = q jest spełniona w 2-elementowej algebrze Boole ’a 2.    ■

Algebrę Boole’a F nazywamy wolną w klasie wszystkich algebr Boole’a, jeśli istnieje w niej taki zbiór X generatorów, że każde przekształcenie h :

X —> B, gdzie B jest zbiorem elementów dowolnej algebry Boole’a, może być rozszerzone do homomorfizmu algebr Boole’a h : F —> B. Mówimy, że zbiór X jest zbiorem generatorów wolnych oraz, że F jest wolna nad zbiorem X. Algebra F jest wyznaczona jednoznacznie przez moc zbioru X.

Twierdzenie 4.46. Algebra T_n/ = jest wolną algebrą Boole’a nad n-ele-mentowym zbiorem generatorów wolnych, ponadto

T_n/= a 2²".    ■

Przykład 4.47. Cztero-elementowa algebra Boole’a jest wolną algebrą Boole’a o jednym generatorze wolnym.