Eine boolesche Funktion nimmt einige Nullen und Einsen und gibt eine Null oder Eins zurück. Jede digitale Schaltung ist so eine Funktion. Rechts steht sie als Kasten mit Drähten. Er zählt am Ende alle möglichen Funktionen durch. Mit Weiter geht es Schritt für Schritt voran.
Skript Teil 1, Folien 15 bis 18: boolesche Funktionen und ihre Anzahl.
Jeder logische Ausdruck aus den Abschnitten 2 bis 5 ordnet jeder Belegung eine 0 oder 1 zu. Das ist eine Funktion. Hier wird sie allgemein definiert, und wir zählen, wie viele es davon gibt.
So gehen wir vor:
Eine -stellige boolesche Funktion ist eine Abbildung
Jedem Tupel mit wird eindeutig ein Wahrheitswert zugeordnet.
ist die Menge aller Tupel aus Nullen und Einsen. Ein Tupel ist eine geordnete Liste, etwa bei . Jedes Tupel ist eine Belegung, also eine Zeile der Wahrheitstafel. -stellig heißt: Eingaben. Abbildung ist ein anderes Wort für Funktion.
Die Funktion gibt zu jeder Zeile genau einen Wert aus: 0 oder 1. „Eindeutig“ heißt: nie zwei Werte für dieselbe Zeile.
Die Negation braucht eine Eingabe: . Sie ist einstellig.
UND und ODER brauchen zwei: . Sie sind zweistellig. Ihre Wahrheitstafeln aus Abschnitt 2 sind genau die Wertetabellen dieser Funktionen.