Tautologies
This wiki is incomplete.
A tautology is a formula whose negation is unsatisfiable. Roughly spoken, a tautoloy is always true. For example,
This statement is either true or false.
A natural number is either even or odd.
There is a special symbol that denotes a tautology. The symbol \(\top\) represents a statement that is a tautology.
With it, we can write that any statement \(A\) is a tautology by simply writing:
\(A\Rightarrow \top\)
Examples of Tautologies
Law of the excluded middle
The Law of the excluded middle states that either a statement is true or the statement's negation is true.
Let \(A\) be a statement, then we can also reword the Law of the excluded middle as
\((A \oplus (\neg A)) \Rightarrow \top\) ,
where \(\oplus\) denotes the exclusive or operation.
Reductio ad absurdum
De Morgan's Law
¬(p ∧ q) ⇔ ¬p ∨ ¬q
¬(p ∨ q) ⇔ ¬p ∧ ¬q
Proof by cases
Verifying a Tautology
If there are \(n \) variables in a formula, we check the \( 2^n \) possible valuations of the formula in a truth table