Skip to content
Tutorials Center
My learning

Topics

Lesson 6 of 37 · Propositional Logic

Tautologies, Contradictions and Logical Equivalence

Classify formulas as tautologies, contradictions or contingencies, learn De Morgan's laws and the standard equivalences, and verify them all with Python.

Some formulas are true no matter what their variables mean. Others are never true. Telling these apart, and knowing when two different-looking formulas always agree, is the engine of algebraic reasoning in logic: it lets you rewrite a formula into a simpler or more useful shape without changing its meaning.

Three kinds of formula

  • Tautology: true under every assignment. Example: p ∨ ¬p (excluded middle).
  • Contradiction: false under every assignment. Example: p ∧ ¬p.
  • Contingency: true under some assignments and false under others. Example: p → q.

A formula is satisfiable if at least one assignment makes it true. So tautologies and contingencies are satisfiable; contradictions are not. And φ is a tautology exactly when ¬φ is a contradiction. That duality is the key to SAT-based proving, which the SAT lesson develops.

Python Classifying formulas

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Surprise: (p → q) ∨ (q → p) is a tautology. In any situation, at least one of the two implications must hold.

Logical equivalence

Two formulas φ and ψ are logically equivalent, written φ ≡ ψ, when they have the same truth value under every assignment. Equivalently, φ ↔ ψ is a tautology. Note that ≡ is a statement about two formulas, while ↔ is a connective inside a formula.

The standard laws

These laws are the algebra of logic. Learn them as you learned a(b+c) = ab + ac.

Law Equivalence
Double negation ¬¬p ≡ p
De Morgan ¬(p ∧ q) ≡ ¬p ∨ ¬q; ¬(p ∨ q) ≡ ¬p ∧ ¬q
Commutative p ∧ q ≡ q ∧ p; p ∨ q ≡ q ∨ p
Associative (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) (same for ∨)
Distributive p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r); p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
Idempotent p ∧ p ≡ p; p ∨ p ≡ p
Absorption p ∨ (p ∧ q) ≡ p; p ∧ (p ∨ q) ≡ p
Implication p → q ≡ ¬p ∨ q
Contrapositive p → q ≡ ¬q → ¬p
Biconditional p ↔ q ≡ (p → q) ∧ (q → p)
Identity/domination p ∧ T ≡ p; p ∨ F ≡ p; p ∨ T ≡ T; p ∧ F ≡ F

De Morgan's laws deserve special attention. "It is not the case that both the test passed and the build is green" means "the test failed or the build is not green". Programmers use this every time they simplify !(a && b) to !a || !b.

Python Verify every law by brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Using laws to simplify

Equivalences let you transform formulas step by step, each step justified by a named law. Simplify ¬(p ∨ q) ∨ (¬p ∧ q):

  1. ¬(p ∨ q) ≡ ¬p ∧ ¬q (De Morgan), giving (¬p ∧ ¬q) ∨ (¬p ∧ q).
  2. Factor out ¬p (distributive, read right to left): ¬p ∧ (¬q ∨ q).
  3. ¬q ∨ q ≡ T (excluded middle), giving ¬p ∧ T.
  4. ¬p ∧ T ≡ ¬p (identity).

So the whole formula is equivalent to ¬p. We can confirm that numerically, which is the right habit: derive by laws, then check by table.

Python Check a simplification

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Substitution and the principle of equivalence

If φ ≡ ψ, you can replace φ by ψ anywhere inside a bigger formula without changing its truth value. That is why the chain of rewrites above is allowed: each step swaps a sub-formula for an equivalent one. This is called the substitution (or replacement) principle.

Also, a tautology stays a tautology if you substitute any formula for a variable. From p ∨ ¬p you get (x ∧ y) ∨ ¬(x ∧ y). This is how a few schemas generate infinitely many valid formulas.

Common mistakes

  • Distributing negation wrongly: ¬(p ∧ q) is not ¬p ∧ ¬q; it is ¬p ∨ ¬q.
  • Assuming the converse is equivalent to the implication.
  • Mixing up ≡ (a meta-statement) and ↔ (a connective).
  • Concluding a formula is a tautology because it is true in two or three rows; you must check all rows.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Which formula is a tautology?

    If both p and q hold then p holds, so the formula is true in every row.
  2. 2. By De Morgan, ¬(p ∨ q) is equivalent to...

    Negating a disjunction gives the conjunction of the negations.
  3. 3. φ and ψ are logically equivalent exactly when...

    Equivalence means identical truth values in every assignment, which is a tautological biconditional.
  4. 4. If φ is a contradiction, then ¬φ is...

    Negating a formula that is always false gives a formula that is always true.

Summary

  • Tautologies are always true, contradictions always false, contingencies sometimes true.
  • φ ≡ ψ means they agree on every assignment; it equals "φ ↔ ψ is a tautology".
  • Learn De Morgan, distributivity, absorption, implication-as-or and contraposition.
  • Simplify by naming each law, then double-check with a truth table or library.
  • Substitution lets you rewrite sub-formulas in place.

Next: Normal Forms: CNF and DNF