Logic 7 - First Order Logic | Stanford CS221: AI (Autumn 2021)

Main ideas / lessons

• Why propositional logic isn’t enough

  • Propositional logic represents facts only as truth-valued symbols.
  • This becomes non-scalable and not expressive when statements involve:
    • Many objects (e.g., “All students know arithmetic” would require enumerating every student with separate symbols).
    • Infinite domains or general rules (e.g., “Every even number greater than two is the sum of two prime numbers” is about infinitely many integers, so propositional logic can’t compactly express it).

• First-order logic (FOL) adds structure

  • FOL represents objects and relationships between them using:
    • Predicates (relations/properties applied to objects)
    • Terms (constants, variables, functions)
    • Quantifiers (to say “for all” / “there exists”)

• Syntax then semantics

  • The module covers:
    • Syntax of FOL (how to write terms and formulas)
    • Semantics of FOL (how meanings/models are defined)

---

Detailed methodology / instruction-like content

A) How to express natural language in first-order logic

Use the following translation patterns:

• “Alice and Bob know arithmetic.”

  • Represent each person as an object constant.
  • Represent “knows” as a predicate relating the person object to the arithmetic object.
  • Example atomic formulas:
    • Knows(Alice, Arithmetic)
    • Knows(Bob, Arithmetic)
  • (as atomic formulas combined)

• “All students know arithmetic.”

  • Use:
    • Universal quantifier (“for all”)
    • Implication to encode conditioning by the restrictor (“students”)
  • Core pattern:
    • For all X: if Student(X) then Knows(X, Arithmetic)

• Subtle point about “every/everyone”

  • Natural language “Every student knows arithmetic” does not mean:
    • “Everyone is a student” AND “Everyone knows arithmetic”
  • Instead it means:
    • “For any X, if X is a student, then X knows arithmetic”
  • Therefore: “everyone” / “every student” often corresponds to universal quantification + implication.

• “Some student knows arithmetic.”

  • Use:
    • Existential quantifier (“there exists”)
    • Conjunction to assert the property once the individual exists
  • Core pattern:
    • There exists X: Student(X) and Knows(X, Arithmetic)

• Rule of thumb given

  • Whenever you see “everyone” / “every student” → usually use ∀ plus implication.
  • Whenever you see “some” → usually use ∃ plus and.

---

B) Example translations given

• Example 1: “There is a course that every student has taken.”

  • ∃Y: Course(Y) and (∀X: if Student(X) then Taken(X, Y))
  • Structure:
    • Existentially introduce the course Y
    • Universally quantify students X
    • Use implication from Student(X) to “X has taken course Y”

• Example 2: Goldbach-style claim

  • “Every even integer greater than two is the sum of two prime numbers.”
  • High-level structure:
    • For all X: if Even(X) and X > 2 then ...
    • Then existentially choose primes Y and Z such that:
      • Prime(Y) and Prime(Z) and X = Y + Z

• Example 3: Rule with “if”

  • “If a student is taking a course and the course covers a concept, then the student knows that concept.”
  • Corresponding structure:
    • For all X (student X) and for all Y (course Y) and for all Z (concept Z):
    • If Studies(X, Y) and Covers(Y, Z) then Knows(X, Z)
  • Note: the lecture frames “if” as essentially like “every”, i.e., universal with implication.

---

Syntax of first-order logic (what symbols/constructs exist)

1) Terms

FOL defines terms as expressions referring to objects:

• Constant symbols

  • Examples: Alice, Mathematics, Arithmetic

• Variables

  • Examples: X
  • Needed because quantifiers range over variables

• Functions

  • Functions take terms as inputs and produce new terms
  • Example given:
    • add( X, 3 ) → a term representing “X + 3”
  • In the lecture: “the sum of 3 and X” produces a term

---

2) Formulas

Formulas are truth-apt expressions built from atomic formulas and operators:

• Atomic formulas

  • Predicate applied to terms
  • Example:
    • “Bob knows arithmetic” is an atomic formula:
      • predicate like Knows(Bob, Arithmetic)

• Connectives / logical operations

  • Like propositional logic:
    • negation, conjunction, disjunction, implication, etc. (the lecture mentions negation and OR/AND)

• Quantifiers

  • Universal quantifier: “for all”
  • Existential quantifier: “exists”

---

3) Important logical properties of quantifiers (constraints)

• Quantifiers are not symmetric:
  • For all X exists Y ... is not equivalent to exists Y for all X ...
  • The order matters.

---

4) Intuition: quantifiers resemble AND/OR

• Universal quantifier (∀) is compared to AND over all possible values:

  • ∀x P(x) behaves like P(a) and P(b) and P(c) ... (when the domain is finite)

• Existential quantifier (∃) is compared to OR over all possible values:

  • ∃x P(x) behaves like P(a) or P(b) or P(c) ...

• Negation and De Morgan-like transformations

  • not (for all x P(x)) is equivalent to there exists x such that not P(x)
  • not (exists x P(x)) corresponds to for all x not P(x) (explained conceptually)

---

Semantics of first-order logic (how meanings/models are defined)

• Models in propositional logic

  • A model assigns truth values to propositional symbols.

• Models in first-order logic

  • A FOL model is described using:
    • Objects associated with constant symbols
    • Predicates interpreted as relations over those objects
  • The lecture explains a graph representation:
    • Nodes represent objects labeled by constant symbols (e.g., node labeled “Alice”)
    • Unary predicates appear as labels above nodes (e.g., Student(Alice))
    • Binary predicates appear as directed edges between nodes (e.g., Knows(Alice, Arithmetic))

---

Additional semantic constraints for easier reasoning (“propositionalization”)

To avoid ambiguity and enable mapping FOL into propositional-style inference:

• Unique names assumption

  • Each object has at most one constant symbol.
  • Prevents cases where two different constants refer to the same object.

• Domain closure assumption

  • Every object has at least one constant symbol.
  • Prevents anonymous objects with no constant label.

• Why these assumptions matter

  • They create a one-to-one correspondence between:
    • constant symbols ↔ objects
  • This enables propositionalization:
    • turning FOL knowledge bases into an equivalent propositional form
    • so the lecture can reuse propositional inference ideas like resolution and modus ponens.

---

How the knowledge base example connects to propositional logic

• Given FOL knowledge base:

  • Student(Alice)
  • Student(Bob)
  • For all X: if Student(X) then Person(X)
  • There exists X: Student(X) and Creative(X)

• Under the assumptions (unique names + domain closure), the lecture claims it can be re-expressed as propositional logic by grounding:

  • e.g., Student(Alice) becomes a propositional atom
  • Person(Alice) becomes a propositional atom
  • similarly for Bob, and for the creative predicate.

---

Speakers / sources featured

• Instructor / lecturer (unnamed in subtitles): the speaker explaining “Logic 7 - First Order Logic | Stanford CS221: AI (Autumn 2021)”
• Stanford CS221 (Autumn 2021): course/source context from the video title
• Goldbach’s conjecture: referenced as a motivating example, not a speaker