Skip to content
learn
  1. Learn
  2. Artificial Intelligence
  3. Knowledge, Logic and Planning

AI AI-02.03

First-order logic

Objects, relations and quantifiers; unification; forward and backward chaining; and a tiny Prolog-style reasoner in Python.

Intermediate 14 min Last reviewed

The big idea

Propositional logic treats every statement as an indivisible symbol. "Alice is Bob's parent" is one proposition, "Bob is Carol's parent" another, and "Alice is Carol's grandparent" a third, with no visible connection between them. To say "anyone's parent's parent is their grandparent" you would need a separate rule for every pair of people. With a thousand people, that is a million rules, and adding one person means writing a thousand more.

First-order logicA logic whose sentences talk about objects, the relations between them and functions on them, with variables and the quantifiers 'for all' and 'there exists'. (FOL) fixes this by looking inside statements. It has objects (Alice, Bob), relations between them (), and variables with quantifiers, so a single sentence can cover everyone:

This is the difference between a phone book and a grammar. A phone book lists every entry separately; a grammar states a few patterns that generate endless correct sentences. First-order logic gives a reasoning system patterns, and that is what makes it the backbone of databases, rule engines, and languages like Prolog and SQL.

How it works

Step 1: Objects, relations, functions

A first-order sentence is built from:

  • Constants that name objects: , , .
  • Predicates that state relations or properties, true or false: , , .
  • Functions that map objects to objects: names a person without giving her a constant.
  • Variables such as and , which stand for objects.
  • The connectives from propositional logic: .

Step 2: Quantifiers

Two quantifiers let sentences talk about many objects at once:

  • Universal, , "for all ": , every human is mortal.
  • Existential, , "there exists an ": , Bob has a parent.

Two classic traps. With the natural connective is : claims that everything is a human, including your toaster. With the natural connective is : is true as soon as there is anything that is not Bob's parent, which is almost certainly not what you meant. And order matters: (everyone loves someone) is very different from (someone is loved by everyone).

Step 3: Unification, matching with variables

To use a rule such as "parent of a parent is a grandparent", a reasoner must match its pattern against known facts. UnificationFinding a substitution of terms for variables that makes two expressions identical, such as {x: Alice, y: Bob} for Parent(x, y) and Parent(Alice, Bob). finds a substitution, an assignment of terms to variables, that makes two expressions identical:

  • and unify with .
  • and do not unify: cannot be both.
  • and unify with .

Unification is the engine of first-order inference. It means a rule written once applies to every object that fits its pattern, without generating every specific case in advance.

Step 4: Forward chaining

Many practical knowledge bases are written as definite clauses: rules of the form "if all of these hold, then this holds", plus facts. Two strategies reason with them.

Forward chainingInference that starts from the known facts and repeatedly applies rules whose conditions are satisfied, adding their conclusions, until nothing new can be derived. starts from the facts. Find every rule whose conditions unify with known facts, add its conclusion as a new fact, and repeat until nothing new appears. It is data-driven: it derives everything that follows, which is ideal when new facts arrive and you want to react to them, as a rule engine or monitoring system does.

Step 5: Backward chaining

Backward chainingInference that starts from a goal and works backwards, finding rules whose conclusion matches the goal and trying to prove their conditions as subgoals, depth first. starts from a question. To prove , find a rule whose head unifies with it, then try to prove that rule's conditions as subgoals, depth first, until every subgoal is a known fact. It is goal-driven: it only explores what is relevant to the question.

Backward chaining proves grandparent(alice, Who) The goal grandparent of alice and Who matches the grandparent rule and splits into two subgoals. The first, parent of alice and Y, unifies with the fact parent of alice and bob, binding Y to bob. The second becomes parent of bob and Who, which unifies with two facts, giving Who equals carol and Who equals dan; a third fact, parent of carol and erin, does not match. Y = bob parent(alice, bob) parent(alice, Y) subgoal 1 Who = carol parent(bob, carol) Who = dan parent(bob, dan) no match parent(carol, erin) parent(bob, Who) subgoal 2, Y = bob grandparent(alice, Who) Figure 1. The grandparent rule turns the question into two subgoals. Solving the first binds Y = bob, which narrows the second to parent(bob, Who). Each fact that unifies gives one answer (green).

