Rycerze i łotrzy

W wyśmienitej książce “Jaki jest tytuł tej książki?” Raymonda M. Smullyana zamieszczone są zagadki o rycerzach i łotrach.

Każdy rycerz (ang. knight) zawsze mówi prawdę a każdy łotr (ang. knave) zawsze kłamie.

Możemy zapisać to następującymi dwiema klauzulami prologowymi:

said(knight, X) :- true(X).
said(knave, X) :- false(X).

Operator :- wyraża implikację z konkluzją po lewej stronie i przesłanką po prawej.

Pierwsza klauzula stwierdza, że jeśli zdanie X jest prawdziwe, to zdanie X było powiedziane przez rycerza.

Analogicznie, druga klauzula stwierdza, że jeśli zdanie X jest fałszywe, to zdanie X powiedział łotr.

Identyfikatory knight i knave są prologowymi stałymi i rozpoczynają się z małej litery. Identyfikator X jest zmienną i rozpoczyna się wielką literą.

Stała knight oznacza pewnego rycerza a stała knave pewnego łotra.

Zmienna X oznacza dowolne zdanie.

Następujące klauzule prologowe definiują, które zdania są prawdziwe:

true(true).
true(knight(knight)).
true(knave(knave)).
true(said(knight, X)) :- true(X).
true(said(knave, X)) :- false(X).
true(not(X)) :- false(X).
true(and(X, Y)) :- true(X), true(Y).
true(or(X, Y)) :- true(X); true(Y).

Ostatnie dwie klauzule zawierają operatory , (przecinek) dla koniunkcji i ; (średnik) dla alternatywy.

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

• true jest prawdziwym zdaniem.
• Prawdą jest, że knight jest rycerzem.
• Prawdą jest, że knave jest łotrem.
• Jeśli zdanie X jest prawdziwe, to prawdą jest, że zdanie X było powiedziane przez rycerza.
• Jeśli zdanie X jest fałszywe, to prawdą jest, że zdanie X było powiedziane przez łotra.
• Jeśli zdanie X jest fałszywe, to zdanie not(X) jest prawdziwe.
• Jeśli zdanie X jest prawdziwe i zdanie Y jest prawdziwe, to prawdziwe jest zdanie and(X, Y).
• Jeśli zdanie X jest prawdziwe lub zdanie Y jest prawdziwe, to prawdziwe jest zdanie or(X, Y).
  

Następujące klauzule prologowe definiują warunki dla fałszywych zdań:

false(false).
false(knight(knave)).
false(knave(knight)).
false(said(knight, X)) :- false(X).
false(said(knave, X)) :- true(X).
false(not(X)) :- true(X).
false(and(X, Y)) :- false(X); false(Y).
false(or(X, Y)) :- false(X), false(Y).

Powyższe klauzule mają następujące znaczenie:

• false jest zdaniem fałszywym.
• Nie jest prawdą, że knave jest rycerzem.
• Nie jest prawdą, że knight jest łotrem.
• Jeśli zdanie X jest fałszywe, to nie jest prawdą, że zdanie X powiedział rycerz.
• Jeśli zdanie X jest prawdziwe, to nie jest prawdą, że zdanie X powiedział łotr.
• Jeśli zdanie X jest prawdziwe, to zdanie not(X) jest fałszywe.
• Jeśli zdanie X jest fałszywe lub zdanie Y jest fałszywe, to zdanie and(X, Y) jest fałszywe.
• Jeśli zdanie X jest fałszywe i zdanie Y jest fałszywe, to zdanie or(X, Y) jest fałszywe.
  

Aby znaleźć rozwiązanie za pomocą prologowego celu zawierającego predykat said, musimy znaleźć wszystkie odpowiedzi:

• Jeśli zmienna dla pewnej osoby jest równa stałej knight we wszystkich odpowiedziach, to znaczy, że ta osoba jest rycerzem.
• Jeśli zmienna dla pewnej osoby jest równa stałej knave we wszystkich odpowiedziach, to znaczy, że ta osoba jest łotrem.
• Jeśli zmienna dla pewnej osoby jest równa stałej knight w części odpowiedzi i stałej knave w pozostałych odpowiedziach, to znaczy, że nie jest możliwe ustalenie czy ta osoba jest rycerzem albo łotrem.
  

Załóżmy, że B powiedział “A powiedział, że jest łotrem.” Kim są A i B?

Poniższy dialog z systemem Prolog przedstawia wszystkie odpowiedzi:

?- said(B, said(A, knave(A))).
A = knight,
B = knave ? ;
A = knave,
B = knave ? ;
false.

W obu odpowiedziach zmienna B jest równa knave, więc osoba B jest łotrem. W pierwszej odpowiedzi A jest równe knight a w drugiej jest równa knave, więc nie można wywnioskować kim jest osoba A.

Na stronie KnightsAndKnavesPuzzleGenerator znajdziesz generator zagadek przygotowany przez Wolfram.com.


Zagadka 28

W tym zadaniu są tylko dwie osoby, A i B, z których każda jest albo rycerzem, albo łotrem. A wygłasza następujące zdanie: „Co najmniej jeden z nas jest łotrem“.

Kim są A i B?

?- said(A, or(knave(A), knave(B))).

Zagadka 29

Załóżmy, że A mówi: „Jestem łotrem lub B jest rycerzem“.

Kim są A i B?

?- said(A, or(knave(A), knight(B))).

Zagadka 30

Załóżmy, że A mówi: „Jestem łotrem lub dwa plus dwa to pięć“.

Jaki stąd wyciągnąłbyś wniosek?

?- said(A, or(knave(A), false)).

Zagadka 33

Załóżmy, że A mówi: „Jestem łotrem, ale B nie jest łotrem“.

Kim są A i B?

?- said(A, and(knave(A), knight(B))).

Źródła programu: knights_knaves.pl