# Which sentence among the three sentences is the lie?

1. The second statement is the lie or the third statement is the lie.
2. This statement is a truth, or the last statement and the second statement cannot both be truths.
3. The first statement is the lie and the second statement is a truth, or this statement is the lie.

There can only be one lie, and the rest of the sentences have to be true. My guess is #3. based on the truth table TTL, TLT, LTT, where 3 contradicts #2. But, I wonder if I have missed anything?

-
It seems to me that #1 can be the lie. It claims that 2 or 3 is the lie, which is false. 2 claims that 2 is true or (doesnt matter), which is true; 3 claims that 1 is the lie and 2 is true, or (doesn't matter). –  MJD May 4 '12 at 19:38
But the second statement cannot be the lie, as then the third would also be a lie. –  TMM May 4 '12 at 19:40
If the third statement is a lie, the second part of the "or" of the third statement is true - and "or" is true if either part is true, so the third statement is true - contradiction. So if there is a consistent solution the third statement must be true. –  Mark Bennet May 4 '12 at 19:45
Note that it is not necessary to know the content of the first two statements, not that exactly one of the sentences is a lie. Everything follows from the third statement. –  Marnix Klooster Mar 23 at 11:16

Let $p,q$, and $r$ stand respectively for '(1) is true', '(2) is true', and '(3) is true'. Then the three statements become (1) $\lnot q\lor\lnot r$, (2) $q\lor\lnot(q\land r)$, and (3) $(\lnot p\land q)\lor\lnot r$. Now you can make the full truth table, as shown below:

$$\begin{array}{c} &&&p\equiv&q\equiv&r\equiv\\ p&q&r&\lnot q\lor\lnot r&q\lor\lnot(q\land r)&(\lnot p\land q)\lor\lnot r\\ \hline \text{T}&\text{T}&\text{F}&\color{blue}{\underline{\color{red}{\textbf{F}}}}&\text{T}&\color{blue}{\underline{\color{red}{\textbf{T}}}}\\ \text{T}&\text{F}&\text{T}&\text{T}&\text{F}&\color{blue}{\underline{\color{red}{\textbf{F}}}}\\ \text{F}&\text{T}&\text{T}&\text{F}&\text{T}&\text{T} \end{array}$$

The red entries show the places where the truth values of the statements are inconsistent. As you can see, only the third assignment of truth values is free of inconsistency, so (1) must be the lie.

In fact $q\lor\lnot(q\land r)$ is logically equivalent to $q\lor(\lnot q\lor\lnot r)$ by De Morgan's laws, and this is a tautology, as is easily seen by rewriting it as $(q\lor\lnot q)\lor r$. Thus, (2) must be a true statement. If (1) were also true, (3) would be the lie, but that would imply that (2) was also a lie, which is impossible.

-
The red is very hard to see, can you make it in another color, or make it boldface as well? –  Asaf Karagila May 4 '12 at 20:17
@Asaf: On my screen red is one of the most visible colors, but let me see what I can do to add another distinction. –  Brian M. Scott May 4 '12 at 20:30
@Asaf: head meets desk –  Brian M. Scott May 4 '12 at 20:34
@TMM: I didn't bother to check the five cases that are ruled out by the statement of the problem: I'm a great believer in constructive laziness! –  Brian M. Scott May 4 '12 at 21:04
Brian, shouldn't p (not Q or not R) in the third assignment result in False? (not T or not T) = (F or F) = F? –  Salman Paracha May 7 '12 at 21:25

Let the three statements be $A$, $B$ and $C$ respectively. Then we can summarize the statements as:

\begin{align} (A &\Leftrightarrow [\neg B \vee \neg C]) \\ \wedge \ (B &\Leftrightarrow [B \vee \neg (B \wedge C)]) \\ \wedge \ (C &\Leftrightarrow [(\neg A \wedge B) \vee \neg C]). \end{align}

Writing out all implications, we get

\begin{align} (A &\Rightarrow [\neg B \vee \neg C]) \\ \wedge \ (A &\Leftarrow [\neg B \vee \neg C]) \\ \wedge \ (B &\Rightarrow [B \vee \neg (B \wedge C)]) \\ \wedge \ (B &\Leftarrow [B \vee \neg (B \wedge C)]) \\ \wedge \ (C &\Rightarrow [(\neg A \wedge B) \vee \neg C]) \\ \wedge \ (C &\Leftarrow [(\neg A \wedge B) \vee \neg C]). \end{align}

Reducing $P \Rightarrow Q$ to $\neg P \vee Q$, we get

\begin{align} &(\neg A \vee [\neg B \vee \neg C]) \\ \wedge& (A \vee \neg [\neg B \vee \neg C]) \\ \wedge& (\neg B \vee [B \vee \neg (B \wedge C)]) \\ \wedge& (B \vee \neg [B \vee \neg (B \wedge C)]) \\ \wedge& (\neg C \vee [(\neg A \wedge B) \vee \neg C]) \\ \wedge& (C \vee \neg [(\neg A \wedge B) \vee \neg C]). \end{align}

Reducing each term individually, we get

\begin{align} &(\neg A \vee \neg B \vee \neg C) \\ \wedge& (A \vee (B \wedge C)) \\ \wedge&\text{true} \\ \wedge& B \\ \wedge& (\neg C \vee (\neg A \wedge B)) \\ \wedge& C. \end{align}

Or, in short,

$$B \wedge C \wedge (A \vee (B \wedge C)) \wedge (\neg A \vee \neg B \vee \neg C) \wedge (\neg C \vee (\neg A \wedge B)).$$

This statement can only hold if $B$ and $C$ both hold, in which case the third, fourth and fifth term reduce to $\text{true}$, $\neg A$ and $\neg A$. So the statements are consistent if and only if

$$\color{blue}{\neg A \wedge B \wedge C}.$$

So even if multiple statements could be a lie, the only consistent scenario is that statement $1$ is a lie, and $2$ and $3$ are truths.

-

#3 does not contradict #2, because "This statement is a truth" in #2 and "The first statement is the lie and the second statement is a truth" in #3 can both hold. So #1 must be the only one that is a lie.

-

Letting $S1,S2,S3$ stand for the three statements, we are given that \begin{align} \tag{0} \text{exactly one of }S1, S2, S3\text{ is false} \\ \end{align} and \begin{align} \tag{1} S1 & \;\equiv\; \lnot S2 \lor \lnot S3 \\ \tag{2} S2 & \;\equiv\; S2 \lor \lnot (S3 \land S2) \\ \tag{3} S3 & \;\equiv\; (\lnot S1 \land S2) \lor \lnot S3 \\ \end{align}

Looking at the shape of formulae $(2)$ and $(3)$ suggests that they can be simplified. For example, $(3)$ has the shape $\;P \;\equiv\; Q \lor \lnot P\;$, which can be simplified as follows: \begin{align} & P \;\equiv\; Q \lor \lnot P \\ \equiv & \qquad \text{"write $\;\psi \;\equiv\; \phi\;$ as $\;\lnot(\lnot \psi \;\equiv\; \phi)\;$} \\ & \qquad \phantom{\text{"}}\text{-- this gives $\;\lnot P\;$ on both sides"} \\ & \lnot(\lnot P \;\equiv\; Q \lor \lnot P) \\ \equiv & \qquad \text{"one way to rewrite $\;\Rightarrow\;$"} \\ & \lnot(Q \Rightarrow \lnot P) \\ \equiv & \qquad \text{"another way to rewrite $\;\Rightarrow\;$"} \\ & \lnot(\lnot Q \lor \lnot P) \\ \equiv & \qquad \text{"DeMorgan"} \\ & P \land Q \\ \end{align} Now we can use this to simplify $(3)$: \begin{align} \tag{3} & S3 \;\equiv\; (\lnot S1 \land S2) \lor \lnot S3 \\ \equiv & \qquad \text{"using the above simplification,} \\ & \qquad \phantom{\text{"}}\text{with $\;P := S3\;$ and $\;Q := \lnot S1 \land S2\;$"} \\ \tag{3'} & S3 \land \lnot S1 \land S2 \\ \end{align}

Interpreting $\text{(3')}$, this means that $S1$ is false and $S2$ and $S3$ are true: the first statement is the lie.

Note how (to my surprise!) we did not need to use $(0)$, $(1)$, or $(2)$ at all: these are all implied by $(3)$.

-