I4 · Problem Solving and Reasoning: Classical AI

First-Order Logic

First-order logic (predicate logic) extends propositional logic with objects, predicates that describe properties and relations of objects, functions, variables and the quantifiers "for all" (∀) and "there exists" (∃). It can state general rules such as ∀x Student(x) ∧ PassedAll(x) → Promoted(x) and derive conclusions about particular objects.

12 min Intermediate · Sublevel Intermediate Jump to the activity

What you need: The earlier topics of this module.

Definition

"All humans are mortal. Socrates is a human. So Socrates is mortal." Propositional logic cannot even write the first sentence for every human at once. First-order logic can.

First-order logic (predicate logic) extends propositional logic with objects, predicates that describe properties and relations of objects, functions, variables and the quantifiers "for all" (∀) and "there exists" (∃). It can state general rules such as ∀x Student(x) ∧ PassedAll(x) → Promoted(x) and derive conclusions about particular objects.

In simple words

Propositional logic has a separate switch for every fact: "Riya passed", "Arjun passed". First-order logic lets you write one rule for everyone, "anyone who passes all subjects is promoted", and then apply it to Riya, Arjun or any new student automatically.

Overview

  • First-order logic (predicate logic) talks about objects, their properties and relations, not just whole statements.
  • It has constants (Asha), variables (x), predicates (Student(x)), functions (motherOf(x)) and quantifiers.
  • ∀ (for all) and ∃ (there exists) express general rules and existence.
  • One rule can replace thousands of propositional facts: ∀x Student(x) → Person(x).
  • Unification finds substitutions that make two expressions identical, the key step in inference.
  • Prolog (1972) is a programming language based on a subset of first-order logic.

Why it matters

First-order logic is the language behind knowledge bases, the rule engines used in business and law, database query languages and the Semantic Web. It shows how AI can represent general knowledge compactly and reason with it exactly.

Key terms

Constant
A name for a specific object, such as Riya or Delhi.
Predicate
A property or relation that is true or false of objects, such as Student(Riya) or Capital(Delhi, India).
Function
A mapping from objects to an object, such as MotherOf(Riya).
Universal quantifier ∀
"For all x": the statement holds for every object.
Existential quantifier ∃
"There exists an x": the statement holds for at least one object.
Unification
Finding substitutions that make two expressions identical, the key step in automated reasoning.

Types

First-order logic is built from several types of element, and reasons with a few types of inference. These are explained here.

1. Terms: constants, variables and functions

Expressions that name objects.

  • How it works: Constants name particular objects; variables stand for any object; functions map objects to other objects.
  • Example: Delhi is a constant; x is a variable; capitalOf(India) is a function term that refers to Delhi.
  • When to use it: Use them to refer to the things your knowledge base is about.

2. Predicates and atomic sentences

Properties and relations that are true or false of objects.

  • How it works: A predicate applied to terms forms an atomic sentence, such as Teaches(Ravi, Maths) or Prime(7).
  • Example: ParentOf(Meera, Arjun) states that Meera is Arjun's parent.
  • When to use it: Use them to state facts about the world in a precise, machine-readable way.

3. Universal and existential quantifiers

∀x (for every x) and ∃x (for at least one x).

  • How it works: ∀ usually pairs with →, and ∃ with ∧; ¬∀x P(x) is equivalent to ∃x ¬P(x).
  • Example: ∀x (Mango(x) → Fruit(x)); ∃x (Student(x) ∧ Topper(x)).
  • When to use it: Use them to write general rules and claims of existence; mixing up → and ∧ with quantifiers is a classic error.

4. Inference by unification and chaining

Applying rules by finding variable substitutions that match facts.

  • How it works: Generalised modus ponens unifies a rule's conditions with known facts; forward chaining adds new facts, backward chaining works back from a query.
  • Example: From ∀x Student(x) → Person(x) and Student(Asha), unify x = Asha and conclude Person(Asha).
  • When to use it: Use backward chaining to answer questions and forward chaining to keep a knowledge base up to date.

5. Resolution theorem proving

A complete proof method for first-order logic that works by refutation.

  • How it works: Convert sentences to clauses, add the negated goal, and resolve clauses with unification until an empty clause (a contradiction) appears.
  • Example: Automated provers have verified results in mathematics and software correctness.
  • When to use it: Use it in automated theorem provers and formal verification tools.

Explained in detail

Translating sentences

EnglishFirst-order logic
Riya is a student.Student(Riya)
Every student has a roll number.∀x Student(x) → ∃n RollNumber(x, n)
Some student scored full marks.∃x Student(x) ∧ FullMarks(x)
No student is a teacher.∀x Student(x) → ¬Teacher(x)
Siblings share parents.∀x ∀y Sibling(x, y) → ∃p Parent(p, x) ∧ Parent(p, y)

