P1-WS04-MusterLoesung04.txt
Version vom 22. Dezember 2006, 07:46 Uhr von fsrwiki_>1illig (antispam)
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.