Elementy algebr Boole'a

Struktura zbioru potęgowego jako źródło algebry Boole'a.

Niech U - będzie dowolnym ustalonym zbiorem (przestrzeni, uniwersum).Wiadomo nam, że:

Np. D_n={x∈N: ^x/_n}⊂N, gdzie n - ustalona liczba naturalna.

Ogólnie: Niech A_p={x∈U: P(x)}, czyli każda mająca sens własność P(x)

wyznacza pewien zbiór A_p. Ta własność zwana jest własnością wy- różniania i jest podstawowym aksjomatem logiki matematycznej.

Odwrotnie: Każdemu zbiorowi A odpowiada własność x∈A, czyli własność należenia elementu x do zbioru A, przynależności elementu do zbioru A

• Przypomnijmy także: 2^U={A: A⊂U} - to jest zbiór potęgowy, czyli zbiór wszystkich podzbiorów zbioru U. Poznaliśmy także twierdzenie:

Jeśli zbiór U ma n elementów, to zbiór 2^U ma 2ⁿ elementów.

Obecnie zdefiniujemy w zbiorze 2^U działania boolowskie, po z definiowaniu pojęć pomocniczych.

• Df: Jednoargumentowe (unarne) działanie na zbiorze A, to jest funkcja określona na zbiorze A i wartościach z tego zbioru.

Np. f(n)=n+1 dla n∈N, czyli funkcja „być następnikiem liczby naturalnej” jest działaniem unarnym w zbiorze N

A'={x∈U: x∉A} - czyli dopełnienie zbioru A do U (uzupełnienie zbioru A do zbioru U) jest działaniem unarnym w zbiorze 2^U.

• Def: Dwuargumentowe (binarne) działanie wewnętrzne na zbiorze A, to jest funkcja określona na zbiorze A×A i wartościach w zbiorze A.

Np. dodawanie (mnożenie) liczb naturalnych jest dwuargumentowym działaniem wewnętrznym w zbiorze N; suma mnogościowa (iloczyn mnogościowy) zbiorów A, B∈2^U jest dwuargumentowym działaniem wewnętrznym (krótko: działaniem binarnym)w zbiorze 2^U

• Def: Określone na podzbiorach zbioru U dwa podstawowe działania binarne: ∪, ∩ oraz działanie unarne zwane dopełnieniem zbioru będziemy nazywać działaniami boolowskimi w zbiorze 2^U. Można udowodnić wówczas następujące twierdzenie:

Działania boolowskie: ∪, ∩, ` na podzbiorach ustalonego zbioru U mają następujące elementarne własności algebraiczne:

Dla dowolnych R, S, T∈2^U:

1. S∩S=S, S∪S=S to jest idempotetność działań ∩ i ∪

2. S∩T=T∩S, S∪T=T∪S - przemienność

3. R∩(S∩T)=(R∩S)∩T; R∪(S∪T)=(R∪S) ∪T - łączność

4. S∩(S∪T)=S∪(S∩T)=S - absorpcja (pochłanianie)

5. · Jeśli R⊂T, to R∪(S∩T)=(R∪S)∩T - modularność

6. R∩(S∪T)=(R∩S)∪(R∩T)

R∪(S∩T)=(R∪S)∩(R∪T)

7. R∩φ=φ, R∪φ=R

R∩U=R, R∪U=U

8. R∩R'=φ, R∪R'=U - uzupełnialność

9. (S')'=S - inwolucja

10. (S∩T)'=S'∪T', (S∪T)'=S'∩T' - prawa de Morgana

Dowody powyższych własności samodzielnie przygotować!

Okazuje się, że zbiór potęgowy 2^U dowolnie ustalonego zbioru U z działaniami boolowskimi tworzy system algebraiczny, tak jak zbiór Z liczb całkowitych z działaniami +,⋅ tworzy system algebraiczny zwany pierścieniem przemiennym. Przyjmijmy, zatem poniższą definicję.

Def. System algebraiczny (2^U, ∩, ∪,') nazywamy algebrą Boole'a (alge­bra Boole'a wszystkich podzbiorów zbioru U), gdy działania boolowskie:

∩, ∪,' spełniają wyżej wymienione własności 1.) - 10.)

Można udowodnić następujące twierdzenie:

Zbiór potęgowy 2^U dowolnego niepustego zbioru U jest algebrą Boole'a.

Przykłady algebr Boole'a

Przykład 1 Niech U={a}

Jeśli przyjmiemy oznaczenia:

, to otrzymamy najprostszą nie­trywialna algebrę Boole'a (2^{a},∩,∪,'), w której działania boolowskie określają poniższe tabelki:

Dla dowodu wystarczy sprawdzić tutaj, że spełnione są wszystkie wyżej wymienione własności 1.) - 10.).

Przykład 2 Niech U={a,b}; a ≠ b; φ
0; {a}= s; {b} =s'; {a,b}=U

Działania boolowskie określają poniższe tabelki:

Wówczas można wykazać, że (2^{a,b}, ∩, ∪, `) jest algebrą Boole'a. Dla dowodu należy wykazać, iż spełnione są wszystkie wyżej wymienione warunki 1). - 10.) definicji algebry Boole'a.

