V sobotu 2. listopadu proběhla mohutná oslava naší plnoletosti !!
Multimediaexpo.cz je již 18 let na českém internetu !!
V tiskové zprávě k 18. narozeninám brzy najdete nové a zásadní informace.

Booleova algebra

Z Multimediaexpo.cz

(Rozdíly mezi verzemi)
m (1 revizi)
(+ Výrazné vylepšení)
Řádka 1: Řádka 1:
-
{{Wikipedia-cs|Booleova algebra|700}}
+
'''Booleova algebra''' je [[algebraická struktura]], která zobecňuje vlastnosti [[množina|množinových]] a [[logika|logických]] operací. Je nazvána podle irského matematika George Boolea (1815–1864). 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]].
 +
 +
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 ∈ ''A'' je [[nejmenší prvek|nejmenší]], 1 ∈ ''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>. Pak triviální svaz tvořený jednoprvkovou množinou není Booleovou algebrou.
 +
{{RIGHTTOC}}
 +
== 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 ==
 +
=== Nejjednodušší příklady ===
 +
* 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.
 +
* 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
 +
|}
 +
 +
=== Používané Booleovy algebry ===
 +
Nejvýznamnější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ů]].
 +
* 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''.
 +
 +
== Související články ==
 +
* [[Booleova logika]]
 +
* [[Forsing]]
 +
* [[De Morganovy zákony]]
 +
 +
 +
{{Článek z Wikipedie}}
[[Kategorie:Algebraické struktury]]
[[Kategorie:Algebraické struktury]]
[[Kategorie:Teorie množin]]
[[Kategorie:Teorie množin]]

Verze z 19. 2. 2014, 10:07

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 (1815–1864). 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: <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>
Neutralita 0 a 1: <math>x \lor 0 = x</math> <math>x \land 1 = x</math>
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>. Pak triviální svaz tvořený jednoprvkovou množinou není Booleovou algebrou.

Obsah

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

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ž 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ů:
<math>x</math> <math>y</math> <math>x \lor y</math> <math>x \land y</math>
0 0 0 0
0 1 1 0
1 0 1 0
1 1 1 1

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.

  • 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


Citováno z „http://www1fdc.multimediaexpo.cz/mmecz/index.php/Booleova_algebra“