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'}")