Dva příklady k tématu Booleových algeber.

Příklad 1.

V Booleově algebře (X, , , ', 0, 1) dokažte:

y <= x' <=> x y = 0

y >= x' <=> x y = 1

Řešení

1. Protože y <= x', potom musí platit, že x' y = y. Potom x (x' y) = 0 a po použití asociativního zákona (x x' ) y = 0, ale (x x' = 0, tedy 0 y = 0 a proto také x y = 0.

2. Obdobně jako u 1. Je-li y >= x', potom x' y = y. Dosadíme za y do první rovnice a vidíme, že x (x' y) = 1. Takže (x x') y = 1 (podle asociativního zákona) a zároveň platí (x x') = 1, tedy 1 y = 1. Netřeba dodávat, že x y = 1.

Vysvětlivky

je operace spojení.
je operace průsek.
x' je komplement (doplněk) k x.
0 je nejmenší prvek algebry a 1 je největší prvek algebry.

Příklad 2.

Nechť X = { 1, 2, 5, 7, 14, 10, 35, 70 }. Položme x y = nsn(x, y), x y = NSD(x, y) a x' = 70/x pro všechna x, y X. Dokažte, že (X, , , ', 1, 70) je Booleova algebra. Nakreslete její Hasseův diagram.

Řešení

Booleova algebra je vlastně Booleův svaz, kde si operací představíme spojení a operací průsek. Stejně jako ostatní svazy i tento má svůj Hasseův diagram.
.
Tento diagram je očividně izomorfní s diagramem pro svaz všech podmnožin tříprvkové množiny:
.
O svazu podmnožin tříprvkové množiny víme, že je komplementární, distributivní, takže i modulární. Je Booleovský. Svaz izomorfní se svazem podmnožin tříprvkové množiny je tedy také Booleovský. Dokonce počet prvků tohoto svazu je třetí množina dvou.
Důkaz se ovšem dá provést dokázáním všech axiomů Booleových algeber. Musí platit asociativita, komutativita, distributivnost, absorbce a idempotence, stejně jako věty o komplementaritě a věta o největším a nejmenším prvku.

Poznámka

Věta o komplementaritě:
x x' = 1 x x' = 0
neboli z příkladu: nsn(x, x') = 70 NSD(x, x') = 1
Věta o nejmenším a největším prvku:
x 0 = x x 1 = x
opět vezmeme-li operace a prvky z příkladu:
nsn(x, 1) = x NSD(x, 70) = x

Vysvětlivky

nsn ... nejmenší společný násobek
NSD ... největší společný dělitel