Artificial Intelligence

Knowledge Reasoning And Planning

First-Order Logic

Chapter 2 ended by identifying propositional logic's core weakness: no way to express a general rule ("all men are mortal") without one sentence per individual.

JrCodex·8 min read

Jr Codex AI Notes

Level: Intermediate–Advanced Prerequisites: Chapter 2 Time to complete: ~30 minutes

Table of Contents

  1. Solving Propositional Logic's Limitation
  2. The Building Blocks: Objects, Relations, Functions
  3. Predicates
  4. Quantifiers — Universal and Existential
  5. Combining Quantifiers with Connectives
  6. Common Translation Mistakes
  7. Representing First-Order Sentences in Code
  8. Summary & Next Steps

1. Solving Propositional Logic's Limitation

Chapter 2 ended by identifying propositional logic's core weakness: no way to express a general rule ("all men are mortal") without one sentence per individual. First-order logic (FOL) fixes this by introducing variables, predicates, and quantifiers — a single sentence can now express a rule covering every object in a domain.

Propositional Logic                    First-Order Logic
─────────────────────────────         ─────────────────────────────
  SocratesIsMan → SocratesIsMortal      ∀x (Man(x) → Mortal(x))
  PlatoIsMan → PlatoIsMortal              "For ALL x, if x is a
  (one sentence PER individual,             man, then x is mortal"
   no way to generalize)                    (ONE sentence, covers
                                              EVERY individual)
─────────────────────────────         ─────────────────────────────

2. The Building Blocks: Objects, Relations, Functions

FOL's Vocabulary
─────────────────────────────────────────
  Constants:    specific, named objects
                  e.g. Socrates, Plato, Bucharest

  Variables:      placeholders standing for ANY object
                    e.g. x, y (as in "for all x...")

  Predicates:       properties or relationships that are
                      TRUE or FALSE of objects
                      e.g. Man(x), Mortal(x), Loves(x, y)

  Functions:          map objects to OTHER objects (not
                        true/false — an actual object)
                        e.g. MotherOf(x), PlusOne(x)
─────────────────────────────────────────

Propositional vs FOL — What Changed
─────────────────────────────────────────
  Propositional atom "SocratesIsMan" is a single, INDIVISIBLE unit.

  FOL's Man(Socrates) has INTERNAL STRUCTURE: a predicate
  Man(...) applied to the SPECIFIC object Socrates — and the
  SAME predicate can be applied to ANY other object:
  Man(Plato), Man(Aristotle), or the VARIABLE version Man(x).
─────────────────────────────────────────

3. Predicates

A predicate takes one or more objects and evaluates to true or false — directly analogous to a Python function returning a boolean (Python Notes, Module 2).

# Modeling FOL predicates directly as Python functions/dictionaries,
# for a small, concrete world of objects
 
objects = ["Socrates", "Plato", "Aristotle", "Zeus"]
 
# Man(x) — represented as a set of objects for which it's TRUE
Man = {"Socrates", "Plato", "Aristotle"}      # Zeus is NOT a man (he's a god, in mythology)
 
def is_man(x):
    return x in Man
 
print(is_man("Socrates"))      # True
print(is_man("Zeus"))            # False
 
# A TWO-argument predicate: Loves(x, y)
Loves = {("Socrates", "Plato"), ("Plato", "Aristotle")}
 
def loves(x, y):
    return (x, y) in Loves
 
print(loves("Socrates", "Plato"))      # True

Predicates can take any number of arguments — Man(x) is unary (one argument), Loves(x, y) is binary (two), and higher-arity predicates (three or more arguments) are equally valid, just less common in introductory examples.

4. Quantifiers — Universal and Existential

Two quantifiers let a sentence talk about all or some objects, without naming them individually:

Universal Quantifier: ∀ ("for all")
─────────────────────────────────────────
  ∀x Man(x) → Mortal(x)
  "For EVERY object x, IF x is a man, THEN x is mortal"

  TRUE only if the implication holds for EVERY SINGLE object
  in the domain — a single counterexample (a man who ISN'T
  mortal) makes the whole sentence FALSE.