Try it

There is no lab for this lesson; the code below is a complete Prolog-style reasoner, with unification and backward chaining, in about 60 lines:

chaining.pyruns with python3 (standard library)
import itertools

# Terms: variables start with a capital ("X"); atoms are lowercase;
# a fact or goal is a tuple: ("parent", "alice", "bob").
FACTS = [("parent", "alice", "bob"), ("parent", "bob", "carol"),
         ("parent", "bob", "dan"), ("parent", "carol", "erin")]
RULES = [  # (head, body): the head holds if every goal in the body does
    (("grandparent", "X", "Z"),
     [("parent", "X", "Y"), ("parent", "Y", "Z")]),
    (("ancestor", "X", "Y"), [("parent", "X", "Y")]),
    (("ancestor", "X", "Z"),
     [("parent", "X", "Y"), ("ancestor", "Y", "Z")]),
]
is_var = lambda t: isinstance(t, str) and t[0].isupper()

def walk(t, s):
    while is_var(t) and t in s:
        t = s[t]
    return t

def unify(a, b, s):
    """Extend substitution s so a and b become equal (or None)."""
    a, b = walk(a, s), walk(b, s)
    if a == b:
        return s
    if is_var(a):
        return {**s, a: b}
    if is_var(b):
        return {**s, b: a}
    if isinstance(a, tuple) and isinstance(b, tuple) and len(a) == len(b):
        for x, y in zip(a, b):
            s = unify(x, y, s)
            if s is None:
                return None
        return s
    return None

fresh = itertools.count()
def rename(t, n):  # give each rule use its own variables
    return tuple(f"{x}_{n}" if is_var(x) else x for x in t)

def prove(goals, s):
    """Backward chaining: yield each substitution proving all goals."""
    if not goals:
        yield s
        return
    first, rest = goals[0], goals[1:]
    for fact in FACTS:
        s2 = unify(first, fact, s)
        if s2 is not None:
            yield from prove(rest, s2)
    for head, body in RULES:
        n = next(fresh)
        s2 = unify(first, rename(head, n), s)
        if s2 is not None:
            yield from prove([rename(b, n) for b in body] + rest, s2)

for goal in [("grandparent", "alice", "Who"),
             ("ancestor", "alice", "Who")]:
    answers = [walk("Who", s) for s in prove([goal], {})]
    print(f"{goal[0]}(alice, Who): Who = {', '.join(answers)}")

Output

grandparent(alice, Who): Who = carol, dan
ancestor(alice, Who): Who = bob, carol, dan, erin

The reasoner knows only four parent facts and three rules, yet it answers questions nobody wrote down. grandparent(alice, Who) follows Figure 1 and finds carol and dan. ancestor is defined recursively, an ancestor is a parent or a parent of an ancestor, and backward chaining follows the recursion three generations down to erin. Notice rename: every time a rule is used, its variables get fresh names, so the Y in one use of the rule does not clash with the Y in another.

If you run it yourself, add ("parent", "erin", "fay") to FACTS and ask again: fay appears as an ancestor answer with no other change.

Going deeper

Prolog and Datalog

PrologA logic programming language whose programs are facts and rules (definite clauses) and whose execution is backward chaining with unification., created in the early 1970s, is backward chaining turned into a programming language. A program is facts and rules; running it means asking a query:

grandparent(X, Z) :- parent(X, Y), parent(Y, Z).
?- grandparent(alice, Who).

Prolog searches depth first, which is fast and memory-light but inherits depth-first search's weakness ( Uninformed search: BFS, DFS, uniform cost ): a rule like ancestor(X, Z) :- ancestor(X, Y), parent(Y, Z) makes it recurse forever, so rule order matters. Datalog, a restricted cousin with no functions, is evaluated forward, always terminates, and powers recursive queries in databases, program analysis tools and access-control systems. SQL's recursive queries are the same idea.

Forward or backward?

Forward chaining computes everything that follows, which can be far more than you need, but every fact is derived once and new data triggers updates naturally. Backward chaining does only the work a question requires, but may re-derive the same subgoal many times; Prolog systems add tabling (memoisation) to avoid this. Production rule engines use forward chaining with clever indexing of partial matches, the Rete algorithm, so that thousands of rules can be checked against changing facts efficiently. You will meet them in Expert systems and rule engines .

