Natural Deduction

Overview

Natural deduction is a proof system typically used alongside classical truth-functional propositional and predicate logic. It is meant to mimic the patterns of reasoning that one might “naturally” make when forming arguments in plain English.

Axioms

Natural deduction is interesting in that it has no axioms.

Inference Rules

Scoped to propositional logic, there are 10 inference rules corresponding to an “introduction” and “elimination” of each propositional logic operator.

Negation

For propositions $E_{1}$ and $E_{2}$ , $\neg - I : from E_{1} infer E_{2} \land \neg E_{2} \neg E_{1}$ and $\neg - E : from \neg E_{1} infer E_{2} \land \neg E_{2} E_{1}$

Conjunction

For propositions $E_{1}, \dots, E_{n}$ , $\land - I : E_{1}, \dots, E_{n} E_{1} \land \dots \land E_{n}$ and $\land - E : E_{1} \land \dots \land E_{n} E_{i}$

Disjunction

For propositions $E_{1}, \dots, E_{n}$ , $\lor - I : E_{i} E_{1} \lor \dots \lor E_{n}$ and $\lor - E : E_{1} \lor \dots \lor E_{n}, E_{1} \Rightarrow E, \dots, E_{n} \Rightarrow E E$

Implication

For propositions $E_{1}, \dots, E_{n}$ , $\Rightarrow - I : from E_{1}, \dots, E_{n} infer E (E_{1} \land \dots \land E_{n}) \Rightarrow E$ and $\Rightarrow - E : E_{1} \Rightarrow E_{2}, E_{1} E_{2}$

Biconditional

For propositions $E_{1}$ and $E_{2}$ , $\Leftrightarrow - I : E_{1} \Rightarrow E_{2}, E_{2} \Rightarrow E_{1} E_{1} \Leftrightarrow E_{2}$ and $\Leftrightarrow - E : E_{1} \Leftrightarrow E_{2} E_{1} \Rightarrow E_{2}, E_{2} \Rightarrow E_{1}$

Bibliography

Gries, David. The Science of Programming. Texts and Monographs in Computer Science. New York: Springer-Verlag, 1981.

My Notebook

Explorer