0
$\begingroup$

This is for a homework problem, so I would prefer bumps or tips in the right direction rather than full answers.

I am supposed to show the logical equivalence of $p \leftrightarrow q$ and $(p \land q) \lor (\lnot p \land \lnot q)$ using logical identities and laws. I have looked through all of the ones I could think of and have applied them different ways and had no luck, perhaps someone could offer me some pointers for what I am missing?

The laws I have tried are - commutative, associative, distributive, identity, negation, double negative, idempotent, universal bound, De Morgan's, absorption, and conditional.

Thank you!

$\endgroup$
  • 1
    $\begingroup$ What is the definition of $\Leftrightarrow$ that you were given? $\endgroup$ – William Sep 12 '14 at 21:36
  • $\begingroup$ I believe it is the biconditional/equivalence symbol. Is there more than one definition for this symbol? $\endgroup$ – turner Sep 12 '14 at 21:41
  • $\begingroup$ All the definitions are equivalent, but how can prove anything if you do not have a fixed definition of what $\Leftrightarrow$ means? In fact, you can even define $p \Leftrightarrow q$ as $(p \wedge q) \vee (\neg p \wedge \neg q)$. $\endgroup$ – William Sep 12 '14 at 21:43
1
$\begingroup$

Apply distributive law to the second expression: \begin{align*} (p \land q) \lor (\lnot p \land \lnot q) &\equiv (p \lor \neg p) \land (p \lor \neg q) \land (q \lor \neg p) \land (q \lor \neg q) \\ &\equiv \cdots \end{align*}

Spoiler:

\begin{align*} &\equiv (\top) \land (p \lor \neg q) \land (q \lor \neg p) \land (\top) \\&\equiv (p \lor \neg q) \land (q \lor \neg p) \\&\equiv (\neg p \lor q) \land (\neg q \lor p) \\&\equiv (p \to q) \land ( q \to p)\\&\equiv p \leftrightarrow q \end{align*}

$\endgroup$
  • $\begingroup$ Ah, perfect! I really didn't understand how to use the distributive law correctly. Also your answer briefly confused me because you have to use distributive law several times to the second expression to get it to how you have the first line. I'm sure that's something I'll notice as I get more used to this stuff but it tripped me up at first. $\endgroup$ – turner Sep 12 '14 at 21:57
  • $\begingroup$ Yep! Compare it to how you FOIL things in algebra: $$ (a + b) \cdot (c + d) = (a \cdot c) + (a \cdot d) + (b \cdot c) + (b \cdot d) $$ $\endgroup$ – Adriano Sep 12 '14 at 22:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.