Reasoning with a Knowledge Base in Pythonبیرکردنەوە بە بنکەیەکی زانین لە Pythonـدا

# minilogic.py - a tiny propositional-logic toolkit (CêIT, original code)
#
# A sentence is either
#   - a symbol: a name in a string, such as "rain", or
#   - a tuple that starts with a connective:
#       ("not", A)  ("and", A, B, ...)  ("or", A, B, ...)
#       ("implies", A, B)  ("iff", A, B)
from itertools import product


class MissingValueError(Exception):
    """A symbol has no True/False value in the model."""


def Not(a):
    return ("not", a)


def And(*parts):
    return ("and",) + parts


def Or(*parts):
    return ("or",) + parts


def Implies(a, b):
    return ("implies", a, b)


def Iff(a, b):
    return ("iff", a, b)

def is_true(s, model):
    """Is sentence s true in this model (a dict: symbol -> True/False)?"""
    if isinstance(s, str):
        if s not in model:
            raise MissingValueError(f"the model has no value for {s!r}")
        return model[s]
    op, *parts = s
    if op == "not":
        return not is_true(parts[0], model)
    if op == "and":
        return all(is_true(p, model) for p in parts)
    if op == "or":
        return any(is_true(p, model) for p in parts)
    if op == "implies":
        return (not is_true(parts[0], model)) or is_true(parts[1], model)
    if op == "iff":
        return is_true(parts[0], model) == is_true(parts[1], model)
    raise ValueError(f"unknown connective {op!r}")


def symbols(s):
    """The set of symbol names used in sentence s."""
    if isinstance(s, str):
        return {s}
    names = set()
    for p in s[1:]:
        names |= symbols(p)
    return names


SIGN = {"and": " ∧ ", "or": " ∨ ", "implies": " → ", "iff": " ↔ "}


def show(s):
    """Write sentence s with logic signs and brackets."""
    if isinstance(s, str):
        return s
    if s[0] == "not":
        inner = show(s[1])
        return "¬" + (inner if isinstance(s[1], str) else "(" + inner + ")")
    parts = []
    for p in s[1:]:
        text = show(p)
        parts.append(text if isinstance(p, str) or p[0] == "not" else "(" + text + ")")
    return SIGN[s[0]].join(parts)

from minilogic import Not, And, Or, Implies, is_true, symbols, show
from minilogic import MissingValueError

rain = "rain"
bus = "bus"
sentence = Implies(rain, bus)          # rain → bus

print(sentence)                        # how Python stores it
print(show(sentence))                  # how we write it
print(sorted(symbols(sentence)))       # the symbols it uses

model = {"rain": True, "bus": False}   # one possible world
print(is_true(sentence, model))
print(is_true(Or(rain, Not(bus)), model))
print(show(And(Not(rain), Or(rain, bus))))

try:
    is_true(sentence, {"rain": True})  # bus has no value
except MissingValueError as error:
    print("Error:", error)

def all_models(names):
    """Every way to give True/False to the names: 2 ** len(names) models."""
    names = sorted(names)
    for values in product([True, False], repeat=len(names)):
        yield dict(zip(names, values))


def entails(kb, query):
    """KB ⊨ query: is the query true in EVERY model where the KB is true?"""
    for model in all_models(symbols(kb) | symbols(query)):
        if is_true(kb, model) and not is_true(query, model):
            return False      # a counter-example: KB true, query false
    return True


def answer(kb, query):
    """'yes' if KB ⊨ query, 'no' if KB ⊨ ¬query, otherwise 'unknown'."""
    if entails(kb, query):
        return "yes"
    if entails(kb, Not(query)):
        return "no"
    return "unknown"


def exactly_one(names):
    """Exactly one of these symbols is true."""
    rules = [Or(*names)]                    # at least one of them
    for i, a in enumerate(names):
        for b in names[i + 1:]:
            rules.append(Not(And(a, b)))    # but never two together
    return And(*rules)

# Model checking with recursion: give one symbol a value at a time.
from minilogic import And, Implies, is_true, symbols


def entails_rec(kb, query, names, model):
    if not names:                     # every symbol has a value: one model
        if is_true(kb, model):
            return is_true(query, model)
        return True                   # KB false here: this model does not matter
    first, rest = names[0], names[1:]
    return (entails_rec(kb, query, rest, {**model, first: True}) and
            entails_rec(kb, query, rest, {**model, first: False}))


def entails(kb, query):
    names = sorted(symbols(kb) | symbols(query))
    return entails_rec(kb, query, names, {})


