text: # Booleova algebra
  Booleova algebra je algebraická struktura se dvěma binárními a jednou unární operací, která zobecňuje vlastnosti množinových a logických operací. Je nazvána podle britského matematika George Boolea. Mimo oblast algebry se pojem Booleova algebra zužuje na dvouprvkovou Booleovu algebru a používá se pro reprezentaci pravdivostních hodnot a logických funkcí. Klíčový význam mají Booleovy algebry také pro metodu forsingu.
  
  ## Formální definice
  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:     | {\displaystyle x\lor y=y\lor x}                           | {\displaystyle x\land y=y\land x}                          |
  | Distributivita:   | {\displaystyle x\lor (y\land z)=(x\lor y)\land (x\lor z)} | {\displaystyle x\land (y\lor z)=(x\land y)\lor (x\land z)} |
  | Neutralita 0 a 1: | {\displaystyle x\lor 0=x}                                 | {\displaystyle x\land 1=x}                                 |
  | Komplementarita:  | {\displaystyle x\lor -x=1}                                | {\displaystyle x\land -x=0}                                |
  Někdy se uvádí ještě axiom nedegenerovanosti: {\displaystyle 0\neq 1}. Při jeho zavedení pak triviální svaz tvořený jednoprvkovou množinou není Booleovou algebrou.
  
  ## Vlastnosti
  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
  Booleovy algebry musí splňovat více axiomů, než svazy, a proto je jejich struktura jednotnější. Například každá konečná Booleova algebra má {\displaystyle 2^{n}} prvků pro nějaké {\displaystyle n>0} a je izomorfní s direktním součinem {\displaystyle n} dvouprvkových Booleových algeber.
  
  ### Dvouprvková algebra
  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ů:
  | {\displaystyle x} | {\displaystyle y} | {\displaystyle x\lor y} | {\displaystyle x\land y} |
  | ----------------- | ----------------- | ----------------------- | ------------------------ |
  | 0                 | 0                 | 0                       | 0                        |
  | 0                 | 1                 | 1                       | 0                        |
  | 1                 | 0                 | 1                       | 0                        |
  | 1                 | 1                 | 1                       | 1                        |
  
  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.
  
  ### Množinové (potenční) algebry
  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.
  
  ### Atomární a bezatomární algebry
  Nekonečné Booleovy algebry mohou být atomární, kdy pod každým nenulovým prvkem {\displaystyle x} je atom {\displaystyle a}; atom je prvek, pod kterým již nic neleží, tj. neexistuje {\displaystyle y} takové, že {\displaystyle 0\prec y\prec a}. Existují naopak bezatomární algebry, které nemají žádné atomy. Příkladem bezatomárních algeber jsou husté Booleovy algebry, v nichž pro každé {\displaystyle a\prec b} existuje {\displaystyle x} takové, že {\displaystyle a\prec x\prec b}.
  Poznámka: Jako v každém svazu se používá symbol {\displaystyle a\preceq b} pro {\displaystyle a\land b=a} (nebo ekvivalentně {\displaystyle a\lor b=b}) a symbol {\displaystyle a\prec b} pro ostré uspořádání, tj. relaci „{\displaystyle a\preceq b} a zároveň {\displaystyle a\neq b}“.
  
  ### Algebry výroků
  Prakticky používaný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ů.
  
  
