P1-WS04-MusterLoesung04.txt

1 a) Falsch. Die folgende intensional spezifizierte Relation ist leer:

     { (x,y) | x ist Element von N, 
               y ist Element von N, 
               x > y,
               y = 2 * x }

  b) Wahr. Relationen sind Teilmengen von Kreuzprodukten, und in
     diesen herrscht immer eine konstante Stelligkeit.

  c) Falsch. Beispielsweise ist die Relation `größer oder gleich'
     reflexiv, aber aus 3 >= 2 folgt nicht 2 >= 3.

  d) Falsch. Diese Relation ist linkseindeutig und transitiv:

     { (1,2), (1,3), (1,4) }

     Das liegt allerdings nur daran, daß die Prämisse "a·b und b·c"
     niemals erfüllt ist, die Relation ist also auf triviale und damit
     uninteressante Weise transitiv. 

     Wenn mindestens ein Element der Bildmenge auch in der Urbildmenge
     enthalten ist, ist die Aussage wahr. Wäre zum Beispiel das Paar
     (0,1) enthalten, so müßte laut Transitivitäts-Definition auch 
     (0,2) enthalten sein; und (0,2) und (1,2) verstoßen gemeinsam
     gegen die Linkseindeutigkeit.
     


2) 

% kind_von(?Kind, ?Mensch)
% Gelingt, wenn Mensch Vater oder Mutter von Kind ist.
kind_von(Kind, Mensch) :- vater_von(Mensch, Kind).
kind_von(Kind, Mensch) :- mutter_von(Mensch, Kind).

% vorfahre( ?Ahn, ?Mensch)
% Gelingt, wenn Mensch in direkter Linie von Ahn abstammt.
vorfahre(Ahn, Mensch) :- kind_von(Mensch, Ahn).
vorfahre(Ahn, Mensch) :-
        kind_von(Kind, Ahn),
        vorfahre(Kind, Mensch).



Test:
-----

?- vorfahre(julia, helga).

Yes
?- vorfahre(walter, otto).

No
?- vorfahre(Vorfahr, hans).

Vorfahr = otto ;

Vorfahr = marie ;

Vorfahr = gerd ;

Vorfahr = julia ;

No
?- vorfahre(charlotte, Nachfahr).

Nachfahr = barbara ;

Nachfahr = magdalena ;

Nachfahr = klaus ;

Nachfahr = andrea ;

No

?- vorfahre(Vorfahr,Nachfahr).

Vorfahr = otto
Nachfahr = hans ;

Vorfahr = otto
Nachfahr = helga ;

Vorfahr = gerd
Nachfahr = otto ;

Vorfahr = johannes
Nachfahr = klaus ;

Vorfahr = johannes
Nachfahr = andrea ;

Vorfahr = walter
Nachfahr = barbara ;

Vorfahr = walter
Nachfahr = magdalena ;

Vorfahr = marie
Nachfahr = hans ;

Vorfahr = marie
Nachfahr = helga ;

Vorfahr = julia
Nachfahr = otto ;

Vorfahr = barbara
Nachfahr = klaus ;

Vorfahr = barbara
Nachfahr = andrea ;

Vorfahr = charlotte
Nachfahr = barbara ;

Vorfahr = charlotte
Nachfahr = magdalena ;

Vorfahr = gerd
Nachfahr = hans ;

Vorfahr = gerd
Nachfahr = helga ;

Vorfahr = walter
Nachfahr = klaus ;

Vorfahr = walter
Nachfahr = andrea ;

Vorfahr = julia
Nachfahr = hans ;

Vorfahr = julia
Nachfahr = helga ;

Vorfahr = charlotte
Nachfahr = klaus ;

Vorfahr = charlotte
Nachfahr = andrea ;

No
?- 

Das Prädikat liefert alle errechenbaren Beziehungen genau einmal. Es
ist terminierungssicher in jeder Instanziierungsvariante.

Die Relation `ist Vorfahr' ist antisymmetrisch (mein Vorfahr muß einer
früheren Generation angehören und kann daher nicht Nachfahr sein) und
irreflexiv (aus demselben Grund). Sie ist außerdem transitiv.


