Asked to show that $(p \land (q \oplus r))$ and $(p \oplus q) \land (p \oplus r)$ are logically equivalent, but truth tables don't match.

Question

Show that $(p \land (q \oplus r))$ and $(p \oplus q) \land (p \oplus r)$ are logically equivalent.

Yet I don't see how they are logically equivalent. I try to use the truth table and they do not match. Am I missing something? or how should I prove they are not logically equivalent except using truth table?

Thanks.

Answer 1

The two expressions are not equivalent. Take $p=0,q=r=1$. They give different values.

Answer 2

Think about it. How could you define equivalence for logical expressions?

A reasonable guess would be $$f(a_1,\dots,a_n) \equiv g(a_1,\dots,a_n) \iff \forall (a_1,\dots,a_n) \ \ f(a_1,\dots,a_n) = g(a_1,\dots,a_n).$$

The condition above is simply stating that the truth tables must match.

Answer 3

Just because one is asked to show something does not mean that one will always be able to do so. One should keep in mind that a question might be in error or it might be posed as a challenge to find what is wrong with it.

If the truth tables do not match, as the OP discovered, then these formulas are not logically equivalent. A counterexample would be any row or valuation for $p$, $q$ and $r$ where the formulas do not have the same truth value.

To get an intuitive feel why these formulas should not be equivalent recall that exclusive or requires that one and only one side of this connective be true, that is, if we have $p \oplus q$ then one of the sides must be true, $p \lor q$, but also only one of the sides must be true, $\neg(p \land q)$.

Consider $p \land (q \oplus r)$. For that to be true both conjuncts must be true. Therefore the left conjunct, $p$, must be true. To make the right conjunct, $q \oplus r$, true one and only one of $q$ and $r$ must be true. Let $q$ be true and $r$ be false.

Now consider, using those valuations, $(p \oplus q) \land (p \oplus r)$. We want this to be true to match the truth value of the other formula. The conjunction requires that both conjuncts be true. In particular, $p \oplus q$ must be true. But this cannot be true if both $p$ and $q$ are both true as the valuations require them to be. Since one of the conjuncts is false that means the conjunction itself is false.

We found a valuation, $p$ and $q$ are true and $r$ is false, where one formula is true and the other formula is false. This should have been a row in the truth tables where they do not match. Therefore, these formulas are not equivalent.