Boolescher Schaltkreis

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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

Formale Definitionen

[Bearbeiten | Quelltext 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 | Quelltext 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 | Quelltext 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

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

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 | Quelltext 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 | Quelltext 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 | Quelltext 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 | Quelltext 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.

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