CS 1571 Introduction to AI

Lecture 13

First-order logic

Milos Hauskrecht
milos@cs.pitt.edu
5329 Sennott Square

CS 1571 Intro to AI M. Hauskrecht

Administration announcements
Midterm:
• Thursday, October 25, 2012
• In-class
• Closed book

CS 1571 Intro to AI M. Hauskrecht

1
 First-order logic (FOL)
• More expressive than propositional logic

• Main additions:
– Represents explicitly objects, their properties, relations and
lets us make statements about them;
– Introduces variables that refer to arbitrary objects of certain
type that can be substituted by a specific object
– Introduces quantifiers allowing us to make statements for
groups objects without the need to represent each of them
separately

CS 1571 Intro to AI M. Hauskrecht

Logic
Logic is defined by:
• A set of sentences
– A sentence is constructed from a set of primitives according
to syntax rules.
• A set of interpretations
– An interpretation gives a semantic to primitives. It associates
primitives with objects, values in the real world.
• The valuation (meaning) function V
– Assigns a truth value to a given sentence under some
interpretation
V : sentence  interpretation  {True , False }

CS 1571 Intro to AI M. Hauskrecht

2
 First-order logic: Syntax

Term – a syntactic entity for representing objects

Terms in FOL:
• Constant symbols: represent specific objects
– E.g. John, France, car89
• Variables: represent objects of a certain type (type = domain of
discourse)
– E.g. x,y,z
• Functions applied to one or more terms
– E.g. father-of (John)
father-of(father-of(John))

CS 1571 Intro to AI M. Hauskrecht

First order logic: Syntax

Sentences in FOL:
• Atomic sentences:
– A predicate symbol applied to 0 or more terms
Examples:
Red(car12),
Sister(Amy, Jane);
Manager(father-of(John));

– t1 = t2 equivalence of terms
Example:
John = father-of(Peter)

CS 1571 Intro to AI M. Hauskrecht

3
 First order logic: Syntax
Sentences in FOL:
• Complex sentences:
• Assume  ,  are sentences in FOL. Then:
– (   ) (   ) (   ) (   )  
and
– x  y 
are sentences

Symbols  , 
- stand for the existential and the universal quantifier

CS 1571 Intro to AI M. Hauskrecht

Semantics: Interpretation
An interpretation I is defined by a mapping constants, predicates
and function to the domain of discourse D or relations on D
• domain of discourse: a set of objects in the world we represent
and refer to;
An interpretation I maps:
• Constant symbols to objects in D
I(John) =
• Predicate symbols to relations, properties on D

I(brother) = ; ; ….

• Function symbols to functional relations on D

I(father-of) = ; ; ….
CS 1571 Intro to AI M. Hauskrecht

4
 Semantics of sentences
Meaning (evaluation) function:
V : sentence  interpretation  {True , False }
A predicate predicate(term-1, term-2, term-3, term-n) is true for
the interpretation I , iff the objects referred to by term-1, term-
2, term-3, term-n are in the relation referred to by predicate

I(John) = I(Paul) =

I(brother) = ; ; ….

brother(John, Paul) = in I(brother)

V(brother(John, Paul), I) = True

CS 1571 Intro to AI M. Hauskrecht

Semantics of sentences
• Equality V(term-1= term-2, I) = True
Iff I(term-1) =I(term-2)
• Boolean expressions: standard

E.g. V(sentence-1  sentence-2, I) = True

Iff V(sentence-1,I)= True or V(sentence-2,I)= True

• Quantifications
V(  x  , I) = True substitution of x with d

Iff for all d  D V(  ,I[x/d])= True

V(  x  , I) = True
Iff there is a d  D , s.t. V(  ,I[x/d])= True

CS 1571 Intro to AI M. Hauskrecht

5
 Sentences with quantifiers
• Universal quantification

All Upitt students are smart

• Assume the universe of discourse of x are Upitt students

CS 1571 Intro to AI M. Hauskrecht

Sentences with quantifiers

• Universal quantification

All Upitt students are smart

• Assume the universe of discourse of x are Upitt students

 x smart(x)

CS 1571 Intro to AI M. Hauskrecht

6
 Sentences with quantifiers
• Universal quantification

All Upitt students are smart

• Assume the universe of discourse of x are Upitt students

 x smart(x)
• Assume the universe of discourse of x are students

CS 1571 Intro to AI M. Hauskrecht

Sentences with quantifiers

• Universal quantification

All Upitt students are smart

• Assume the universe of discourse of x are Upitt students

 x smart(x)
• Assume the universe of discourse of x are students
 x at(x,Upitt )  smart(x)

CS 1571 Intro to AI M. Hauskrecht

7
 Sentences with quantifiers
• Universal quantification

All Upitt students are smart

• Assume the universe of discourse of x are Upitt students

 x smart(x)
• Assume the universe of discourse of x are students
 x at(x,Upitt )  smart(x)
• Assume the universe of discourse of x are people

CS 1571 Intro to AI M. Hauskrecht

Sentences with quantifiers

• Universal quantification

All Upitt students are smart

• Assume the universe of discourse of x are Upitt students

 x smart(x)
• Assume the universe of discourse of x are students
 x at(x,Upitt )  smart(x)
• Assume the universe of discourse of x are people
 x student(x)  at(x,Upitt )  smart(x)

CS 1571 Intro to AI M. Hauskrecht

8
 Sentences with quantifiers
• Universal quantification

All Upitt students are smart

• Assume the universe of discourse of x are Upitt students

 x smart(x)
• Assume the universe of discourse of x are students
 x at(x,Upitt )  smart(x)
• Assume the universe of discourse of x are people
 x student(x)  at(x,Upitt )  smart(x)

Typically the universal quantifier connects with an implication

CS 1571 Intro to AI M. Hauskrecht

Sentences with quantifiers

• Existential quantification

Someone at CMU is smart

• Assume the universe of discourse of x are CMU affiliates

CS 1571 Intro to AI M. Hauskrecht

9
 Sentences with quantifiers
• Existential quantification

Someone at CMU is smart

• Assume the universe of discourse of x are CMU affiliates

 x smart(x)

CS 1571 Intro to AI M. Hauskrecht

Sentences with quantifiers

• Existential quantification

Someone at CMU is smart

• Assume the universe of discourse of x are CMU affiliates

 x smart(x)

• Assume the universe of discourse of x are people

CS 1571 Intro to AI M. Hauskrecht

10
 Sentences with quantifiers
• Existential quantification

Someone at CMU is smart

• Assume the universe of discourse of x are CMU affiliates

 x smart(x)

• Assume the universe of discourse of x are people

 x at(x,CMU)  smart(x)

CS 1571 Intro to AI M. Hauskrecht

Sentences with quantifiers

• Existential quantification

Someone at CMU is smart

• Assume the universe of discourse of x are CMU affiliates

 x smart(x)

• Assume the universe of discourse of x are people

 x at(x,CMU)  smart(x)

Typically the existential quantifier connects with a conjunction

CS 1571 Intro to AI M. Hauskrecht

11
 Translation with quantifiers
• Assume two predicates S(x) and P(x)

Universal statements typically tie with implications

• All S(x) is P(x)
– x ( S(x)  P(x) )
• No S(x) is P(x)
– x( S(x)  ¬P(x) )

Existential statements typically tie with conjunction

• Some S(x) is P(x)
– x (S(x)  P(x) )
• Some S(x) is not P(x)
– x (S(x)  ¬P(x) )
CS 1571 Intro to AI M. Hauskrecht

Nested quantifiers
• More than one quantifier may be necessary to capture the
meaning of a statement in the predicate logic.

Example:
• There is a person who loves everybody.
• Translation:
– Assume:
• Variables x and y denote people
• A predicate L(x,y) denotes: “x loves y”
• Then we can write in the predicate logic:
?

CS 1571 Intro to AI M. Hauskrecht

12
 Nested quantifiers
• More than one quantifier may be necessary to capture the
meaning of a statement in the predicate logic.

Example:
• There is a person who loves everybody.
• Translation:
– Assume:
• Variables x and y denote people
• A predicate L(x,y) denotes: “x loves y”
• Then we can write in the predicate logic:
 x y L(x,y)

CS 1571 Intro to AI M. Hauskrecht

Translation exercise
Suppose:
– Variables x,y denote people
– L(x,y) denotes “x loves y”.
Translate:
• Everybody loves Raymond. ?

CS 1571 Intro to AI M. Hauskrecht

13
 Translation exercise
Suppose:
– Variables x,y denote people
– L(x,y) denotes “x loves y”.
Translate:
• Everybody loves Raymond. x L(x,Raymond)
• Everybody loves somebody. ?

CS 1571 Intro to AI M. Hauskrecht

Translation exercise
Suppose:
– Variables x,y denote people
– L(x,y) denotes “x loves y”.
Translate:
• Everybody loves Raymond. x L(x,Raymond)
• Everybody loves somebody. xy L(x,y)
• There is somebody whom everybody loves. ?

CS 1571 Intro to AI M. Hauskrecht

14
 Translation exercise
Suppose:
– Variables x,y denote people
– L(x,y) denotes “x loves y”.
Translate:
• Everybody loves Raymond. x L(x,Raymond)
• Everybody loves somebody. xy L(x,y)
• There is somebody whom everybody loves. yx L(x,y)
• There is somebody who Raymond doesn't love. ?

