Lexikon der Mathematik: Boolesche Funktion
Funktion f : D → {0, 1}
Ist der Definitionsbereich D der Booleschen Funktion eine echte Teilmenge von {0, 1}
Boolesche Funktionen werden zumeist eingesetzt, um das Verhalten kombinatorischer logischer Schaltkreise zu beschreiben. Von besonderer Wichtigkeit sind hierbei die Booleschen Funktionen, die über einer oder über zwei Variablen definiert sind, da sie als Elemente der Bausteinbibliotheken verwendet werden.
Die Komplexität einer Booleschen Funktion ist definiert als die Kosten ihrer billigsten Beschreibung. Arbeitet man mit Booleschen Ausdrücken als Beschreibungsform, so ist die Komplexität einer Booleschen Funktion \(f:{\{0,1\}}^{n}\to \{0,1\}\) gegeben durch
\begin{eqnarray}{C}_{{{\mathfrak{A}}}_{n}}:=\min \{costs({\mathscr{W}});{\mathscr{W}}\in {{\mathfrak{A}}}_{n}\text{\hspace{0.17em}}\text{und}\text{\hspace{0.17em}}\phi ({\mathscr{W}})=f\},\end{eqnarray}
wobei costs(w) die Kosten des Booleschen Ausdrucks w sind und \(\phi ({\mathscr{W}})\) die durch w beschriebene Boolesche Funktion ist (Boolescher Ausdruck). Arbeitet man mit logischen Schaltkreisen als Beschreibungsform, so ist die Komplexität \({C}_{\Omega }(f)\) einer Booleschen Funktion f gegeben durch die Kosten des billigsten logischen Schaltkreises über einer gegebenen vollständigen Bausteinbibliothek Ω, der sie realisiert. Es gilt der Satz:Für je zwei vollständige Bausteinbibliotheken Ω1und Ω2gibt es eine Konstante \(c\in {\mathbb{Z}}\), so daß für jede Boolesche Funktion f die Ungleichung \({C}_{{\Omega }_{1}}(f)\le c\cdot {C}_{{\Omega }_{2}}(f)\)gilt.
Daher bezieht man sich bei komplexitätstheoretischen Untersuchungen Boolescher Funktionen in der Regel auf die vollständige Bausteinbibliothek
\begin{eqnarray}{{\mathfrak{B}}}_{\le 2}:=\{g|g:{\{0,1\}}^{n}]\to \{0,1\}\text{\hspace{0.17em}}\text{mit}\text{\hspace{0.17em}}n\le 2\}.\end{eqnarray}
Eine der in diesem Zusammenhang fundamentalen Fragen ist die, ob es zu jeder Booleschen Funktion \(f:\{0,1\}]\to \{0,1\}\) einen billigen logischen Schaltkreis gibt, der f realisiert. Ein einfaches Abzählargument beweist, daß fast alle Booleschen Funktionen nur mit exponentiellem Aufwand realisiert werden können. Es gilt der Satz:
Für ausreichend großesn ∈ ℕ haben wenigstens
\begin{eqnarray}{2}^{{2}^{n}}(1-{2}^{{2}^{{n}_{n}^{-1}}\mathrm{log}\mathrm{log}n})\end{eqnarray}
der \({2}^{{2}^{n}}\)vollständig spezifizierten Booleschen Funktionen \(f:{\{0,1\}}^{n}\to \{0,1\}\)eine Komplexität von wenigstens \(\frac{{2}^{n}}{n}\).Die Darstellung von Lupanow zeigt, daß die Komplexität \({C}_{{{\mathfrak{B}}}_{\le 2}}(f)\) einer Booleschen Funktion \(f:{\{0,1\}}^{n}\to \{0,1\}\) kleiner oder gleich
\begin{eqnarray}\frac{{2}^{n}}{n}+o(\frac{{2}^{n}}{n})\end{eqnarray}
ist. Es liegt somit ein Shannon-Effekt vor.[1] Wegener, I.: The Complexity of Boolean Functions. Wiley-Teubner Series in Computer Science, 1987.
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.