Implication of three statements

Three fellows accused of stealing CDs make the following statements:

(1) Ed: “Fred did it, and Ted is innocent.”
(2) Fred: “If Ed is guilty, then so is Ted.”
(3) Ted: “I’m innocent, but at least one of the others is guilty.”

If the innocent told the truth and the guilty lied, who is guilty? (Remember that false statements imply anything).

I think Ed and Ted are innocent and Fred is guilty. Is it in contradiction with statement 2.

What do you say?

-

Let us write the following propositions:

$F_g$ means Fred is guilty, and $F_i$ means Fred is innocent, $T_g$ and $T_i$ for Ted and $E_g$ and $E_i$ for Ed.

1. Ed says: $F_g \wedge T_i$
2. Fred says: $E_g \rightarrow T_g$
3. Ted says: $T_i \wedge (F_g \vee E_g)$

We know that the guilty is lying and the innocent tells the truth.

Assume Fred did it, he is guilty and lying. Meaning $E_g \rightarrow T_g$ is false, meaning $E_g$ is true and $T_g$ is false, that is Ed is guilty and Ted is innocent.

In turn it means that Ed is also lying, that is either Fred is innocent or Ted is guilty. If Fred is innocent then he is telling the truth - contradiction.

Therefore we know that Ted is guilty as well, another contradiction because it follows from Fred's lie that Ted is innocent.

Alright, then we have that Fred is definitely not guilty. So either Ed is innocent or Ted is guilty.

Assume that Ed is innocent, this is a right out contradiction, as this implies Fred is guilty. So we have that Ed has to be guilty, which means Ted is also guilty - therefore he is lying. Which means he either guilty or both the other guys are innocent. Since he is guilty we have a good solution:

Fred is innocent, Ted and Ed are guilty.

-
Nice. Can you suggest a book which solves logical puzzles using math. – Vinod Dec 23 '10 at 1:51
@Vinod: I don't know any books about puzzles, sorry. I can only recommend you to study propositional calculus, and the basics behind mathematical thought process. – Asaf Karagila Dec 23 '10 at 7:01

You are right. According to the problem, the guilty lie, so Fred's statement should be false. If the problem is well constructed (and I think this one is) there should be only one consistent assignment of truth values to the atomic sentences.

There is a large body of problems of this nature. One of my favorite authors if Raymond Smullyan. A couple of his books lead you through the logic of Goedel's incompleteness proof.

-
You are not correct. See my answer for further proof. – Asaf Karagila Dec 22 '10 at 16:39
Right you are. I misread it. – Ross Millikan Dec 22 '10 at 16:43

The approach that I like best for puzzles like this, is to translate it to logic, and then let the shape of the formulas guide the solution.

Some puzzles of this type require more sophisticated formalizations (see for example this and that answer of mine here on math.SE), but for this puzzle it suffices to let $\;E\;$ stand for both "Ed is innocent" and "Ed tells the truth", and similarly $\;F\;$ and $\;T\;$.

With this, Ed's statement can be translated to \begin{align} \tag{0} E & \;\equiv\; \lnot F \land T \\ \end{align} In words: "Ed tells the truth if and only if Fred is guilty and Ted is innocent." Similarly, we have \begin{align} \tag{1} F & \;\equiv\; (\lnot E \Rightarrow \lnot T) \\ \tag{2} T & \;\equiv\; T \land (\lnot E \lor \lnot F) \\ \end{align} And we now need to determine $\;E,F,T\;$.

The shape of these formulas suggests that $(0)$ and $(1)$ can be substituted in the other equations to reduce the number of variables.

So let's start with substituting $(0)$ in $(1)$, after an initial simplification: \begin{align} & (1) \\ \equiv & \qquad \text{"write $\;\phi \Rightarrow \psi\;$ as $\;\lnot \phi \lor \psi\;$, and simplify"} \\ & F \;\equiv\; E \lor \lnot T \\ \equiv & \qquad \text{"substitute for $\;E\;$ using $(0)$"} \\ & F \;\equiv\; (\lnot F \land T) \lor \lnot T \\ \equiv & \qquad \text{"use negation of $\;\lnot T\;$ on other side of $\;\lor\;$"} \\ & F \;\equiv\; (\lnot F \land \text{true}) \lor \lnot T \\ \equiv & \qquad \text{"simplify"} \\ & F \;\equiv\; \lnot F \lor \lnot T \\ \equiv & \qquad \text{"simplify -- see below"} \\ & F \land \lnot T \tag{1'} \\ \end{align} (For a proof of the last step, see another answer of mine.)

So we already know that $\;F\;$ is true and $\;T\;$ is false, and now we can substitute this in $(0)$ to determine $\;E\;$: \begin{align} & E \\ \equiv & \qquad \text{"$(0)$"} \\ & \lnot F \land T \\ \equiv & \qquad \text{"left part of $\text{(1')}$; right part of $\text{(1')}$; simplify"} \\ & \text{false} \\ \end{align}

So we've determined that Fred is innocent and both Ted and Ed are guilty, and we did not need to use Ted's statement $(2)$.

-