Booleaanse functie

Een booleaanse waarde of booleaanse constante is een van de twee waarden "waar" (vaak gepresenteerd door het getal 1) en "onwaar" (vaak gepresenteerd door het getal 0). Een booleaanse functie is een functie met de vorm , waarbij en k ≥ 0 de ariteit van de functie aangeeft (het aantal inputvariabelen). Voor elke k zijn er invoerwaarden met elk 2 mogelijke uitvoerwaarden, dus in totaal zijn er functies met ariteit k. Dit is inclusief de functies van formeel k booleaanse variabelen, die feitelijk van minder variabelen afhangen. Zo zijn er: * twee booleaanse constanten: waar en onwaar * vier functies van één booleaanse variabele (unaire operatie), namelijk de twee bovengenoemde en nog twee, namelijk de identieke afbeelding en de logische negatie * 16 functies van twee booleaanse variabelen (binaire operatie), namelijk de twee constanten en voor elk van beide variabelen de twee hierboven genoemde, en nog tien: disjunctie, conjunctie, implicatie (in twee richtingen), en equivalentie, en de negatie van elk van deze vijf Elke booleaanse functie met ariteit k kan genoteerd worden als een logische propositie in k variabelen. Twee logische proposities zijn logisch equivalent dan en slechts dan als zij dezelfde booleaanse functie representeren. Een booleaanse functie duidt aan hoe men een booleaanse waarde kan verkrijgen op basis van booleaanse invoerwaarden. Booleaanse functies kunnen gerepresenteerd worden als logische proposities maar er bestaan ook andere representaties, zoals binaire beslissingsdiagrammen.