Skip to content
Tutorials Center
My learning

Topics

Lesson 25 of 46 Β· Logic and Knowledge Representation

First-Order Logic and Knowledge Bases

Move beyond propositional logic: objects, predicates and quantifiers, unification, lifted inference, a Prolog-style rule engine in Python, semantic nets and the limits of logic.

Propositional logic cannot say "every square next to a pit is breezy" without writing one sentence per square. It has no way to talk about things and their properties. First-order logic (FOL, also called predicate logic) adds exactly that: objects, relations between them, and the quantifiers "for all" and "there exists". With these, one short sentence can replace thousands of propositional ones, and a knowledge base can describe families, maps, software configurations or medical facts in a way that reads almost like natural language.

In this lesson you will learn the syntax and meaning of FOL, how to translate English into it without the classic mistakes, and the key algorithm that makes reasoning with variables possible: unification. Then you will build a tiny Prolog-style engine in Python that answers questions about a family tree. We finish with semantic networks, which organize knowledge as an is-a hierarchy, and with an honest look at what logic cannot do.

Objects, predicates and quantifiers

FOL sentences are built from these parts.

  • Constants name particular objects: tom, paris, zero.
  • Variables stand for any object: x, y. (In the code below, variables start with a capital letter, as in Prolog.)
  • Functions map objects to objects: mother(x), plus(x, y). A function call is a term, not a sentence.
  • Predicates express properties and relations and give true or false: Student(x), Parent(x, y).
  • Connectives are the ones you know: Β¬, ∧, ∨, β†’, ↔.
  • Quantifiers: βˆ€x P(x) ("for all x") and βˆƒx P(x) ("there exists an x").

Some translations:

English First-order logic
Tom is a parent of Bob Parent(tom, bob)
Every student is smart βˆ€x (Student(x) β†’ Smart(x))
Some student is smart βˆƒx (Student(x) ∧ Smart(x))
Nobody likes everyone Β¬βˆƒx βˆ€y Likes(x, y)
A grandparent is a parent of a parent βˆ€x βˆ€z (Grandparent(x, z) ↔ βˆƒy (Parent(x, y) ∧ Parent(y, z)))

Two patterns cause most translation errors, so memorize them.

  1. βˆ€ goes with β†’. "All students are smart" is βˆ€x (Student(x) β†’ Smart(x)). Writing βˆ€x (Student(x) ∧ Smart(x)) says everything is a smart student, which is far too strong.
  2. βˆƒ goes with ∧. "Some student is smart" is βˆƒx (Student(x) ∧ Smart(x)). Writing βˆƒx (Student(x) β†’ Smart(x)) is true as soon as there is anything that is not a student, because then the implication holds trivially.

The order of quantifiers matters as well. βˆ€y βˆƒx Likes(y, x) says everyone likes somebody (possibly different people). βˆƒx βˆ€y Likes(y, x) says there is one person that everybody likes. The second is much stronger.

Meaning: models with objects

A model of propositional logic assigns true or false to symbols. A model of FOL is richer: it has a domain (a set of objects), says which object each constant names, and for each predicate lists the tuples of objects for which it is true. Over a finite domain you can evaluate quantifiers directly: βˆ€ becomes all(...) and βˆƒ becomes any(...).

Python Quantifiers evaluated in a small finite world

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In world A every student is smart, so the correct universal sentence is true, but the "common mistake" version is false, because di is not a student. In world B no student is smart, so the correct existential sentence is false while the mistaken version is still true (thanks to di, who is not a student). Finally, everyone likes somebody, but no single person is liked by everyone: the quantifier order changed the truth value.

Real FOL domains are often infinite (the integers, all strings), and there you cannot loop over the objects. Inference has to work symbolically, which brings us to unification.

Unification

Suppose the KB contains the rule βˆ€x βˆ€y (Parent(x, y) ∧ Parent(y, z)) β†’ Grandparent(x, z) and the facts Parent(tom, bob) and Parent(bob, ann). To use the rule we must find values for the variables that make the premises match the facts. Unification finds the most general substitution that makes two expressions identical.

  • Knows(john, X) and Knows(john, jane) unify with {X = jane}.
  • Knows(john, X) and Knows(Y, mary) unify with {Y = john, X = mary}.
  • Knows(john, X) and Knows(X, mary) do not unify, but only because both use the same variable name X by accident. This is why rules are standardized apart: every time a rule is used, its variables are renamed to fresh ones.
  • P(X) and P(f(X)) do not unify: that would make X = f(X), an infinite term. The occurs check rejects this.
Python Unification with an occurs check

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the fourth line: unification handles nested terms and substitutions that depend on each other. It finds Y = john and then X = mother(john). The fifth fails because X would have to be both a and b.

Lifted inference

Propositional inference needs every instance of a rule written out. Lifted inference works with the rule directly. Its core step is generalized modus ponens: from a rule p1 ∧ p2 ∧ ... β†’ q and facts that unify with each premise under a substitution ΞΈ, conclude q with ΞΈ applied. Forward chaining and backward chaining both lift this way, and so does resolution (with extra steps such as removing βˆƒ by introducing new constants or Skolem functions). A famous result, Herbrand's theorem, links FOL proofs back to propositional ones over ground instances.

For definite clauses (Horn clauses with variables), backward chaining with unification is the engine of Prolog, which writes our family rule as:

TEXT
grandparent(X, Z) :- parent(X, Y), parent(Y, Z).
parent(tom, bob).
parent(bob, ann).
?- grandparent(tom, Who).
Who = ann.

A Prolog program is a list of facts and rules (Horn clauses). The query is a goal. The system tries clauses top to bottom, unifies the goal with the head of each clause, replaces the goal by the clause's body, and backtracks on failure.

graph TD
    G["grandparent(tom, Z)"] --> R["parent(tom, Y), parent(Y, Z)"]
    R -- "Y = bob" --> P1["parent(bob, Z)"]
    R -- "Y = liz" --> P2["parent(liz, Z)"]
    P1 -- "Z = ann" --> S1["success: ann"]
    P1 -- "Z = pat" --> S2["success: pat"]
    P2 --> F["fail: liz has no children"]

The search tree for one query. Each branch is a different unification; failed branches are abandoned.

A Prolog-style engine in Python

The engine below is about thirty lines on top of unify. Terms are tuples; variables begin with a capital letter. A knowledge base entry is (head, body), where a fact has an empty body. solve is a generator: it yields every substitution that proves all the goals, trying clauses in order and renaming each clause's variables to fresh ones first (standardizing apart). The built-in different lets us say that a person is not their own sibling.

Python A tiny Prolog in Python: the family tree

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The answers are what you would expect: Tom's grandchildren are Ann and Pat, the ancestors of Jim are Pat, Tom and Bob, and Ann has one sibling, Pat. The sister query finds three pairs: Bob is a brother of Liz, so Liz counts as Bob's sister; Ann and Pat are sisters of each other. The last two queries return False because no clause proves them. Notice what "False" means here: the engine could not prove it, which Prolog treats as false (the closed-world assumption). It does not mean the opposite was proved.

The clause counts give a feel for the cost: every goal tries every clause in the knowledge base. Real Prolog systems index clauses by predicate and first argument to avoid that. Note also that the recursive ancestor rule puts parent before the recursive call. Written the other way around (ancestor(X, Z) :- ancestor(Y, Z), parent(X, Y)), this depth-first strategy would recurse forever, which is a classic Prolog trap.

Semantic networks and ontologies

Logic is not the only way to organize knowledge. A semantic network draws concepts as nodes, with links such as is-a (a penguin is a bird) between them, and properties stored on the most general node where they apply. Looking up a property means walking up the is-a chain until some node has a value, so a specific node can override a general default. The structure is just a labeled graph, and it is the ancestor of modern ontologies and knowledge graphs (OWL, RDF, schema.org vocabularies). Description logics, the formal basis of OWL, are carefully restricted fragments of FOL chosen so that reasoning stays decidable.

graph BT
    penguin["penguin<br/>flies = false"] -- "is-a" --> bird["bird<br/>flies = true, legs = 2"]
    bird -- "is-a" --> animal["animal<br/>alive = true"]
    fish["fish<br/>swims = true"] -- "is-a" --> animal
    pingu["pingu"] -- "is-a" --> penguin
    tweety["tweety"] -- "is-a" --> bird

Property lookup climbs the arrows. Pingu inherits "bird" facts but the "penguin" node overrides flies.

Python Inheritance with exceptions in a semantic net

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Tweety inherits flies = True from bird. Pingu finds flies = False at penguin first, so the exception wins, while legs = 2 still comes from bird. Nemo's flying ability is simply unknown: the net has no value anywhere along its chain.

This is default reasoning, and notice that it is not classical logic: adding the fact "Pingu is a penguin" made us retract the conclusion that Pingu flies. In FOL, adding facts can never remove conclusions (the logic is monotonic). To keep βˆ€x (Bird(x) β†’ Flies(x)) true you would have to list every exception in the rule, or switch to a nonmonotonic formalism.

The limits of logic

First-order logic is a magnificent tool, but a good AI engineer knows where it stops.

  • Undecidability. FOL entailment is only semi-decidable. A complete proof procedure exists (GΓΆdel's completeness theorem, resolution): if the KB entails the query, a proof will eventually be found. If it does not, the search may run forever, and no algorithm can always tell you. Richer logics lose even completeness (GΓΆdel's incompleteness theorem for arithmetic).
  • Uncertainty. Logic says true or false. "The patient probably has flu" has no place in it, which is why the Probabilistic Reasoning chapter follows.
  • Commonsense is full of exceptions. "Birds fly" needs the exception for penguins, ostriches, injured birds and birds in boxes. Listing all conditions of an action is the qualification problem, and saying what does not change when an action happens is the frame problem.
  • Brittleness and effort. Hand-written knowledge bases are expensive to build and fail when the world steps outside them, one reason learning methods took over in many areas.
  • Cost. Even with decidable fragments, inference can be exponential.

Logic's strengths remain real: precise semantics, explainable proofs, and sound conclusions. Many modern systems pair it with learning and probability, using logic for structure and constraints and statistics for noise.

Check your understanding

Quick check Β· 5 questions

of 5 answered You scored / 5 Β· perfect!

  1. 1. Which sentence correctly expresses 'every student is smart'?

    A universal statement about students is an implication from Student to Smart. The conjunction version claims that everything is a smart student.
  2. 2. What does the sentence βˆƒx βˆ€y Likes(y, x) mean?

    The existential quantifier comes first, so a single x must be liked by every y. Swapping the quantifiers gives the weaker 'everyone likes somebody'.
  3. 3. Why do the terms Knows(john, X) and Knows(X, mary) fail to unify, and what is the fix?

    Using the same variable name in both terms is an accident of naming. Renaming one of them to a fresh variable allows the unification {X = mary, Y = john}.
  4. 4. What does the occurs check prevent?

    X = f(X) would require an infinite term. The occurs check makes unification fail instead.
  5. 5. In the semantic-net demo, why does pingu not inherit flies = True from bird?

    Property lookup climbs the is-a chain from the most specific node, so the exception stored at penguin overrides the default stored at bird.

Summary

  • First-order logic adds objects, functions, predicates and the quantifiers βˆ€ and βˆƒ to propositional logic; βˆ€ pairs with β†’, βˆƒ pairs with ∧, and quantifier order matters.
  • Over a finite domain, quantifiers can be evaluated with all and any.
  • Unification finds the most general substitution that makes two terms equal; rules are standardized apart and the occurs check rejects infinite terms.
  • Lifted inference (generalized modus ponens, backward chaining with unification) is the engine of Prolog; we built one in Python.
  • Semantic nets store knowledge as an is-a graph with inheritance and overriding; they lead to ontologies and description logics.
  • FOL is semi-decidable, monotonic and bad at uncertainty and exceptions, which motivates planning, probability and learning.

Next: Classical Planning with STRIPS and PDDL.