2
$\begingroup$

I tried to solve the following logic puzzle. It seems that $(A \vee \neg A) \wedge B$ is the answer, but I'm not sure. Can anyone give me an answer?

A certain country is inhabited only by truth-tellers (people who always tell the truth) and liars (people who always lie). Moreover, the inhabitants will respond only to yes or no questions. A tourist comes to a fork in a road where one branch leads to the capital and the other does not. There is no sign indicating which branch to take, but there is a native standing at the fork. What yes or no question should the tourist ask in order to determine which branch to take?

Hint: Let $A$ stand for “You are a truth-teller” and let $B$ stand for “The left-hand branch leads to the capital.” Construct, by means of a suitable truth table, a statement form involving $A$ and $B$ such that the native's answer to the question as to whether this statement form is true will be yes when and only when $B$ is true.

$\endgroup$
  • $\begingroup$ That's a very old and well known puzzle. "If I asked you if the left-hand branch leads to the captital would you answer 'yes'". A truth teller would tell the truth and tell you whether a truth teller would answer 'yes'; a liar would lie and tell you whether a truth teller would answer 'yes'. Either way you will be told whether a truth teller would answer 'yes'. $\endgroup$ – fleablood Oct 29 '15 at 6:06
2
$\begingroup$

You shall find a formula that has the following truth table:

$$\begin{array}{cc|c} A & B & ? \\ \hline T & T & T \\ T & F & F \\ F & T & F \\ F & F & T \\ \end{array}$$

Reason: If the person you ask is actually a truth teller (i.e. $A$ is true), then the desired formula shall have the same truth value as B. If the person you ask is a liar (i.e. $A$ is false), though, the desired formula shall have flipped truth values, because (so to speak) the liar will flip the truth value again.

Now the desired formula is easy to come up with; it's simply $A \leftrightarrow B$.

Explanation: Ask the local "Is the following the case: you're a truth teller iff the left hand branch leads to the capital?" (assuming he will understand "iff" truth-functionally)

First assume he's a truth teller. If the left hand branch leads to the capital, the biconditional is true and he will answer "yes". If the left hand branch does not lead to the capital, the biconditional is false (since the two sentences differ in truth value), and he will answer "no".

Second assume he's a liar. If the left hand branch leads to the capital, the truth values of $A$ and $B$ differ, so the biconditional is false, and because you're asking a liar by assumption, he will answer "yes". If the left hand branch does not lead to the capital, then the biconditional is true and the answer will be "no".

In both cases, the answer is "yes" if the left hand branch leads to the capital, but "no" if it does not $-$ which is exactly the desired result, I take it.

$\endgroup$
  • $\begingroup$ If you ask a liar "Are you not a truth teller", the liar would say "I am a truth teller". So, you can't infer A directly. $\endgroup$ – crocket Oct 29 '15 at 12:38
  • $\begingroup$ The idea was something else; I've added more explanation to my post. $\endgroup$ – user278201 Oct 29 '15 at 18:08
  • $\begingroup$ This is great. I finally understood the logic of your comment. $\endgroup$ – crocket Oct 30 '15 at 5:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.