Obecnie zwróćmy naszą uwagę na poniższe przykłady funkcji, operacje boolowskie i kolejny (relacyjny) przykład algebry Boole'a.

Przykłady funkcji pożytecznych w informatyce

Oto przykłady funkcji wykorzystywanych w informatyce.

1. Injekcja, surjekcja, bijekcja

Sprawdź, że:

1. f: Z → Z ∧ f(n) = -n dla n∈Z jest bijekcją;

2. f: Z → Z ∧ f(n) = 2n dla n∈Z jest injekcją, ale nie jest surjekcją;

3) f: Z → Z ∧ f(n) = n² dla n∈Z nie jest ani injekcją ani surjekcją;

2. Funkcja Peano (funkcja następnika liczby naturalnej). Niech σ: N → N i σ(n) = n+1 dla n∈N. Zbadać, że:σ jest injekcją, ale nie jest surjekcją.

3. Permutacja cykliczna zbioru n elementowego.

Def: Permutację cykliczną zbioru A = {1,2,...,n} będziemy oznaczać ν_n i nazywać funkcję ν_n: A → A, która każdej liczbie naturalnej k∈A przypo­rządkowuje jej następnik k + 1, z wyjątkiem liczby n, której przyporządkowuje liczbę 1.

• Stąd, permutację cykliczną ν_n można zapisać tak:

ν_n: 1 → 2, 2 → 3, ..., n-1 → n, n →1

• Wykazać, że permutacja cykliczna ν_n jest bijekcją.

4. Funkcja charakterystyczna zbioru.

Def: Funkcję charakterystyczną zbioru A ∈ 2^U będziemy oznaczać χ_A i określamy następująco:

1 dla x∈A

0 dla x∉A

Zad. Niech A,B ∈ 2^U. Udowodnić, że:

1)

2)

3)

4)
, gdy A∩B≠φ

5)

Wskazówka: W dowodzie należy wykazać prawdziwość odpowiedniej równości korzystając miedzy innymi z definicji funkcji charakterystycznej zbioru.

Uwaga! Symbol ν czytamy ni, zaś symbol χ czytamy kappa; są to litery alfabetu greckiego.

Przykład

Funkcja f: A →χ_A dla A∈2^U jest przykładem bardzo ważnej (bar­dzo użytecznej) bijekcji zbioru 2^U na zbiór {0,1}^U, czyli wszystkich funkcji określonych na zbiorze U o wartościach ze zbioru {0,1}

Np. Niech U={1,2,3}

Wówczas funkcja f: A→χ_A dla A∈2^{1,2,3} jest przyporządkowaniem określonym następująco:

U={1,2,3}→ (1,1,1) {1,2}→ (1,1,0)

φ → (0,0,0) {1} → (1,0,0)

{2,3}→ (0,1,1) {2} → (0,1,0)

{1,3}→ (1,0,1) {3} → (0,0,1)

Zatem powyższa funkcja f ma następujące własności:

1. D_f = 2^U;

2. Zbiorem wartości funkcji f jest zbiór wszystkich ciągów trójwyrazo­wych o wartościach ze zbioru {0,1};

3. f jest bijekcją między zbiorem 2^U a zbiorem {0,1}^U, zatem każdy ele­ment zbioru 2^U można utożsamić z jednym z ośmiu dwuwarto­ściowych trójek (po opuszczeniu nawiasów i przecinków) postaci, czyli kodów w układzie binarnym (dwójkowym):

