Math Home

Logic

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 - \(\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.

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\]

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

T

F

\(\mathcal{T}\)

T

T

T

T

\(\neg P\)

F

T

F

T

\(P \oplus \mathcal{T}\)

F

T

F

T

Also, let's replace the \(=\) with \(\leftrightarrow.\)

\(\neg P\)

F

T

F

T

\(P \oplus \mathcal{T}\)

F

T

F

T

\(\neg P \leftrightarrow P \oplus \mathcal{T}\)

T

T

T

T

Claim: \(\mathcal{F} \rightarrow P = \mathcal{T}\)

We show the claim is true with a truth table:

\(P\)

T

F

T

F

\(\mathcal{F}\)

F

F

F

F

\(\mathcal{T}\)

T

T

T

T

\(\mathcal{F} \rightarrow P\)

T

T

T

T

Try entering values for \(P.\)

\(\mathcal{T} \rightarrow P=\) T

\(P \rightarrow \mathcal{F}=\) T

\(P \oplus \mathcal{F}=\) T

\(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