Logische Verknüpfung

Grundidee und Bedeutung

Eine logische Verknüpfung ist eine Operation der Booleschen Algebra. Mit ihr werden in der Aussagenlogik und in der Schaltalgebra aus einfachen Aussagen zusammengesetzte Aussagen gebildet. Dabei muss der Wahrheitswert der zusammengesetzten Aussage eindeutig durch die Wahrheitswerte der einzelnen Aussagen bestimmt sein. Eine Wahrheitstabelle, auch Wahrheitstafel genannt, definiert eine solche Verknüpfung.

Mehrere Eingangssignale, zum Beispiel 1, 2, 3 oder mehr, werden durch eine logische Verknüpfung zu einem Ausgangssignal zusammengesetzt. Auch 2 oder mehr Ausgangssignale sind möglich. Die Verknüpfung legt fest, welche logischen Zusammenhänge zwischen Eingängen und Ausgängen gelten.

Logische Verknüpfungen heißen auch Satzoperatoren. Ihre Operatoren werden Boolesche Operatoren genannt. Die Zeichen, mit denen logische Verknüpfungen dargestellt werden, heißen Junktoren. Die Definitionsmenge und die Zielmenge sind jeweils W={w, f}, wobei w für wahr und f für falsch steht. Andere Schreibweisen sind W={1, 0}, W={WAHR, FALSCH} und W={TRUE, FALSE}.

Arten und Anwendungen

Man unterscheidet logische Verknüpfungen danach, wie viele Aussagen oder Eingangssignale miteinander verbunden werden. Es gibt einstellige, zweistellige und höherstellige Verknüpfungen. Höherstellige Verknüpfungen, zum Beispiel dreistellige Verknüpfungen, sind von untergeordneter Bedeutung, weil sie sich durch ein- und zweistellige Verknüpfungen ausdrücken lassen.

Wichtige zweistellige logische Verknüpfungen sind Konjunktion, Disjunktion, Implikation und Äquivalenz. In der Digitaltechnik sind AND, OR, NOT, NOR und NAND die gängigsten logischen Grundschaltungen. Unter den einstelligen logischen Verknüpfungen gibt es nur eine nicht-triviale, nämlich die Negation.

Praktische Anwendungen gibt es unter anderem bei Suchoperatoren in Datenbanken, bei Anfragen an Suchmaschinen und in der Digitaltechnik. In der Digitaltechnik werden logische Verknüpfungen durch logische Schaltungen realisiert. Sie sind Grundelemente der Digitaltechnik, etwa beim Schaltungsentwurf und in der digitalen Steuerungstechnik.

Auch höhere Programmiersprachen verwenden logische Verknüpfungen. Meist kennen sie nur AND, OR und NOT; andere Verknüpfungen müssen aus diesen Bausteinen konstruiert werden. Programmiersprachen arbeiten nur mit zweistelligen logischen Ausdrücken. Mehrstellige logische Ausdrücke werden deshalb durch Kombination mehrerer zweistelliger Ausdrücke gebildet.

Zweistellige Verknüpfungen

Bei zwei logischen Variablen gibt es insgesamt 16 mögliche zweistellige Operatoren. Eine Wahrheitstabelle mit 2 Eingängen hat 4 Zeilen, weil es vier Kombinationen der Eingangssignale gibt. Daraus folgen 16 mögliche Ergebnisse, denn 2^{4} = 16. Jede der 16 möglichen zweiwertigen Verknüpfungen hat einen Namen.

Zu den zweistelligen Verknüpfungen gehören TRUE oder Tautologie: Das Ergebnis ist unabhängig von der Eingabe immer 1. Eine Tautologie wird in jedem Fall wahr, zum Beispiel A OR NOT A. Das Gegenstück ist FALSE oder Kontradiktion: Das Ergebnis ist unabhängig von der Eingabe immer 0. Außerdem gibt es die Identität von A oder B, bei der der Ausgang 1 ist, wenn der jeweilige Eingang 1 ist, sowie die Negation von A oder B.

AND, auch Konjunktion, liefert 1, wenn alle Eingänge 1 sind. NAND, der Sheffersche Strich, verhält sich umgekehrt zu AND. OR, auch Disjunktion, liefert 1, wenn ein oder zwei Eingänge 1 sind; mindestens ein Teilausdruck muss wahr sein, damit der ganze Ausdruck wahr ist. NOR, die Peirce-Funktion, ist eine Kombination aus OR und NOT und verhält sich umgekehrt zu OR.

