Propositions and Logic Gates: What if Statements Really Mean

A production system checks whether to deny access like this:

if not user.is_active and not user.is_admin:
    deny_access()

The intent: deny access when the user should not have access. The original grant condition was user.is_active and user.is_admin. Someone needed the opposite. They negated each piece: not active and not admin. Looks right. Every reviewer thought so.

It went to production. For three days, inactive admins bypassed the access check. The wrong version only denies access when the user is both inactive and not an admin. An inactive admin passes through.

The fix:

if not user.is_active or not user.is_admin:
    deny_access()

One word changed: and to or. The rule that prevents this bug has a name: De Morgan’s law. Push the negation in, flip the operator. AND becomes OR. It takes 10 seconds to apply once you know it.

This is just the first rule. There are dozens. They are the algebra of boolean expressions, and not knowing them means you are doing arithmetic by guessing.

By the end of this post, you will know the formal rules behind boolean expressions, be able to simplify any compound condition using algebraic laws, and have a Python truth table generator that verifies your work.

Why This Matters

The access control bug is not unusual. It is a specific instance of a general problem: developers work with boolean logic every day without knowing the rules.

Consider what “not knowing the rules” looks like in practice:

• Complex conditions in production code that no reviewer can confidently verify
• Boolean expressions that “probably work” but no one can prove
• Code review comments that say “I think this is right?” instead of “this is equivalent because De Morgan’s law”
• Debugging by adding print statements to check every combination, instead of reading the expression and knowing

The gap between “I can write code” and “I can reason about code” is the gap between informal intuition and formal rules. Every if statement evaluates a proposition. Every compound condition uses logical connectives. Every boolean refactor is an algebraic simplification. The rules exist. They are not hard. This post gives them names.

Propositions

You already work with propositions. Every boolean variable is one. isActive, hasPermission, isConnected. Each holds a value that is either true or false, nothing else. The formal name for this kind of statement is proposition. The formal rule: exactly two possible values, true or false, never both, never neither.

“The server is running” is a proposition. It is either true or false at any given moment.

“Is the server running?” is not a proposition. Questions are not declarative sentences. “Start the server” is not a proposition. Commands are not declarative sentences. x + 1 > 3 is not a proposition until you know the value of x (it becomes a predicate, which we cover in Part 2).

In code, every boolean expression that evaluates to true or false is a proposition. The variable isActive holds a propositional value. The expression user.age >= 18 is a proposition (once user.age has a value).

We use lowercase letters to represent propositions: p, q, r, s. This is the standard mathematical convention, and it matches what you already do in code when you write const p = user.isActive.

Logical Connectives

Propositions become powerful when you combine them. There are six standard connectives. You already know five of them from code.

Negation (NOT)

The simplest connective flips the truth value. If something is true, its negation is false. You use this every time you write ! or not.

In code: !p (JavaScript), not p (Python).

Conjunction (AND)

When you check two conditions together, you are using conjunction. Both must hold.

In code: p && q (JavaScript), p and q (Python).

The truth table has exactly four rows because there are two variables, each with two possible values: 2² = 4 combinations. Three variables would give 2³ = 8 rows. The number of rows is always 2ⁿ where n is the number of variables.

Disjunction (OR)

At least one condition must hold. This is the || you write when checking alternatives.

In code: p || q (JavaScript), p or q (Python).

This is inclusive or. “Soup or salad” in a restaurant is exclusive or (pick one). “Users who like Python or JavaScript” in a database query is inclusive or (could be both). Logic uses inclusive or by default.

Exclusive Or (XOR)

In code: p ^ q (for booleans in Python and JavaScript).

XOR has a useful property: p ⊕ p is always false, and p ⊕ false is always p. This is why XOR is used in encryption (XOR with a key, XOR again to decrypt) and in the classic swap trick (a ^= b; b ^= a; a ^= b).

Implication (IF…THEN)

Every function contract, every API guarantee, every guard clause is an implication. “If you give me valid input, I give you correct output.” Implication is the connective that makes this precise.

This is the most unintuitive connective for programmers. “If pigs fly, then I am the queen of England” is a true implication. When the hypothesis (p) is false, the implication is true regardless of the conclusion. This is called vacuous truth.

Think of it as a contract: “If you submit a valid request, I will return a 200.” The contract is only broken when you submit a valid request AND I return an error. If you submit an invalid request, the contract says nothing. It is not violated.

In code, there is no direct → operator. The equivalent is !p || q:

def implies(p: bool, q: bool) -> bool:
    return not p or q

Biconditional (IF AND ONLY IF)

In code: p === q (JavaScript for booleans), p == q (Python for booleans).

The biconditional is equivalent to (p → q) ∧ (q → p). “You pass the test if and only if you score above 70” means both: if you score above 70 then you pass, AND if you pass then you scored above 70.

