Back to Basics (4) Proof by Contradiction

The method of proof by contradiction establishes a statement as true by showing that its negation leads to two mutually exclusive results. This method is made possible by the fact that in Boolean Algebraic logic a proposition is either true or false and no where in between. 

For every contradiction N and every proposition ᵹ the formula ᵹ ⇔ ( ¬ᵹ ⇒ N) is a tautology. If ¬ᵹ ⇒ N is true, then ᵹ is true by contraposition. N can also be represented by (ᴔ ∧ ¬ᴔ) where ᴔ is a proposition. If it can be shown that ¬ᵹ ⇒ ᴔ and ¬ᵹ ⇒ ¬ᴔ, then [¬ᵹ ⇒ (ᴔ ∧ ¬ᴔ)] ⇔ ( ¬ᵹ ⇒ N). Since, the proposition ¬ᵹ ⇒ (ᴔ ∧ ¬ᴔ) can be constructed (is true) the only possibility is that ¬ᵹ must be false.

Assume P and Q are propositions, P ⇒ Q, and (P ⇒ Q) ⇔ ᵹ. (P ⇒ Q) ⇔ ¬(P ∧ ¬Q). So, ¬ᵹ ⇔ (P ∧ ¬Q). In order to prove ¬ᵹ ⇒ (ᴔ ∧ ¬ᴔ), if P ⇒ ᴔ and ¬Q ⇒ ¬ᴔ, then ¬ᵹ ⇒ (ᴔ ∧ ¬ᴔ) since [(P ⇒ ᴔ) ∧ (¬Q ⇒ ¬ᴔ)] ⇒ [(P ∧ ¬Q) ⇒ (ᴔ ∧ ¬ᴔ)]. Therefore P ⇒ Q is true according to the method of proof by contradiction.

Back To Basics (3) Proof by Tautology

Tautologies can be used to prove new propositions or justify old ones. The transitive property of both ⇒ and ⇔ allow this to be done. Start with truth tables to demonstrate their transitivity, then use proof by tautology. (Tautologies listed on pages tab at the top right corner of the Home page)

Proof by Tautology 1

1.) A ∧ B                                         Assume

2.) ¬[¬(A ∧ B)]                             t8

3.) ¬[(¬A ∨ ¬B)]                           De Morgan's First Law

 ∴ (A ∧ B) ⇔ ¬[(¬A ∨ ¬B)]        Conclusion

Each line in this proof is equivalent to the next. The transitive property allows for the "detachment" and/or "addition" of propositions. Since each line from the first is a tautology built from line one, each proposition must therefore be equivalent to the first.

Proof by Tautology 2

1.) ¬A ∧ ¬B                             Assume

2.) ¬{[¬(¬A)] ∨ ¬(¬B)]}       Proof by Tautology 1

3.) ¬{A ∨ B}                            Complete Law of Double Negation

∴ ¬A ∧ ¬B ⇔ ¬{A ∨ B}        Conclusion

Tetrahedron

Back to Basics (2) Tautologies and Contradictions

A formula is a tautology iff it is true for all possible truth values of its components. To find out if a propositional form is a tautology a truth table is a sufficient means of proof. Here is a list of five important tautological formulae:

1.) A ∨ ¬A                                                         Law of Excluded Middle
2.) ¬(¬A ) ⇔ A                                                 Complete Law of Double Negation
3.) (A ⇒ B) ⇔ (¬B ⇒ ¬A)                               Complete Law of Contraposition
4.) (A ⇒ (B ⇒ C) ⇒ [(A ⇒ B) ⇒ (A ⇒ C)]     Transitivity of Logical Implication
5.) (A ∧¬A) ⇒ B                                               A Contradiction Implies Every Consequent

A and B are logical formulae and logically equivalent iff A ⇔ B is a tautology.

A formula is a contradiction iff it is false for all possible truth values of its components. To find out if a propositional form is a contradiction again a truth table can be used. Here are a couple examples of contradictions:

1.) A ∧¬A
2.) (A ∧ B) ∧ (¬A ∧ ¬B)

Icosahedron

Dodecahedron

Back to Basics (1) Forming Propositions

A proposition is a formula possessing a truth value indicated by ○ (true) and ● (false). In Boolean Algebraic Logic each proposition is either ○ or ● and no where in between. The following tables indicate how each connective alters the truth values of its components. Each truth value of a compound formula is a function of the truth values of its components.

¬ is called negation, ∧ is called a conjunction, ∨ disjunction, ⇒ implication, and ⇔ equivalence.