Category Archives: serious stuff

Knight-Knave Puzzle

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.

  1. Is it possible for any inhabitant of this island to claim that he is a knave?
  2. Is it possible for an inhabitant of the island to claim that he and his brother are both knaves?
  3. 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?
  4. Suppose A instead says: “Exactly one of us is a knave.” What can be deduced about A and what can be deduced about B?
  5. 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.

Advertisements

Plotting Riemann Zeta Function

Reading John Derbyshire’s Prime Obsession and playing around with Python library matplotlib for a course project brought me to plotting Riemann zeta function. The function is defined as follows:

where s is a complex variable, thus s = a + bi. The real part of s, denoted by Re(s), is a; while the imaginary part, denoted by Im(s), is b.

Python library mpmath has implemented this function in zeta and zetazero. Here is an example of the function plot in the complex plane with Re(s) in the range [-10,10] and Im(s) in the range [-5,35]:

 >>> from mpmath import zeta, cplot  
>>> cplot(zeta,[-10,10],[-5,35])
The function zetazero computes the n-th nontrivial zero of the zeta function. The following figure shows 100 first non-trivial zero. As stated in the hypothesis, they have real part 1/2 (note: x-axis is the real part, y-axis is the imaginary part).
Let:
  • ΞΆ(s) = v
  • Re(s) = 1/2
  • Im(s) in the range [0.1,50]
  • Re(v) = x
  • Im(v) = y

I plot the function value on 2D plane in this movie according to the growth of Im(s).

 import matplotlib.pyplot as plt  
from numpy import arange
from mpmath import zeta

X = []
Y = []

for t in arange(0.1,50,0.1):
v = zeta(complex(0.5,t))
X.append(v.real)
Y.append(v.imag)

fig = plt.figure()
ax = fig.add_subplot(111)
ax.plot(X,Y)
ax.set_xlabel("Re(v)")
ax.set_ylabel("Im(v)")
plt.show()
Ok, I hope this post can be useful for someone somewhere. I learn mostly from here and here.