Booleaanse algebra

In de wiskunde, met name de abstracte algebra, en in de informatica is een booleaanse algebra of boolealgebra een algebraïsche structuur met de logische operatoren AND (en), OR (of) en NOT (niet). Deze operatoren zijn direct gerelateerd aan de begrippen doorsnede, vereniging en complement uit de verzamelingenleer.

Zo is het logische "uitgesloten derde", dat stelt dat een uitspraak waar is of onwaar, equivalent met de regel dat de vereniging van een verzameling en z'n complement alle in het geding zijnde elementen bevat.

${\displaystyle A\cup A^{c}=U}$.

Complementair daaraan is de logische vaststelling dat een uitspraak en z'n ontkenning niet samen waar kunnen zijn. Dit wordt voor verzamelingen weerspiegeld in de regel dat een verzameling en z'n complement geen gemeenschappelijk element hebben.

${\displaystyle A\cap A^{c}=\emptyset }$.

De booleaanse operatoren zijn genoemd naar de Brit George Boole, die ze in het midden van de 19e eeuw invoerde. Een booleaanse algebra is een poging om algebraïsche technieken te gebruiken teneinde te kunnen omgaan met logische uitdrukkingen. Booleaanse algebra's vinden bijvoorbeeld toepassing in het samenstellen van digitale elektronische schakelingen, zoals die in computers worden gebruikt. In de praktijk kan men de werking ervan onder meer zien in sommige zoeksystemen voor internetpagina's.

Definitie

Een booleaanse algebra of boolealgebra bestaat uit een verzameling ${\displaystyle S}$ die ten minste twee verschillende elementen 0 (onwaar, logische FALSE) en 1 (waar, logische TRUE) bevat, en die voorzien is van twee binaire bewerkingen ${\displaystyle \land }$ (en, logische AND, ook genoteerd als ${\displaystyle \times }$ of ${\displaystyle \ \cdot \ }$) en ${\displaystyle \lor }$ (of, logische OR, ook genoteerd als ${\displaystyle +}$), en een unaire bewerking ${\displaystyle \lnot }$ (niet, logische NOT), die voldoen aan de volgende axioma's voor alle ${\displaystyle a,b,c\in S}$:

associativiteit

${\displaystyle a\lor (b\lor c)=(a\lor b)\lor c}$

${\displaystyle a\land (b\land c)=(a\land b)\land c}$

commutativiteit

${\displaystyle a\lor b=b\lor a}$

${\displaystyle a\land b=b\land a}$

absorptie

${\displaystyle a\lor (a\land b)=a}$

${\displaystyle a\land (a\lor b)=a}$

distributiviteit

${\displaystyle a\lor (b\land c)=(a\lor b)\land (a\lor c)}$

${\displaystyle a\land (b\lor c)=(a\land b)\lor (a\land c)}$

complement

${\displaystyle a\lor \lnot a=1}$

${\displaystyle a\land \lnot a=0}$

De eerste drie paren axioma's, associativiteit, commutativiteit en absorptie, houden in dat het geordende drietal ${\displaystyle (S,\land ,\lor )}$ een tralie is.

Uit de axioma's volgt dat in de partiële ordening van het tralie 0 het kleinste element is en 1 het grootste element. (Die partiële ordening wordt bepaald door de relatie ${\displaystyle a\leq b\Longleftrightarrow a=a\land b}$.)

Verder volgt uit de axioma's dat het complement ${\displaystyle \lnot a}$ van een element ${\displaystyle a}$ eenduidig bepaald is en dat:

idempotentie

${\displaystyle a\lor a=a}$

${\displaystyle a\land a=a}$

kleinste en grootste elementen

${\displaystyle a\lor 0=a}$

${\displaystyle a\land 1=a}$

${\displaystyle a\lor 1=1}$

${\displaystyle a\land 0=0}$

complementen

${\displaystyle \lnot 0=1}$

${\displaystyle \lnot 1=0}$

regels van De Morgan

${\displaystyle \lnot (a\lor b)=\lnot a\land \lnot b}$

${\displaystyle \lnot (a\land b)=\lnot a\lor \lnot b}$

involutie

${\displaystyle \lnot \lnot a=a}$.

Veel gebruikte Engelse benamingen zijn:

naam	Engelse naam	symbolen
en	meet, and	${\displaystyle \land }$	${\displaystyle \times }$
of	join, or	${\displaystyle \lor }$	${\displaystyle +}$
niet	not	${\displaystyle \lnot }$	${\displaystyle \sim }$
onwaar	false	0
waar	true	1

Andere bewerkingen zijn:

naam	Engelse naam	symbool
niet-en	nand	${\displaystyle \lnot (a\land b)}$
niet-of	nor	${\displaystyle \lnot (a\lor b)}$
exclusieve of	xor	${\displaystyle (a\lor b)\land \lnot (a\land b)}$

Notatie

Soms wordt vanwege een zekere mate van overeenkomst een + gebruikt voor ${\displaystyle \lor }$ en een ${\displaystyle \cdot }$ voor ${\displaystyle \land }$. Voor wie bekend is met getallenalgebra schept deze notatie verwarring, omdat deze symbolen, die ook in getallenalgebra worden gebruikt, hier een andere betekenis hebben.

+   betekent OR (OF)

·    betekent AND (EN)

${\displaystyle {\overline {A}}}$ betekent NOT ${\displaystyle A}$ (NIET)

Een booleaanse algebra werkt met variabelen die slechts de waarden 0 en 1 aannemen. Voorbeelden van vergelijkingen:

${\displaystyle {\begin{matrix}1+1=1\end{matrix}}}$

${\displaystyle {\begin{matrix}A+B\cdot C=(A+B)\cdot (A+C)\end{matrix}}}$

${\displaystyle {\begin{matrix}A+{\overline {A}}\cdot B=A+B\end{matrix}}}$

Soms wordt ook een vierde booleaanse operator gehanteerd, de exclusive OR ofwel XOR (ook EXCLUSIEVE OF, of exclusieve disjunctie), gedefinieerd door de regel

${\displaystyle A\oplus B=A\cdot {\overline {B}}+B\cdot {\overline {A}}}$

(ook te schrijven als ${\displaystyle (A\land \lnot B)\lor (B\land \lnot A)}$)

De operator ${\displaystyle \oplus }$ gedraagt zich ongeveer als de klassieke getallenoperator ${\displaystyle +}$, weliswaar met de eigenaardigheid dat ${\displaystyle 1\oplus 1=0}$

Een volledig stel logische uitdrukkingen wordt gemodelleerd door een algebra van verzamelingen. Het is, in de formele zin, een associatieve algebra met eenheidselement over het lichaam (in België: veld) ${\displaystyle \mathbb {Z} /2\mathbb {Z} =\{0,1\}}$ met de bewerkingen ${\displaystyle \oplus }$ en ${\displaystyle \cdot }$.

Voorbeelden

De eenvoudigste booleaanse algebra bestaat slechts uit de elementen 0 en 1. De rekenregels volgen uit de axioma's van deze waarheidstabellen:

${\displaystyle \land }$ 0 1 0 0 0 1 0 1

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

a  ${\displaystyle \lnot }$ a 0 1 1 0

Een ander voorbeeld van een booleaanse algebra wordt gevormd door de machtsverzameling van een gegeven verzameling ${\displaystyle U}$ met de bekende bewerkingen vereniging, doorsnede en complement.

Zie ook

• Booleaanse functie
• Logische conjunctie
• Logische disjunctie
• Robbins-algebra

Zie de categorie Boolean algebra van Wikimedia Commons voor mediabestanden over dit onderwerp.