In discrete mathematics, logical propositions are analyzed based on how their truth values behave under all possible conditions. Some statements are always false (contradictions), while others vary (contingencies). A special and important class of propositions is tautology, which is always true regardless of the truth values of its components.
Tautologies are fundamental in:
A tautology is a compound proposition that is true for all possible truth values of its variables.
A proposition is called a tautology if its truth table contains only True values.
There is no single symbol that represents tautology universally. Instead, a statement is identified as a tautology by verifying that it is always true.
A standard example is:
p ∨ ¬p
Consider:
p ∨ ¬p
| p | ¬p | p ∨ ¬p |
|---|---|---|
| True | False | True |
| False | True | True |
p, the expression is always truep ∨ ¬p
✔ Always true
(p → q) ∨ (q → p)
✔ Always true regardless of p and q
¬(p ∧ q) ↔ (¬p ∨ ¬q)
✔ This represents De Morgan’s Law, which is always true
A proposition is a tautology if:
| Type | Description | Example |
|---|---|---|
| Tautology | Always true | p ∨ ¬p |
| Contradiction | Always false | p ∧ ¬p |
| Contingency | Sometimes true, sometimes false | p → q |
p ∨ ¬p
p → q ≡ ¬p ∨ q
This expression can lead to tautologies in many cases.
p ↔ p
✔ Always true
A tautology is a proposition that is always true
Identified using truth tables
Standard example: p ∨ ¬p
Plays a key role in logic, proofs, and computation
Distinguished from: