Wikipedia · einfach zusammengefasst · Stand
Boolescher Schaltkreis
In der theoretischen Informatik (insbesondere in der Komplexitätstheorie) ist ein boolescher Schaltkreis ein mathematisches Modell für digitale Schaltungen.
Inhalt5 Abschnitte
Grundidee und Aufbau
Ein boolescher Schaltkreis ist in der theoretischen Informatik, besonders in der Komplexitätstheorie, ein mathematisches Modell für digitale Schaltungen. Er verarbeitet boolesche Werte, also 0 und 1, und erzeugt daraus eine oder mehrere boolesche Ausgaben.
Formal ist ein n-Input-m-Output-boolescher-Schaltkreis über einer Basis Υ von Gattertypen ein gerichteter azyklischer Graph G=(V,E). „Gerichtet“ bedeutet, dass jede Kante eine Verarbeitungsrichtung besitzt; „azyklisch“ bedeutet, dass es keinen gerichteten Weg gibt, der zu seinem Ausgangspunkt zurückführt. Die Knoten werden als Gatter bezeichnet.
Der Schaltkreis besitzt n Input-Knoten i₁,i₂,…,iₙ ohne eingehende Kanten. Alle übrigen Knoten heißen interne Knoten. Jedem internen Knoten ist ein Gattertyp υ∈Υ zugeordnet. Seine Stelligkeit, also die Anzahl seiner Eingaben, stimmt mit dem In-Grad des Knotens überein. Falls die Reihenfolge der Argumente wichtig ist, wird auch die Reihenfolge der eingehenden Kanten festgelegt. Außerdem sind m Knoten o₁,o₂,…,oₘ als Output-Knoten markiert.
Eine häufig verwendete Basis ist Υ={∧,∨,¬}, die auch Standardbasis genannt wird. Mit diesen Gattertypen lassen sich alle booleschen Funktionen bilden.
Gattertypen
Gatter sind die Bestandteile eines booleschen Schaltkreises. Sie erhalten boolesche Eingaben und kombinieren diese zu einem booleschen Ausgabewert. Ein Gattertyp ist allgemein eine boolesche Funktion, die ein k-Tupel boolescher Werte auf einen booleschen Wert abbildet.
• Für jede Stelligkeit k gibt es ein AND-Gatter ∧ₖ. Es gibt genau dann 1 aus, wenn alle seine Eingaben den Wert 1 besitzen. Für k=2 schreibt man auch ∧, also ∧=∧₂.
• Für jede Stelligkeit k gibt es ein OR-Gatter ∨ₖ. Es gibt genau dann 1 aus, wenn mindestens eine Eingabe den Wert 1 besitzt. Für k=2 schreibt man auch ∨, also ∨=∨₂.
• Das Negations-Gatter ¬ hat genau eine Eingabe. Es gibt genau dann 1 aus, wenn seine Eingabe 0 ist.
Auswertung und berechnete Funktion
Für eine Eingabe X=(x₁,x₂,…,xₙ) wird jedem Knoten v∈V des Schaltkreises C ein Wahrheitswert gᵥ(X)∈{0,1} zugeordnet. Jeder Input-Knoten iⱼ erhält den entsprechenden Eingabewert xⱼ, also gᵢⱼ(X)=xⱼ.
Ein interner Knoten wird erst ausgewertet, nachdem alle seine direkten Vorgänger ausgewertet worden sind. Hat der Knoten v die k direkten Vorgänger u₁,…,uₖ und den Gattertyp υ∈Υ, so gilt:
gᵥ(X)=υ(gᵤ₁(X),…,gᵤₖ(X)).
Die vom gesamten Schaltkreis berechnete boolesche Funktion fasst die Werte der m Output-Knoten zusammen:
f_C(X)=(gₒ₁(X),…,gₒₘ(X)).
Ein Subschaltkreis eines internen Knotens v besteht aus allen Gattern, die Vorgänger von v sind, also aus allen Gattern, von denen ein gerichteter Pfad zu v führt. Der Grad einer Basis Υ ist die maximale Stelligkeit ihrer Gattertypen.
Ein Schaltkreis heißt monoton, wenn eine komponentenweise Vergrößerung der Eingabe von X=(x₁,…,xₙ) zu Y=(y₁,…,yₙ), also xⱼ≤yⱼ für 1≤j≤n, auch die Ausgabewerte nicht verkleinert: Für alle Ausgabekomponenten gilt f_C(X)ⱼ≤f_C(Y)ⱼ. Häufig bezeichnet man auch Schaltkreise, die ausschließlich aus AND- und OR-Gattern bestehen, als monotone Schaltkreise.
Maße und Komplexitätsklassen
Boolesche Schaltkreise sind ein wichtiges Werkzeug der Komplexitätstheorie. Mit der Schaltkreiskomplexität wird untersucht, welche Schaltkreise zur Berechnung von Funktionen nötig sind und wie aufwendig diese Schaltkreise sind.
Wichtige Komplexitätsmaße sind:
• Die Schaltkreisgröße (circuit size) ist die Anzahl der internen Knoten.
• Die Schaltkreistiefe (circuit depth) ist die maximale Länge eines Pfades von einem Eingabegatter zu einem Ausgangsgatter.
• Die Anzahl der Alternierungen gibt an, wie oft AND- und OR-Gatter entlang der betrachteten Struktur wechseln.
• Ingrad und Ausgrad bezeichnen die maximale Anzahl eingehender beziehungsweise ausgehender Kanten eines Knotens. Der Ingrad ist durch die gewählte Basis Υ beschränkt.
Auch bedeutende Komplexitätsklassen lassen sich mithilfe boolescher Schaltkreise definieren. Dazu gehören die Klasse NC mit der Hierarchie NCⁱ sowie die Klasse AC mit der Hierarchie ACⁱ.
Zentrale Entscheidungsprobleme
Beim Schaltkreis-Auswertungsproblem (Circuit Value Problem) sind ein boolescher Schaltkreis und ein Input-String gegeben. Der Input-String weist jedem Input-Gatter einen Wahrheitswert zu. Gesucht werden daraus die Werte der Output-Gatter. Das Entscheidungsproblem, ob ein Output-Gatter bei der gegebenen Eingabe wahr ist, ist P-vollständig.
Das Erfüllbarkeitsproblem für Schaltkreise (circuit satisfiability problem) betrachtet einen booleschen Schaltkreis C über der Basis Υ={∧,∨,¬} mit genau einem Output-Gatter. Gefragt wird, ob mindestens eine Eingabe existiert, die dieses Gatter auf 1 setzt. Formal wird also gefragt, ob es ein X mit f_C(X)=1 gibt. Dieses Problem ist NP-vollständig.
