Einführung in die Programmiermethoden und Sprachen der KI (3)

3. Teil: Programmieren in Logik

Einführung in die Problematik

Die Logik ist ein Zweig der Mathematik, der eigentlich nichts mit der Programmierung von Computern zu tun hat. Allerdings finden sich die Methoden der Logik in vielfacher Weise in jedem Computer wieder. Da ist zunächst einmal die Hardware des Computers: Jeder echte Hardware-Kenner weiß, daß das Zusammenspiel von Bussignalen nur durch eine sinnvolle Zusammenarbeit logischer Bausteine sinnvoll funktionieren kann. Diese Bausteine (sogenannte Gatter) werden heute in hochintegrierter Bauweise auf den Markt gebracht und erfüllen meist ein ganzes Bündel logischer Funktionen. Uns interessiert hier weniger die physikalische Funktionsweise dieser Bausteine, sondern die dahintersteckende mathematische Logik. Und natürlich darf die Frage nicht zu kurz kommen, welche mathematische Umformungsarbeit die KI dem geplagten Entwicklungsingenieur bei der Erstellung logischer Bausteine abnimmt.

Grundlagen der Aussagenlogik

Unter der Aussagenlogik versteht man jenen Teil der Logik, der die Verknüpfung von Aussagen zum Thema hat. Die Verknüpfung der einzelnen Aussagen erfolgt durch Junktoren, die Verknüpfungsoperatoren. Es läßt sich zeigen, daß alle Verknüpfungen von Aussagen durch die elementare Junktoren dargestellt werden können: Negation (Zeichen: ~), Konjunktion (Zeichen: &, Bedeutung: und) und Disjunktion (Zeichen: v, Bedeutung: oder). Aussagen sind für den Logiker, was für den Programmierer die Booleschen Variablen sind: Objekte, die nur den Zustand Wahr (True) oder Falsch (False, Fail, Nil...) annehmen können. Ob eine Aussage den Wahrheitswert W oder F besitzt, interessiert den Logiker herzlich wenig. Genausowenig, wie es den Programmierer interessiert, ob eine Boolesche Variable im konkreten Fall den Wert True oder False besitzt. Für beide ist nur die Frage interessant: Was wäre wenn? Diese Frage beantwortet der Logiker gerne mit einer sogenannten Wahrheitstafel. Abb. 1 zeigt die Wahrheitstafeln der drei Elementarjunktoren. Zuerst zur Negation: Wenn die Aussage A den Wahrheitswert W besitzt, dann hat die Negation von A den Wert F. Wenn aber die Aussage A den Wahrheitswert F besitzt, dann hat die Negation von A den Wert W. Wobei es, wie gesagt, völlig belanglos ist, ob die Aussage A wahr oder falsch ist und wie sie lautet. Für den Logiker ist somit die Aussage der Mond ist aus Käse von gleicher Bedeutsamkeit wie die Wahlaussagen der Parteien bei der letzten Bundestagswahl. Analog liest sich die Wahrheitstafel für die Konjunktion (Und-Funktion): Wenn die Aussage A wahr ist und die Aussage B wahr ist, dann ist die Aussage A und B wahr. Sonst ist die Aussage A und B nicht wahr. Hierzu ein Beispiel. Aussage A: Adam liebt Eva. Aussage B: Eva liebt Adam. Der Wahrheitsgehalt der einzelnen Aussage ist für uns zunächst uninteressant. Uns interessiert als angehende Logiker nur die Frage, wann die Aussage A und B wahr ist. Die Aussage A und B (Adam liebt Eva und Eva liebt Adam) ist nur dann wahr, wenn die Aussage A wahr ist (also Adam wirklich Eva liebt) und die Aussage B wahr ist (also Eva wirklich Adam liebt). Sollte eine der Aussagen nicht wahr sein, dann ist auch die Aussage A und B nicht wahr.

Abbildung 1: Wahrheitstafeln logischer Verknüpfungen

Abbildung 2: Schaltbilder der elementaren Logikgatter

Anwendung in der Digitaltechnik

