First-Order Logic Notes | EduRev

: First-Order Logic Notes | EduRev

 Page 1


CPS 270: Artificial Intelligence
http://www.cs.duke.edu/courses/fall08/cps270/
First-Order Logic
Instructor: Vincent Conitzer
Page 2


CPS 270: Artificial Intelligence
http://www.cs.duke.edu/courses/fall08/cps270/
First-Order Logic
Instructor: Vincent Conitzer
Limitations of propositional logic
• So far we studied propositional logic
• Some English statements are hard to model in 
propositional logic:
• “If your roommate is wet because of rain, your 
roommate must not be carrying any umbrella”
• Pathetic attempt at modeling this:
• RoommateWetBecauseOfRain => 
(NOT(RoommateCarryingUmbrella0) AND 
NOT(RoommateCarryingUmbrella1) AND 
NOT(RoommateCarryingUmbrella2) AND …)
Page 3


CPS 270: Artificial Intelligence
http://www.cs.duke.edu/courses/fall08/cps270/
First-Order Logic
Instructor: Vincent Conitzer
Limitations of propositional logic
• So far we studied propositional logic
• Some English statements are hard to model in 
propositional logic:
• “If your roommate is wet because of rain, your 
roommate must not be carrying any umbrella”
• Pathetic attempt at modeling this:
• RoommateWetBecauseOfRain => 
(NOT(RoommateCarryingUmbrella0) AND 
NOT(RoommateCarryingUmbrella1) AND 
NOT(RoommateCarryingUmbrella2) AND …)
Problems with propositional logic
• No notion of objects
• No notion of relations among objects
• RoommateCarryingUmbrella0 is instructive to us, 
suggesting 
– there is an object we call Roommate,
– there is an object we call Umbrella0,
– there is a relationship Carrying between these two objects
• Formally, none of this meaning is there
– Might as well have replaced RoommateCarryingUmbrella0  
by P
Page 4


CPS 270: Artificial Intelligence
http://www.cs.duke.edu/courses/fall08/cps270/
First-Order Logic
Instructor: Vincent Conitzer
Limitations of propositional logic
• So far we studied propositional logic
• Some English statements are hard to model in 
propositional logic:
• “If your roommate is wet because of rain, your 
roommate must not be carrying any umbrella”
• Pathetic attempt at modeling this:
• RoommateWetBecauseOfRain => 
(NOT(RoommateCarryingUmbrella0) AND 
NOT(RoommateCarryingUmbrella1) AND 
NOT(RoommateCarryingUmbrella2) AND …)
Problems with propositional logic
• No notion of objects
• No notion of relations among objects
• RoommateCarryingUmbrella0 is instructive to us, 
suggesting 
– there is an object we call Roommate,
– there is an object we call Umbrella0,
– there is a relationship Carrying between these two objects
• Formally, none of this meaning is there
– Might as well have replaced RoommateCarryingUmbrella0  
by P
Elements of first-order logic
• Objects: can give these names such as Umbrella0, 
Person0, John, Earth, …
• Relations: Carrying(., .), IsAnUmbrella(.)
– Carrying(Person0, Umbrella0), 
IsUmbrella(Umbrella0)
– Relations with one object = unary relations = 
properties
• Functions: Roommate(.)
– Roommate(Person0)
• Equality: Roommate(Person0) = Person1
Page 5


CPS 270: Artificial Intelligence
http://www.cs.duke.edu/courses/fall08/cps270/
First-Order Logic
Instructor: Vincent Conitzer
Limitations of propositional logic
• So far we studied propositional logic
• Some English statements are hard to model in 
propositional logic:
• “If your roommate is wet because of rain, your 
roommate must not be carrying any umbrella”
• Pathetic attempt at modeling this:
• RoommateWetBecauseOfRain => 
(NOT(RoommateCarryingUmbrella0) AND 
NOT(RoommateCarryingUmbrella1) AND 
NOT(RoommateCarryingUmbrella2) AND …)
Problems with propositional logic
• No notion of objects
• No notion of relations among objects
• RoommateCarryingUmbrella0 is instructive to us, 
suggesting 
– there is an object we call Roommate,
– there is an object we call Umbrella0,
– there is a relationship Carrying between these two objects
• Formally, none of this meaning is there
– Might as well have replaced RoommateCarryingUmbrella0  
by P
Elements of first-order logic
• Objects: can give these names such as Umbrella0, 
Person0, John, Earth, …
• Relations: Carrying(., .), IsAnUmbrella(.)
– Carrying(Person0, Umbrella0), 
IsUmbrella(Umbrella0)
– Relations with one object = unary relations = 
properties
• Functions: Roommate(.)
– Roommate(Person0)
• Equality: Roommate(Person0) = Person1
Things to note about functions
• It could be that we have a separate name for 
Roommate(Person0)
• E.g., Roommate(Person0) = Person1
• … but we do not need to have such a name
• A function can be applied to any object
• E.g., Roommate(Umbrella0)
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!