Discrete Math Exercise: Solving Logic Puzzle in Computer Science

[Casual]

The Subject is Discrete Mathematics as part of a Computer Science major. The exercise is as follows:

Erica, Stanley and Robert were all witnesses in a car crash. Their statements are contradictory to one another, and all of them claimed that someone else lied. Erica claimed that Stanley lied, Stanley claimed that Robert lied, while Robert claimed that both of them lied. After thinking for a little bit, without any further questions the judged figured out who was telling the truth. Who was telling the truth?
I need to provide a step by step proof based on logic equivalences and deductions made based on the rules of logic.

Here's my take on the exercise:

p:Erica is telling the truth.
q:Stanley is telling the truth.
s:Robert is telling the truth.

Based on this representation we have:

p -> ¬q ( if Erica is telling the truth, then Stanley is not telling the truth )
q -> ¬s ( if Stanley is telling the truth, then Robert is not telling the truth )
s -> ¬p ^ ¬q ( if Robert is telling the truth, then both Erica and Stanley are not telling the truth)

Now we will examine the possibilities. If Erica is telling the truth we have:
1. p
2. p -> ¬q
3. ¬(¬s) - Since Stanley is lying, the opposite of what Stanley said is correct
4. s -> ¬p ^ ¬q
These 4 are conditions.
5. s - double negation on 3.
6. ¬p ^ ¬q - Modus Ponens of 4 and 5
7. ¬p - simplification of 6
8. ¬p ^ p - addition of 1 and 7.
Because of this contradiction it is clear that Erica is not telling the truth.

Similarly we will examine if Stanley is telling the truth.
1.q
2.p -> ¬q
3.q -> ¬s
4. ¬(¬p ^ ¬q) - Since Robert is lying, the opposite of what Robert said is true.
These 3 are conditions.
5. ¬p Modus Ponens of 1 and 2
6. ¬s Modus Ponens of 1 and 3
No contradiction, meaning Stanley was in fact telling the truth.

Lastly, let's examine the case if Robert was telling the truth.
1.s
2.¬(p->¬q) - since Erica is lying, the opposite is true
3.¬(q->¬s) - since Stanley is lying, the opposite is true
4. s -> ¬p ^ ¬q
These 4 are conditions.
5. ¬p ^ ¬q - Modus Ponens of 1 and 4.
6. ¬(¬p v ¬q) substitution of the implication in 2
7. p ^ q De Morgan's law on 6.
8. p simplification of 7
9. ¬p simplification of 5
10. p ^ ¬p addition of 8 and 9
Because of the contradiction it is clear that Robert also couldn't have been telling the truth.Can my logic be justified? And is it possible to divide the exercise like so? If not, can you please show me the path to righteousness?(that might've been a bit too cheesy xD ) Thanks!

 

[Ackbach]

The Subject is Discrete Mathematics as part of a Computer Science major. The exercise is as follows:

Erica, Stanley and Robert were all witnesses in a car crash. Their statements are contradictory to one another, and all of them claimed that someone else lied. Erica claimed that Stanley lied, Stanley claimed that Robert lied, while Robert claimed that both of them lied. After thinking for a little bit, without any further questions the judged figured out who was telling the truth. Who was telling the truth?
I need to provide a step by step proof based on logic equivalences and deductions made based on the rules of logic.

Here's my take on the exercise:

p:Erica is telling the truth.
q:Stanley is telling the truth.
s:Robert is telling the truth.

I would highly recommend a different labeling scheme thus:

E: Erica is telling the truth.
S: Stanley is telling the truth.
R: Robert is telling the truth.

Based on this representation we have:
p ->

¬q ( if Erica is telling the truth, then Stanley is not telling the truth )
q -> ¬s ( if Stanley is telling the truth, then Robert is not telling the truth )
s -> ¬p ^ ¬q ( if Robert is telling the truth, then both Erica and Stanley are not telling the truth)

I would agree with this scheme, but you need parentheses to make it clearer here:

$s\implies(\neg p\land\neg q).$

Now we will examine the possibilities. If Erica is telling the truth we have:

1. p
2. p -> ¬q
3. ¬(¬s) - Since Stanley is lying, the opposite of what Stanley said is correct

This is incorrect reasoning. The implication $A\implies B$ does not give you $\neg A\implies \neg B$, which would be the converse. You do have this (using my labeling scheme):
\begin{align*}
1.\;&E\implies\neg S\\
2.\;&S\implies \neg R\\
3.\;&R\implies(\neg E\land\neg S).
\end{align*}
Then if you start with the assumption of $E$, you have:
\begin{align*}
1.\;&E\\
2.\;&E\implies\neg S\\
3.\;&\neg S\\
4.\;&E\lor S\\
5.\;&\neg(\neg E\land\neg S)\quad\text{Can you see how to get this?}\\
6.\;&\neg R\\
7.\;&S\implies\neg R.\quad\text{Can you see how to get this?}
\end{align*}
I don't see a contradiction here.

As usual, if Evgeny.Makarov could look this over, I'd appreciate that. I dabble. He's a professional.

 

[Casual]

What if I added [FONT=MathJax_Main]¬S -> R as a condition and then got R out of here?
Without the assumption that if they're lying it would mean that the negation of what there implying is true, I find this exercise impossible to solve.
My verbal approach to the exercise would go as follows:
If Erica is telling the truth it means that Stanley is lying. If Stanley is lying then Robert is telling the truth. If Robert is in fact telling the truth, it means that both Erica and Stanley are lying which contradicts with the statement that Erica is telling the truth.
If Stanley is telling the truth it means that Robert is lying. If Robert is lying, then at least one of the two is telling the truth. Therefore, Erica could be lying and Stanley be the one who was telling the truth, which is not contradictory.
If Robert is telling the truth, then Erica and Stanley are both lying. If Erica is lying, it would suggest that Stanley was telling the truth and that would mean that Robert was lying which is contradictory to the statement that Robert was telling the truth.
This leaves us with only one possibility. That Erica and Robert are lying and Stanley is telling the truth. Only in this case there are no contradictions.[/FONT]

 

[Casual]

Managed to solve it, by taking the three conditions for telling the truth, and adding three conditions for when they're lying. Worked like a charm. Thanks!

 

[Evgeny.Makarov]

I agree with what was said in this thread. In particular, statements should probably be interpreted as biconditionals and not as implications:

1. \(E\leftrightarrow\neg S\)
2. \(S\leftrightarrow\neg R\)
3. \(R\leftrightarrow\neg E\land\neg S\)

Then there is a unique solution E = R = F and S = T.

Of course, in reality one can't interpret the given claims:

Erica claimed that Stanley lied, Stanley claimed that Robert lied, while Robert claimed that both of them lied.

using the formulas 1-3 above. I can't imagine a situation where the witnesses said the following.

Erica: The statement that Stanley is about to make is false.
Stanley: The statement that Robert is about to make is false.
Robert: The statements that Erica and Stanley have just made are false.

Rather, they were talking about the statements that they made previously. If we denote those statements by E', S' and R', then the formulas should be

1. \(E\leftrightarrow\neg S'\)
2. \(S\leftrightarrow\neg R'\)
3. \(R\leftrightarrow\neg E'\land\neg S'\)

This system has more solutions; for example, all of E, S and R can be true and E', S' and R' can be false.