Natürlich haben die Praktiker längst erkannt, daß die Wahrheitstafeln der logischen Verknüpfung in Abb. 1 nichts anderes sind als die Verknüpfungstafeln logischer Gatter. Üblicherweise trägt man dort aber als Werte nicht W und F, sondern 1 und 0 ein, stellvertretend für Spannung ein und Spannung aus. Abb. 2 zeigt die Schaltsymbole der zu den logischen Elementarverknüpfungen gehörenden Gatter. Die hier verwendeten Schaltzeichen entsprechen zwar nicht mehr der DIN-Norm, man findet sie aber in allen gängigen Schaltungen der Digitaltechnik und der Gatterhersteller wieder. In einem Computer gibt es eine endlose Vielzahl verschiedener logischer Funktionen, die erfüllt werden müssen. Sie können alle aus den in Abb. 1 zusammengefaßten elementaren logischen Verknüpfungen zusammengesetzt werden. Nehmen wir als Beispiel einen Ein-Bit Halbaddierer. Das ist eine Schaltung, die zwei Ein-Bit-Zahlen addiert. Abb. 3 zeigt die möglichen Ergebnisse dieser Addition zweier Binärzahlen sowie die zugehörige Schaltung und die logischen Funktionen S(RA,B) und U(A,B). S(A,B) bedeutet die Summe der beiden Ein-Bit Binärzahlen, U(A,B) den Übertrag der Summe. Der Sinn des Übertrags wird klar, wenn man sich veranschaulicht, daß 1b + 1b = 10b ist, womit zur Darstellung aller möglichen Ergebnisse der Addition zweier Ein-Bit Zahlen Zwei-Bit Zahl erforderlich ist, deren niederwertiges Bit durch die Funktion S(A,B) und deren hochwertiges Bit durch die Funktion U(A,B) dargestellt wird.

Schaltungsalgebra - angewandte Aussagenlogik

Hat man erst einmal die logische Funktion gefunden, die für eine bestimmte Aufgabe erforderlich ist, dann läßt sie sich mit Hilfe der Gatter nachbauen. Bei der heutigen hohen Integrationsdichte von Bauelementen ist es allerdings verständlich, wenn die Hersteller nicht mehr einzelne Gatter verkaufen. Selbst in der verstaubt anmutenden TTL-Logik waren in einem 14-poligen DIL-Gehäuse mindestens vier Logikgatter enthalten. Und dann kann es Vorkommen, daß eine Schaltung durch geschickte Wahl von Bauelementen mit weniger Bausteinen auskommt als beim unüberlegten Einsatz der Standardgatter. Damit die Schaltung genauso funktioniert wie vorgesehen, muß eine äquivalente Umformung der logischen Funktion vorgenommen werden, d. h. es müssen folgende Gesetze beachtet werden:

Abbildung 3: 1-Bit Halbaddierer

  1. A v ~ A (Es gibt nur 2 Möglichkeiten für A)

  2. ~ (A & ~ A) (A kann nicht gleichzeitig wahr und nicht wahr sein)

  3. ~~A < = > A (Das Prinzip der doppelten Verneinung)

  4. A & (B v C) < = > (A & B) v (A & C) (Distributivgesetz)

  5. A v (B & C) < = > (A v B) & (A v C) (Distributivgesetz)

  6. ~(A & B) < = > ~A v ~B (Verneinungsgesetz)

  7. ~(A v B) < = > ~A & ~B (Verneinungsgesetz)

Das Zeichen „ < = > “ bedeutet, daß der Ausdruck auf der linken Seite durch den auf der rechten Seite ersetzt werden darf und umgekehrt. Berücksichtigt man diese Gesetze, so erhält man mit Sicherheit wieder eine Schaltung, die genauso funktioniert wie die Ausgangsschaltung. Ein einfaches Beispiel einer Umformung möchte ich am Beispiel des NAND-Gatters erläutern. Abb. 4 zeigt Schaltzeichen, Verknüpfungstafel und die logische Funktion dieses Gatters sowie des XODER-Gatters, das die exklusiv-Oder-Funktion darstellt. Das Verblüffende an diesen Gattern ist, daß sich alle drei logischen Grundfunktionen mit Hilfe dieser Gatter nachbilden lassen und deshalb alle logischen Funktionen überhaupt. Abb. 5 zeigt, wie die drei logischen Grundverknüpfungen durch die NAND-Funktion dargestellt werden und wie sich die Funktionen mit Hilfe der Gesetzt 1-7 ableiten lassen (die Nummern über dem „ < = > “-Zeichen entsprechen dem verwendeten Gesetz). Natürlich werden die äquivalenten Umformungen (also Umformungen unter Benutzung der Gesetze 1-7) immer komplizierter, je komplexer die zu realisierenden logischen Funktionen werden. Vielleicht versuchen Sie mal, den Ein-Bit-Halbaddierer nur aus NANDs aufzubauen?

Abbildung 4: Die Universalfunktionen NAND und XODER und ihre Schaltzeichen

Abbildung 5: Symbole, NAND-Form und Herleitung derselben für die logischen Grundfunktionen

