Boolesche Schaltkreise sind ein idealisiertes Modell echter elektronischer Schaltkreise. Als primitive Bausteine haben wir Boolesche Operatoren, auch Gatter (englisch gates) genannt, die mehrere (typischerweise ein oder zwei) Signale zu einem Ausgabe-Signal kombinieren. Die Signale können nur zwei Werte annehmen: wahr/falsch bzw. 1/0 bzw. true/false. Hier sehen Sie die drei üblichsten Gatter:

Von links nach rechts sind dies: das Und-Gatter (and-gate), Oder-Gatter (or-gate) und das Nicht-Gatter (not-gate). In C, C++ und Java kennen Sie diese Booleschen Operatoren als &&, || und !. Was diese Operatoren tun, können wir als Wahrheitstabelle darstellen. Wir listen alle Kombinationen für $x,y$ auf und schreiben in jede Zeile auch den Wert, den der Operator ausgibt.

Die dritte Zeile der mittleren Tabelle sagt beispielsweise aus, dass $1 \vee 0 = 1$ gilt.

Vielleicht wünschen Sie sich noch mehr Gates, zum Beispiel ein if-then-else-Gate mit drei Inputs $x,y,z$, welches $y$ ausgibt, wenn $x$ wahr ist und ansonsten $z$ ausgibt. So ein Gate können Sie sich einfach aus And, Or, Not bauen:

Jeder Schaltkreis berechnet eine Funktion (formale Definition weiter unten). Informell gesprochen, wenn wir Wahrheitswerte (0/1) in die Input-Gates reinstecken, dann fließen diese durch den Schaltkreis und werden von den AND/OR/NOT-Gates entsprechend ihrer Funktion kombiniert und werden schließlich an den Output-Gates ausgegeben:

Das if-then-else-Gate mit einer konkreten Belegung und einem Ausgabewert

Je nach Kontext kann es hilfreich sein, Gatter mit beliebig vielen Inputs zuzulassen, beispielsweise $x_1 \land x_2 \land \ldots \land x_n$ als ein Gate darzustellen:

Man bezeichnet dies als AND-Gate mit einem Fan-in von $n$. Das "normale" AND-Gate hat einen Fan-in von 2. Mit $\lor$- und $\oplus$-Gates geht das ganz analog. Für andere Gates (wie zum Beispiel ein if-then-else-Gate) würde das keinen Sinn machen. Größerer Fan-in ist aber nicht wirklich etwas neues unter der Sonne: Sie können jederzeit großen Fan-in durch kleinen simulieren:

Also als geschachteltes AND, oder aber in Form eines Binärbaums:

Schaltkreise, wie wir sie in diesem Kapitel betrachten, sind immer azyklisch. Das heißt insbesondere, das Dinge mit "Feedback-Schleifen" wie Flipflops eben keine Schaltkreis in unserem Sinn sind:

Das Flipflop zeigt ein interessantes Verhalten: wenn $\text{Reset} = 0$, $\text{Set} = 1$ ist, so ist der Ausgabe-Wert des unteren OR-Gates auf jeden Fall 1, und somit ist $\bar{Q} = 0$; somit sind wiederum beide Input-Werte des oberen OR-Gates 0 und $Q = 1$. Wenn $\text{Reset} = 1$, $\text{Set} = 0$, dann ist analog $Q = 0$, $\bar{Q} = 1$. Wenn $\text{Reset} = \text{Set} = 0$, dann leiten beide OR-Gates einfach die Werte der anderen, von rechts kommenden Kabel durch, und somit gilt $Q = \neg{\bar{Q}}$ und $\bar{Q} = \neg{Q}$; das heißt, die Werte, die zuvor bestanden, bestehen weiter. Das Flipflop implementiert somit einen 1-Bit-Speicher (die Kombination $\text{Set} = \text{Reset} = 1$ würde $Q = \bar{Q} = 0$ erzeugen und gilt als illegale Eingabe). Ein Flipflop hat somit einen inneren Zustand. Die Schaltkreise in diesem Kapitel haben keinen inneren Zustand: die Werte der Ausgabe-Gates sind vollständig durch die Werte der Input-Gates determiniert. Wir sind nun bereit für eine formale Definition von Schaltkreisen.

Oft haben wir es mit Schaltkreisen mit nur einem Output-Gate zu tun; in diesem Falle lassen wir die Beschriftung auch gerne weg, weil sie keine zusätzliche Information bringt. Wenn wir allen Input-Variablen eines Schaltkreises $C$ einen Wahrheitswert zugewiesen bekommen haben, dann können wir den Schaltkreis von "unten" (Input-Gates) nach "oben" (Output-Gates) auswerten, indem eben jeder mit OR/AND/NOT beschriftete Knoten den ihm zugeordnete Booleschen Operator auswertet. Es ist klar, dass der Schaltkreis $C$ eine Funktion $f_C : \{0,1\}^n \to \{0,1\}^m$ berechnet. Oft schreiben wir einfach $C : \{0,1\}^n \to \{0,1\}^m$.

Es ist auch nicht weiter überraschend, dass es Schaltkreise für die gleiche Funktion geben kann (sie haben für die Funktion $x_1 \land \ldots \land x_n$ auch bereits drei verschiedene Schaltkreise gesehen, und im Rahmen der obigen Übungsaufgabe wohl auch mehrere Schaltkreise, die das gleiche tun, entwickelt.