2
$\begingroup$

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?

$\endgroup$
5
  • 2
    $\begingroup$ $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$ $\endgroup$
    – user4143
    Apr 27, 2011 at 7:40
  • 2
    $\begingroup$ Couldn't you just write down the truth table and check that it's always true? $\endgroup$
    – Josh
    Apr 27, 2011 at 14:23
  • $\begingroup$ 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 $\endgroup$
    – Arvin
    May 1, 2011 at 13:09
  • $\begingroup$ 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? $\endgroup$
    – Arvin
    May 1, 2011 at 13:16
  • $\begingroup$ 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. $\endgroup$ May 2, 2011 at 10:51

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ ahh yes, that is what I meant, thanks $\endgroup$
    – Arvin
    Apr 27, 2011 at 8:35
5
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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