Lew i Jednorożec

W rozdziale Alicja w Lesie Zapomnienia, książki „Jaki jest tytuł tej książki?“ Raymonda Smullyana, zamieszczone są zagadki o Lwie i Jednorożcu.

Rozpoczniemy od predykatów definiujących dni tygodnia oraz relacji poprzedzania między dniami:

day(monday).
day(tuesday).
day(wednesday).
day(thursday).
day(friday).
day(saturday).
day(sunday).

next(monday, tuesday).
next(tuesday, wednesday).
next(wednesday, thursday).
next(thursday, friday).
next(friday, saturday).
next(saturday, sunday).
next(sunday, monday).

Użyjemy funktorów after i before do opisania dnia następnego i poprzedniego względem danego dnia.

Dla przykładu term after(sunday) oznacza poniedziałek a term before(saturday) oznacza piątek.

Następujący predykat analizuje term i znajduje odpowiadający mu dzień tygodnia:

resolve_day(D, D) :- var(D), !, day(D).
resolve_day(D, D) :- atom(D), !, day(D).
resolve_day(after(X), D) :- resolve_day(X, D1), next(D1, D).
resolve_day(before(X), D) :- resolve_day(X, D1), next(D, D1).

W powyższych klauzulach zostały użyte następujące predykaty:

• var(Term), który jest spełniony jeśli Term jest zmienną,
• atom(Term), który jest spełniony jeśli Term jest stałą,
• !, który jest zawsze spełniony ale odcina nawrót (poczytaj o odcięciu i negacji).

Lew kłamie w poniedziałki, wtorki i środy. Jednorożec kłamie w czwartki, piątki i soboty. Następujące fakty wyrażają to:

lies(lion, monday).
lies(lion, tuesday).
lies(lion, wednesday).
lies(unicorn, thursday).
lies(unicorn, friday).
lies(unicorn, saturday).

Głównym predykatem jest said(C, D, S), który jest spełniony gdy postać C mogła powiedzieć zdanie S w dniu D:

said(lion, X, Y) :- resolve_day(X, D), lies(lion, D), false(Y).
said(lion, X, Y) :- resolve_day(X, D), \+ lies(lion, D), true(Y).
said(unicorn, X, Y) :- resolve_day(X, D), lies(unicorn, D), false(Y).
said(unicorn, X, Y) :- resolve_day(X, D), \+ lies(unicorn, D), true(Y).

W drugiej i czwartej klauzuli operator \+ został użyty aby wyrazić negację.

Znaczenie powyższych klauzul jest następujące:

• Jeśli D jest dniem kiedy Lew kłamie i zdanie X jest fałszywe, to Lew mógł powiedzieć zdanie X w dniu D.
• Jeśli D jest dniem kiedy Lew nie kłamie i zdanie X jest prawdziwe, to Lew mógł powiedzieć zdanie X w dniu D.
• Jeśli D jest dniem kiedy Jednorożec kłamie i zdanie X jest fałszywe, to Jednorożec mógł powiedzieć zdanie X w dniu D.
• Jeśli D jest dniem kiedy Jednorożec nie kłamie i zdanie X jest prawdziwe, to Jednorożec mógł powiedzieć zdanie X w dniu D.

Poniższe klauzule definiują predykat true(X), który jest spełniony jeśli zdanie X jest prawdziwe:

true(true).
true(lies(X, Y)) :- resolve_day(Y, D), lies(X, D).
true(not(X)) :- false(X).
true(and(X, Y)) :- true(X), true(Y).
true(or(X, Y)) :- true(X); true(Y).

Powyższe klauzule możemy odczytać następująco:

• true jest zdaniem prawdziwym.
• Jeśli postać X kłamie w dniu Y, to lies(X, Y) jest zdaniem prawdziwym.
• Jeśli X jest zdaniem fałszywym, to not(X) jest zdaniem prawdziwym.
• Jeśli zdania X i Y są zdaniami prawdziwymi, to and(X, Y) jest zdaniem prawdziwym.
• Jeśli zdanie X lub zdanie Y jest prawdziwe, to or(X, Y) jest zdaniem prawdziwym.

Następujące klauzule definiują predykat false(X), który jest spełniony jeśli zdanie X jest fałszywe:

false(false).
false(lies(lion, X)) :- resolve_day(X, D), \+ lies(lion, D).
false(lies(unicorn, X)) :- resolve_day(X, D), \+ lies(unicorn, D).
false(not(X)) :- true(X).
false(and(X, Y)) :- false(X); false(Y).
false(or(X, Y)) :- false(X), false(Y).

i mogą być odczytane następująco:

• false jest zdaniem fałszywym.
• Jeśli X jest dniem, w którym Lew nie kłamie, to zdanie lies(lion, X) jest fałszywe.
• Jeśli X jest dniem, w którym Jednorożec nie kłamie, to zdanie lies(unicorn, X) jest fałszywe.
• Jeśli X jest zdaniem prawdziwym, to not(X) jest zdaniem fałszywym.
• Jeśli zdanie X lub zdanie Y jest fałszywe, to and(X, Y) jest zdaniem fałszywym.
• Jeśli zdania X i Y są fałszywe, to or(X, Y) jest zdaniem fałszywym.

Poniższy dialog pokazuje jak wywnioskować, w którym dniu Lew i Jednorożec jednocześnie nie kłamią:

?- said(lion, Day, true), said(unicorn, Day, true).
Day = sunday ;
false.

Odpowiedź sunday jest jedynym rozwiązaniem.

Zagadka 47

Pewnego dnia Alicja spotkała Lwa i Jednorożca odpoczywających pod drzewem. Wygłosili oni następujące zdania:
Lew: Wczoraj był jeden z dni, w które kłamię.
Jednorożec: Wczoraj był jeden z dni, w które ja również kłamię.
Z tych dwóch zdań Alicja (która była bardzo bystrą dziewczynką) potrafiła wydedukować, jaki był dzień tygodnia.

Jaki to dzień?

?- said(lion, Day, lies(lion, before(Day))), said(unicorn, Day, lies(unicorn, before(Day))).

Zagadka 48

Kiedy indziej Alicja spotkała samego Lwa. Wygłosił on dwa następujące zdania:

• Wczoraj kłamałem.
• Będę znów kłamał w dwa dni po jutrze.

Jaki to był dzień tygodnia?

?- said(lion, Day, lies(lion, before(Day))), said(lion, Day, lies(lion, after(after(after(Day))))).

Zagadka 49

W jakie dni tygodnia Lew może wygłosić następujące zdania:

• Wczoraj kłamałem.
• Jutro znów będę kłamał.

?- said(lion, Day, lies(lion, before(Day))), said(lion, Day, lies(lion, after(Day))).

Zagadka 50

W jaki dzień tygodnia Lew może wygłosić następujące zdanie: „Wczoraj kłamałem i jutro znów będę kłamał“. Uwaga! Rozwiązanie tego zadania nie jest takie jak rozwiązanie poprzedniego!

?- said(lion, Day, and(lies(lion, before(Day)), lies(lion, after(Day)))).

Źródła programu: lion_unicorn.pl