Tautologies and Contradictions
| Definition: A formula is said to be a Tautology if every truth assignment to its component statements results in the formula being true. A formula is said to be a Contradiction if every truth assignment to its component statements results in the formula being false. |
It is easy to tell whether a formula is a tautology, contradiction, or neither by first constructing the truth table for the formula and examining the far right column. If the far right column contains only true then the formula is a tautology. If the far right column contains only false then the formula is a contradiction. Otherwise, the formula is neither a tautology or a contradiction. Let's look at a few examples
Let $P$ and $Q$ be statements and consider the formula:
(1)We construct the truth table for this formula:
| $P$ | $Q$ | $\neg P$ | $(P \wedge \neg P)$ | $(P \wedge \neg P) \rightarrow Q$ |
|---|---|---|---|---|
| T | T | F | F | T |
| T | F | F | F | T |
| F | T | T | F | T |
| F | F | T | F | T |
We look at the far right column of the truth table and see all trues. Therefore $(P \wedge \neg P) \rightarrow Q$ is a tautology.
For an example of a contradiction, consider the formula $(P \vee \neg P) \rightarrow (Q \wedge \neg Q)$. It is easy to see that $P \vee \neg P$ is true for all truth assignments to $P$. Furthermore, it is easy to see that $Q \wedge \neg Q$ is false for all truth assignments to $Q$. Therefore it must be that this formula results in falsehood for all truth assignments to $P$ and $Q$. So $(P \vee \neg P )\rightarrow (Q \wedge \neg Q)$ is a contradiction.