Simple Algorithm
Artificial Intelligence · Input Layer · 16 min

Knowledge, Logic & Reasoning

Representing what is known and deriving what follows.

Either the butler or the gardener did it; if it was the butler, the knife is in the pantry; the knife is not in the pantry. You can name the culprit without a single new clue. This topic is about machines that store knowledge as sentences and derive, with certainty, what follows.

What you’ll learn

  • Read and write simple sentences of propositional logic, including the slippery "if…then".
  • Decide entailment by checking models, and refute a bad argument with a countermodel.
  • Explain what sound and complete inference means, and follow a resolution proof.
  • Describe how first-order logic and knowledge graphs represent objects and relations.
  • Frame planning as search over states described by facts, with actions defined by preconditions and effects.

Knowledge as sentences

A knowledge base (KB) is a set of sentences, written in a formal language, that an agent takes to be true. You can tell it new facts and ask it questions, and its answers come from inference, not from looking anything up.

The simplest such language is propositional logic. Its atoms are statements that are either true or false, like Rain\text{Rain} or Wet\text{Wet}, and five connectives combine them:

SentenceRead asTrue when
¬A\neg Anot AAAA is false
A∧BA \land BAA and BBboth are true
A∨BA \lor BAA or BBat least one is true
A⇒BA \Rightarrow Bif AA then BBAA is false, or BB is true
A⇔BA \Leftrightarrow BAA if and only if BBboth have the same truth value
In the widgets you type these in ASCII: ~, &, |, -> and <->.
Check your understanding

When is the sentence Rain⇒Wet\text{Rain} \Rightarrow \text{Wet} false?

  1. When it is not raining
  2. When the ground is wet but it is not raining
  3. When it is raining and the ground is wet
  4. Only when it is raining and the ground is not wet
Show the answer

D. Only when it is raining and the ground is not wet

An implication promises something only when its premise holds. It is broken in exactly one case, Rain\text{Rain} true and Wet\text{Wet} false, and true in every other row, including both rows where it is not raining.

Entailment: true in every world

A model is one possible world: an assignment of true or false to every atom. A KB rules out every world in which one of its sentences is false. It entails a sentence α\alpha, written KB⊨α\text{KB} \models \alpha, if α\alpha is true in every world the KB leaves open.

So to refute a conclusion you need just one countermodel: a world where the KB holds and the conclusion fails. Try it on a tempting argument. "If it rains, the grass gets wet. If the sprinkler runs, the grass gets wet. The grass is wet. So it rained."

Check your understanding

A different KB says Rain⇒Wet\text{Rain} \Rightarrow \text{Wet} and ¬Wet\neg\text{Wet}. Does it entail ¬Rain\neg\text{Rain}?

  1. Yes: in every world where both sentences hold, it is not raining
  2. No: it might have rained and the ground dried
  3. No: the KB never mentions ¬Rain\neg\text{Rain}
  4. Only if we also know whether the sprinkler ran
Show the answer

A. Yes: in every world where both sentences hold, it is not raining

Of the four assignments to Rain\text{Rain} and Wet\text{Wet}, only one satisfies both sentences: both false. ¬Rain\neg\text{Rain} holds there, so it is entailed. This valid pattern is called modus tollens.

Proofs instead of tables

Checking every model always works, but the truth table doubles with every new atom.

Predict before you look

A truth table over 5 atoms has 25=322^5 = 32 rows. How many rows does a table over 10 atoms have?

Show the answer

1024 rows

Each new atom doubles the table, so 210=1,0242^{10} = 1{,}024 rows: 32 times as many as for 5 atoms, not twice as many. With 100 atoms there would be about 103010^{30} rows.

Instead, an inference procedure derives new sentences from old ones by rules, the way a mathematician writes a proof. Two properties matter. A procedure is sound if it derives only entailed sentences, and complete if it can derive every entailed sentence.

Proof by resolution is both, for propositional logic, and it needs just one rule: from A∨BA \lor B and ¬B∨C\neg B \lor C, conclude A∨CA \lor C. To prove a query, it adds the query's negation to the KB, rewrites everything as clauses (CNF), and resolves until it derives the empty clause, a contradiction. Here is the mystery from the start of the lesson.

Objects, relations and knowledge graphs

Propositional logic cannot say "every person has a mother" except by writing one sentence per person. First-order logic adds objects, relations and the quantifiers ∀\forall ("for all") and ∃\exists ("there exists"):

∀x  (Person(x)⇒∃y  MotherOf(y,x))\forall x\; \big(\text{Person}(x) \Rightarrow \exists y\; \text{MotherOf}(y, x)\big)
"For every xx, if xx is a person, then some yy is the mother of xx." One sentence covers every person, named or not.

Large systems often store simple facts as a knowledge graph: entities are nodes and relations are labeled edges, written as (subject, relation, object) triples. An ontology fixes the vocabulary and its hierarchy of categories, so a reasoner can draw conclusions nobody wrote down.

SubjectRelationObject
Marie Curieis aphysicist
physicistsubclass ofscientist
scientistsubclass ofperson
Marie CuriewonNobel Prize in Physics
Four triples. Following the "subclass of" edges, a reasoner concludes that Marie Curie is a scientist and a person.

Planning: reasoning about actions

An agent that knows facts can also reason about changing them. In automated planning a state is a set of facts, and each action has preconditions that must hold before it runs and effects that make facts true or false. This is the STRIPS representation, created in 1971 for Shakey, a mobile robot at SRI. Its descendant PDDL is the standard language of planning competitions.

