Eine erste Problemstellung

Aus Informatik
Wechseln zu: Navigation, Suche

Unter einem wissensbasierten System (z. B. einem Prolog-System) wird ein auf EDV-Anlagen ausführbares Programmsystem verstanden, das einem Anwender, auf Anfrage hin, Informationen aus einem bestimmten Erfahrungsbereich bereitstellen kann. Wir lernen die Arbeitsweise eines wissensbasierten Systems kennen, indem wir als Entwickler und Anwender ein konkretes Problem bearbeiten (learning by doing).

Problemstellung

Gegeben sind folgende Beziehungen zwischen einer beliebig gewählten Personengruppe:

  • Peter liebt Susi.
  • Hans liebt Susi und Sabine.
  • Sabine liebt Peter und hasst Hans.
  • Susi liebt Peter und Felix.
  • Susi hasst Sabine.
  • Peter hasst Felix.
  • Felix liebt sich selbst.

Zu diesen Beziehungsaussagen lassen sich nun verschiedene Fragen formulieren, z. B.:

  1. Wen liebt Sabine? Wer liebt Sabine? Wer liebt wen?
  2. Wer liebt jemanden, der ihn auch liebt?
  3. Wessen Liebe wird mit Hass vergolten?


Aufgabe 1

Beantworte die oben gestellten Fragen auf der Basis der gegebenen Beziehungsaussagen.


Bearbeitung mit bekannten Möglichkeiten

Das Beantworten der Fragen "per Hand" sollte kein Problem darstellen. Allerdings dürfte diese Vorgehensweise für komplexere Problemstellungen nicht wirklich geeignet sein.

Prüfen wir daher, ob wir mit den uns (aus dem Informatikunterricht) bekannten Möglichkeiten weiter kommen.

Aufgabe 2

Wie müsste ein Programm (Java, Delphi, ...) aussehen, welches unser Problem lösen kann.

  • Beschreibe, wie die Aussagen erfasst werden könnten.
  • Wie könnten die einzelnen Fragen gestellt werden? Wie werden die Antworten gefunden?
  • Wie flexibel wäre ein solches Programm hinsichtlich der Datenbasis (Aussagen über Beziehungen) und möglicher (neuer) Fragen?


Eventuell funktioniert es so besser:

Aufgabe 3

Das gegebene Problem soll durch eine SQL-Datenbank gelöst werden.

  • Erstelle ein geeignetes ERM und leite daraus das RM ab.
  • Gib geeignete Abfragen für unser Problem an.
  • Wie flexibel wäre ein solches DB-System hinsichtlich der Datenbasis (Aussagen über Beziehungen) und möglicher (neuer) Fragen?

Bearbeitung der Problemstellung mit Prolog

Was soll nun mit Prolog anders werden? Prolog ist eine Programmiersprache mit einem grundlegend anderen Programmierparadigma als Delphi oder SQL. Sie gehört ebenfalls einer anderen Generation von Programmiersprachen an.

Gut, Prolog ist also eine deklarative, logische Programmiersprache und gehört zur 5. Generation der Programmiersprachen ... aber wie hilft uns das bei unserem Problem weiter? Nun, der wichtigste Unterschied (zu Delphi) besteht darin, dass wir uns um das WIE des Problemlösens keine Gedanken mehr machen müssen. Denken wir an Aufgabe 2, war gerade dies unser Problem. Der Unterschied zur Lösung mit einer Datenbank und einer Datenbankabfragesprache wie SQL dürfte in einer wesentlich einfacheren Formulierung der Datenbasis und der Abfragen (bzw. dann Anfragen) bestehen. In Prolog geben wir nur noch an, WAS wir wissen bzw. wissen wollen.

Ein Prolog-Programm besteht aus Fakten, Regeln und Anfragen. Fakten und Regeln werden in das Prolog-Programm geschrieben und dann in die Wissensbasis des Prolog-Interpreters geladen (konsultiert). Mit Anfragen an diesen Interpreter wird dann das Programm ausgeführt.

Regeln und Fakten als Wissensbasis

Setzen wir nun das zu Beginn gegebene Problem in einem Prolog-Programm um. Zuerst beschreiben wir die gegebenen Beziehungen als Fakten. Diese können in Prolog folgendermaßen erfasst werden:

liebt(peter, susi).
liebt(hans, susi).
liebt(hans, sabine).
liebt(sabine, peter).
liebt(susi, peter).
liebt(susi, felix).
liebt(felix, felix).

hasst(sabine, hans).
hasst(susi, sabine).
hasst(peter, felix).

An diesen Beispielen sind einige grundlegende Vereinbarungen für die Prolog-Syntax erkennbar:

  • Jedes Faktum beginnt mit einem Namen (Funktor), welcher mit einem Kleinbuchstaben beginnen muss.
  • In Klammern folgt eine Liste von Argumenten.
  • Eine Faktendefinition schließt mit einem Punkt.
  • Konstanten - also in unserem Fall die Namen - werden immer klein geschrieben. (Möchte man die Namen dennoch groß schreiben, setzt man diese in Anführungszeichen.)
  • Beginnt ein Bezeichner mit Großbuchstaben, steht er für eine Variable.