Two patterns are worth remembering. "All A are B" uses ∀ with →: ∀x A(x) → B(x). "Some A is B" uses ∃ with ∧: ∃x A(x) ∧ B(x). Mixing them up is the most common translation error: ∀x Student(x) ∧ Promoted(x) would claim that everything in the world is a promoted student. The order of quantifiers matters too: ∀x ∃y Loves(x, y) says everyone loves someone; ∃y ∀x Loves(x, y) says there is one person everyone loves.

Reasoning

To use a general rule on a particular object, a reasoner substitutes the object for the variable. From ∀x Student(x) ∧ PassedAll(x) → Promoted(x) and the facts Student(Riya) and PassedAll(Riya), substituting Riya for x gives Promoted(Riya). Finding such substitutions automatically is called unification, introduced by John Alan Robinson in 1965 together with resolution for first-order logic. The logic programming language Prolog, created by Alain Colmerauer and Philippe Roussel in 1972, is built directly on this idea: you write facts and rules, and Prolog answers questions by searching for substitutions.

Power and limits

  • Much more expressive than propositional logic: one rule covers infinitely many objects.
  • Semi-decidable: if a conclusion follows, a complete prover will eventually find a proof, but if it does not, the search may never end.
  • Still all-or-nothing: it cannot express "usually" or "probably", which most real knowledge needs.
  • Writing complete, correct rules by hand is very hard for messy domains, one reason learning from data became dominant.

First-order ideas are everywhere in modern computing even when the word logic is never used. A database query such as "find every customer who has placed an order in the last month" is an existential statement about customers and orders, and SQL engines are, in effect, specialised reasoners over first-order facts. Knowledge graphs store billions of predicate facts of the form Relation(subject, object), and the rules that check them for consistency are first-order rules. Learning to translate English into logic therefore sharpens how you write precise queries, specifications and tests, a skill that pays off well beyond classical AI.

How it works

  1. Identify the objects, their properties (predicates) and relations.
  2. Write general rules with ∀ and →, and existence claims with ∃ and ∧.
  3. Add specific facts as ground predicates such as Student(Riya).
  4. Infer by substituting objects into rules (unification).
  5. Check translations by reading them back in plain English.

In code

first_order.py
# A tiny forward-chaining reasoner over first-order style facts.
facts = {("Student", "Riya"), ("Student", "Arjun"), ("PassedAll", "Riya"),
         ("Parent", "Meera", "Riya"), ("Parent", "Meera", "Arjun")}

def rule_promoted(facts):
    # forall x: Student(x) and PassedAll(x) -> Promoted(x)
    return {("Promoted", x) for (p, x, *_) in facts if p == "Student" and ("PassedAll", x) in facts}

def rule_sibling(facts):
    # forall x, y, p: Parent(p, x) and Parent(p, y) and x != y -> Sibling(x, y)
    parents = [f for f in facts if f[0] == "Parent"]
    return {("Sibling", a[2], c[2]) for a in parents for c in parents if a[1] == c[1] and a[2] != c[2]}

changed = True
while changed:
    new = rule_promoted(facts) | rule_sibling(facts)
    changed = not new <= facts
    facts |= new

for fact in sorted(facts):
    print(fact)

Output

('Parent', 'Meera', 'Arjun')
('Parent', 'Meera', 'Riya')
('PassedAll', 'Riya')
('Promoted', 'Riya')
('Sibling', 'Arjun', 'Riya')
('Sibling', 'Riya', 'Arjun')
('Student', 'Arjun')
('Student', 'Riya')

Try it yourself

One rule, every student

A school's rule engine decides promotions.

Which translation is correct?

Sort each into correct or incorrect.

  • "All birds fly": ∀x Bird(x) ∧ Flies(x)

  • "All birds fly": ∀x Bird(x) → Flies(x)

  • "Some student is absent": ∃x Student(x) ∧ Absent(x)

  • "Some student is absent": ∃x Student(x) → Absent(x)

Common mistakes

  • Using ∧ instead of → with ∀.
  • Swapping the order of quantifiers and changing the meaning.
  • Expecting logic to handle exceptions such as penguins that do not fly, without writing them in.

Check yourself

Question 1

1. How do you write "every student passed"?

Question 2

2. What does first-order logic add over propositional logic?

Question 3

3. What is unification?

Summary

  • First-order logic adds objects, predicates, functions and quantifiers.
  • "All A are B" uses ∀ and →; "some A is B" uses ∃ and ∧.
  • Unification applies general rules to specific facts; Prolog and rule engines build on this.

Finished reading?

Sources: Russell and Norvig, Artificial Intelligence: A Modern Approach (4th edition) · Stanford Encyclopedia of Philosophy: Classical Logic