# Proving logical equivalences

The question is to prove

$\neg (p \wedge q) \to (p \vee r)$ equivalent to $p \vee r$

So far, I got

• $¬[¬(p \wedge q)] \vee (p \vee r)$ - implication
• $(p \wedge q) \vee (p \vee r)$ - double negation

Now, is this question logically not equivalent?

Or is there some way I can prove this is logically equivalent?

• This is really propositional, rather than first-order, logic. – Noah Schweber Mar 17 '15 at 3:28
• I will be aware of it. My apologies if it bothered. – Minjae Mar 17 '15 at 4:00
• @Minjae It's just to ensure it gets the proper attention for searchers. – Graham Kemp Mar 17 '15 at 4:57

Use association, to get $((p\wedge q)\vee p) \vee r$, then use absorption.

• I got to the association part, but I can't to the absorption - is 'absorption' maybe called in any different names? I actually never heard – Minjae Mar 17 '15 at 4:07
• I think I got it now! in the exam, can I write 'absorption' on the place where where I put which law I used? – Minjae Mar 17 '15 at 4:23
• Yes, @Minjae , the Absorption laws are the equivalences: \begin{align} A & \equiv A\vee (A\wedge B) \\ & \equiv A\wedge (A\vee B)\end{align} – Graham Kemp Mar 17 '15 at 4:51

$(p \land q) \lor (p \lor r)$ is logically equivalent to $(p \land q) \lor p \lor r$ (the parentheses can be removed because we have the same $\lor$ sign inside and outside the parentheses. This is in turn logically equivalent to $p \land q \lor r$ which implies $p \lor r$. But the converse is not true, so I don't think the question has specified a valid logical equivalence.

• If $p$ is true, then $(p\wedge q)\vee p$ is true, and if $p$ is false then $(p\wedge q)\vee p$ is false. So $(p\wedge q)\vee p$ is equivalent to $p$ alone. – Graham Kemp Mar 17 '15 at 3:46

To prove the conditional statement: $\neg$ (p $\wedge$ q) $\to$ (p $\vee$ r) you assume the first part and then you could try using De Morgan's Laws, they are listed below.

$\neg$ (p $\wedge$ q) = ($\neg$ p) $\vee$ ($\neg$q)
$\neg$ (p $\vee$ q) = ($\neg$ p) $\wedge$ ($\neg$q)

• I think I skipped that part by negating twice, and I was fine. – Minjae Mar 17 '15 at 4:08