Booleova algebra

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Booleova algebra je algebraická struktura, která zobecňuje vlastnosti množinových a logických operací. Je nazvána podle irského matematika George Boolea. Klíčový význam mají Booleovy algebry také pro metodu forsingu.

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:  x \lor y = y \lor x  x \land  y = y \land x
Distributivita:  x \lor  (y \land z) = (x \lor y) \land (x \lor z)  x \land  (y \lor z) = (x \land y) \lor (x \land z)
Neutralita 0 a 1: x \or 0 = x x \and 1 = x
Komplementarita:  x \lor  -x = 1  x \land -x = 0

Někdy se uvádí ještě axiom nedegenerovanosti: 0\neq 1. 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, zA platí:

  • asociativita: (xy) ∨ z = x ∨ (yz), (xy) ∧ z = x ∧ (yz)
  • absorpce: x ∨ (xy) = x, x ∧ (xy) = x
  • agresivita nuly: x ∧ 0 = 0
  • agresivita jedničky: x ∨ 1 = 1
  • idempotence: xx = x, xx = x
  • absorpce negace: x ∨ (−xy) = xy, x ∧ (−xy) = xy
  • dvojitá negace: −(−x) = x
  • De Morganovy zákony: −x ∧ −y = −(xy), −x ∨ −y = −(xy)
  • 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ů:
x y x \lor y x \land y
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.

Související články[editovat | editovat zdroj]