Booleaanse functie

De 16 booleaanse functies van twee variabelen

Een booleaanse waarde of booleaanse constante is een van de twee waarden 'waar', vaak weergegeven door het getal 1, en 'onwaar', vaak weergegeven door het getal 0. Een booleaanse functie is een functie met de vorm

$f:{\mathbf{\text{B}}}^k\to \mathbf{\text{B}}$

Hierin is $\mathbf{\text{B}}=\{\text{waar},\text{onwaar}\}$ en geeft $k\ge 0$ de plaatsigheid van de functie aan, het aantal invoervariabelen. Voor elke $k$ zijn er

$2^k$

invoerwaarden met elk twee mogelijke uitvoerwaarden, dus in totaal zijn er

$2^{(2^k)}$

booleaanse functies met plaatsigheid $k$. Dit is inclusief de functies van $k$ booleaanse variabelen, die van minder variabelen afhangen. Zo zijn er:

• twee booleaanse constanten: waar en onwaar
• vier functies van één booleaanse variabele, de unaire operaties, namelijk de twee bovengenoemde en nog twee, de identieke afbeelding en de logische negatie
• 16 functies van twee booleaanse variabelen, de binaire operaties, namelijk de twee constanten en voor elk van beide variabelen de twee hierboven genoemde, en nog tien: disjunctie, conjunctie, implicatie in twee richtingen, bi-implicatie en de negatie van elk van deze vijf.

Elke booleaanse functie met plaatsigheid $k$ kan worden genoteerd als een logische propositie in $k$ variabelen. Een booleaanse functie duidt aan hoe men de booleaanse waarde van een propositie kan bepalen op basis van de booleaanse invoerwaarden. Booleaanse functies kunnen als logische proposities worden weergegeven, maar er zijn meer mogelijkheden om ze weer te geven, zoals met binaire beslissingsdiagrammen.

Twee logische proposities zijn logisch equivalent dan en slechts dan als zij dezelfde booleaanse functie representeren.

Booleaanse operator

Een booleaanse operator is een booleaanse functie met plaatsigheid twee, $k=2$. Bekende booleaanse operatoren zijn de logische conjunctie en logische disjunctie. In hardware zijn dit poorten, zoals de AND-poort en de OF-poort.