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.
[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: |
|
| Komplementarita: |
| x ∧ (-x) = 0 |
x ∨ (-x) = 1 |
|
| Někdy se přidává ještě |
| Nedegenerovanost: |
 |
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.
Pro A Booleovu algebru a každé x, y, z ∈ A platí:
- asociativita: (x ∨ y) ∨ z = x ∨ (y ∨ z), (x ∧ y) v 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
[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