AI: Decide entailment by model checking

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, then entailed (the query is true in all of them), contradicted (false in all), unknown (true in some, false in others), or inconsistent 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")

Lesson: Propositional logic →