The price of expressiveness

Propositional entailment can always be decided, at worst by a giant truth table. First-order entailment cannot: there is no algorithm that answers every "does this follow?" question, a result due to Church and Turing in the 1930s. Resolution-based provers are complete in the sense that they will eventually prove anything that does follow, but if a sentence does not follow they may run forever. Practical systems therefore restrict the language, to definite clauses, to Datalog, or to description logics used in ontologies ( Knowledge graphs and ontologies ), trading expressiveness for guaranteed answers.

The trade between expressiveness and decidability Four boxes from left to right: propositional logic, Datalog, description logics, and full first-order logic. An arrow runs from left to right labelled more expressive. Full first-order logic is marked as undecidable in general; the others always give an answer. Propositional decidable Datalog always terminates Description logics decidable, costly Full first-order undecidable in general more expressive, harder to reason with Figure 2. Moving right, the language can say more, and reasoning gets harder. Full first-order logic is so expressive that no algorithm can answer every entailment question.

Trade-offs

OptionWins whenLoses when
Forward chaining Facts arrive continuously and you must react, as in rule engines and monitoring Derives many facts nobody asks about
Backward chaining Answering specific questions; exploring only what is relevant Can repeat work or loop on recursive rules without tabling
Full first-order logic Stating general mathematical or legal knowledge precisely Entailment is undecidable; provers may not terminate
Restricted logics (Datalog, description logics) Guaranteed answers at scale: databases, ontologies, access control Some knowledge cannot be expressed

Common mistakes

  • Writing when you mean . The first claims everything is an A.
  • Writing when you mean . The first is almost always trivially true.
  • Swapping quantifier order. "Everyone loves someone" and "someone is loved by everyone" are different claims.
  • Reusing variable names across rule applications. Each use of a rule needs fresh variables, or bindings leak between them.
  • Writing left-recursive rules for a depth-first reasoner. Put the base case first and recurse on the right.

In the wild

Where you will see this: SQL is first-order logic with a database underneath, and its recursive queries are Datalog. Static analysis and security tools express "this value can reach that function" as Datalog rules over facts extracted from code. Access-control policies, tax and benefits rules, and some smart-contract checkers are written in logic languages so that every decision can be traced to the rules that produced it. Interactive theorem provers, used to verify chip designs, compilers and mathematical proofs, are built on richer logics still.

Check yourself

  1. What can first-order logic say that propositional logic cannot?

    Show answer

    B. General statements about all objects using variables and quantifiers Objects, relations and quantifiers let one sentence cover every object, instead of one proposition per case.

  2. Which correctly says 'every human is mortal'?

    Show answer

    B. for all x, Human(x) implies Mortal(x) A universal is usually paired with implication. The 'and' version claims that everything is human.

  3. What substitution unifies Likes(x, Pizza) and Likes(Ada, y)?

    Show answer

    B. {x: Ada, y: Pizza} Matching position by position: x takes Ada and y takes Pizza, making both Likes(Ada, Pizza).

  4. A fraud system must react whenever a new transaction arrives. Which strategy fits?

    Show answer

    B. Forward chaining Forward chaining is data-driven: each new fact triggers the rules it satisfies.

  5. Why do practical systems often avoid full first-order logic?

    Show answer

    B. Entailment in it is undecidable, so reasoning may never finish No algorithm can answer every first-order entailment question, so systems restrict the language to get guaranteed answers.

Recap

  • First-order logic adds objects, relations, functions and quantifiers, so one sentence can cover every object.
  • Pair 'for all' with implies and 'there exists' with and; quantifier order matters.
  • Unification finds variable bindings that make two expressions match; it lets one rule apply to every case.
  • Forward chaining derives everything from the facts; backward chaining works back from a goal, as Prolog does.
  • Full first-order entailment is undecidable, so practical systems use restricted logics such as Datalog.

Get new lessons by email

Get new posts on backend and AI internals. No spam, unsubscribe anytime.

Your email is only used to send new posts. Privacy