─────────────────────────────────────────

Existential Quantifier: ∃ ("there exists")
─────────────────────────────────────────
  ∃x Man(x) ∧ Wise(x)
  "There EXISTS at least one object x that is BOTH a man AND wise"

  TRUE if EVEN ONE object in the domain satisfies both
  conditions — doesn't require it to hold for everyone.
─────────────────────────────────────────

def for_all(objects, predicate):
    """∀x predicate(x) — true only if EVERY object satisfies the predicate."""
    return all(predicate(x) for x in objects)
 
def there_exists(objects, predicate):
    """∃x predicate(x) — true if AT LEAST ONE object satisfies the predicate."""
    return any(predicate(x) for x in objects)
 
Mortal = {"Socrates", "Plato", "Aristotle", "Zeus"}      # everyone in this toy world happens to be mortal
 
def man_implies_mortal(x):
    return (not is_man(x)) or (x in Mortal)      # Man(x) → Mortal(x), using Ch.2's implication rule
 
print(for_all(objects, man_implies_mortal))      # True — holds for every object
 
Wise = {"Socrates"}
print(there_exists(objects, lambda x: is_man(x) and x in Wise))      # True — Socrates satisfies it

A critical, easily-confused rule: ∀ pairs naturally with → (implication), while ∃ pairs naturally with ∧ (and) — Section 6 covers exactly why mixing these up is the single most common FOL translation mistake.

5. Combining Quantifiers with Connectives

Quantifiers and Chapter 2's connectives combine to express genuinely rich statements:

# "All birds that are not penguins can fly"
# ∀x (Bird(x) ∧ ¬Penguin(x)) → CanFly(x)
 
Bird = {"Sparrow", "Eagle", "Penguin1", "Penguin2"}
Penguin = {"Penguin1", "Penguin2"}
CanFly = {"Sparrow", "Eagle"}
 
def bird_rule(x):
    if x in Bird and x not in Penguin:
        return x in CanFly
    return True      # vacuously true for non-birds or penguins — implication rule from Ch.2
 
all_objects = Bird | {"Dog", "Cat"}
print(for_all(all_objects, bird_rule))      # True — holds for this world
# Nested quantifiers — "everyone loves someone" vs "someone is loved by everyone"
# ∀x ∃y Loves(x, y)   ≠   ∃y ∀x Loves(x, y)
 
people = ["Alice", "Bob", "Charlie"]
loves_relation = {("Alice", "Bob"), ("Bob", "Charlie"), ("Charlie", "Alice")}
 
def loves(x, y):
    return (x, y) in loves_relation
 
# ∀x ∃y Loves(x,y): "EVERYONE loves AT LEAST ONE person" (not necessarily the SAME person)
everyone_loves_someone = for_all(people, lambda x: there_exists(people, lambda y: loves(x, y)))
print(everyone_loves_someone)      # True — this toy world has a "love triangle"
 
# ∃y ∀x Loves(x,y): "THERE IS ONE SPECIFIC person that EVERYONE loves"
someone_loved_by_all = there_exists(people, lambda y: for_all(people, lambda x: loves(x, y)))
print(someone_loved_by_all)      # False — no single person is loved by ALL three
Order of Quantifiers MATTERS
─────────────────────────────────────────
  ∀x ∃y Loves(x, y)     "everyone has SOMEONE they love"
                          (can be a DIFFERENT y for each x)

  ∃y ∀x Loves(x, y)        "there's ONE person EVERYONE loves"
                             (the SAME y for every x — a much
                             STRONGER, more specific claim)

  Swapping the order of DIFFERENT quantifier types changes
  the MEANING entirely — this is a frequent source of
  translation errors for beginners.
─────────────────────────────────────────

6. Common Translation Mistakes

