Decide what a knowledge base says about a question.
What to build
A program that decides whether a knowledge base entails a query, contradicts it, or neither.
Requirements
- Sentences use the syntax of the truth-table exercise. A model of the KB is a model of all the symbols (in the KB and the query) where every KB sentence is true.
- Print
models of KB: M, thenentailed(the query is true in all of them),contradicted(false in all),unknown(true in some, false in others), orinconsistent knowledge base(M = 0).
Input
Line 1: k. Then k sentences. Last line: the query.
Output
Two lines.
Constraints
At most 12 symbols in total.
Example
Input:
2
Rain -> Wet
~Wet
~Rain
Output:
models of KB: 1
entailed
Why it works
The query follows from the knowledge base exactly when no model of the knowledge base makes it false; if both kinds of model exist, the knowledge base cannot decide it.
Examples
Example 1 · Input
2 Rain -> Wet ~Wet ~Rain
Expected output
models of KB: 1 entailed
Example 2 · Input
2 Rain -> Wet Wet Rain
Expected output
models of KB: 2 unknown
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Collect the symbols of the knowledge base and the query, and go through every model.
Hint 2
Keep only the models where every sentence of the knowledge base is true, then look at the query in those.
Solution
Show one correct solution (try it yourself first)
import itertools
import re
def parse(text):
tokens = re.findall(r"<->|->|[~&|()]|[A-Za-z]\w*", text)
pos = 0
def peek():
return tokens[pos] if pos < len(tokens) else None
def take():
nonlocal 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()
return iff()
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]]
def names(node):
return {node} if isinstance(node, str) else set().union(*(names(child) for child in node[1:]))
kb = [parse(input()) for _ in range(int(input()))]
query = parse(input())
symbols = sorted(set().union(names(query), *(names(f) for f in kb)))
results = []
for values in itertools.product([True, False], repeat=len(symbols)):
model = dict(zip(symbols, values))
if all(holds(f, model) for f in kb):
results.append(holds(query, model))
print("models of KB:", len(results))
if not results:
print("inconsistent knowledge base")
elif all(results):
print("entailed")
elif not any(results):
print("contradicted")
else:
print("unknown")