I need to prove that $(\neg p \wedge (p \vee q)) \rightarrow q $ is a tautology using Laws of Logic (not truth tables).

This is what I tried:

$\equiv (( \neg p \wedge p) \vee (\neg p \wedge q)) \rightarrow q \\ \equiv (F \vee (\neg p \wedge q)) \rightarrow q \\ \equiv (\neg p \wedge q) \rightarrow q \\ \equiv (F) \rightarrow q \\ \equiv T $

Is this logically correct? The laws I used in order were: Distributive, then negation, and identity. My only issue is with the last step where I know the truth values of $(\neg p \wedge q)$ are all $F$ but I dont know what law it uses.

Please Help!

  • $\begingroup$ $\neg p\land q$ can have either truth value; it need not be $F$. Do you have $p\to q\equiv \neg p\lor q$? $\endgroup$ Jan 31 '15 at 3:08
  • $\begingroup$ As Brian M. Scott points out, $\neg p\land q$ may be either $T$ or $F$. My answer gives you a strong hint on how to use the equivalences you deduced so far to end up with your tautology. :) $\endgroup$ Jan 31 '15 at 3:10
  • $\begingroup$ @induktio Thanks a lot! I forgot about manipulating the $\rightarrow$ symbol. $\endgroup$ Jan 31 '15 at 6:27
  • $\begingroup$ @DigitalShrapnel Does it make sense now? $\endgroup$ Jan 31 '15 at 6:28
  • $\begingroup$ @induktio Yeah. I just need to backtrack to fully understand how $\neg p \wedge q$ is operated on. But I see where it leads. $\endgroup$ Jan 31 '15 at 6:31

Hint: We have that $$ (\neg p \land q)\to q \equiv (p\lor \neg q)\lor q \equiv p \lor (\neg q\lor q). $$ You should be able to take it from there.


It's been a while since my discrete class, but here's my try. It looks like all you really need to use is the simple Elimination Rule, which states:

$p \wedge q \rightarrow p$

OR (stay with me)

$p \wedge q \rightarrow q$

So, to finish off the last part of your problem:

$\equiv (\neg p \wedge q) \rightarrow q \\ \equiv q \rightarrow q \\$

Or, heck:

$\equiv (\neg p \wedge q) \rightarrow q \\ \equiv \neg p \rightarrow q \\$

Here's a clean, handy cheat sheet that may help you out. One thing I remember is it's easy getting caught up in what the values of p and q may be, when what's important in "proofs" like these is establishing a route to truth. Thinking that way helped me out.


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.