Definition: A formula of propositional logic is a tautology if the formula itself is always true regardless of which valuation is used for the propositional variables.
There are infinitely many tautologies.
Example
This formula has only 1 variable, A. To valuate this formula A, we must assign one of the truth values true or false, and assign ~A to the other truth value.
|
tautology |
meaning | |||
|
A |
˅ |
~ |
A |
 Law of excluded middle: for any proposition, either that proposition is true, or its negation is. |
|
T |
T |
F |
T |
A or not A |
|
F |
T |
T |
F |
not A or A |
Verifying with tautologies
Why should we want to have tautologies? A tautology is a semantic way to verify that premises are true as well as their conclusion.
How do we determine whether a formula is a tautology? We 1st evaluate every variable and then the operand(s) for its possible valuations, till every part of the formula is mapped. For every variable in a formula, we have 2 values, T and F. If a formula has n variables, then there are 2n possible valuations of the formula.
For example (A˅B) has 2 variables, then this statement has 22 (=2×2=4) possible valuations. When a statement has 3 variables, then it has 23 (=2x2x2=8) possible valuations.
Tautological implication
Suppose formula S is a label for formula (A˅(B˅~B)). If R implies S, when every valuation that causes R to be true also causes S to be true, then we have a tautology.
However, suppose formula S is a label for (A˄(B˅~B)). Any valuation that makes A false, will make the formula S false, so that S is not a tautology.
Contradiction
Definition: A contradiction is a statement that is false under all circumstances.
If R is false for all values of its variables, so that there is no truth valuation that causes R to be true, then R is a contradiction.
What happens when we have a contradiction?
For example, in R implies S, the outcome of R→S for R=false, is always true, regardless of the truth or falsity of S. Say R is a label for a formula (p˄~p), which is a contradiction; then R is always false.
|
contradiction |
meaning | |||
|
p |
˄ |
~ |
p |
 |
|
T |
F |
F |
T |
p and not p |
|
F |
F |
T |
F |
not p and p |
A contradiction does not eliminate anything, and therefore it implies everything. So a contradiction is useless for purposes of logic or evidence because it is always false, and anything can follow from it.
