Alle Booleschen Funktionen können auf die Kombination von ein- und zweistelligen Booleschen Funktionen zurückgeführt werden. Die entsprechenden Schaltelemente, die logische Verknüpfungen zwischen anderen Schaltelementen herstellen, heißen Gatter (engl. gate).
Ein Gatter ist eine nicht weiter zerlegbare Funktionseinheit, die eine elementare Boolesche Funktion als physikalisches Bauelement realisiert.
Jedes Schaltnetz lässt sich durch die Kombination einer Grundmenge von Gattern (Bausteinsatz) realisieren.
Wichtige Gatter:
Beispiel einer zusammengesetzten Schaltung
Prinzipiell kann man jede Schaltung allein aus AND und NOT Gliedern oder allein aus OR und NOT Gliedern aufbauen. Für praktische Zwecke ist es sinnvoll, weitere elementare Bausteine zu verwenden. Wichtige solche Bausteine sind:
NOR (Realisierung der negierten Disjunktion, auch für mehrere Variablen)
Eine wichtige Schaltung ist auch der Multiplexer, auch als MUX-Glied bezeichnet.
Ein Multiplexer (Komponente, die eine Leitung für die gleichzeitige Übertragung mehrerer Signale
nutzt) realisiert eine Art „IF-THEN-ELSE“ Schaltung: Wenn c = 1 ist, dann ist z = x, ansonsten ist z = y;
mit anderen Worten: z = if c then x else y:
Variationen der elementaren Gatter
Die elementaren Gatter sind auch in leicht abgewandelter Version mit zusätzlichen Eingängen und eventuell auch mehreren Ausgängen verfügbar:
Die elektronischen Komponenten eines Rechners bestehen aus Schaltkreisen, die binär codierte Information verarbeiten. Sie enthalten physikalische Gatter und diese Transistoren, Dioden, Leiterbahnen, etc. Komplexere Schaltkreise enthalten Hunderte, Tausende solcher Gatter.
Ein Schaltkreis oder ein Schaltnetz ist eine – in der Regel – schleifenfreie Komposition von Verknüpfungsgliedern (Gattern), so dass keine Speicherwirkung auftritt.
Die Werte an den Ausgängen hängen nur von den Werten an den Eingängen ab. Ein Schaltnetz realisiert eine Schaltfunktion:
f: 2n → 2m
Die Funktionsweise eines Schaltkreises lässt sich durch ein System von Schaltfunktionen beschreiben. In der Absicht, einen Schaltkreis zu realisieren, ist als erstes die gewünschte Schaltfunktion zu spezifizieren. Der nächste Schritt besteht darin, geeignete Boolesche Ausdrücke dafür auszuwählen und diese in ein Schaltnetz aus logischen Gattern zu übertragen. Ein solches Schaltnetz definiert nur die "logische" Operation des Schaltkreises. Das zeitliche Verhalten der Bauelemente bleibt dabei unberücksichtigt. Den Übergang von einer Schaltfunktion zu einem sie darstellenden Schaltnetz nennt man (logische) Synthese der Schaltkreisfunktion.