6
$\begingroup$

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!

$\endgroup$
16
  • $\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$
    – Brian M. Scott
    Jan 31, 2015 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$
    – Daniel W. Farlow
    Jan 31, 2015 at 3:10
  • $\begingroup$ @induktio Thanks a lot! I forgot about manipulating the $\rightarrow$ symbol. $\endgroup$
    – Digital Shrapnel
    Jan 31, 2015 at 6:27
  • $\begingroup$ @DigitalShrapnel Does it make sense now? $\endgroup$
    – Daniel W. Farlow
    Jan 31, 2015 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$
    – Digital Shrapnel
    Jan 31, 2015 at 6:31

2 Answers 2

Reset to default
6
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .