1
$\begingroup$

I would like to prove the following statement : $$[ (\neg p \implies q) \land (\neg p\implies \neg q)] \implies p$$

  • I'm interested in others ways of proving that

My Proof:

  • Method $1$:

Let $ R: [ (\neg p \implies q) \land (\neg p\implies \neg q)]$

Suppose that $R$ is true

\begin{align} R &\iff [ (\neg p \implies q) \land (\neg p\implies \neg q)] \\ R &\iff ( p \lor q) \land ( p \lor \neg q) \\ R &\iff p \lor ( q \land \neg q) \\ R &\iff p \lor \bot \\ R &\iff p \end{align} - Method $2$:

Let $ R: [ (\neg p \implies q) \land (\neg p\implies \neg q)]$

Suppose that $R$ is true \begin{align} R &\iff ( p \lor q) \land ( p \lor \neg q) \\ R &\iff ( p \land p) \lor ( p \land \neg q ) \lor ( q \land p) \lor ( q \land \neg q)\\ R &\iff p \lor ( p \land \neg q ) \lor ( q \land p) \lor \bot \\ R &\iff p \lor ( p \land \neg q ) \lor ( q \land p) \\ R &\implies p \lor ( q \lor \neg q ) \\ R &\implies p \lor \bot \\ R &\implies p \end{align} i used for that line : $$p \lor ( p \land \neg q ) \lor ( q \land p) \implies p \lor ( q \lor \neg q )$$ enter image description here

  • Is my proof correct for both method if not would you explain me why and correct it

Update:

Method $2$:

\begin{align} R &\iff ( p \lor q) \land ( p \lor \neg q) \\ R &\iff ( p \land p) \lor ( p \land \neg q ) \lor ( q \land p) \lor ( q \land \neg q)\\ R &\iff p \lor ( p \land \neg q ) \lor ( q \land p) \lor \bot \\ R &\iff p \lor ( p \land \neg q ) \lor ( q \land p) \\ R &\implies p \lor ( q \lor \neg q ) \\ R &\implies p \lor \top \\ R &\implies p \end{align} am i right since i used the argument $p\land q \implies p$

$\endgroup$
2
$\begingroup$

Method 1 is correct method 2 has a flaw in the third to last line. \begin{align} R &\iff p \lor ( p \land \neg q ) \lor ( q \land p) \\ \end{align} is equivalent with \begin{align} R &\iff p \lor (p \land (\neg q \lor q)) \\ \end{align} Which in turn can be transformed to \begin{align} R &\iff p \lor (p \land \top) \\ R &\iff p \lor p \\ R &\iff p \\ \end{align} Thus we are done. What should tip you off in your solution is the fact that $q\vee \neg q $ is equivalent with $\top$ not $\bot$.

$\endgroup$
  • $\begingroup$ am i wrong using the argument $(p \land q) \implies p$ $\endgroup$ – Educ Dec 4 '15 at 14:59
  • $\begingroup$ No you are not. However it does not get you anywhere. In this case instead of getting an equivalent expression, you get $q\vee \neg q$ which is equivalent to $\top$, and this will not lead you to $p$. The only fault in your argument is really that $(q\vee \neg q)$ is equivalent with $\bot$. $\endgroup$ – Ove Ahlman Dec 4 '15 at 15:04
  • $\begingroup$ see my update please $\endgroup$ – Educ Dec 4 '15 at 15:06
  • $\begingroup$ With the update, the faulty step is that $p\vee \top$ implies $p$. The only thing which $p\vee \top$ leads to is $\top$, which is not the same as $p$. $\endgroup$ – Ove Ahlman Dec 4 '15 at 15:08
  • $\begingroup$ so i have to follow the same principale of method 1 $\endgroup$ – Educ Dec 4 '15 at 15:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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