3 a) Ein Knoten ist an das Wassernetz angeschlossen, wenn er 

 I  ein Wasserwerk ist
 II an einen angeschlossenen Knoten angeschlossen ist.

Eine Region ist auf dem Trockenen, wenn sie nicht ans Wassernetz
angeschlossen ist. Also:


% versorgt(?Ort)
% Gelingt, wenn der Netzknoten Ort mit Wasser versorgt ist.
versorgt(Ort) :-
  wasserwerk(Ort).

versorgt(Ort) :-
  ist_angeschlossen_an(Ort,Ort2),
  versorgt(Ort2).
  
% auf_dem_trockenen(?Ort)
% Gelingt, wenn die Region Ort nicht an die Wasserversorgung
% angeschlossen ist.
auf_dem_trockenen(Ort) :-
  region(Ort),
  not(versorgt(Ort)).

b) Knoten A wird von Knoten B mit Trinkwasser versorgt, wenn
er direkt oder indirekt an ihn angeschlossen ist und B Trinkwasser zu
vergeben hat. (Das bloße Angeschlossensein reicht nicht - zwei
miteinander verbundene Orte könnten ja beide vom Netz getrennt sein.)

% wird_versorgt_von(?Senke,?Quelle)
% Gelingt, wenn Senke von Quelle mit Trinkwasser versorgt wird.
wird_versorgt_von(Senke,Quelle) :-
  ist_angeschlossen_an(Senke,Quelle),
  versorgt(Quelle).

wird_versorgt_von(Senke,Quelle) :-
  ist_angeschlossen_an(Senke,Ort),
  wird_versorgt_von(Ort,Quelle).

Dies Prädikat terminiert nur deshalb immer, weil das zugrundeliegende
Wassernetz keine Zyklen enthält.

c) Dies Prädkat ist eine Kombination der Lösung zu b) mit den
vorgegebenen Fakten.

% region_wird_versorgt_von_wasserwerk(?Region, ?W)
% Gelingt, wenn Region letztlich von Wasserwerk
% mit Wasser versorgt wird.
region_wird_versorgt_von_wasserwerk(Region,Wasserwerk) :-
  region(Region),
  wasserwerk(Wasserwerk),
  wird_versorgt_von(Region,Wasserwerk).

d) Es müssen all jene Orte gewarnt werden, die vom gestörten
Wasserwerk versorgt oder mitversorgt werden: Bei einem Ausfall erhält
Humbarg zwar weiterhin Wasser von den anderen Wasserwerken, aber
insgesamt weniger. (Wir sortieren die berechnete Liste nur deshalb, um
Doppelte zu entfernen.)

% ort_muß_gewarnt_werden(+Wasserwerk, -Orte)
% Berechnet zu einem Wasserwerk die Orte, die von dessen
% Störung betroffen sein können.
ort_muß_gewarnt_werden(Wasserwerk, Orte) :-
  findall(Ort, region_wird_versorgt_von_wasserwerk(Ort, Wasserwerk), L),
  sort(L, Orte).

e) Es müssen genau jene Orte gewarnt werden, die teilweise von W
versorgt werden, also solche, die mindestens einen anderen Versorger
besitzen.

% ort_muß_vor_einschränkung_gewarnt_werden(+Wasserwerk, -Orte)
% Berechnet zu einem Wasserwerk die Orte, deren Wasserversorgung 
% bei einer Störung des Wasserwerks nur eingeschränkt wird.
ort_muß_vor_einschränkung_gewarnt_werden(Wasserwerk, Orte) :-
  findall(Ort,
          (region_wird_versorgt_von_wasserwerk(Ort, Wasserwerk),
           region_wird_versorgt_von_wasserwerk(Ort, Wasserwerk2),
           Wasserwerk \= Wasserwerk2),
          L),
  sort(L, Orte).

