Skip to content
Tutorials Center
My learning

Topics

Lesson 6 of 68 · Logic

Logical Equivalences and Laws

Learn the laws of propositional logic, including De Morgan, distributive and absorption, use them to simplify expressions, and verify each law in Python.

Two statements are logically equivalent when they always have the same truth value, whatever the variables are. Equivalences are the algebra of logic: just as you can rewrite 2(x + 3) as 2x + 6 without changing its value, you can rewrite a Boolean expression into a simpler or more useful shape without changing what it says. This is how compilers optimize conditions, how database engines rewrite queries and how you tidy a tangled if in your own code.

In this lesson you will learn the standard laws, see why De Morgan's laws matter in practice, simplify expressions step by step, and check every law by brute force. You met the checking idea in Truth Tables; here we use it to build a reusable law checker.

The standard laws

Write A ≡ B for "A and B are logically equivalent". Here is the list you will use again and again, where T stands for any tautology and F for any contradiction.

Laws that look like arithmetic

Commutative p ∧ q ≡ q ∧ p, and the same for OR.
Associative Grouping of a long AND or OR does not matter.
Distributive AND spreads over OR, and OR spreads over AND.
Idempotent p ∧ p ≡ p and p ∨ p ≡ p.
1 / 2

Written in full:

Law AND form OR form
Identity p ∧ T ≡ p p ∨ F ≡ p
Domination p ∨ T ≡ T p ∧ F ≡ F
Idempotent p ∧ p ≡ p p ∨ p ≡ p
Complement p ∧ ¬p ≡ F p ∨ ¬p ≡ T
Commutative p ∧ q ≡ q ∧ p p ∨ q ≡ q ∨ p
Distributive p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
Absorption p ∧ (p ∨ q) ≡ p p ∨ (p ∧ q) ≡ p
De Morgan ¬(p ∧ q) ≡ ¬p ∨ ¬q ¬(p ∨ q) ≡ ¬p ∧ ¬q

Plus double negation (¬¬p ≡ p) and the conditional rewrite p → q ≡ ¬p ∨ q, which turns every implication into AND, OR and NOT.

Notice the symmetry: swap every ∧ with ∨ and every T with F in a law, and you get another law. This duality is a hidden gift: prove one half and you get the other.

Verifying the laws in Python

Instead of trusting the table, we can test each law on every assignment of its variables. The helper below represents a law as two functions and compares them on all rows.

Python Check 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.

Every line prints True. Now a warning in the opposite direction: some "laws" that look plausible are false. The checker will tell you so.

Python A fake law is caught

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.

The first fake law fails at p = True, q = False. The second also fails: "if p and q then r" is weaker than "if p then r, and if q then r".

De Morgan's laws in practice

De Morgan's laws say that negating an AND gives an OR of negations, and negating an OR gives an AND of negations. They are the rule behind many code refactors:

Python
# "not (logged_in and has_permission)"
if not (logged_in and has_permission):
    deny()

# the same condition, spelled out
if (not logged_in) or (not has_permission):
    deny()

They also explain a common search-box surprise: "NOT (cat OR dog)" excludes pages that mention either word, which means "no cat AND no dog". Beginners often write "no cat OR no dog", which still lets through pages that mention one of the animals.

Simplifying expressions

Laws let you transform a formula step by step, writing the reason for each step. Let us simplify ¬(p ∨ ¬q) ∨ (p ∧ q).

  1. ¬(p ∨ ¬q) ≡ ¬p ∧ ¬¬q by De Morgan.
  2. ¬¬q ≡ q by double negation, giving ¬p ∧ q.
  3. The formula is now (¬p ∧ q) ∨ (p ∧ q).
  4. Factor out q by the distributive law (read right to left): (¬p ∨ p) ∧ q.
  5. ¬p ∨ p ≡ T by complement, and T ∧ q ≡ q by identity.

The whole expression simplifies to just q. A correct simplification should preserve truth values everywhere, and we can double check with Python.

Python Confirm 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.

A related use is simplifying a convoluted condition:

Python
# before
if (age >= 18 and not banned) or (age >= 18 and not banned and vip):
    ...

# after absorption: A or (A and B) == A
if age >= 18 and not banned:
    ...

Here A is age >= 18 and not banned, and B is vip; the absorption law deletes the second branch.

Python's and and or return one of their operands, not strictly True or False: [] or "x" gives "x". The laws hold for genuine booleans. When your values can be truthy or falsy objects, the results of two equivalent formulas may differ in type even when they agree in truthiness. Wrap values in bool(...) if you compare them.

Equivalence chains as proofs

A chain of equivalences is a real proof, which is the algebraic counterpart of a truth table. The proof that p → q ≡ ¬q → ¬p (the contrapositive from Implication and Biconditional) takes three steps: rewrite as ¬p ∨ q, then swap the operands to q ∨ ¬p, and read it as ¬¬q ∨ ¬p, which is ¬q → ¬p. No table needed, and it works unchanged for formulas with 100 variables. Later, in Normal Forms and SAT, you will use these laws to convert any formula to a standard shape.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. What is ¬(p ∨ q) equivalent to?

    De Morgan's law says the negation of an OR is the AND of the negations.
  2. 2. Which law lets you simplify p ∨ (p ∧ q) to p?

    Absorption says that p ∨ (p ∧ q) ≡ p, because whenever the second part is true, p is already true.
  3. 3. Which pair is NOT logically equivalent?

    De Morgan turns ¬(p ∧ q) into ¬p ∨ ¬q, with an OR. Using AND is the classic mistake; at p true and q false the two sides disagree.
  4. 4. What does p ∧ ¬p simplify to?

    By the complement law, p ∧ ¬p is a contradiction, so it is always false.
  5. 5. Which is the safest way to gain confidence that a proposed law is correct?

    A law must hold for all assignments, and with few variables you can test them all. One failing row is a counterexample.

Summary

  • Logical equivalence means equal truth values on every assignment; laws let you rewrite formulas safely.
  • Key laws: commutative, associative, distributive, idempotent, identity, domination, complement, absorption, double negation and De Morgan.
  • De Morgan swaps AND with OR when pushing a negation inward; forgetting the swap is a classic bug.
  • Simplify step by step, naming the law used, and confirm with a brute-force Python check.
  • Equivalence chains are real proofs, and unlike truth tables they scale to formulas of any size.

Next: Normal Forms and SAT, standard shapes for formulas and the problem of satisfying them.