Connectives Summary

Compound Propositions and Precedence

You build complex expressions by combining connectives, just like in code. And just like in code, precedence matters.

The standard precedence, from highest to lowest:

1. ¬ (NOT) — binds tightest
2. ∧ (AND)
3. ∨ (OR)
4. → (implication)
5. ↔ (biconditional)

So ¬p ∧ q means (¬p) ∧ q, not ¬(p ∧ q).

When in doubt, use parentheses. In proofs and in code, explicit parentheses are never wrong.

De Morgan’s Laws

¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q

Proof. We prove the first law by truth table. If both sides have the same truth values for every possible input, they are logically equivalent.

The ¬(p ∧ q) column and the ¬p ∨ ¬q column are identical. The expressions are logically equivalent. ∎

Try it yourself. Toggle inputs and watch the equivalence in an interactive truth table:

Step through the proof. Walk through De Morgan’s first law one step at a time:

!(a && b)  ≡  (!a || !b)
!(a || b)  ≡  (!a && !b)

The Access Control Bug, Formally

Remember the bug from the opening? Here is exactly what went wrong.

The original grant condition: active ∧ admin

To deny access, the developer needed the negation: ¬(active ∧ admin)

What they wrote: ¬active ∧ ¬admin. They negated each piece but did not flip the operator.

What De Morgan’s law gives: ¬active ∨ ¬admin. Push the negation in, flip AND to OR.

The difference shows up when active is false and admin is true (the inactive admin case):

Row 3 is the bug. The wrong version says F (do not deny), so the inactive admin gets through. The correct version says T (deny). One operator, one row, one bug. De Morgan’s law catches it every time.

See it as a circuit. Toggle the admin and owner inputs to watch the bug in action — the AND gate (Bug) vs the OR gate (Fix):

Compare in a truth table:

Short-Circuit Evaluation Is Logic

Programming languages evaluate && and || with short-circuit evaluation: if the result can be determined from the first operand alone, the second operand is not evaluated.

For &&: if the first operand is false, the result is false regardless of the second. This IS the truth table for conjunction. Look at the rows where p is F: the result is always F.

For ||: if the first operand is true, the result is true regardless of the second. This IS the truth table for disjunction. Look at the rows where p is T: the result is always T.

Short-circuit evaluation is not a performance hack. It is a direct implementation of the logical definition.

This has practical consequences:

// Safe: if ptr is null, the && short-circuits and ptr.value is never accessed
if (ptr !== null && ptr.value > 0) { ... }

// Unsafe: both sides always evaluate
if (ptr.value > 0 && ptr !== null) { ... }  // crashes if ptr is null

The order matters because of short-circuit evaluation. But it also matters logically: you cannot evaluate ptr.value if ptr is null. The implication is: if ptr is not null, THEN check its value. That is p → q, which is only evaluated when p is true.

Tautologies, Contradictions, and Contingencies

Every compound proposition falls into one of three categories, and knowing which category tells you something important about your code.

Tautologies are important because they represent logical truths. Assertions in code are propositions you believe to be tautologies in your program’s context. If an assertion fires, your “tautology” was actually a contingency, and you have a bug.

Contradictions tell you that a set of conditions can never be simultaneously satisfied. If you write if (x > 5 && x < 3), that is a contradiction. The branch is dead code. Some static analyzers catch this.

Logical Equivalence

Two boolean expressions that always produce the same output for the same inputs are interchangeable. You can replace one with the other and your program’s behavior does not change. This is the idea behind code simplification, and it has a formal name.

Logical equivalence is the foundation of code simplification. If two boolean expressions are logically equivalent, they produce the same result for every possible input. You can replace one with the other without changing behavior.

Here are the most useful logical equivalences. These are the “algebra rules” for boolean expressions.

Identity Laws

p ∧ T ≡ p
p ∨ F ≡ p

Domination Laws

p ∨ T ≡ T
p ∧ F ≡ F

Idempotent Laws

p ∧ p ≡ p
p ∨ p ≡ p

Double Negation

¬(¬p) ≡ p

Commutative Laws

p ∧ q ≡ q ∧ p
p ∨ q ≡ q ∨ p

Associative Laws

(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)

Distributive Laws

p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)

De Morgan’s Laws

¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q

Absorption Laws

p ∧ (p ∨ q) ≡ p
p ∨ (p ∧ q) ≡ p

Implication Equivalence

p → q ≡ ¬p ∨ q

Code Companion: Truth Table Generator

This program generates a truth table for any propositional logic expression. You give it variables and an expression, and it evaluates every possible combination.

from itertools import product


