Boolescher Schaltkreis

In d​er theoretischen Informatik (insbesondere i​n der Komplexitätstheorie) i​st ein boolescher Schaltkreis e​in mathematisches Modell für digitale Schaltungen.

Formale Definitionen

Gatter

Gatter s​ind die Bestandteile, a​us denen boolesche Schaltkreise aufgebaut sind. Diese bekommen boolesche Eingaben u​nd kombinieren d​iese zu e​inem booleschen Wert a​ls Ausgabe. Es g​ibt verschiedene Typen v​on Gattern, d​ie Eingaben unterschiedlich kombinieren. Ein Gatter-Typ i​st eine boolesche Funktion, d​ie ein k-Tupel v​on booleschen Werten a​uf einen booleschen Wert abbildet.

Beispiele für Gatter-Typen:

• Die Familie von AND-Gattern: Für jede beliebige Stelligkeit k gibt es ein ${\displaystyle \wedge _{k}}$-Gatter, das genau dann 1 ausgibt, wenn alle Eingaben 1 sind. Für ${\displaystyle k=2}$ notieren wir die Gatter auch mit ${\displaystyle \wedge }$, d. h., ${\displaystyle \wedge =\wedge _{2}}$
• Die Familie von OR-Gattern: Für jede beliebige Stelligkeit k gibt es ein ${\displaystyle \vee _{k}}$-Gatter, das genau dann 1 ausgibt, wenn mindestens eine Eingabe 1 ist. Für ${\displaystyle k=2}$ notieren wir die Gatter auch mit ${\displaystyle \vee }$, d. h., ${\displaystyle \vee =\vee _{2}}$
• Das Negations-Gatter ${\displaystyle \neg }$: Es hat genau eine Eingabe und gibt 1 aus genau dann, wenn die Eingabe 0 ist.

Boolescher Schaltkreis

Ein ${\displaystyle n}$-Input- ${\displaystyle m}$-Output-boolescher-Schaltkreis über eine Basis ${\displaystyle \Upsilon }$ von Gattertypen ist ein gerichteter azyklischer Graph ${\displaystyle G=(V,E)}$. Die Knoten des Graphen werden auch als Gatter bezeichnet.

• Es gibt ${\displaystyle n}$ Knoten ${\displaystyle i_{1},i_{2},\dots ,i_{n}\in V}$, die Inputs, die keine eingehenden Kanten haben.
• Die verbleiben Knoten werden als interne Knoten bezeichnet.
• Jedem internen Knoten ist ein Gattertyp ${\displaystyle \upsilon \in \Upsilon }$ zugeordnet, dessen Stelligkeit mit dem In-Grad des Knoten übereinstimmt (wenn notwendig, wird auch die Reihenfolge der eingehenden Kanten festgelegt).
• Des Weiteren gibt es ${\displaystyle m}$ Knoten ${\displaystyle o_{1},o_{2},\dots ,o_{m}}$, die als Output-Knoten markiert sind.

Eine häufige Wahl für die Basis ${\displaystyle \Upsilon }$ ist ${\displaystyle \Upsilon =\{\wedge ,\vee ,\neg \}}$ (manchmal auch als Standardbasis bezeichnet), da mit diesen Gatter-Typen alle Booleschen Funktionen gebildet werden können.

Funktion des Schaltkreises

Für eine Eingabe ${\displaystyle X=(x_{1},x_{2},\dots ,x_{n})}$ wird jedem Knoten ${\displaystyle v\in V}$ des Schaltkreises ${\displaystyle C}$ wie folgt ein Wahrheitswert ${\displaystyle g_{v}(X)\in \{0,1\}}$ zugewiesen:

• Jeder Input-Knoten ${\displaystyle i_{j}}$ bekommt den Wert ${\displaystyle x_{j}}$, d. h. ${\displaystyle g_{i_{j}}(X)=x_{j}}$.
• Interne Knoten werden so ausgewertet, dass zuerst alle Vorgänger ausgewertet werden, bevor der Knoten selbst ausgewertet wird und diese Werte dann entsprechend dem Gatter-Typ kombiniert werden.

Für einen internen Knoten ${\displaystyle v\in V}$ mit ${\displaystyle k}$ direkten Vorgängern ${\displaystyle u_{1},\dots u_{k}}$ und Gatter-Typ ${\displaystyle \upsilon \in \Upsilon }$ berechnet man ${\displaystyle g_{v}(X)}$ als

