Gatter
Jede Schaltfunktion fSchalt : {0,1}n -> {0,1}m kann durch die Kombination von m n-stelligen Booleschen Funktionen realisiert werden.
Alle Booleschen Funktionen können auf die Kombination von ein- und zweistelligen BFen zurückgeführt werden, s. Operatorenbasen. Die entsprechenden Schaltelemente heißen Gatter.
Def. Gatter: Ein Gatter ist eine nicht weiter zerlegbare Funktionseinheit, die eine elementare Boolesche Funktionen als physikalisches Bauelement realisiert.
Es gilt: Jedes Schaltnetz läßt sich durch die Kombination einer Grundmenge von Gattern (Bausteinsatz) realisieren.
- NOT, AND, OR (Boolescher Satz)
- NAND (Realisierung der negierten Konjunktion, auch für mehrere Variable)
- NOR (Realisierung der negierten Disjunktion, auch für mehrere Variable)