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.
Best Answer
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.