Booleova algebra

Z Wikipedie, otevřené encyklopedie

Booleova algebra je algebraická struktura, která modeluje 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.

Obsah

[editovat] Formální definice

Axiomy Booleových algeber
Komutativita:
x ∧ y = y ∧ x x ∨ y = y ∨ x
Distributivita:
x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z) x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z)
Neutralita 0 a 1:
x ∨ 0 = x x ∧ 1 = x
Komplementarita:
x ∧ (-x) = 0 x ∨ (-x) = 1
Někdy se přidává ještě
Nedegenerovanost: 0\neq 1

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 (komplement) a ∧, ∨ jsou binární operace (průsek, spojení) na A, splňující axiomy uvedené v tabulce.

[editovat] Vlastnosti

Pro A Booleovu algebru a každé x, y, zA platí:

  • asociativita: (xy) ∨ z = x ∨ (yz), (xy) v z = x ∧ (yz)
  • absorpce: x ∨ (xy) = x, x ∧ (xy) = x
  • agresivita nuly: x0 = 0
  • agresivita jedničky: x1 = 1
  • idempotence: xx = x, xx = x
  • absorpce negace: x ∨ (-x ∧ y) = x y, x ∧ (-x y) = x y
  • 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

[editovat] Příklady

[editovat] Nejjednodušší příklady

  • 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ž se z vypustí axiom nedegenerovanosti.
  • Dvouprvková algebra je algebra nad množinou A={0,1}, kde operace jsou dány přirozeným způsobem.

[editovat] Používané Booleovy algebry

Nejvýznamnějšími příklady Booleových algeber jsou algebry výroků (či obecněji Lindenbaumovy algebry formulí) a množinové algebry.

[editovat] Podívejte se také na