2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Check the truth table : if they "do not match" the formulas are not equivalent. $\endgroup$ Commented Sep 5, 2019 at 7:10
  • 3
    $\begingroup$ If the truth tables are not the same then they can't be logically equivalent. $\endgroup$ Commented Sep 5, 2019 at 7:10
  • $\begingroup$ I am 100% sure this is the question. $\endgroup$
    – Www
    Commented Sep 5, 2019 at 7:14
  • 1
    $\begingroup$ The first one is equivalent to $(p \land q) \oplus (p \land r)$, though. So maybe a typo somewhere? $\endgroup$ Commented Sep 5, 2019 at 7:45

3 Answers 3

5
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ So, can I say because their truth values are different, they are not equivalent? $\endgroup$
    – Www
    Commented Sep 5, 2019 at 7:20
  • 1
    $\begingroup$ Yes, that is right. They should generate the same output for the same input, otherwise they are not equivalent. $\endgroup$ Commented Sep 5, 2019 at 7:28
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .