Logische Verknüpfung

Logische Verknüpfungen sind Operationen der Booleschen Algebra. Mit Hilfe der logischen Verknüpfungen lassen sich in der Aussagenlogik und Schaltalgebra aus einfacheren Aussagen kompliziertere Aussagen zusammensetzen. Dabei muss der Wahrheitswert der zusammengesetzten Aussage durch die Wahrheitswerte der enthaltenen einfacheren Aussagen eindeutig bestimmt sein, beispielsweise durch eine Wahrheitstabelle (Wahrheitstafel). Eine Wahrheitstabelle ist die Definition einer logischen Verknüpfung. Mehrere Eingangssignale (1, 2, 3 oder mehr) werden mittels logischer Verknüpfung zu einem Ausgangssignal (auch 2 oder mehr Ausgangssignale sind möglich) zusammengesetzt. Die logische Verknüpfung definiert die Gesetzmäßigkeiten und logische Zusammenhänge zwischen Eingangssignal und Ausgangssignal.

Verknüpfungsarten

Logische Verknüpfungen werden auch Satzoperatoren genannt. Die Operatoren der logischen Verknüpfung werden Boolesche Operatoren genannt. 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.

Bild 1 – die ersten 8 logischen Verknüpfungen; A und B sind die Eingänge (auch als E₁ und E₂ bezeichnet oder als x₀ und x₁), die nummerierten Spalten sind die Ausgänge der verschiedenen logischen Verknüpfungen (auch als A bezeichnet oder als y);
1. Kontradiktion
2. Konjunktion (AND-Verknüpfung)
3. Inhibition (AND-Verknüpfung mit Eingangsnegation)
4. Identität von a
5. Inhibition (AND-Verknüpfung mit Eingangsnegation)
6. Identität von b
7. Antivalenz (XOR-Verknüpfung)
8. Disjunktion (OR-Verknüpfung)

Bild 2 – die letzten 8 logischen Verknüpfungen; die Spalte 9 bis 16 stellt die Definition der jeweiligen logischen Verknüpfung dar;
9. Peirce-Funktion (NOR-Verknüpfung)
10. Äquivalenz (NXOR-Verknüpfung)
11. Negation von b
12. Implikation aus b (OR-Verknüpfung mit Eingangsnegation)
13. Negation von a
14. Implikation aus a (OR-Verknüpfung mit Eingangsnegation)
15. Sheffer-Funktion (NAND-Verknüpfung)
16. Tautologie

In Analogie zum mathematischen Verknüpfungsbegriff spricht man von einstelligen (Bild 5) und zweistelligen (Bild 1 und 2) Verknüpfungen – je nachdem, wie viele Aussagen zusammengesetzt werden. Höherstellige Verknüpfungen (beispielsweise dreistellige Verknüpfung – Bild 3 und 4) sind hier von untergeordneter Bedeutung, weil sie sich durch ein- und zweistellige Verknüpfungen ausdrücken lassen. Die Symbole, mit denen die logischen Verknüpfungen ausgedrückt werden, nennt man Junktoren.

Unter den einstelligen logischen Verknüpfungen gibt es nur eine nicht-triviale, nämlich die Negation.

Praktische Anwendung finden die logischen Verknüpfungen unter anderem als Suchoperatoren bei Datenbanken, Anfragen an Suchmaschinen und in der Digitaltechnik. Die praktische Realisierung von logischen Verknüpfungen in der Digitaltechnik erfolgt durch logische Schaltungen. Logische Verknüpfungen sind die Grundelemente der Digitaltechnik – unter anderem beim Schaltungsentwurf oder in der digitalen Steuerungstechnik.

Eine weitere praktische Anwendung der logischen Verknüpfungen besteht bei höheren Programmiersprachen, die meistens nur die Verknüpfungen AND, OR und NOT kennen, so dass die anderen logischen Verknüpfungen aus diesen drei Bausteinen konstruiert werden müssen. Programmiersprachen arbeiten nur mit zweistelligen logischen Ausdrücken. Mehrstellige logische Ausdrücke müssen ebenfalls durch Kombination mehrerer zweistelliger logischer Ausdrücke gebildet werden.

