De Morgan’s Laws

De Morgan’s Laws are the most important identities in boolean algebra for working programmers.

Law 1: NOT (P AND Q) = (NOT P) OR (NOT Q)

Law 2: NOT (P OR Q) = (NOT P) AND (NOT Q)

In plain language:

• To negate a conjunction, distribute the negation and change AND to OR.
• To negate a disjunction, distribute the negation and change OR to AND.

The transformation is symmetric. If you negate the result of applying the law, you get back the original.

Why this matters in code:

Programmers frequently write conditions as negative checks. “Don’t allow if suspended or banned.” In code:

# Version A: direct negation of compound condition
if not (user.is_suspended or user.is_banned):
    allow_access()

# Version B: De Morgan's applied manually
if not user.is_suspended and not user.is_banned:
    allow_access()

These are equivalent. A and B evaluate identically for every combination of is_suspended and is_banned. You can verify this with a truth table (Chapter 3 will formalize this). For now, trust the law and verify with a few cases:

Identical. The laws are correct.

Where De Morgan’s fails programmers:

The failure is not in the law. The law is provably correct. The failure is in applying the law incorrectly while refactoring.

Consider the payments bug from the opening hook. The original condition was computed as:

is_suspended = account_frozen and payment_blocked  # True only when BOTH hold

The authorization check was:

if not is_suspended:  # allow if NOT (frozen AND blocked)
    # By De Morgan: allow if (NOT frozen) OR (NOT blocked)
    # This is True for almost everyone
    process_payment()

The developer changed is_suspended to account_frozen or payment_blocked. Now:

is_suspended = account_frozen or payment_blocked  # True if EITHER holds

But the authorization check still reads not is_suspended, which now means NOT (frozen OR blocked), which by De Morgan’s equals (NOT frozen) AND (NOT blocked). This is correct behavior. The problem was that the intermediate variable was named is_suspended but its semantics changed, and a distant piece of code implicitly relied on those semantics. The contract (FM8) broke silently.

# Safer pattern: name the authorization condition explicitly
def can_process_payment(account_frozen: bool, payment_blocked: bool) -> bool:
    # Explicit statement: account is usable for payments
    # Named conditions prevent silent semantic drift
    account_is_usable = not account_frozen and not payment_blocked
    return account_is_usable

By naming the terminal condition, you eliminate the intermediate is_suspended variable and the implicit De Morgan inversion.

Short-Circuit Evaluation

Most programming languages implement short-circuit evaluation for AND and OR. This is a performance and safety optimization derived from the truth table structure.

Short-circuit AND:

If the left operand of P AND Q is False, the whole expression is False. The right operand does not need to be evaluated. Python, Java, C, JavaScript — all short-circuit AND.

def get_user_role(user_id: int, db) -> str | None:
    # Short-circuit AND: if user_id is falsy, db.get() is never called
    # This prevents a database call with an invalid ID
    user = user_id and db.get_user(user_id)
    return user.role if user else None

# More common pattern: guard clause using short-circuit
def process(items: list, transform) -> list:
    # If items is empty, transform is never called
    return items and [transform(item) for item in items]

Short-circuit OR:

If the left operand of P OR Q is True, the whole expression is True. The right operand is not evaluated.

def get_config_value(key: str) -> str:
    # Short-circuit OR: use cached value if available, otherwise fetch
    # fetch_from_remote() is only called if cache returns None/falsy
    return config_cache.get(key) or fetch_from_remote(key)

Implications for side effects:

Short-circuit evaluation means the right operand might not run. If the right operand has side effects — increments a counter, logs a message, modifies state — those side effects are conditional on the left operand’s value.

# Dangerous: side effect in right operand
# record_attempt() may or may not run depending on is_enabled
if is_enabled and record_attempt(user_id):
    grant_access()

If is_enabled is False, record_attempt is never called. If audit logging is required for all access attempts (including denied ones), this code silently skips the log. This is FM11 (Observability Blindness) in miniature — the system fails to record events it should be recording.

Non-short-circuit evaluation:

When you need both operands to evaluate regardless of the first, avoid compound boolean expressions with side-effectful operands. Call each function separately and store the result:

# Safe: both functions always called
attempt_recorded = record_attempt(user_id)    # always runs
is_enabled = check_enabled(user_id)            # always runs

if is_enabled and attempt_recorded:
    grant_access()

Operator Precedence

In code, NOT binds tighter than AND, which binds tighter than OR. This matches mathematical convention.

NOT > AND > OR

not a or b and c parses as (not a) or (b and c).

Explicit parentheses eliminate ambiguity. The recommendation is simple: parenthesize compound conditions. The performance cost is zero. The readability cost is zero. The correctness benefit is real.

# Ambiguous: relies on precedence knowledge
if not is_suspended or has_override and is_premium:
    ...

# Unambiguous: explicit structure
if (not is_suspended) or (has_override and is_premium):
    ...

Truth Table Preview

Each operator’s behavior is fully captured by a 2-variable truth table. Chapter 3 builds these systematically. For reference:

P     Q     P AND Q   P OR Q   NOT P   P XOR Q
True  True  True      True     False   False
True  False False     True     False   True
False True  False     True     True    True
False False False     False    True    False