FIRST-ORDER LOGIC

First order logic

• The language of first-order logic(predicate logic) is built around
objects and relations
• First-order logic can also express facts about some or all of the
objects in the universe.
• This enables one to represent general laws or rules
• 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
• This commitment is expressed through the nature of the formal
models with respect to which the truth of sentences is defined

• First-order logic (FOL), also known as Predicate Logic, extends

propositional logic by adding the ability to express statements about
objects and their relationships.
 First-order logic

• 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 are ordered
• Higher-order logic views the relations and functions referred to by
first-order logic as objects in themselves. This allows one to make
assertions about all relations
 SYNTAX AND SEMANTICS OF FIRST-ORDER LOGIC

Models for 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
• It doesn’t matter what these objects are—all that matters is
how many there are in each particular model
 Model for first-order logic

A model containing five objects, two binary relations, three unary relations
(indicated by labels on the objects), and one unary function, left-leg
 Model for FOL

Figure shows a model with five 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
• a crown.
 Model for FOL
• The objects in the model may be related in various ways
• Richard and John are brothers
• A relation is just the set of tuples of objects that are related
• 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)
• 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
 Symbols and interpretations
Constant symbols - stand for objects –
Ex: Richard and John
Predicate symbols - stand for relations –
Ex: Brother , OnHead, Person, King, and Crown
Function symbols - stand for functions
Ex: LeftLeg

Each predicate and function symbol comes with an arity that

fixes the number of arguments.
The syntax of first-order logic with equality,
specified in Backus–Naur form
• A term is a logical expression that refers to an object
• An atomic sentence is formed from a predicate symbol
optionally followed by a parenthesized list of terms
Ex: Brother (Richard, John)
• Atomic sentences can have complex terms as arguments.
Ex: Married(Father (Richard), Mother (John))
• We can use logical connectives to construct more complex
sentences, with the same syntax and semantics as in
propositional calculus
Ex:
Brother (Richard, John) ∧ Brother (John, Richard)
King(Richard) ∨ King(John)
¬King(Richard) ⇒ King(John)
 Quantifiers
• Universal quantification (∀)
“All kings are persons,” is written in first-order logic as ∀ x King(x) ⇒ Person(x)
• Existential quantification (∃)
King John has a crown on his head is written as
∃ x Crown(x) ∧ OnHead(x, John)
• Nested quantifiers
“Brothers are siblings” can be written as
∀ x ∀ y Brother (x, y) ⇒ Sibling(x, y)
∀ x, y Sibling(x, y) ⇔ Sibling(y, x)
“Everybody loves somebody” can be written as
∀ x ∃ y Loves(x, y)
“There is someone who is loved by everyone”
∃ y ∀ x Loves(x, y) .
 Connections between ∀ and ∃
• ∀ x ¬Likes(x,Parsnips ) is equivalent to
¬∃ x Likes(x,Parsnips)
“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, 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
Richard has at least two brothers can be
written as
∃ x, y Brother (x, Richard) ∧ Brother (y,
Richard) ∧ ¬(x = y)
 USING FIRST-ORDER LOGIC
Assertions and queries in first-order logic
• Sentences are added to a knowledge base using TELL, Such sentences are
called assertions.
• For example, we can assert that John is a king, Richard is a person, and all
kings are persons:
TELL(KB, King(John))
TELL(KB, Person(Richard))
TELL(KB, ∀ x King(x) ⇒ Person(x))
• We can ask questions of the knowledge base using ASK.
• For example, ASK(KB, King(John)) returns true.
• Questions asked with ASK are called queries or goals.
• Generally speaking, any query that is logically entailed by the knowledge base
should be answered affirmatively.
• For example, given the two preceding assertions,
the query ASK(KB, Person(John)) should also return true.
• We can ask quantified queries, such as ASK(KB, ∃ x Person(x)) .
 The kinship domain
we consider the domain of family relationships, or kinship
For example,
One’s mother is one’s female parent:
∀ m, c Mother (c) = m ⇔ Female(m) ∧ Parent(m, c) .
One’s husband is one’s male spouse:
∀ w, h Husband(h, w) ⇔ Male(h) ∧ Spouse(h, w) .
Male and female are disjoint categories:
∀ x Male(x) ⇔ ¬Female(x) .
Parent and child are inverse relations:
∀ p, c Parent(p, c) ⇔ Child(c, p) .
A grandparent is a parent of one’s parent:
∀ g, c Grandparent(g, c) ⇔ ∃ p Parent(g, p) ∧ Parent(p, c) .
A sibling is another child of one’s parents:
∀ x, y Sibling(x, y) ⇔ x = y ∧ ∃ p Parent(p, x) ∧ Parent(p, y)
 KNOWLEDGE ENGINEERING IN FIRST-ORDER
LOGIC
• General process of knowledge-base construction
• A knowledge engineer is someone who investigates a
particular domain, learns what concepts are
important in that domain, and creates a formal
representation of the objects and relations in the
domain
 The knowledge-engineering process
• Identify the task - The knowledge engineer must delineate the range of questions
that the knowledge base will support and the kinds of facts that will be available
for each specific problem instance
• Assemble the relevant knowledge - The knowledge engineer might already be an
expert in the domain, or might need to work with real experts to extract what they
know—a process called knowledge acquisition
• Decide on a vocabulary of predicates, functions, and constants - translate the
important domain-level concepts into logic-level names
• Encode general knowledge about the domain - The knowledge engineer
writes down the axioms for all the vocabulary terms. This pins down the
meaning of the terms, enabling the expert to check the content
• Encode a description of the specific problem instance - If the ontology is well
thought out, this step will be easy. It will involve writing simple atomic
sentences about instances of concepts that are already part of the ontology
• Pose queries to the inference procedure and get answers - we can let the
inference procedure operate on the axioms and problem-specific facts to derive
the facts we are interested in knowing
• Debug the knowledge base - the answers to queries will seldom be
correct on the first try. More precisely, the answers will be correct for the
knowledge base as written, assuming that the inference procedure is
sound, but they will not be the ones that the user is expecting.