Building Truth Tables

Introduction

A function has 32 boolean parameters.

How many test cases do you need to exhaustively verify its behavior?

The answer is 2³² — 4,294,967,296. Four billion, two hundred ninety-four million test cases. At one test per microsecond, that is 71 minutes of pure execution time. Before assertions. Before test framework overhead. Before any I/O.

No real test suite does this. No real test suite can. This is not a gap in practice — it is a mathematical fact about the nature of boolean space. With n boolean inputs, there are 2ⁿ possible combinations. The space doubles with each additional variable.

This is where truth tables meet computational reality. A truth table is the specification of a boolean function. It lists every input combination and the required output. For small n, it is finite and buildable. For large n, it is infinite in practice. The tension between specification completeness and computational feasibility is one of the central problems of software verification.

The 32-parameter function is not hypothetical. Legacy codebases are full of functions with a dozen flag parameters, each of which is a boolean. The combination space is untestable. The bugs hide in the corners.

Thread Activation

Thread 12 (Tradeoffs) enters here — the tension between exponential completeness and practical feasibility.

Boolean composition (Chapter 2) opens a combination space. This chapter quantifies that space: n variables produce 2ⁿ rows. Chapter 17 extends this into asymptotic complexity — the formal language for measuring how costs scale. The arrow is:

T12 (Tradeoffs) ← boolean composition (Ch 2) → exponential blowup (Ch 3) → measuring efficiency (Ch 17)

The exponential growth of truth tables is the simplest concrete example of exponential complexity in this series. Every algorithm designer who avoids exponential-time solutions is, at some level, avoiding the combinatorial explosion first visible in truth tables.

The Concept

A truth table is a systematic enumeration of all possible truth value assignments to a set of variables, together with the resulting truth value of a logical expression under each assignment.

Truth tables serve two purposes:

1. Definition — they fully define what a logical operator or expression means. No ambiguity is possible. The table says what the output is for every input.
2. Verification — given two expressions claimed to be equivalent, you build both tables and compare them column by column. If they match on every row, the expressions are equivalent (Chapter 4).

The visual model: a truth table is a switch-and-circuit diagram flattened into a table. Every row is one configuration of all switches. The output column shows whether current flows (True) or not (False) through the circuit for that configuration.

How It Works

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)

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)

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:
    ...

Tradeoffs

AT9 — Correctness vs. Performance

The truth table gives you correctness. Full truth-table testing guarantees the function is correct for all inputs. The cost is 2ⁿ test cases.

For n=3, correctness is cheap. For n=32, correctness via exhaustion is impractical. You choose between:

• Correctness guarantee (enumerate 2ⁿ rows) — exponential cost, no bugs.
• Performance (test a subset of rows) — polynomial cost, possible bugs in untested combinations.

No engineering choice eliminates this tension. The tools available are:

1. Reduce n. Fewer boolean parameters means fewer combinations. Functions with many boolean flags often have implicit parameter coupling that can be expressed as enums. An enum with 4 values is one variable with 4 states — not 4 boolean variables with 16 combinations.

2. Formal methods. Model checkers and SMT solvers reason over all combinations without enumerating them. They trade compute time for theoretical completeness. For functions with 50 boolean inputs, a SAT solver might determine satisfiability of a property in milliseconds.

3. Property-based testing. Tools like Hypothesis (Python) generate random inputs from the input domain, then search for failing cases. This is not 2ⁿ coverage, but it explores the space more broadly than manual tests.

4. Accept partial coverage. For most production software, this is the actual choice. Document which combinations are tested. Design the function to minimize the impact of untested edge cases.

The AT9 tradeoff is always present. Making it explicit forces a deliberate decision about which corners of the truth table are important.

# AT9 illustration: reduce parameter count by replacing booleans with enum
from enum import Enum

class AccessLevel(Enum):
    # Instead of 3 booleans (is_admin, is_editor, is_viewer) = 8 combinations
    # Use one enum = 4 states, clearly ordered
    ADMIN = "admin"
    EDITOR = "editor"
    VIEWER = "viewer"
    NONE = "none"

def can_edit(access: AccessLevel) -> bool:
    # 4 cases instead of 8 combinations — truth table is 4 rows
    return access in (AccessLevel.ADMIN, AccessLevel.EDITOR)

Where It Fails

FM3 — Unbounded Resource Consumption

The failure mode is not in building truth tables. It is in expecting exhaustive truth-table testing to scale.

Consider a function with a boolean gate for each feature flag in a production system. Large systems have dozens of feature flags. 40 feature flags → 2⁴⁰ ≈ 1 trillion combinations. A test suite attempting to cover the full truth table would require terabytes of test data and years of runtime.

The symptom: a CI pipeline that grows slower with every new feature flag. Each flag doubles the number of theoretically-required test cases. Teams respond by testing less — fewer combinations per flag — and that is the correct tradeoff when made explicitly. It is FM3 when the team does not realize they are making it and simply runs out of capacity.

The structural fix is to minimize interaction between feature flags. If two flags are fully independent — one governs the payment flow, the other governs the notification system — they do not interact in the truth table. You can test each independently: 2¹ + 2¹ = 4 tests instead of 2² = 4. Wait, that is the same. For 3 independent flags: 3 × 2 = 6 tests instead of 2³ = 8. The saving grows: 40 independent flags require 80 tests instead of 10¹².

Independence is the key. When flags interact, the combination space grows. When they are independent, it collapses. Designing feature flags to be independent — to avoid shared mutable state and shared decision points — is a concrete engineering technique to prevent FM3 in test suites.

Real Systems

Hardware Verification — digital circuits are boolean functions. A 64-bit adder has 128 input bits → 2¹²⁸ input combinations. No team builds the full truth table. Instead, hardware design uses formal verification: the circuit is expressed as a boolean formula, and an automated theorem prover checks properties (commutativity, overflow behavior, carry propagation) over all inputs symbolically. The truth table is never enumerated; its properties are proven.

CPU Instruction Decoders — the instruction decoder in a CPU maps binary opcode patterns to control signals. Each opcode bit is a boolean. The decoder’s behavior is fully defined by a truth table (or Karnaugh map). CPU designers use Boolean minimization algorithms (Quine-McCluskey, Espresso) to reduce the truth table to the smallest circuit that produces the correct outputs. Truth tables are inputs to optimization algorithms.

Test Coverage Metrics — code coverage tools (coverage.py, gcov) measure how many branches of the program’s implicit truth table have been exercised. A function with 5 boolean conditions has a theoretical 2⁵ = 32 path combinations. Branch coverage checks each condition individually (2 × 5 = 10 states). Modified Condition/Decision Coverage (MC/DC), required for aviation software (DO-178C), checks that each condition independently affects the outcome — a formal property that reduces 32 combinations to a provable subset.

SQL Query Optimization — the SQL query optimizer treats a WHERE clause as a boolean expression. It applies truth-table-based identities to rewrite the expression: eliminate redundant terms, transform expressions to use available indexes, collapse constant sub-expressions. An expression like WHERE TRUE AND status = 'active' reduces to WHERE status = 'active'. The optimizer is applying boolean simplification — the same transformations that reduce truth table rows.

Feature Flag Systems — platforms like LaunchDarkly evaluate feature flag conditions against user attributes. A flag might be: environment == "production" AND user_in_group("beta") AND random_percentage < 0.1. This is a truth-table row — a conjunction of atomic conditions. Evaluating this for every request is fast (one conjunction). The complexity appears when flags depend on other flags — the combination space grows and interactions become hard to reason about.

Exercises