Bc. Vojtěch Hordějčuk

„Čas je způsob, jakým příroda zajišťuje, aby se vše neodehrálo najednou.” - J. A. Wheeler

Domů » Wiki » Matematika » Booleova algebra

Booleova algebra

Booleova algebra je abstraktní matematická struktura, pojmenovaná podle irského matematika George Boolea (1815–1864). V roce 1938 ukázal Claude Elwood Shannon (1914–2001), že ji lze použít pro formální popis logických obvodů, které pracují se dvěma hodnotami. Od té doby se používá jako teoretický model kombinačních obvodů.

Z algebraického hlediska se jako Booleova algebra označuje každý komplementární a distributivní svaz, který má alespoň dva prvky.

Definice

Booleova algebra je množina B obsahující dvě binární operace (např. ^ a v), jednu unární operaci (např. -) a alespoň dva rozlišitelné prvky (označená např. jako 0 a 1). Operace a všechny prvky a, b, c z množiny B splňují následující zákony:

Idempotence

a \land a = a \lor a = a

Komutativita

\begin{align*} a \land b &= b \land a \\ a \lor b &= b \lor a \\ \end{align}

Asociativita

\begin{align*} a \land (b \land c) &= (a \land b) \land c \\ a \lor (b \lor c) &= (a \lor b) \lor c \\ \end{align}

Absorpce

a \land (a \lor b) = a \lor (a \land b) = a

Vzájemná distribuce

\begin{align*} a \land (b \lor c) &= (a \land b) \lor (a \land c) \\ a \lor (b \land c) &= (a \lor b) \land (a \lor c) \\ \end{align}

Komplementarita

\begin{align*} a \land \lnot a = 0 \\ a \lor \lnot a = 1 \\ \end{align}

Vlastnosti prvků

Množina B obsahuje alespoň dva rozlišitelné prvky (např. 0 a 1), pro které platí tyto zákonitosti:

\begin{align*} 0 \land a &= 0 \\ 0 \lor a &= a \\ 1 \land a &= a \\ 1 \lor a &= 1 \\ \end{align}

Odvozené vlastnosti

Pro všechna a, b z množiny B platí:

De Morganovy zákony

\begin{align*} \lnot a \land \lnot b =& \lnot (a \lor b) \\ \lnot a \lor \lnot b =& \lnot (a \land b) \\ \end{align}

Základní pojmy

Literál

Literál je logická proměnná nebo její negace.

a, b, \lnot c

Formule

Formule je syntakticky správná posloupnost literálů a operátorů.

a \lor \lnot b \land (\lnot c \lor a)

Konjukce

Konjunkce je jiné označení pro logický součin (AND).

a \land b

Disjunkce

Disjunkce je jiné označení pro logický součet (OR).

a \lor b

Booleova funkce

Booleova funkce n proměnných, kde n je přirozené číslo, je každé zobrazení f, které každé n-tici nul a jedniček přiřazuje nulu nebo jedničku.

f: \{0,1\}^n \to \{0,1\}

Disjunktní normální tvar

Formule je v disjunktivním normálním tvaru (DNF), je-li zapsána jako disjunkce jedné nebo několika formulí, z nichž každá je literálem nebo konjunkcí literálů. Každá Booleova funkce se dá zapsat v disjunktivním normálním tvaru.

(a \land \lnot b) \lor a \lor (\lnot c \land a)

Konjunktní normální tvar

Formule je v konjunktivním normálním tvaru (CNF), je-li zapsána jako konjunkce jedné nebo několika formulí, z nichž každá je literálem nebo disjunkcí literálů. Každá Booleova funkce se dá zapsat v konjunktivním normálním tvaru.

(a \lor b \lor c) \land (\lnot c \lor a) \land a

Reference