${\displaystyle g_{v}(X)=\upsilon (g_{u_{1}}(X),\dots ,g_{u_{k}}(X)}$

Die boolesche Funktion ${\displaystyle f_{C}(X)}$ eines booleschen Schaltkreises ${\displaystyle C}$ ist dann

${\displaystyle f_{C}(X)=(g_{o_{1}}(X),\dots ,g_{o_{m}}(X))}$.

Begriffe

• Der Subschaltkreis eines internen Knotens ${\displaystyle v}$ besteht aus allen Gattern, die Vorgänger von ${\displaystyle v}$ sind, d. h., von denen es einen gerichteten Pfad zu ${\displaystyle v}$ gibt.
• Der Grad einer Basis ${\displaystyle \Upsilon }$ ist die maximale Stelligkeit ihrer Elemente.
• Monotoner Schaltkreis: Ein boolescher Schaltkreis ${\displaystyle C}$, bei dem die Funktion ${\displaystyle f_{C}(\cdot )}$ monoton in dem Sinne ist, dass, wann immer ${\displaystyle X=(x_{1},\dots ,x_{n}),Y=(y_{1},\dots ,y_{n}),x_{j}\leq y_{j}}$ für ${\displaystyle 1\leq j\leq n}$, auch ${\displaystyle f_{C}(X)_{j}\leq f_{C}(Y)_{j}}$ für ${\displaystyle 1\leq j\leq m}$ gilt. Oft werden damit auch boolesche Schaltkreise, die nur aus AND und OR Gattern bestehen, bezeichnet.

Komplexität

Boolesche Schaltkreise s​ind in d​er Komplexitätstheorie v​on Bedeutung, insbesondere i​m Teilgebiet d​er Schaltkreiskomplexität (englisch Circuit complexity).

Komplexitätsmaße für Schaltkreise

Es g​ibt unterschiedliche Maße für d​ie Komplexität e​ines Schaltkreises:

• Schaltkreisgröße (englisch circuit size): Die Anzahl der internen Knoten des Schaltkreises.
• Schaltkreistiefe (englisch circuit depth): Die maximale Länge eines Pfades von einem Eingabegatter zu einem Ausgangsgatter.
• Anzahl der Alternierungen von AND und OR Gattern (englisch number of alternations).
• Ingrad / Ausgrad des Schaltkreises: Die maximale Anzahl an eingehenden / ausgehenden Kanten eines Knotens des Schaltkreises. Der Ingrad wird durch die Basis ${\displaystyle \Upsilon }$ beschränkt.

Komplexitätsklassen

Einige bedeutende Komplexitätsklassen können m​it Hilfe boolescher Schaltkreise definiert werden.

• Die Klasse NC und die dazugehörige Hierarchie ${\displaystyle {\mbox{NC}}^{i}}$
• Die Klasse AC und die dazugehörige Hierarchie ${\displaystyle {\mbox{AC}}^{i}}$

Schaltkreis-Auswertungsproblem

→ Hauptartikel: Schaltkreis-Auswertungsproblem

Beim Auswerten eines booleschen Schaltkreises (englisch Circuit Value Problem) berechnet man für einen gegebenen Input-String, der allen Input-Gattern einen Wahrheitswert zuordnet, die Werte der Output-Gatter. Das Entscheidungsproblem, ob ein Output-Gatter eines Schaltkreises für eine gegebene Eingabe wahr ist, ist P-vollständig.

Erfüllbarkeitsproblem für Schaltkreise

→ Hauptartikel: Erfüllbarkeitsproblem für Schaltkreise

Das Erfüllbarkeitsproblem für Schaltkreise (englisch circuit satisfiability problem) betrachtet einen booleschen Schaltkreis ${\displaystyle C}$ mit Basis ${\displaystyle \Upsilon =\{\wedge ,\vee ,\neg \}}$ und einem einzigen Output-Gatter und fragt, ob es eine Eingabe gibt, die dieses Gatter auf 1 setzt, d. h., ob es ein ${\displaystyle X}$ gibt, so dass ${\displaystyle f_{C}(X)=1}$. Das Erfüllbarkeitsproblem für Schaltkreise ist NP-vollständig.

Literatur

• K. Rüdiger Reischuk: Einführung in die Komplexitätstheorie: Band 1: Grundlagen Maschinenmodelle, Zeit- und Platzkomplexität, Nichtdeterminismus. Teubner Verlag, 1999, ISBN 978-3-519-12275-3, 2.2 Schaltkreis-Familien.
• Christos H.Papadimitriou: Computational Complexity. Addison-Wesley, Reading/Mass, 1995, ISBN 978-0-201-53082-7, 4.3 Boolean functions and circuits & 8 Reductions and completeness (englisch).