Establishing Equivalence by Truth Table

The mechanical method: build truth tables for both expressions. Compare the output columns row by row. If the columns are identical, the expressions are equivalent.

Example: Show that P → Q is equivalent to NOT P OR Q.

First, define the conditional P → Q (“if P then Q”): it is False only when P is True and Q is False. In all other cases, it is True.

The P → Q column and the NOT P OR Q column are identical. The expressions are equivalent.

This equivalence is important in programming. The conditional “if authenticated then process” is equivalent to “either not authenticated, or process.” The second form is useful when you want to express the contrapositive or when negation-normal form is required.

Key Equivalence Laws

These laws are the algebraic identities of boolean logic. They are proven by truth table and used as rewrite rules.

Identity Laws

• P AND True ≡ P
• P OR False ≡ P

Domination Laws

• P AND False ≡ False
• P OR True ≡ True

Idempotent Laws

• P AND P ≡ P
• P OR P ≡ P

Double Negation

• NOT (NOT P) ≡ P

Commutative Laws

• P AND Q ≡ Q AND P
• P OR Q ≡ Q OR P

Associative Laws

• (P AND Q) AND R ≡ P AND (Q AND R)
• (P OR Q) OR R ≡ P OR (Q OR R)

Distributive Laws

• P AND (Q OR R) ≡ (P AND Q) OR (P AND R)
• P OR (Q AND R) ≡ (P OR Q) AND (P OR R)

De Morgan’s Laws (from Chapter 2)

• NOT (P AND Q) ≡ NOT P OR NOT Q
• NOT (P OR Q) ≡ NOT P AND NOT Q

Absorption Laws

• P AND (P OR Q) ≡ P
• P OR (P AND Q) ≡ P

Complement Laws

• P AND NOT P ≡ False (contradiction)
• P OR NOT P ≡ True (tautology — Law of Excluded Middle)

Each of these can be verified by truth table. They are universally applicable substitution rules.

Using Equivalence Laws to Simplify Expressions

Example: Simplify (P AND Q) OR (P AND NOT Q).

Step 1: Factor out P using the Distributive Law.

(P AND Q) OR (P AND NOT Q)
= P AND (Q OR NOT Q)        [Distributive: P AND (Q OR NOT Q)]

Step 2: Apply the Complement Law.

= P AND True               [Q OR NOT Q ≡ True]

Step 3: Apply the Identity Law.

= P                        [P AND True ≡ P]

The expression (P AND Q) OR (P AND NOT Q) is equivalent to P. Regardless of Q’s value, the whole expression reduces to P’s value.

In programming:

# Original: complex condition
def should_notify(is_subscribed: bool, prefers_email: bool) -> bool:
    return (is_subscribed and prefers_email) or (is_subscribed and not prefers_email)

# Simplified: logically equivalent, clearer
def should_notify_simplified(is_subscribed: bool, prefers_email: bool) -> bool:
    # (subscribed AND email) OR (subscribed AND NOT email) ≡ subscribed
    # The email preference is irrelevant — notify any subscribed user
    return is_subscribed

The simplified version makes the actual logic visible. The original version hides it. Both are correct. The simplification is a logical equivalence transformation.

Normal Forms

Two canonical forms for expressing any boolean expression:

Conjunctive Normal Form (CNF): A conjunction (AND) of disjunctions (OR). Every clause is a group of variables combined with OR; the clauses are combined with AND.

(P OR Q OR NOT R) AND (NOT P OR R) AND (Q OR R)

CNF is the input format for SAT solvers. Converting any boolean expression to CNF is always possible.

Disjunctive Normal Form (DNF): A disjunction (OR) of conjunctions (AND). Every term is a group of variables combined with AND; the terms are combined with OR. This is the form produced by the truth table construction from Chapter 3.

(P AND Q AND NOT R) OR (NOT P AND R) OR (P AND NOT Q AND R)

DNF is the form produced by reading True rows from a truth table. Converting any boolean expression to DNF is always possible.

Any expression has equivalent CNF and DNF forms. The CNF and DNF forms are themselves logically equivalent to each other and to the original expression. They differ only in structure, not in meaning.

def convert_to_dnf_from_truth_table(
    variables: list[str],
    truth_table: list[tuple[tuple[bool, ...], bool]]
) -> str:
    """
    Mechanically convert any truth table to a DNF expression.
    This always produces a logically equivalent expression.
    """
    minterms = []
    for assignment, output in truth_table:
        if not output:
            continue  # DNF uses only True-output rows

        # Build minterm: AND of each variable (negated if False)
        literals = []
        for var, value in zip(variables, assignment):
            literals.append(var if value else f"NOT {var}")
        minterms.append("(" + " AND ".join(literals) + ")")

    return " OR ".join(minterms) if minterms else "FALSE"

Tautologies and Contradictions in Code

A tautology in code is a condition that is always True. A contradiction is a condition that is always False. Both represent logic errors — you are checking something that cannot vary.

# Tautology: always True — this check is useless
def validate_count(count: int) -> bool:
    return count >= 0 or count < 0  # P OR NOT P ≡ True

# Contradiction: always False — this check always fails
def can_be_both(flag: bool) -> bool:
    return flag and not flag  # P AND NOT P ≡ False

# Real-world tautology that looks plausible
def should_log(level: str) -> bool:
    # If ERROR is the only level, this is always True — AT3 violation
    return level == "ERROR" or level != "ERROR"

Static analysis tools and type checkers detect tautologies and contradictions. A tautology in a conditional means the code always takes one branch — the other is dead code. A contradiction means the code never takes that branch. Both signal logic errors.

The SQL Query Optimizer as an Equivalence Checker

A SQL query passes through the optimizer as a tree of relational algebra operations. The optimizer applies equivalence transformations to this tree:

Predicate pushdown: Move WHERE conditions as close to the data source as possible.

-- Original
SELECT * FROM orders JOIN users ON orders.user_id = users.id
WHERE users.country = 'US'

-- Equivalent (after pushdown): filter users before the join
SELECT * FROM (SELECT * FROM users WHERE country = 'US') u
JOIN orders ON orders.user_id = u.id

Both queries return identical results for any data. They are logically equivalent. The optimizer chooses the second form because it reduces the number of rows in the join.

Constant folding:

WHERE 1 = 1 AND status = 'active'
-- Equivalent to:
WHERE status = 'active'
-- Because (True AND P) ≡ P (Identity Law)

Index selection: The optimizer knows that WHERE a = 5 AND b = 3 is equivalent to WHERE b = 3 AND a = 5 (commutative law). It chooses whichever variable has a better index and evaluates that condition first.

Every one of these is a logical equivalence transformation, applied automatically, invisibly, to every query you write.