Constructing a Truth Table

Step 1: Identify the variables.

Count how many distinct propositional variables appear in the expression. Call this n.

Step 2: Determine the number of rows.

The table has 2ⁿ rows (plus a header row). One row per unique assignment of True/False to all n variables.

Step 3: Fill in the variable columns.

Assign truth values systematically. For the last variable, alternate T/F. For the second-to-last, alternate in pairs (TT/FF). For the third-to-last, alternate in groups of four (TTTT/FFFF). The pattern for variable k (counting from the right, starting at 0) is: repeat True for 2ᵏ rows, then False for 2ᵏ rows, then True again, and so on.

Step 4: Evaluate sub-expressions.

For complex expressions, add intermediate columns. Evaluate one operator at a time, left to right, following precedence.

Step 5: Fill in the output column.

The final column is the truth value of the full expression for each row.

Example: One Variable

Expression: NOT P

Two rows. The output is the inverse of the input.

Example: Two Variables

Expression: P AND Q

Four rows. AND is True only on the first row — when both P and Q are True.

Example: Three Variables with Sub-expressions

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

Three variables: P, Q, R. Eight rows.

The intermediate columns make each step auditable. You can verify any single cell without reading the whole table.

Counting Rows: Why 2ⁿ

Each variable is independent. It can be True or False. Two choices. n variables, each with two choices, give 2 × 2 × … × 2 (n times) = 2ⁿ combinations.

This is the fundamental counting principle applied to boolean variables. It is also the same logic that gives you 2ⁿ possible subsets of an n-element set (each element is either in or out — two choices, n decisions).

The growth is not linear. It is not polynomial. It is exponential. Each variable added doubles the table size. At n=32 you are already in “impractical to exhaust” territory for most testing frameworks.

Truth Tables as Boolean Function Specifications

A truth table is the canonical specification of a boolean function. Given a truth table, you can construct a boolean expression that produces exactly those outputs. The procedure is called Disjunctive Normal Form (DNF) construction:

1. For every row where the output is True, write a conjunction (AND) of all input variables (negated if the variable is False on that row).
2. Combine all these conjunctions with disjunctions (OR).

def build_dnf_expression(truth_table: list[dict]) -> str:
    """
    Build a DNF expression string from a truth table.
    truth_table: list of rows, each row is a dict with variable names as keys
    and 'output' key for the result.
    """
    terms = []
    variables = [k for k in truth_table[0] if k != 'output']

    for row in truth_table:
        if not row['output']:
            continue  # DNF only uses rows where output is True

        # Build a minterm: conjunction of all variables (negated if False)
        literals = []
        for var in variables:
            if row[var]:
                literals.append(var)          # positive literal
            else:
                literals.append(f"NOT {var}")  # negated literal

        term = " AND ".join(literals)
        terms.append(f"({term})")

    return " OR ".join(terms) if terms else "False"


# Example: XOR truth table
xor_table = [
    {'P': True,  'Q': True,  'output': False},
    {'P': True,  'Q': False, 'output': True},
    {'P': False, 'Q': True,  'output': True},
    {'P': False, 'Q': False, 'output': False},
]

print(build_dnf_expression(xor_table))
# Output: (P AND NOT Q) OR (NOT P AND Q)

The output — (P AND NOT Q) OR (NOT P AND Q) — is a valid boolean expression for XOR. It is derived mechanically from the truth table without any insight into what XOR “means.” This is the power of the DNF construction: given any desired behavior (any truth table), you can construct an expression for it.

This also proves that AND, OR, NOT are functionally complete: they can express any boolean function. Any truth table. Any behavior.

Truth Tables as Tests

A truth table is also a test suite. Each row is a test case: given these inputs, the output must be this value.

import itertools

def verify_boolean_function(func, expected_table: dict) -> bool:
    """
    Verify a boolean function against its truth table.
    expected_table: dict mapping (input tuples) to expected outputs.
    Returns True if all rows match, raises AssertionError otherwise.
    """
    for inputs, expected_output in expected_table.items():
        actual_output = func(*inputs)
        assert actual_output == expected_output, (
            f"Truth table violation: f{inputs} = {actual_output}, expected {expected_output}"
        )
    return True


# Truth table for a rate-limit decision function
# Inputs: (under_limit, is_premium, is_admin)
# Output: should the request be allowed?
rate_limit_truth_table = {
    (True,  True,  True):  True,   # under limit, premium, admin → allow
    (True,  True,  False): True,   # under limit, premium → allow
    (True,  False, True):  True,   # under limit, admin → allow
    (True,  False, False): True,   # under limit → allow
    (False, True,  True):  True,   # over limit, premium, admin → allow (premium override)
    (False, True,  False): True,   # over limit, premium → allow (premium override)
    (False, False, True):  True,   # over limit, admin → allow (admin override)
    (False, False, False): False,  # over limit, no overrides → block
}

def should_allow_request(under_limit: bool, is_premium: bool, is_admin: bool) -> bool:
    # Truth-table-derived implementation
    return under_limit or is_premium or is_admin

verify_boolean_function(should_allow_request, rate_limit_truth_table)

The truth table is written first (the specification). The function is written to match it. The test calls verify_boolean_function to confirm they agree. This is specification-driven development for boolean functions. It is not a methodology — it is just the natural consequence of having a complete, finite specification.

The Combinatorial Test Coverage Problem

For 3 variables, 8 rows, and 8 test cases, full coverage is trivial. For 10 variables, 1024 rows, full coverage is feasible. For 20 variables, one million rows — possible but slow. For 32 variables, 4 billion rows — impractical.

The real-world analog is any function with multiple boolean flags. Consider a function that processes an HTTP request with these boolean flags:

def process_request(
    is_authenticated: bool,
    has_read_permission: bool,
    has_write_permission: bool,
    is_rate_limited: bool,
    request_is_valid: bool,
    session_is_active: bool,
    resource_exists: bool,
    content_type_valid: bool,
) -> Response:
    ...

8 boolean parameters → 256 input combinations. A thorough manual test would cover all 256. In practice, testing frameworks use equivalence partitioning and boundary value analysis to select representative subsets. These are heuristics for approximating full truth table coverage.

The alternative is formal verification: express the function as a boolean formula and use an SMT solver (Satisfiability Modulo Theories) to automatically check properties over all 256 combinations. This is how hardware verification works. Software verification is catching up.