Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I just need my solution checked since I'm not sure if it's valid, especially the final statement

Question:

Show $p \Rightarrow (\neg(q \land \neg p))$ is a tautology by assuming:

$u \Rightarrow v$ is logically equivalent to $\neg u \lor v$

My solution:

$\neg(q \land \neg p))$ is logically equivalent to $\neg q \lor p$ (by De Morgan's law),

so $\neg q \lor p$ is logically equivalent to $q \Rightarrow p$ (given by the question) hence $p \Rightarrow (q \Rightarrow p)$ and therefore $p$ is a tautology?

share|improve this question
2  
$p \Rightarrow (\neg(q \wedge \neg p)) \equiv \neg p \vee \neg q \vee p \equiv \neg p \vee p \vee q \equiv 1 \vee q \equiv 1$ –  user4143 Apr 27 '11 at 7:40
2  
Couldn't you just write down the truth table and check that it's always true? –  jd.r Apr 27 '11 at 14:23
    
Josh, yes, but that would be the longest way to answer the question, besides this particular question asks us to solve it using the hint given –  Arvin May 1 '11 at 13:09
    
by the way, user4143 I think you made a mistake on the last 2 statements, I believe it's meant to be $\lnot q$, prob a typo? –  Arvin May 1 '11 at 13:16
    
I think the title is inaccurate. You are not asking us to show this is a tautology, which in this case is easily done with a truth table. Instead, you are asking us to check your homework answer for you. –  Carl Mummert May 2 '11 at 10:51
add comment

2 Answers

For your final statement, you want to see if $p\implies(q\implies p)$ is a tautology, not $p$, since $p$ is just an atomic sentence and could take any truth value. If $p\equiv\bot$, then the hypothesis is false, so the whole statement is true. If $p\equiv\top$, then $q\implies p$ is true, since any implication with a true conclusion is true. So $p\implies(q\implies p)\equiv\top$, that is, it is a tautology.

share|improve this answer
    
ahh yes, that is what I meant, thanks –  Arvin Apr 27 '11 at 8:35
add comment

Use De Morgan twice. You want to evaluate $A\equiv [p\Rightarrow\lnot(q\land\lnot p)]$.

(1) For every $r$, $[p\Rightarrow r]\equiv[\lnot p \lor r]$, hence $A\equiv[\lnot p \lor \lnot(q \land \lnot p)]$.

(2) For every $r$, $[\lnot(q\land r)]\equiv[\lnot q \lor \lnot r]$, hence $A\equiv[\lnot p \lor \lnot q \lor p]$.

(3) Since $[p \lor \lnot p]\equiv[$true] and [true $\lor r]\equiv[$true] for every $r$, $A\equiv[$true].

Edit A less systematic but shorter path is to note that for every $r$, $[p\Rightarrow\lnot r]\equiv[r\Rightarrow\lnot p]$ and that, for $r\equiv [q\land\lnot p]$, $[r\Rightarrow\lnot p]$ is obviously true.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.