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 ;

If A is a knight, he wouldn’t lie by saying he is a knave; if A is a knave, he wouldn’t admit that he is.

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.