Podręcznik

1. Algebra Boole’a

1.1. Algebra Boole’a, definicja

Algebra Boole’a (ang. Boolean algebra) to szczególnego typu algebra ogólna. Dokładniej jest to 6-tka uporządkowana $(A, \cup, \cap, -, 0, 1)$ , gdzie $A$ jest niepustym zbiorem, a działania $\cup, \cap, -$ i wyróżnione elementy $0, 1 \in A$ (działania zero argumentowe) spełniają cały szereg warunków tzw. aksjomatów algebry Boole’a. Działanie dwuargumentowe $"\cup"$ nazywamy sumą, działanie dwuargumentowe $"\cap"$ nazywamy iloczynem a działanie jednoargumentowe $"-"$ uzupełnieniem. Wyróżnione elementy $0, 1 \in A$ są takie, że 0 jest zerem (dla działania sumy) jest to tzw. zero algebry Boole'a a 1 jedynką dla działania mnożenia jest to tzw. jedynka algebry Boole'a.

Zanim precyzyjnie zdefiniujemy algebrę Boole'a omówimy nieco prostszą od algebry Boole'a algebrę tzw. kratę (ang. lattice).

Krata to algebra $(A, \cup, \cap)$ . Działanie dwuargumentowe $"\cup"$ nazywamy sumą, działanie dwuargumentowe $"\cap"$ nazywamy iloczynem. Algebra $(A, \cup, \cap)$ jest kratą wtedy i tylko wtedy, z definicji, gdy spełnione są następujące aksjomaty (w sumie mamy 8 aksjomatów):

(1)	$x \cup y=y \cap x \quad , \quad x \cap y=y \cap x$	(przemienność sumy i iloczynu)
(2)	$x \cup(y \cup z)=(x \cup y) \cup z \quad , \quad x \cap(y \cap z)=(x \cap y) \cap z$	(łączność sumy i iloczynu)
(3)	$x \cup x=x \quad , \quad x \cap x=x$	(idempotentność)
(4)	$x \cup (x \cap y)=x \quad , \quad x \cap (x \cup y)=x$	(prawa pochłaniania)

Zauważmy, że jeśli konsekwentnie zamienimy w powyższych aksjomatach sumę $"\cup"$ na iloczyn $"\cap"$ oraz iloczyn $"\cap"$ na sumę $"\cup"$ to otrzymamy dokładnie taki sam zestaw aksjomatów.

Krata dystrybutywna (ang. distributive lattice) to krata, w której spełnione są jeszcze dodatkowo dwa aksjomaty: rozdzielczość mnożenia względem dodawania i rozdzielczość dodawania względem mnożenia.

(5)	$x \cap (y \cup z)=(x \cap y)\cup(x \cap z)$	(rozdzielczość mnożenia względem dodawania)
	$x \cup (y \cap z)=(x \cup y)\cap(x \cup z)$	(rozdzielczość dodawania względem mnożenia)

Algebrę $(A, \cup, \cap, -, 0, 1)$ nazywamy algebrą Boole’a jeśli $(A, \cup, \cap)$ jest kratą dystrybutywną, element 0 jest zerem dla działania dodawania a element 1 jedynką dla działania mnożenia czyli spełnione są równości (6) a ponadto działanie uzupełnienia spełnia równości (7).

(6)	$x \cup 0=x \quad$ (istnienie zera), $\qquad x \cap1=x \quad$ (istnienie jedności)
(7)	$x \cup -x=1, \quad x \cap -x=0$

Zapisując wyrażenia algebry Boole’a będziemy zakładać, że działanie uzupełnienia ma największy priorytet a potem w kolejności mnożenie i dodawanie. Tak więc mamy np.

$-x \cup -y=(-x)\cup(-y)$

Niech $A$ będzie dowolnym niepustym podzbiorem zbioru liczb rzeczywistych. Zdefiniujmy działania $"\cup"$ i $"\cap"$ wzorami

$x \cup y=\max(x,y), \qquad x \cup y=\min(x,y)$

Algebra

$(A, \cup, \cap)$ jest kratą

Niech

$X$ będzie dowolnym ustalonym niepustym zbiorem a suma

$"\cup"$ i iloczyn

$"\cap"$ odpowiednio sumą i iloczynem zbiorów a uzupełnienie dopełnieniem zbioru. Algebra

$(2^x, \cup, \cap, -, \varnothing, X)$ wszystkich podzbiorów zbioru

$X$ jest algebrą Boole’a.

Każde ciało podzbiorów pewnego ustalonego niepustego zbioru

$X$ jest algebrą Boole’a (działania

$\cup, \cap, -$ oraz wyróżnione elementy jak w przykładzie 1).

Każde ciało

$\sigma-$ (np.:

$\sigma-$ ciało zdarzeń – pojęcie znane z teorii prawdopodobieństwa) jest algebrą Boole’a.

Z definicji algebry Boole’a nie wynika, że musi być $1\neq0$ . Jeśli $1=0$ to algebra Boole’a ma tylko jeden element. Nazywamy taką algebrę Boole’a zdegenerowaną algebrą Boole’a. Algebrę Boole’a, która ma tylko 2 elementy, nazywamy algebą Boole’a dwuelementową.