Artificial Intelligence

Lecture 6
First Order Logic
17-11-2022
Outline
 Syntax and Semantics of FOL
 Using FOL
 Knowledge Engineering
 Bound and free variables
 Conjunctive Normal Form (CNF)
First-order logic (FOL)
 Whereas propositional logic assumes the world
contains facts.
 first-order logic (like natural language) assumes the
world contains:
 Objects:people, houses, numbers, colors, wars, …
 Relations:
◼ unary relations are called properties: person, red, round,
prime, …
◼ n-ary relations such as brother of, bigger than, owns, …
 Functions: father of, best friend, one more than, plus,
…
Examples
1. “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.)
Examples
2. “Evil King John ruled England in 1200.”
Objects: John, England, 1200;
Relation: ruled;
Properties: evil, king.
Syntax of FOL: Basic elements
 Constants: KingJohn, Adel, Mona, Red,
Cairo, 2,...
 Predicates Brother, >,...
 Functions Sqrt, Plus, Father,...
 Variables x, y, a, b,...
 Connectives , , , , 
 Equality =
 Quantifiers , 
BNF grammar of sentences in first-
order logic
Sentence → AtomicSentence | ComplexSentence
AtomicSentence → Predicate | Predicate(Term,…) | Term=Term
ComplexSentence → (Sentence) | [Sentence]
|  Sentence
| Sentence  Sentence
| Sentence  Sentence
| Sentence  Sentence
| Sentence  Sentence
| Quantifier Variable Sentence
BNF grammar of sentences in first-
order logic (Cont.)
Term → Function(Term, …)
| Constant
| Variable
Quantifier → ∀ | ∃
Constant → Adel | 3 | A |…
Variable → a | x | y | …
Predicate → True | False | Loves | Raining | …
Function → Mother |…
Operator Precedence : , , , , 
Conventions
 Constant symbols stands for objects;
 Predicate symbols stands for relations (property or n-ary); and
 Function symbols stands for functions.
 Conventions:
 constant symbols, predicate symbols, and function symbols begin with
uppercase letters,
 variables begin with lowercase letter.
 For example, the constant symbols Richard and John; the predicate
symbols Brother , OnHead, Person, King, and Crown; and the function
symbols Mother and Plus.
 The choice of names is entirely up to the user.
 Each predicate and function symbol has an arity that indicates the number
of arguments.
Note
 The predicate P(x, y) is read as x is a P of y, e.g.,
 Father(Adel, Mona) : Adel is a father of Mona.
 Likes (Ali, Java) : Ali likes Java.
Types of sentences
 Term: constant, variable, function(𝑡𝑒𝑟𝑚1 ,…, 𝑡𝑒𝑟𝑚𝑛 )
 Atomic sentences: predicate(term, term)

𝑡𝑒𝑟𝑚1 = 𝑡𝑒𝑟𝑚2 or Equal (𝑡𝑒𝑟𝑚1 , 𝑡𝑒𝑟𝑚2 )

e.g., Person(Mona)
 Complex sentences

 Combine atomic sentences using connectives

S, S1  S2, S1  S2, S1  S2, S1  S2,

E.g., Sibling(KingJohn,Richard)  Sibling(Richard,KingJohn)
>(1,2)  ≤ (1,2)
>(1,2)   >(1,2)
Examples 1: translate the following
natural language statements into FOL
 Adam is a man and Mona is a woman
Man(Adam) ∧ Woman (Mona)
 Adam is married to Mona
Married(Adam, Mona)
 Every person has a mother
∀x∃y [Person(x) ⇒Hasmother(x, y)]
Examples 1: translate the following
natural language statements into FOL
 Adam is a man and Mona is a woman
Man(Adam) ∧ Woman (Mona)
Objects: Adam, Mona
 Adam is married to Mona Properties: Man, Woman, Person
Binary relations: Married, HasMother
Married(Adam, Mona)
 Every person has a mother
∀x∃y [Person(x) ⇒HasMother(x, y)]
Examples 2
 Represent the following statement in FOL:
 Allstudents are smart
Objects: Java
x. Student(x) ⟹ Smart (x) Properties: Student, Smart, Clever
 Some students are clever Binary relations: Like

x. Student(x)  Clever (x)

 Some students like Java.

x. Student(x)  Like(x, Java)

Question
 Select a correct representation of the English
statement:
Tanta and Aswan are both in Egypt
use the predicate In(x, y)
1. In(Tanta ∧ Aswan, Egypt)
2. In(Tanta, Egypt) ∧ In(Aswan, Egypt)
3. In(Tanta, Egypt) ∨ In(Aswan, Egypt)
Question
 Select a correct representation of the English
