Jewiki unterstützen. Jewiki, die größte Online-Enzy­klo­pädie zum Judentum.

Helfen Sie Jewiki mit einer kleinen oder auch größeren Spende. Einmalig oder regelmäßig, damit die Zukunft von Jewiki gesichert bleibt ...

Vielen Dank für Ihr Engagement! (→ Spendenkonten)

How to read Jewiki in your desired language · Comment lire Jewiki dans votre langue préférée · Cómo leer Jewiki en su idioma preferido · בשפה הרצויה Jewiki כיצד לקרוא · Как читать Jewiki на предпочитаемом вами языке · كيف تقرأ Jewiki باللغة التي تريدها · Como ler o Jewiki na sua língua preferida

Boolesche Funktion

Aus Jewiki
Zur Navigation springen Zur Suche springen

Eine Boolesche Funktion (auch logische Funktion) ist eine mathematische Funktion der Form (teilweise auch allgemeiner ). ist dabei eine Boolesche Algebra.

Der Funktionsbezeichner, hier , wird für Boolesche Funktionen im Allgemeinen groß gewählt, da in einer Booleschen Algebra die verwendeten Größen bevorzugt mit Großbuchstaben bezeichnet werden. Boolesche Funktionen sind dann in Ausdrücke der Booleschen Algebra einsetzbar und können wie Variablen behandelt werden. Die Verknüpfungen einer Booleschen Algebra wie ∧, ∨ oder ¬ sehen aus wie spezielle ein- und zweistellige Boolesche Funktionen, sie sind jedoch nicht mit den entsprechenden Booleschen Funktionen zu verwechseln. Es handelt sich lediglich um Verknüpfungen auf einer Menge, über die noch nichts weiter bekannt ist, während für die Definitions- und Wertebereiche einer Booleschen Funktion bereits alle Axiome einer Booleschen Algebra als gegeben vorausgesetzt werden können.

Unterscheidung nach Stelligkeit

Wie bei der Untersuchung anderer Funktionstypen auch, unterscheidet man Boolesche Funktionen gerne nach ihrer Stelligkeit. Aufgrund der auf die Binärzahlen eingeschränkten Definitions- und Wertebereiche sind niederstellige Boolesche Funktionen verhältnismäßig einfach zu handhaben. So gibt es überhaupt nur 4 verschiedene einstellige Boolesche Funktionen, die man als Identität, Negation, konstante 1 und konstante 0 bezeichnen kann. Für die Boolesche Algebra ist hier insbesondere die Negation von Bedeutung. Die Anzahl der zweistelligen Booleschen Funktionen beträgt bereits 16. Zu den wichtigsten zählen dabei Konjunktion, Disjunktion, Äquivalenz, Antivalenz, NAND und NOR. Es existieren allgemein -stellige Boolesche Funktionen. Beispielsweise existieren verschiedene vierstellige Boolesche Funktionen. Im Folgenden werden Boolesche Funktionen verschiedener Stelligkeit etwas näher beschrieben.

Nullstellige Funktion

220 = 21 = 2

Das sind die zwei Konstanten 1 und 0, auch wahr und falsch, verum und falsum, true und false genannt.

Einstellige Funktion

221 = 22 = 4

Die vier möglichen Booleschen Funktionen y = f0(x) … f3(x) mit einer Variablen sind:

x 0 1 Funktion (y =) Name
f0 0 0 0 Kontradiktion
f1 0 1 x Identität
f2 1 0 ¬x = x = 1 − x Negation
f3 1 1 1 Tautologie

Zweistellige Funktion


Für zwei Variablen y = f(x1, x2) gibt es

222 = 24 = 16

verschiedene Boolesche Funktionen. Diese Funktionen y = f0(x1, x2) … f15(x1, x2) sind:

Zweistellige Boolesche Funktionen
x1, x2 0, 0 0, 1 1, 0 1, 1 Funktion Name
f0 0 0 0 0 x1 · x1 0 x1 ∧ ¬x1 Kontradiktion, Nullfunktion
f1 0 0 0 1 x1 · x2 x1, x2 x1x2 Konjunktion, AND(x1, x2)
f2 0 0 1 0 x1 · x2 x1 > x2 x1x2 Inhibition von x1
f3 0 0 1 1 x1 x1 x1 Identität von x1
f4 0 1 0 0 x1 · x2 x1 < x2 x1x2 Inhibition von x2
f5 0 1 0 1 x2 x2 x2 Identität von x2
f6 0 1 1 0 (x1 · x2) + (x1 · x2) x1x2 x1x2 Antivalenz, Alternative, XOR(x1, x2)
f7 0 1 1 1 x1 + x2 x1, x2 x1x2 Disjunktion, OR(x1, x2)
f8 1 0 0 0 x1 + x2 = x1 · x2 1 − ⌈x1, x2 x1x2 Nihilition, Peirce-Funktion, NOR(x1, x2)
f9 1 0 0 1 (x1 · x2) + (x1 · x2) x1 = x2 x1x2 Äquivalenz, XNOR (x1,x2)
f10 1 0 1 0 x2 1 − x2 ¬x2 Negation von x2, NOT(x2)
f11 1 0 1 1 x1 + x2 x1x2 x1x2 Replikation
f12 1 1 0 0 x1 1 − x1 ¬x1 Negation von x1, NOT(x1)
f13 1 1 0 1 x1 + x2 x1x2 x1x2 Implikation
f14 1 1 1 0 x1 · x2 = x1 + x2 1 − ⌊x1, x2 x1x2 Exklusion, Sheffer-Funktion, NAND(x1, x2)
f15 1 1 1 1 x1 + x1 1 x1 ∨ ¬x1 Tautologie, Einsfunktion

Mehr als zwei Variablen

