Boolova algebra

Boolova algebra je algebrická štruktúra, ktorá modeluje vlastnosti množinových a logických operácií. Je nazvaná podľa írskeho matematika George Boolea.

Boolova algebra je abstraktný formálny systém obsahujúci množinu prvkov (a, b, c, ...), nad ktorou sú definované dve binárne operácie symbolizované pomocou znakov ${\displaystyle \lor }$ a ${\displaystyle \land }$. Boolova algebra je komplementárny a distributívny zväz pomenovaný podľa Georgea Boolea (1815 – 1864). Boolova algebra je zvláštnym prípadom štruktúry zvanej zväz.

Boolova algebra má interpretácie v rôznych vedných disciplínach, napríklad:

Boolova algebra	množinová algebra	výroková algebra (logika)
a, b, c, ... prvky ${\displaystyle \lor }$ (alebo)	A, B, C, ... podmnožiny množiny I U (zjednotenie)	p, q, r, ... výroky množiny U ∨ (disjunkcia)
${\displaystyle \land }$ (a)	∩ (prienik)	∧ (konjunkcia)
a ${\displaystyle \lor }$ b = b ${\displaystyle \lor }$ a	A U B = B U A	p ∨ q = q ∨ p

Definícia

Boolova algebra je definovaná ako distributívny komplementárny zväz.

Boolova algebra je šestica (A, ∧, ∨, −, 0, 1), kde A je neprázdna množina, 0 ∈ A je najmenší, 1 ∈ A najväčší prvok, − je unárna operácia (komplement) a ∧, ∨ sú binárne operácie (priesečník, spojenie) na A, spĺňajúce nasledujúce axiómy.

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}$
Nedegenerovanosť:	${\displaystyle 0\neq 1}$

Vlastnosti

Pre Boolovu algebru A a každé x, y, z ∈ A platí:

• asociativita: (x ∨ y) ∨ z = x ∨ (y ∨ z), (x ∧ y) ∧ z = x ∧ (y ∧ z)
• absorpcia: x ∨ (x ∧ y) = x, x ∧ (x ∨ y) = x
• agresivita nuly: x ∧ 0 = 0
• agresivita jednotky: x ∨ 1 = 1
• idempotencia: x ∨ x = x, x ∧ x = x
• absorpcia negácie: x ∨ (−x ∧ y) = x ∨ y, x ∧ (−x ∨ y) = x ∧ y
• dvojitá negácia: −(−x) = x
• De Morganove zákony: −x ∧ −y = −(x ∨ y), −x ∨ −y = −(x ∧ y)
• 0 a 1 sú vzájomne komplementárne: −0 = 1, −1 = 0

Označovanie

Existujú najmenej tri najznámejšie tradície v označovaní v teórii Boolovej algebry. Vo vyššie použitej definícii sú použité symboly ${\displaystyle \lor ,\land ,\lnot }$, ale bežne sú používané tiež ${\displaystyle \cup ,\cap ,\sim }$, a na bežné použitie tiež ${\displaystyle +,\cdot ,-}$. Symboly dvojargumentovýh operácií Boolovej algebry sú takmer vždy výberom jedného z páru ${\displaystyle (+,\cdot )}$, ${\displaystyle (\lor ,\land )}$ alebo ${\displaystyle (\cup ,\cap )}$. Označenie operácií jednoargumentovej algebry je menej, v dôsledku toho sa môžeme stretnúť ako so symbolmi ${\displaystyle +,\cdot ,\sim }$ tak aj ${\displaystyle \lor ,\land ,{}^{\prime }}$.

Symboly ${\displaystyle \wedge ,\vee }$ sa často používajú v súvislosti algebrickými teóriami.

Stretávame sa aj s použitím iných symbolov resp. ich kombinácií (na príklad  &  na miesto  ${\displaystyle \cap }$,  alebo  ${\displaystyle a^{\prime }}$  namiesto  ${\displaystyle \;\sim a}$. V oblasti elektroniky a informačných technológií je často používaný ako OR, AND resp. NOT  na mieste  ${\displaystyle \cup }$, ${\displaystyle \cap }$ resp. ${\displaystyle \sim }$.

Príklady

• Najjednoduchšia Boolova algebra obsahuje len jeden prvok, alebo 0 = 1 (tu nejde o spor, ale o dvojité označovanie jedného prvku). Všetky operácie dávajú rovnaký výsledok (iné tu ani neexistujú), preto sa nazýva triviálne. Táto algebra samozrejme môže existovať jedine vtedy, keď sa vypustí Axiom nedegenerovanosti.
• Duálna algebra je algebra nad množinou A= (0, 1), kde operácie sú dané prirodzeným spôsobom.

Používané Boolové algebry

Najvýznamnejšími príkladmi Boolových algebier sú algebry výrokov (alebo všeobecnejšie Lindenbaumovej algebry formulí) a množinové algebry.

• U algebier výrokov v dvojhodnotovej logike je A= (nepravda, pravda), 0 = nepravda, 1 = pravda, a operácie zodpovedajú disjunkcii, konjunkcii a negácii.

Konjunkcia ${\displaystyle \wedge }$ 0 1 0 0 0 1 0 1

Disjunkcia ${\displaystyle \lor }$ 0 1 0 0 1 1 1 1

Negácia   ${\displaystyle \neg }$ 0 1 1 0

• Lindenbaumovy algebry sú definované nad množinou A všetkých tried ekvivalencie formulou dotknutého jazyka a operácie sú rovnaké ako u algebier výrokov.
• U množinových algebier je algebra definovaná nad potenčnou množinou ľubovoľnej množiny S, tzn. A= 2 ^S, najmenším prvkom 0 je prázdna množina, najväčším prvkom 1 je sama množina Sa operácie zodpovedajú prieniku, zjednoteniu a doplnku do množiny S.

Pozri aj

• De Morganove zákony