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

Formale Definitionen

Bearbeiten

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  -Gatter, das genau dann 1 ausgibt, wenn alle Eingaben 1 sind. Für   notieren wir die Gatter auch mit  , d. h.,  
  • Die Familie von OR-Gattern: Für jede beliebige Stelligkeit k gibt es ein  -Gatter, das genau dann 1 ausgibt, wenn mindestens eine Eingabe 1 ist. Für   notieren wir die Gatter auch mit  , d. h.,  
  • Das Negations-Gatter  : Es hat genau eine Eingabe und gibt 1 aus genau dann, wenn die Eingabe 0 ist.

Boolescher Schaltkreis

Bearbeiten

Ein  -Input-  -Output-boolescher-Schaltkreis über eine Basis   von Gattertypen ist ein gerichteter azyklischer Graph  . Die Knoten des Graphen werden auch als Gatter bezeichnet.

  • Es gibt   Knoten  , die Inputs, die keine eingehenden Kanten haben.
  • Die verbleiben Knoten werden als interne Knoten bezeichnet.
  • Jedem internen Knoten ist ein Gattertyp   zugeordnet, dessen Stelligkeit mit dem In-Grad des Knoten übereinstimmt (wenn notwendig, wird auch die Reihenfolge der eingehenden Kanten festgelegt).
  • Des Weiteren gibt es   Knoten  , die als Output-Knoten markiert sind.

Eine häufige Wahl für die Basis   ist   (manchmal auch als Standardbasis bezeichnet), da mit diesen Gatter-Typen alle Booleschen Funktionen gebildet werden können.

Funktion des Schaltkreises

Bearbeiten

Für eine Eingabe   wird jedem Knoten   des Schaltkreises   wie folgt ein Wahrheitswert   zugewiesen:

  • Jeder Input-Knoten   bekommt den Wert  , d. h.  .
  • 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   mit   direkten Vorgängern   und Gatter-Typ   berechnet man   als
 

Die boolesche Funktion   eines booleschen Schaltkreises   ist dann

 .

Begriffe

Bearbeiten
  • Der Subschaltkreis eines internen Knotens   besteht aus allen Gattern, die Vorgänger von   sind, d. h., von denen es einen gerichteten Pfad zu   gibt.
  • Der Grad einer Basis   ist die maximale Stelligkeit ihrer Elemente.
  • Monotoner Schaltkreis: Ein boolescher Schaltkreis  , bei dem die Funktion   monoton in dem Sinne ist, dass, wann immer   für  , auch   für   gilt. Oft werden damit auch boolesche Schaltkreise, die nur aus AND und OR Gattern bestehen, bezeichnet.

Komplexität

Bearbeiten

Boolesche Schaltkreise sind in der Komplexitätstheorie von Bedeutung, insbesondere im Teilgebiet der Schaltkreiskomplexität (englisch Circuit complexity).

Komplexitätsmaße für Schaltkreise

Bearbeiten

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   beschränkt.

Komplexitätsklassen

Bearbeiten

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

  • Die Klasse NC und die dazugehörige Hierarchie  
  • Die Klasse AC und die dazugehörige Hierarchie  

Schaltkreis-Auswertungsproblem

Bearbeiten

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

Bearbeiten

Das Erfüllbarkeitsproblem für Schaltkreise (englisch circuit satisfiability problem) betrachtet einen booleschen Schaltkreis   mit Basis   und einem einzigen Output-Gatter und fragt, ob es eine Eingabe gibt, die dieses Gatter auf 1 setzt, d. h., ob es ein   gibt, so dass  . Das Erfüllbarkeitsproblem für Schaltkreise ist NP-vollständig.

Literatur

Bearbeiten
  • 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).