Tautologies
A tautology is a statement that is always true.
Examples:
- \(P \vee \neg P\) Check with a truth table:
\(P\)
T
F
\(\neg P\)
F
T
\(P \vee \neg P\)
T
T
Every statement is either true or false. For example, "It is raining or it isn't."
- \(\neg(P \vee Q) \leftrightarrow \neg P \wedge \neg Q\) This is a restatement of De Morgan's law, which said \(\neg(P \vee Q) = \neg P \wedge \neg Q\). Where we have been using \(=\) to say two statements are equivalent, we could instead use \(\leftrightarrow\) and say the statement is a tautology.
We are always looking for tautologies in math. As shown in the second example, we could always replace the statement "\(P = Q\)" with the statement "\(P \leftrightarrow Q\) is a tautology".
In lesson 1.5, we stated the transitive property as \(((P \leftrightarrow Q) \wedge (Q \leftrightarrow R)) \rightarrow (P \leftrightarrow R)\) is always true. Instead, we could have said it is a tautology.
Contradictions
A contradiction is a statement that is always false.
Examples:
- \(P \wedge \neg P\) An example would be: "I am 6 feet tall, and I'm not."
- \(P \wedge (P \rightarrow \neg P)\) Check for yourself with a truth table.
- \(\neg(P \vee (Q \wedge R) \leftrightarrow (P \vee Q) \wedge (P \vee R))\) This is a negation of the distributive property of \(\vee\) over \(\wedge.\)
We use \(\mathcal{F}\) to represent a contradiction. It is not the same as \(F,\) because \(F\) is a value in the \(T, F\) space whereas \(\mathcal{F}\) is a statement that is false no matter what values you plug in.
The negation of a contradiction, \(\neg \mathcal{F},\) is a tautology. So, finding a contradiction is essentially equivalent to finding a tautology since we can always negate the contradiction. The first example of a tautology above is the negation of the first example of a contradiction: \[\neg (P \wedge \neg P) = P \vee \neg P\]
Examples
The statement \(\mathcal{T}\) is a tautology, and the statement \(\mathcal{F}\) is a contradiction.
Claim: \(P \oplus \mathcal{T} = \neg P\)
We show the claim is true with a truth table:
\(P\)
T
F
\(\mathcal{T}\)
T
T
\(\neg P\)
F
T
\(P \oplus \mathcal{T}\)
F
T
Notice that there are only 2 rows, even though there are 2 variables. This is because \(\mathcal{T}\) can only be true, so all possible inputs for \(P\) and \(\mathcal{T}\) can be written in 2 rows.
Also, let's replace the \(=\) with \(\leftrightarrow.\)
\(\neg P\)
F
T
\(P \oplus \mathcal{T}\)
F
T
\(\neg P \leftrightarrow P \oplus \mathcal{T}\)
T
T
So, since \(P \oplus \mathcal{T} = \neg P,\) \(P \oplus \mathcal{T} \leftrightarrow \neg P\) is a tautology.
Claim: \(\mathcal{F} \rightarrow P = \mathcal{T}\)
We show the claim is true with a truth table:
\(P\)
T
F
\(\mathcal{F}\)
F
F
\(\mathcal{T}\)
T
T
\(\mathcal{F} \rightarrow P\)
T
T
Try entering values for \(P.\)
\(P \wedge \mathcal{T}=\) T
\(P \vee \mathcal{F}=\)
T
\(\mathcal{T} \rightarrow P=\)
T
\(P \rightarrow \mathcal{F}=\)
T
\(P \oplus \mathcal{F}=\)
T