000, 001, 010, 100, 101, 110, 111

Warto dodać, że, ta notacja jest bardzo użyteczna w informatyce, gdy te dwuargumentowe trójki uporządkowane są w naturalnej kolejności (czyli rosnąco).

Operacje boolowskie

Niech α ⊂ X
Y będzie relacją dwuargumentową (binarną) między ele­mentami zbioru X i Y. Wówczas następujące zapisy:

x α y czytamy element x zbioru X jest w relacji α z elementem y zbioru Y, bądź krotko: x jest w relacji α z y;

x α' y czytamy: x nie jest w relacji α z y.

Wiadomo, że każda funkcja f: X→Y definiuje relację binarną α między elementami zbiorów X i Y ale odwrotnie nie.

Stąd: x α y ⇔ y=f(x) dla x∈X, y∈Y.

Obecnie zdefiniujemy pojęcia pomocnicze dla zdefiniowania operacji boolowskich.

Def: Grafem relacji binarnej α między elementami zbirów X i Y nazywamy zbiór S(α) wszystkich par uporządkowanych (x,y) ∈ X
Y takich, że

x α y.

Stąd: S(α) = {(x,y) ∈ X
Y: x ၡ y} ⊂ X
Y.

Def. Relację ၡ'⊂X
Y określoną następująco: x ၡ' y
~(x ၡ y) dla x∈X, y∈Y nazywamy negacją relacji binarnej α ⊂ X
Y.