def truth_table(
    variables: list[str],
    expressions: dict[str, str],
) -> None:
    """Generate a truth table for one or more logical expressions.

    Args:
        variables: List of variable names (e.g., ["p", "q"])
        expressions: Dict of label -> Python boolean expression
                     (e.g., {"p ∧ q": "p and q"})
    """
    # Header
    header = variables + list(expressions.keys())
    widths = [max(len(h), 5) for h in header]
    header_line = " | ".join(h.center(w) for h, w in zip(header, widths))
    separator = "-+-".join("-" * w for w in widths)

    print(header_line)
    print(separator)

    # Evaluate for every combination of truth values
    for values in product([True, False], repeat=len(variables)):
        env = dict(zip(variables, values))

        row = []
        for val in values:
            row.append("T" if val else "F")

        for expr_code in expressions.values():
            result = eval(expr_code, {"__builtins__": {}}, env)
            row.append("T" if result else "F")

        print(" | ".join(r.center(w) for r, w in zip(row, widths)))


if __name__ == "__main__":
    print("=== Basic Connectives ===\n")
    truth_table(
        ["p", "q"],
        {
            "¬p": "not p",
            "p ∧ q": "p and q",
            "p ∨ q": "p or q",
            "p ⊕ q": "p ^ q",
            "p → q": "not p or q",
            "p ↔ q": "p == q",
        },
    )

    print("\n=== De Morgan's Laws ===\n")
    truth_table(
        ["p", "q"],
        {
            "¬(p ∧ q)": "not (p and q)",
            "¬p ∨ ¬q": "(not p) or (not q)",
            "Match": "not (p and q) == ((not p) or (not q))",
        },
    )

    print("\n=== Three Variables ===\n")
    truth_table(
        ["p", "q", "r"],
        {
            "(p ∧ q) ∨ r": "(p and q) or r",
            "p ∧ (q ∨ r)": "p and (q or r)",
        },
    )

    print("\n=== Access Control Bug ===\n")
    print("Original: active AND admin")
    print("Wrong negation vs correct negation:\n")
    truth_table(
        ["active", "admin"],
        {
            "Original": "active and admin",
            "Wrong ¬": "not active and not admin",
            "Right ¬": "not active or not admin",
        },
    )

Run it:

python truth_table.py

The output for De Morgan’s laws will show “Match” as T in every row, confirming the equivalence. The access control example will show exactly which rows differ between the wrong and correct negations — specifically, the row where active is F and admin is T.

Modify the expressions dictionary to verify any equivalence you want. Add more variables by extending the variables list. The program handles any number of variables, though tables get large past 4 (2⁴ = 16 rows).

Interactive Sandbox

Build your own truth table. Type formulas using p ∧ q, !(p || q), p → q, or use the symbol toolbar. The table auto-generates, detects equivalences, and classifies each expression:

Build your own circuit. Drag gates from the palette, click to connect wires, and toggle inputs to see signals propagate:

What’s Coming

Next in Part 2: Predicate Logic, we move from simple true/false propositions to statements about all or some elements in a set. You will meet quantifiers (∀ and ∃), which are the formal version of .every() and .some() in JavaScript, and WHERE clauses in SQL. The rules for negating quantified statements explain why a surprising number of bugs come from getting “for all” and “there exists” confused.

Practice with Rosen (8th Edition)

Essential (do these): Section 1.1: 1, 3, 5, 7, 11, 15, 23, 25; Section 1.2: 1, 3, 5, 7 Recommended (if time): Section 1.1: 27, 29, 31, 33; Section 1.2: 11, 15 Challenge (stretch): Section 1.1: 41, 43; Section 1.2: 23, 25

Further Resources

• MIT 6.042J Lecture 1 — Propositional logic, truth tables, and the first proof. The first 20 minutes cover exactly this material.
• Book of Proof, Chapter 2 (Richard Hammack) — Logic chapter covering connectives, implication, and vacuous truth in depth. Free at bookofproof.com.
• Rosen Section 1.2 — 25+ exercises drilling logical equivalences, if you want them to feel automatic.
• Coursera: Introduction to Discrete Mathematics (UCSD), Week 1 — Propositional logic with autograded exercises.

Key Takeaways

1. Every if statement is a proposition, every && is conjunction, every || is disjunction, and the rules of logic are the specification your programming language implements.
2. De Morgan’s laws (push the negation in, flip the operator) are the single most useful logical rule for simplifying code, and getting them wrong is the source of real production bugs.
3. A truth table is an exhaustive test suite for a logical expression: if two expressions produce the same column, they are equivalent, period. This is proof by exhaustion, and it is the first proof technique in your toolkit.
4. Implication (p → q) is true when p is false, which is unintuitive but correct: a contract is only broken when the precondition holds and the postcondition does not.
5. The precedence of logical operators (¬ before ∧ before ∨) matches programming languages exactly, and this is not a coincidence.