Build a Truth Table Generator in Python (Parser, Evaluator, Tautology Checker)

Truth tables show up in discrete math, digital logic, and philosophy courses, and they're tedious by hand. A 4-variable expression means 16 rows, and one slipped F ruins the whole table.

This is a good small project for developers: a tokenizer, a recursive descent parser, and an evaluator, in under 150 lines of Python with no dependencies. I'll walk through how it works and link a free web version at the end.

The plan

Given an input like ~(A & B) <-> (~A | ~B), we need to:

1. Tokenize the string into operators, parentheses, and variable names.
2. Parse the tokens into an expression tree, respecting operator precedence.
3. Collect the variables, then generate every T/F combination (2ⁿ rows).
4. Evaluate the tree for each row.
5. Classify the result: tautology, contradiction, or contingent.

Step 1: Tokenizing

One regex handles everything. Longer operators (<->, ->) must come before shorter ones so they aren't split apart:

import re

TOKEN = re.compile(r"\s*(<->|->|[()~!&|^]|[A-Za-z_]\w*)")

def tokenize(expr):
    tokens, pos = [], 0
    expr = expr.strip()
    while pos < len(expr):
        m = TOKEN.match(expr, pos)
        if not m:
            raise ValueError(f"Unexpected character at position {pos}: {expr[pos]!r}")
        tokens.append(m.group(1))
        pos = m.end()
    return tokens

Word operators like AND, OR, NOT, and XOR come through as variable-looking tokens, so we map them to symbols in the parser.

Step 2: Precedence

This is where most hand-rolled parsers go wrong. From lowest to highest binding:

Operator	Meaning	Notes
<->	biconditional (IFF)	left-associative
->	implication	right-associative
`\	`	OR
^	XOR
&	AND
~ / !	NOT	prefix, binds tightest

Right-associativity for -> matters: P -> Q -> R means P -> (Q -> R), not (P -> Q) -> R. These two give different truth tables.

Step 3: A recursive descent parser

Each precedence level becomes one method that calls the next-tighter level:

WORDS = {"NOT": "~", "AND": "&", "OR": "|", "XOR": "^"}

class Parser:
    def __init__(self, tokens):
        self.toks = [WORDS.get(t.upper(), t) for t in tokens]
        self.i = 0

    def peek(self):
        return self.toks[self.i] if self.i < len(self.toks) else None

    def eat(self, tok=None):
        t = self.peek()
        if t is None or (tok and t != tok):
            raise ValueError(f"Expected {tok!r}, got {t!r}")
        self.i += 1
        return t

    def parse(self):
        node = self.iff()
        if self.peek() is not None:
            raise ValueError(f"Unexpected token {self.peek()!r}")
        return node

    def iff(self):
        left = self.implies()
        while self.peek() == "<->":
            self.eat()
            left = ("iff", left, self.implies())
        return left

    def implies(self):
        left = self.or_()
        if self.peek() == "->":              # right-associative
            self.eat()
            return ("imp", left, self.implies())
        return left

    def or_(self):
        left = self.xor()
        while self.peek() == "|":
            self.eat()
            left = ("or", left, self.xor())
        return left

    def xor(self):
        left = self.and_()
        while self.peek() == "^":
            self.eat()
            left = ("xor", left, self.and_())
        return left

    def and_(self):
        left = self.not_()
        while self.peek() == "&":
            self.eat()
            left = ("and", left, self.not_())
        return left

    def not_(self):
        if self.peek() in ("~", "!"):
            self.eat()
            return ("not", self.not_())
        return self.atom()

    def atom(self):
        t = self.peek()
        if t == "(":
            self.eat("(")
            node = self.iff()
            self.eat(")")
            return node
        if t and re.match(r"[A-Za-z_]\w*$", t):
            self.eat()
            return ("var", t)
        raise ValueError(f"Unexpected token {t!r}")

The result is a nested tuple tree, e.g. ("imp", ("var", "P"), ("var", "Q")).

Step 4: Evaluate every row

from itertools import product

def evaluate(node, env):
    op = node[0]
    if op == "var": return env[node[1]]
    if op == "not": return not evaluate(node[1], env)
    a, b = evaluate(node[1], env), evaluate(node[2], env)
    return {"and": a and b, "or": a or b, "xor": a != b,
            "imp": (not a) or b, "iff": a == b}[op]

def variables(node, acc=None):
    acc = acc if acc is not None else []
    if node[0] == "var":
        if node[1] not in acc: acc.append(node[1])
    else:
        for child in node[1:]: variables(child, acc)
    return acc

def truth_table(expr):
    tree = Parser(tokenize(expr)).parse()
    names = sorted(variables(tree))
    rows = []
    for values in product([True, False], repeat=len(names)):
        env = dict(zip(names, values))
        rows.append((values, evaluate(tree, env)))
    return names, rows

def classify(rows):
    results = {r for _, r in rows}
    if results == {True}:  return "tautology"
    if results == {False}: return "contradiction"
    return "contingent"

itertools.product([True, False], repeat=n) gives the standard top-down truth table ordering (all T first).

Try it

def show(expr):
    names, rows = truth_table(expr)
    print(expr, "->", classify(rows))
    print(" ".join(names), "|", "result")
    for vals, res in rows:
        print(" ".join("T" if v else "F" for v in vals), "|", "T" if res else "F")

show("P -> Q")

P -> Q -> contingent
P Q | result
T T | T
T F | F
F T | T
F F | T

Now De Morgan's law, which should be a tautology:

show("~(A & B) <-> (~A | ~B)")
# -> tautology  (all four rows are T)

A contradiction:

show("A & ~A")
# -> contradiction

Checking that the precedence matches the table above:

show("P -> Q -> R")
# False only when P=T, Q=T, R=F, which matches P -> (Q -> R)

Edge cases and improvements

• Performance: rows grow as 2ⁿ. Ten variables is 1,024 rows, which is fine. Twenty is over a million, so for large inputs use a SAT solver instead of brute force.
• Better errors: report the character position of a syntax error and highlight it in the UI.
• Unicode operators: accept ∧ ∨ ¬ → ↔ ⊕ by adding them to the tokenizer and mapping them to the same internal symbols.
• Sub-expression columns: textbooks show intermediate columns (A & B, then ~(A & B)). You can add these by evaluating each subtree separately and labeling it.
• Equivalence checking: two expressions are equivalent if expr1 <-> expr2 is a tautology.
• Tests: property-based testing works well here. Generate random expressions and check that De Morgan-transformed versions produce identical tables.

Skip the code

If you just want a table, I built a free web version: Truth Table Generator.

[Describe what it does: supported operators, whether it shows sub-expression columns, tautology detection, max variables, and so on.]

This is my own project, so bug reports are welcome, especially expressions it gets wrong.

Your turn

What's the nastiest expression you'd throw at a truth table generator? Drop it in the comments and I'll run it through and post the result.