AI: Print a truth table

Evaluate a sentence in every model.

What to build

A program that prints the truth table of a propositional sentence.

Requirements

  • Connectives: ~ (not), & (and), | (or), -> (implies, grouping from the right), <-> (if and only if); brackets allowed. Precedence from strongest: ~, &, |, ->, <->. Symbols are words starting with a letter.
  • List the symbols in alphabetical order and the models from all true to all false (T before F in each position). Print each row as A=T B=F : T.

Input

One line: the sentence.

Output

One row per model.

Constraints

At most 5 symbols.

Example

Input:

A & B

Output:

A=T B=T : T
A=T B=F : F
A=F B=T : F
A=F B=F : F

Why it works

A sentence's value is decided entirely by its symbols' values, so listing every model shows exactly when it is true.

Examples

Example 1 · Input
A & B
Expected output
A=T B=T : T
A=T B=F : F
A=F B=T : F
A=F B=F : F
Example 2 · Input
A -> B
Expected output
A=T B=T : T
A=T B=F : F
A=F B=T : T
A=F B=F : T

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Parse with one function per precedence level: <->, then ->, then |, then &, then ~ and brackets.

Hint 2

Use itertools.product([True, False], repeat=n) to list the models from all true to all false.

Solution

Show one correct solution (try it yourself first)
import itertools
import re

tokens = re.findall(r"<->|->|[~&|()]|[A-Za-z]\w*", input())
pos = 0


def peek():
    return tokens[pos] if pos < len(tokens) else None


def take():
    global pos
    pos += 1
    return tokens[pos - 1]


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


def implies():
    left = disjunction()
    if peek() == "->":
        take()
        return ("->", left, implies())
    return left


def disjunction():
    left = conjunction()
    while peek() == "|":
        take()
        left = ("|", left, conjunction())
    return left


def conjunction():
    left = negation()
    while peek() == "&":
        take()
        left = ("&", left, negation())
    return left


def negation():
    if peek() == "~":
        take()
        return ("~", negation())
    if peek() == "(":
        take()
        inner = iff()
        take()
        return inner
    return take()


def holds(node, model):
    if isinstance(node, str):
        return model[node]
    if node[0] == "~":
        return not holds(node[1], model)
    a, b = holds(node[1], model), holds(node[2], model)
    return {"&": a and b, "|": a or b, "->": (not a) or b, "<->": a == b}[node[0]]


tree = iff()
names = sorted({t for t in tokens if t[0].isalpha()})
for values in itertools.product([True, False], repeat=len(names)):
    model = dict(zip(names, values))
    cells = " ".join(f"{n}={'T' if model[n] else 'F'}" for n in names)
    print(f"{cells} : {'T' if holds(tree, model) else 'F'}")

Lesson: Propositional logic →