Logic and Knowledge Representation

Most of this site is about learning from data - estimating quantities that are uncertain, and being careful about how uncertain they are. There is an older tradition in artificial intelligence that asks a different question: given what I already know, what must be true?

That is not a statistical question. It admits a definite answer, and the machinery for computing it is logic.

A. Knowledge bases, models, entailment

A knowledge base (KB) is a set of sentences asserted to be true about the world. A model is one complete assignment of truth values to every proposition - one possible world, fully specified. A sentence is true in some models and false in others, and we write $M(\alpha)$ for the set of models in which $\alpha$ is true.

The central relation is entailment:

$\text{KB} \models \alpha$ - read "KB entails $\alpha$" - means $\alpha$ is true in every model in which KB is true. Equivalently, $M(\text{KB}) \subseteq M(\alpha)$.

The idea is familiar from arithmetic, where $x = 0$ entails $xy = 0$: in any world where $x$ is zero, $xy$ is zero too, whatever $y$ happens to be.

Entailment is a fact about meaning, not about any algorithm. Russell & Norvig put the distinction memorably: think of the consequences of KB as a haystack and $\alpha$ as a needle. Entailment is the needle being in the haystack; inference is finding it.

B. Working an entailment out by hand

Take the standard setting. An agent is exploring a grid of caves, some containing pits. A square is breezy exactly when an adjacent square contains a pit. The agent starts at $[1,1]$, feels no breeze, moves to $[2,1]$, and feels a breeze.

Three squares are in question: $[1,2]$, $[2,2]$, and $[3,1]$. Each either holds a pit or does not, so there are $2^3 = 8$ possible worlds.

The KB says two things:

• No breeze at $[1,1]$. Its neighbours are $[1,2]$ and $[2,1]$, so neither holds a pit. In particular $[1,2]$ is pit-free.
• A breeze at $[2,1]$. Its neighbours are $[1,1]$, $[2,2]$ and $[3,1]$. The agent stood safely in $[1,1]$, so at least one of $[2,2]$, $[3,1]$ holds a pit.

Enumerate all eight and mark where the KB holds:

Exactly three models survive. Now test two candidate conclusions.

$\alpha_1$: "there is no pit in $[1,2]$." True in all three surviving models. So $\text{KB} \models \alpha_1$ - the agent may safely move there.

$\alpha_2$: "there is no pit in $[2,2]$." False in two of the three. So $\text{KB} \not\models \alpha_2$. Note carefully what this does not say: it does not establish that there is a pit in $[2,2]$ either, since one surviving model has none. The honest conclusion is that the evidence does not settle it.

This procedure - enumerate every model, check that $\alpha$ holds wherever KB does - is model checking, and it is a direct transcription of the definition of entailment.

All eight worlds are in the figure below, with the three that survive the knowledge base marked. Pick a conclusion and the table marks something more useful still: every surviving world in which that conclusion is false. For “no pit in [2,2]” there are two of them, and each one is a world entirely consistent with everything known - which is what “not entailed” means, and why asserting the opposite would be just as unsupported. Switch a sentence of the KB off and watch the surviving set grow.

C. Soundness, completeness, and cost

Once inference is a procedure rather than a definition, two properties matter. An algorithm is sound (or truth-preserving) if everything it derives is genuinely entailed: it never invents conclusions. It is complete if it can derive everything that is entailed: it never misses one.

Model checking is both. It is sound because it implements the definition directly, and complete because there are only finitely many models and it examines all of them.

The cost is the problem. With $n$ proposition symbols there are $2^n$ models, so the time complexity is $O(2^n)$ - the space complexity is only $O(n)$, since the enumeration can be done depth-first. Our three unknowns gave eight rows; thirty would give over a billion.

Nor is this merely a weakness of one naive algorithm. Deciding propositional entailment is co-NP-complete, so no known method avoids exponential behaviour in the worst case. Practical systems therefore use inference rules that derive conclusions syntactically rather than enumerating worlds - Modus Ponens and its relatives - which are dramatically faster on typical problems while remaining sound.

Below is one of those relatives at work: a resolution prover, with its working shown, on a smaller knowledge base than the one above. It holds the rule that $[1,1]$ is breezy exactly when $[1,2]$ or $[2,1]$ has a pit, $B_{1,1} \Leftrightarrow (P_{1,2} \lor P_{2,1})$, and the percept $\neg B_{1,1}$, with no percept at $[2,1]$. The clause list is that knowledge base converted to clauses, plus the negated query, and every line under it is a resolvent in the order the search produced it. Ask for "no pit at [1,2]" and the empty box appears; ask for "a pit at [1,2]" and the search saturates without it, which is an answer rather than a failure. Each query is also decided a second time by enumerating the eight worlds, with no code shared between the two, and the figure reports whether they agree.

D. Where propositional logic runs out

Everything above used propositions: atomic facts that are simply true or false. That is a genuine limitation, and it shows up as soon as you try to say something general.

To express "all squares adjacent to a pit are breezy" propositionally, you must write one sentence per square, and rewrite them all if the grid changes size. The rule itself - the thing you actually know - cannot be stated. Russell & Norvig's verdict is blunt: propositional logic is too puny a language to represent knowledge of complex environments concisely.

The difference is one of ontological commitment - what a language assumes about the nature of reality:

First-order logic assumes the world contains objects with relations between them. That buys quantifiers - $\forall$ ("for all") and $\exists$ ("there exists") - and with them, generality. The breeze rule becomes a single sentence quantified over all squares, true regardless of how large the grid is.

Inference lifts accordingly. Generalized Modus Ponens applies the familiar rule to sentences containing variables by first finding a substitution $\theta$ that makes the premises match - a process called unification - and then applying $\theta$ to the conclusion. Reasoning that had to be repeated per object is done once, schematically.

That is an algorithm, so the figure below runs it: argument by argument, with each binding recorded as it is made, and both terms printed with the unifier applied so that "identical" can be read rather than asserted. Two failing pairs sit beside it. The occurs check is the one worth pressing - unifying x with Mother(x) has no solution, and an implementation that omits the check builds an infinite term instead of saying so.

E. Why this still matters

It would be easy to file this as history. That would be a mistake, for three reasons.

Some knowledge is not statistical. Constraints, rules, definitions, and policies are naturally stated as sentences that hold or fail, and learning them from examples when you could simply write them down is wasteful and unreliable.

Logical conclusions come with guarantees. A sound inference procedure never returns a wrong answer, and it can show its work as a chain of applied rules. A learned model offers a probability and, usually, no derivation. Where correctness must be certified rather than estimated, that difference is decisive.

The representational question did not go away. How to encode what a system knows so that it can be combined and reasoned over is the same question whether the contents are hand-written axioms or extracted from a corpus. Ontologies, knowledge graphs, typed schemas, and constraint solvers are all descendants of this line of work.

The realistic position is that the two traditions answer different questions. Learning handles perception and uncertainty; logic handles structure and guaranteed consequence. Systems that need both tend to end up with both.

Key takeaways

• A knowledge base is asserted sentences; a model is one fully specified possible world.
• $\text{KB} \models \alpha$ means $\alpha$ holds in every model where KB holds - $M(\text{KB}) \subseteq M(\alpha)$.
• Entailment is a semantic fact; inference is the search for it - needle and haystack.
• In the worked example, 8 possible worlds reduced to 3 consistent with the percepts, entailing "no pit in $[1,2]$" but leaving $[2,2]$ genuinely undetermined.
• Failing to entail $\alpha$ is not entailing $\neg\alpha$.
• Sound means never wrong; complete means never missing. Model checking is both, at $O(2^n)$ time and $O(n)$ space.
• Propositional entailment is co-NP-complete, so worst-case exponential cost is intrinsic, not an artefact of a naive algorithm.
• Propositional logic cannot state general rules; first-order logic commits to objects and relations, gaining quantifiers and lifted inference.

What's next

For the probabilistic counterpart - reasoning when facts are not simply true or false but hold with some degree of belief - see Bayes' Theorem and Belief Updating, and for the decision-making layer built on top of it, Markov Decision Processes.