Stąd oczywistym staje się fakt: (α')'=α

• Dowolną relację binarną α⊂ X×Y można przedstawić za pomocą reprezentacji tablicowej zero-jedynkowej, gdy przyjmiemy x α y
1, zaś

~(x α y)
0. Wówczas reprezentację tablicową danej relacji binarnej

α⊂ X×Y można utożsamić z funkcją charakterystyczną jej grafu S(α). Stąd, jeśli
,
, x_i∈ dla i∈{1,2,...,n}, y_j∈Y dla j∈{1,2,..,n},to otrzymujemy:

1, gdy x_i α y_j

0, gdy ~( x_i α y_j)

Wówczas relacja binarna α⊂X×Y, gdzie X={x₁,x₂,...,x_n}, Y={y₁,y₂,...,y_n} generuje macierz relacyjną A=[a_ij]_n×m, gdzie 1, gdy x_i α y_j

0, gdy ~( x_i α y_j)

Także odwrotnie: każda macierz A=[a_ij]_n×m złożona z zer i jedynek definiuje pewną relację binarną ρ(A), a tę macierz A nazywamy macierzą relacyjną.

Reasumując powyższe stwierdzamy, iż:

1. Każda relacja binarna α⊂ X×Y jest wyznaczona przez jej graf S(α).

2. Dla danych zbiorów X i Y każdy podzbiór T ⊂ X×Y jest grafem tylko jednej relacji dwuargumentowej ρ_T między elementami zbiorów X i Y określonymi następująco: x
y ⇔ (x,y) ∈ T dla x∈X, y∈Y.

3 Przyporządkowania α→S(α) i T→ρ_T są wzajemnie odwrotnymi bijekcjami między zbiorem wszystkich relacji dwuargumentowych między elementami zbiorów X i Y a zbiorem potęgowym 2^X×Y.

Stąd : ρ_S(α)=α oraz S(ρ_T)=T dla dowolnych α ⊂ X×Y i T ⊂ X×Y.

4 Ponadto S(α')= [S(α)]', czyli ta bijekcja przekształca negację relacji na dopełnienie zbioru będącego jej grafem.

Definicja operacji boolowskich

Def. Niech ρ ⊂ X×Y, σ ⊂ X×Y oraz niech dla dowolnych x∈X, y∈Y zachodzą następujące równoważności:

1. x ρ' y
   ~(xρy)

2. x (ρ∧σ) y
   xρy ∧ xσy

3. x (ρ∨σ) y
   xρy ∨ xσy

• Tak określone relacje ρ' ρ ∧ σ oraz ρ ∨ σ nazywamy odpowiednio negacją relacji, iloczynem, sumą relacji binarnych między elementami zbiorów X i Y, zaś negację, iloczyn i sumę relacji binarnych nazywamy operacjami boolowskimi na nich.

Natomiast z powyższej definicji operacji boolowskich na relacjach binarnych oraz definicji działań ∩ i ∪ wynika, że:

• S(ρ∧σ)= S(ρ) ∩ S(σ); ρ_T∩V= ρ_T ∧ ρ_V

• S(ρ∨σ)= S(ρ) ∪ S(σ); ρ_T∪V= ρ_T ∨ ρ_V

dla dowolnych relacji ρ ⊂ X×Y, σ ⊂ X×Y oraz T,V ⊂ X×Y;

W szczególności: S(α∨α')= S(α) ∪ S(α') = X×Y

S(α∧α')= S(α) ∩ S(α')= S(α) ∩ [S(α)]'= φ

S(α') = [S(α)]'

• W zbiorze relacji binarnych można zdefiniować porządek:

ρ
σ
S(ρ) ⊂ S(σ) ⇔

• Dowodzi się także, że:

działania iloczynu, sumy, negacji relacji binarnych między elementami zbiorów X i Y spełniają warunki 1.) - 10.) wymienione w definicji algebry Boole'a. Reasumując powyższe otrzymujemy kolejny przykład algebry Boole'a:

Przykład 3 Relacje binarne między elementami ustalonych zbiorów X i Y z operacjami boolowskimi tworzą algebrę Boole'a, przy czym 1oznacza relację pełną, 0 oznacza relację pustą.

Zadanie: Sprawdź, że układ 21 równości wymienionych w warunkach

przyjętej powyżej definicji algebry Boole'a zawiera równości zależne. Np. sprawdź, że równość 1. wynika z równości 4.

Formalna definicja algebry Boole'a

Def: Algebrą Boole'a B=(A, ∧, ∨, `, 0, 1) nazywamy zbiór A, do którego należą przynajmniej dwa różne elementy z dwoma działaniami dwuargumentowymi (∧, ∨), dwiema stałymi (0, 1) oraz jednym działaniem jednoargumentowym ` (negacją), taki, że dla dowolnych x, y, z∈A spełnione są następujące aksjomaty:

1. (x∨y)∧z = xლ(yკz)

2. (xკy) ლz = xკ(yლz)

3. xლy = yლx

4. xკy = yკx

5. xლ0 = 0ლx = x

6. xკ1 = 1კx = x

7. xლ(yკz) = (xლy) კ (xლz)

8. xკ(yლz) = (xკy) ლ (xკz)

9. xკx' = 0; xლx' = 1

Wówczas dowodzi się między innymi, że: dla dowolnych x, y będących elementami algebry Boole'a zachodzą następujące twierdzenia:

Tw1 xლx = x

Tw2 xკx = x

Tw3 xლ1 = 1

Tw4 xკ0 = 0

Tw5 xლxკy = x

Tw6 (x')' = x

Tw7 (xლy)' = x'კy'

Tw8 (xკy)' = x'ლy'

=

Przykłady algebr Boole'a (w sensie powyższej definicji)

1° Podane wcześniej przykłady algebry Boole'a także są przykładami algebry Boole'a w sensie formalnej jej definicji. Sprawdź to!

2° Kontrprzykład algebry Boole'a: (A, ∧, ∨, `, 0), przy czym: A={0}, zaś 0∨0=0∧0=0'=0.

3° Niech x∧y= min (x,y) dla x,y ∈A={0,1};

x∨y= max (x,y) dla x,y ∈A={0,1};

x'= -x dla x ∈A={0,1}.

Sprawdź, że B=({0,1}, ∧, ∨, `, 0, 1) jest algebrą Boole'a.

Wskazówka: Dla dowodu należy sprawdzić, że spełnione są warunki formalnej definicji algebry Boole'a.

dystrybutywność

uniwersalność stałych: φ; U

∩	1	0
1	1	0
0	0	0

∪	1	0
1	1	1
0	1	0

`
1	0
0	1

∩	0	S	S'	U
0	0	0	0	0
S	0	S	0	S
S'	0	0	S'	S'
U	0	S	S'	U

∪	0	S	S'	U
0	0	S	S'	U
S	S	S	U	U
S'	S'	U	S'	U
U	U	U	U	U

	`
0	U
S	S'
S'	S
U	0

χ_S(α)(x_i,y_i) ={

χ_A(x)={

a_ij={

---