InhaltVorheriges Kapitel Nächstes Kapitel

1 Boolesche Algebra und digitale Logik

1.4 Klassifizierung Boolescher Funktionen



Wie oben gezeigt wurde, können Boolesche Funktionen (auch Schaltfunktionen genannt) in vielfältiger Form dargestellt werden.

Im Prinzip ist eine Boolesche Funktion eine Zuordnungsvorschrift, die formal über einen mathematischen Ausdruck definiert werden kann.
Neben dieser mathematischen Beschreibungsform existiert eine weitere formale Darstellungsmethode über Wahrheitstafeln, d.h. über eine tabellarisch geordnete Wiedergabe des funktionalen Zusammenhanges.

Betrachten wir eine Boolesche Funktion f, die n Argumente xi hat, dann erhalten wir folgende generische Wahrheitstafel (Wertetabelle):

xn
...
x2
x1
f(x1,x2,...,xn)
0
...
0
0
f1
0
...
0
1
f2
0
...
1
0
f3
0
...
1
1
f4
:
...
:
:
:
:
...
:
:
:
1
...
1
1
f2n

wobei gilt: fi {0,1}

Tab. 1.5: Wahrheitstafel einer Booleschen Funktion

Wie ersichtlich, wird in dieser Tabelle in 2n Zeilen zu jeder der 2n möglichen Wertekombinationen der Variablen x1,x2,...,xn der zugehörige Funktionswert geschrieben.

Da in jeder Zeile entweder der Funktionswert 0 oder 1 angenommen wird, gibt es

(1.3)

nichtäquivalente Funktionen f(x1,x2,...,xn).

Im einfachsten Fall hängt die Boolesche Funktion nur von einer einzigen Variablen ab (s.o. unäre Funktionen), so daß


verschiedene Funktionen existieren.

Bei zwei Variablen (binäre Boolesche Funktionen) existieren entsprechend


unterschiedliche Funktionen.

Es zeigt sich also, daß die Anzahl der möglichen Booleschen Funktionen mit steigender Variablenzahl n sehr stark zunimmt.

In der folgenden Behandlung wird allerdings erkennbar werden, daß nur einige wenige dieser Funktionen nicht-triviale Eigenschaften besitzen und daher für die praktische Anwendung von Bedeutung sind.



1.4.1 Unäre Boolesche Funktionen (n = 1)

Von den vier möglichen Booleschen Funktionen einer Variablen (n=1) ist bereits die wichtigste eingeführt worden, die "Negation" (Invers-Funktion, s.o.).

Die folgende Tabelle gibt einen Überblick über alle Funktionen mit Hilfe der entsprechenden Wahrheitstafeln, funktionalen Ausdrücke und Venn-Diagramme. Wo immer sinnvoll, ist außerdem das in der Digitaltechnik verwendete Schaltsymbol (nach DIN/IEC) angegeben.

Name
Nullfunktion
Negation
Identität
Einsfunktion
Wahrheitstafel
a
f(a)
f(a)
f(a)
f(a)
0
0
1
0
1
1
0
0
1
1
Ausdruck
Venn-Diagramm
Schaltsymbol

(DIN/IEC)

Abb. 1.11: Unäre Boolesche Funktionen.



1.4.2 Binäre Boolesche Funktionen (n = 2)

In der folgenden Zusammenstellung der binären Booleschen Funktionen werden für die wichtigsten Funktionen die gebräuchlichsten Namen sowie die DIN-Schaltsymbole angegeben.


Name
Nullfunktion
NOR
Wahrheitstafel
b
a
f(a,b)
f(a,b)
f(a,b)
f(a,b)
0
0
0
1
0
1
0
1
0
0
1
1
1
0
0
0
0
0
1
1
0
0
0
0
Ausdruck



Venn-Diagramm
Schaltsymbol
(DIN/IEC)

Name
XOR
NAND
Wahrheitstafel
b
a
f(a,b)
f(a,b)
f(a,b)
f(a,b)
0
0
0
1
0
1
0
1
0
0
1
1
1
0
1
1
1
1
1
1
0
0
0
0
Ausdruck
Venn-Diagramm
Schaltsymbol
(DIN/IEC)

Abb. 1.12: Binäre Boolesche Funktionen.

Name
AND

UND
XNOR
a
Wahrheitstafel
b
a
f(a,b)
f(a,b)
f(a,b)
f(a,b)
0
0
0
1
0
1
0
1
0
0
1
1
1
0
0
0
0
0
1
1
1
1
1
1
Ausdruck
Venn-Diagramm
Schaltsymbol
(DIN/IEC)

Name
b
OR

ODER
Eins-

funktion
Wahrheitstafel
b
a
f(a,b)
f(a,b)
f(a,b)
f(a,b)
0
0
0
1
0
1
0
1
0
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1
Ausdruck
Venn-Diagramm
Schaltsymbol
(DIN/IEC)

Abb. 1.13: Binäre Boolesche Funktionen (Fortsetzung).




1.4.3 Boolesche Funktionen mit n >= 3

Wie gezeigt wurde, wächst die Anzahl der definierbaren Booleschen Funktionen mit Erhöhung der Anzahl der Argumente sehr stark an. Für n = 3 ergeben sich bereits m = 256 mögliche Funktionen, die größtenteils bedeutungslos sind.

Die Digitaltechnik beschränkt sich daher auch bei n >= 3 auf die von n = 2 her bekannten wichtigen Funktionen und den zugehörigen Schaltzeichen bei entsprechender Erhöhung der Anzahl der Eingangs-Variablen (s.u. UND- bzw. ODER-Funktion).

InhaltVorheriges Kapitel Nächstes Kapitel