Propositional logic

Intermediate

Introduction

Search finds actions; logic lets an agent reason about what is true. A knowledge-based agent stores facts and rules as sentences, such as "if it rains, the ground is wet", and derives new facts that must also be true. Propositional logic is the simplest such language. It is exact, so its conclusions are guaranteed, and it underlies hardware verification, planning systems and SAT solvers.

How it works

Syntax. Sentences are built from proposition symbols (Rain, Wet) with connectives:

ConnectiveWrittenTrue when
not~AA is false
andA & Bboth are true
orA | Bat least one is true
impliesA -> BA is false, or B is true
if and only ifA <-> BA and B have the same value

Precedence, from strongest: not, and, or, implies, if-and-only-if.

Semantics. A model gives every symbol a value. A sentence's value in a model follows from the table above. The truth table lists every model: with n symbols there are 2ⁿ rows.

A sentence is valid if it is true in every model (A | ~A), satisfiable if it is true in at least one, and unsatisfiable if in none (A & ~A).

Entailment. A knowledge base KB entails α, written KB ⊨ α, if α is true in every model where all of the KB is true. Then α follows from the KB: the agent can be certain of it. Model checking decides this directly: go through all models, and look for one where the KB is true and α false. If there is none, KB ⊨ α. Equivalently, KB ⊨ α if and only if KB & ~α is unsatisfiable.

Useful equivalences: A -> B is the same as ~A | B; ~(A & B) is ~A | ~B and ~(A | B) is ~A & ~B (De Morgan); A -> B is the same as ~B -> ~A (contraposition).

Example

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("Rain -> Wet"), parse("~Wet")]
query = parse("~Rain")
symbols = sorted(set().union(*(names(f) for f in kb + [query])))
print("Rain  Wet   KB    ~Rain")
entailed = True
for values in itertools.product([True, False], repeat=len(symbols)):
    model = dict(zip(symbols, values))
    kb_true = all(holds(f, model) for f in kb)
    q = holds(query, model)
    print("  ".join(f"{'T' if v else 'F':4}" for v in [*values, kb_true, q]))
    if kb_true and not q:
        entailed = False
print("KB entails ~Rain" if entailed else "KB does not entail ~Rain")
Open in compiler

Line by line

  1. parse turns text into a tree, with one function per precedence level, as in a compiler.
  2. holds evaluates a tree in a model; names collects the symbols.
  3. The knowledge base says: if it rains the ground is wet, and the ground is not wet.
  4. The table shows every model; the KB is true only in the last row, Rain false and Wet false.
  5. In that row ~Rain is true, so the KB entails that it is not raining: the rule called modus tollens.

Expected result

Rain  Wet   KB    ~Rain
T     T     F     F   
T     F     F     F   
F     T     F     T   
F     F     T     T   
KB entails ~Rain

In the real world

Chip makers prove that circuits behave correctly by turning the question into propositional logic and handing it to a SAT solver. Package managers such as those for Linux distributions use SAT solvers to choose versions that satisfy every dependency. Software verification tools, puzzle solvers and AI planners encode their problems the same way.

Common mistakes

  • Reading A -> B as "A causes B" or assuming it is false when A is false: it is true.
  • Mixing up precedence: A | B & C means A | (B & C).
  • Confusing entailment with satisfiability: a query true in some models of the KB is not entailed.
  • Forgetting that the number of models doubles with each symbol.

Best practices

  • Name symbols clearly (Rain, not R1) so the knowledge base is readable.
  • Use brackets when in doubt about precedence.
  • Check small knowledge bases with a truth table before trusting a faster method.

Summary

Propositional logic builds sentences from symbols and connectives, and a model gives each symbol a value. A sentence is valid, satisfiable or unsatisfiable depending on the models where it holds. KB ⊨ α if α holds in every model of the KB, which model checking tests by enumerating all models.

Quick check

1. When is A -> B false?
2. How many rows does a truth table with 4 symbols have?
3. What does KB ⊨ α mean?
4. Which sentence is valid?

Key takeaways

  • Implication A → B is false only when A is true and B is false.
  • KB ⊨ α can be decided by checking every model: 2ⁿ of them for n symbols.
  • KB ⊨ α exactly when KB ∧ ¬α is unsatisfiable.

Practice problems for this lesson

My notes

Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.