Prolog unterscheidet also zwischen Groß- und Kleinschreibung, d. h. Peter und peter haben eine unterschiedliche Bedeutung für den Prolog-Interpreter.

Da einzelne Fakten (und später auch Regeln) durchaus unterschiedlich interpretiert werden können, sollte man von Beginn an auf eine ausreichende Dokumentation achten. In unserem Fall könnte liebt(peter,susi). mit "Peter liebt Susi." oder auch mit "Peter wird von Susi geliebt." interpretiert werden. Daher sollte unser erstes Prolog-Programm schließlich das folgende Aussehen haben:

% liebt(X,Y) -- X liebt Y
liebt(peter, susi).
liebt(hans, susi).
liebt(hans, sabine).
liebt(sabine, peter).
liebt(susi, peter).
liebt(susi, felix).
liebt(felix, felix).

% hasst(X,Y) -- X hasst Y
hasst(sabine, hans).
hasst(susi, sabine).
hasst(peter, felix).

Anfragen an die Wissensbasis

Um zu den festgelegten Fakten Anfragen stellen zu können, muss das Prolog-Programm in die Wissensbasis geladen werden. Dies geschieht mit dem Befehl consult(), wobei in Klammern der Name des gewünschten Programms stehen muss. Im SWI-Prolog-Editor genügt es allerdings, den entsprechenden Button zu drücken. Hat alles funktioniert, dürfte etwa diese Meldung im SWI-Prolog-Fenster zu sehen sein:

1 ?- consult('lieben_hassen.pl').
% lieben_hassen.pl compiled 0.02 sec, 212 bytes

Yes

Die 1 ist lediglich eine Zeilennummerierung (Deshalb lassen wir diese in Zukunft auch weg.). Zu Erkennen ist, dass auch Anfragen (z. B. consult) mit einem Punkt abgeschlossen werden müssen.

Nun können wir uns den Anfragen widmen. Dabei ist es notwendig, die Struktur der Fakten zu kennen. Die Frage "Wen liebt Sabine?" ist über die Fakten liebt(X,Y). zu beantworten, wobei nach unserer Definition an erster Stelle sabine stehen müsste. Damit ergibt sich folgende Anfrage (und Antwort) an den Prolog-Interpreter:

?- liebt(sabine,X).

X = peter

Damit wäre die erste Frage beantwortet: Peter. Die nächsten zwei Fragen sollten dann kein Problem darstellen:

?- liebt(X,sabine).
...
?- liebt(X,Y).

Mit Großbuchstaben (bzw. Bezeichnern mit großen Anfangsbuchstaben) werden Variablen definiert, die mit möglichen Lösungen belegt (unifiziert) werden. Der Prolog-Interpreter gestattet allerdings auch folgende Anfragen:

?- hasst(felix,susi).
?- liebt(sabine,_).
?- hasst(_,sabine).
?- liebt(_,_).
Aufgabe 4

Formuliere zu den oben gegebenen Anfragen geeignete Fragestellungen und teste diese in SWI-Prolog.


Die nächste Frage "Wer liebt jemanden, der ihn auch liebt?" stellt eigentlich eine Konjunktion (UND-Verknüpfung) zweier Anfragen dar. Eine Konjunktion zweier Anfragen kann durch ein "," (Komma) realisiert werden. So könnten wir erstmal fragen, ob z. B. Sabine oder Susi jemanden lieben, der sie auch liebt:

?- liebt(sabine,X), liebt(X,sabine).
?- liebt(susi,X), liebt(X,susi).

Um die ursprüngliche Frage beantwortet zu bekommen, müsste nun nur noch eine Kleinigkeit geändert werden:

?- liebt(Y,X), liebt(X,Y).

Stellen wir diese Anfrage, bekommen wir drei Lösungen. Dabei ist die Lösung mit dem Liebespaar Susi und Peter doppelt. Dies ist aus logischer Sicht auch völlig korrekt, da der Prolog-Interpreter einmal testet, ob Susi auch wieder geliebt wird und dieses danach auch für Peter überprüft.

Regeln

Um die letzte Frage zu beantworten, kann auch eine Regel definiert werden. Eine Regel stellt eine logische Aussage in Wenn-Dann-Form dar. Mit einer Regel können aus bekannten Fakten neue Fakten logisch gefolgert werden.

% grosseLiebe(X,Y) -- X und Y lieben sich gegenseitig
grosseLiebe(X,Y) :-
  liebt(X,Y),
  liebt(Y,X).

Jede Regel besteht aus drei Teilen: dem Regelkopf, dem Prolog-Atom ":-" und einem Regelrumpf. Der Regelkopf stellt die logische Schlussfolgerung (Konklusion) dar, welche sich aus dem Regelrumpf ergibt, der Regelrumpf enthält die Konjunktion aller Bedingungen.

Da es in unserem Fall ungünstig ist, Felix mit Felix zu "verkuppeln", sollten wir ausschließen, dass Y und X in der Regel identisch sind:

% grosseLiebe(X,Y) -- X und Y lieben sich gegenseitig
grosseLiebe(X,Y) :-
  liebt(X,Y),
  liebt(Y,X),
  X \== Y.
Aufgabe 5

Formuliere eine Regel ungluecklicheLiebe(X,Y), mit der sich die 3. Frage unseres Eingangsproblems lösen lässt.