Abbildung 6: 1-Bit Halbaddierer in NAND-Form. Schraffiert: der Übertrag

Abbildung 7: Umformung des 1-Bit Halbaddierers

Abbildung 8: Übersetzungen der grammatischen Regeln des Programms Listing2

Logik als Problemlösungsmaschine

Der Fortschritt in der Mikroelektronik würde wahrscheinlich bei weitem nicht so abenteuerlich schnell verlaufen, wenn es nicht gelungen wäre, die Schaltungsalgebra zu mechanisieren. Die beiden heutigen Beispielprogramme in LISP und PROLOG zeigen, wie der Computer die äquivalenten Umformungen selbständig vornehmen kann. Listing 1 zeigt die LISP-Variante. Der Benutzer muß die Schaltung als Liste eingeben. Die Ausgabe erfolgt ebenfalls in Listenform. Abb. 7 zeigt das Protokoll der Umformung für den Ein-Bit-Halbaddierer. Auf Abb. 6 sind die beiden Ausgangslisten wieder von Hand zu dem vertrauten Bild einer Gatterschaltung zusammengefaßt. Darin ist die Übertragsschaltung schraffiert wiedergegeben. Die Funktionsweise des LISP-Programmes ist relativ einfach zu erklären. Jede Schaltung wird in Präfix-Notation als Liste im Aufruf der Funktion nandform angegeben. Mit Hilfe der cond-Entscheidung wird dann das erste Argument der Liste untersucht. Je nach dem ersten Argument (dem Namen des Gatters) wird dann eine neue Liste in Präfix-Notation gebildet, die der Substitution gemäß Abb. 5 entspricht. Das NICHT-Gatter wird beispielsweise ersetzt durch ein NAND-Gatter, dessen zweiter Eingang ständig „Wahr“ gesetzt wird. Man beachte, daß die beiden folgenden Argumente der Liste wieder jeweils rekursiv einer Umformung unterworfen werden, bis als Abbruchskriterium feststeht, daß das zweite bzw. dritte Argument (also die am Eingang des Gatters anliegenden Eingangsschaltungen) atomat sind. Dann nämlich besteht die „Eingangsschaltung“ aus dem Namen der Eingangssignale, diese sind im Gegensatz zu den in Präfix-Listennotation eingegebenen Schaltungen LISP-Atome. Die Funktionen argument1, argument 2 und argument3 sind nur der besseren Lesbarkeit wegen gewählt. Dieses LISP-Programm stellt also ein kleines Expertensystem dar, das in der Lage ist, mit dem Wissen von Abb. 5 alle logischen Funktionen durch NAND-Bausteine technisch zu realisieren.

Logik logisch programmiert

