Logical equivalence

• A tautology is true in every row: p ∨ ¬p.
• A contradiction is false in every row: p ∧ ¬p.
• A contingency is neither.

Two formulas are logically equivalent, written A ≡ B, when they have the same value in every row, that is, when A ↔ B is a tautology. Equivalent formulas can replace each other anywhere, which is how programmers simplify conditions and how chip designers shrink circuits.

Checking by brute force

With few letters, a computer can simply try every row:

from itertools import product

def equivalent(f, g, letters):
    """Same value in every row? Returns (True, None) or (False, a row where they differ)."""
    for row in product([True, False], repeat=letters):
        if f(*row) != g(*row):
            return False, row
    return True, None

def implies(p, q):
    return (not p) or q

de_morgan = equivalent(lambda p, q: not (p and q), lambda p, q: (not p) or (not q), 2)
contrapositive = equivalent(lambda p, q: implies(p, q), lambda p, q: implies(not q, not p), 2)
converse = equivalent(lambda p, q: implies(p, q), lambda p, q: implies(q, p), 2)

print("De Morgan:", de_morgan)
print("contrapositive:", contrapositive)
print("converse:", converse)

equivalent takes two functions and tries all 2ⁿ rows. It confirms De Morgan's law and the contrapositive, and finds the row where the converse fails: p false, q true.

The laws

De Morgan's laws in words: "not (rainy and cold)" means "not rainy, or not cold". Programmers use them every day: not (x > 0 and x < 10) is x <= 0 or x >= 10.

Simplifying with the laws

¬(p ∨ (¬p ∧ q))
≡ ¬p ∧ ¬(¬p ∧ q)        De Morgan
≡ ¬p ∧ (¬¬p ∨ ¬q)       De Morgan
≡ ¬p ∧ (p ∨ ¬q)         double negation
≡ (¬p ∧ p) ∨ (¬p ∧ ¬q)  distributive
≡ F ∨ (¬p ∧ ¬q)         ¬p ∧ p is a contradiction
≡ ¬p ∧ ¬q               identity

Contrapositive, converse, inverse

For p → q:

"If it is a mango, it is a fruit" is true, and so is its contrapositive "if it is not a fruit, it is not a mango". Its converse "if it is a fruit, it is a mango" is false. Mixing up a statement and its converse is one of the most common errors in reasoning.

Mark lesson complete