XOR, auch Antivalenz oder exklusives OR, liefert 1, wenn die Eingänge unterschiedlich sind, also genau ein Eingang 1 ist. XNOR, auch Äquivalenz, ist das Gegenteil von XOR und liefert 1, wenn beide Eingänge identische Logikzustände haben. Inhibition ist ein AND mit einem invertierten Eingang. Subjunktion oder Implikation von A auf B ist wahr, wenn A falsch (0) ist oder B wahr (1) ist; die Replikation von B auf A ist wahr, wenn B falsch (0) ist oder A wahr (1) ist.

In der Digitaltechnik wird die Funktion logischer Verknüpfungen durch Logikgatter realisiert. Das logische Schaltsymbol kann nach EN 60617-12 dargestellt werden. Der Artikel merkt an, dass die IEC 60617-12-Symbolik von XOR- und XNOR-Gatter vertauscht sei und XOR keine Negation am Ende der Verknüpfung habe.

Computer und Kurzschlussauswertung

Höhere Computersprachen, besonders C, C++, C#, Java und PHP, kennen bei den logischen Operatoren AND und OR die abgekürzte Auswertung, auch Kurzschlussauswertung genannt. Sie dient zur Optimierung der Laufzeit und zur Vermeidung von Fehlern, die ohne die Abkürzung auftreten könnten, zum Beispiel bei x == 0 || a/x == 2.

Der Operator && bezeichnet die abgekürzte Auswertung der Konjunktion. Wenn die erste Eingangsvariable bereits FALSCH ist, muss die zweite nicht mehr betrachtet werden, weil das Ergebnis schon FALSCH sein muss. Soll keine abgekürzte Auswertung stattfinden, wird der Operator & verwendet.

Für die Disjunktion wird || als OR-Operator mit abgekürzter Auswertung verwendet. Der Operator | steht für die nicht abgekürzte Auswertung der ODER-Funktion. Bei OR steht das Endergebnis WAHR bereits fest, wenn die erste Eingangsvariable WAHR ist; die weitere Auswertung kann dann abgebrochen werden. Gründe für die unbedingte Auswertung beider Operanden können Seiteneffekte oder beabsichtigte Ausnahmebehandlung sein. In Visual Basic .NET werden Kurzschlussauswertungen durch AndAlso beziehungsweise OrElse erzeugt.

Drei Eingänge, ein Eingang und mehrere Ausgänge

Bei drei Eingangsvariablen A, B und C gibt es 8 mögliche Kombinationen, also 8 Zeilen in der Wahrheitstabelle. Es gibt 256 achtstellige Binärzahlen von 0000.0000 bis 1111.1111, denn 2^{8} = 256. Daher hat eine dreistellige logische Verknüpfung 256 mögliche verschiedene Ergebnisse. Nur wenige davon haben einen allgemeinverbindlichen Namen. Diese Aussagen gelten nur für binäre Logik, in der eine Aussage nur den Wert 0 oder 1 annehmen kann, nicht für dreiwertige oder ähnliche mehrwertige Logiksysteme.

Als Beispiel für eine dreistellige Verknüpfung wird ein Operator angegeben: (A AND B AND NOT-C) OR (A AND NOT-B AND C) OR (NOT-A AND NOT-B AND C). Er beschreibt eine zusammengesetzte Bedingung aus drei Variablen und ihren Negationen.

Bei einstelligen logischen Verknüpfungen gibt es vier Möglichkeiten. Die wichtigste nicht-triviale einstellige Verknüpfung ist die Negation, also die Umkehrung eines Wahrheitswerts.

Weitere Varianten entstehen, wenn eine Verknüpfung nicht nur ein Ergebnis, sondern mehrere Ergebnisse hat. In logischen Digitalschaltungen bedeutet das mehrere Ausgänge. Beispiele sind ein 1-aus-n-Decoder mit 2 Eingängen und 4 Ausgängen sowie ein Volladdierer mit 3 Eingängen und 2 Ausgängen.

Fuzzy-Logik

In der Fuzzy-Logik werden die logischen Operationen der Booleschen Algebra durch Fuzzy-Operationen ersetzt. Der Artikel nennt dies als Abgrenzung zur binären Booleschen Logik, in der nur die Werte wahr/falsch beziehungsweise 1/0 verwendet werden.