Tautologies

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$

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

If there are $n$ variables in a formula, we check the $2^n$ possible valuations of the formula in a truth table