CS 1571 Intro to AI M. Hauskrecht

Translation exercise
Suppose:
– Variables x,y denote people
– L(x,y) denotes “x loves y”.
Translate:
• Everybody loves Raymond. x L(x,Raymond)
• Everybody loves somebody. xy L(x,y)
• There is somebody whom everybody loves. yx L(x,y)
• There is somebody who Raymond doesn't love.
y¬L(Raymond,y)
• There is somebody whom no one loves. ?

CS 1571 Intro to AI M. Hauskrecht

15
 Translation exercise
Suppose:
– Variables x,y denote people
– L(x,y) denotes “x loves y”.
Translate:
• Everybody loves Raymond. x L(x,Raymond)
• Everybody loves somebody. xy L(x,y)
• There is somebody whom everybody loves. yx L(x,y)
• There is somebody who Raymond doesn't love.
y¬L(Raymond,y)
• There is somebody whom no one loves.
y x ¬L(x,y)

CS 1571 Intro to AI M. Hauskrecht

Order of quantifiers
• Order of quantifiers of the same type does not matter
For all x and y, if x is a parent of y then y is a child of x
 x , y parent ( x , y )  child ( y , x )
 y , x parent ( x , y )  child ( y , x )

• Order of different quantifiers changes the meaning

 x  y loves ( x , y )

CS 1571 Intro to AI M. Hauskrecht

16
 Order of quantifiers
• Order of quantifiers of the same type does not matter
For all x and y, if x is a parent of y then y is a child of x
 x , y parent ( x , y )  child ( y , x )
 y , x parent ( x , y )  child ( y , x )

• Order of different quantifiers changes the meaning

 x  y loves ( x , y )
Everybody loves somebody
 y  x loves ( x , y )

CS 1571 Intro to AI M. Hauskrecht

Order of quantifiers
• Order of quantifiers of the same type does not matter
For all x and y, if x is a parent of y then y is a child of x
 x , y parent ( x , y )  child ( y , x )
 y , x parent ( x , y )  child ( y , x )

• Order of different quantifiers changes the meaning

 x  y loves ( x , y )
Everybody loves somebody
 y  x loves ( x , y )
There is someone who is loved by everyone

CS 1571 Intro to AI M. Hauskrecht

17
Connections between quantifiers
Everyone likes ice cream
?

CS 1571 Intro to AI M. Hauskrecht

Connections between quantifiers

Everyone likes ice cream

 x likes ( x , IceCream )

CS 1571 Intro to AI M. Hauskrecht

18
 Connections between quantifiers
Everyone likes ice cream

 x likes ( x , IceCream )

Is it possible to convey the same meaning using an existential

quantifier ?

CS 1571 Intro to AI M. Hauskrecht

Connections between quantifiers

Everyone likes ice cream

 x likes ( x , IceCream )

Is it possible to convey the same meaning using an existential

quantifier ?

There is no one who does not like ice cream

 x  likes ( x , IceCream )

A universal quantifier in the sentence can be expressed using an

existential quantifier !!!

CS 1571 Intro to AI M. Hauskrecht

19
 Connections between quantifiers

Someone likes ice cream

?

CS 1571 Intro to AI M. Hauskrecht

Connections between quantifiers

Someone likes ice cream

 x likes ( x , IceCream )

Is it possible to convey the same meaning using a universal

quantifier ?

CS 1571 Intro to AI M. Hauskrecht

20
 Connections between quantifiers

Someone likes ice cream

 x likes ( x , IceCream )

Is it possible to convey the same meaning using a universal

quantifier ?

Not everyone does not like ice cream

 x  likes ( x , IceCream )

An existential quantifier in the sentence can be expressed using a

universal quantifier !!!

CS 1571 Intro to AI M. Hauskrecht

Representing knowledge in FOL

Example:
Kinship domain

• Objects: people
John , Mary , Jane , 
• Properties: gender
Male ( x ), Female ( x )
• Relations: parenthood, brotherhood, marriage
Parent ( x , y ), Brother ( x , y ), Spouse ( x , y )
• Functions: mother-of (one for each person x)
MotherOf ( x )

CS 1571 Intro to AI M. Hauskrecht

21
 Kinship domain in FOL
Relations between predicates and functions: write down what
we know about them; how relate to each other.
• Male and female are disjoint categories
 x Male ( x )   Female ( x )
• Parent and child relations are inverse
 x , y Parent ( x , y )  Child ( y , x )
• A grandparent is a parent of parent
g , c Grandparen t ( 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 )

• And so on ….
CS 1571 Intro to AI M. Hauskrecht

22