Einführung in die Logik

Einführung in die Logik

Prof. Janis Voigtländer � Folienversion: 10.01.2022, 15:11:28 +00:00

Einführung in die Logik

Organisatorisches

Logik Organisatorisches 2

Mit wem haben Sie es hier zu tun?

Dozent: Prof. Dr. Janis Voigtländer

Raum LF 233

E-Mail: [email protected]

Übungsleitung und Tutorium: M.Sc. Oliver Westphal

Raum LF 232

E-Mail: [email protected]


Und wer sind Sie?

Meines Wissens zum allergrößten Teil:

Bachelor-Studierende „Komedia“ (vorwiegend 1. Semester)

Falls Sie im Studiengang „Angewandte Informatik“ sind, haben Sie sichwahrscheinlich verirrt und suchen eigentlich die Lehrveranstaltung „Logik“von Frau Prof. König.


Zur Lehrveranstaltung

Form:

2 V + 1 Ü

Vorlesung:donnerstags, 8:30 – 10:00, LB 107, voraussichtlich 15 Termine

Übungen:Abgaben (elektronisch) zu Übungsblättern mit anschließenderKorrektur und Besprechung in Präsenz

zusätzlich Tutorium:

demnächst montags, 16:15 – 17:45, LB 104

Videos:

gibt es teils aus dem Vorjahr, sowohl zum Vorlesungs- als auch zumÜbungsbetrieb


Lernplattform Moodle

Wir verwenden Moodle, um

Materialien zur Lehrveranstaltung sowie die Aufgabenblätter jeweilsaktuell zur Verfügung zu stellen und

Übungseinreichungen elektronisch abgeben zu lassen.

Außerdem gibt es im Moodle-Kurs ein Ankündigungsforum.


Hinweise zu den Übungen

Machen Sie die Übungsaufgaben!

Weitere Hilfestellung können Sie bei Bedarf in den Lern- undDiskussionszentren (LuDi Informatik, Komedia + LuDi Mathematik)erhalten: Infos unter https://udue.de/ludi

Wenn Sie die schriftlichen Übungsaufgaben in Gruppen bearbeiten,geben Sie bitte pro Gruppe nur einmal ab.

Das erste Übungsblatt wird zeitnah veröffentlicht.

Schriftliche Einreichungen sind jeweils bis zu einer verkündeten Fristmöglich, immer als einzelne PDF-Datei über Moodle.

Zusätzlich: „Autotool“-Aufgaben, dazu Details demnächst.


https://udue.de/ludi

Klausur

Die Lehrveranstaltung wird durch eine 90-minütige schriftliche Klausur amEnde des Semesters geprüft.

Der derzeitige Planungsstand für den Klausurtermin ist Mittwoch,2. März 2022, 08:30 Uhr.

Die Anmeldung erfolgt über das Prüfungsamt.


Hinweise zu Kommunikationswegen

In den meisten Fällen ist eine Frage in/nach Vorlesung oder Übungsinnvoller als eine E-Mail an mich oder die Übungsleitung bzw.Tutor/innen.

E-Mails von anderen als uni-due.de Adressen werden gänzlichignoriert.

Umgekehrt sollten Sie Ihre uni-due.de E-Mails mindestenswerktäglich abholen.


Inhaltliche Übersicht I

AussagenlogikSprache der Aussagenlogik (AL)Wahrheitstafeln, Status von FormelnNormalformen und ÄquivalenzenResolutionsverfahren der ALAL-Hornformeln und der Markierungsalgorithmus

Logikprogrammierung in PrologSprachelementeProlog-AusführungProgrammieren mit RelationenRekursion und ListenverarbeitungGenerate-and-Test


Inhaltliche Übersicht II

PrädikatenlogikSprache der Prädikatenlogik (PL)Variablen und QuantorenStatus von FormelnNormalformen und ÄquivalenzenResolutionsverfahren der PL


Literatur

Es existieren sehr viele Lehrbücher zur Logik „in unserem Sinne“!

Geeignet sind zum Beispiel:

Kreuzer, Kühling: Logik für Informatiker. Pearson, 2006.

Uwe Schöning: Logik für Informatiker. Spektrum, 2000.


Warum diese Lehrveranstaltung?

Aus dem Modulhandbuch des Komedia-Studiengangs:

Logik-Kalküle bilden die Grundlage für verschiedene Anwen-dungsbereiche der Informatik, z.B. in den Bereichen Datenbank-systeme oder Wissensrepräsentation. Die Studierenden sollenmit logikbasierten Verfahren vertraut gemacht werden und sollenverschiedene Verfahren und Kalküle zur Lösung von Grundauf-gaben (wie Bestimmung von Modellen, Unerfüllbarkeit) anwen-den können.

Logik Inhaltliche Einführung 13

Warum diese Lehrveranstaltung?

Wenn Sie an Informatik und Logik denken, denken Sie vielleicht als erstesan so etwas:

Uns geht es jedoch vor allem um symbolische Logik.

Viel Motivation, und so manches Beispiel, wird aus dem Bereichsprachlichen Schlussfolgerns kommen.


Ein berühmtes Rätsel



































Einige der angewendeten „Strategien“:

Repräsentation von sprachlichen Aussagen in „atomarer“ bzw.kompakter Form (hier: als Tabelleneinträge)

Exploration von Alternativen (z.B. bezüglich ivory und green)

direkte Schlussfolgerungen (z.B. bezüglich green⇒ coffee)

Aufdecken und Ausnutzen von Widersprüchen

Ausschlussverfahren (z.B. bezüglich yellow)


Syllogismen

Solche Art der sprachlichen direkten Schlussfolgerungen/Argumentationnennt man „Syllogismen“:

bei Aristoteles:Wenn alle Menschen sterblich sind und Sokrates ein Mensch ist,dann ist Sokrates sterblich.

im Rätsel:Wenn wer im grünen Haus wohnt Kaffee trinkt, und X im grünenHaus wohnt, dann trinkt X Kaffee.


Syllogismen

Weitere Syllogismen:

Alle Philosophen sind Menschen.Alle Menschen sind sterblich.Alle Philosophen sind sterblich.

Keine Blume ist ein Tier.Alle Hunde sind Tiere.Keine Blume ist ein Hund.

Alle Delfine sind Säugetiere.Alle Delfine leben im Meer.Einige Säugetiere leben im Meer.


Syllogismen

Angenommen, Delfine sind leider ausgestorben. Was wäre dann, stattdes letzten Syllogismus von eben, mit folgenden Varianten?

Alle Elefanten sind Säugetiere.Alle Elefanten leben im Meer.Einige Säugetiere leben im Meer.

Alle Tomaten sind Säugetiere.Alle Tomaten leben im Meer.Einige Säugetiere leben im Meer.

Alle Aliens sind Säugetiere.Alle Aliens leben im Meer.Einige Säugetiere leben im Meer.


Weitere „bizarre“ Aussagen

Was halten Sie denn von folgender Aussage?

Wenn der Mond grün ist, haben wir Donnerstag.

Oder von folgender?

Weil der Mond grün ist, haben wir Donnerstag.

Oder von folgender?

Weil der Mond nicht grün ist, haben wir Donnerstag.

In der Tat eignet sich Logik zur Untersuchung der „wirklichen Bedeutung“von sprachlichen Mitteln/Begriffen wie „wenn“, „weil“, „sofern“, „nur falls“,aber auch „oder“, „entweder-oder“ und sogar auch „aber“, . . .


Probleme mit natürlicher Sprache

Andererseits hat natürliche Sprache, etwa auf Grund ihrer Struktur (oftmangelnd), auch grundsätzliche Probleme, wie fehlende Eindeutigkeit.

Beispiel:

Ich sah den Mann auf dem Berg mit dem Fernrohr.



(((Ich sah den Mann) auf dem Berg) mit dem Fernrohr)



((Ich sah (den Mann auf dem Berg)) mit dem Fernrohr)



((Ich sah den Mann) (auf dem Berg mit dem Fernrohr))



(Ich sah ((den Mann auf dem Berg) mit dem Fernrohr))



(Ich sah (den Mann (auf dem Berg mit dem Fernrohr)))



Natürliche Sprache ist einfach nicht immer eindeutig.

(((Ich sah den Mann) auf dem Berg)mit dem Fernrohr)

((Ich sah (den Mann auf dem Berg))mit dem Fernrohr)

((Ich sah den Mann) (auf dem Bergmit dem Fernrohr))

(Ich sah ((den Mann auf dem Berg)mit dem Fernrohr))

(Ich sah (den Mann (auf dem Bergmit dem Fernrohr)))

mindestens fünfmögliche

Interpretationen


Aussagenlogik versus Prädikatenlogik

Aussagenlogik:

Aussagen, die prinzipiell entweder wahr oder falsch sein können:„es regnet“ – R, „die Straße ist nass" – N

Verknüpfung solcher Aussagen mit einfachen Operatoren:„Es regnet und die Straße ist nass.“ – R ∧ N„Wenn die Straße nicht nass ist, dann regnet es nicht.“ – ¬N⇒¬R

Prädikatenlogik:

zusätzlich Aussagen über Beziehungen zwischen Objekten sowieexistentielle Aussagen und universelle Aussagen:„Für jede natürliche Zahl x gilt, dass es eine natürliche Zahl y gibt, sodass x kleiner als y ist.“ – ∀x : ∃y : (x < y)

Logik Aussagenlogik 44

Aussagenlogik

Entsprechung einiger der Strategien aus dem Einstein-Rätsel:

Repräsentation von sprachlichen Aussagen in „atomarer“ Form:A, B, R, N etc., später auch A1, A2, . . . , Ai

Exploration von Alternativen:A ∨ ¬A (Prinzip des ausgeschlossenen Dritten)

direkte Schlussfolgerungen:(A ∧(A⇒ B))⇒ B (Modus Ponens)

Aufdecken und Ausnutzen von Widersprüchen:¬(B ∧ ¬B) (Prinzip des ausgeschlossenen Widerspruchs)

Ausschlussverfahren:((C ∨ D) ∧ ¬C)⇒ D


Aussagenlogik

Noch eine Logelei, diesmal von „Zweistein“ (siehe Artikel in Moodle):

B Eine Logelei von Zweistein

Unter dem Pseudonym Zweistein veroffentlichte der unlangst verstorbene[43] Thomas von Ran-dow (1921 – 2009) in der Wochenzeitung DIE ZEIT kleine Logik- und Mathematikaufgaben[59, 60]. Hier eine typische Logikaufgabe, die sehr schon zeigt, daß die Bedeutung der Objekte,die man in der Logik behandelt, irrelevant ist. Zweistein benutzte gern bedeutungslose Phantasie-namen, so daß die Aufgabenstellung auf die reine Form reduziert wurde. [60, S. 74]:

1. Wer gedrupt ist, makst nicht.2. Wer knaselt, hat eine Mause.3. Jeder, der nicht deuken kann, makst.4. Alle Drumser nehmen Pfuff.5. Wer kein Pli ist, matupelt nicht.6. Kein betuxter Klep kann deuken.7. Wer Pfuff nimmt, ist gedrupt.8. Nur betuxte Kleps knaseln nicht.9. Jeder Pli ist ein Drumser.

Aus diesen Aussagen laßt sich ein Zusammenhang zwischen �matupeln� und �eine Mause ha-ben� ableiten. Wie lautet diese Aussage?

Losung Einige der Aussagen sind in der Form ¬A → ¬B geschrieben (5, 6). Es empfiehlt sich,diese

”richtigzustellen“ in die Form B → A, also zum Beispiel

¬5. Wer matupelt, ist ein Pli.

Also: ¬5: Wer matupelt, ist ein Pli.Aussagen 9 und 4 liefern: Ein Pli nimmt Pfuff.7 und 1: Wer Pfuff nimmt, makst nicht.3: Wer nicht makst, kann deuken.6: Wer deuken kann, ist kein betuxter Klep.8: Wer kein betuxter Klep ist, knaselt.2: Wer knaselt, hat eine Mause.Schlußfolgerung: Wer matupelt, der hat eine Mause.

C Das Paradoxon des Sancho Pansa

In dem bekannten Buch Don Quixote [9] wird ein klassisches Paradoxon durch Sancho Pansaeiner uberraschenden Losung zugefuhrt:

Zehntes Buch, Achtzehntes Kapitel Fortgesetzte Regierung des SanchoPansa und andre angenehme Begebenheiten.

. . . Wenn jemand uber diese Brucke von einem Ende zum andern geht, so soll er vorherschworen, wohin er geht und was sein Geschaft. Ist sein Schwur wahr, so lasse manihn ziehn, sagt er eine Luge, so soll er an den Galgen gehangt werden, der dort steht,ohne alle Barmherzigkeit. Dieses Gesetz und sein strenger Inhalt waren bekannt, vielegingen uber die Brucke, man sah, daß das, was sie beschworen hatten, die Wahrheitsei, und die Richter ließen sie ungehindert ziehn. Es geschah darauf, daß man einemManne den Eid abnahm, welcher schwur und sagte, daß bei dem Schwure, welchen er

26


Aussagenlogik

Unter anderem erwartet uns in diesem Kapitel:

Syntax der Aussagenlogik:Was sind die Operatoren? Was ist eine Formel?Welche Formeln sind „wohl-aufgebaut“?

Semantik der Aussagenlogik:Was ist die Bedeutung einer Formel?Welche Formeln sind allgemeingültig, d.h. immer wahr?Welche Formeln sind unerfüllbar, d.h. immer falsch?Was liegt dazwischen?

Verfahren und Methoden, die den Grad der Gültigkeit oderErfüllbarkeit einer Formel überprüfen.


Syntax der Aussagenlogik

Eine atomare Formel hat die Form A oder B . . . oder Ai (mit i = 1,2,3, . . .).

Definition (Formel allgemein)

Formeln werden durch folgenden schrittweisen Prozess definiert:

1. Alle atomaren Formeln sind bereits Formeln.

2. Für alle Formeln F und G sind (F ) ∧(G) und (F ) ∨(G) wiederumauch Formeln.

3. Für jede Formel F ist auch ¬(F ) eine Formel.

Sprechweise:

(F ) ∧(G): „F und G“, „Konjunktion von F und G“

(F ) ∨(G): „F oder G“, „Disjunktion von F und G“

¬(F ): „nicht F “, „Negation von F “Logik Aussagenlogik – Syntax 48

Formeln als Syntaxbäume

Jede Formel kann auch durch einen Syntaxbaum dargestellt werden.

Beispiel: F = ¬((¬A4 ∨ A1) ∧ A3)

¬

¬

A4

∨ A3

∧

A1

Logik Aussagenlogik – Syntax 49

Syntax der Aussagenlogik

Anmerkungen:

Es werden noch weitere Operatoren hinzukommen, insbesondere„⇒ “ und „⇔ “, die aber in gewissem Sinne nur „Abkürzungen“ aufBasis der bisher vorgegebenen sind.

Zu einer gegebenen Formel lässt sich das Konzept der Teilformelbetrachten, nämlich ihrerseits wohl-aufgebaute „Ausschnitte“.

Zum Beispiel sind hier einige Teilformeln in (¬A ∨ B) ∧ C markiert:

(¬A ∨ B) ∧ C

(¬A ∨ B) ∧ C

(¬A ∨ B) ∧ C

Wohingegen etwa diese Markierung keiner Teilformel entspricht:

(¬A ∨ B) ∧ C


Teilformeln

Die Teilformeln einer Formel F entsprechen den Teilbäumen desursprünglichen Syntaxbaums.

A4

¬

¬

∨ A3

∧

A4

A1A1

¬

¬

A4

∨ A3

∧

A1A3

¬

¬

A4

∨

∧

A3

A1

¬A4

¬

∨ A3

∧

A4

¬ A1¬A4 ∨ A1

¬

A3

∧

A4

∨

¬ A1

(¬A4 ∨ A1) ∧ A3

¬

A4

∨

¬

∧

A3

A1¬((¬A4 ∨ A1) ∧ A3)

¬

A4

∨

¬

∧

A3

A1


Semantik der Aussagenlogik

Und was ist nun der Wahrheitswert einer Formel (oder ihrer Teilformeln)?

Kommt drauf an!

Diskussion am Beispiel:

Anne sagt: „Bettina lügt.“

Bettina sagt: „Claudia lügt.“

Claudia sagt: „Anne und Bettina lügen beide.“

Wer lügt denn nun?

Logik Aussagenlogik – Semantik 52


Wir bezeichnen die Elemente der Menge W = {0,1} als Wahrheitswerte,wobei 0 für falsch und 1 für wahr steht.

Sei M eine Menge von atomaren Formeln.

Eine Belegung von M ist dann eine Zuordnung α : M→W , womitgemeint ist, dass α für jedes Element aus M einen Wert aus W angibt.(zum Beispiel: „α(A) = 0, α(B) = 1, α(C) = 0“)

Sei nun M die Menge aller Formeln, die nur aus den atomaren Formeln inM aufgebaut sind.

Dann erweitern wir α zu einer Zuordnung α : M→W , um für jede Formeleinen Wahrheitswert zu erhalten.



Die Definition dieser erweiterten Zuordnung:

α(A) = α(A) falls A ∈M eine atomare Formel ist

α((F ) ∧(G)) =

