---
title: First-Order Logic
module: Logic and Planning
moduleNumber: 3
lessonNumber: 3
order: 303
summary: >
  Propositional logic can only say that facts hold; it cannot talk about the
  objects a fact is about, or state a rule once and have it cover every object.
  First-order logic fixes this by committing to a world of objects, relations,
  and functions. This first part builds the language from the ground up: the
  ontology it commits to, the model that gives a sentence a truth value, the
  syntax of terms and sentences, the two quantifiers with their standard mistakes,
  and equality.
topics: [Logic]
sources:
  - book: AIMA
    ref: "Ch. 8 — First-Order Logic; §8.1 Representation Revisited; §8.2 Syntax and Semantics"
---


[Propositional logic](/artificial-intelligence/logic-and-planning/propositional-logic)
gave a knowledge-based agent a declarative language: facts are separate from
inference, partial information survives through disjunction and negation, and
the meaning of a sentence is fixed by the meanings of its parts. Those are the
right properties for a representation language. The problem is expressive
power. A proposition symbol like $B_{1,1}$ is an atom with no internal
structure — it says nothing about _which_ square, and it cannot be related to
$B_{1,2}$ except by writing out, by hand, a fresh biconditional for every
square:[^aima-repr]

$$
B_{1,1} \iff (P_{1,2} \lor P_{2,1}).
$$

There are sixteen squares in a $4 \times 4$ wumpus world, so this rule has to be
stated sixteen times, once per square, even though in English it is one
sentence: "a square is breezy exactly when a neighbor holds a pit." Propositional
logic has no way to say "for every square," because it has no notion of a square
as an **object** it can quantify over. **First-order logic** adds exactly that
notion, and with it the ability to state general laws once and have them apply
everywhere.[^aima-fol]

## What propositional logic cannot say

The gap is best seen through what a representation language commits to about
reality — its **ontological commitment**. Propositional logic assumes the world
is a collection of _facts_, each of which holds or does not. That is enough to be
declarative and to handle partial information, but it leaves three things out:

- **No objects.** You cannot refer to Richard, or to square $[2,2]$, as a thing
  that properties attach to. There are only atomic facts.
- **No relations.** You cannot say that two objects stand in a relation —
  "Richard is the brother of John" — as a fact built from the two objects and the
  relation between them. `RichardIsBrotherOfJohn` is an unanalyzable symbol.
- **No generality.** Because there are no objects and no variables ranging over
  them, there is no way to say "_every_ king is a person." Each instance must be
  written separately.

First-order logic keeps propositional logic's declarative, compositional core
and borrows one idea from natural language: sentences are about **objects**
(nouns), the **relations** among them (verbs), and **functions**, the special
relations that map each input to exactly one output.[^aima-natural] The table
below places both logics on the spectrum of ontological commitments AIMA
uses (its Figure 8.1).[^aima-commit]

| Language | Ontological commitment (what exists) | Epistemological commitment (belief about facts) |
| --- | --- | --- |
| Propositional logic | facts | true / false / unknown |
| First-order logic | facts, objects, relations | true / false / unknown |
| Temporal logic | facts, objects, relations, times | true / false / unknown |
| Probability theory | facts | degree of belief $\in [0,1]$ |
| Fuzzy logic | facts with degree of truth $\in [0,1]$ | known interval value |

The two logics agree on _epistemology_ — an agent believes a sentence true,
false, or has no opinion — and differ only in _ontology_. First-order logic
commits to more of the structure of the world, and that is precisely where its
extra expressive power comes from.

