Conjunction and Implication

From ProofWiki
Jump to: navigation, search

Contents

Theorems

\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle p \land q\) \(\dashv \vdash\) \(\displaystyle \neg \left({p \implies \neg q}\right)\) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle p \implies q\) \(\dashv \vdash\) \(\displaystyle \neg \left({p \land \neg q}\right)\) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle p \land \neg q\) \(\dashv \vdash\) \(\displaystyle \neg \left({p \implies q}\right)\) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle p \implies \neg q\) \(\dashv \vdash\) \(\displaystyle \neg \left({p \land q}\right)\) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \)          Sometimes called Modus Ponendo Tollens (abbreviated $\textrm{MPT}$)          


Alternative rendition

They can alternatively be rendered as:

\(\displaystyle \) \(\displaystyle \vdash\) \(\displaystyle \) \(\displaystyle \left({p \land q}\right)\) \(\iff\) \(\displaystyle \left({\neg \left({p \implies \neg q}\right)}\right)\) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \vdash\) \(\displaystyle \) \(\displaystyle \left({p \implies q}\right)\) \(\iff\) \(\displaystyle \left({\neg \left({p \land \neg q}\right)}\right)\) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \vdash\) \(\displaystyle \) \(\displaystyle \left({p \land \neg q}\right)\) \(\iff\) \(\displaystyle \left({\neg \left({p \implies q}\right)}\right)\) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \vdash\) \(\displaystyle \) \(\displaystyle \left({p \implies \neg q}\right)\) \(\iff\) \(\displaystyle \left({\neg \left({p \land q}\right)}\right)\) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \)                    


They can be seen to be logically equivalent to the forms above.


The following can also be seen to hold:

\(\displaystyle \) \(\displaystyle \vdash\) \(\displaystyle \) \(\displaystyle \neg \left({p \implies q}\right)\) \(\implies\) \(\displaystyle p\) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \vdash\) \(\displaystyle \) \(\displaystyle \neg \left({p \implies q}\right)\) \(\implies\) \(\displaystyle \neg q\) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \)                    

which follow immediately from

$\left({p \land \neg q}\right) \iff \left({\neg \left({p \implies q}\right)}\right)$

and the rule of simplification.


Proofs

Proof by Natural Deduction

By the tableau method:

$p \land q \vdash \neg \left({p \implies \neg q}\right)$
Line Pool Formula Rule Depends upon Notes
1 1 $p \land q$ P (None)
2 2 $p \implies \neg q$ A (None) Assume the opposite of what we want to prove ...
3 1 $p$ $\land \mathcal E_1$ 1
4 1 $q$ $\land \mathcal E_2$ 1
5 1, 2 $\neg q$ $\implies \mathcal E$ 2, 3 ... and show that the assumption leads to a contradiction ...
6 1, 2 $\bot$ $\neg \mathcal E$ 4, 5
7 1 $\neg \left({p \implies \neg q}\right)$ $\neg \mathcal I$ 2-6 ... so the result follows.

$\blacksquare$


$p \implies q \vdash \neg \left({p \land \neg q}\right)$
Line Pool Formula Rule Depends upon Notes
1 1 $p \implies q$ P (None)
2 2 $p \land \neg q$ A (None) Assume the opposite of what we want to prove ...
3 2 $p$ $\land \mathcal E_1$ 2
4 2 $\neg q$ $\land \mathcal E_2$ 2
5 1, 2 $q$ $\implies \mathcal E$ 1, 3 ... and show that the assumption leads to a contradiction ...
6 1, 2 $\bot$ $\neg \mathcal E$ 5, 4
7 1 $\neg \left({p \land \neg q}\right)$ $\neg \mathcal I$ 2-6 ... so the result follows.

$\blacksquare$


$p \land \neg q \vdash \neg \left({p \implies q}\right)$
Line Pool Formula Rule Depends upon Notes
1 1 $p \land \neg q$ P (None)
2 2 $p \implies q$ A (None) Assume the opposite of what we want to prove ...
3 1 $p$ $\land \mathcal E_1$ 1
4 1 $\neg q$ $\land \mathcal E_2$ 1
5 1, 2 $q$ $\implies \mathcal E$ 2, 3 ... and show that the assumption leads to a contradiction ...
6 1, 2 $\bot$ $\neg \mathcal E$ 5, 4
7 1 $\neg \left({p \implies q}\right)$ $\neg \mathcal I$ 2-6 ... so the result follows.

$\blacksquare$


Proof of Modus Ponendo Tollens

Proof by Natural Deduction

By the tableau method:

$\neg \left({p \land q}\right) \vdash p \implies \neg q$
Line Pool Formula Rule Depends upon Notes
1 1 $\neg \left({p \land q}\right)$ P (None)
2 2 $p$ A (None)
3 3 $q$ A (None)
4 2, 3 $p \land q$ $\land \mathcal I$ 2, 3
5 1, 2, 3 $\bot$ $\neg \mathcal E$ 4, 1
6 1, 2 $\neg q$ $\neg \mathcal I$ 3-5
7 1 $p \implies \neg q$ $\implies \mathcal I$ 2-6

$\blacksquare$