{1 falls α(F ) = 1 und α(G) = 10 sonst

α((F ) ∨(G)) =

{1 falls α(F ) = 1 oder α(G) = 10 sonst

α(¬(F )) =

{1 falls α(F ) = 00 sonst

Beobachtung: Der Wert von α für eine Formel hängt nur davon ab,wie α auf den in ihr vorkommenden atomaren Formelndefiniert ist.


Verknüpfungstafeln

Die bei der Berechnung von α verwendeten Regeln kann man auch alsVerknüpfungstafeln / Wahrheitstafeln festhalten.

Die Tafeln für die Operatoren ∧ , ∨ , ¬ sind:

A B A ∧ B0 0 00 1 01 0 01 1 1

A B A ∨ B0 0 00 1 11 0 11 1 1

A ¬A0 11 0


„Abkürzende“ Operatoren

Wir schreiben oft:

(F )⇒(G) für ¬(F ) ∨(G) (Implikation, Folgerung)

(F )⇔(G) für ((F )⇒(G)) ∧((G)⇒(F )) (Biimplikation, Äquivalenz)

Die entsprechenden Wahrheitstafeln für die so eingeführten Operatorensind:

A B A⇒ B0 0 10 1 11 0 01 1 1

A B A⇔ B0 0 10 1 01 0 01 1 1

Logik Aussagenlogik – Implikation und Biimplikation 56

„Abkürzende“ Operatoren

Für unser vorheriges Beispiel:




. . . haben wir dann: F = ((A⇔¬B) ∧(B⇔¬C) ∧(C⇔(¬A ∧ ¬B)))

A B C ¬A ¬B ¬C A⇔¬B B⇔¬C C⇔(¬A ∧ ¬B) F0 0 0 1 1 1 0 0 0 00 0 1 1 1 0 0 1 1 00 1 0 1 0 1 1 1 1 10 1 1 1 0 0 1 0 0 01 0 0 0 1 1 1 0 1 01 0 1 0 1 0 1 1 0 01 1 0 0 0 1 0 1 1 01 1 1 0 0 0 0 0 0 0


Genauere Betrachtung von Implikation

Zur Erinnerung, wir haben als abkürzende Schreibweise eingeführt:(F )⇒(G) für ¬(F ) ∨(G). Ist das überhaupt „logisch richtig“?

Nun, denken wir noch mal an folgenden Satz:Wenn der Mond grün ist, haben wir Donnerstag.

Als Elementaraussagen werden verwendet:

A: Der Mond ist grün. B: Wir haben Donnerstag.

Unter welchen der folgenden vier möglichen Konstellationen würden wirdem obigen Satz, also A⇒ B, zustimmen?

Der Mond ist nicht grün. Wir haben nicht Donnerstag. 3

Der Mond ist nicht grün. Wir haben Donnerstag. 3

Der Mond ist grün. Wir haben nicht Donnerstag. 7

Der Mond ist grün. Wir haben Donnerstag. 3



Noch mal als Wahrheitstafel:

A B A⇒ B0 0 10 1 11 0 01 1 1

Aber eben auch:

A B ¬A ¬A ∨ B0 0 1 10 1 1 11 0 0 01 1 0 1



Auch das Konzept der Kontraposition können wir uns so genaueranschauen:

A B A⇒ B ¬B ¬A ¬B ⇒ ¬A0 0 1 1 1 10 1 1 0 1 11 0 0 1 0 01 1 1 0 0 1

Es lässt sich aber auch gut aus der „Definition“, (F )⇒(G) := ¬(F ) ∨(G),ableiten:

A⇒ B steht für ¬A ∨ B,

¬B⇒¬A steht für ¬¬B ∨ ¬A,

und da ¬¬B gemäß doppelter Verneinung gerade B entspricht,„kommt das aufs selbe raus“.



Und bezüglich Biimplikation, (F )⇔(G) := ((F )⇒(G)) ∧((G)⇒(F )),können wir beobachten:

A B A⇒ B B ⇒ A (A⇒ B) ∧(B⇒ A)

0 0 1 1 10 1 1 0 01 0 0 1 01 1 1 1 1

Von früherer Folie:

A B A⇔ B0 0 10 1 01 0 01 1 1



Kehren wir noch mal zu diesem Beispiel zurück:




formalisiert als: F = ((A⇔¬B) ∧(B⇔¬C) ∧(C⇔(¬A ∧ ¬B)))

A B C ¬A ¬B ¬C A⇔¬B B⇔¬C C⇔(¬A ∧ ¬B) F0 0 0 1 1 1 0 0 0 00 0 1 1 1 0 0 1 1 00 1 0 1 0 1 1 1 1 10 1 1 1 0 0 1 0 0 01 0 0 0 1 1 1 0 1 01 0 1 0 1 0 1 1 0 01 1 0 0 0 1 0 1 1 01 1 1 0 0 0 0 0 0 0

Logik Aussagenlogik – Modelle und Status von Formeln 62


Kehren wir noch mal zu diesem Beispiel zurück, bzw. Variationen davon:


Bettina sagt: „Claudia lügt, aber Anne sagt die Wahrheit.“


formalisiert als: F = ((A⇔¬B) ∧(B⇔(¬C ∧ A)) ∧(C⇔(¬A ∧ ¬B)))

A B C ¬A ¬B ¬C A⇔¬B . . . C⇔(¬A ∧ ¬B) F0 0 0 1 1 1 0 1 0 00 0 1 1 1 0 0 1 1 00 1 0 1 0 1 1 0 1 00 1 1 1 0 0 1 0 0 01 0 0 0 1 1 1 0 1 01 0 1 0 1 0 1 1 0 01 1 0 0 0 1 0 1 1 01 1 1 0 0 0 0 0 0 0



Kehren wir noch mal zu diesem Beispiel zurück, bzw. Variationen davon:


Bettina sagt: „Anne und Claudia lügen beide.“


formalisiert als: F = ((A⇔¬B) ∧(B⇔(¬C ∧ ¬A)) ∧(C⇔(¬A ∧ ¬B)))

A B C ¬A ¬B ¬C A⇔¬B . . . C⇔(¬A ∧ ¬B) F0 0 0 1 1 1 0 0 0 00 0 1 1 1 0 0 1 1 00 1 0 1 0 1 1 1 1 10 1 1 1 0 0 1 0 0 01 0 0 0 1 1 1 1 1 11 0 1 0 1 0 1 1 0 01 1 0 0 0 1 0 0 1 01 1 1 0 0 0 0 0 0 0


Eigenschaften von Belegungen und Formeln

Eine Belegung α : M→{0,1} heißt passend zu einer Formel F fallsin M alle atomaren Teilformeln von F vorkommen.

Ist α zu F passend und gilt α(F ) = 1, so sagen wir F gilt unter α

bzw. α ist ein Modell für F , auch geschrieben als: α |= F .

Eine Formel heißt erfüllbar, wenn sie (mindestens) ein Modell besitzt.Ansonsten heißt sie unerfüllbar.

Eine Formel F heißt gültig (oder Tautologie), wenn α(F ) = 1 für allezu F passenden Belegungen.

Zwei Formeln F und G heißen (semantisch) äquivalent, wennα(F ) = α(G) für alle zu F und G passenden Belegungen.Wir schreiben dann F ≡G.


Eigenschaften von Belegungen und Formeln

Sei F = (¬A1 ∨(A2 ∧ A3)).

Beispiele für „passende Belegung“?passende Belegung α : A1 7→ 1,A2 7→ 1,A3 7→ 0nicht passende Belegung α : A2 7→ 1,A3 7→ 1,A4 7→ 0

Beispiel für ein Modell für F?α : A1 7→ 0,A2 7→ 0,A3 7→ 0, weil damit α(F ) = 1

Status von F?erfüllbar, nicht unerfüllbarkeine Tautologie, nicht (allgemein)gültig


Tautologien

Allgemeine, gültige Strategien wie für die Lösung des Einstein-Rätselssollten besser Tautologien sein. Und in der Tat:

Exploration von Alternativen / Prinzip des ausgeschlossenen Dritten:

A ¬A A ∨ ¬A0 1 11 0 1

direkte Schlussfolgerungen / Modus Ponens:

A B A⇒ B A ∧(A⇒ B) (A ∧(A⇒ B))⇒ B0 0 1 0 10 1 1 0 11 0 0 0 11 1 1 1 1


Tautologien

. . .

Prinzip des ausgeschlossenen Widerspruchs:

B ¬B B ∧ ¬B ¬(B ∧ ¬B)

0 1 0 11 0 0 1

„allgemeines Ausschlussverfahren“:

C D C ∨ D (C ∨ D) ∧ ¬C ((C ∨ D) ∧ ¬C)⇒ D0 0 0 0 10 1 1 1 11 0 1 0 11 1 1 0 1


Tautologien

. . .

transitives Schließen:

F = (((A⇒ B) ∧(B⇒ C))⇒(A⇒ C))

A B C A⇒ B B⇒ C (A⇒ B) ∧(B⇒ C) A⇒ C F0 0 0 1 1 1 1 10 0 1 1 1 1 1 10 1 0 1 0 0 1 10 1 1 1 1 1 1 11 0 0 0 1 0 0 11 0 1 0 1 0 1 11 1 0 1 0 0 0 11 1 1 1 1 1 1 1


Status von Formeln

Formel

unerfüllbar(z.B. A ∧ ¬A)

erfüllbar

nichttautologisch

(z.B. A)

tautologisch(z.B. A ∨ ¬A)


Status von Formeln

zum Durchdenken:

gültig erfüllbar unerfüllbar

AA ∨ BA ∨ ¬AA ∧ ¬AA⇒¬AA⇒ BA⇒(B⇒ A)

A⇒(A⇒ B)

A⇔¬A


Status von Formeln

Gelten die folgenden Zusammenhänge, für beliebige Formeln F?

Ja/Nein Gegenbsp.

Wenn F gültig, dann F erfüllbarWenn F gültig, dann ¬F unerfüllbarWenn F erfüllbar, dann ¬F unerfüllbarWenn F nicht gültig, dann F unerfüllbarWenn F nicht gültig, dann ¬F erfüllbarWenn F unerfüllbar, dann ¬F erfüllbarWenn F unerfüllbar, dann ¬F gültig


Status von Formeln

Spiegelungsprinzip:

¬FFG

gültigeFormeln

¬G

erfüllbare, abernicht gültige

Formeln

unerfüll-bareFormeln


Status von Formeln

Wie kann man überprüfen, ob eine gegebene Formel F gültig bzw.erfüllbar oder unerfüllbar ist?

Eine Möglichkeit ist offenbar, die Wahrheitstafel aufzustellen. Allerdingswächst deren Größe exponentiell in der Anzahl der atomaren Formeln.

Denn, angenommen die Formel F enthält n verschiedene atomareFormeln, wie groß ist dann die Wahrheitstafel?

Die Anzahl der Zeilen ist 2n, und in jeder Zeile müssen dann ja nochdiverse Einträge befüllt werden.

Geht es auch effizienter?

Methoden und Verfahren, die den Grad der Gültigkeit oder Erfüllbarkeiteiner Formel überprüfen, sind weiterer Stoff dieser Lehrveranstaltung.


Normalformen – Motivation

Bisher hatten wir (beliebig gebildete) Formeln und haben deren Semantikausgewertet, also im Wesentlichen die Wahrheitstafeln aufgestellt.

Es stellt sich die Frage, ob es denn umgekehrt zu jeder Wahrheitstafelauch eine Formel gibt. Oder mehrere? Ganz spezielle, die einemgewissen Schema folgen? Mit Verwendung aller eingeführten Operatoren,oder nur ausgewählter?

Auch wenn aus anderen Gründen (also nicht von einer Wahrheitstafelausgehend) eine Formel aufgestellt wird, kann es sein, dass nurbestimmte Operatoren verwendet werden sollen oder ein gewissessyntaktisches Schema unbedingt einzuhalten ist.

Zum Beispiel, . . .

Logik Aussagenlogik – Normalformen 75

Beispiel: Bedingungen in Moodle

In Moodle lassen sich einzelne Objekte (Textblöcke, Umfragen,Materialien, . . . ) mit Voraussetzungen versehen.

Dafür gibt es atomare Bedingungen, etwa folgende Arten:

und Operatoren zur Kombination:



Etwas genauer angeschaut, gibt es:

diverse „atomare Formeln“, unter anderem:

Ai : Zeitpunkt ist ab so-und-so¬Ai : Zeitpunkt ist vor so-und-so

Bj : Aktivität so-und-so wurde abgeschlossen¬Bj : Aktivität so-und-so noch nicht abgeschlossen

bestimmte Operatoren, unter anderem:

A1 ∧ . . . ∧ An : . . . muss alle erfüllen . . .¬(A1 ∧ . . . ∧ An) : . . . darf nicht alle erfüllen . . .

A1 ∨ . . . ∨ An : . . . muss mindestens eine erfüllen . . .

aber nicht alle denkbaren Operatoren, etwa keine Implikation,

und keine syntaktische Schachtelung.



In einem vergangenen Semester wollte ich ausdrücken, dass einegewisse Umfrage genau dann verfügbar sein soll, wenn:

die Umfrage noch nicht beantwortet wurde,

es vor dem 8. September ist,

und es nicht am 21. April zwischen 8:30 und 10:00 Uhr ist.

Reichen dafür die vorhandenen Ausdrucksmittel?

Erstes Problem:

Atomare Aussagen der Form „Datum ist zwischen . . . und . . . “ werden inMoodle nicht unterstützt, also die letzte Bedingung könnte man allenfallsmittels eines Operators aus einfacheren zusammenbauen.



Unter Verwendung folgender atomarer Aussagen:

A : Umfrage noch nicht abgeschlossenB : Zeitpunkt ist vor 8. SeptemberC : Zeitpunkt ist ab 8:30 Uhr am 21. AprilD : Zeitpunkt ist vor 10:00 Uhr am 21. April

würden wir gern ausdrücken: A ∧ B ∧ ¬(C ∧ D).

Jedoch:

Die Operatoren lassen sich in Moodle nicht schachteln, also es ist zumBeispiel nicht möglich, ¬(C ∧ D) in A ∧ B ∧ . . . einfach „einzusetzen“.

Auch diverse andere Ansätze, etwa Umformulierung der Formel zu¬(¬A ∨ ¬B ∨(C ∧ D)), scheiterten in der Umsetzung an mangelnderFlexibilität von Moodle beim „Zusammenklicken“.



Meine etwas getrickste Lösung letztlich:

. . . entspricht der Formel A ∧ B ∧(¬C ∨ ¬D).

Anmerkung: Das klappt so (per Sichtbarkeits-Schachtelung vonMoodle-Objekten) nur genau für Konjunktion, nicht für Disjunktion.

Relevantere Beobachtung:Verwendet habe ich somit letztlich eine Formel in KNF.


Normalformen

Ein Literal ist eine atomare Formel oder die Negation einer atomarenFormel. Wir sprechen von positiven und negativen Literalen.

Eine Formel F ist in konjunktiver Normalform (KNF), falls sie alsKonjunktion von Disjunktionen von Literalen Li,k aufgebaut ist:

F = (L1,1 ∨ . . . ∨ L1,n1) ∧(L2,1 ∨ . . . ∨ L2,n2) ∧ . . . ∧(Lm,1 ∨ . . . ∨ Lm,nm )

Eine Formel F ist in disjunktiver Normalform (DNF), falls sie alsDisjunktion von Konjunktionen von Literalen Li,k aufgebaut ist:

F = (L1,1 ∧ . . . ∧ L1,n1) ∨(L2,1 ∧ . . . ∧ L2,n2) ∨ . . . ∨(Lm,1 ∧ . . . ∧ Lm,nm )

Theorem: Zu jeder Formel gibt es eine äquivalente Formel in KNFund eine äquivalente Formel in DNF.


Beispiele KNF / DNF

(A1 ∧ A2) ∨(¬A1 ∧ A3) DNF

¬A1 ∨ A3 ∨(¬A1 ∧ A3) DNF

(¬A1 ∧ A2) ∨(¬A2 ∧(A3 ∨ ¬A3)) weder KNF, noch DNF

(¬A2 ∨ A3) ∧(A1 ∨ A4) KNF

(A1 ∨ A3 ∨ ¬A2 ∨ A4) ∧(¬A1 ∨ A4) KNF

(A1 ∧ ¬¬A3) ∨(¬A2 ∧ A4) weder KNF, noch DNF

¬A2 ∨ ¬A3 ∨ ¬A4 KNF und DNF

¬(A2 ∨ A3 ∨ A4) weder KNF, noch DNF

A1 KNF und DNF


Äquivalenzen

Angenommen, wir stehen vor dem Problem, für eine gegebene Formeleine äquivalente Formel in KNF zu finden. Wie könnten wir vorgehen?

Im Beispiel formte ich A ∧ B ∧ ¬(C ∧ D) zu A ∧ B ∧(¬C ∨ ¬D) um.

Warum durfte ich das, und welche anderen Umformungen sind erlaubt?

Zur Erinnerung:

Zwei Formeln F und G heißen (semantisch) äquivalent, wennα(F ) = α(G) für alle zu F und G passenden Belegungen α .Wir schreiben dann F ≡G.

Korrekte Umformungen sind immer auch „in Kontext“ erlaubt. Also wennwir ¬(C ∧ D)≡ (¬C ∨ ¬D) wissen, dann können wir das wie oben auchinnerhalb von A ∧ B ∧ . . . verwenden.

Logik Aussagenlogik – Äquivalenzen 83

Fundamentale Äquivalenzen der Aussagenlogik

Für aussagenlogische Formeln F ,G,H gelten folgende Äquivalenzen:

Teil I

(F ∧ F ) ≡ F(F ∨ F ) ≡ F (Idempotenz)

(F ∧G) ≡ (G ∧ F )

(F ∨G) ≡ (G ∨ F ) (Kommutativität)

((F ∧G) ∧ H) ≡ (F ∧(G ∧ H))

((F ∨G) ∨ H) ≡ (F ∨(G ∨ H)) (Assoziativität)

(F ∧(F ∨G)) ≡ F(F ∨(F ∧G)) ≡ F (Absorption)


Fundamentale Äquivalenzen der Aussagenlogik

Teil II

(F ∧(G ∨ H)) ≡ ((F ∧G) ∨(F ∧ H))(F ∨(G ∧ H)) ≡ ((F ∨G) ∧(F ∨ H)) (Distributivität)

¬¬F ≡ F (Doppelnegation)

¬(F ∧G) ≡ (¬F ∨ ¬G)

¬(F ∨G) ≡ (¬F ∧ ¬G) (de Morgansche Regeln)

(F ∨G) ≡ F , falls F gültig(F ∧G) ≡ G, falls F gültig (Tautologieregeln)

(F ∨G) ≡ G, falls F unerfüllbar(F ∧G) ≡ F , falls F unerfüllbar (Unerfüllbarkeitsregeln)


Algorithmus zum Erzeugen einer KNF

Gegeben sei eine Formel F . Führe folgende Schritte durch:

0. Eliminiere ⇒ und ⇔ mittels ihrer jeweiligen „Definition“.

1. Ersetze jede Teilformel der Bauart ¬¬G durch G.

2. Ersetze jede Teilformel der Bauart ¬(G ∧ H) durch (¬G ∨ ¬H).Wende für hierdurch gegebenenfalls entstehende Teilformeln derBauart ¬¬K jeweils Schritt 1 an.

3. Ersetze jede Teilformel der Bauart ¬(G ∨ H) durch (¬G ∧ ¬H).Wende für hierdurch gegebenenfalls entstehende Teilformeln derBauart ¬¬K jeweils Schritt 1 an.

4. Wiederhole die Schritte 2 und 3 so oft wie möglich.

5. . . . siehe nächste FolieLogik Aussagenlogik – Umformen nach KNF / DNF 86

Algorithmus zum Erzeugen einer KNF

5. Ersetze jede Teilformel der Bauart G ∨(H ∧ I) durch((G ∨ H) ∧(G ∨ I)).

6. Ersetze jede Teilformel der Bauart (G ∧ H) ∨ I durch((G ∨ I) ∧(H ∨ I)).


Dabei gilt:

Schritte 1 bis 4 „drücken Negation im Syntaxbaum nach unten“.Danach wird keine Negation mehr „angefasst“ oder „eingeführt“.

Schritte 5 bis 7 „drücken Disjunktion im Syntaxbaum nach unten“(weil KNF angestrebt wird).

Es sind, „unterwegs“ oder am Ende, manchmal Vereinfachungenmöglich . . . siehe Beispiele.

Logik Aussagenlogik – Umformen nach KNF / DNF 87

Algorithmus zum Erzeugen einer DNF

Schritte 0 bis 4 exakt wie beim Algorithmus zum Erzeugen einer KNF!

Und dann:

5. Ersetze jede Teilformel der Bauart G ∧(H ∨ I) durch((G ∧ H) ∨(G ∧ I)).

6. Ersetze jede Teilformel der Bauart (G ∨ H) ∧ I durch((G ∧ I) ∨(H ∧ I)).


Logik Aussagenlogik – Umformen nach KNF / DNF 88

Von Wahrheitstafel zu Formel (in Normalform)

Bisher:

zu Formel die Wahrheitstafel aufstellen

eine Formel in KNF / DNF bringen

Noch offen:

zu einer Wahrheitstafel eine Formel aufstellen

Ansatz:

Konstruktion einer KNF oder DNF zu gegebener Wahrheitstafel

durch Konjunktion von Max-Termen bzw. Disjunktion von Min-Termen

Logik Aussagenlogik – Min/Max-Terme 89

Min/Max-Terme

Gegeben sei eine Menge atomarer Formeln (wie A, B, . . . ), zu der wireine Wahrheitstafel haben oder eine bestimmte 0-1-wertige Funktionbeschreiben wollen.

Dann bezeichnen wir als

Max-Term: eine mehrstellige Disjunktion, die genau zu jeder dergegebenen atomaren Formeln entweder ein positives oderein negatives Literal enthält

Min-Term: eine mehrstellige Konjunktion, die . . . (analog)

Beispiele (gegeben als atomare Formeln seien A1, A2, A3):

A1 ∨ ¬A2 ∨ ¬A3 Max-Term

¬A1 ∧ A2 ∧ ¬A3 Min-Term


Min/Max-Terme

Beispiele (gegeben als atomare Formeln seien A1, A2, A3):

A1 ∨ ¬A2 ∨ ¬A3 Max-Term

¬A1 ∧ A2 ∧ ¬A3 Min-Term

Max-Terme führen nur bei genau einer Konfiguration zu 0,Min-Terme nur bei genauer einer Konfiguration zu 1.

Idee Erzeugung KNF:Max-Terme für Zeilen der Wahrheitstafel mit Ergebnis 0dabei negative Literale genau für mit 1 belegte atomare Aussagen

Idee Erzeugung DNF:Min-Terme für Zeilen der Wahrheitstafel mit Ergebnis 1dabei negative Literale genau für mit 0 belegte atomare Aussagen


KNF und DNF aus Min/Max-Termen


Nicht-Eindeutigkeit der Normalform

Zur Erinnerung:

Als per Max-Termen aufgestellte KNF zu dieser Formel ergibt sich:

(¬A ∨ B ∨ C) ∧(¬A ∨ B ∨ ¬C) ∧(¬A ∨ ¬B ∨ C)


Modelle und Status von Formeln

Zur Erinnerung:

Um zu überprüfen, ob eine gegebene Formel F gültig bzw. erfüllbaroder unerfüllbar ist (und gegebenenfalls ein konkretes Modell zufinden), haben wir bisher Wahrheitstafeln verwendet.

Diese konnten aber sehr groß werden.

Wegen des Spiegelungsprinzips sind die Probleme Tautologietest,Erfüllbarkeitstest, Modellsuche miteinander verwandt.

Durch Umformen/Vereinfachen können wir Formeln in KNF oder DNFbringen.

Wenn wir Verfahren für die obigen „Grundprobleme“ kennen würden, diefür KNF oder DNF gut funktionieren, könnten wir diese nun auch im Fallallgemeiner Formeln zum Einsatz bringen. −→ Resolutionsverfahren

Logik Aussagenlogik – Resolution 94

Mengenschreibweise von Formeln in KNF

Erinnerung: Formel in KNF

F = (L1,1 ∨ . . . ∨ L1,n1) ∧(L2,1 ∨ . . . ∨ L2,n2) ∧ . . . ∧(Lm,1 ∨ . . . ∨ Lm,nm )

Einzelne Disjunktionsterme wie (L1,1 ∨ . . . ∨ L1,n1) werden auchKlauseln genannt.

Wir verwenden für das Resolutionsverfahren folgendeMengenschreibweise:

F = {{L1,1, . . . ,L1,n1},{L2,1, . . . ,L2,n2}, . . . ,{Lm,1, . . . ,Lm,nm}}

Dabei wurden ∧ und ∨ beide zu Kommata. Wie kann das sein, ohnezu Verwirrung zu führen?

Bedeutung ist eindeutig dadurch, dass F in KNF vorliegt.


Resolutionsverfahren der Aussagenlogik

Sei L ein Literal. Dann bezeichnet L das komplementäre Literal.Das heißt, L = ¬A falls L = A, sowie L = A falls L = ¬A.

Seien K1,K2 Klauseln einer KNF-Formel F mit K1 6= K2. Dann wirdeine Klausel R als Resolvent von K1 und K2 bezeichnet, falls es einLiteral L gibt, so dass: L ∈ K1, L ∈ K2, R = (K1 \{L})∪ (K2 \{L}).

Dann gilt: F ≡ F ∧ R, bzw. in Mengenschreibweise: F ≡ F ∪{R}.

Falls durch fortgesetzte Bildung von Resolventen die leere KlauselR = ∅ abgeleitet werden kann, dann ist F unerfüllbar.

(Und zwar genau in dem Fall.)


Resolutionsschritt – Beispiel

K1 = {A,¬B,C} K2 = {B,C,¬D}

R = {A,C,¬D }

Grundidee: ((G ∨ L) ∧(H ∨ L)) ⇒ (G ∨ H)


Resolutionsschritt – Nicht-Beispiel

K1 = {A,¬B,C} K2 = {B,¬C,¬D}

R = {A,¬D }

Falsch!


Resolutionsschritt – Beispiel

K1 = {A,¬B,C} K2 = {B,¬C,¬D}

R = {A,C,¬C,¬D } R = {A,B,¬B,¬D }

Wichtig: In jedem Resolutionsschritt werden nur genau ein Literal unddessen Komplement eliminiert!


Resolution – Beispiel

Gegeben sei: F = ((A ∨ B ∨ C) ∧(¬A ∨ B ∨ C) ∧(B ∨ ¬C))

Frage: Gilt F ⇒ B ?

Zur Klärung der Frage können wir Unerfüllbarkeit von F ∧ ¬Büberprüfen, also von:

((A ∨ B ∨ C) ∧(¬A ∨ B ∨ C) ∧(B ∨ ¬C)) ∧ ¬B

{A,B,C} {¬A,B,C} {B,¬C} {¬B}

{B,C}

{B}

∅Logik Aussagenlogik – Resolution 100

Resolution – „Merkregeln“

Es werden jeweils zwei Klauseln resolviert.

Klauseln (die ursprünglichen sowie die unterwegs entstandenen)dürfen beliebig oft benutzt werden, werden also nicht etwa„verbraucht“.

Es müssen nicht unbedingt alle Klauseln überhaupt jemalsverwendet werden, um am Schluss die leere Klausel herzuleiten.

In jedem Resolutionsschritt werden nur genau ein Literal und dessenKomplement eliminiert.

Das Verfahren ist beendet, wenn die leere Klausel hergeleitet wurdeoder Gewissheit besteht, dass dies nicht geht.


Hornformeln

Eine Formel ist eine Hornformel, falls

sie in KNF vorliegt,

und jede ihrer Klauseln eine Hornklausel ist, was bedeutet, dass jedeKlausel jeweils nur maximal ein positives Literal enthalten darf.

Hornformeln haben die Besonderheit, dass sie sich immer als Konjunktionvon Implikationen zwischen Konjunktionen von nur positiven Literalenschreiben lassen.

Denn es gilt ja folgende Äquivalenz:

(¬A1 ∨ . . . ∨ ¬Ak ∨ B) ≡ ((A1 ∧ . . . ∧ Ak )⇒ B)

Logik Aussagenlogik – Hornformeln 102

Hornformeln

Umgekehrt lassen sich „Wissensbasen“ der häufig auftretenden Form„Konjunktion von Implikationen zwischen Konjunktionen positiver Literale“immer als Hornformel ausdrücken.

Denn zum Beispiel

(A⇒ B) ∧ ((C ∧ D)⇒(E ∧ F )) ∧ ((G ∧ H)⇒ I)

lässt sich ja umformen zu folgender KNF, die in der Tat auch eineHornformel ist:

(¬A ∨ B) ∧(¬C ∨ ¬D ∨ E) ∧(¬C ∨ ¬D ∨ F ) ∧(¬G ∨ ¬H ∨ I)


Hornformeln

Da es bezüglich Hornklauseln hieß, dass sie jeweils maximal ein positivesLiteral enthalten dürfen, stellt sich natürlich noch die Frage, inwieweitdann etwa (¬A1 ∨ . . . ∨ ¬Ak ) als Implikation zwischen Konjunktionenpositiver Literale angesehen werden kann.

Und ebenfalls, wie der Fall zu sehen ist, bei dem keine negativen Literalevorliegen, also k = 0 in (¬A1 ∨ . . . ∨ ¬Ak ∨ B).

Diese Betrachtung führt zur Benennung bestimmter Typen vonHornklauseln.


Typen von Hornklauseln

Sei K eine Hornklausel.

Kommt in K genau ein positives und mindestens ein negatives Literalvor, so heißt K Prozedurklausel oder Regel.

Beispiel: (¬A1 ∨ ¬A2 ∨ B), geschrieben als ((A1 ∧ A2)⇒ B)

Kommt in K genau ein positives und kein negatives Literal vor, soheißt K Tatsachenklausel oder Fakt.

Beispiel: B, fortan geschrieben als (1⇒ B)

Enthält K kein positives Literal, aber mindestens ein negatives Literal(ansonsten wäre K ja ganz leer), so heißt K Zielklausel oder Anfrage.

Beispiel: (¬A1 ∨ ¬A2), fortan geschrieben als ((A1 ∧ A2)⇒ 0)


Ausblick auf Logikprogramme

Regeln und Fakten zusammen werden auch „Programmklauseln“genannt.

Die Bedeutung von „Zielklausel“ bzw. „Anfrage“ wird dann klar, wenn mansie als „negierte Frage“ interpretiert und sich (per Spiegelungsprinzip) dieÄquivalenz zwischen einerseits

„((Fakten ∧ Regeln)⇒ Frage) ist gültig“

und„(Fakten ∧ Regeln ∧ ¬Frage) ist unerfüllbar“

andererseits bewusst macht.


Markierungsalgorithmus

Zur Erinnerung:

Um Unerfüllbarkeit einer KNF zu prüfen, können wir dasResolutionsverfahren nutzen.

Dabei kann die „Suche nach einem Weg zur leeren Klausel“aufwändig werden, weil wir oft viele Möglichkeiten haben, etwa diebeiden als nächstes zu resolvierenden Klauseln auszuwählen, bzw.das als nächstes zu eliminierende Literal/Komplement-Paar.

Und wenn sich herausstellt, dass die ursprüngliche Formel docherfüllbar war, haben wir keine direkte Möglichkeit, eine erfüllendeBelegung abzulesen.

Andererseits existiert die spezielle Klasse Hornformeln von KNFs, etwa:

((A ∧ C)⇒ B) ∧ (C⇒ D) ∧ (B⇒ 0) ∧ (D⇒ A) ∧ (1⇒ C)

Logik Aussagenlogik – Markierungsalgorithmus 107


Idee des Algorithmus am Beispiel:((A ∧ C)⇒ B) ∧ (C⇒ D) ∧ (B⇒ 0) ∧ (D⇒ A) ∧ (1⇒ C)

1. Wegen 1⇒ C muss jede erfüllende Belegung bei C eine 1 haben.Das können wir durch Markierung in der Formel festhalten, und zwaran allen Stellen des Auftretens.

2. Wegen C⇒ D muss jede erfüllende Belegung auch bei D eine 1haben. Auch das können wir wieder durch Markierungen in derFormel festhalten.

3. Wegen nun D⇒ A können wir auch für A so vorgehen.

4. Erst wenn alle Aussagen in der Voraussetzung einer Implikationbereits markiert sind, können wir auch die Aussage aus derFolgerung markieren. Nun also B.

5. Aus B⇒ 0 ergibt sich ein Widerspruch, also kann die ursprünglicheFormel hier nicht erfüllbar gewesen sein.



Allgemeine Beschreibung, wobei zum Zwecke der Nachvollziehbarkeitjeweils die „Schrittnummer“ der Markierungen festzuhalten ist:

Für jede Teilformel der Form 1⇒ A markiere alle Vorkommen von Ain der Gesamtformel. Schrittnummer dafür ist 1.Solange es eine Teilformel der Form A1 ∧ . . . ∧ Ak ⇒ . . . gibt, bei deralle Ai bereits markiert sind, entscheide:

Falls statt des . . . eine 0 steht, gib „unerfüllbar“ aus und stoppe.Falls statt des . . . eine noch nicht markierte Aussage B steht,inkrementiere den Schrittzähler und markiere alle Vorkommenvon B in der Gesamtformel entsprechend.

Falls obiger Ablauf nicht zur Ausgabe „unerfüllbar“ geführt hat, gibam Ende „erfüllbar“ aus. Eine erfüllende Belegung ergibt sich, indemalle markierten Aussagen auf 1 gesetzt werden, die anderen auf 0.



Entsprechend aufgeschrieben für das vorige Beispiel:

((A3 ∧ C1)⇒ B4) ∧ (C1⇒ D2) ∧ (B4⇒ 0) ∧ (D2⇒ A3) ∧ (1⇒ C1)

Schritt 1: C

Schritt 2: D

Schritt 3: A

Schritt 4: B

„unerfüllbar“



Anderes Beispiel:

(¬A ∨ B) ∧ A ∧ C ∧(¬C ∨ D) ∧(¬C ∨ ¬D ∨ E) ∧ ¬F

Markierungsalgorithmus:

(A1⇒ B3) ∧ (1⇒ A1) ∧ (1⇒ C1) ∧ (C1⇒ D2)

∧ ((C1 ∧ D2)⇒ E4) ∧ (F ⇒ 0)

Schritt 1: A, C

Schritt 2: D

Schritt 3: B

Schritt 4: E

„erfüllbar“, mit α(A) = α(B) = α(C) = α(D) = α(E) = 1 und α(F ) = 0


Vergleich zu (linearer) Resolution

((A ∧ C)⇒ B) ∧ (C⇒ D) ∧ (B⇒ 0) ∧ (D⇒ A) ∧ (1⇒ C)

{¬B}

{¬A,¬C}

{¬C,¬D}

{¬C}

∅

Seitenklauseln

{¬A,B,¬C}

{A,¬D}

{¬C,D}

{C}


Erster Blick auf Prolog

Logik Logikprogrammierung 113

Zur Erinnerung


Zur Erinnerung


Zur Erinnerung


Ein „echtes“ Prolog-Programm


Verwendung von Prädikaten

In Abkehr von reiner Aussagenlogik, wo wir von atomaren Aussagen wie

A = Der Mond ist grün.B = Es regnet.C = Die Straße ist nass.

ausgegangen sind, ohne sie weiter zu „zerlegen“, können ab jetzt dieAussagen, welche durch Konjunktion, Implikation etc. verknüpft werden,selbst noch eine innere Struktur haben.

Zum Beispiel gruen(mond) statt obigem A und dann etwa alsEntsprechung für

Wenn der Mond grün ist, haben wir Donnerstag.

die folgende Prolog-Regel: donnerstag :- gruen(mond).

Logik Logikprogrammierung – Prädikate 118


„Ich sah den Mann auf dem Berg mit dem Fernrohr.“

sah(ich,mann), auf(ich,berg),mit(ich,fernrohr)

auf(mann,berg), sah(ich,mann),mit(ich,fernrohr)

sah(ich,mann), auf(ich,berg),auf(fernrohr,berg)

auf(mann,berg), mit(mann,fernrohr),sah(ich,mann)

auf(fernrohr,berg), auf(mann,berg),sah(ich,mann)



Neben der flexibleren Verwendung dieser „neuen Art Literale“, etwa durchWiederverwendbarkeit der Prädikate für verschiedene Subjekte/Objekte,ergeben sich mittels Variablen auch neue Arten interessanter Regeln.

Zum Beispiel:

auf(J,berg) :- auf(fernrohr,berg), mit(J,fernrohr).

Prolog arbeitet mit genau diesen Mitteln.


Einfachstes Prolog: Fakten und Anfragen

Logik Logikprogrammierung – Fakten, Regeln, Anfragen 121

Fakten + einfache Implikationen


Komplexere Regeln


Relationen, und komplexere Anfragen


Variablen in Regeln (nicht nur in Anfragen)


Variablen in Regeln (nicht nur in Anfragen)


Einige Beobachtungen zu Variablen


Syntaxbegriffe in Prolog


Prolog-Ausführung

Logik Logikprogrammierung – Prolog-Ausführung 129

Prolog-Ausführung


Prolog-Ausführung


Prolog-Ausführung


Prolog-Ausführung


Prolog-Ausführung


Prolog-Ausführung


Prolog-Ausführung nochmal anders dargestellt


Zum Vergleich mit Resolution

Entsprechungen zwischen Hornklauseln und Prolog, an Beispielen:

Art Klausel als Disjunktion als Implikation in PrologFakt {a} a 1⇒ a a.Fakt {lustig(otto)} lustig(otto) 1⇒ lustig(otto) lustig (otto ).Regel {b,¬a} b ∨ ¬a a⇒ b b :− a.Regel {¬c,b,¬a} ¬c ∨ b ∨ ¬a (a ∧ c)⇒ b b :− a, c.Anfrage {¬a} ¬a a⇒ 0 ?− a.Anfrage {¬b,¬c} ¬b ∨ ¬c (b ∧ c)⇒ 0 ?− b, c.

Zur Erinnerung, in Prolog:

Fakten und Regeln stehen im Programmcode (d.h. in zu ladenderDatei, separatem Programmfenster o.ä.).

Anfragen ?− ... werden interaktiv (z.B. in laufenden Interpreterhinein) gestellt.


Was genau passiert bei einer Prolog-Anfrage?

?− a.

1. Prolog negiert die gestellte Anfrage zur Klausel {¬a}.2. Prolog versucht mit Hilfe der Programmklauseln einen Widerspruch

(also ∅) zu {¬a} herzuleiten.

Zur Herleitung eines Widerspruchs sucht Prolog systematisch eine lineareResolution (siehe Diskussion weiter vorn), die bei {¬a} startet, nur dieProgrammklauseln als Seitenklauseln verwendet, und die Resolventeimmer direkt weiterverwendet (bis dies nicht mehr geht, oder leereKlausel erreicht).

Diese Suche spannt einen sogenannten „SLD-Baum“ auf.



Betrachten wir beispielhaft das folgende Prolog-Programm:

1 a :− b , c .2 a :− d .3 b .4 b :− d .5 c .6 d .7 d :− e .

und rufen es entsprechend auf mit: ?− a.

Es entsteht folgende „Suchstruktur“: (siehe nächste Folie)



1 a :− b , c .2 a :− d .3 b .4 b :− d .5 c .6 d .7 d :− e .

{¬a}

{¬b,¬c} {¬d}

{¬c} {¬c,¬d} {¬b} ∅ {¬e}

∅ {¬c} {¬c,¬e} {¬d} ∅

∅ {¬e} {¬e} ∅

(1) (2)

(3) (4) (5) (6) (7)

(5) (6) (7) (5) (3)(4)

(5) (5) (7) (6)



Alle Pfade, die in ∅ enden, wären erfolgreiche SLD-Resolutionen.

Problem: Wie kann Prolog erfolgreiche SLD-Resolutionenmöglichst schnell finden?

Prinzipiell existieren mindestens zwei Herangehensweisen.Tiefensuche (depth-first search):Expandiere immer zunächst weiter in die Tiefe und springeansonsten zurück (Backtracking).Breitensuche (breadth-first search):Expandiere zunächst alle Nachfolger der aktuellen Ebene, bevorweiter in die Tiefe gegangen wird.

Prolog benutzt Tiefensuche. (Dies kann zu Problemen führen.)


Mit „First-Literal-Selection“

1 a :− b , c .2 a :− d .3 b .4 b :− d .5 c .6 d .7 d :− e .

?− a.

?− b, c. ?− d.

?− c. ?− d, c. � ?− e.

� ?− c. ?− e, c.

�

(1) (2)

(3) (4) (6) (7)

(5) (6) (7)

(5)


Probleme mit Tiefensuche

Anfrage:?− a.

Programm:

1 a :− b .2 a .3 b :− a .

?− a.

?− b.

?− a.

...

(1)

(3)

(1)

Die Tiefensuche terminiert hier nicht, weil sie immer wieder eine Regelanwenden kann. −→ Speicher wird voll. −→ Stack Overflow!


Resolution mit Variablen

Beispiel weiter vorn, Anfrage ?− istGrossvaterVon(kurt,X)., sowie u.a.:

1 i s tGrossvaterVon (G,E) :− i s tVaterVon (G,V) ,i s tVaterVon (V,E ) .

2 i s tVaterVon ( kur t , f r i t z ) .3 i s tVaterVon ( f r i t z , paul ) .

Das erste (und hier einzige) Literal der Anfrage lässt sich per Substitution{G/kurt,X/E} mit dem Kopf von Klausel (1) unifizieren, dann darüberresolvieren zu: ?− istVaterVon(kurt,V), istVaterVon(V,E).

Per {V/fritz} lässt sich dann das erste Literal davon mit dem Fakt (2)unifizieren; neue Resolvente dadurch: ?− istVaterVon( fritz,E).

Per {E/paul} lässt sich schließlich dieses Literal mit dem Fakt (3)unifizieren, dann darüber weiter resolvieren zur leeren Klausel.

Insgesamt haben wir damit als Lösung für X gefunden: paul.Logik Logikprogrammierung – Prolog-Ausführung 144

SLD-/Ableitungsbaum mit Variablen

Anderes Beispielprogramm:

1 g r o s s e l t e r n t e i l (X ,Y) :− e l t e r n t e i l (X , Z ) ,e l t e r n t e i l (Z ,Y ) .

2 e l t e r n t e i l (X ,Y) :− va te r (X,Y ) .3 e l t e r n t e i l (X ,Y) :− mutter (X,Y ) .

4 va te r ( ka r l , mat th ias ) .5 va te r ( ka r l , c h r i s t a ) .6 va te r ( ingo , leon ) .7 mutter ( ch r i s t a , leon ) .


SLD-/Ableitungsbaum mit Variablen

?−grosselternteil( karl , leon).

?−elternteil( karl ,Z), elternteil (Z,leon).

?− vater(karl ,Z), elternteil (Z,leon).

?−elternteil(matthias,leon). ?−elternteil( christa ,leon).

?− vater(matthias,leon).?− mutter(matthias,leon).

?− vater(christa ,leon).?− mutter(christa,leon).

�

(1)

(2)

(4) (5)

(2)(3)

(2)(3)

(7)

Freie Variable Z

wird hier jeweils

gebunden


Weitere „Sprachverfeinerung“

In Abkehr von reiner Aussagenlogik hatten wir schon atomare Aussagenwie A = „Der Mond ist grün.“ strukturell verfeinert durch Verwendung vonPrädikaten, etwa gruen(mond) oder auch sah(ich,mann).

Eine weitere Verfeinerung ist möglich, indem wir auch den Argumentenvon Prädikaten eine innere Struktur zubilligen.

Zum Beispiel könnten wir dann in child(harry,X) statt von harrypräziser von person(harry,potter) sprechen.

Dabei können solche Datenterme beliebig tief geschachtelt sein, undselbst auch Variablen enthalten, etwa:

address(City,Street,person(harry,potter))

Logik Logikprogrammierung – Datenstrukturen 147

Weitere „Sprachverfeinerung“

Beispielverwendung:

v a l i d ( address ( c i t y (Z ,C) , s t r e e t ( _ ,H) , person (F ,S ) ) ):− zipOkay (Z ,C) , H > 0 , H =< 99 , F \= S.

zipOkay (45141 , essen ) .zipOkay (47048 , duisburg ) .zipOkay (47057 , duisburg ) .

?− v a l i d ( address ( c i t y (47057 , duisburg ) , s t r e e t ( l o t h a r s t r,65 ) , person ( harry , p o t t e r ) ) ) .t r ue .

Achtung: Nicht die Rollen von Prädikaten und „Datenkonstruktoren“verwechseln!


Syntaxbegriffe in Prolog

Statt Konstanten und Variablen sind in

nun also beliebige solche Datenterme (möglicherweise mit Variablen anihren „Blättern“) als Argumente von Prädikaten möglich.

Dabei nennt man das Symbol person in person(harry,potter)einen zweistelligen Funktor, oder Funktionssymbol, oder Konstruktor, undnotiert dies auch als person/2.


Datenstrukturen allgemein

Konstanten können dann einfach als nullstellige Konstruktorenangesehen werden, etwa harry/0.

Schachtelungen können beliebig tief sein, etwa mit s/1 und z/0können wir beliebig große natürliche Zahlen repräsentieren:13 „=“ s(s(s(s(s(s(s(s(s(s(s(s(s(z))))))))))))).

(Diese Kodierung wird auch als „Peano-Zahlen“ bezeichnet.)

Bereits gesehen haben wir, dass „normale“ Zahlen aber auch direktals Konstanten verwendet werden können, etwa incity(47057,duisburg).

Als spezielle Datenstruktur kommen in Prolog auch noch Listenhinzu, notiert als [1,2,3,4,5] oder etwa auch Variablenenthaltend: [duisburg,X,essen], etc.


Beispiel: Symbolisches Rechnen


Beispiel: Symbolisches Rechnen


Rekursion

Wenn eine Regel für ein bestimmtes Prädikat dieses Prädikat auch aufder rechten Seite benutzt, nennt man das „Rekursion“. Zum Beispiel:

Bevor wir uns ein weiteres Beispiel für dieses Prinzip ansehen, ein paarAnmerkungen:

In rein aussagenlogischem Prolog ist Rekursion eher nicht sinnvoll.

Rekursion kann sich auch über mehr als eine Regel erstrecken, alsoindirekt passieren.

Die Reihenfolge von Regeln, und auch die innerhalb der rechtenSeiten von Regeln, kann bei rekursiven Definitionen einen großenUnterschied machen.

Das hat auch mit der Suchstrategie, Tiefen- vs. Breitensuche, zu tun.Logik Logikprogrammierung – Rekursion 153

Zur Erinnerung

Anfrage:?− a.

Programm:

1 a :− b .2 a .3 b :− a .

?− a.

?− b.

?− a.

...

(1)

(3)

(1)

Die Tiefensuche terminiert hier nicht, weil sie immer wieder eine Regelanwenden kann. −→ Speicher wird voll. −→ Stack Overflow!

Logik Logikprogrammierung – Rekursion 154

Rekursion für „transitive Hülle“

Als weiteres nicht rein aussagenlogisches Beispiel, nehmen wir an, wirhaben diverse Fakten für Prädikate vater/2 und mutter/2 gegeben, sowie:

e l t e r n t e i l (X ,Y) :− va te r (X,Y ) .e l t e r n t e i l (X ,Y) :− mutter (X,Y ) .

Wir wissen bereits, dass wir dann eine Großelternbeziehung ausdrückenkönnen über:

g r o s s e l t e r n t e i l (X ,Y) :− e l t e r n t e i l (X , Z ) ,e l t e r n t e i l (Z ,Y ) .

Aber was, wenn wir beliebige Vorfahren ermitteln wollen?

Ein möglicher Versuch:

u r g r o s s e l t e r n t e i l (X ,Y) :− e l t e r n t e i l (X , Z ) ,g r o s s e l t e r n t e i l (Z ,Y ) .



Versuch fortgesetzt:

u r u r g r o s s e l t e r n t e i l (X ,Y) :− g r o s s e l t e r n t e i l (X , Z ) ,g r o s s e l t e r n t e i l (Z ,Y ) .

oder alternativ:

u r u r g r o s s e l t e r n t e i l (X ,Y) :− e l t e r n t e i l (X , Z ) ,u r g r o s s e l t e r n t e i l (Z ,Y ) .

Aber zu einem wirklich allgemein verwendbaren Prädikat kommen wir soleider nicht.

Stattdessen, Verwendung von Rekursion:

vo r f ah r (X,Y) :− e l t e r n t e i l (X ,Y ) .vo r f ah r (X,Y) :− e l t e r n t e i l (X , Z ) , vo r f ah r (Z ,Y ) .



Dabei erfasst die vorfahr-Relation alle Instanzen von eltern, grosseltern,urgrosseltern, ururgrosseltern, . . . , ist also in diesem Sinne die „Hülle“ der„transitiven Fortsetzung“ der eltern-Relation.

Als gute Praxis, an diesem Beispiel

vo r f ah r (X,Y) :− e l t e r n t e i l (X ,Y ) .vo r f ah r (X,Y) :− e l t e r n t e i l (X , Z ) , vo r f ah r (Z ,Y ) .

demonstriert:

Es muss mindestens einen Basisfall für die Rekursion geben.

Basisfälle werden am besten zuerst aufgeführt.

In den Regeln für Nicht-Basisfälle kommen die rekursiven Aufrufe ambesten möglichst weit „hinten“.


Spezielle Datenstruktur: Listen

Neben Konstanten und per Schachtelung von Datenkonstruktoren wies/1 und z/0 zu erhaltenden Datenstrukturen, wurden auch Listen mitSyntax wie [1,2,3,4,5] und [duisburg,X,essen] zuvor bereitskurz erwähnt.

Zur Arbeit mit Listen hält Prolog diverse Prädikate bereit, zum Beispiel:

member/2, um auszudrücken, dass ein Element in einer Listevorkommt

append/3, um auszudrücken, dass eine Liste dieAneinanderhängung zweier bestimmter Listen ist

length/2, um auszudrücken, welche Länge eine Liste hat

Logik Logikprogrammierung – Listen 158

Vordefinierte Prädikate auf Listen

Interessant dabei ist, dass (ganz im Sinne „unseres“ add/3-Prädikates)diverse Aufrufmodi der Listenprädikate funktionieren. Zum Beispiel:

?− member ( 3 , [ 1 , 2 , 3 , 4 , 5 ] ) .t r ue .

?− member (X , [ 1 , 2 , 3 ] ) .X = 1 ;X = 2 ;X = 3.

?− member ( 3 , [X ,Y, Z ] ) .X = 3 ;Y = 3 ;Z = 3.



Auch für die anderen Listenprädikate, zum Beispiel:

?− append ( [ 1 , 2 , 3 ] , [ 4 , 5 ] , L ) .L = [ 1 , 2 , 3 , 4 , 5 ] .

?− append (X,Y , [ a , b ] ) .X = [ ] , Y = [ a , b ] ;X = [ a ] , Y = [ b ] ;X = [ a , b ] , Y = [ ] .

?− append (X,X , [ a , b ] ) .f a l s e .

?− append (X,X , [ a ,Y ] ) .X = [ a ] , Y = a .



Sowie:

?− l eng th ( [ a , b , c ] ,N ) .N = 3.

?− l eng th ( L , 3 ) .L = [ _1570 , _1576 , _1582 ] .

?− l eng th ( L , 3 ) , append (X,X, L ) .f a l s e .

?− l eng th ( L , 4 ) , append (X,X, L ) .L = [ _1610 , _1616 , _1610 , _1616 ] , X = [ _1610 , _1616 ] .

?− l eng th ( L , 2 ) , member ( a , L ) ,member ( b , L ) ,member ( c , L ) .f a l s e .


Definition von Prädikaten auf Listen

Definiert werden Prädikate auf Listen typischerweise durch Verwendungbereits vorhandener:

i n s e r t (X, L ,R) :− append (U,V, L ) , append (U , [ X ] ,Y) ,append (Y,V,R ) .

und/oder Rekursion:

permutat ion ( [ ] , [ ] ) .permutat ion ( L ,P) :− append ( [ X ] ,Y, L ) , permutat ion (Y, Z ) ,

i n s e r t (X, Z ,P ) .

Mit obigen Definitionen, zum Beispiel:

?− permutat ion ( [ 1 , 2 , 3 ] , L )L = [ 1 , 2 , 3 ] ;L = [ 2 , 1 , 3 ] ;. . .


Generate-and-Test – Das „Was“ und das „Wie“

Angenommen, wir möchten Listen sortieren können, also zum BeispielAnfragen wie

?− sor t ingTo ( [ 4 , 2 , 6 , 9 , 1 ] ,R ) .

stellen können, und darauf als Antwort

R = [ 1 , 2 , 4 , 6 , 9 ] .

erhalten.

Also was wollen wir genau?

Logik Logikprogrammierung – Generate-and-Test 163


Die gewünschte Eigenschaft der Ergebnisliste können wir relativ leicht alsProlog-Prädikat ausdrücken:

i sSor ted ( [ ] ) .i sSor ted ( [ _ ] ) .i sSor ted ( Xs ) :− append ( [ X,Y ] , Ys , Xs ) , X =< Y,

append ( [ Y ] , Ys , Zs ) , i sSor ted ( Zs ) .

Dann gilt zum Beispiel:

?− i sSor ted ( [ 4 , 2 , 6 , 9 , 1 ] ) .f a l s e .?− i sSor ted ( [ 1 , 2 , 4 , 6 , 9 ] ) .t r ue .

Und wie können wir eine solche passende Liste herstellen?



Nun, eine recht naive, aber funktionierende Lösung wäre:

sor t ingTo ( Xs , Ys ) :− permutat ion ( Xs , Ys ) , i sSor ted ( Ys ) .

Dann in der Tat:

?− sor t ingTo ( [ 4 , 2 , 6 , 9 , 1 ] ,R ) .R = [ 1 , 2 , 4 , 6 , 9 ] .

Prinzip hier:

Um eine Regel auf Eingaben zu formulieren, die genau dann true liefert,wenn eine gültige Lösung des Problems vorliegt, Zerlegung in zwei Teile:

Generate-Teil definiert einen Suchraum.

Test-Teil definiert die Lösungsbedingung, die erfüllt sein soll.


Generate-and-Test – Weitere Beispiele

Aufgabe: Ermittle alle Möglichkeiten, bei dreimaligem Würfeln insgesamt15 Punkte zu erzielen.

Lösung:

?− W = [1 ,2 ,3 ,4 ,5 ,6 ] , member (A,W) , member (B,W) ,member (C,W) , A + B + C =:= 15.



Aufgabe: Ermittle alle Möglichkeiten, bei dreimaligem Würfeln mitverschiedenen Augenzahlen insgesamt 15 Punkte zu er-zielen.

Lösung:

?− W = [1 ,2 ,3 ,4 ,5 ,6 ] , member (A,W) , member (B,W) ,member (C,W) , A \= B, A \= C, B \= C,A + B + C =:= 15.

oder:

?− permutat ion ( [ 1 , 2 , 3 , 4 , 5 , 6 ] , [A ,B,C, _ , _ , _ ] ) ,A + B + C =:= 15.



Aufgabe: Ermittle alle Möglichkeiten, bei dreimaligem Würfeln mit ver-schiedenen Augenzahlen in aufsteigender Reihenfolge insge-samt 15 Punkte zu erzielen.

Lösung:

?− permutat ion ( [ 1 , 2 , 3 , 4 , 5 , 6 ] , [A ,B,C, _ , _ , _ ] ) ,i sSor ted ( [ A,B,C] ) , A + B + C =:= 15.

Generate-and-Test ist sinnvoll einzusetzen bei nicht-trivialenkombinatorischen Problemen, wenn

die Menge der potentiellen Lösungen endlich oder besser sogarrecht klein ist, oder

man keine Vorstellung darüber hat, wie systematisch schneller eineLösung gefunden werden könnte.


Beispiel: Krypto-Arithmetik

ABB – CD = EED

– –

FD + EF =

*

CE

=

EGD

=

FH

=

?*

=

=

Jeder Buchstabe entspreche einer anderen Ziffer.

Wie lautet eine gültige Belegung?



solve (A,B,C,D,E, F ,G,H) :− generate (A,B,C,D,E, F ,G,H) ,t e s t (A,B,C,D,E, F ,G,H) .

generate (A,B,C,D,E, F ,G,H) :−permutat ion ( [0 ,1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ] ,

[A ,B,C,D,E, F ,G,H, _ , _ ] ) .

t e s t (A,B,C,D,E, F ,G,H) :− ???

Zum Beispiel die erste Zeile entspricht:

(A * 100 + B * 10 + B) − (C * 10 + D)=:= E * 100 + E * 10 + D

Und die erste Spalte:

(A * 100 + B * 10 + B) − (F * 10 + D)=:= E * 100 + G * 10 + D



Zweite Zeile und zweite Spalte:

(F * 10 + D) + (E * 10 + F) =:= C * 10 + E,(C * 10 + D) − (E * 10 + F) =:= F * 10 + H

Schließlich noch die Bedingung, dass gleiches Ergebnis in letzter Zeileund letzter Spalte:

(E * 100 + E * 10 + D) * (C * 10 + E)=:= (E * 100 + G * 10 + D) * (F * 10 + H)



Insgesamt für den Test-Teil:

t e s t (A,B,C,D,E, F ,G,H) :−(A * 100 + B * 10 + B) − (C * 10 + D)

=:= E * 100 + E * 10 + D,(A * 100 + B * 10 + B) − (F * 10 + D)

=:= E * 100 + G * 10 + D,(F * 10 + D) + (E * 10 + F) =:= C * 10 + E,(C * 10 + D) − (E * 10 + F) =:= F * 10 + H,(E * 100 + E * 10 + D) * (C * 10 + E)

=:= (E * 100 + G * 10 + D) * (F * 10 + H) .

Als eindeutige erfüllende Belegung findet Prolog mit der Anfrage

?− solve (A,B,C,D,E, F ,G,H) .

dies: A = 2, B = 0, C = 8, D = 5, E = 1, F = 6, G = 3, H = 9.Logik Logikprogrammierung – Generate-and-Test 172

Beispiel: Krypto-Arithmetik – Lösung

200 – 85 = 115

– –

65 + 16 =

*

81

=

135

=

69

=

9315*

=

=


Beispiel: Einstein’s Riddle

Zur Erinnerung:



Versuchen wir, das Rätsel per Generate-and-Test zu lösen.

Für den Generate-Teil wäre zunächst einfach denkbar:

Houses = [ _ , _ , _ , _ , _ ]

Oder auch bereits:

Houses = [ [ _ , _ , _ , _ , _ ], [ _ , _ , _ , _ , _ ], [ _ , _ , _ , _ , _ ], [ _ , _ , _ , _ , _ ], [ _ , _ , _ , _ , _ ] ]



Für den Test-Teil nehmen wir uns die einzelnen Hinweise vor.

Zum Beispiel:

1. The Englishman lives in the red house.

Unter der Festlegung, dass wir die einzelnen Attribute jeweils in derReihenfolge „color“, „nationality“, „drink“, „pet“, „smoke“ angeben werden,können wir diesen ersten Hinweis wie folgt ausdrücken:

member ( [ red , englishman , _ , _ , _ ] , Houses )

Analog:

2. The Spaniard owns the dog.

wird zu:

member ( [ _ , spaniard , _ , dog , _ ] , Houses )Logik Logikprogrammierung – Generate-and-Test 176


Die nächsten beiden Hinweise:

3. Coffee is drunk in the green house.

4. The Ukrainian drinks tea.

werden auch analog behandelt:

member ( [ green , _ , cof fee , _ , _ ] , Houses )

bzw.:

member ( [ _ , uk ra in ian , tea , _ , _ ] , Houses )



Dann wird es wieder etwas interessanter:

5. The green house is immediately to the right of the ivory house.

Das könnten wir so ausdrücken:

r i g h t O f ( [ green , _ , _ , _ , _ ] ,[ i vo ry , _ , _ , _ , _ ] ,Houses )

wenn wir ein solches Prädikat hätten.

Definieren wir es uns doch einfach:

r i g h t O f (R, L , L i s t ) :− append ( Pre f i x , _ , L i s t ) ,append ( _ , [ L ,R] , P r e f i x ) .



Nun kommen nochmal zwei sehr einfach umzusetzende Hinweise:

6. The Winston smoker owns snails.

7. Kools are smoked in the yellow house.

Dann wieder spannender:

8. Milk is drunk in the middle house.

9. The Norwegian lives in the leftmost house.

Diese beiden können wir umsetzen, indem wir

Houses = . . .

verfeinern zu:

Houses = [ [ _ , norwegian , _ , _ , _ ] , _, [ _ , _ , mi lk , _ , _ ] , _ , _ ]



Für den nächsten Hinweis:

10. The man who smokes Chesterfield lives in the house next to the manwith the fox.

brauchen wir nochmal ein Hilfsprädikat:

nextTo ( [ _ , _ , _ , _ , c h e s t e r f i e l d ] ,[ _ , _ , _ , fox , _ ] ,Houses )

welches wir wie folgt definieren können:

nextTo (X,Y, L i s t ) :− r i g h t O f (X,Y, L i s t ) .nextTo (X,Y, L i s t ) :− r i g h t O f (Y,X, L i s t ) .



Die restlichen Hinweise:

11. Kools are smoked in the house next to the house where the horse iskept.

12. The Lucky Strike smoker drinks orange juice.

13. The Japanese smokes Parliaments.

14. The Norwegian lives next to the blue house.

lassen sich dann alle analog zu schon vertrauten umsetzen.

Es bleibt noch, letztlich den Zebra-Besitzer und den Wasser-Trinker zubestimmen.

Dazu können Variablen und weitere member-Aufrufe verwendet werden.


Beispiel: Einstein’s Riddle – Gesamtlösung


Übergang zur Prädikatenlogik

Was bisher geschah:

1. AussagenlogikSprache der Aussagenlogik (AL)Wahrheitstafeln, Status von FormelnNormalformen und ÄquivalenzenResolutionsverfahren der ALAL-Hornformeln und der Markierungsalgorithmus

2. Logikprogrammierung in PrologSprachelementeProlog-Ausführung (unter Verwendung von Resolution!)Programmieren mit RelationenRekursion und ListenverarbeitungGenerate-and-Test

Logik Prädikatenlogik 183


Was uns ab jetzt beschäftigen wird:

3. PrädikatenlogikSprache der Prädikatenlogik (PL), mit Variablen und QuantorenStatus von Formeln, Normalformen und ÄquivalenzenResolutionsverfahren der PL

Zur Unterscheidung zwischen Aussagen- und Prädikatenlogik hatte ichzuvor auf solche Beispiele verwiesen:

Aussagenlogik:„Es regnet und die Straße ist nass.“ – R ∧ N„Wenn die Straße nicht nass ist, dann regnet es nicht.“ – ¬N⇒¬R

Prädikatenlogik:„Für jede natürliche Zahl x gilt, dass es eine natürliche Zahl y gibt, sodass x kleiner als y ist.“ – ∀x : ∃y : (x < y)



Auch die eingangs diskutierten Syllogismen passen in diePrädikatenlogik, etwa:

Wenn alle Menschen sterblich sind und Sokrates ein Mensch ist,dann ist Sokrates sterblich.

Wenn wer im grünen Haus wohnt Kaffee trinkt, und X im grünenHaus wohnt, dann trinkt X Kaffee.

oder:

Keine Blume ist ein Tier.Alle Hunde sind Tiere.Keine Blume ist ein Hund.

Alle Aliens sind Säugetiere.Alle Aliens leben im Meer.Einige Säugetiere leben im Meer.



Was in der Prädikatenlogik ähnlich zu Prolog sein wird:

Verwendung von Prädikaten (in PL, auch „Relationssymbole“)

Verwendung von Datenkonstruktoren (in PL, „Funktionssymbole“)

Verwendung von Variablen (in PL, in der Regel klein geschrieben)

Was wir aus der Prolog-Programmierung nicht in unsere Beschäftigungmit Prädikatenlogik übernehmen werden:

arithmetische Interpretation von Zahlen, Arbeit mit Listen

rekursive Definition/Ausführung, Generate-and-Test

Davon abgesehen lassen sich Prolog-Programme im Prinzip in diePrädikatenlogik „einbetten“.



Andererseits ist Prädikatenlogik echt „mehr“ als Prolog.

Denn neben anderer Syntax für die Verknüpfungsoperationen (etwawieder „ ∧ “ und „ ∨ “ statt „ , “ und „ ; “) kommen neu die Quantoren∀ und ∃ hinzu, welche auch semantisch große Auswirkungen haben.

Außerdem beschränken wir uns in der Prädikatenlogik nicht mehr aufHornklauseln.

Wieder relevant werden dann die aus der Aussagenlogik bekanntenNormalformen KNF/DNF.



Auch aus der Aussagenlogik übernommen (und teils erweitert) werden diefolgenden Konzepte:

(passende) Belegung, und Zuordnung Wahrheitswert zu Formel

Status von Formeln („erfüllbar“ etc.), Spiegelungsprinzip

Äquivalenzen und Umformungen

Resolution für Formeln in Mengenschreibweise

Speziell für Resolution wird gelten:

anders als in Prolog, nicht mehr nur lineare/SLD-Resolution,

aber wie in Prolog, Berücksichtigung von Variablen.

Aus der Aussagenlogik ab jetzt eher nicht relevant:

Min/Max-Terme

MarkierungsalgorithmusLogik Prädikatenlogik 188

Documents

Einführung in die Logik