First-Order Logic

First-Order Logic (FOL): What it Models

First-Order Logic (FOL) models: 1) Objects (individual entities with distinct identities). 2) Properties (attributes that distinguish objects). 3) Relations (connections that hold among sets of objects). 4) Functions (a special type of relation where each input maps to a single output value). 5) Quantifiers (∀ for "all", ∃ for "exists") to make statements about groups of objects.

FOL: Constant Symbols

Constant Symbols in FOL represent specific, named individual objects in the domain. Examples: Mary, 3, Green, London. They are the formal analogs of proper nouns or specific values.

FOL: Function Symbols

Function Symbols represent mappings from objects to objects. They take one or more terms (constants, variables, or other function results) as arguments and return a single object. Examples: father-of(Mary), color-of(Grass), plus(2,3).

FOL: Predicate Symbols

Predicate Symbols represent relations or properties that can be true or false of objects. They take one or more terms as arguments and denote a statement. Examples: Greater(5,3) (a relation), Green(Grass) (a property), Color(Grass, Green) (a relation).

Term in FOL

A Term in FOL is defined recursively: 1) A constant symbol is a term. 2) A variable symbol is a term. 3) If f is an n-place function symbol and t₁, …, tₙ are terms, then f(t₁, …, tₙ) is a term. Terms denote objects in the domain. Example: father-of(father-of(John)).

Atomic Sentence in FOL

An Atomic Sentence (or atomic formula) is formed by applying an n-place predicate symbol to n terms. It represents a basic fact that can be true or false. Examples: Greater(5,3), Sibling(John, Mary), Color(Grass, Green). It is the FOL analog of a propositional symbol.

Complex Sentence in FOL

A Complex Sentence is formed by combining atomic sentences (or other complex sentences) using logical connectives:

(not), ∧ (and), ∨ (or), ⇒ (implies), ⇔ (iff). Example: *Sibling(John, Mary) ∧

Sibling(John, Alice)*.

Quantified Sentence in FOL

A Quantified Sentence contains a quantifier (∀ or ∃) applied to a variable in a formula. Universal Quantification (∀x): "For all x, …". Existential Quantification (∃x): "There exists an x such that …". Example: ∀x (Cat(x) ⇒ Mammal(x)). The variable bound by the quantifier is called a bound variable.

Well-Formed Formula (WFF) in FOL

A Well-Formed Formula (WFF) in FOL is a syntactically correct sentence where every variable is either: 1) Bound by a quantifier within the formula, or 2) Appears as an argument in a function or predicate but is introduced in a properly quantified context. A sentence with no free variables (unquantified variables) is a closed formula.

Universal Quantifier (∀)

The Universal Quantifier (∀x) φ(x) asserts that the formula φ holds for every object x in the domain. Example: ∀x (Student(x) ⇒ HasID(x)) means "Every student has an ID." It is logically equivalent to a conjunction over all domain objects.

Existential Quantifier (∃)

The Existential Quantifier (∃x) φ(x) asserts that there exists at least one object x in the domain for which φ(x) is true. Example: ∃x (Student(x) ∧ TopGrade(x)) means "There is a student who has a top grade." It is logically equivalent to a disjunction over all domain objects.