statement:
Tanta and Aswan are both in Egypt
use the predicate In(x, y)
1. In(Tanta ∧ Aswan, Egypt) (not correct Syntax)
2. In(Tanta, Egypt) ∧ In(Aswan, Egypt)
3. In(Tanta, Egypt) ∨ In(Aswan, Egypt) (does not
represent the statement)
Question
 Select a correct representation of the English
statement:
There is a country that borders both Iraq and Pakistan
use the predicate Country(x) and Border(x, y)
1. x. Country(x)  Border (x, Iraq)  Border (x,
Pakistan)
2. x. Country(x) [ Border (x, Iraq)  Border (x,
Pakistan) ]
3. x. Border( Country(x), Iraq)  Pakistan)
Question
 Select a correct representation of the English statement:
There is a country that borders both Iraq and Pakistan
use the predicate Country(x) and Border(x, y)
1. x. Country(x)  Border (x, Iraq)  Border (x,
Pakistan) Statement 2 says there is a country x that border
Iraq and Pakistan. But it also says: If x is not a
2. x. Country(x) [ Border
country (x, Iraq)
it borders Iraq
both Border (x, (from
and Pakistan
Pakistan) ] the truth table of ⇒ )

3. x. Border( Country(x), Iraq)  Pakistan)

(not valid syntax)
Truth in first-order logic
 Sentences are true with respect to a model and an interpretation.
 Model contains objects (domain elements) and relations among them.
 The domain of a model is the set of objects or domain elements it contains.
 Interpretation specifies referents for
constant symbols → objects
predicate symbols → relations on objects
function symbols → functional relation on objects
 An atomic sentence predicate(term1,...,termn) is true
iff the objects referred to by term1,...,termn are in the relation
referred to by predicate
Example 1: Interpretation of FOL
 As in propositional logic, every model must have
the information required to determine if any given
sentence is true or false.
 Each model includes an interpretation that specifies
exactly which objects, relations and functions are
referred to by the constant, predicate, and function
symbols.
 Example 1: (Models for FOL)
A model has :
• 5 objects: Richard the Lionheart, King John,
left leg of Richard, left leg of John, a crown Constants
• 2 binary relations: brother, on head
• 3 unary relation : person, king, crown Predicates
• 1 unary function: left-leg
Function

The objects of the

model may be
related in various
ways, e.g.,
Richard and John
are brothers
 Example 1: Models for FOL (cont.)
A model has :
• 5 objects: Richard the Lionheart, King John,
left leg of Richard, left leg of John, a crown
• 2 binary relations: brother, on head
• 3 unary relation : Person, King, Crown
• 1 unary function: leftLeg

Brother(R, J), Brother (J, R)

OnHead( , J)

Person (R), Person(J)

Crown ( )
King(J) LeftLeg(R) = ( )
LeftLeg(J) = ( )
Example: Interpretation of FOL
 One possible interpretation for this example—
which is called the intended interpretation:
 Richard refers to Richard the Lionheart
 John refers to the evil King John
 Brother refers to the brotherhood relation
 OnHead refers to the “on head” relation that holds
between the crown and King John; Person, King, and
Crown refer to the sets of objects that are persons,
kings, and crowns.
 LeftLeg refers to the “left leg” function, that is, the
mapping given in Equation
Example: Interpretation of FOL (cont.)

 Under this interpretation, Brother(Richard, John) is

true
just in case Richard the Lionheart and the evil King
John are in the brotherhood relation in the model
Example 2
1) Consider the set of natural numbers ℕ as a domain
 Constant symbols: 0, 1, 2, …

 Predicate symbols: Even, Prime, LE, …

 Functions symbols: Add, Mult, …

LE is interpreted as less than or equal to relation on

natural numbers ℕ:
LE(0, y) is true in this interpretation on domain ℕ
2) Consider the set of integers ℤ as a domain
LE(0, y) is false for some y in this interpretation on
domain ℤ .
Universal quantification
 <variables> <sentence>
All kings are persons
x King (x)  Person (x)

Everyone at London is smart:

x At(x, London)  Smart(x)

 x P is true in a model M iff P is true with x being each possible

object in the model

 Roughly speaking, equivalent to the conjunction of instantiations of P

At(KingJohn, London)  Smart(KingJohn)
 At(Richard, London)  Smart(Richard)
 At(London, London)  Smart(London)

….
A common mistake to avoid
 Typically,  is the main connective with 
 Common mistake is using  as the main
connective with :
x At(x, London)  Smart(x)
means “Everyone is at London, and everyone is smart”
Existential quantification
 <variables> <sentence>
 King John has a crown on his head:
∃ x Crown(x) ∧ OnHead(x, John)

 Someone at London is smart:

x At(x, London)  Smart(x)
 x P is true in a model M iff P is true with x being some possible
object in the model
 Roughly speaking, equivalent to the disjunction of instantiations of P
At(KingJohn, London)  Smart(KingJohn)
 At(Richard, London)  Smart(Richard)
 At(London, London)  Smart(London)

…
Another common mistake to avoid
 Typically,  is the main connective with 

 Common mistake is using  as the main connective with :

x At(x, London)  Smart(x)

is true if there is anyone who is not at London!

(the implication  is true if both the premise and
conclusion are true, or if its premise is false)
Nested quantifiers
 Quantifiers can be nested as in the statement:
Brothers are siblings:
 ∀ x ∀ y Brother (x, y) ⟺ Sibling(x, y)
Properties of quantifiers
 x y is the same as y x
 x y is the same as y x

 x y is NOT the same as y x

For example, x y Loves(x, y)

 “There is a person who loves everyone in the world”
but y x Loves(x, y)
 “Everyone in the world is loved by at least one person”

 Quantifier duality: each can be expressed using the other

 x Likes(x, IceCream) is equivalent to x Likes(x, IceCream)

 x Likes(x, Banana) is equivalent to  x Likes(x, Banana)

Equality
 term1 = term2 is true under a given interpretation if
and only if term1 and term2 refer to the same object
 The object referred to by Father (Ali) and the object
referred to by Adam are the same:
Father (Ali) = Adam
 Richard has at least two brothers:

∃ x, y Brother (x, Richard) ∧ Brother (y, Richard) ∧ ¬(x = y)

 Note the following sentence does not have the intended
meaning:
∃ x, y Brother (x, Richard) ∧ Brother (y, Richard)
Using FOL
The kinship domain:

 Brothers are siblings

x,y Brother(x, y)  Sibling(x, y)

 One's mother is one's female parent

m,c Mother(c) = m  (Female(m)  Parent(m, c))

 “Sibling” is symmetric
x,y Sibling(x, y)  Sibling(y, x)
Interacting with FOL KBs
 Suppose a Wumpus-world agent is using an FOL KB and perceives a smell
and a breeze (but no glitter) at t =5 (t is the time of the breeze)

Percept([Stench, Breeze, None],5))

what is the best action at time 5: a BestAction(a,5))

 I.e., does the KB entail some best action at t =5?

 Answer: Yes, {a/Shoot} ← substitution (binding list)

 Given a sentence S and a substitution σ,

 Sσ denotes the result of plugging σ into S; e.g.,
S = Smarter(x, y)
σ = {x/Hillary, y/Bill}
Sσ = Smarter(Hillary, Bill)

 Is KB entails S, returns some/all σ such that KB╞ Sσ

Knowledge base for the wumpus world

 Perception
 t, s, b Percept([s,b,Glitter],t)  Glitter(t)

 Reflex
 t Glitter(t)  BestAction(Grab,t)
Wumpus world in FOL
 x, y, a, b Adjacent([x, y],[a, b]) 
(x = a  (y = b-1  y = b + 1)) 
(y = b  (x = a-1  x = a + 1))

Squares are breezy near a pit:

 Diagnostic rule---infer cause from effect

s Breezy(s)   r Adjacent(r, s)  Pit(r)

 Causal rule---infer effect from cause

r Pit(r)  [s Adjacent(r, s)  Breezy(s)]
Knowledge engineering
 Knowledge engineering: A general process of
knowledge-base construction.
 Knowledge engineer 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.
Knowledge engineering process
1. Identify the task.
2. Assemble the knowledge
3. Decide on a vocabulary of predicates, functions,
and constants
4. Encode general knowledge about the domain
5. Encode a description of the specific problem
instance
6. Pose queries to the inference procedure and get
answers
7. Debug the knowledge base
Exercise
Represent the following sentences using FOL
1. Horses, cows, and pigs are mammals.
2. An offspring of a horse is a horse.
3. Bluebeard is a horse.
4. Bluebeard is Charlie’s parent.
5. Offspring and parent are inverse relations.
6. Every mammal has a parent.
Exercise
Represent the following sentences using FOL
1. Horses, cows, and pigs are mammals.
Horse(x) ⇒ Mammal (x)
Cow (y) ⇒ Mammal (y)
Pigs (z) ⇒ Mammal (z)
2. An offspring of a horse is a horse.
Horse(x) ∧ Offspring (x, y) ⇒ Horse(y)
3. Bluebeard is a horse.
Horse(Bluebeard )
4. Bluebeard is Charlie’s parent.
Parent (Bluebeard, Charlie)
Exercise
Represent the following sentences using FOL
5. Offspring and parent are inverse relations.
Parent (x, y) ⇔ Offspring (y, x)
6. Every mammal has a parent.
∀x ∃ y Mammal (x) ⇒ Parent (y, x)
Bound and free variables
 A variable in statements is bound if it is within the scope of a
quantifier naming the variable, otherwise the variable is free.
 For example,
 ∀x(P(x) → Q(x, y)), x is bound, and y is free

 [∀x(Q(x) → R(x))] ∧ P(x), the x in P(x) is free variable.

 In last case it is better to rename the variable x to remove

the ambiguity:
[∀z(Q(z) → R(z))] ∧ P(x)
Conversion to CNF
 Everyone who loves all animals is loved by someone:
x [y (Animal(y)  Loves(x,y))]  [y Loves(y,x)]

1. Eliminate biconditionals and implications

x [y Animal(y)  Loves(x,y)]  [y Loves(y,x)]

2. Move  inwards: x P(x) ≡ x P(x) and

 x P(x) ≡ x P(x)
x [y (Animal(y)  Loves(x, y))]  [y Loves(y, x)]
x [y Animal(y)  Loves(x, y)]  [y Loves(y, x)]
x [y Animal(y)  Loves(x, y)]  [y Loves(y, x)]
Conversion to CNF (cont.)
3. Standardize variables: each quantifier should use a different
name
x [y Animal(y)  Loves(x,y)]  [z Loves(z,x)]

4. Skolemize: a more general form of existential instantiation.

Each existential variable is replaced by a Skolem function of the
enclosing universally quantified variables:

x [Animal(F(x))  Loves(x, F(x))] 

Loves(G(x), x)
Conversion to CNF (cont.)

5. Drop universal quantifiers:

[Animal(F(x))  Loves(x, F(x))]  Loves(G(x), x)

6. Distribute  over  :

[Animal(F(x))  Loves(G(x),x)]  [Loves(x, F(x)) 

Loves(G(x), x)]
By and elimination:
[Animal(F(x))  Loves(G(x),x)]
[Loves(x, F(x))  Loves(G(x), x)]
Example 1: Convert to CNF
∃x∀y [(∀z P( F(x), y, z))⇒ (∃u Q(x, u) ∧ ∃v R(y, v))]

1. Eliminate implication:
∃x∀y [￢∀z P(F(x), y, z) ∨ (∃u Q(x, u) ∧ ∃v R( y, v))]
2. Move negative symbols to the atom:
∃x∀y[∃z￢P(F(x), y, z) ∨ (∃u Q(x, u) ∧ ∃v R(y, v))]
3. Rename variables; not required in this example.
Example 1: Convert to CNF (cont.)
4. Skolemize:
1) Replace existentially quantified variables not in the scope of universal
quantifier by constants:
∃x∀y[∃z￢P(F(x), y, z) ∨ (∃u Q(x, u) ∧ ∃v R(y, v))]
∀y[∃z ￢P(F(A), y, z) ∨ (∃u Q(A, u) ∧ ∃v R(y, v))]
A is a Skolem constant
2) Replace existentially quantified variables that are in the scope
of universal quantifier by Skolem functions :
∀y[∃z ￢P(F(A), y, z) ∨ (∃u Q(A, u) ∧ ∃v R(y, v))]
∀y[ ￢P(F(A), y, G(y)) ∨ ( Q(A, H(y)) ∧ R(y, L(v))]
G(y), H(y), L(y) are Skolem functions
Example 1: Convert to CNF (cont.)
4. Drop universal quantifiers:
[ ￢P(F(A), y, G(y)) ∨ ( Q(A, H(y)) ∧ R(y, L(v))]
5. Distribute  over  :
￢P(F(A), y, G(y)) ∨ Q(A, H(y) ∧
￢P(F(A), y, G(y)) ∨ R(y, L(v))
by and elimination:

￢P(F(A), y, G(y)) ∨ Q(A, H(y)

￢P(F(A), y, G(y)) ∨ R(y, L(v))
Midterm exam
 Next Thursday 24 -11-2022 at 9’Oclock.