First-Order Logic

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:¹

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.²

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.³ The table below places both logics on the spectrum of ontological commitments AIMA uses (its Figure 8.1).⁴

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.

The ontology: objects, relations, functions

The building blocks of a first-order world are three kinds of thing.⁵

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.⁶

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

The on-head relation contains the single tuple $⟨\text{crown},\text{John}⟩$. 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.⁷

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:⁸

• 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.

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.

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.

The semantics of a term is direct: given a term $f(t_1,\dots ,t_n)$, the interpretation fixes the function $F$ that $f$ denotes and the objects $d_1,\dots ,d_n$ that the argument terms denote, and the whole term denotes $F(d_1,\dots ,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.

Complex sentences combine atomic ones with the same connectives as propositional logic — $\neg$, $\wedge$, $\vee$, $\Rightarrow$, $\iff$ — with the same truth tables. Under the intended interpretation of the kinship model, all four of these are true:⁹

Quantifiers

The point of objects is being able to quantify over them. First-order logic has two standard quantifiers, universal $\forall$ and existential$\exists$.¹⁰

Universal quantification, $\forall$

The rule all kings are persons is written

$\forall$ reads for all; $x$ is a variable (lowercase by convention). The semantics is careful but intuitive: $\forall xP$ 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:

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.

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

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$ reads there exists or for some. Its semantics is dual to $\forall$: $\exists xP$ 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.

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

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 $\wedge$ with $\exists$.

A worked interpretation: evaluating $\forall xKing(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 xKing(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.

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 $\wedge$ in place of $\Rightarrow$, the body would read $King(x)\wedge 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 yBrother(x,y)\Rightarrow Sibling(x,y)$, and siblinghood's symmetry is $\forall x,ySibling(x,y)\iff Sibling(y,x)$. The subtle case is mixing types, where order matters. Everybody loves somebody is

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:

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 $\{⟨a,b⟩,⟨b,b⟩,⟨c,b⟩\}$ — everyone loves $b$, and nobody loves anyone else. Evaluate the outer-$\forall$ sentence $\forall x\exists yLoves(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 xLoves(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.

The equivalence fails in general. Delete the pair $⟨c,b⟩$ and add $⟨c,a⟩$: 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:

More generally,

So $\forall$ and $\exists$ are interdefinable, just as $\wedge$ and $\vee$ 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.¹¹ Equality is what lets us insist that two terms name different objects. Richard has at least two brothers needs it:

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\ne y$ stands for $\neg (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, which covers database semantics, the first-order/higher-order boundary, and the seven-step knowledge-engineering process on the kinship and digital-circuit domains.