FOL Syntax and Semantics

Syntax Components

Terms (refer to objects)

• Constant symbol: John, 2, NCCL — refers to a specific object
• Variable: x, y, s — ranges over objects (lowercase by convention)
• Function symbol: LeftLeg(John), Sqrt(4) — maps objects to objects

Atomic Sentences (the simplest sentences)

predicate(term₁, term₂, ..., termₙ)

• Person(John) — John is a person
• Loves(John, Mary) — John loves Mary
• Greater(Sqrt(4), 1) — √4 > 1

Complex Sentences

Built using connectives (same as propositional logic): ∧ ∨ ¬ → ↔︎

Quantifiers

Universal quantification (for all):

∀x P(x)     -- P is true of every object x

Existential quantification (there exists):

∃x P(x)     -- P is true of at least one object x

Quantifier Conventions

Universal → paired with implication

∀x King(x) → Person(x)     -- All kings are persons

NOT: ∀x King(x) ∧ Person(x) — this says everything is both a king and a person.

Existential → paired with conjunction

∃x Crown(x) ∧ OnHead(x, John)     -- Something is a crown and on John's head

NOT: ∃x Crown(x) → OnHead(x, John) — trivially true if anything is not a crown.

Equality

The binary predicate = has special semantics: - x = y means x and y refer to the same object - Father(John) = Henry — John’s father is Henry

Can define uniqueness: ∃x Crown(x) ∧ ∀y Crown(y) → y=x — exactly one crown.

Semantics: Interpretations

An interpretation assigns: 1. A domain D (non-empty set of objects) 2. A mapping from each constant to an object in D 3. A mapping from each predicate to a relation over D 4. A mapping from each function to a function over D

Truth condition: a sentence is true under an interpretation I iff: - Atomic P(t₁,...,tₙ): (I(t₁),…,I(tₙ)) ∈ I(P) - ∀x φ: φ is true for every object in D as value of x - ∃x φ: φ is true for some object in D as value of x - Connectives: same as propositional logic

Quantifier Duality (De Morgan for Quantifiers)

∀x ¬P(x)   ≡   ¬∃x P(x)
∃x ¬P(x)   ≡   ¬∀x P(x)
¬∀x P(x)   ≡   ∃x ¬P(x)
¬∃x P(x)   ≡   ∀x ¬P(x)

Example Knowledge Base

∀x Man(x) → Person(x)
∀x Woman(x) → Person(x)
∀x Person(x) → Mortal(x)
Man(Socrates)
∀x Mortal(x) → Dies(x)

Entailed: Dies(Socrates) — derivable by forward chaining (universal instantiation + modus ponens).

Higher-Order Logic vs FOL

FOL quantifies over objects: ∀x P(x)

Higher-order logic also quantifies over predicates and functions: ∀P P(John)

FOL is the sweet spot: - More expressive than propositional - Semi-decidable (complete inference procedures exist) - Higher-order: inference is not even semi-decidable in general