title: Booleova algebra
wikitext: [[Soubor:PSM V17 D740 George Boole.jpg|náhled|George Boole 1879]]
  '''Booleova algebra''' je [[algebraická struktura]] se dvěma [[Binární operace|binárními]] a jednou [[Unární operace|unární]] [[Operace (matematika)|operací]], která zobecňuje vlastnosti [[množina|množinových]] a [[logika|logických]] operací. Je nazvána podle britského matematika [[George Boole]]a. Mimo oblast [[Algebra|algebry]] se pojem Booleova algebra zužuje na ''dvouprvkovou'' Booleovu algebru{{Sfn|Aplikovaná matematika|s=187}} a používá se pro reprezentaci [[Pravdivostní hodnota|pravdivostních hodnot]] a [[Logická funkce|logických funkcí]]. Klíčový význam mají Booleovy algebry také pro metodu [[forsing]]u.
  
  == Formální definice ==
  Booleova algebra je definována jako [[distributivní svaz|distributivní]] [[komplementární svaz|komplementární]] [[Svaz (matematika)|svaz]].{{Sfn|Aplikovaná matematika|s=184}}
  
  Jinou ekvivalentní definicí je následující. Booleova algebra je [[uspořádaná n-tice|šestice]] (''A'', ∧, ∨, −, 0, 1), kde ''A'' je neprázdná [[množina]], 0&nbsp;∈&nbsp;''A'' je [[nejmenší prvek|nejmenší]], 1&nbsp;∈&nbsp;''A'' [[největší prvek]], − je unární operace (doplněk neboli [[Komplement (svazy)|komplement]]) a ∧, ∨ jsou binární operace ([[průsek (matematika)|průsek]] a [[spojení (matematika)|spojení]]) na ''A'', splňující následující [[axiom]]y.
  
  :{| cellpadding=5
  |-
  | [[Komutativita]]:
  |<math> x \lor y = y \lor x </math>
  |<math> x \land  y = y \land x </math>
  |-
  | [[Distributivita]]:
  |<math> x \lor  (y \land z) = (x \lor y) \land (x \lor z) </math>
  |<math> x \land  (y \lor z) = (x \land y) \lor (x \land z) </math>
  |-
  | [[Neutrální prvek|Neutralita]] 0 a 1:
  |<math>x \lor 0 = x</math>
  |<math>x \land 1 = x</math>
  |-
  | [[Komplement (svazy)|Komplementarita]]:
  |<math> x \lor  -x = 1 </math>
  |<math> x \land -x = 0 </math>
  |}
  
  Někdy se uvádí ještě axiom nedegenerovanosti: <math>0\neq 1</math>. Při jeho zavedení pak triviální svaz tvořený jednoprvkovou množinou není Booleovou algebrou.
  
  == Vlastnosti ==
  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 ==
  
  Booleovy algebry musí splňovat více axiomů, než svazy, a proto je jejich struktura jednotnější. Například každá konečná Booleova algebra má <math>2^n</math> prvků pro nějaké <math>n>0</math> a je izomorfní s [[Direktní součin|direktním součinem]] <math>n</math> dvouprvkových Booleových algeber.
  
  {{Kotva|Dvouprvková algebra}}
  === Dvouprvková algebra ===
  
  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 &lt; 1, [[průsek (matematika)|průsek]] (infimum) je menší z operandů, [[spojení (matematika)|spojení]] (supremum) je větší z operandů:
  
  {|class="wikitable"
  ! <math>x</math> !! <math>y</math> !! <math>x \lor y</math> !! <math>x \land y</math> 
  |-
  | 0 || 0 ||align="center"| 0 ||align="center"| 0
  |-
  | 0 || 1 || align="center" | 1 || align="center" | 0
  |-
  | 1 || 0 || align="center" | 1 || align="center" | 0
  |-
  | 1 || 1 ||align="center"| 1 ||align="center"| 1
  |}
  
  Nejjednodušší Booleova algebra obsahuje pouze jeden prvek, neboli 0&nbsp;=&nbsp;1 (zde nejde o [[spor (logika)|spor]], nýbrž o dvojí značení jednoho [[prvek množiny|prvku]]). Všechny [[operace (matematika)|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.
  
  {{Kotva|Potenční algebra}}
  === Množinové (potenční) algebry ===
  
  U množinových algeber je algebra definována nad množinou všech podmnožin ([[potenční množina|potenční množinou]]) libovolné množiny ''S'', tzn. ''A''&nbsp;=&nbsp;2<sup>''S''</sup>, nejmenším prvkem 0 je [[prázdná množina]], největším prvkem 1 je celá množina ''S'' a operace odpovídají [[průnik]]u, [[sjednocení]] a [[doplněk (matematika)|doplňku]] do množiny ''S''.
  
  === Atomární a bezatomární algebry ===
  
  Nekonečné Booleovy algebry mohou být '''atomární''', kdy pod každým nenulovým prvkem <math>x</math> je atom <math>a</math>; '''atom''' je prvek, pod kterým již nic neleží, tj. neexistuje <math>y</math> takové, že <math>0 \prec y \prec a</math>. Existují naopak '''bezatomární''' algebry, které nemají žádné atomy. Příkladem bezatomárních algeber jsou '''husté''' Booleovy algebry, v nichž pro každé <math>a \prec b</math> existuje <math>x</math> takové, že <math>a\prec x\prec b</math>.
  
  Poznámka: Jako v každém [[Svaz (matematika)|svazu]] se používá symbol <math>a \preceq b</math> pro <math>a \land b = a</math> (nebo ekvivalentně <math>a \lor b = b</math>) a symbol <math>a \prec b</math> pro [[Částečně_uspořádaná_množina#Ostré_uspořádání|ostré uspořádání]], tj. relaci „<math>a \preceq b</math> a zároveň <math>a\neq b</math>“.
  
  === Algebry výroků ===
  
  Prakticky používanými příklady Booleových algeber jsou algebry [[Výrok (logika)|výroků]] (či obecněji [[Lindenbaumova algebra|Lindenbaumovy algebry]] [[formule (logika)|formulí]]) a množinové algebry.
  * U algeber [[Výrok (logika)|výroků]] v dvouhodnotové logice je ''A''&nbsp;=&nbsp;{nepravda, pravda} a operace odpovídají [[konjunkce (matematika)|konjunkci]], [[disjunkce|disjunkci]] a [[negace|negaci]]; pokud ztotožníme 0&nbsp;=&nbsp;nepravda, 1&nbsp;=&nbsp;pravda, algebra přejde na výše uvedenou dvouprvkovou algebru nad množinou ''A'' = {0, 1}
  * [[Lindenbaumova algebra|Lindenbaumovy algebry]] jsou definovány nad množinou ''A'' všech tříd ekvivalence [[formule (logika)|formulí]] daného [[jazyk (logika)|jazyka]] a operace jsou stejné jako u algeber [[Výrok (logika)|výroků]].
  
  == Odkazy ==
  
  === Reference ===
  <references />
  
  === Literatura ===
  * {{Citace monografie
   | titul = Aplikovaná matematika
   | edice = oborové encyklopedie
   | autor = kolektiv autorů | redaktoři = Kutinová, Blanka; Nečas, Jiří
   | místo = Praha
   | rok = 1977
   | vydavatel = SNTL – Nakladatelství technické literatury, n.p.
   | počet stran = 1318
   | ref = Aplikovaná matematika
  }}
  * {{Citace monografie
   | titul = Uspořádání a Booleovy algebry
   | jméno = Faure
   | příjmení = Robert
   | jméno2 = Edith
   | příjmení2 = Heurgonová
   | vydavatel = Academia
   | místo = Praha
   | rok = 1984
  }}
  
  === Související články ===
  * [[Booleova logika]]
  * [[Forsing]]
  * [[De Morganovy zákony]]
  
  === Externí odkazy ===
  * {{Commonscat}}
  
  {{Autoritní data}}
  {{Logické obvody}}
  
  [[Kategorie:Booleovy algebry| ]]
  [[Kategorie:Teorie množin]]
infoboxes: []