Zur Themenwahl

Von der Logik zu Schaltkreisfunktionen

Aussagenlogik

Aussagen sind Sätze, die wahr oder falsch sein können. Diese Sätze können der gewöhnlichen Sprache entstammen oder auch der Sprache der Mathematik. Beispiele: ‘Heute ist Montag’ , 3=3. Aussagen werden im Folgenden mit großen Buchstaben bezeichnet: A,B,.... Es gibt die folgenden Grundverknüpfungen für Sätze A und B:

Wahrheitstafel

Logische Verknüpfungen sind Funktionen, denn sie ordnen den Kombinationen der Wahrheitswerte ‘wahr’ (1) und ‘falsch’ (0) von Variablen A,B,... jeweils einen Wahrheitswert ‘wahr’ (1) oder ‘falsch’ (0) zu. Eine Standardmöglichkeit logische Funktionen darzustellen sind Wahrheitstafeln. Das sind Funktionstabellen, die die Eigenschaften der logischen Funktionen übersichtlich darstellen:

Die Implikation und die Äquivalenz

Bei logischen Begründungsketten tritt die logische Folgerung oder Implikation häufig auf, sie wird geschrieben mit A → B und gesprochen ‘Aus A folgt B’. Eine noch stärkere Beziehung zwischen A und B wird durch die Äquivalenz, geschrieben A ↔ B, gesprochen ‘A äquivalent B’ angegeben. Die Wahrheitstafeln sind dafür Implikation und Äquivalenz können, wie alle logischen Funktionen, mit den logischen Grundverknüpfungen ausgedrückt werden. Am Beispiel der Implikation soll eine Methode erläutert werden, mit der man aus der Wahrheitstafel einer Funktion eine Darstellung mit den Grundverknüpfungen gewinnt.

Disjunktive Normalform einer logischen Funktion

Es werden alle Zeilen der Tabelle für die logische Funktion A → B, in denen der Wert 1 steht, betrachtet. Es gilt dann: A → B hat den Wert 1 für (A Λ B) oder ( ¬A Λ B) oder ( ¬A Λ ¬B) . Das kann man schreiben als (A Λ B) v ( ¬A Λ B) v ( ¬A Λ ¬B). Vereinbart man, dass Λ stärker bindet als v und benutzt man für A Λ B die Abkürzung AB, so erhält man A → B = AB v ¬A B v ¬A ¬B Diese Darstellung als Disjunktion von Konjunktionen nennt man disjunktive Normalform der logischen Funktion. Man kann diese Darstellung überprüfen: Die Wahrheitstafel für den gefundenen Ausdruck muss mit der Wahrheitstafel für die Implikation übereinstimmen. Um diese Überprüfung vorzunehmen, geht man in den folgenden Schritten in der Wahrheitstafel vor:

Ähnlich wie bei Zahltermen können logische Terme identisch umgeformt werden - dabei besteht eine Analogie von (·,+) zu ( Λ.v) Umformungen können zu einfacheren Termen führen. Am Beispiel des Terms für die Implikation sieht das so aus:

Tautologien

Es gibt logische Verknüpfungen, die völlig unabhängig von den Wahrheitswerten der einzelnen Satzvariablen wahr sind. Solche Aussagen sind also allein aus logischen Gründen wahr. Sie heißen Tautologien. Beispiele: Die beiden letzten Formeln heißen De Morgans Formeln. Nachweis für die letzte Tautologie:

Kontradiktionen

Das Gegenstück zur Tautologie ist die Kontradiktion. Ein Satz, der aus logischen Gründen, unabhängig von den Wahrheitswerten der einzelnen Satzvariablen, stets falsch ist. Die Negation einer Tautologie ist eine Kontradiktion. Beispiel:

Schaltkreisfunktionen oder Gatter

Erstaunlicherweise können alle Ergebnisse der Aussagenlogik direkt benutzt werden, um im Computer die benötigten Verknüpfungen von Dualzahlketten darzustellen und diese Darstellung dient dann als Grundlage für die technische Realisierung. Diese Verknüpfungen von Dualzahlketten heißen Schaltkreisfunktionen oder Gatter. Als Schaltzustände werden die Werte 0 und 1 gewählt - das entspricht in der technischen Realisierung z.B. 0 Volt und 5 Volt Spannung. Den einzelnen Dualstellen sind die Variablen A,B,... zugeordnet, die also die Werte 0 und 1 annehmen können. Am Beispiel der Addition von zwei einstelligen Dualzahlen wird eine Schaltkreisfunktion entwickelt.

Tabelle der Addition von zwei einstelligen Dualzahlen A und B

Für die beiden Dualstellen der Summe können nun genau in der Weise wie bei logischen Funktionen die Schaltkreisfunktionen mit den Grundverknüpfungen gebildet werden. Wenn für den Schaltkreis Bausteine für die Grundverknüpfungen ‘und’ , ‘oder’ , ‘nicht’ vorhanden sind, kann die Schaltkreisfunktion zur Addition aufgebaut werden. Ein Schaltbild für diese Schaltkreisfunktion wird mit den folgenden Grundelementen gezeichnet.

Grundelemente für Gatter

Gatter für die Addition von zwei Dualzahlen Bezeichnung: Halbaddierer (Rechts das Symbol für einen Halbaddierer)

Schaltbilder mit Funktionsanzeige in LOCAD

Als Bauelemente sind Schalter und Leds eingefügt Werden Dualzahlen mit mehreren Stellen addiert, so führt die alleinige Verwendung von Halbaddierern i.a. nicht zu korrekten Ergebnissen, da die Überträge aus vorangegangenen Additionen von Dualziffern nicht berücksichtigt werden. Für eine korrekte Addition von zwei Dualziffern A und B muss die Summe aus den Werten für A und B und dem Übertrag aus der vorangegangenen Addition gebildet werden. Das sich so ergebende Gatter heißt deshalb auch Volladdierer.

Volladdierer - Funktionstabelle

Aus der Tabelle entnimmt man die Funktionsterme (disjunktive Normalform) für s und ü: Mit den logischen Grundverknüpfungen könnte man Schaltungen für ü und s bauen. Hat man aber als Bauteile Halbaddierer, so ist es zweckmäßig, diese zum Bau der Schaltungen zu benutzen. Dafür müssen die Funktionsterme für ü und s so umgeschrieben werden (identisch umgeformt werden), dass man sieht, wie das geschehen kann. Es müssen die Logikterme für den Halbaddierer in den Termen für den Volladdierer auftreten. Es gilt für den Halbaddierer (zur Unterscheidung nun neue Bezeichnungen) Nun kann das Gatter für den Volladdierer mit dem Baustein Halbaddierer (mit einigem Geschick) gebaut werden:

Volladdierer-Gatter und Volladdierer-Symbol

Die Addition von 2 dreistelligen Dualzahlen mit Voll- und Halbaddierern

(mit LOCAD-Elementen wird 111 +101 = 1100 errechnet)

Zur Themenwahl