In: Computer Science
You come across three people. P says, “If Q is lying, then so is R,” Q says, “If R is lying, then so is P,” and R says, “If P is lying, then so is Q.” Who if anyone is telling the truth?
Consider the following cases:
1. All of them are lying. Consider P's statement, which can be
restated as "either R is lying or Q is tellling the truth". If P is
lying, then the negation of the statement must hold, which by the
Demorgan law, is "R is telling the truth and Q is lying". But it
was assumed that R is lying, which is a contradiction. Hence this
case is not possible.
2. Two of them are lying. Let that be P and Q for now. Then R is
telling the truth. Similar to above, the negation of Q's statement
is "P is telling the truth and R is lying". But R is telling the
truth, hence this is a contradiction. Similar analysis works when P
and R, or Q and R are lying. Hence this case is not possible.
3. One of them is lying. Let that be P for now. Then this means Q
and R are telling the truth. But as R says "If P is lying, then so
is Q", and R is telling the truth, this implies Q is lying as well.
But this is a contradiction. Similar analysis works for when the
person lying is Q or R. Hence this case is not possible.
4. All of them are telling the truth. This case is possible, as it
doesn't contradict anyone's statement.
This means the only case possible is that everyone is telling the truth. Hence the answer is that everyone is telling the truth.
Comment in case of any doubts.