Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


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|cite|improve this question
$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
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

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|cite|improve this answer
ahh yes, that is what I meant, thanks – Arvin Apr 27 '11 at 8:35

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|cite|improve this answer

Your Answer


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.