# Propositional Logic Help: $(\neg p \wedge (p \vee q)) \rightarrow q$ is a tautology

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.

• $\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$? Jan 31 '15 at 3:08
• 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. :) Jan 31 '15 at 3:10
• @induktio Thanks a lot! I forgot about manipulating the $\rightarrow$ symbol. Jan 31 '15 at 6:27
• @DigitalShrapnel Does it make sense now? Jan 31 '15 at 6:28
• @induktio Yeah. I just need to backtrack to fully understand how $\neg p \wedge q$ is operated on. But I see where it leads. 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.