Die Definitionsmenge und die Zielmenge der logischen Verknüpfung sind jeweils W={w, f}, wobei ‚w‘ für wahr steht und ‚f‘ für falsch. Andere Schreibweisen sind:

• W={1, 0},
• W={WAHR, FALSCH},
• W={TRUE, FALSE}.

Zweistellige logische Verknüpfung

Wenn man zwei logische Variablen miteinander kombiniert, dann sind insgesamt 16 verschiedene Ergebnisse möglich. Eine Funktionstabelle mit zweistelligen logischen (Bild 1) Verknüpfungen (2 Eingänge) hat insgesamt vier Zeilen, also vier verschiedene Kombinationsmöglichkeiten der Eingangssignale. Folglich sind 16 verschiedene Ergebnisse möglich (2⁴ = 16) – Bild 1 und 2. Jede der 16 möglichen zweiwertigen Verknüpfungen hat einen Namen. Es gibt 16 mögliche zweistellige Operatoren.

Die Spalten 1 bis 8 (Bild 1) stellen symmetrisch die Negationen der Spalten 9 bis 16 (Bild 2) dar. In den übrigen Bildern wird in der Mitte oben das logische Schaltsymbol nach DIN 40900 dargestellt, rechts die elektrische Schaltung und in der Mitte unten die Wahrheitstabelle; links unten befindet sich das Karnaugh-Veitch-Diagramm, links oben sind die disjunktive Normalform, die konjunktive Normalform und ggf. eine weitere Normalform abgebildet.

In der Digitaltechnik wird die Funktion logischer Verknüpfungen durch Logikgatter realisiert; im Artikel Logikgatter sind auch die anderen gebräuchlichen Schaltsymbole dargestellt.

Tabelle 1: Binäre Verknüpfungen

Bild 1, Spalte 1: FALSE (unabhängig von der Eingabe ist das Ergebnis immer Null) – Kontradiktion	Bild 1, Spalte 2: AND (Konjunktion) – Der Ausgang ist 1, wenn alle Eingänge 1 sind.
Bild 1, Spalte 3: Inhibition - Ein AND mit einem invertierten Eingang	Bild 1, Spalte 4: Identität
Bild 1, Spalte 5: Inhibition - Ein AND mit einem invertierten Eingang	Bild 1, Spalte 6: Identität
Bild 1, Spalte 7: XOR (Antivalenz, exklusives OR) – Der Ausgang ist 1, wenn die Eingänge unterschiedlich sind. – Wenn beide Eingänge unterschiedliche Logikzustände haben, dann wird am Ausgang 1 ausgegeben. – Nur wenn genau ein Eingang 1 ist, ist der Ausgang 1.	Bild 1, Spalte 8: OR (Disjunktion) – Der Ausgang ist 1, wenn ein oder zwei Eingänge 1 sind – Es muss mindestens 1 Teilausdruck wahr sein, damit der ganze Ausdruck wahr ist.
Bild 1, Spalte 9: NOR (Peirce-Funktion) – Kombination aus hintereinandergeschaltetem OR und NOT – Am Ausgang liegt 0 an, wenn an mindestens einem der Eingänge 1 anliegt. – NOR verhält sich umgekehrt zu OR.	Bild 1, Spalte 10: XNOR (Äquivalenz) – XNOR ist das Gegenteil von XOR, also eine Kombination aus hintereinandergeschaltetem XOR und NOT. – Wenn beide Eingänge identische Logikzustände haben, dann wird am Ausgang 1 ausgegeben.
Bild 1, Spalte 11: Negation von B.	Bild 1, Spalte 12: Implikation (von B auf A) – Subjunktion – Wenn B falsch (0) ist oder A wahr (1) ist, dann ist das Ergebnis wahr.
Bild 1, Spalte 13: Negation von A.	Bild 1, Spalte 14: Implikation (von A auf B) – Subjunktion – Wenn A falsch (0) ist oder B wahr (1) ist, dann ist das Ergebnis wahr.
Bild 1, Spalte 15: Shefferscher Strich (NAND)	Bild 1, Spalte 16: TRUE (unabhängig von der Eingabe ist das Ergebnis immer „Eins“) – Tautologie – eine Tautologie wird in jedem Fall wahr. Es gibt unendlich viel Tautologien – beispielsweise: A OR NOT A.

