HSG

Aktuelle Seite: HSG/Fächer/Informatik/Material/Prolog/Logik-Probleme

Aufgabe bungsaufgabe 4, 2.Übungsblatt, Rechnersysteme WS00/01 Uni Kaiserslautern

Anna, Bert, Cordula, Dirk und Erik verabreden sich fürs Kino. Dabei treten allerdings folgende Bedingungen auf:
  1. Geht Anna ins Kino, so müssen auch Cordula und Erik gehen.
  2. Wenn Anna nicht ins Kino geht, so geht Erik.
  3. Bert und Erik wollen zusammen ins Kino oder keiner von beiden.
  4. Wenn Cordula ins Kino geht, dann auch Dirk.
  5. Bert geht genau dann, wenn Dirk nicht geht und umgekehrt.

Formale Übersetzung der Bedingungen

Abkürzungen: A = Anna geht ins Kino; B = Bert geht ins Kino; ...
  1. A => CE   ( A→C∧E )
  2. /A => E   ( ¬A→E )
  3. BE + /B/E   ( (B∧E)∨(¬B∧¬E) )
  4. C => D   ( C→D )
  5. B /D   ( B↔¬D )
Gesucht ist eine Belegung der Variablen A,B,C,D und E mit Wahrheitswerten (z.B. 0 und 1), so dass alle Bedingungen wahr werden. Prolog enthält keine vordefinierten Prädikate für die üblichen logischen Funktionen. Die sind aber (nach einer Vorlage von H.-U.Zimmermann, Grundkurs Informatik) schnell geschrieben:
nicht(0,1).
nicht(1,0).

oder(0,0,0).
oder(0,1,1).
oder(1,0,1).
oder(1,1,1).

und(0,0,0).
und(0,1,0).
und(1,0,0).
und(1,1,1).

exor(0,0,0).
exor(0,1,1).
exor(1,0,1).
exor(1,1,0).

impl(0,0,1).
impl(0,1,1).
impl(1,0,0).
impl(1,1,1).

equ(0,0,1).
equ(0,1,0).
equ(1,0,0).
equ(1,1,1).
Nun müssen nur noch die Bedingungen übersetzt werden:
loesung(A,B,C,D,E):-und(C,E,E1),impl(A,E1,1),
                    nicht(A,NotA),impl(NotA,E,1),
                    nicht(B,NotB),nicht(E,NotE),und(B,E,E2),und(NotB,NotE,E3),
                    oder(E2,E3,1),
                    impl(C,D,1),
                    nicht(D,NotD),equ(B,NotD,1).
Man beachte, wie z.B. in und(C,E,E1) zuerst ein Zwischenergebnis E1 errechnet wird, das dann in das Prädikat impl(A,E1,1) eingesetzt wird. Letzteres ist so zu lesen: A und E1 sind so zu wählen, dass die Implikation wahr (1) wird.

Jetzt ist das Problem schnell gelöst:
?- loesung(A,B,C,D,E).

A = 0
B = 1
C = 0
D = 0
E = 1 ;

No
Bert und Erik gehen also ins Kino.

Aufgabe

Der anspruchsvolle Gast aus Grundkurs Informatik von H.-U.Zimmermann
Der Mann, den sie Doc nannten, war in der Kneipe noch nie gesehen worden. Seine stechenden Augen und die riesigen, behaarten Hände hätte sich der Wirt bestimmt gemerkt. Er legte leise und behutsam den Colt auf den Schanktisch, lächelte sardonisch und begann in dozierendem Ton: ”Wirt, ich werde dich ungeschoren lassen, wenn du genau auf meine Trinkgewohnheiten achtest.
  1. Du musst mir jedesmal Aquavit servieren, wenn du mir kein Bier bringst.
  2. Schenkst du beides ein, dann wage nicht, mir zugleich Cognac anzubieten.
  3. Trägst Du aber Cognac auf oder bringst du mir kein Bier, rate ich dir gut, mich mit Aquavit zu verschonen
Ich werde dich dreimal rufen und du musst mir jedesmal eine andere Zusammenstellung bringen”.

Der Wirt betrachtete nachdenklich die trommelnden Finger des ungebetenen Gastes, schrieb ein kurzes PROLOG - Programm und bediente gemäß der Antworten des Rechners seinen Gast. Der Gast war von der raschen Lösung so beeindruckt, dass er ebenfalls PROLOG erlernen wollte. Der Wirt gab ihm die Telefonnummer des Abendgymnasiums....
  1. Überführen Sie die Aussagen des Gastes in die Schreibweise der Aussagenlogik. A steht für ”Aquavit servieren”, ¬A steht für ”kein Aquavit servieren” usw.
  2. Lösen Sie das Problem mit Hilfe geeigneter Wahrheitswertetabellen.
  3. Implementieren Sie eine Umsetzung als PROLOG-Programm.