Chapter 8
First-Order Logic  

8.1 REPRESENTATION REVISITED

 

Some examples:

Objects (nouns)

• John
• wumpus
• pit
• 302
• stench

Relations (verbs) also known as predicates

• likes(wumpus, stench)
• brotherof(John, wumpus)
• smells(wumpus)

Functions are one-to-one relations

• plus(1,2)
• minus1(5)
• fatherof(wumpus)       wumpus have only one father

8.2 SYNTAX AND SEMANTICS OF FIRST-ORDER LOGIC

Constants

Represent objects in the domain

• wumpus
• agent
• pit

Predicates

Name a relationship between zero or more objects in the domain.

Map objects into range of True or False

• Hates(agent, wumpus)
• Brother(agent, wumpus)
• Hates( Father( agent ), wumpus )
• Smelly(wumpus)
• Smelly( Who([3,1] )

Functions

Map one or more elements in a set (domain) into a unique value of another set (range)

• Father( wumpus ) is daddie wumpus
• Plus(4, 5) is 9
• Who( [1,1], 1 ) is wumpus  at time 1
• Who( [1,1], 3 ) is agent at time 3

Stench( [2,1] ) is False; what is the domain and range? Is it a predicate or a function? There are three pits, one wumpus and one agent. What is the range of function Location(X) for the domain {wumpus, agent}? Can the three pits be added to the domain of function Location? if so, how? Should Shoots(agent, wumpus) be a function or predicate? What's the difference?

 

Which of the following are valid atomic sentences? Hates(agent, wumpus) Hates( Father( agent ), wumpus ) Smelly(wumpus) Who([3,1]) Smelly( Who([3,1] ) X agent X=agent Who( [1,1] ) = agent

Which of the following are valid complex sentences? Smelly(wumpus) Hates(agent, wumpus) Hates( Father( agent ), wumpus ) Smelly( Who([3,1] ) agent Who( [1,1] ) Hates(agent, wumpus) Hates(agent, wumpus) Smelly( Who([3,1] )

For the relations: Hates(agent, wumpus) Hates(agent, pit) Smelly(agent) Smelly(wumpus) At([3,1], wumpus) At([4,1], stench) Which of the following are True? Hates(wumpus, agent) Smelly(pit) Hates(agent, wumpus) Smelly( Who([3,1] ) At([2,2], stench) At([2,1], wumpus) Give the sentence for 'if a wumpus is at [3,1] a stench is at [4,1]. Give the sentence for 'if no wumpus is at [2,1] no stench is at [2,2]. Give the sentence for 'if stench is at [1,2], [2,3] and [1,4] there is a wumpus at [1,3].

 

 

With objects: wumpus agent pit [1,1], [2,1], ... With predicates: Stench([1,2]) At([1,3], wumpus) At([1,1], agent) At([3,1], pit) What is the meaning of: "s Stench(s) "s At(s, wumpus) "s ØAt(s, wumpus) Ø"s At(s, wumpus) "s At(s, wumpus) Þ Stench(s) Give the following in FOL. Square [2,3] has a stench. Every square has a stench. Every square has no stench. Not every square has a stench. Every square with a wumpus has a stench. Every square with an agent has no wumpus. Every square with an agent has no wumpus and no stench.

 

What is the difference between (consider that "s means that for all s must be true): "s At(s, wumpus) Þ Stench(s) º At([1,1], wumpus) Þ Stench([1,1]) Ù ...                                            false Þ true º true "s At(s, wumpus) Ù Stench(s) º At([1,1], wumpus) Ù Stench([1,1]) Ù ...                                            false Ù true º false Ù ...

With objects: wumpus agent pit [1,1], [2,1], ... With predicates: Stench([1,2]) At([1,3], wumpus) At([1,1], agent) At([3,1], pit) What is the meaning of: $s Stench(s) $s ØStench(s) Ø$s Stench(s) "s ØStench(s) "s At(s, wumpus) $s At(s, wumpus) Ø$s At(s, wumpus) $s ØAt(s, wumpus) $s At(s, wumpus) Ù At(s, agent) Give the following in FOL. Somewhere is a stench. The agent is at a stench. The agent is at no stench. Nowhere is the agent at a stench.

What is the difference between (consider that $s means that for at least one s must be true): $s At(s, wumpus) Ù At(s, wumpus) $s At(s, wumpus) Þ At(s, wumpus)

 

 

$s ØP(s) º Ø"s P(s)        Ø$s P(s) º "s ØP(s)

Ø$s ØP(s) º "s P(s)        $s P(s) º Ø"s ØP(s)

With objects: wumpus agent pit [1,1], [2,1], ... With predicates: Stench([1,2]) At([1,3], wumpus) At([1,1], agent) At([3,1], pit) What is: "s"x At(s, x) $s$x At(s, x) "x$s At(s, x) $s"x At(s, x) "s ØAt(s, wumpus) Ø$s At(s, wumpus) Ø$s Stench(s) Ø$s At(s, wumpus) Ù At(s, agent) "x Ø$s At(s, x) Ø"x $s At(s, x) "x $s ØAt(s, x) Give the following in FOL. At somewhere is a stench. At no where is a stench. At everywhere is a stench. At everywhere is a wumpus. At everywhere is everything (i.e. pit, agent, stench, wumpus, breeze, gold). Somewhere is everything. At everywhere is something. At somewhere is something. At somewhere is nothing. At no where is everything.

Define: An uncle is a brother of a parent. A grandparent is the parent of a parent. A grandmother is a female parent of a parent. A second cousin is a child of a parent's first cousin. Siblings have a common parent.

What is: "x At(x, wumpus) Þ At(x,stench) "x"y [At(x, wumpus) Þ At(y,stench)] "x"y [(x=y) At(x, wumpus) Þ At(y,stench)] "x"y [Ø(x=y) At(x, wumpus) Þ At(y,stench)] $x,y x=y "x,y x=y $x,y Ø[x=y] Define: An only child does not have a sibling (i.e. a sibling is not a sibling of themselves). Siblings cannot be parents of the same child. There is only one wumpus.

8.3 USING FIRST-ORDER LOGIC

 

Substitution

For the KB with two assertions:

• Person(John)
• Person(Mary)

$x Person(x) returns {x/John, x/Mary}

 

 

Representing percepts

Recall that the agent has five sensors with an additional time parameter:

1. Stench
2. Breeze
3. Glitter (for gold)
4. Bump when hitting a wall
5. Scream when wumpus is killed

A typical percept sentence with a stench and breeze percept taken at time 5 can be represented and added to KB by:

Tell(KB, Percept([Stench, Breeeze, Glitter, None, None], 5) )

where Percept is a binary predicate, Stench is a constant, etc.

Representing actions

Actions can be represented by terms:

• Turn(Right)
• Forward
• Turn(Left)
• Grab
• etc.

Deciding actions

To determine an action the agent constructs a query:

$a BestAction(a, 5)

Ask would solve the query returning the binding of { a/Grab }

To maintain truth in KB, the agent would Tell(KB, Grab)

What is KB after: Tell(KB, At([2,1], agent) Tell(KB, At([2,1], breeze) Tell(KB, At([1,2], stench) Tell(KB, At([3,1], pit) Tell(KB, At([3,3], pit) What is the result of: At([2,1], agent) $a At(a, agent) $b At([2,1], b) $a At(a, pit) $a,b At(a, b)

In propositional logic, a rule that a wumpus at [3,1] implies a stench at adjacent squares [4,1], [2,1] and [2,3]:

At([3,1], wumpus)ÞAt([4,1], stench) Ù At([2,1], stench) Ù At([2,3], stench)

An Adjacent square relation can be defined in FOL as:

"x, y, a, b Adjacent([x,y], [a,b]) Û [a,b] Î {[x,y+1], [x,y-1],[x+1,y],[x-1,y]}

The rule that a wumpus in at a square implies that at adjacent squares there is a stench:

• "s At(s, wumpus) Þ  $r At(r, stench) Ù Adjacent(r,s)

Use the Adjacent relation to define a Stench predicate.

 

 

 

 

 

8.4 KNOWLEDGE ENGINEERING IN FIRST-ORDER LOGIC

1. Identify the task - Implement a one-bit full adder.
2. Assemble the relevant knowledge - AND, OR, XOR and NOT gates transform their inputs according to the following table. A full adder is implemented by the diagram at right.
   •  

   In1 In2 AND Out OR Out XOR Out NOT Out 0 0 0 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 0

3. Decide on a vocabulary
   • Name each individual gate a constant: X₁, X₂, etc.
   • Function to type each gate: Type(X₁)=AND
   • Functions for gate terminals: In(1,X₁) input  terminal 1, Out(1, X₂) output terminal 3.
   • Predicate defines relations (connections): Connect(In(1,X₁), Out(1,X₂))
   • Objects 1 for On and 0 for Off
   • Function to define signal value for a terminal: Signal(In(1,X₁))=0
4. Encode general knowledge of the domain
   1. If two terminals are connected, then they have the same signal:
            "t₁, t₂ Connected(t₁,t₂) Signal(t₁)=Signal(t₂)
   2. A signal at every terminal is either 1 or 0 but not both and 1 ≠ 0:
            "t Signal(t)=1 Ú Signal(t)=0
             1 ≠ 0
   3. Connected is a commutative predicate:
            "t₁, t₂ Connected(t₁,t₂)Connected(t₂,t₁)
   4. An OR output is 1 if and only if any of its inputs is 1:
            "g Type(g)=OR Signal(Out(1,g))=1 $n Signal(In(n,g))=1
   5. An AND output is 0 if and only if any of its inputs is 0:
            "g Type(g)=AND Signal(Out(1,g))=0 $n Signal(In(n,g))=0
   6. An XOR output is 1 if and only if its inputs different:
            "g Type(g)=XOR Signal(Out(1,g))=1 Signal(In(1,g)) ≠ Signal(In(2,g))
   7. A NOT output is different than its input:
            "g Type(g)=NOT Signal(Out(1,g))!=Signal(In(1,g))
5. Encode specific problem instance

   Type(X₁)=XOR    Type(X₂)=XOR

   Type(A₁)=AND    Type(A₂)=AND

   Type(O₁)=OR

   Connected(Out(1,X₁),In(1,X₂))
   Connected(Out(1,X₁),In(2,A₂))
   Connected(In(1,C₁),In(1,X₁))
   Connected(In(1,C₁),In(1,A₁))

   A few others?

6. Pose queries to the inference procedure      
   
   What combination of inputs would cause the output of X₁ to be 1?
   
   $i₁, i₂ Signal(In(1,C₁))=i1   Signal(In(2,C₁))=i₂   Signal(Out(1,X₁))=1
   
   Answer entailed by knowledge base is: {i₁/0, i₂/1} {i₁/1, i₂/0}

What query would give the combination of inputs that would cause the output of: A1 to be 1? X2 to be 1? C1 output 2 to be 1? C1 output 2 to be any value in its range?

i1 i2 Cin i3 Sum o1 Cout o2 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1

• $"ÞÛº≠ØÎÚÙ