Proof formula of Proof by Contradiction $[ (\neg p \implies q) \land (\neg p\implies \neg q)] \implies p$

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 )$$

• 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$

1 Answer

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$.

• am i wrong using the argument $(p \land q) \implies p$ – Educ Dec 4 '15 at 14:59
• 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$. – Ove Ahlman Dec 4 '15 at 15:04
• see my update please – Educ Dec 4 '15 at 15:06
• 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$. – Ove Ahlman Dec 4 '15 at 15:08
• so i have to follow the same principale of method 1 – Educ Dec 4 '15 at 15:11