Definition 4.1.1. Tautologies and contradictions.
A tautology is a statement that is always true, while a contradiction is a statement that is always false.
Section 4.1 Tautologies and contradictions
If we play around with compound statements and explore what can and cannot happen, we will quickly run into some statements which seem (potentially) rather silly:
\begin{gather*}
P \lor (\neg P)
\end{gather*}
This statement is always true — no matter whether \(P\) is true or false. Such a statement is called a tautology. Why might this be useful? Well — you’ve seen that when we prove things, we need to use things that are true and the above is always true.
Here is another (more obviously useful) one
\begin{gather*}
\neg (P \land Q ) \iff ( (\neg P) \lor (\neg Q) )
\end{gather*}
This statement is always true no matter what the truth values of \(P\) and \(Q\text{,}\) so it is a tautology. To see this we could either write up the truth-table, or argue
- The left-hand clause is false only when \(P\) and \(Q\) are both true. Otherwise it is false.
- The right-hand clause is false only when \(\neg P\) and \(\neg Q\) are both false. That is, it is only true when both \(P\) and \(Q\) are false. Otherwise it is true.
- Hence both clauses take the same truth values and so the biconditional is always true.
We’ll come back to this expression very shortly.
Just as there are statements that are always true, there are statements such as
\begin{gather*}
P \land (\neg P)
\end{gather*}
that are always false.This is a contradiction. Another example is
\begin{gather*}
(P \land Q) \land ((\neg P) \lor (\neg Q))
\end{gather*}
Lets write these definitions in a proper formal way so that we can refer back to it easily later if we need to do so.
We will use tautologies in the very near future, but contraditions will have to wait until later in the course — there is a proof technique called “proof by contradiction” which relies on us arriving at a contradiction.
