4.14 Logical agents and propositional logic

What this is and why it exists

The semantic networks in this module are pictures of relationships, and they work because a reader supplies the meaning. Logic is what happens when you stop relying on the reader. Sentences have a defined meaning, an inference procedure derives new sentences mechanically, and you can state precisely what the procedure is guaranteed to get right and what it might miss. That precision is the point. It is also the reason the same architecture appears at the end of this module wearing a different name: an expert system is a knowledge base and an inference engine, and this is where both terms are defined.

The vocabulary

• Knowledge base — the set of sentences currently believed.
• Sentence — a statement in the logic, either true or false in a world.
• Model — one complete assignment of true and false to the symbols.
• Entailment — every model of the knowledge is a model of the conclusion.
• Inference procedure — a mechanical way of deriving new sentences.
• Sound — everything it derives is genuinely entailed.
• Complete — everything entailed can be derived.
• Literal — a symbol, or its negation.
• Clause — a group of literals joined by or.
• Conjunctive normal form — a set of clauses, all of which must hold.
• Resolution — the single rule that combines two clauses.

The mental model

Keep what is known apart from the reasoning over it. One part holds sentences; another part derives consequences. That separation is unremarkable until you notice what it buys: the same facts can be read by a different procedure, and the same procedure can be pointed at a different domain. Nothing else in this module reuses its parts that cleanly, and it is the reason a rule-based system built this way can be given new rules rather than new code.

Entailment is about meaning, not about proof. A knowledge base entails a sentence when every world in which the knowledge holds is a world in which the sentence holds. Notice what is not in that definition: no algorithm, no derivation, no procedure. It is a relation between what the sentences mean. Three words get confused here and are worth separating. Implication is a connective that appears inside a single sentence. Entailment is a relation between a set of sentences and one more. Provability is what a particular procedure can actually reach, and it is the only one of the three that depends on which procedure you chose.

The baseline method is to enumerate every world. List all assignments of true and false to the symbols, keep the rows where every sentence in the knowledge base holds, and check whether the conclusion holds in all of them. It is correct, it needs no cleverness, and it costs two to the power of the number of symbols. Every faster method is measured against it, and its cost is the honest reason the faster methods exist.

Resolution reduces all of logic to one rule, at the price of rewriting everything first. Convert every sentence to conjunctive normal form — a collection of clauses, each a set of literals joined by or, all of which must hold. The conversion is mechanical: rewrite implications, push negations inwards, distribute. Then a single rule does everything: if one clause contains a symbol and another contains its negation, the two combine into a new clause holding everything else from both. Resolution is complete for propositional logic, which is what makes the conversion worth doing — one rule, and nothing entailed can escape it.

It works by refutation, which surprises people the first time. To prove a sentence, add its negation to the knowledge base and derive a contradiction. If assuming the opposite is impossible, the sentence follows. Working backwards from an impossibility is what lets one rule cover a whole logic instead of needing a rule for each connective.

Soundness and completeness are the two promises, and an agent needs both. Sound means nothing false is ever derived. Complete means nothing true is ever missed. They fail in different directions and both failures are real. An unsound agent acts on conclusions that do not follow, which is how a system confidently does the wrong thing. An incomplete agent fails to work out something it had every fact needed to work out, which is how an agent walks into a hazard it could have proved was there.

The Wumpus world is the smallest example where this earns its keep. An agent moves on a small grid. Some squares hold pits and one holds a hazard; adjacent squares smell or feel draughty. The agent never sees the grid — it sees only what it senses where it stands. From a breeze in one square and no breeze in another, it can prove that a particular square is safe, and prove that another one is not. That is deduction doing something pattern matching cannot: the conclusion is about squares the agent has never visited, and it is certain rather than likely.

What you should now be able to explain or do

Separate a knowledge base from the inference procedure, and say what the separation buys. Define entailment and distinguish it from implication and from provability. Decide entailment by enumerating models, and state the cost. Convert sentences to conjunctive normal form and apply resolution, including the refutation step. State soundness and completeness, and describe the different damage each failure does. Work a Wumpus world square by square and prove which cells are safe.

Check yourself