Logikfunktionen

Logikfunktionen bezeichnen in der Informatik und Logik Funktionen, die Wahrheitswerte als Eingaben akzeptieren und einen Wahrheitswert als Ausgang liefern. Formal handelt es sich um Abbildungen F: {0,1}^n -> {0,1}, wobei n die Anzahl der Eingänge ist. Die Eingangsvariablen nehmen in der Praxis die Werte 0 oder 1 an, und der Ausgang hat ebenfalls den Wert 0 oder 1. Typische Beispiele sind die Grundfunktionen AND (A ∧ B), OR (A ∨ B) und NOT (¬A). Kombiniert man diese, entstehen komplexe Logikfunktionen, die in digitalen Schaltungen implementiert werden.

Eine Logikfunktion lässt sich durch Truth Tables, boolesche Gleichungen oder Normalformen ausdrücken. In der Wahrheitstabelle ist für jede Eingabekombination der Ausgang angegeben. In Normalformen lassen sich Funktionen als Disjunktive Normalform (DNF, Summe von Min-Termen) oder Konjunktive Normalform (KNF, Produkt von Max-Termen) darstellen. Jedes n-stellige Logikfunktion lässt sich als Summe von Min-Termen oder als Produkt von Max-Termen darstellen.

Funktionale Vollständigkeit bezeichnet die Eigenschaft, dass eine Menge von Funktionen jede Boolesche Funktion ausdrücken kann. Beispiele sind NAND allein oder NOR allein. XOR wird häufig zur Ermittlung von Parität eingesetzt und lässt sich aus den Grundoperationen darstellen, ist aber an sich nicht allein funktionsvollständig.

Anwendungen finden Logikfunktionen in digitalen Schaltungen, der Computerarchitektur, der Logikoptimierung, der Fehlererkennung sowie der Compiler- und Protokolltheorie. Verwandte Begriffe sind Boolesche Algebra, Schaltkreise, Karnaugh-Karten und Schaltungsentwurf.