Bei drei Variablen gibt es bereits 28 = 256 Boolesche Funktionen, bei vier Variablen 216 = 65.536, bei fünf Variablen 232 = 4.294.967.296, bei sechs Variablen sind es 264 = über 18 Trillionen, also zu viele, um sie hier alle darzustellen.

Grafische Veranschaulichung

Die grafische Veranschaulichung Boolescher Funktionen kann zumindest für niedrigstellige Funktionen durch Auftragen von Punkten in einem Koordinatensystem erfolgen. Einstellige Funktionen lassen sich in einem kartesischen Koordinatensystem als Eckpunkte eines Einheitsquadrats auftragen. Für zweistellige Funktionen gelingt dies noch einigermaßen anschaulich mittels der Eckpunkte eines Einheitswürfels in einem dreidimensionalen Koordinatensystem. n-stellige Funktionen lassen sich allgemein in einem n+1-dimensionalen Koordinatensystem als ein n+1-dimensionaler Einheitshyperwürfel darstellen.

Algebraische Darstellbarkeit

Diese Darstellung wird jedoch spätestens ab vier Variablen zu komplex, um noch anschaulich zu sein. Daher ist für höhere Dimensionen unbedingt ein algebraischer Zugang erforderlich. Tatsächlich ist es möglich, jede beliebige (etwa mittels einer Funktionstafel willkürlich festgelegte) Boolesche Funktion rein algebraisch auszudrücken. Ein System von Booleschen Funktionen, welches dies ermöglicht, bezeichnet man auch als vollständiges Operatorensystem oder Verknüpfungsbasis. Vollständige Operatorensysteme sind etwa das UND-ODER-NICHT-System, das UND-Antivalenz-System, das NAND- und das NOR-System. Man beachte, dass es sich bei diesen Funktionen nicht um die Verknüpfungen der zugrundeliegenden Booleschen Algebra handelt, sondern um definierte Funktionen.

Boolesche Grund- bzw. Basisfunktionen

Jede Boolesche Funktion mit zwei oder mehr Eingängen lässt sich mit den Funktionen UND (Konjunktion), ODER (Disjunktion) und NICHT (Negation) realisieren. In der Praxis wird das auch so gehandhabt. Deshalb sind diese drei Booleschen Funktionen die Grundfunktionen.

Wegen der De Morganschen Regel reichen grundsätzlich auch zwei dieser drei Grundfunktionen aus (NICHT zusammen mit ODER oder NICHT zusammen mit UND).

Beispiel XOR-Funktion

Bei der XOR-Verknüpfung ist der Ausgangszustand 1 (wahr), wenn die beiden Eingangszustände x1 und x2 unterschiedlich sind:

0 0 0
0 1 1
1 0 1
1 1 0

In der disjunktiven Normalform geschrieben:

Beispiel Mehrheits-Funktion

Angenommen man hat drei Personen, die jeweils einen Schalter vor sich haben. Eine Lampe l soll nur aufleuchten, wenn die Mehrheit, also zwei der Personen oder alle drei, ihren Schalter betätigen:


Da sich und nur in einem Zustand unterscheiden, kann man den sich unterscheidenden Teil wegfallen lassen und erhält .
Das Gleiche gilt für und , sowie für und , so dass am Ende folgende optimierte Funktion übrig bleibt:

Vollständige Logiksysteme

Für ein vollständiges System oder auch die Verknüpfungsbasis wird entweder die Grundverknüpfungen AND oder OR benötigt. Zusätzlich benötigt man das NOT. Für einen Schaltungsentwurf hat dieser Umstand einen Vorteil: Es werden lediglich zwei Grundschaltungen benötigt, die dieses vollständige System ((AND oder OR) und NOT) realisieren. Durch eine entsprechende Kombination der Grundoperatoren können dann alle anderen Operatoren gebildet werden.

Die NAND-Verknüpfung und NOR-Verknüpfung stellt bereits ein solches vollständiges System dar.

Normalformen (DNF, KNF, RSNF)

Jede Boolesche Funktion lässt sich in einer Normalform darstellen. Eine Überführung von einer Normalform in eine andere ist möglich. Normalformen sind nützlich für bestimmte Algorithmen, Schaltungen oder Beweise. Beispiele von Normalformen sind:

Besondere Boolesche Funktionen

  • Die immer wahr berechnende Funktion heißt Tautologie.
  • Die immer falsch berechnende Funktion heißt Kontradiktion.
  • Einstellige Boolesche Funktionen, die immer genau den Eingangswert zurückliefern, nennt man Identität.
  • Einstellige Boolesche Funktionen, die immer genau die Umkehrung des Eingangswertes zurückliefern, nennt man Negation.
  • Eine Boolesche Funktion heißt symmetrisch, wenn der Funktionswert nur von der Anzahl der Einsen im Argument, jedoch nicht von deren Position abhängt, also invariant gegenüber Permutationen der Eingabevariablen ist.

Boolesche Funktionen in Kombination

Man kann komplexere Strukturen erhalten, wenn man mehrere Boolesche Funktionen zusammenfasst. So erhält man beispielsweise einen Halbaddierer, wenn man die gleichen Eingänge x und y für die UND- und die XOR-Funktion verwendet, um am Ausgang der UND-Funktion den Carry-Zustand c, und am Ausgang der XOR-Funktion den Summen-Zustand s zu bekommen.

Dieser Artikel basiert ursprünglich auf dem Artikel Boolesche Funktion aus der freien Enzyklopädie Wikipedia und steht unter der Doppellizenz GNU-Lizenz für freie Dokumentation und Creative Commons CC-BY-SA 3.0 Unported. In der Wikipedia ist eine Liste der ursprünglichen Wikipedia-Autoren verfügbar.