Schaltfunktionen

Eine Schaltfunktion (Boolesche Funktion oder logische Funktion) ist eine Funktion der Form \(\displaystyle F\colon B^n \to B^1\), wobei \(\displaystyle B\) eine zweielementige Boolesche Algebra ist. Typischerweise wird \(\displaystyle B=\{0,1\}\) mit den logischen Operatoren \(\displaystyle \and\), \(\displaystyle \or\) und \(\displaystyle \not\) gewählt.
 
 

Aufzählung nach Stelligkeit

Die Anzahl der möglichen Schaltfunktionen der Form \(\displaystyle F\colon B^n \to B^1\), wobei \(\displaystyle B\) ist \(\displaystyle 2^{(2^n)}\) und daher stets endlich. Beispielsweise existieren \(\displaystyle 2^{2^4} = 2^{16} = 65536\) verschiedene vierstellige Boolesche Funktionen. Es bietet sich eine Unterscheidung nach der Stelligkeit an.

Nullstellige Funktion

\(\displaystyle n=0\); Anzahl der Funktionen: \(\displaystyle 2^{2^0}=2^{1} = 2\).
Diese beiden "Funktionen" sind aber eigentlich Konstanten, da man bei Funktionen ohne Argumente nicht wirklich von Funktionen sprechen kann. Sie entsprechen genau \(\displaystyle 1\in\B\) und \(\displaystyle 0\in\B\) werden aber auch wahr und falsch, verum und falsum, true und false genannt.

Einstellige Funktion

\(\displaystyle n=1\); Anzahl der Funktionen: \(\displaystyle 2^{2^1}= 2^{2} = 4\)
Die vier möglichen unären Booleschen Funktionen \(\displaystyle y\) = \(\displaystyle f_{0} (x)\) … \(\displaystyle f_{3} (x)\) mit einer Variablen sind:
\(\displaystyle x\) 0 1 Funktion (\(\displaystyle y\) =) Name
\(\displaystyle f_{0}\) 0 0 0 Kontradiktion
\(\displaystyle f_{1}\) 0 1 \(\displaystyle x\) Identität
\(\displaystyle f_{2}\) 1 0 \(\displaystyle \not x\) \(\displaystyle =\ovl x\) \(\displaystyle =1 - x \) Negation
\(\displaystyle f_{3}\) 1 1 1 Tautologie

Zweistellige Funktion