ActionPreconditionsEffects
Go(a,b)\text{Go}(a, b)robot at aa; aa connects to bbrobot at bb, no longer at aa
Pick(o,a)\text{Pick}(o, a)robot at aa; oo at aa; hand emptyholding oo; oo no longer at aa; hand not empty
Drop(o,a)\text{Drop}(o, a)robot at aa; holding oooo at aa; hand empty; not holding oo
Three action schemas for a delivery robot. A plan is a sequence of actions whose preconditions hold in turn and whose effects make the goal true.

A planner then searches. It starts from the initial facts, applies any action whose preconditions hold, and looks for a sequence that reaches the goal. In the grid below, every cell is a state and every move is an action with one precondition: no wall in the way.

Logic meets learning

Logic offers guarantees: a sound reasoner's conclusions follow from its premises. But hand-built knowledge is brittle and expensive, which is part of why expert systems faded. Machine learning has the opposite profile: flexible and learned from data, but with no guarantee that its conclusions follow.

Neurosymbolic AI tries to get both. A language model might propose a proof for a proof checker to verify, or translate a word problem into logic for a solver. As of the mid-2020s, pairing learned models with formal verifiers is an active research area, especially in mathematics and programming.

Think first A language model writes a fluent, step-by-step argument. Does that make its conclusion entailed by its premises?

No. Fluency is not validity. Models are trained to produce likely text, and a plausible-looking step can be invalid or rest on a false premise (a hallucination). That is exactly why checking each step with a sound procedure is so attractive.

Hidden Layer lessonWhat you will do there
Propositional & First-Order LogicMaster syntax, semantics and entailment, then resolution, unification and the limits of what any reasoner can decide.
Knowledge Representation & GraphsBuild ontologies and knowledge graphs, and see why common sense is so hard to encode.
Automated PlanningWrite problems in STRIPS and PDDL, see why planning is computationally hard, and meet the heuristics that make planners fast.
Neurosymbolic AI & Reasoning ModelsCombine learning with structured reasoning: program synthesis, differentiable logic and reasoning in language models.
In the Hidden Layer, each idea from this lesson gets its formal machinery.

Key takeaways

  • A knowledge-based agent stores sentences in a formal language and answers questions by inference, not lookup.
  • KB⊨α\text{KB} \models \alpha means α\alpha is true in every model of the KB. A single countermodel is enough to refute an argument.
  • Truth tables grow as 2n2^n. Sound and complete procedures such as resolution prove a query by deriving a contradiction from its negation.
  • First-order logic adds objects, relations and quantifiers; knowledge graphs store facts as triples. Common sense remains hard to write down.
  • Planning is search over states made of facts, with actions defined by preconditions and effects. Neurosymbolic AI pairs such reasoning with learning.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

What does KB⊨α\text{KB} \models \alpha mean?

  1. α\alpha is one of the sentences written in the KB
  2. α\alpha is true in every model in which the KB is true
  3. α\alpha is true in at least one model of the KB
  4. The KB is true in every model in which α\alpha is true
Show the answer

B. α\alpha is true in every model in which the KB is true

Entailment means the KB leaves no possible world in which α\alpha is false.

Question 2

An inference procedure derives only sentences that the KB entails, but it misses some entailed ones. It is…

  1. complete but not sound
  2. both sound and complete
  3. neither sound nor complete
  4. sound but not complete
Show the answer

D. sound but not complete

Sound: everything derived is entailed, so no false conclusions. Complete: everything entailed can be derived, so nothing is missed. This procedure has only the first property.

Question 3

A KB contains Fire⇒Smoke\text{Fire} \Rightarrow \text{Smoke} and Smoke\text{Smoke}. Which statement is true?

  1. Fire\text{Fire} is not entailed: there is a model with smoke and no fire
  2. Fire\text{Fire} is entailed, by modus ponens
  3. ¬Fire\neg\text{Fire} is entailed
  4. The KB contradicts itself
Show the answer

A. Fire\text{Fire} is not entailed: there is a model with smoke and no fire

The world with Smoke\text{Smoke} true and Fire\text{Fire} false satisfies both sentences, so it is a countermodel: the smoke may have another cause.

Question 4

Why does "every person has a mother" call for first-order logic?

  1. Propositional logic cannot express "and"
  2. Family relations are uncertain, so it needs probability
  3. Propositional logic has no variables or quantifiers, so it would need a separate sentence for every person
  4. Knowledge graphs cannot store family relations
Show the answer

C. Propositional logic has no variables or quantifiers, so it would need a separate sentence for every person

"Every person" ranges over all objects, including ones not yet named. First-order logic's ∀x\forall x says it once; propositional logic would need one atom per person.

Question 5

How does STRIPS describe an action?

  1. By the reward for taking it
  2. By preconditions that must hold before it, and effects that make facts true or false
  3. By a table of probabilities for each possible outcome
  4. By a neural network that predicts the next state
Show the answer

B. By preconditions that must hold before it, and effects that make facts true or false

A STRIPS action applies only when its preconditions hold, and its effects list exactly which facts change. Everything else is assumed to stay the same, which sidesteps the frame problem of spelling out what an action does not change.

Go deeper

Further reading

  • S. Russell & P. Norvig, Artificial Intelligence: A Modern Approach, 4th ed. (Pearson, 2020), chapters 7–11.
  • J. A. Robinson, "A Machine-Oriented Logic Based on the Resolution Principle," Journal of the ACM 12(1) (1965), 23–41.