Logische Verknüpfung in Computersprachen

Höhere Computersprachen, insbesondere C, C++, C#, Java, PHP, kennen die abgekürzte Auswertung (Kurzschlussauswertung) der logischen Operatoren für AND bzw. OR. Die abgekürzte Auswertung wird zur Optimierung der Laufzeit benutzt, sowie (durch die bedingte Ausführung des zweiten Operanden) zur Vermeidung von Fehlern, die ohne die Abkürzung auftreten würden (z.B. x == 0 || a/x == 2). Der Operator „&&“ (AND) bezeichnet die abgekürzte Auswertung der Konjunktion. Wenn bereits die erste Eingangsvariable (A) FALSCH, dann muss B nicht mehr näher betrachtet werden, da das Ergebnis bereits bekannt ist – es muss FALSCH sein. Soll auf die abgekürzte Auswertung verzichtet werden, dann wird der Operator "&" verwendet. Analog wird für die Disjunktion der Operator "||" (OR) für die abgekürzte Auswertung und der Operator "|" für die nicht abgekürzte Auswertung der ODER-Funktion verwendet. Bei der ODER-Funktion steht das Endergebnis WAHR bereits fest, wenn die erste Eingangsvariable (A) WAHR ist. Die weitere Auswertung der logischen Verknüpfung kann dann abgebrochen werden.

Weitere logische Verknüpfungen in Computersprachen, allerdings ohne abgekürzte Auswertung, sind:

• exklusives ODER „^“,
• bitweises UND „&“,
• bitweises ODER „|“.

Dreistellige logische Verknüpfung

Bild 3

Bild 4

Bei drei Eingangsvariablen (A, B, C) gibt es 8 mögliche Kombinationen (die Tabelle hat 8 Zeilen). Es gibt 256 achtstellige Binärzahlen von 0000.0000 bis 1111.1111 (2⁸ = 256). Folglich hat eine dreiwertige logische Verknüpfung 256 mögliche verschiedene Ergebnisse. Die wenigsten von ihnen haben einen allgemeinverbindlichen Namen. Bild 3 und 4 zeigen Anfang und Ende der 256 möglichen Kombinationen.

Obige Aussagen treffen nur für die binäre Logik zu, in der also eine Aussage nur den Wert 0 oder 1 annehmen kann, nicht jedoch für dreiwertige oder ähnliche mehrwertige Logiksysteme.

Beispiel für eine dreistellige logische Verknüpfung:

A B C A*B*C w w w f  w w f w  w f w w  w f f f  f w w f  f w f f  f f w w  f f f f

Operator:(A AND B AND NOT-C) OR (A AND NOT-B AND C) OR (NOT-A AND NOT-B AND C)

Einstellige logische Verknüpfung

Bild 5

Bild 5 zeigt alle vier Möglichkeiten einer einstelligen logischen Verknüpfung.

Mehrere logische Ausgänge

Weitere Variationsmöglichkeiten entstehen, wenn es statt eines Ergebnisses (bei logischen Digitalschaltungen: ein Ausgang) mehrere Ergebnisse (bei logischen Digitalschaltungen: mehrere Ausgänge) gibt – beispielsweise beim 1-aus-n-Decoder (2 Eingänge, 4 Ausgänge) oder Volladdierer (3 Eingänge, 2 Ausgänge).

Fuzzy-Logik

In der Fuzzy-Logik werden die logischen Operationen der Booleschen Algebra durch Fuzzy-Operationen ersetzt.

Literatur

• Klaus Beuth: Digitaltechnik – Elektronik 4, 12. Auflage, 2003, Vogel Fachbuchverlag, ISBN 3-802-31958-3