Solved!!!

Here is a logic puzzle from Discrete Mathematics and Its Application by Kenneth H Rosen. Its very easy, and can be solved straight away by reasoning but the reason for which i am mentioning it here is that for the first time in life I could figure out the formal way of writing it in the language of propositional logic and solving it on that basis. :-)

Here it goes:

"An island has 2 kinds of inhabitants, knights, who always tell the truth, and their opposites, knaves, who always lie. You encounter 2 people A and B. What are A and B if A says "B is a knight" and B says "The two of us are opposite types"?"

Solution:-

p: "A is a knight"

q: "B is a knight"

Here 'p' and 'q' are propositional statements that can have true and false values.

now we have following four propositional statements from the above puzzle:

p --> q           ( "if p then q" ie. if A is a Knight then B is a Knight as A had specified the same and he tells

                           the truth being a Knight.)

q --> !p          ( "if q then !p" ie. if B is a Knight then A is a Knave as B says they are of opposite types and

                           tells the truth being a Knight)

!p --> !q         ( "if !p then !q" ie. if A is a Knave then B is a Knave as A was lying about B)

!q--> !p          ( "if !q then !p" ie. if B is a Knave then A is also a Knave as B was lying that they are of

                          opposite types)

Now with these if we make a truth table for each:

p	q	!p	!q	p-->q	q-->!p	!p-->!q	!q-->!p
T	T	F	F	T	F	T	T
T	F	F	T	F	T	T	F
F	T	T	F	T	T	F	T
F	F	T	T	T	T	T	T

This is the truth table.

Now as we can see except for the last case we dont have any other case in which all the 4 conditions can be True simultaneously hence, without much ado I can declare that

p is False and q is False to make all 4 conditions hold true simultaneously.

That is, A is a Knave and B is a Knave as well :-)