Proof Identities
Direct Proofs
These date back to as early as Aristotle and are very well-known syllogisms.
Modus Ponens
“Modus Ponens” is Latin for “method of affirming” and is also known as “affirming the consequent”.
$(a \Rightarrow b) \wedge a \quad \Rightarrow \quad b$
\[\begin{align} &(a \Rightarrow b) \wedge a && \\ &= (\overline{a} \vee b) \wedge a &&\text{Material Implication} \\ &= a \wedge (\overline{a} \vee b) &&\text{Commutativity} \\ &= a \wedge b &&\text{Simplification} \\ &\Rightarrow b &&\text{Specialization} \end{align}\]Modus Tollens
“Modus Tollens” is Latin for “method of denying” and is also known as “denying the consequent”.
$(a \Rightarrow b) \wedge \overline{b} \quad \Rightarrow \quad \overline{a}$
\[\begin{align} &(a \Rightarrow b) \wedge \overline{b} && \\ &= (\overline{a} \vee b) \wedge \overline{b} &&\text{Material Implication} \\ &= \overline{b} \wedge (b \vee \overline{a}) &&\text{Commutativity 2 times} \\ &= \overline{b} \wedge \overline{a} &&\text{Simplification} \\ &\Rightarrow \overline{a} &&\text{Specialization} \end{align}\]Disjunctive Syllogism
$(a \vee b) \wedge \overline{a} \quad \Rightarrow \quad b$
\[\begin{align} &(a \vee b) \wedge \overline{a} && \\ &= \overline{a} \wedge (a \vee b) &&\text{Commutativity} \\ &= \overline{a} \wedge b &&\text{Simplification} \\ &\Rightarrow b &&\text{Specialization} \end{align}\]Reductio ad Adsurdum / Proof by Contradiction
This is one of the most widely used proof methods. Now, we have a rigorous proof for it.
$\overline{a} \Rightarrow \color{red}F \quad = \quad a$
\[\begin{align} &\overline{a} \Rightarrow \color{red}F && \\ &= a \vee \color{red}F &&\text{Material Implication and Double Negation} \\ &= a &&\text{Identity} \end{align}\]Contrapositive
This can be extremely useful in some proofs.
$(a \Rightarrow b) \quad = \quad (\overline{b} \Rightarrow \overline{a})$
\[\begin{align} &a \Rightarrow b && \\ &= \overline{a} \vee b &&\text{Material Implication} \\ &= b \vee \overline{a} &&\text{Commutativity} \\ &= \overline{(\overline{b})} \vee \overline{a} &&\text{Double Negation} \\ &= \overline{b} \Rightarrow \overline{a} &&\text{Material Implication} \end{align}\]