Courses

# 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:
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:
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:
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:
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