$p \implies \neg q \vdash \neg \left({p \land q}\right)$
Line Pool Formula Rule Depends upon
1 1 $p \implies \neg q$ P (None)
2 2 $p \land q$ A (None) Assume the opposite of what we want to prove ...
3 2 $p$ $\land \mathcal E_1$ 2
4 2 $q$ $\land \mathcal E_2$ 2
5 1, 2 $\neg q$ $\implies \mathcal E$ 1, 3 ... and show that the assumption leads to a contradiction ...
6 1, 2 $\bot$ $\neg \mathcal E$ 5, 4
7 1 $\neg \left({p \land q}\right)$ $\neg \mathcal I$ 2-6 ... so the result follows.

$\blacksquare$


Proof by Truth Table

As can be seen by inspection, the truth values under the main connectives match for all models.

$\begin{array}{|cccc||cccc|} \hline \neg & (p & \land & q) & p & \implies & \neg & q \\ \hline T & F & F & F & F & T & T & F \\ T & F & F & T & F & T & F & T \\ T & T & F & F & T & T & T & F \\ F & T & T & T & T & F & F & T \\ \hline \end{array}$

$\blacksquare$


Proofs using the LEM

The remaining proofs depend (directly or indirectly) on the Law of the Excluded Middle.

$\neg \left({p \implies \neg q}\right) \vdash p \land q$
Line Pool Formula Rule Depends upon Notes
1 1 $\neg \left({p \implies \neg q}\right)$ P (None)
2 2 $\neg \left({p \land q}\right)$ A (None) Assume the negation of what we want to prove ...
3 2 $p \implies \neg q$ SI: from above 2 ... and use it to prove the negation of the proposition ...
4 1, 2 $\bot$ $\neg \mathcal E$ 3, 1 ... an obvious contradiction ...
5 1 $p \land q$ RAA 2-4 .. and the result follows by Reductio Ad Absurdum.

$\blacksquare$


$\neg \left({p \land \neg q}\right) \vdash p \implies q$
Line Pool Formula Rule Depends upon Notes
1 1 $\neg \left({p \land \neg q}\right)$ P (None)
2 1 $\neg p \lor \neg \neg q$ DM 1 This result depends on the Law of the Excluded Middle.
3 1 $p \implies \neg \neg q$ Rule of Material Implication 1
4 4 $p$ A (None)
5 1, 4 $\neg \neg q$ $\implies \mathcal E$ 3, 4
6 1, 4 $q$ $\neg \neg \mathcal E$ 5
7 1 $p \implies q$ $\implies \mathcal I$ 4-6

$\blacksquare$


$\neg \left({p \implies q}\right) \vdash p \land \neg q$
Line Pool Formula Rule Depends upon Notes
1 1 $\neg \left({p \implies q}\right)$ P (None)
2 2 $\neg \left({p \land \neg q}\right)$ A (None) Assume the negation of what we want to prove ...
3 2 $p \implies q$ SI: from directly above 2 ... and use it to prove the negation of the proposition ...
4 1, 2 $\bot$ $\neg \mathcal E$ 3, 1 ... an obvious contradiction ...
5 1 $p \land \neg q$ RAA 2-4 .. and the result follows by Reductio Ad Absurdum.

$\blacksquare$


Comment

Note that the Modus Ponendo Tollens:

$\neg \left({p \land q}\right) \dashv \vdash p \implies \neg q$

can be proved in both directions without resorting to the LEM.


All the others:

  • $p \land q \vdash \neg \left({p \implies \neg q}\right)$
  • $p \implies q \vdash \neg \left({p \land \neg q}\right)$
  • $p \land \neg q \vdash \neg \left({p \implies q}\right)$

are not reversible in intuitionist logic.



Proof by Truth Table

We apply the Method of Truth Tables to the propositions in turn.

As can be seen by inspection, in all cases the truth values under the main connectives match for all models.


$\begin{array}{|ccc||ccccc|} \hline p & \land & q & \neg & (p & \implies & \neg & q) \\ \hline F & F & F & F & F & T & T & F \\ F & F & T & F & F & T & F & T \\ T & F & F & F & T & T & T & F \\ T & T & T & T & T & F & F & T \\ \hline \end{array}$

$\blacksquare$


$\begin{array}{|ccc||ccccc|} \hline p & \implies & q & \neg & (p & \land & \neg & q) \\ \hline F & T & F & T & F & F & T & F \\ F & T & T & T & F & F & F & T \\ T & F & F & F & T & T & T & F \\ T & T & T & T & T & F & F & T \\ \hline \end{array}$

$\blacksquare$


$\begin{array}{|cccc||cccc|} \hline p & \land & \neg & q & \neg & (p & \implies & q) \\ \hline F & F & T & F & F & F & T & F \\ F & F & F & T & F & F & T & T \\ T & T & T & F & T & T & F & F \\ T & F & F & T & F & T & T & T \\ \hline \end{array}$

$\blacksquare$

Sources

Retrieved from "http://www.proofwiki.org/w/index.php?title=Conjunction_and_Implication&oldid=62315"
Personal tools
Namespaces
Variants
Actions
Navigation
ProofWiki.org
ToDo
Toolbox
Google AdSense