Boolesche Funktion

Definition und Bedeutung

Eine Boolesche Funktion, auch logische Funktion, ist eine mathematische Funktion der Form F: Bⁿ → B¹; teilweise wird sie allgemeiner als F: Bⁿ → Bᵐ definiert. B bezeichnet eine Boolesche Algebra. Eingaben und Ausgaben sind typischerweise die beiden Wahrheitswerte 0 und 1 beziehungsweise falsch und wahr.

Boolesche Funktionen bilden die Grundlage logischer Ausdrücke und digitaler Schaltungen. Sie können in Ausdrücke der Booleschen Algebra eingesetzt und dort ähnlich wie Variablen behandelt werden. Dabei muss man zwischen Booleschen Funktionen und den Verknüpfungen ∧, ∨ und ¬ der zugrunde liegenden Booleschen Algebra unterscheiden: Die Verknüpfungen sind zunächst Operationen auf einer Menge, während bei einer Booleschen Funktion für Definitions- und Wertebereich bereits alle Axiome einer Booleschen Algebra vorausgesetzt werden.

Die Stelligkeit n gibt an, wie viele Eingabevariablen eine Funktion besitzt. Allgemein gibt es 2^(2ⁿ) verschiedene n-stellige Boolesche Funktionen, weil für jede der 2ⁿ möglichen Eingabekombinationen unabhängig einer von zwei Ausgabewerten festgelegt werden kann.

Funktionen nach ihrer Stelligkeit

Für n = 0 gibt es 2^(2⁰) = 2 Funktionen: die Konstanten 0 und 1. Sie heißen auch falsch und wahr, falsum und verum oder false und true.

Für n = 1 existieren 2^(2¹) = 4 Funktionen. Die Kontradiktion liefert unabhängig von x stets 0. Die Identität liefert x selbst. Die Negation liefert den umgekehrten Wert ¬x = 1 − x. Die Tautologie liefert stets 1.

Für n = 2 gibt es 2^(2²) = 16 Funktionen. Zu ihnen gehören die konstanten Funktionen 0 und 1, die Identitäten und Negationen beider Eingänge sowie wichtige zweistellige Verknüpfungen. Die Konjunktion AND, x₁ ∧ x₂, ist nur bei zwei Einsen wahr. Die Disjunktion OR, x₁ ∨ x₂, ist wahr, sobald mindestens ein Eingang 1 ist. XOR, auch Antivalenz, ist genau bei unterschiedlichen Eingängen wahr; XNOR oder Äquivalenz genau bei gleichen Eingängen. Die Implikation x₁ → x₂ ist nur für x₁ = 1 und x₂ = 0 falsch. NAND ist die Negation von AND, NOR die Negation von OR. Weitere zweistellige Funktionen sind die Inhibitionen und die Replikation.

Die Zahl der Funktionen wächst sehr schnell: Bei drei Variablen gibt es 2⁸ = 256, bei vier 2¹⁶ = 65.536, bei fünf 2³² = 4.294.967.296 und bei sechs 2⁶⁴, also über 18 Trillionen, verschiedene Boolesche Funktionen.

Darstellung und Normalformen

Niederstellige Boolesche Funktionen können grafisch veranschaulicht werden. Einstellige Funktionen erscheinen als Punkte an den Ecken eines Einheitsquadrats, zweistellige Funktionen an den Ecken eines Einheitswürfels. Allgemein lässt sich eine n-stellige Funktion in einem n+1-dimensionalen Koordinatensystem als n+1-dimensionaler Einheitshyperwürfel darstellen. Spätestens bei vier Variablen wird diese Darstellung jedoch zu komplex, sodass eine algebraische Darstellung benötigt wird.

Jede Boolesche Funktion kann algebraisch ausgedrückt werden, auch wenn sie zunächst nur durch eine beliebige Funktionstafel festgelegt ist. Außerdem lässt sich jede Boolesche Funktion in Normalformen überführen. Eine Normalform ist eine festgelegte Struktur für einen logischen Ausdruck und erleichtert bestimmte Algorithmen, Schaltungsentwürfe und Beweise. Genannt werden die Disjunktive Normalform (DNF), die Konjunktive Normalform (KNF), die Ringsummennormalform (RSNF) und die Negationsnormalform (NNF). Eine Umwandlung zwischen Normalformen ist möglich.

Ein System von Funktionen, mit dem jede Boolesche Funktion dargestellt werden kann, heißt vollständiges Operatorensystem oder Verknüpfungsbasis. Beispiele sind das UND-ODER-NICHT-System, das UND-Antivalenz-System sowie jeweils NAND oder NOR allein.

Grundfunktionen und vollständige Systeme

Jede Boolesche Funktion mit mindestens zwei Eingängen kann mithilfe von UND, ODER und NICHT realisiert werden. Aufgrund der De Morganschen Regel genügen auch NICHT zusammen mit UND oder NICHT zusammen mit ODER. Für einen Schaltungsentwurf bedeutet das, dass lediglich zwei Arten von Grundschaltungen benötigt werden und sich alle weiteren Operatoren durch passende Kombinationen daraus bilden lassen.

Auch NAND allein bildet ein vollständiges Logiksystem; dasselbe gilt für NOR. Als weitere vollständige Verknüpfungsbasis nennt der Artikel AND, XOR und T.

Besondere Boolesche Funktionen werden nach ihrem Verhalten benannt: Eine Tautologie ist immer wahr, eine Kontradiktion immer falsch. Die Identität gibt den Eingang unverändert zurück, die Negation kehrt ihn um. Eine Funktion heißt symmetrisch, wenn ihr Wert nur von der Anzahl der Einsen unter den Eingaben abhängt, nicht von deren Position. Sie bleibt damit gegenüber Permutationen der Eingabevariablen unverändert.

Typische Beispiele

Bei XOR ist die Ausgabe y genau dann 1, wenn x₁ und x₂ verschieden sind. Für die Eingaben 00, 01, 10 und 11 lauten die Ausgaben entsprechend 0, 1, 1 und 0. In disjunktiver Normalform gilt: y = ¬x₁x₂ ∨ x₁¬x₂.

Die Mehrheitsfunktion für drei Schalter s₁, s₂ und s₃ soll eine Lampe l einschalten, wenn mindestens zwei der drei Schalter betätigt werden. Zunächst lässt sich die Funktion als l = ¬s₁s₂s₃ ∨ s₁¬s₂s₃ ∨ s₁s₂¬s₃ ∨ s₁s₂s₃ darstellen. Terme, die sich nur im Wert einer Variablen unterscheiden, können zusammengefasst werden. Dadurch entsteht die optimierte Funktion l = s₂s₃ ∨ s₁s₃ ∨ s₁s₂.

Mehrere Boolesche Funktionen lassen sich zu komplexeren Bausteinen verbinden. Ein Halbaddierer verwendet dieselben Eingänge x und y für eine UND- und eine XOR-Funktion. Die UND-Funktion erzeugt den Übertrag c, die XOR-Funktion die Summe s. Damit gilt c = x ∧ y und s = x XOR y.