\(\displaystyle n=2\); Anzahl der Funktionen: \(\displaystyle 2^{2^2}= 2^{4} = 16\)
\(\displaystyle x _{1},\, x_{2}\) 0, 0 0, 1 1, 0 1, 1 Funktion Name
\(\displaystyle f_{0}\) 0 0 0 0 \(\displaystyle 0=x _{1}+{x _{1}}\) 0 \(\displaystyle x _{1}\cdot \not x _{1}\) Kontradiktion, Nullfunktion
\(\displaystyle f_{1}\) 0 0 0 1 \(\displaystyle x _{1}\) · \(\displaystyle x _{2}\) \(\displaystyle \min( x _{1},\, x_{2})\) \(\displaystyle x _{1}\and x _{2}\) Konjunktion, AND\(\displaystyle (x _{1},\, x_{2})\)
\(\displaystyle f_{2}\) 0 0 1 0 \(\displaystyle x _{1}+ {x_1 x _{2}}\) \(\displaystyle x _{1}\) > \(\displaystyle x _{2}\) \(\displaystyle \not(x _{1}\ra x _{2})\) Inhibition von \(\displaystyle x _{1}\)
\(\displaystyle f_{3}\) 0 0 1 1 \(\displaystyle x _{1}\) \(\displaystyle x _{1}\) \(\displaystyle x _{1}\) Identität von \(\displaystyle x _{1}\)
\(\displaystyle f_{4}\) 0 1 0 0 \(\displaystyle x _{2}+ {x_1 x _{2}}\) \(\displaystyle x _{1}\) < \(\displaystyle x _{2}\) \(\displaystyle \not(x _{1}\leftarrow x _{2})\) Inhibition von \(\displaystyle x _{2}\)
\(\displaystyle f_{5}\) 0 1 0 1 \(\displaystyle x _{2}\) \(\displaystyle x _{2}\) \(\displaystyle x _{2}\) Identität von \(\displaystyle x _{2}\)
\(\displaystyle f_{6}\) 0 1 1 0 \(\displaystyle x _{1} + x _{2}\) \(\displaystyle x _{1} \neq x_{2}\) \(\displaystyle x _{1}\) ↮ \(\displaystyle x _{2}\) Antivalenz, Alternative, XOR\(\displaystyle (x _{1},\, x_{2})\)
\(\displaystyle f_{7}\) 0 1 1 1 \(\displaystyle x_1+x_2+x_1 \cdot x_2\) \(\displaystyle \max(x _{1},\, x_{2})\) \(\displaystyle x _{1}\) ∨ \(\displaystyle x _{2}\) Disjunktion, OR\(\displaystyle (x _{1},\, x_{2})\)
\(\displaystyle f_{8}\) 1 0 0 0 \(\displaystyle 1+x_1+x_2+x_1 \cdot x_2\) \(\displaystyle 1-\max(x _{1},\, x_{2})\) \(\displaystyle x _{1}\) ↓ \(\displaystyle x _{2}\) Nihilition, Peirce-Funktion, NOR\(\displaystyle (x _{1},\, x_{2})\)
\(\displaystyle f_{9}\) 1 0 0 1 \(\displaystyle 1+x_1+x_2\) \(\displaystyle x _{1}\) = \(\displaystyle x _{2}\) \(\displaystyle x _{1}\) ↔ \(\displaystyle x _{2}\) Äquivalenz
\(\displaystyle f_{10}\) 1 0 1 0 \(\displaystyle 1+{x _{2}}\) 1 - \(\displaystyle x _{2}\) ¬\(\displaystyle x _{2}\) Negation von \(\displaystyle x _{2}\), NOT\(\displaystyle (x _{2})\)
\(\displaystyle f_{11}\) 1 0 1 1 \(\displaystyle 1+ x _{2}+ {x_1 x _{2}}\) \(\displaystyle x _{1} \geq x_{2}\) \(\displaystyle x _{1}\) ← \(\displaystyle x _{2}\) Replikation
\(\displaystyle f_{12}\) 1 1 0 0 \(\displaystyle 1+x_1\) 1 - \(\displaystyle x _{1}\) ¬\(\displaystyle x _{1}\) Negation von \(\displaystyle x _{1}\), NOT\(\displaystyle (x _{1})\)
\(\displaystyle f_{13}\) 1 1 0 1 \(\displaystyle 1+ x _{1}+ {x_1 x _{2}}\) \(\displaystyle x _{1} \leq x_{2}\) \(\displaystyle x _{1} \to x_{2}\) Implikation
\(\displaystyle f_{14}\) 1 1 1 0 \(\displaystyle 1+x_1\cdot x_2\) \(\displaystyle 1-\min( x _{1},\, x_{2})\) \(\displaystyle x _{1}\) ↑ \(\displaystyle x _{2}\) Exklusion, Sheffer-Funktion, NAND\(\displaystyle (x _{1},\, x_{2})\)
\(\displaystyle f_{15}\) 1 1 1 1 1 1 \(\displaystyle x _{1}\) ∨ ¬\(\displaystyle x _{1}\) Tautologie, Einsfunktion

Mehr als zwei Variablen

\(\displaystyle n>2\) Bei drei Variablen gibt es bereits \(\displaystyle 2^{8}\) = 256 Boolesche Funktionen, bei vier Variablen \(\displaystyle 2^{16}\) = 65.536, bei fünf Variablen \(\displaystyle 2^{32}\) = 4.294.966.416, bei sechs Variablen sind es \(\displaystyle 2^{64}\) = über 18 Trillionen.

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:

Strukturen sind die Waffen der Mathematiker.

N. Bourbaki

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Boolesche Funktion aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе