MODULE 4 – PART 2

FIRST ORDER PREDICATE LOGIC

FIRST ORDER LOGIC
• First-order logic, a much more expressive language
than the propositional logic
Objects, Relations and Functions
• The elements nouns and noun phrases that refer to
objects (squares, pits, wumpus) and verbs and verb
phrases that refer to relations among objects (is
breezy, is adjacent to, shoots).
• Some of these relations are functions—relations in
which there is only one “value” for a given “input.”
Examples of objects, relations, and functions:
• Objects: people, houses, numbers, theories, Ronald
McDonald, colors, baseball games, wars, centuries ...
• Relations: these can be unary relations or properties
such as red, round, bogus, prime, multistoried ..., or
more general n-ary relations such as brother of, bigger
than, inside, part of, has color, occurred after, owns,
comes between, ...
• Functions: father of, best friend, third inning of, one
more than, beginning of ...
• Indeed, almost any assertion can be thought of as referring to objects and
properties or relations.
• Some examples follow:
• “One plus two equals three.”
Objects: one, two, three, one plus two;
Relation: equals;
Function: plus.
(“One plus two” is a name for the object that is obtained by applying the
function “plus” to the objects “one” and “two.” “Three” is another name for this
object.)
• “Squares neighboring the wumpus are smelly.”
Objects: wumpus, squares;
Property: smelly;
Relation: neighboring.
• “Evil King John ruled England in 1200.”
Objects: John, England, 1200;
Relation: ruled;
Properties: evil, king.
Difference between propositional and first-
order logic
• The primary difference between propositional and first-order logic lies in the
ontological commitment made by each language—that is, what it assumes
about the nature of reality.
• Mathematically, this commitment is expressed through the nature of the formal
models with respect to which the truth of sentences is defined.
• For example, propositional logic assumes that there are facts that either hold or
do not hold in the world. Each fact can be in one of two states: true or false, and
each model assigns true or false to each proposition symbol.
• First-order logic assumes more; namely, that the world consists of objects with
certain relations among them that do or do not hold.
• The formal models are correspondingly more complicated than those for
propositional logic.
• Special-purpose logics make still further ontological
commitments; for example, temporal logic assumes
that facts hold at particular times and that those times
(which may be points or intervals) are ordered.
• Thus, special-purpose logics give certain kinds of
objects (and the axioms about them) “first class”
status within the logic, rather than simply defining
them within the knowledge base.
• A logic can also be characterized by its epistemological
commitments—the possible states of knowledge that
it allows with respect to each fact.
• In both propositional and first order logic, a sentence
represents a fact and the agent either believes the
sentence to be true, believes it to be false, or has no
opinion.
• These logics therefore have three possible states of
knowledge regarding any sentence.
• Systems using probability theory, on the other hand,
can have any degree of belief, ranging from 0 (total
disbelief) to 1 (total belief).
Syntax and Semantics of First – Order Logic
• The domain of a model is the set of objects or domain elements it
contains.
• The domain is required to be nonempty—every possible world must
contain at least one object.
• Mathematically speaking, it doesn’t matter what these objects are—
all that matters is how many there are in each particular model.
Figure 8.2 shows a model with five objects:
• Objects: Richard the Lionheart, King of England from 1189 to 1199; his
younger brother, the evil King John, who ruled from 1199 to 1215; the left
legs of Richard and John; and a crown.
• The objects in the model may be related in various ways.
• In the figure, Richard and John are brothers.
• Formally speaking, a relation is just the set of tuples of objects that are
related. (A tuple is a collection of objects arranged in a fixed order and is
written with angle brackets surrounding the objects.)
• Thus, the brotherhood relation in this model is the set
{ <Richard the Lionheart, King John>, <King John, Richard the Lionheart >} .
• The crown is on King John’s head, so the “on head” relation contains just
one tuple, <the crown, King John>.
• The “brother” and “on head” relations are binary relations—that is, they
relate pairs of objects.
• The model also contains unary relations, or properties: the
“person” property is true of both Richard and John; the
“king” property is true only of John (presumably because
Richard is dead at this point); and the “crown” property is
true only of the crown.
• Certain kinds of relationships are best considered as
functions, in that a given object must be related to exactly
one object in this way.
• For example, each person has one left leg, so the model has
a unary “left leg” function that includes the following
mappings:
<Richard the Lionheart >→ Richard’s left leg
<King John> → John’s left leg . ------------- (Eqn.8.2)
• Strictly speaking, models in first-order logic require total
functions, that is, there must be a value for every input
tuple.
• Thus, the crown must have a left leg and so must each of the
left legs.
Symbols and Interpretations
• The basic syntactic elements of first-order logic are the symbols that
stand for objects, relations, and functions
• Three kinds of symbols: constant symbols, which stand for objects;
predicate symbols, which stand for relations; and function symbols,
which stand for functions.
• These symbols will begin with uppercase letters.
• For example, we might use the constant symbols Richard and John;
the predicate symbols Brother , OnHead, Person, King, and Crown;
and the function symbol LeftLeg.
• ARITY : Each predicate and function symbol comes with an arity that
fixes the number of arguments.
Intended Interpretation
• As in propositional logic, every model must provide the
information required to determine if any given sentence is
true or false.
• Thus, in addition to its objects, relations, and functions, each
model includes an interpretation that specifies exactly which
objects, relations and functions are referred to by the
constant, predicate, and function symbols. One possible
interpretation is called as Intended Interpretation.
Terms
• A term is a logical expression that refers to an object.
• Constant symbols are therefore terms, but it is not always
convenient to have a distinct symbol to name every object.
• Consider a term f(t1,...,tn). The function symbol f refers to some
function in the model (call it F); the argument terms refer to
objects in the domain (call them d1,...,dn); and the term as a
whole refers to the object that is the value of the function F
applied to d1,...,dn.
• For example, suppose the LeftLeg function symbol refers to the
function shown in Equation (8.2) and John refers to King John,
then LeftLeg(John) refers to King John’s left leg.
• In this way, the interpretation fixes the referent of every term.
Atomic sentences
• The terms for referring to objects and predicate symbols for referring
to relations, we can put them together to make atomic sentences that
state facts. An atomic sentence (or atom for short) is formed from a
predicate symbol optionally followed by a parenthesized list of terms,
such as Brother (Richard, John).
• An atomic sentence is true in a given model if the relation referred to
by the predicate symbol holds among the objects referred to by the
arguments.
Complex sentences
• We can use logical connectives to construct more complex
sentences, with the same syntax and semantics as in
propositional calculus.
• Here are four sentences that are true in the model of Figure
8.2 under our intended interpretation:
¬Brother (LeftLeg(Richard), John)
Brother (Richard, John) ∧ Brother (John, Richard)
King(Richard) ∨ King(John)
¬King(Richard) ⇒ King(John) .
Quantifiers
• Once we have a logic that allows objects, it is only natural to
want to express properties of entire collections of objects,
instead of enumerating the objects by name. Quantifiers let
us do this.
• First-order logic contains two standard quantifiers, called
universal and existential.
Universal quantification (∀)
“All kings are persons,”
• is written in first-order logic as
∀ x King(x) ⇒ Person(x) .
• ∀ is usually pronounced “For all ...”. (Remember that the upside-down A
stands for “all.”)
• Thus, the sentence says, “For all x, if x is a king, then x is a person.”
• The symbol x is called a variable. By convention, variables are lowercase
letters.
• A variable is a term all by itself, and as such can also serve as the
argument of a function—for example, LeftLeg(x).
• A term with no variables is called a ground term.
• Intuitively, the sentence ∀ x P, where P is any logical
expression, says that P is true for every object x.
• More precisely, ∀ x P is true in a given model if P is
true in all possible extended interpretations
constructed from the interpretation given in the
model, where each extended interpretation specifies
a domain element to which x refers.
Existential quantification (∃)
• Universal quantification makes statements about every object.
• Similarly, we can make a statement about some object in the universe
without naming it, by using an existential quantifier.
• To say, for example, that King John has a crown on his head, we write
∃ x Crown(x) ∧ OnHead(x, John) .
• ∃x is pronounced “There exists an x such that ...” or “For some x...”.
• Intuitively, the sentence ∃ x P says that P is true for at least one object
x.
• More precisely, ∃ x P is true in a given model if P is true in at least one
extended interpretation that assigns x to a domain element.
• Just as ⇒ appears to be the natural connective to use
with ∀, ∧ is the natural connective to use with ∃.
Nested quantifiers
• Used to express more complex sentences using multiple quantifiers.
• The simplest case is where the quantifiers are of the same type.
• For example, “Brothers are siblings” can be written as
∀ x ∀ y Brother (x, y) ⇒ Sibling(x, y) .
• Consecutive quantifiers of the same type can be written as one
quantifier with several variables.
• For example, to say that siblinghood is a symmetric relationship,
we can write
∀ x, y Sibling(x, y) ⇔ Sibling(y, x) .
• “Everybody loves somebody”
means that for every person, there is someone that person loves:
∀ x ∃ y Loves(x, y) .
• On the other hand, to say “There is someone who is loved by everyone,”
we write ∃ y ∀ x Loves(x, y) .
• The order of quantification is therefore very important. It becomes
clearer if we insert parentheses.
• ∀ x (∃ y Loves(x, y)) says that everyone has a particular property, namely,
the property that they love someone.
• On the other hand, ∃ y (∀ x Loves(x, y)) says that someone in the world
has a particular property, namely the property of being loved by
everybody.
 Connections between ∀ and ∃
• The two quantifiers are actually intimately connected with each
other, through negation.
• Asserting that everyone dislikes parsnips is the same as asserting
there does not exist someone who likes them, and vice versa:
∀ x ¬Likes(x,Parsnips ) is equivalent to ¬∃ x Likes(x,Parsnips) .
• We can go one step further: “Everyone likes ice cream” means
that there is no one who does not like ice cream:
∀ x Likes(x,IceCream) is equivalent to ¬∃ x ¬Likes(x,IceCream)
.
• Because ∀ is really a conjunction over the universe of objects and
∃ is a disjunction, it should not be surprising that they obey De
Morgan’s rules.
• The De Morgan rules for quantified and unquantified sentences
are as follows:
∀ x ¬P ≡ ¬∃ x P ¬(P ∨ Q) ≡ ¬P ∧ ¬Q
¬∀ x P ≡ ∃ x ¬P ¬(P ∧ Q) ≡ ¬P ∨ ¬Q
∀ x P ≡ ¬∃ x ¬P P ∧ Q ≡ ¬(¬P ∨ ¬Q)
∃ x P ≡ ¬∀ x ¬P P ∨ Q ≡ ¬(¬P ∧ ¬Q) .
Equality
• We can use the equality symbol to signify that two terms
refer to the same object.
• For example, Father (John) = Henry says that the object
referred to by Father (John) and the object referred to by
Henry are the same.
• Because an interpretation fixes the referent of any term,
determining the truth of an equality sentence is simply a
matter of seeing that the referents of the two terms are the
same object.
• To say that Richard has at least two brothers, we would write
∃ x, y Brother (x, Richard) ∧ Brother (y, Richard) ∧ ¬(x = y) .
⇒
.