$$
% caption: Propositional logic sees a fact $B_{1,1}$ as one unanalyzable symbol
% (left); first-order logic decomposes the same fact into an object, a relation,
% and another object (right), which is what lets a rule range over all objects.
\begin{tikzpicture}[>=stealth, font=\small,
  atom/.style={draw, minimum width=22mm, minimum height=10mm, align=center, font=\footnotesize},
  obj/.style={draw, circle, minimum size=11mm, inner sep=0pt, align=center, font=\footnotesize},
  rel/.style={draw, minimum width=17mm, minimum height=8mm, align=center, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  % --- left: propositional ---
  \node[atom] (p) at (0,0) {Breezy1-1};
  \node[font=\footnotesize, anchor=south, text=black] at (0,1.0) {propositional: one symbol};
  % --- right: first-order ---
  \begin{scope}[xshift=6.4cm]
    \node[obj] (r) at (-1.9,0) {sq(1,1)};
    \node[rel, draw=acc, text=acc] (b) at (0,0) {Breezy};
    \draw[->, acc, thick] (r) -- (b);
    \node[font=\footnotesize, anchor=south, text=black] at (-0.9,1.0) {f\/irst-order: object + relation};
  \end{scope}
\end{tikzpicture}
$$

## The ontology: objects, relations, functions

The building blocks of a first-order world are three kinds of thing.[^aima-orf]

> **Definition (Object).** A thing in the world that the language can name and
> reason about: people, squares, numbers, colors, wars, centuries. The set of all
> objects in a given model is its **domain**, and the domain must be nonempty.

> **Definition (Relation).** A set of tuples of objects that stand in some
> relationship. A **unary** relation is a **property** (red, prime, a king); a
> binary relation relates pairs (brother-of, adjacent-to); an $n$-ary relation
> relates $n$-tuples. Formally a relation _is_ the set of tuples for which it
> holds.

> **Definition (Function).** A relation in which each input tuple maps to exactly
> one output object — "father of," "left leg of," "one more than." First-order
> logic requires functions to be **total**: there is an output for every possible
> input tuple.

Almost any assertion decomposes into these. "Evil King John ruled England in
1200" has objects John, England, and 1200; the relation _ruled_; and the
properties _evil_ and _king_. "One plus two equals three" has objects one, two,
and three; the function _plus_ applied to one and two; and the relation
_equals_. Once the world is objects with relations and functions among them,
first-order logic can also quantify over them — say something about _some_ or
_all_ objects — which is the source of its ability to state general laws.

## Models: a domain and an interpretation

The **model** of a first-order sentence is a possible world: a set of objects
plus a link from the vocabulary to those objects. AIMA's running example is a
kinship scene with five objects — Richard the Lionheart, his brother the evil
King John, the left legs of each, and a crown.[^aima-model]

$$
% caption: A first-order model (after AIMA Fig. 8.2) with five objects, the binary
% relation $Brother$ holding symmetrically between R and J, the binary $OnHead$
% relation, three unary relations shown as labels on objects, and the total unary
% function $LeftLeg$ mapping each person to a leg.
\begin{tikzpicture}[>=stealth, font=\small,
  obj/.style={draw, circle, minimum size=13mm, inner sep=0pt, font=\footnotesize},
  leg/.style={draw, ellipse, minimum width=11mm, minimum height=16mm, inner sep=0pt, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % crown
  \node[obj] (crown) at (3.0,3.1) {crown};
  % people
  \node[obj] (R) at (0,0.6) {R};
  \node[obj] (J) at (6.0,0.6) {J};
  % legs
  \node[leg] (RL) at (0,-2.4) {leg-of-R};
  \node[leg] (JL) at (6.0,-2.4) {leg-of-J};
  % brother relation (both directions), routed clear of the crown
  \draw[->, thick] (R) to[bend left=22] node[above, font=\scriptsize] {brother} (J);
  \draw[->, thick] (J) to[bend left=22] node[below, font=\scriptsize] {brother} (R);
  % on head
  \draw[->, red, thick] (crown) to[bend left=12] node[right, font=\scriptsize, text=red] {on-head} (J);
  % left-leg function
  \draw[->, acc, thick] (R) -- node[left, font=\scriptsize, text=acc] {LeftLeg} (RL);
  \draw[->, acc, thick] (J) -- node[right, font=\scriptsize, text=acc] {LeftLeg} (JL);
  % unary-relation labels (properties)
  \node[font=\scriptsize, anchor=east, text=black] at (-0.9,0.6) {person};
  \node[font=\scriptsize, anchor=west, text=black] at (6.9,1.05) {person};
  \node[font=\scriptsize, anchor=west, text=black] at (6.9,0.15) {king};
  \node[font=\scriptsize, anchor=south, text=black] at (3.0,4.0) {crown};
\end{tikzpicture}
$$

The relations in this model are literally sets of tuples. The brotherhood
relation is symmetric, so it contains two tuples:

$$
\{\, \langle \text{Richard}, \text{John} \rangle,\ \langle \text{John}, \text{Richard} \rangle \,\}.
$$

The _on-head_ relation contains the single tuple $\langle \text{crown},
\text{John} \rangle$. The unary relations are the sets of objects with a
property: _person_ holds of both Richard and John, _king_ holds only of John
(Richard is dead at this point in the story), _crown_ holds only of the crown.
The one function, _left leg_, maps each person to that person's leg. Because
functions must be total, even the crown and the legs must map to _something_
under $LeftLeg$; the standard trick is an invisible object that is the left leg
of everything without one, which does no harm as long as no assertion mentions
the left legs of legless things.[^aima-total]

### Symbols and the interpretation

A model supplies objects; the other half is the **interpretation** that connects
the vocabulary to them. The vocabulary comes in three kinds of symbol, which by
convention begin with an uppercase letter:[^aima-symbols]

- **Constant symbols** stand for objects: $Richard$, $John$.
- **Predicate symbols** stand for relations: $Brother$, $OnHead$, $Person$,
  $King$, $Crown$. Each carries an **arity** fixing its number of arguments.
- **Function symbols** stand for functions: $LeftLeg$, $Mother$, also with an
  arity.

> **Definition (Interpretation).** The part of a model that specifies exactly
> which objects, relations, and functions the constant, predicate, and function
> symbols refer to. The **intended interpretation** is the one the author has in
> mind; a model is a domain _together with_ an interpretation, and every model
> must fix the referent of every symbol.

The intended interpretation for the kinship scene sends $Richard$ to Richard the
Lionheart, $John$ to King John, $Brother$ to the two-tuple brotherhood set,
$LeftLeg$ to the leg mapping, and so on. Nothing forces this choice. There is
also an interpretation that maps $Richard$ to the crown and $John$ to a leg — with
five objects there are $5 \times 5 = 25$ interpretations of the two constant
symbols alone, and not every object needs a name. This freedom mirrors
propositional logic, where a model can make $Cloudy$ and $Sunny$ both true; it is
the knowledge base's job to rule out the models that clash with what we know.

$$
% caption: The set of all models is unbounded (after AIMA Fig. 8.4): models vary
% in how many objects they hold — from one up to infinity — and in how the two
% constant symbols R and J map onto them, so enumerating models to check
% entailment is infeasible for first-order logic.
\begin{tikzpicture}[>=stealth, font=\small,
  world/.style={draw, circle, minimum size=15mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  % model 1: one object, both constants map to it
  \node[world] (w1) at (0,0) {};
  \fill[black] (0,0) circle (1.6pt);
  \node[font=\scriptsize] at (-0.35,1.15) {R};
  \node[font=\scriptsize] at ( 0.35,1.15) {J};
  \draw[->, black] (-0.35,0.95) -- (-0.1,0.12);
  \draw[->, black] ( 0.35,0.95) -- ( 0.1,0.12);
  % model 2: two objects
  \node[world] (w2) at (3.0,0) {};
  \fill[black] (2.7,0.25) circle (1.6pt);
  \fill[black] (3.3,-0.3) circle (1.6pt);
  \node[font=\scriptsize] at (2.65,1.15) {R};
  \node[font=\scriptsize] at (3.35,1.15) {J};
  \draw[->, black] (2.65,0.95) -- (2.7,0.4);
  \draw[->, black] (3.35,0.95) -- (3.3,-0.15);
  % model 3: three objects
  \node[world] (w3) at (6.0,0) {};
  \fill[black] (5.7,0.3) circle (1.6pt);
  \fill[black] (6.3,0.05) circle (1.6pt);
  \fill[black] (6.0,-0.4) circle (1.6pt);
  \node[font=\scriptsize] at (5.65,1.15) {R};
  \node[font=\scriptsize] at (6.35,1.15) {J};
  \draw[->, black] (5.65,0.95) -- (5.7,0.45);
  \draw[->, black] (6.35,0.95) -- (6.3,0.2);
  % ellipsis
  \node[font=\large] at (8.1,0) {. . .};
\end{tikzpicture}
$$

Because the number of objects ranges from one to infinity, the set of models is
unbounded, and checking entailment by enumerating models — the method that works
for propositional logic — is not feasible here. Even bounding the objects, the
count explodes: for two constants and one binary relation there are already
$137{,}506{,}194{,}466$ models with six or fewer objects.

## Syntax: terms and sentences

With the semantics fixed, the syntax is a short grammar (AIMA's Figure 8.3).
Everything is built from **terms** and **sentences**.

$$
% caption: The syntax of first-order logic in Backus-Naur form (after AIMA Fig.
% 8.3). A sentence is atomic or complex; an atomic sentence is a predicate applied
% to terms or an equality of terms; a term is a function applied to terms, a
% constant, or a variable; operator precedence runs (from KaTeX in the caption)
% $\lnot,\ =,\ \land,\ \lor,\ \Rightarrow,\ \Leftrightarrow$, and a quantifier holds
% over everything to its right.
\begin{tikzpicture}[>=stealth, font=\small,
  cat/.style={anchor=east, font=\footnotesize},
  rhs/.style={anchor=west, font=\footnotesize, text=black!75}]
  \definecolor{acc}{HTML}{2348F2}
  \node[cat] at (0,3.0)  {Sentence};
  \node[rhs] at (0.5,3.0) {AtomicSentence  or  ComplexSentence};
  \node[cat] at (0,2.3)  {AtomicSentence};
  \node[rhs] at (0.5,2.3) {Predicate(Term, ...)  or  Term = Term};
  \node[cat] at (0,1.6)  {ComplexSentence};
  \node[rhs] at (0.5,1.6) {not S  /  S and S  /  S or S  /  S $\Rightarrow$ S  /  S $\Leftrightarrow$ S};
  \node[cat] at (0,0.9)  {};
  \node[rhs] at (0.5,0.9) {Quanti\/f\/ier Variable, ...  S};
  \node[cat] at (0,0.2)  {Term};
  \node[rhs] at (0.5,0.2) {Function(Term, ...)  /  Constant  /  Variable};
  \node[cat] at (0,-0.5) {Quanti\/f\/ier};
  \node[rhs] at (0.5,-0.5) {"for all"  /  "exists"};
  \draw[acc, thick] (-2.1,2.65) -- (7.5,2.65);
\end{tikzpicture}
$$

> **Definition (Term).** A logical expression that refers to an object. A constant
> ($John$) is a term; a variable ($x$) is a term; and a function symbol applied to
> terms — $LeftLeg(John)$ — is a **complex term**. A complex term is not a
> subroutine call that "returns a value"; it is just a complicated name for an
> object. A term with no variables is a **ground term**.

The semantics of a term is direct: given a term $f(t_1, \ldots, t_n)$, the
interpretation fixes the function $F$ that $f$ denotes and the objects $d_1,
\ldots, d_n$ that the argument terms denote, and the whole term denotes
$F(d_1, \ldots, d_n)$. If $John$ denotes King John and $LeftLeg$ denotes the leg
mapping, then $LeftLeg(John)$ denotes King John's left leg. The interpretation
fixes the referent of every term.

> **Definition (Atomic sentence).** A predicate symbol applied to a list of terms:
> $Brother(Richard, John)$. Its arguments may themselves be complex terms, as in
> $Married(Father(Richard), Mother(John))$. An atomic sentence is **true** in a
> model exactly when the relation named by the predicate holds among the objects
> named by the terms.

Complex sentences combine atomic ones with the same connectives as propositional
logic — $\lnot$, $\land$, $\lor$, $\Rightarrow$, $\Leftrightarrow$ — with the
same truth tables. Under the intended interpretation of the kinship model, all
four of these are true:[^aima-complex]

$$
\lnot Brother(LeftLeg(Richard), John), \qquad
Brother(Richard, John) \land Brother(John, Richard),
$$
$$
King(Richard) \lor King(John), \qquad
\lnot King(Richard) \Rightarrow King(John).
$$

## Quantifiers

The point of objects is being able to quantify over them. First-order
logic has two standard quantifiers, **universal** $\forall$ and **existential**
$\exists$.[^aima-quant]

### Universal quantification, $\forall$

The rule "all kings are persons" is written

$$
\forall x \; King(x) \Rightarrow Person(x).
$$

$\forall$ reads "for all"; $x$ is a **variable** (lowercase by convention). The
semantics is careful but intuitive: $\forall x \; P$ is true in a model when $P$
is true under every **extended interpretation** that assigns $x$ to some domain
object. In the kinship model that means checking five extended interpretations,
one sending $x$ to each object, and confirming the sentence holds in all of them:

$$
\begin{aligned}
& \text{Richard is a king} \Rightarrow \text{Richard is a person}, \\
& \text{John is a king} \Rightarrow \text{John is a person}, \\
& \text{Richard's leg is a king} \Rightarrow \text{Richard's leg is a person}, \\
& \text{John's leg is a king} \Rightarrow \text{John's leg is a person}, \\
& \text{the crown is a king} \Rightarrow \text{the crown is a person}.
\end{aligned}
$$

Only John is actually a king, so only the second implication has a true premise —
and it holds. The other four are true _vacuously_: an implication is true
whenever its premise is false, so the claims about legs and crowns cost nothing.
That vacuous truth is why $\Rightarrow$ is the connective that pairs with
$\forall$: it asserts the conclusion only for objects that satisfy the premise and
stays silent about the rest.

> **Definition (Universal quantifier).** $\forall x \; P$ is true in a model when
> $P$ is true for every object that $x$ could denote. It states a general law over
> all objects and reduces, in a finite model, to the conjunction of $P$ over each
> object.

The standard mistake is to reach for $\land$ instead of $\Rightarrow$:

$$
\forall x \; King(x) \land Person(x).
$$

This says every object in the universe is _both_ a king and a person — that
Richard's leg is a king, that the crown is a king. It is far too strong and
plainly not what we meant. Use $\Rightarrow$ with $\forall$.

### Existential quantification, $\exists$

To say that King John has a crown on his head — some object is a crown and is on
John's head — we write

$$
\exists x \; Crown(x) \land OnHead(x, John).
$$

$\exists$ reads "there exists" or "for some." Its semantics is dual to $\forall$:
$\exists x \; P$ is true when $P$ holds in _at least one_ extended interpretation.
Checking the crown object makes both conjuncts true, so the sentence is true in
the model.

> **Definition (Existential quantifier).** $\exists x \; P$ is true in a model
> when $P$ is true for at least one object that $x$ could denote. It reduces, in a
> finite model, to the disjunction of $P$ over each object.

Here the natural connective is $\land$, and the mirror-image mistake is to use
$\Rightarrow$:

$$
\exists x \; Crown(x) \Rightarrow OnHead(x, John).
$$

Because an implication is satisfied by _any_ object that fails its premise, this
sentence is true as soon as some object is not a crown — which is trivially the
case — so it says almost nothing. Use $\land$ with $\exists$.

$$
% caption: The two standard errors. With $\forall$, using $\land$ instead of
% $\Rightarrow$ claims every object satisfies both predicates (far too strong);
% with $\exists$, using $\Rightarrow$ instead of $\land$ is satisfied by any object
% that fails the premise (far too weak). The diagonal pairings are the correct ones.
\begin{tikzpicture}[>=stealth, font=\small,
  cell/.style={draw, minimum width=34mm, minimum height=15mm, align=center, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[font=\footnotesize] at (0,1.6)  {with "for all"};
  \node[font=\footnotesize] at (4.2,1.6) {with "exists"};
  \node[cell, draw=acc, text=acc] (ai) at (0,0)   {use $\Rightarrow$ \\ correct: a law};
  \node[cell, text=red] (aa) at (4.2,0) {use and \\ wrong: too strong};
  \node[cell, text=red] (ei) at (0,-2.0) {use $\Rightarrow$ \\ wrong: too weak};
  \node[cell, draw=acc, text=acc] (ea) at (4.2,-2.0) {use and \\ correct: a witness};
\end{tikzpicture}
$$

### A worked interpretation: evaluating $\forall x \; King(x) \Rightarrow Person(x)$

A universal sentence is true when it holds under every extended interpretation.
Carrying one through on the five-object kinship model shows the procedure an
inference engine must eventually mechanize. Number the five domain objects: $o_1$
is Richard, $o_2$ is John, $o_3$ is Richard's leg, $o_4$ is John's leg, $o_5$ is
the crown. The unary relations are fixed by the model: $Person = \{o_1, o_2\}$ and
$King = \{o_2\}$. Evaluating $\forall x \; King(x) \Rightarrow Person(x)$ means
building five extended interpretations $I_{x \mapsto o_i}$, one per object, and
checking the body $King(x) \Rightarrow Person(x)$ in each.

$$
% caption: Evaluating $\forall x\; King(x)\Rightarrow Person(x)$ over the five
% kinship objects. Each row is one extended interpretation; a filled dot marks
% membership in $King$ or $Person$. The implication is true in every row — once
% because both hold ($o_2$), four times vacuously because the premise fails — so
% the universal is true.
\begin{tikzpicture}[>=stealth, font=\small,
  dot/.style={circle, fill=black, minimum size=3.4pt, inner sep=0pt},
  ndot/.style={circle, draw=black, minimum size=3.4pt, inner sep=0pt},
  hdr/.style={font=\footnotesize, text=black}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % column headers
  \node[hdr] at (0,0.7)  {object};
  \node[hdr] at (2.4,0.7) {King};
  \node[hdr] at (4.2,0.7) {Person};
  \node[hdr] at (6.6,0.7) {body value};
  \draw[black] (-0.9,0.42) -- (7.9,0.42);
  % rows: label, King?, Person?, result
  \foreach \r/\y/\lab/\k/\p/\res/\col in {
    1/0/Richard/n/y/true (vacuous)/blk,
    2/-0.75/John/y/y/true/acc,
    3/-1.5/leg-of-R/n/n/true (vacuous)/blk,
    4/-2.25/leg-of-J/n/n/true (vacuous)/blk,
    5/-3.0/crown/n/n/true (vacuous)/blk} {
    \node[font=\footnotesize, anchor=west] at (-0.9,\y) {\lab};
  }
  % King column dots
  \node[ndot] at (2.4,0)    {}; \node[dot] at (2.4,-0.75) {};
  \node[ndot] at (2.4,-1.5) {}; \node[ndot] at (2.4,-2.25) {}; \node[ndot] at (2.4,-3.0) {};
  % Person column dots
  \node[dot] at (4.2,0)    {}; \node[dot] at (4.2,-0.75) {};
  \node[ndot] at (4.2,-1.5) {}; \node[ndot] at (4.2,-2.25) {}; \node[ndot] at (4.2,-3.0) {};
  % results
  \node[font=\footnotesize, anchor=west] at (5.7,0)     {true (vacuous)};
  \node[font=\footnotesize, anchor=west, text=acc] at (5.7,-0.75) {true};
  \node[font=\footnotesize, anchor=west] at (5.7,-1.5)  {true (vacuous)};
  \node[font=\footnotesize, anchor=west] at (5.7,-2.25) {true (vacuous)};
  \node[font=\footnotesize, anchor=west] at (5.7,-3.0)  {true (vacuous)};
  \draw[black] (-0.9,-3.35) -- (7.9,-3.35);
  \node[font=\footnotesize, text=acc, anchor=west] at (-0.9,-3.75) {conjunction over all rows: TRUE};
\end{tikzpicture}
$$

Only the John row ($o_2$) has a true premise, and there the conclusion also holds,
so that row is true outright. The other four rows are true because their premise
$King(x)$ is false; an implication with a false antecedent is true regardless. The
universal is the conjunction of the five body values, so it comes out **true**. If
we had used $\land$ in place of $\Rightarrow$, the body would read $King(x) \land
Person(x)$, which is false in the very first row (Richard is a person but not a
king), and the whole sentence would collapse to false — the concrete form of the
"too strong" error from the diagram above.

### Nested quantifiers and their order

Multiple quantifiers combine to express richer sentences. Consecutive quantifiers
of the same type collapse into one: "brothers are siblings" is $\forall x \,
\forall y \; Brother(x, y) \Rightarrow Sibling(x, y)$, and siblinghood's symmetry
is $\forall x, y \; Sibling(x, y) \Leftrightarrow Sibling(y, x)$. The subtle case
is mixing types, where **order matters**. "Everybody loves somebody" is

$$
\forall x \; \exists y \; Loves(x, y),
$$

which says every person has _some_ object (possibly a different one each time)
that they love. Swapping the quantifiers gives a different claim, "there is
someone who is loved by everyone":

$$
\exists y \; \forall x \; Loves(x, y).
$$

The first says everyone has the property of loving someone; the second says a
single individual has the property of being loved by all. When the same variable
name appears under two quantifiers, the variable belongs to the innermost one that
mentions it, so to avoid confusion use distinct names for nested variables.

A concrete model shows the two readings really do differ. Take three people $a$,
$b$, $c$ and let the $Loves$ relation be $\{ \langle a, b \rangle, \langle b, b
\rangle, \langle c, b \rangle \}$ — everyone loves $b$, and nobody loves anyone
else. Evaluate the outer-$\forall$ sentence $\forall x \; \exists y \; Loves(x, y)$
by fixing each $x$ and asking whether _some_ witness $y$ exists: $x = a$ is
witnessed by $y = b$, $x = b$ by $y = b$, $x = c$ by $y = b$. Every $x$ finds a
witness, so the sentence is **true**. Now the outer-$\exists$ sentence $\exists y
\; \forall x \; Loves(x, y)$: here a single $y$ must work for _every_ $x$.
Object $b$ does — $Loves(a, b)$, $Loves(b, b)$, $Loves(c, b)$ all hold — so this
sentence is also true in this model.

$$
% caption: The $Loves$ relation $\{\langle a,b\rangle,\langle b,b\rangle,\langle
% c,b\rangle\}$ as arrows into $b$. Both nested sentences are true here, but they
% assert different things: $\forall x\,\exists y$ lets the witness $y$ depend on
% $x$, while $\exists y\,\forall x$ demands one witness $b$ good for all $x$. Delete
% the arrow from $c$ and the second sentence fails while the first can still hold.
\begin{tikzpicture}[>=stealth, font=\small,
  per/.style={draw, circle, minimum size=10mm, inner sep=0pt, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[per] (a) at (0,1.6)  {a};
  \node[per] (c) at (0,-1.6) {c};
  \node[per, draw=acc, text=acc] (b) at (3.4,0) {b};
  % arrows everyone -> b
  \draw[->, thick] (a) -- (b);
  \draw[->, thick] (c) -- (b);
  % b loves itself (self-loop)
  \draw[->, thick] (b) to[out=40, in=-40, looseness=6] (b);
  \node[font=\scriptsize, text=black, anchor=west] at (4.15,0) {loves self};
  \node[font=\scriptsize, text=acc, anchor=south] at (3.4,0.85) {witness for all};
\end{tikzpicture}
$$

The equivalence fails in general. Delete the pair $\langle c, b \rangle$ and add
$\langle c, a \rangle$: now $c$ loves $a$ instead of $b$. The outer-$\forall$
sentence still holds — every person loves someone — but no single object is loved
by everyone, so the outer-$\exists$ sentence is now false. This is the asymmetry
that makes quantifier order carry meaning: $\forall x \, \exists y$ always follows
from $\exists y \, \forall x$, but not the reverse.

### The connection between $\forall$ and $\exists$

The two quantifiers are linked through negation, and obey De Morgan's rules — as
they should, since $\forall$ is really a conjunction over the universe and
$\exists$ a disjunction. "Everyone dislikes parsnips" is the same as "no one likes
them":

$$
\forall x \; \lnot Likes(x, \text{Parsnips}) \quad\equiv\quad \lnot \exists x \; Likes(x, \text{Parsnips}).
$$

More generally,

$$
\forall x \; \lnot P \equiv \lnot \exists x \; P, \qquad
\lnot \forall x \; P \equiv \exists x \; \lnot P, \qquad
\forall x \; P \equiv \lnot \exists x \; \lnot P, \qquad
\exists x \; P \equiv \lnot \forall x \; \lnot P.
$$

So $\forall$ and $\exists$ are interdefinable, just as $\land$ and $\lor$ are. We
keep both because readability beats parsimony.

## Equality

First-order logic has one further way to build an atomic sentence: the **equality
symbol**, $=$. The sentence $Father(John) = Henry$ says the object denoted by
$Father(John)$ and the object denoted by $Henry$ are one and the same, and it is
true exactly when their referents coincide.[^aima-eq] Equality is what lets us
insist that two terms name _different_ objects. "Richard has at least two
brothers" needs it:

$$
\exists x, y \; Brother(x, Richard) \land Brother(y, Richard) \land \lnot(x = y).
$$

Without the final conjunct, the sentence is satisfied by taking $x$ and $y$ to be
the same brother, so it would be true even if Richard had only one. The
abbreviation $x \neq y$ stands for $\lnot(x = y)$.


## Where this continues

We now have the full language: a world of objects with relations and functions
over them, a model that fixes truth, terms and sentences, the two quantifiers, and
equality. That is enough to _write_ knowledge down. What remains is the pragmatics
of using it — the semantic shortcuts a database makes, where first-order logic
stops and higher-order begins, the Tell/Ask interface, and the disciplined process
of turning a real domain into axioms.

This continues in
[First-Order Logic in Use](/artificial-intelligence/logic-and-planning/first-order-logic-in-use),
which covers database semantics, the first-order/higher-order boundary, and the
seven-step knowledge-engineering process on the kinship and digital-circuit
domains.

[^aima-repr]: **AIMA**, §8.1 — Representation Revisited: propositional logic is declarative and compositional but lacks the expressive power to describe an environment with many objects concisely, forcing a separate breeze-pit rule per square.
[^aima-fol]: **AIMA**, Ch. 8 introduction: first-order logic (also first-order predicate calculus, FOL or FOPC) is expressive enough to represent much commonsense knowledge and subsumes or founds many other representation languages.
[^aima-natural]: **AIMA**, §8.1.2 — Combining the best of formal and natural languages: keep propositional logic's declarative, compositional, context-independent foundation and borrow from natural language the ontology of objects (nouns), relations (verbs), and functions.
[^aima-commit]: **AIMA**, §8.1, Figure 8.1 — Formal languages and their ontological and epistemological commitments: propositional logic commits to facts; first-order logic to facts, objects, and relations; both share true/false/unknown epistemology.
[^aima-orf]: **AIMA**, §8.1.2 — objects, relations (including unary properties and $n$-ary relations), and functions as relations with a single value per input; almost any assertion decomposes into these.
[^aima-model]: **AIMA**, §8.2.1, Figure 8.2 — Models for first-order logic: the five-object kinship model with domain, two binary relations ($Brother$, $OnHead$), three unary relations, and one unary function $LeftLeg$; a relation is a set of tuples.
[^aima-total]: **AIMA**, §8.2.1 — Total functions: models require a value for every input tuple, handled by an invisible object that is the left leg of everything without one.
[^aima-symbols]: **AIMA**, §8.2.2 — Symbols and interpretations: constant, predicate, and function symbols, each with an arity; the interpretation specifies their referents, and the intended interpretation is only one of many possible.
[^aima-complex]: **AIMA**, §8.2.4–8.2.5 — Atomic and complex sentences: an atomic sentence is a predicate applied to terms (arguments may be complex terms) and is true when the relation holds among the referents; connectives build complex sentences as in propositional calculus.
[^aima-quant]: **AIMA**, §8.2.6 — Quantifiers: universal ($\forall$) with extended interpretations and its pairing with $\Rightarrow$; existential ($\exists$) with its pairing with $\land$; the $\land$-with-$\forall$ and $\Rightarrow$-with-$\exists$ mistakes; nested quantifiers, order, and the $\forall$/$\exists$ connection through negation and De Morgan's rules.
[^aima-eq]: **AIMA**, §8.2.7 — Equality: the equality symbol is true when its two terms have the same referent; $\lnot(x = y)$ (abbreviated $x \neq y$) is needed to state that two objects are distinct.