f) Die Versorgungsrelation ist laut Aufgabenstellung transitiv und
antisymmetrisch. Sie ist außerdem (laut Lösung) irreflexiv; obwohl
vermutlich die Kantine im Wasserwerk Riesberg vom Werk selbst versorgt
wird, wird diese Beziehung durch wird_versorgt_von/2 nicht erfaßt,
d.h. wird_versorgt_von(X,X) gelingt nie.

4 a) Typische symmetrische Relationen sind solche, die jeweils zwei
Dingen dieselbe Eigenschaft zuschreiben:

  A hat dieselbe Nationalität wie B
  A und B liegen weniger als 10km entfernt
  A darf für B in Formeln substituiert werden

Die Symmetrie geht verloren, wenn eine Beziehung einseitig sein kann:

  A liebt B (unglücklich)
  A hat eine billige Flugverbindung nach B 
    (im Zeitalter der Lockangebote)

b) 1:m-Relationen sind solche, die Funktionen (eindeutige Abbildungen)
beschreiben:

  A ist der Vater von B
  A ist die Quersumme von B
  A ist der Geburtstag von B

Wenn mehr als ein Paar möglich ist, ist die Eigenschaft verletzt:

  A ist der Trainer von B
    (Ostblockteams haben mehr Trainer als Athleten)
  Autor A hat Buch B verfaßt
    (es gibt Kollaborationen)

c) Transitive Relationen sind solche, die sich über mehrere
Verknüpfungen fortsetzen:

  A ist größer als B
  A könnte B angesteckt haben
  A liegt flußaufwärts von B

Nicht transitiv sind Relationen, wenn die Beziehung zum
Ursprungselement verlorengeht:

  A und B sind verwandt
    (Eltern sind mit ihrem Kind verwandt, aber nicht miteinander)
  A liegt nahe bei B 
    (das Doppelte einer kurzen Entfernung ist nicht mehr kurz)

d) Reflexive Relationen sind solche, bei denen Selbstbezug nicht nur
möglich, sondern allgegenwärtig ist:

  A ist nicht größer als B
  A und B haben dieselbe Hausnummer
  A trainiert mit B

Nicht reflexiv sind Relationen, wenn es mindestens ein Gegenbeispiel
gibt:

  A liebt B 
    (es gibt gänzlich gefühlskalte Gesellen)
  A und B haben dasselbe Handicap 
    (nicht alle Personen spielen überhaupt Golf)


5. 

older(lux, mary).
older(mary, cecilia).
older(cecilia, therese).
older(therese, bonnie).

older(A,C) :- older(A,B), older(B,C).

Nein, die gänzlich unterspezifizierte Anfrage liefert nur 7 der 10
möglichen `ältere Schwester'-Paare. Bei Umstellung des Regelkörpers
werden sogar nur vier Paare gefunden. Je nachdem, wieviele Schwestern
dargestellt sind, wird also nur ein kleiner Teil der tatsächlichen
Wahrheit ausgegeben, bevor erstmals eine zyklische Beweisführung
versucht wird. Das liegt daran, daß die Struktur des Lösungsraumes mit
der Zahl der Schwestern beliebig kompliziert werden kann, aber Prolog
nur die einfache Tiefensuche ohne Längenbegrenzung beherrscht. 

Man kann die Suche nur dadurch dazu zwingen, zuerst die kürzeren
Ableitungen aufzubauen, indem man eine Prüfung einbaut, welche
Teilziele in einer Ableitung bereits passiert wurden. Das mittlere
Argument der erweiterten Version speichert diese Ziele und verhindert
so, daß unendlich viel Zeit in einer Ableitung verbracht wird.

older_sister(lux, mary).
older_sister(mary, cecilia).
older_sister(cecilia, therese).
older_sister(therese, bonnie).

older(A,_,B):-older_sister(A,B).
older(A,List,C) :-
        older_sister(A,X),
        not(member(X, List)),
        older(X,[X|List],C).

Dann ist aber ein Hilfsprädikat notwendig, um die vorgegebene
zweistellige Schnittstelle wiederherzustellen.