Tautologies
A tautology is a statement that is always true.
Examples:
- P∨¬P Check with a truth table:
P
T
F
¬P
F
T
P∨¬P
T
T
Every statement is either true or false. For example, "It is raining or it isn't."
- ¬(P∨Q)↔¬P∧¬Q This is a restatement of De Morgan's law, which said ¬(P∨Q)=¬P∧¬Q. Where we have been using = to say two statements are equivalent, we could instead use ↔ 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↔Q is a tautology".
In lesson 1.5, we stated the transitive property as ((P↔Q)∧(Q↔R))→(P↔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∧¬P An example would be: "I am 6 feet tall, and I'm not."
- P∧(P→¬P) Check for yourself with a truth table.
- ¬(P∨(Q∧R)↔(P∨Q)∧(P∨R)) This is a negation of the distributive property of ∨ over ∧.
We use F to represent a contradiction. It is not the same as F, because F is a value in the T,F space whereas F is a statement that is false no matter what values you plug in.
The negation of a contradiction, ¬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: ¬(P∧¬P)=P∨¬P
Examples
The statement T is a tautology, and the statement F is a contradiction.
Claim: P⊕T=¬P
We show the claim is true with a truth table:
P
T
F
T
T
T
¬P
F
T
P⊕T
F
T
Notice that there are only 2 rows, even though there are 2 variables. This is because
T can only be true, so all possible inputs for
P and
T can be written in 2 rows.
Also, let's replace the
= with
↔.
¬P
F
T
P⊕T
F
T
¬P↔P⊕T
T
T
So, since
P⊕T=¬P, P⊕T↔¬P is a tautology.
Claim: F→P=T
We show the claim is true with a truth table:
P
T
F
F
F
F
T
T
T
F→P
T
T