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?

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

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

  • $\begingroup$ 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 $\endgroup$ – Minjae Mar 17 '15 at 4:07
  • $\begingroup$ I think I got it now! in the exam, can I write 'absorption' on the place where where I put which law I used? $\endgroup$ – Minjae Mar 17 '15 at 4:23
  • $\begingroup$ 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}$$ $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – 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)

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

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.