4

How do I prove this using logical equivalences?

$(p \rightarrow q) \lor (q \land r) \equiv \neg ((p \land \neg r) \land \neg q) \land \neg (r \land (\neg q \land p))$

Any suggestions or tips would be greatly appreciated. Thanks in advance!

EDIT: Stuff I've tried so far:

Using the law of implication to change the $p \rightarrow q$ into $\neg p \lor q$

It seems like $r$ appears on both sides of the $\land$ in the final expression, so I tried expanding the single $r$ in $q \land r$ into $r \land r$ to give $q \land (r \land r)$ but that doesn't seem to be getting me anywhere

M42
  • 71
  • A simple and straightforward approach is to construct truth tables if you have a few primitive statements or logical variables. – ThisIsNotAnId Apr 03 '16 at 23:46

3 Answers3

2

Claim: $$ (p \rightarrow q) \lor (q \land r) \equiv \neg ((p \land \neg r) \land \neg q) \land \neg (r \land (\neg q \land p)) $$ LHS: $$ (p \rightarrow q) \lor (q \land r) \equiv (\neg p \lor q) \lor (q \land r) \equiv ((\neg p \lor q) \lor q ) \land ((\neg p \lor q) \lor r) \equiv \\ (\neg p \lor q ) \land ((\neg p \lor q) \lor r) \equiv (\neg p \lor q) $$ RHS: $$ \neg ((p \land \neg r) \land \neg q) \land \neg (r \land (\neg q \land p)) \equiv \\ \neg [((p \land \neg r) \land \neg q) \lor (r \land (\neg q \land p))] \equiv \\ \neg [((\neg q \land p) \land \neg r) \lor ((\neg q \land p) \land r)] \equiv \\ \neg [((\neg q \land p) \land (r \lor \neg r)] \equiv \\ q \lor \neg p \equiv (\neg p \lor q) $$

so LHS = RHS and the Claim is true.

Anonymous
  • 1,158
0

Hint: Convert each side to DNF (an OR of ANDs) using the identities:

  • $x \to y \equiv \neg x \lor y$
  • $\neg (x \lor y) \equiv \neg x \land \neg y$
  • $\neg (x_1 \land \cdots \land x_n) \equiv \neg x_1 \lor \cdots \lor \neg x_n$
Adriano
  • 41,576
0

First let’s recall a few laws.

  • definition of implication: $a\implies b \equiv \lnot a \lor b$
  • DeMorgan's Laws:
    • $a \lor b \equiv \lnot(\lnot a \land \lnot b)$
    • $a \land b \equiv \lnot(\lnot a \lor \lnot b)$
  • Commutation:
    • $a \lor b \equiv b \lor a$
    • $a \land b \equiv b \land a$
  • Association:
    • $(a \lor b) \lor c \equiv a \lor (b \lor c)$
    • $(a \land b) \land c \equiv a \land (b \land c)$
  • Distribution:
    • $a \lor (b \land c) \equiv (a \lor b) \land (a \lor c)$
    • $a \land (b \lor c) \equiv (a \land b) \lor (a \land c)$
  • Idempotency:
    • $a \lor a \equiv a$
    • $a \land a \equiv a$
  • Identity:
    • $a \lor \bot \equiv a$
    • $a \land \top \equiv a$
  • Zero:
    • $a \lor \top \equiv \top$
    • $a \land \bot \equiv \bot$

Starting with the RHS and working backward, \begin{align} \lnot((p \land \lnot r) \land \lnot q) &\land \lnot(r \land (\lnot q \land p))\\ \lnot(p \land \lnot q \land \lnot r) &\land \lnot(p \land \lnot q \land r) \quad\text{Association and Commutation}\\ (\lnot p \lor q \lor r) &\land (\lnot p \lor q \lor \lnot r) \quad\text{DeMorgan}\\ ((p \implies q) \lor r) &\land ((p \implies q) \lor \lnot r) \quad\text{dfn. of impl.}\\ (p \implies q) &\lor (r \land \lnot r) \quad\text{Distribution}\\ (p \implies q) &\lor \bot \quad\text{dfn. of Contradiction}\\ p &\implies q \quad\text{Identity}\\ \end{align}

Now starting with the LHS and working forward, \begin{align} (p \implies q) &\lor (q \land r)\\ ((p \implies q) \lor q) &\land ((p \implies q) \lor r) \quad\text{Distribution}\\ ((\lnot p \lor q) \lor q) &\land ((p \implies q) \lor r) \quad\text{dfn. of impl.}\\ (\lnot p \lor q) &\land ((p \implies q) \lor r) \quad\text{Associativity and Idempotency}\\ (p \implies q) &\land ((p \implies q) \lor r) \quad\text{dfn. of impl.}\\ ((p \implies q) \lor \bot) &\land ((p \implies q) \lor r) \quad\text{Identity}\\ (p \implies q) &\lor (\bot \land r) \quad\text{Distribution}\\ (p \implies q) &\lor \bot \quad\text{Zero}\\ p &\implies q \quad\text{Identity}\\ \end{align}

Therefore both the LHS and RHS are logically equivalent to $p \implies q$, and by Transitivity of equivalence, the LHS and the RHS are logically equivalent to each other.

chharvey
  • 2,612
  • 1
    You didn't make a mistake - I did (d'oh!). The RHS is supposed to be ¬((p∧¬r)∧¬q), not ¬((p∧r)∧¬q). I've updated the equation. Thanks for your help. PS: The "squares" law is called idempotency. Just in case you were still wondering. – M42 Apr 02 '16 at 20:41
  • why only editing your answer instead of upvoting the one that already provided the solution? Besides most of what you did is based on that solution. – Anonymous Apr 03 '16 at 06:03
  • It's called "Absorption Law" btw.... http://mathworld.wolfram.com/AbsorptionLaw.html – Anonymous Apr 05 '16 at 03:02
  • I find it odd, that you copy my answer (modified it a bit) and submit it as yours.... – Anonymous Apr 05 '16 at 03:03
  • @Anonymous as hard as it may be to realize that there are other people with intelligence in this world, I arrived at my solution independently from yours. I can send you screenshots of my hand-written scratch work if you'd like. – chharvey Apr 05 '16 at 03:14
  • Then why commenting "not sure of this step...." ? in one of your edits? Besides in your very first answer you were only defining stuff not dealing with the problem is after my answer that you "started" (copied) the process – Anonymous Apr 05 '16 at 03:15
  • @Anonymous because, as I'm sure you know, the first answer is not always perfect. it takes many revisions to get it right. I'll admit I took that one step from your answer, which at the time I wasn't sure of, but the important part is that I went back and proved it later on when I had time. I never take material I don't understand and claim it as my own. but if mathematicians weren't allowed to borrow material from one another, we'd still be in the Stone Age. get off your high horse and stop fretting over reputation points. – chharvey Apr 05 '16 at 03:23