CSCE 420 Lecture 16

« previous | Tuesday, March 19, 2013 | next »

First-Order Logic

Syntax

• Quantifiers & variables
• propositions → predicates
• Predicates have terms:
  1. variables
  2. functions
  3. constants

In the Wumpus World problem, a room with a pit causes a breeze in adjacent rooms:

∀r ∀s room(r) ∧ room(s) ∧ pit(r) ∧ adjacent(r,s) → breeze(s)
∀r ∀s ∀p ∀q ∀x ∀y adjacent(r,s) ∧ coords(r,x,y) ∧ coords(s,p,q) → |x-p|+|y-q| == 1

--OR--

∀x ∀y ∀p ∀q pit(x,y) → breeze(x+1, y) ∧ breeze(x-1, y) ∧ breeze(x, y+1) ∧ breeze(x, y-1)

Sensing from agent's perspective:

∀x ∀y room(x,y) ∧ breezy(x,y) → pit(x-1,y) ∨ pit(x+1,y) ∨ pit(x,y+1) ∨ pit(x,y-1)

--OR--

∀r room(r) ∧ breeze(r) → ∃s room(s) ∧ adjacent(r,s) ∧ pit(s)

Helpful hints:

• Use ∀ with implications
• Use ∃ with conjunctions

"Joe owns a book by Charles Dickens"

∃x book(x) ∧ author(x, Charles Dickens) ∧ owns(Joe, x)

Be careful, since the following would imply that Joe owns all books by Charles Dickens:

∃x book(x) ∧ owns(Joe, x) → author(x, Charles Dickens)
∀x book(x) ∧ owns(Joe, x) ∧ author(x, Charles Dickens)

"The president and vice president are from (necessarily) different towns"

∀x,y,a,b president(US, a, time()) ∧ vice_president(US, b, time()) ∧ town(a,x) ∧ town(b,y) → ¬Eq(x,y)
PresidentAndVicePresidentFromDifferentHomeTowns()

The latter is syntactically correct, but translation to first-order logic involves identifying

• objects
• properties
• relationships

Semantics

We saw from propositional logic that a model can be represented as a truth assignmet over propositional symbols.

In first-order logic, the truth values of predicates depend on the arguments.

For example, does adjacent(A,B) &madels; adjacent(B,A) ? This could be axiomitized by ∀r ∀s adjacent(r,s) → adjacent(s,r)

Therefore, a model might consist of a tuple of three things, (U,D,R)

• U = set of objects: "Universe of Discourse"
• D = Denotations: mappings from (constant) terms to objects
• R = Relations between objects for each predicate.
  • These can be defined as subsets of $U^{n}$, where $n$ is the arity of the predicate.
  • This is called the extensional definition of a predicate.

Example:

U = {o1,o2,o3}
D = {joe => o1, dickens => o2}
R[book] = {o3}
R[owns] = {(o1,o3)}

Definition of a Triangle

∀x triangle(x) ↔ ∃a ∃b ∃c ∃p ∃q ∃r

edge(x,a) ∧ edge(x,b) ∧ edge(x,c) ∧ a ≠ b ∧ a ≠ c ∧ b ≠ c ∧

vertex(x,p) ∧ vertex(x,q) ∧ vertex(x,r) ∧ p ≠ q ∧ p ≠ r ∧ q ≠ r ∧

intersect(a,b,p) ∧ intersect(a,c,q) ∧ intersect(b,c,r)

Satisfying model:

• U = {o1,o2,o3,o4,o5,o6}
• D = {}
• R[edge] = {o1,o2,o3}
• R[vertex] = {(o1,o4), (o2,o5), (o3,o6), (o2,o4), (o3,o6), …}
• R[intersect] = {(o1,o2,o4), (o2,o1,o4), (o1,o3,o5), (o2,o2,o5), (o2,o3,o6), (o3,o2,o6)}