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 or , and five connectives combine them:
| Sentence | Read as | True when |
|---|---|---|
| not | is false | |
| and | both are true | |
| or | at least one is true | |
| if then | is false, or is true | |
| if and only if | both have the same truth value |
~, &, |, -> and <->.When is the sentence false?
- When it is not raining
- When the ground is wet but it is not raining
- When it is raining and the ground is wet
- 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, true and 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 , written , if 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."
A different KB says and . Does it entail ?
- Yes: in every world where both sentences hold, it is not raining
- No: it might have rained and the ground dried
- No: the KB never mentions
- 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 and , only one satisfies both sentences: both false. 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.
A truth table over 5 atoms has rows. How many rows does a table over 10 atoms have?
Show the answer
1024 rows
Each new atom doubles the table, so rows: 32 times as many as for 5 atoms, not twice as many. With 100 atoms there would be about 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 and , conclude . 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 ("for all") and ("there exists"):
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.
| Subject | Relation | Object |
|---|---|---|
| Marie Curie | is a | physicist |
| physicist | subclass of | scientist |
| scientist | subclass of | person |
| Marie Curie | won | Nobel Prize in Physics |
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.
| Action | Preconditions | Effects |
|---|---|---|
| robot at ; connects to | robot at , no longer at | |
| robot at ; at ; hand empty | holding ; no longer at ; hand not empty | |
| robot at ; holding | at ; hand empty; not holding |
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 lesson | What you will do there |
|---|---|
| Propositional & First-Order Logic | Master syntax, semantics and entailment, then resolution, unification and the limits of what any reasoner can decide. |
| Knowledge Representation & Graphs | Build ontologies and knowledge graphs, and see why common sense is so hard to encode. |
| Automated Planning | Write problems in STRIPS and PDDL, see why planning is computationally hard, and meet the heuristics that make planners fast. |
| Neurosymbolic AI & Reasoning Models | Combine learning with structured reasoning: program synthesis, differentiable logic and reasoning in language models. |
Key takeaways
- A knowledge-based agent stores sentences in a formal language and answers questions by inference, not lookup.
- means is true in every model of the KB. A single countermodel is enough to refute an argument.
- Truth tables grow as . 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.
What does mean?
- is one of the sentences written in the KB
- is true in every model in which the KB is true
- is true in at least one model of the KB
- The KB is true in every model in which is true
Show the answer
B. is true in every model in which the KB is true
Entailment means the KB leaves no possible world in which is false.
An inference procedure derives only sentences that the KB entails, but it misses some entailed ones. It is…
- complete but not sound
- both sound and complete
- neither sound nor complete
- 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.
A KB contains and . Which statement is true?
- is not entailed: there is a model with smoke and no fire
- is entailed, by modus ponens
- is entailed
- The KB contradicts itself
Show the answer
A. is not entailed: there is a model with smoke and no fire
The world with true and false satisfies both sentences, so it is a countermodel: the smoke may have another cause.
Why does "every person has a mother" call for first-order logic?
- Propositional logic cannot express "and"
- Family relations are uncertain, so it needs probability
- Propositional logic has no variables or quantifiers, so it would need a separate sentence for every person
- 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 says it once; propositional logic would need one atom per person.
How does STRIPS describe an action?
- By the reward for taking it
- By preconditions that must hold before it, and effects that make facts true or false
- By a table of probabilities for each possible outcome
- 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
- Propositional & First-Order Logic · Syntax, semantics, entailment and inference.
- Knowledge Representation & Graphs · Ontologies, semantic networks and knowledge graphs.
- Automated Planning · STRIPS, PDDL and searching over actions.
- Neurosymbolic AI & Reasoning Models · Combining learning with structured reasoning.
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.