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:
| Connective | Written | True when |
|---|---|---|
| not | ~A | A is false |
| and | A & B | both are true |
| or | A | B | at least one is true |
| implies | A -> B | A is false, or B is true |
| if and only if | A <-> B | A 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")Line by line
parseturns text into a tree, with one function per precedence level, as in a compiler.holdsevaluates a tree in a model;namescollects the symbols.- The knowledge base says: if it rains the ground is wet, and the ground is not wet.
- The table shows every model; the KB is true only in the last row, Rain false and Wet false.
- 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
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.