What is the name of the logical puzzle, where one always lies and another always tells the truth?
So i was solving exercises in propositional logic lately and stumbled upon a puzzle, that goes like this:
Each inhabitant of a remote village always tells the truth or always lies. A villager will only give a "Yes" or a "No" response to a question a tourist asks. Suppose you are a tourist visiting this area and come to a fork in the road. One branch leads to the ruins you want to visit; the other branch leads deep into the jungle. A villager is standing at the fork in the road. What one question can you ask the villager to determine which branch to take?
I intuitively guessed the answer is "If I asked you this path leads to the ruins, would you say yes?". So my questions are:
- What is the name and/or source of this logical riddle?
- How can i corroborate my answer with mathematical rigor?
The specific problem is shown in My Best Mathematical and Logic Puzzles, by Martin Gardner. It was in his Scientific American column long ago. The solution is on page 40 with a reference in 1957. The problem itself is the fourth one and is on the page 2. The full definition of the problem is, as published on This Side of the Pond:
The Fork in the Road
Here’s a recent twist on an old type of logic puzzle. A logician vacationing in the South Seas finds himself on an island inhabited by the two proverbial tribes of liars and truth-tellers. Members of one tribe always tell the truth; members of the other always lie. He comes to a fork in a road and has to ask a native bystander which branch he should take to reach a village. He has no way of telling whether the native is a truth-teller or liar. The logician thinks a moment and then asks one question only. From the reply, he knows which road to take. What question does he ask?
Added: the point is that you get only one bit of information. You need that bit to tell you which road leads to the village, so you can't learn whether the native tells the truth or lies. The key to many of these puzzles is finding a way to get the information you need without getting anything more. In this case (and in many truth-teller/liar puzzles) the secret is arranging two negations so you get the answer you need.
Knights and Knaves?
How: read about it.
Define the following propositions:
$Liar$ = villager is a liar
$Ruins$ = tourist points to road to ruins
$Yes$ = answer is yes to direct question (Is this the road to the ruins?)
$Yes'$ = answer is yes indirect question (If I asked you if this was the road to the ruins, would you say yes?)
Use a truth table or natural deduction to prove:
$(Liar\rightarrow (Ruins\leftrightarrow \neg Yes))$
$\land (\neg Liar\rightarrow (Ruins\leftrightarrow Yes))$
$\land (Liar \rightarrow (Yes' \leftrightarrow \neg Yes))$
$\land (\neg Liar \rightarrow (Yes' \leftrightarrow Yes))$
$\rightarrow (Ruins \leftrightarrow Yes')$
Try truth table generator at:
http://www.wolframalpha.com/input/?i=truth+table+%28~a+%3D%3E%28b+%3C%3D%3E+c%29%29%26%28a+%3D%3E%28b%3C%3D%3E~c%29%29%26%28~a+%3D%3E%28d%3C%3D%3Ec%29%29%26%28a+%3D%3E%28d%3C%3D%3E~c%29%29%3D%3E%28b%3C%3D%3Ed%29
See my formal proof at:
http://www.dcproof.com/sindikat.htm
$ \newcommand{\cansay}[2]{#1\text{ can say }\unicode{0x2018}#2\unicode{0x2019}} \newcommand{\says}[2]{#1\text{ says }\unicode{0x2018}#2\unicode{0x2019}} $Here is a way to construct a solution to this puzzle, and many like it.
We want to know whether some specific $\;P\;$ (e.g., "Does this path lead to the ruins?") is true, from the answer $\;a\;$ ($\;\text{true}\;$ for yes, $\;\text{false}\;$ for no) to a question $\;q\;$.
Formally, for some specific villager $\;x\;$, we are asked to find a $\;q\;$ that makes $$ (0) \;\;\; \says x {q \equiv a} \;\Rightarrow\; (P \equiv a) $$ true for all $\;a\;$. And we are given that \begin{align} (1) \;\;\; & \says x P \;\Rightarrow\; \cansay x P \\ (2) \;\;\; & \cansay x P \;\equiv\; T(x) \equiv P \\ \end{align} where $\;T(x)\;$ means that $\;x\;$ is a truth-teller.
(Note that in $(2)$ I use the fact that $\;\equiv\;$ is associative, so that I can leave out the parentheses.)
With the above, we can calculate \begin{align} & \says x {q \equiv a} \;\Rightarrow\; (P \equiv a) \;\;\;\;\;\text{-- $(0)$} \\ \Leftarrow & \;\;\;\;\;\text{"by $(1)$ -- the only thing we know about $\;\says{\cdot}{\ldots}\;$"} \\ & \cansay x {q \equiv a} \;\Rightarrow\; (P \equiv a) \\ = & \;\;\;\;\;\text{"by $(2)$ -- the only other thing we know about $\;\cansay{\cdot}{\ldots}\;$"} \\ & (T(x) \equiv q \equiv a) \;\Rightarrow\; (P \equiv a) \\ \Leftarrow & \;\;\;\;\;\text{"weaken -- the only way forward, as far as I can see"} \\ & T(x) \equiv q \equiv a \equiv P \equiv a \\ = & \;\;\;\;\;\text{"reorder using symmetry of $\;\equiv\;$; simplify"} \\ & q \;\equiv\; T(x) \equiv P \\ = & \;\;\;\;\;\text{"by $(2)$ -- to turn $\;q\;$ in to a real question"} \\ & q \;\equiv\; \cansay x P \\ \end{align}
So we ask the villager, "Can you say that this path leads to the ruins?" An answer of "yes" means it does lead there, an answer of "no" means it doesn't.