I'm currently reading Raymond Smullyan's To Mock A Mockingbird, a book recommended by my thesis supervisor/NLP teacher. Anyway, in chapter 5, Smullyan discussed some knight-and-knave puzzles, which reminds me of the good old Discrete Math days. Here it is:
In the Island of Knights and Knaves, every inhabitant is either a knight or a knave. Knights make only true statements and knaves only false ones.
- Is it possible for any inhabitant of this island to claim that he is a knave?
- Is it possible for an inhabitant of the island to claim that he and his brother are both knaves?
- Suppose an inhabitant A says about himself and his brother B: "At least one of us is a knave." What type is A and what type is B?
- Suppose A instead says: "Exactly one of us is a knave." What can be deduced about A and what can be deduced about B?
- Suppose A instead says: "My brother and I are the same type; we are either both knights or both knaves." What could then be deduced about A and B?
Prolog solution
It's been a while since I last code in Prolog, but here's a quick-and-dirty solution that I came up with: truth(not(X),true) :- truth(X,false).
truth(and(X,Y),true) :- truth(X,true), truth(Y,true).
truth(or(X,Y),true) :- truth(X,true) ; truth(Y,true).
truth(imp(X,Y),true) :- truth(X,false) ; truth(Y,true).
truth(exor(X,Y),true) :- (truth(X,true),truth(Y,false)) ; (truth(X,false),truth(Y,true)).
truth(biimp(X,Y),true) :- truth(exor(X,Y),false).
truth(not(X),false) :- truth(X,true).
truth(and(X,Y),false) :- truth(X,false) ; truth(Y,false).
truth(or(X,Y),false) :- truth(X,false) , truth(Y,false).
truth(imp(X,Y),false) :- truth(X,true) , truth(Y,false).
truth(exor(X,Y),false) :- (truth(X,true),truth(Y,true)) ; (truth(X,false),truth(Y,false)).
truth(biimp(X,Y),false) :- truth(exor(X,Y),true).
truth(is_a(knight,knight),true).
truth(is_a(knave,knave),true).
truth(is_a(knight,knave),false).
truth(is_a(knave,knight),false).
truth(say(knight,Statement),true) :- truth(Statement,true).
truth(say(knave,Statement),true) :- truth(Statement,false).
truth(say(knight,Statement),false) :- truth(Statement,false).
truth(say(knave,Statement),false) :- truth(Statement,true).
Answer 1: no
?- truth(say(A,is_a(knave,A)),TruthValue).
A = knight,
TruthValue = false ;
A = knave,
TruthValue = false ;
Answer 2: yes
?- truth(say(A,and(is_a(knave,A),is_a(knave,B))),true).
A = knave,
B = knight .
Answer 3: A is a knight and B is a knave
?- truth(say(A,or(is_a(knave,A),is_a(knave,B))),true).
A = knight,
B = knave .
Answer 4: B is a knave, A cannot be determined.
?- truth(say(A,exor(is_a(knave,A),is_a(knave,B))),true).
A = knight,
B = knave ;
A = B, B = knave ;
Answer 5: B is a knight, A cannot be determined.
?- truth(say(A,biimp(is_a(knave,A),is_a(knave,B))),true).
A = B, B = knight ;
A = knave,
B = knight ;
The Search for Arthur York
Inspector Craig: What do you know about Arthur York?
Defendant: Arthur York once claimed that I was a knave.
Inspector Craig: Are you by any chance Arthur York?
Defendant: Yes.
Is the defendant Arthur York?
Let's assume that the defendant is Arthur York, that is truth(say(Defendant,is_a(Defendant,Arthur_York)),true).
?- truth(say(Defendant,is_a(Defendant,Arthur_York)),true), truth(say(Defendant,say(Arthur_York,is_a(knave,Defendant))),Truth).
Defendant = Arthur_York, Arthur_York = knight,
Truth = false ;
Defendant = knave,
Arthur_York = knight,
Truth = false ;
Under this assumption, evaluation of the first claim leads to contradiction. Thus the defendant cannot be Arthur York.
