Prove that $((p\lor q)\land(p\lor(\lnot q)))\rightarrow p$

Please could someone give me some feed back on this proof? Does it look correct?

= $\lnot ((p\lor q)\land(p\lor(\lnot q)))\lor p$

= $ (\lnot(p\lor q) \lor \lnot(p\lor(\lnot q)))\lor p$

= $((\lnot p\land \lnot q)\lor(\lnot p\land \lnot(\lnot q)))\lor p$

= $((\lnot p\land \lnot q)\lor(\lnot p\land q))\lor p$

= $(\lnot p(\lnot q \lor q)))\lor p$ <----- Is this step correct?

= $(\lnot p(T))\lor p$ $\equiv true $

Thanks a million

  • 1
    $\begingroup$ @amWhy has already pointed out the actual error, but I’ll note in addition that the fourth line duplicates the third. $\endgroup$ – Brian M. Scott Jan 17 '13 at 17:36
  • $\begingroup$ Unless you're required to stick with a particular proof formalism, a plain truth table proof might be shorter and simpler. $\endgroup$ – Henning Makholm Jan 17 '13 at 18:07
  • $\begingroup$ (Though not shorter and simpler than amWhy's answer) $\endgroup$ – Henning Makholm Jan 17 '13 at 18:15

The step in question should be, using the distributive law: $$((\lnot p\land \lnot q)\lor(\lnot p\land q))\lor p$$ $$\equiv (\lnot p \land (\lnot q \lor q)) \lor p)$$

$$\equiv (\lnot p \land T) \lor p$$ $$\equiv \lnot p \lor p \equiv T$$

  • 1
    $\begingroup$ You're welcome: everything else looks good; just be sure to include your "justifications" for each step (DeMorgan's Law, etc.) in your final proof. $\endgroup$ – Namaste Jan 17 '13 at 17:44
  • $\begingroup$ Will do thanks.. $\endgroup$ – bosra Jan 17 '13 at 17:45

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.