Ein Blick genügt, um zu erkennen, daß das gleiche Problem in PROLOG viel kürzer und übersichtlicher zu lösen ist. Das Listing 2 benutzt allerdings grammatische Regeln, die ich in meiner kurzen Einführung in PROLOG (in der Februar-Ausgabe dieser Zeitschrift) ausgelassen habe. Die Bedeutung dieser grammatischen Regeln ist einfach zu verstehen. Das Argument des Prädikates äquivalent ist ein Term, der durch die äquivalente NAND-Form ersetzt werden soll. Diese befindet sich rechts von „--> “, dem Zeichen für eine grammatische Regel. In diesem Programm benutze ich ein spezielles TOY-PROLOG-Prädikat, phrase/2, das in der Edinburgh-1C-Syntax fehlt. Mit diesem Prädikat geht die Auswertung der grammatischen Regel besonders einfach. Das erste Argument dieses Prädikates ist die linke Seite einer grammatischen Regel, das zweite Argument die entsprechende Übersetzung (rechte Seite). Ich möchte trotzdem dieses einfache Beispiel zum Anlaß nehmen, die Interpretation einer grammatischen Regel durch den PROLOG-Interpreter etwas genauer zu untersuchen. Die syntaktische Struktur einer grammatischen Regel in der BNF entnehmen Sie bitte wieder der TOY-PROLOG-Dokumentation. Übersetzt liest Sie sich etwa so: Eine grammatische Regel besteht aus einer linken und einer rechten Seite, getrennt durch „--->“. Die linke Seite besteht aus einem Funktor, der übersetzt werden soll. Und da er übersetzt wird, also noch nicht das Ende der Übersetzung darstellt, heißt er nicht terminal. Auf der rechten Seite der grammatischen Regel steht das, wodurch das nicht terminale Symbol auf der linken Seite letztlich ersetzt wird, aso ein terminales Symbol, bzw. Alternativen von terminalen Symbolen. Bei rekursiven Aufrufen von grammatischen Regeln kann es auch Vorkommen, daß die rechte Seite auch nicht terminale Symbole enthält. Wer nun das Programm Listing 2 mit Hilfe des consult/1-Prädikates geladen hat und den TOY-Editor startet, um sich beispielsweise die erste Klausel des Prädikates äquivalent anzuschauen, wird (wenn er PROLOG nicht kennt) eine Überraschung erleben. Der Versuch das Prädikat äquivalent/1 zu editieren, scheitert, weil PROLOG eine grammatische Regel übersetzt. Bei dieser Übersetzung wird aus dem Prädikat äquivalent/1 das Prädikat äquivalent/3, die Arität des Prädikates ist also angewachsen. Abb. 8 zeigt den Aufruf des Editors für das Prädikat äquivalent/3. Man erkennt ganz rechts die Argumentliste, als mittleres Argument die Variable X2 bzw. X3 und ganz links eine Liste, die sich zusammensetzt aus der Übersetzung (Kopf) und der Variablen X2 bzw. X3 (Rest). Die mittlere Variable heißt die Startproduktion. Mit ihr kann man u. U. einen nicht zu verändernden Startterm vorgeben, der im Ergebnis einfach angehängt wird. Statt die Auswertung der grammatischen Regel dem Prädikat phrase/2 zu überlassen, wäre auch z. B. die Anfrage äquivalent(X,[ ], [nicht,a,b]). möglich, die X mit der Übersetzung instanziert. Abb. 9 zeigt das Protokoll der Umformung des Ein-Bit Halbaddierers in die NAND-Form. Die Übertragungsfunktion ist auch hier wieder schraffiert unterlegt. Für die Summenfunktion S(A,B) sind in Abb. 9 und Abb. 7 jeweils zwei äquivalente Formulierungen angegeben:

S(A,B) = ((~A) & B) v (A & (~B)) < = > S(RA,B) = (~U(A,B)) & (A v B)

Die Umformung ist etwas langwierig und soll hier nicht ausgeführt werden. Aber durch äquivalente Umformung ist es damit gelungen, pro Halbaddierer ein NAND-Gatter zu sparen, wie Sie leicht in Abb. 7 und 9 nachzählen können.

Abbildung 9: Umformung des 1-Bit Halbaddierers in PROLOG

Ausblick

Auch im nächsten Beitrag werde ich mich wieder mit der Logik beschäftigen. Wer sich in der Zwischenzeit einige Anregungen über Logik und künstliche Intelligenz holen möchte, dem sei das amüsante und lesenswerte Buch von D. R. Hofstadter empfohlen. Für tiefergehende Beschäftigung mit dem Thema Logik als Programmiersprache ist Kowalskis Arbeit in englischer Sprache zu empfehlen.

Literatur

Hofstadter, D. R. Gödel, Escher, Bach: Ein endlos geflochtenes Band. Stuttgart: Klett-Cotta, 1985.

Kowalski, R. Logic for Problem Sol-ving. Elsevier North Holland Inc., 1979.

Sarnow, K. PD-PROLOG Review. ST-Computer 2/87

(defun nandform (formel) 
    (cond
        ((atom formel) formel) 
        ((eq (argument1 formel) ’nand)
            (list ’nand
                (nandform (argument2 formel))
                (nandform (argument3 formel))) ) 
        ((eq (argument1 formel) 'nicht)
            (nandform (list 'nand
                (argument2 formel) t)) )
        ((eq (argument1 formel) 'und)
            (nandform (list 'nicht 
                (list 'nand
                    (argument2 formel) 
                    (argument3 formel)))) )

        ((eq (argument1 formel) 'oder)
            (nandform (list 'nand
                (list 'nicht (argument2 formel))
                (list 'nicht (argument3 formel)))) )
        ((eq (argument1 formel) 'xoder)
            (nandform (list 'und
                (list 'nand (argument2 formel) (argument3 formel)) 
                (list'nand (list 'nicht (argument2 formel))
                            (list 'nicht (argument3 formel)))
                )
            )
        )
    )
)

(defun argument1 (liste)
    (car liste))

(defun argument2 (liste)
    (car (cdr liste)))

(defun argument3 (liste)
    (argument2 (cdr liste)))

Abbildung 10: Umformung des 1-Bit Halbaddierers in LISP (BOOLE.LSP)



Aus: ST-Computer 05 / 1987, Seite 92

Links

Copyright-Bestimmungen: siehe Über diese Seite