Verifying Tautologies
The problem of determining whether a formula is a tautology is fundamental in propositional logic. If there are n variables occurring in a formula then there are 2n distinct valuations for the formula. Therefore the task of determining whether or not the formula is a tautology is a finite, mechanical one: one need only evaluate the truth value of the formula under each of its possible valuations. One algorithmic method for verifying that every valuation causes this sentence to be true is to make a truth table that includes every possible valuation.
For example, consider the formula
There are 8 possible valuations for the propositional variables A, B, C, represented by the first three columns of the following table. The remaining columns show the truth of subformulas of the formula above, culminating in a column showing the truth value of the original formula under each valuation.
| A | B | C | |||||
| T | T | T | T | T | T | T | T |
| T | T | F | T | F | F | F | T |
| T | F | T | F | T | T | T | T |
| T | F | F | F | T | T | T | T |
| F | T | T | F | T | T | T | T |
| F | T | F | F | T | F | T | T |
| F | F | T | F | T | T | T | T |
| F | F | F | F | T | T | T | T |
Because each row of the final column shows T, the sentence in question is verified to be a tautology.
It is also possible to define a deductive system (proof system) for propositional logic, as a simpler variant of the deductive systems employed for first-order logic (see Kleene 1957, Sec 1.9 for one such system). A proof of a tautology in an appropriate deduction system may be much shorter than a complete truth table (a formula with n propositional variables requires a truth table with 2n lines, which quickly becomes infeasible as n increases). Proof systems are also required for the study of intuitionistic propositional logic, in which the method of truth tables cannot be employed because the law of the excluded middle is not assumed.
Read more about this topic: Tautology (logic)
Famous quotes containing the word tautologies:
“Propositions show what they say: tautologies and contradictions show that they say nothing.”
—Ludwig Wittgenstein (1889–1951)