Tautologies and Contradictions

It has been said that all of mathematics reduces to tautologies. Whether this is true or not - I am not sure! Nonetheless, an intuitive grasp of basic tautologies is part of the equipment of anyone who reasons with mathematics. Although the word "tautology" stands for much wider class of statements, from here on, we shall use it as a short for "truth table tautology."

A tautology is a sentential formula (or statement form) that is always true regardless of the truth values of the individual sentential formulas (or statements) substituted for its sentential variables (or statement variables).

As an example, show that the sentential formula (or statement form) p ∨ ~p is a tautology.

Notice all T's in the last column so, p ∨ ~p is a tautology.

We can also use the concept of tautology to summarize the laws of logic [see methods of proofs] in the following theorem.

Theorem 1. For propositions p, q and r, each of the following is a tautology.

A Quick Test for Tautology

If we wish to test, say, the sentential formula p ∧ q→ p ∨ r, we might proceed as follows:

For conditional to be false, the hypothesis has to be true and the conclusion false. for the given hypothesis, p ∧ q, to be true, both p and q must be true. For the given conclusion, p ∨ r, to be false, both p and r must be false. Since p cannot be true in one occurrence and false in another, it is impossible for the given sentential formula (or statement) to be false, and it is therefore tautology.

We can schematize the above argument as follows:

The unavoidable contradiction has been indicated above.

Useful Tautological Formulas

The list is, by no means, an exhaustive list. The list includes only some that are most generally useful out of the infinitude of possible tautological formulas.

The first five formulas are useful for negating complex statements.

1.     ~~p ↔ p

2.     ~(p ∧ q) ↔ ~p ∨ ~q

3.     ~(p ∨ q) ↔ ~p ∧ ~q

4.     ~(p → q) ↔ p ∧ ~q

5a.     ~(p ↔ q) ↔ (~p ↔ q)

5b.    ~(p ↔ q) ↔ (p ↔ ~q)

The next three are Commutative Laws.

6.    p ∧ q ↔ q ∧ p

7.     p ∨ q ↔ q ∨p

8.    (p ↔ q) ↔ (q ↔ p)

The next three are laws of associatively.

9.     (p ∧ q) ∧ r  ↔ p ∧ (q ∧ r)

10.    (p ∨ q) ∨ r ↔ p ∨ (q ∨ r)

11.     ((p ↔ q) ↔ r) ↔ (p ↔ (q ↔ r))

The next seven are distributive laws, involving two distinct operators and three distinct sentential variables.

12.    p ∧ (q ∨ r) ↔ (p ∧ q) ∨ ( p ∧ r)

13.    p ∨ (q ∧ r) ↔ (p ∨ q) ∧ ( p ∨ r)

14.    p → (q ∧ r) ↔ (p → q) ∧ (p → r)

15.    p → (q ∨ r) ↔ (p → q)  ∨ (p → r)

16.    (p → q) ∨ r ↔ (p ∨ r) → (q ∨ r)

17.     (p ↔ (q ∧ r)) ↔ (p ↔ q) ∧ (p ↔ r) 

18.     (p ∨ (q ↔ r)) ↔ ((p ∨ q) ↔ (p ∨ r))

19. p ↔ p Reflexivity of the Biconditional

20. p ∨ ~p Excluded Middle

21. ~(p ∧ ~p) Contradiction

____________________________________

Negation ~

And ∧

or  ∨

implies → 

equivalence  ≡ ↔ 

XOR ⊕