kb = And(Implies("snow", "road_closed"), Implies("road_closed", "home"))
print(entails(kb, Implies("snow", "home")))
print(entails(kb, "home"))

from minilogic import Not, And, Or, Implies, show, answer

ai_lab = "ai_lab"            # Shilan has the AI lab today
network_lab = "network_lab"  # Shilan has the networks lab today
lab_open = "lab_open"        # the computer lab is open
rain = "rain"                # it rains
bus = "bus"                  # Shilan takes the bus

kb = And(
    Or(ai_lab, network_lab),     # she has the AI lab or the networks lab
    Implies(ai_lab, lab_open),   # if she has the AI lab, the lab is open
    Not(lab_open),               # the computer lab is closed today
    Implies(rain, bus),          # if it rains, she takes the bus
)
print(show(kb))
for question in [network_lab, ai_lab, lab_open, rain, bus]:
    print(question, "->", answer(kb, question))

from minilogic import Not, Or, Implies, show, answer

kb = Or("ai_lab", "network_lab")
kb = Implies("ai_lab", "lab_open")
kb = Not("lab_open")
kb = Implies("rain", "bus")       # each line REPLACES the one before

print(show(kb))
print("network_lab ->", answer(kb, "network_lab"))

# Lost and found: who left something behind, where, and what was it?
from minilogic import Not, And, Implies, answer, exactly_one

people = ["aram", "dilan", "hana"]
rooms = ["lab", "library", "canteen"]
items = ["charger", "umbrella", "scarf"]

kb = And(
    exactly_one(people),            # one person left one thing
    exactly_one(rooms),             # in one room
    exactly_one(items),
    Not("hana"),                    # Hana was at home all day
    Not("library"),                 # the library was closed
    Implies("aram", "canteen"),     # Aram only went to the canteen
    Not("canteen"),                 # nothing was found in the canteen
    Not("umbrella"),                # the caretaker: "it was not an umbrella"
)

for name in people + rooms + items:
    print(f"{name:9} {answer(kb, name)}")

# Four students present their projects on four days. Who presents when?
import time
from minilogic import And, Or, entails, exactly_one

people = ["aram", "shilan", "karwan", "dilan"]
days = ["sun", "mon", "tue", "wed"]

rules = []
for person in people:                  # each student presents on exactly one day
    rules.append(exactly_one([f"{person}_{day}" for day in days]))
for day in days:                       # one student per day
    rules.append(exactly_one([f"{person}_{day}" for person in people]))

rules.append("karwan_wed")                       # Karwan presents on Wednesday
rules.append(Or("aram_tue", "aram_wed"))         # Aram: Tuesday or Wednesday
rules.append(Or("shilan_mon", "shilan_tue"))     # Shilan: Monday or Tuesday
kb = And(*rules)

start = time.perf_counter()
for person in people:
    for day in days:
        if entails(kb, f"{person}_{day}"):
            print(f"{person} presents on {day}")
print(f"16 questions, 2 ** 16 = {2 ** 16} models each,",
      f"{time.perf_counter() - start:.1f} seconds")

# Knights always tell the truth. Knaves always lie.
# The symbol "hana" means "Hana is a knight"; Not("hana") means she is a knave.
from minilogic import Not, And, Or, Iff, answer


def says(person, statement):
    # What a person says is true exactly when that person is a knight.
    return Iff(person, statement)


def solve(title, kb, people):
    print(title)
    for person in people:
        kind = {"yes": "knight", "no": "knave", "unknown": "unknown"}
        print(f"  {person}: {kind[answer(kb, person)]}")


# Puzzle 1
# Hana says: "Rezan is a knave."
# Rezan says: "Hana and I are the same kind."
kb1 = And(
    says("hana", Not("rezan")),
    says("rezan", Iff("hana", "rezan")),
)
solve("Puzzle 1", kb1, ["hana", "rezan"])

# Puzzle 2
# Aram says: "Shilan and Karwan are both knaves."
# Shilan says: "Aram is a knave."
# Karwan says: "At least one of Aram and Shilan is a knave."
kb2 = And(
    says("aram", And(Not("shilan"), Not("karwan"))),
    says("shilan", Not("aram")),
    says("karwan", Or(Not("aram"), Not("shilan"))),
)
solve("Puzzle 2", kb2, ["aram", "shilan", "karwan"])

from minilogic import Not, And, show, answer

# Mistake 1: Python's own `and` instead of the toolkit's And(...)
kb = "rain" and "bus"          # Python keeps only "bus"!
print(show(kb))

# Mistake 2: a knowledge base that contradicts itself
kb = And("rain", Not("rain"))
print(answer(kb, "snow"), answer(kb, Not("snow")))