Boolesche Funktion

Eine Boolesche Funktion (man spricht auch von logischen Funktionen) ist eine mathematische Funktion der Form F: Bn -> B¹. B ist dabei eine Boolesche Algebra. Der Funktionsbezeichner, hier F, 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 mit 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.

Inhaltsverzeichnis

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 2^{2^n} n-stellige Boolesche Funktionen. Beispielsweise existieren 2^{2^4} = 2^{16} = 65536 verschiedene vierstellige Boolesche Funktionen. Im folgenden werden Boolesche Funktionen verschiedener Stelligkeit etwas näher beschrieben.

n=0

2^{2^0}=2^1=2

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

n=1

2^{2^1}=2^2=4.

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

x01 
f000Kontradiktion, y=0
f101Identität, y=x
f210Negation, y=¬x
f311Tautologie, y=1

n=2

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

2^{2^2}=2^4=16

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

x10011 
x20101 
f00000y=0, die Kontradiktion (oder auch Nullfunktion genannt)
f10001y=x1∧x2, die Konjunktion
f20010y=x1∧¬x2, Inhibition x1
f30011y=x1, die Identität (von x1)
f40100y=¬x1∧x2, Inhibition x2
f50101y=x2, die Identität (von x2)
f60110y=(x1∧¬x2)∨(¬x1∧x2), die Antivalenz: &not(x1≡x2), XOR(x1,x2), Alternative
f70111y=x1∨x2, die Disjunktion
f81000y=¬(x1∨x2) = ¬x1∧¬x2 = NOR(x1,x2), Peirce-Funktion
f91001y=(x1∧x2)∨(¬x1∧¬x2), die Äquivalenz x1≡x2
f101010y=¬x2, die Negation (von x2)
f111011y=x1∨(¬x2), die Replikation
f121100y=¬x1, die Negation (von x1)
f131101y=¬x1∨x2, die Implikation x1→x2
f141110y=¬(x1∧x2) = ¬x1∨¬x2 = NAND(x1,x2), Sheffer-Funktion
f151111y=1, die Tautologie (oder auch Einsfunktion genannt)

n>2

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

Grafische Veranschaulichung

Die grafische Veranschaulichung Boolescher Funktionen kann zumindest für niederstellige Funktionen mittels des Auftragens 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-dimenstionalen 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. Vollständige Operatorensysteme sind etwa das UND-ODER-NICHT-System, dass 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äßt sich mit den Funktionen UND (Konjunktion), ODER (Disjunktion) und NICHT (Negation) realisieren. In der Praxis wird das auch so gehandhabt. Deshalb sind diese drei Boolesche 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: Die XOR-Funktion:

Wenn die beiden Eingangszustände x1 und x2 unterschiedlich sind, ist der Ausgangszustand 1 (wahr)

x1x2y
y0=000
y1=011
y2=101
y3=110

In der disjunktiven Normalform geschrieben:

y=\bar{x_1}x_2 \vee x_1\bar{x_2}

Beispiel: Die 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:

l=\bar{s_1}s_2s_3\vee s_1\bar{s_2}s_3\vee s_1s_2\bar{s_3}\vee s_1s_2s_3

Da sich \bar{s_1}s_2s_3 und s1s2s3 nur in einem Zustand unterscheiden, kann man den sich unterscheidenden Teil wegfallen lassen: s2s3. Das gleiche gilt für s_1\bar{s_2}s_3 und s1s2s3, sowie für s_1s_2\bar{s_3} und s1s2s3, so das am Ende folgende optimierte Funktion übrig bleibt:

l=s_2s_3\vee s_1s_3\vee s_1s_2

Vollständige Logiksysteme

Mit den Grundverknüpfungen AND, OR und NOT können alle anderen Verknüpfungen dargestellt werden. Man bezeichnet daher diese Verknüpfungen als vollständiges System. Für einen Schaltungsentwurf hat dieser Umstand einen Vorteil: Es werden lediglich drei Grundschaltungen benötigt die dieses vollständige System (AND, OR, NOT) realisieren. Durch eine entsprechende Kombination der Grundoperatoren können dann alle anderen Operatoren gebildet werden.

Die NAND-Verknüpfung stellt bereits ein solches vollständiges System dar. Beweisen kann man diesen Sachverhalt sehr einfach indem man mit einem NAND die Grundverknüpfungen AND, OR und NOT nachbildet. Das gleiche gilt auch für die NOR-Verknüpfung.

Bild:Logiksysteme.JPG

Disjunktive Normalform (DNF) und konjunktive Normalform (KNF)

Jede Boolesche Funktion läßt sich in der disjunktiven Normalform und in der konjunktiven Normalform darstellen. Ebenso kann man eine Funktion von der disjunktiven Normalform in die konjunktive Normalform überführen und umgekehrt.

Besondere Boolesche Funktionen

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.

Bild:Halbaddierer Aufbau.png Bild:Halbaddierer Schaltsymbol.png
Halbaddierer-Schaltung Halbaddierer-Schaltsymbol

See also: Boolesche Funktion, Boolesche Algebra, De Morgansche Gesetze, Definitionsbereich, Disjunktion, Disjunktive Normalform, Funktion (Mathematik), Halbaddierer, Hyperwürfel, Identische Abbildung