Search code examples
logicdiscrete-mathematics

How double negation in problem from Ken Rosen's Discrete Math exercise "an explorer captured by a group of two cannibals" work?


There is a puzzle in the book Discrete Mathematics and its applications Page 23 - Exercise 16 . Puzzle goes like - "An Explorer captured by a group of two cannibals. There are two type of cannibals-those who always tell the truth and those who always lie. The cannibals will barbecue the explorer unless he can determine whether a particular cannibal always lies or always tells the truth. He is allowed to ask the cannibal exactly one question. Find the question that the explorer can use to determine whether the cannibal always lies or always tells the truth."

I know some solutions like you can ask cannibals "are you a cannibal", "is the colour of sky is blue?". But that is not how logic works right? There is another solution which is perfect. Solution is, you ask cannibal "If I were to ask you if you are a liar, would you answer 'Yes'?" Truther cannibal will answer "No" because he is not a liar. But I don't know what Liar cannibal will answer. Will he also answer "No" because he always lies? And I want to know how double Negation is working here.


Solution

  • Let's break it into parts.
    The liar cannibal will always say the wrong answer. When you ask him "If I were to ask you if you are a liar, would you answer 'Yes'?" he answers the opposite.
    The liar cannibal thinks for himself: "If I was asked if I am a liar, would I answer 'Yes'?" Because he is a liar, if he was asked, he would answer 'No, I am not a liar'. But that not you asked him. You asked "If I were to ask you". So the liar would lie about that too- instead of saying 'No, I am not al liar' he would say "Yes, If I was asked if I am a liar I would answer 'Yes'".

    The double negation is something like this:

    not (if I was asked: not (am I a liar?))

    "am I a liar?" is true so (not (am I a liar?)) is false. Because of that the whole statement is true.

    Hope it was clear :) This is indeed a tricky question.