Boolescher Schaltkreis

In der theoretischen Informatik (insbesondere in der Komplexitätstheorie) ist ein boolescher Schaltkreis ein mathematisches Modell für digitale Schaltungen.

Formale Definitionen

Gatter

Gatter sind die Bestandteile, aus denen boolesche Schaltkreise aufgebaut sind. Diese bekommen boolesche Eingaben und kombinieren diese zu einem booleschen Wert als Ausgabe. Es gibt verschiedene Typen von Gattern, die Eingaben unterschiedlich kombinieren. Ein Gatter-Typ ist eine boolesche Funktion, die ein k-Tupel von booleschen Werten auf einen booleschen Wert abbildet.

Beispiele für Gatter-Typen:

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

Boolescher Schaltkreis

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

• Es gibt $n$ Knoten $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 $\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 $m$ Knoten $o_{1},o_{2},\dots ,o_{m}$, die als Output-Knoten markiert sind.

Eine häufige Wahl für die Basis $\Upsilon$ ist $\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 $X=(x_{1},x_{2},\dots ,x_{n})$ wird jedem Knoten $v\in V$ des Schaltkreises $C$ wie folgt ein Wahrheitswert $g_{v}(X)\in \{0,1\}$ zugewiesen:

• Jeder Input-Knoten $i_{j}$ bekommt den Wert Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_j} , d. h. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v \in V} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} direkten Vorgängern Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u_1, \dots u_k} und Gatter-Typ Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \upsilon \in \Upsilon} berechnet man Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g_v(X)} als

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g_v(X) = \upsilon(g_{u_1}(X),\dots, g_{u_k}(X)}

Die boolesche Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f_C(X)} eines booleschen Schaltkreises Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C} ist dann

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f_C(X) = (g_{o_1}(X),\dots,g_{o_m}(X))} .

Begriffe

• Der Subschaltkreis eines internen Knotens Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v} besteht aus allen Gattern, die Vorgänger von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v} sind, d. h., von denen es einen gerichteten Pfad zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v} gibt.
• Der Grad einer Basis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Upsilon} ist die maximale Stelligkeit ihrer Elemente.
• Monotoner Schaltkreis: Ein boolescher Schaltkreis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C} , bei dem die Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f_C(\cdot)} monoton in dem Sinne ist, dass, wann immer Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X=(x_1, \dots, x_n), Y=(y_1,\dots, y_n), x_j \leq y_j} für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1 \leq j \leq n} , auch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f_C(X)_j \leq f_C(Y)_j} für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 sind in der Komplexitätstheorie von Bedeutung, insbesondere im Teilgebiet der Schaltkreiskomplexität (englisch Circuit complexity).

Komplexitätsmaße für Schaltkreise

Es gibt unterschiedliche Maße für die Komplexität eines 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Upsilon} beschränkt.

Komplexitätsklassen

Einige bedeutende Komplexitätsklassen können mit Hilfe boolescher Schaltkreise definiert werden.

• Die Klasse NC und die dazugehörige Hierarchie Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mbox{NC}^i}
• Die Klasse AC und die dazugehörige Hierarchie Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C} mit Basis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X} gibt, so dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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).