Booleova algebra
Booleova algebra je algebraická struktura, která zobecňuje vlastnosti množinových a logických operací. Je nazvána podle britského matematika George Boolea. Klíčový význam mají Booleovy algebry také pro metodu forsingu.
Obsah
Formální definice[editovat | editovat zdroj]
Booleova algebra je definována jako distributivní komplementární svaz.
Jinou ekvivalentní definicí je následující. Booleova algebra je šestice (A, ∧, ∨, −, 0, 1), kde A je neprázdná množina, 0 ∈ A je nejmenší, 1 ∈ A největší prvek, − je unární operace (doplněk neboli komplement) a ∧, ∨ jsou binární operace (průsek a spojení) na A, splňující následující axiomy.
Komutativita: Distributivita: Neutralita 0 a 1: Komplementarita:
Někdy se uvádí ještě axiom nedegenerovanosti: . Pak triviální svaz tvořený jednoprvkovou množinou není Booleovou algebrou.
Vlastnosti[editovat | editovat zdroj]
Pro Booleovu algebru A a každé x, y, z ∈ A platí:
- asociativita: (x ∨ y) ∨ z = x ∨ (y ∨ z), (x ∧ y) ∧ z = x ∧ (y ∧ z)
- absorpce: x ∨ (x ∧ y) = x, x ∧ (x ∨ y) = x
- agresivita nuly: x ∧ 0 = 0
- agresivita jedničky: x ∨ 1 = 1
- idempotence: x ∨ x = x, x ∧ x = x
- absorpce negace: x ∨ (−x ∧ y) = x ∨ y, x ∧ (−x ∨ y) = x ∧ y
- dvojitá negace: −(−x) = x
- De Morganovy zákony: −x ∧ −y = −(x ∨ y), −x ∨ −y = −(x ∧ y)
- 0 a 1 jsou vzájemně komplementární: −0 = 1, −1 = 0
Příklady[editovat | editovat zdroj]
Nejjednodušší příklady[editovat | editovat zdroj]
- Nejjednodušší Booleova algebra obsahuje pouze jeden prvek, neboli 0 = 1 (zde nejde o spor, nýbrž o dvojí značení jednoho prvku). Všechny operace dávají stejný výsledek (jiné zde ani neexistují), proto se nazývá triviální. Tato algebra samozřejmě může existovat jedině tehdy, když nepoužijeme axiom nedegenerovanosti.
- Dvouprvková algebra je algebra nad množinou A = {0, 1}, kde operace jsou dány přirozeným způsobem, tj. 0 a 1 jsou vzájemně komplementární a protože platí 0 < 1, průsek (infimum) je menší z operandů, spojení (supremum) je větší z operandů:
0 | 0 | 0 | 0 |
0 | 1 | 1 | 0 |
1 | 0 | 1 | 0 |
1 | 1 | 1 | 1 |
Používané Booleovy algebry[editovat | editovat zdroj]
Nejvýznamnějšími příklady Booleových algeber jsou algebry výroků (či obecněji Lindenbaumovy algebry formulí) a množinové algebry.
- U algeber výroků v dvouhodnotové logice je A = {nepravda, pravda} a operace odpovídají konjunkci, disjunkci a negaci; pokud ztotožníme 0 = nepravda, 1 = pravda, algebra přejde na výše uvedenou dvouprvkovou algebru nad množinou A = {0, 1}
- Lindenbaumovy algebry jsou definovány nad množinou A všech tříd ekvivalence formulí daného jazyka a operace jsou stejné jako u algeber výroků.
- U množinových algeber je algebra definována nad množinou všech podmnožin (potenční množinou) libovolné množiny S, tzn. A = 2S, nejmenším prvkem 0 je prázdná množina, největším prvkem 1 je celá množina S a operace odpovídají průniku, sjednocení a doplňku do množiny S.