Mistake 1: Using ∧ Instead of → with ∀
─────────────────────────────────────────
  WRONG:   ∀x (Bird(x) ∧ CanFly(x))
             "for all x, x is a bird AND x can fly"
             — this WRONGLY claims EVERY object in the
               ENTIRE domain is a flying bird!

  CORRECT:   ∀x (Bird(x) → CanFly(x))
                "for all x, IF x is a bird THEN x can fly"
                — correctly restricts the claim to birds only
─────────────────────────────────────────

Mistake 2: Using → Instead of ∧ with ∃
─────────────────────────────────────────
  WRONG:   ∃x (Bird(x) → CanFly(x))
             — TRIVIALLY true if even ONE non-bird exists
               in the domain (implication is vacuously true
               for anything that isn't a bird!) — says almost
               NOTHING useful

  CORRECT:   ∃x (Bird(x) ∧ CanFly(x))
                "there EXISTS an x that IS a bird AND can fly"
                — the intended, meaningful claim
─────────────────────────────────────────

Memory aid: "∀ likes →, ∃ likes ∧" — internalizing this pairing prevents the majority of first-order logic translation errors.

7. Representing First-Order Sentences in Code

Bringing this chapter together with Chapter 1's knowledge base structure — a small first-order knowledge base supporting general rules, not just individual facts:

class FirstOrderKB:
    def __init__(self, domain):
        self.domain = domain      # all objects under consideration
        self.predicates = {}        # predicate_name -> set of tuples for which it's true
 
    def add_fact(self, predicate_name, *args):
        self.predicates.setdefault(predicate_name, set()).add(args)
 
    def holds(self, predicate_name, *args):
        return args in self.predicates.get(predicate_name, set())
 
    def check_universal_rule(self, condition, conclusion):
        """∀x condition(x) → conclusion(x)"""
        return all((not condition(x)) or conclusion(x) for x in self.domain)
 
    def check_existential_rule(self, condition):
        """∃x condition(x)"""
        return any(condition(x) for x in self.domain)
 
 
kb = FirstOrderKB(domain=["Socrates", "Plato", "Zeus"])
kb.add_fact("Man", "Socrates")
kb.add_fact("Man", "Plato")
kb.add_fact("Mortal", "Socrates")
kb.add_fact("Mortal", "Plato")
kb.add_fact("Mortal", "Zeus")      # even Zeus is mortal in THIS toy world, for the example
 
rule_holds = kb.check_universal_rule(
    condition=lambda x: kb.holds("Man", x),
    conclusion=lambda x: kb.holds("Mortal", x),
)
print(rule_holds)      # True — "all men are mortal" holds given these facts

This structure — a knowledge base of predicate-tuples plus universal/existential rule-checking — is a simplified version of what real inference engines (Chapter 4) build on, and directly foreshadows how automated planning (Chapter 5) represents world states using first-order predicates.

8. Summary & Next Steps

Key Takeaways

  • First-order logic adds variables, predicates, and quantifiers to propositional logic, allowing a single sentence to express a rule about every object in a domain, rather than requiring one sentence per individual.
  • Predicates (like Man(x), Loves(x, y)) evaluate to true or false for specific objects, directly analogous to boolean-returning functions.
  • ∀ (universal, "for all") naturally pairs with →; ∃ (existential, "there exists") naturally pairs with ∧ — mixing these up is the most common translation mistake.
  • The order of different quantifier types changes meaning entirely: ∀x ∃y Loves(x,y) ("everyone loves someone") is very different from ∃y ∀x Loves(x,y) ("someone is loved by everyone").

Concept Check

  1. Why can't propositional logic (Chapter 2) express "all men are mortal" as a single, general sentence?
  2. Why is ∃x (Bird(x) → CanFly(x)) a nearly meaningless (trivially true) statement, while ∃x (Bird(x) ∧ CanFly(x)) is the intended, useful one?
  3. What's the difference in meaning between ∀x ∃y Loves(x, y) and ∃y ∀x Loves(x, y)?

Next Chapter

→ Chapter 4: Inference & Reasoning Systems

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index