FirstOrder Logic
Propositional logic can only represent facts about the world.
Firstorder logic describes a world which consists of objects and properties
(or predicates) of those objects.
Among objects, various relations hold, e.g., Parent(Martin, Zac).
A function is a relation in which there is only one value for
a given input.
Examples
Objects: people, houses, numbers, planets,...
Relations: parent, brotherof, greaterthan,...
Properties: red, round, prime,...
Functions: fatherof, onemorethan
Examples:
"One plus one equals two."
"Squares neighbouring the Wumpus are smelly."
Firstorder logic is universal in the sense that it can express anything
that can be programmed.
Syntax and semantics
Firstorder logic has sentences just like propositional logic and, in addition,
it has terms, which represent objects. Constant symbols, variables
and function symbols are used to build terms and quantifiers and predicate
symbols are used to build sentences.
<Sentence> := <AtomicSentence>
 <Sentence> <Connective> <Sentence>
 <Quantifier> <Variable>,... <Sentence>
 <Sentence>
 (<Sentence>)
<Atomic Sentence> := <Predicate>(<Term>,...)
 <Term> = <Term>
<Term> := <Function>(<Term>,...)
 <Constant>
 <Variable>
<Connective> :=  
<=>  =>
<Quantifier> :=

<Constant> := Martin  59302  Cat  X  ...
<Variable> := a  x  s  ...
<Predicate> := Before  Likes  Raining  Fails  ...
<Function> := Father  Hairof  304gradefor  ...
BNF for firstorder logic
Constant symbols: A, B, C, 1, John,...
Each constant symbol names exactly one object in the world, not
all objects need to have names and some can have more than one name.
Predicate symbols: Round, Brother,...
A predicate symbol refers to a particular relation in the model. For
example, Brother ; since Brother is a binary
relation symbol, the relation it refers to must also be binary, i.e., it
must hold or fail to hold between pairs of objects.
Function symbols: Cosine, Fatherof, Leftlegof
A functional relation relates an object to exactly one other object.
The last element in the tuple is the value of the function for the other
elements. e.g. Officeof(Martin,sc1.40)
Terms
A term is a logical expression that refers to an object. Constant
symbols are terms. Terms can also be constructed from function symbols
and constant symbols, e.g., Fatherof(John).
The formal semantics of terms is as follows: An interpretation specifies
a functional relation referred to by the function symbol and objects referred
to by the constant symbols. Hence, a function term refers to the n+1^{th}
object in a tuple whose first n elements are those objects refereed to
by the arguments of the function.
Atomic sentences
An atomic sentence is formed from a predicate symbol follows by a parenthesized
list of terms, for example, Brother(Richard,John) states that the
object referred to by Richard is the brother of the object referred to
by John.
Atomic sentences can have arguments that are complex terms:
Married(Fatherof(Richard),Motherof(John))
Complex sentences
We can use logical connectives to construct more complex sentences.
The semantics of these is the same as in propositional logic.
Examples
Brother(Richard,John)
Brother(John,Richard)
is true just in case John is the brother of Richard and Richard is the
brother of John.
Older(John,30)
Younger(John,30) is true when John is older than 30 or he is younger
than 30.
Quantifiers
We now have a logic that allows objects, quantifiers let us
express properties of entire collections of objects.
There are two quantifiers in firstorder logic: universal and
existential.
Universal quantification()
Using this we can say things like, "All cats are mammals."
Notice the difference between
x Cat(x)=>Mammal(x)
and x
Cat(x) Mammal(x)
Universal statements are true if they are true for every individual in
the world. They can be thought of as an infinite conjunction.
Existential Quantification
Where universal quantification makes statements about every object,
existential quantification makes statements about some objects.
To say, for example that Spot has a sister that is a cat, we write
x Sister(x,spot)Cat(x)
x P is true if P is true
for some object in the world. It can be thought of as an infinite disjunction.
Nested quantifiers
Very complex statements can be made if one nests quantifiers. Starting
simply, without mixing types of quantifiers, we can say things like
x,y Parent(x,y)
=> Child(y,x)
We can also mix quantifiers, as in

xy
Goodat(x,y)
"Everybody is good at something"
Connections between
and
There is an intimate connection between the two quantifiers. To see
this, consider the sentence

xLikes(x,Deceitful
Politicians)
"For all x, x does not like Deceitful Politicians."
Another way to say this is, "There does not exists an x that likes
Deceitful Politicians"

x
Likes(x,Deceitful Politicians.)
This is true in general because
is a conjunction over all objects and
is a disjunction over all objects. In fact, all of the following are also
true
x P <=> x P PQ<=>(PQ)
x P<=>x P (PQ)<=>PQ
x P<=>x P PQ<=>(PQ)
x P<=>x P PQ<=>(PQ)
Equality
Often the equality symbol is included as a special symbol. This
is because the notion of equality is so important in our thinking. With
this symbol, we can write things like Father(John)=Bill, whose intended
meaning is that the object that is the father of John is the same object
as Bill.
Equality can also be thought of as an ordinary binary relation symbol,
so the interpretation of = is a set of pairs.
Equality can be used to say that there are two or more individuals
with a particular property

x,y Sister(Spot,x)Sister(Spot,y)(x=y)
"There is an x and y that are sisters of Spot and they are not the same
individual."
The equality symbol can also be used to restrict the number of objects
that have a certain property, for example,

x P(x)
P(y) => x=y
"Every pair of objects with property P are equal." This statement restricts
there to being one object with property P.
A short hand that is often used is !x
King(x) which means

x King(x) y
King(y) => x=y
Using FirstOrder Logic
In knowledge representation, a domain is a section of the world
about which we wish to express some knowledge.
Here we give some simple examples of using FOL to encode domains.
The Kinship domain
Examples
m,c Mother(c)=m <=>
Female(m) Parent(m,c)
w,h Husband(h,w) <=>
Male(h) Spouse(h,w)
x Male(x) <=> Female(x)
g,c Grandparent(g,c) <=> p
Parent(g,p) Parent(p,c)
x,y Sibling(x,y) <=>
xy p
Parent(p,x) Parent(p,y)
Axioms, Definitions and Theorems
Axioms capture the basic facts about a domain, e.g., the examples
above are axioms. The axioms are then used to prove theorems.
We can have too few or too many axioms. If we have too few, then we
cannot prove theorems that we expect should actually follow in a domain.
If we have too many axioms, then some axioms follow from (combinations
of) others. An axiom is said to be independent of a set of axioms
if it does not follow from that set.
None of the primitive predicates (functions) are defined, instead we
give partial specifications of the properties of these.
Asking questions and getting answers
To add sentences to the knowledge base, we call TELL, e.g.,
TELL(KB,m,c
Mother(c)=m <=> Female(m)
Parent(m,c))
This goes both for axioms (as above) and specific facts about a particular
situation such as
TELL(KB,(Female(Maxi)Parent(Maxi,Spot)Parent(Spot,Boots)))
With these facts added, we can
ASK(KB,Grandparent(Maxi,Boots))
and receive a yes/no answer. We can also ask questions that return
additional information in the answers such as
ASK(KB,x
Child(x,Spot)).
Here we do not want simply a yes/no answer. In addition we would like
to know a term for x denoting an object in the domain. In general, for
a query involving existentially quantified variables, we want to know bindings
for those variables. Hence, ASK returns a binding list, e.g., {x/boots}.
Logical Agents for the Wumpus World
We will consider three agent architectures for the Wumpus World: reflex
agents that merely classify their percepts and act on that classification,
modelbased
agents that construct an internal representation of the world and use
it to act, and goalbased agents that form goals and try to achieve
them.
The first step is to define the interface between the agent and the
world. The percept sequence must contain both the percepts and the time
at which they occurred, otherwise the agent will not be able to tell when
things were observed. We will use integers for time steps so a typical
percept sentence would be

Percept([Stench,Breeze,Glitter,None, None],5)
The agent's action must be one of:
Turn(Right), Turn(Left), Forward, Shoot, Grab, Release, Climb
To determine which one is best, we create a query such as a
Action(a,5). If we set things up right, such a query will return a binding
list such as {a/Grab}.
A Simple Reflex Agent
The simplest type of rule connects actions directly with percepts. These
rules resemble reflexes. For example, if the agent sees a glitter, it should
perform a Grab:

s,b,u,c,t Percept([s,b,Glitter,u,c],t)=>Action(Grab,t)
The connection between percepts and actions can be mediated by rules for
perception, which turn the immediate perceptual input into more useful
forms:

b,g,u,c,t Percept([Stench,b,g,u,c],t)=>Stench(t)

s,b,u,c,t Percept([s,b,Glitter,u,c],t)=>AtGold(t)
Then a connection can be made from these predicates to action choices with
separate rules:

t Atgold(t) => Action(Grab,t)
Limitations of simple reflex agents
Simple reflex agents react to only the current percept sequence. Therefore,
they cannot know what things were discovered in previous steps. Hence,
they are doomed to a life of wondering aimlessly.
Representing Change in the World
We would like to have rules that refer to previous times. The best way
to do this is to maintain an internal model of the world.
The most straightforward way to deal with change is simply to change
the knowledge base, erasing and adding sentences as the agent explores
its environment. This approach solves some of the problems we saw with
the propositional agent. However, it does not allow the agent to keep track
of the past.
Situation Calculus
Situation Calculus is the name for a particular way of describing
change in FOL. It conceives of the world as a sequence of situations,
each of which is a snapshot of the state of the world. Situations are generated
from previous situations by actions.
Every relation whose truth can change over time is handled by giving
an extra situation argument to the corresponding predicate symbol. By convention,
we make the situation argument always the last. Hence, instead of At(Agent,Location),
we would have At(Agent,[1,1],S0)
At(Agent,[1,2],S1).
Relations or properties that do not change over time need not have
the extra argument, e.g., WallAt([0,1]).
The next step is to represent how the world changes from one situation
to the next. One way to do this is to have a function result that
maps actions and states to new states. Then we would have:

Result(Forward,S0)=S1

Result(Turn(Right),S1)=S2

Result(Forward,S2)=S1
Actions are described by stating their effects. We specify the properties
of the situation that results from doing the action.

Portable(Gold)

s AtGold(s) => Present(Gold,s)

x,s Present(x,s)
Portable(x) => Holding(x,Result(Grab,s))
Or

x,s Holding(x,Result(Release,s))
These axioms are called effect axioms. Alone they are not sufficient
to keep track of whether the agent is holding the gold. We also need to
say that if the agent is holding something in a state then it is still
holding it in the state that results from an action other than Release:

a,x,s Holding(x,s)aRelease
=> Holding(x,Result(a,x))

a,x,s Holding(x,s)(aGrab(Present(x,s)Portable(x))
=> Holding(x,Result(a,s))
Axioms like these are called frame axioms. The combination of effect
and frame axioms provide a complete description of how the world changes
in response to an agent's actions.
A more elegant representation combines the effects and frame axioms
into a single axiom that describes how to compute the next time step. These
axioms have the structure

true afterwards <=> [an action made it true
true already and no action made it false]
The use of <=> ensures that a predicate will be true if it is made true
or stays true and that it will be false in all other cases.
a,x,s Holding(x,Result(a,s))<=>[(a=GrabPresent(x,s)Portable(x))
(Holding(x,s)aRelease)]
This type if axiom is called a successorstate axiom. One such
axiom is needed for each predicate that may change its value over time.
The axiom must list all the ways in which a predicate can become true and
all the ways in which it can become false.
Keeping track of location
In the Wumpus world, the agent cannot directly perceive its location,
so it needs to keep track of where it has been. Its also a good idea for
it to keep track of what it has seen in previous locations. The agent needs
to know its location and orientation:

At(Agent,[1,1],S0)

Orientation(Agent,S0)=0 (an angle in degrees, with 0 along the x axis)
The agent also needs to know how the locations are arranged. Its "map"
consists of the values of the function LocationToward, which takes
a location and a direction and gives the location that is one step forward
in the given direction:

x,y LocationToward([x,y],0)=[x+1,y]
and so on.
From the map it is possible to tell which square is directly ahead of the
agent

p,l,s At(p,l,s)=>LocationAhead(p,s)=Locationtoward(l,Orientation(p,s))

l1,l2 Adjacent(l1,l2)<=>d
l1=LocationToward(l2,d)
The agent also needs to know whatever is known about the contents of the
locations. Assume that the perimeter locations contain walls and the rest
do not.

x,y Wall([x,y])<=>(x=0x=5y=0y=5)
The agent needs to know what the actions do to locations:

a,d,p,s At(p,l,Result(a,s))<=>
[ (a=Forwardl=LocationAhead(p,s)Wall(l))
(At(p,l,s)aForward)]
Finally the agent needs to know what the actions do to orientations.

a,d,p,s Orientation(p,Result(a,s))=d
<=> [a=Turn(Right)d=Mod(Orientation(p,s)90,360))
(a=Turn(Left)d=Mod(Orientation(p,s)+90,360))
(Orientation(p,s)=d(a=Turn(Right)a=Turn(Left)))]
In addition to keeping track of location and the gold, the agent should
also keep track of whether the Wumpus is alive or dead. We also need to
describe shoot.
Deducing Hidden Properties of the World
From the perceptual information we obtain in situations, we can infer properties
of locations.

l,s At(Agent,l,s)Breeze(s)=>Breezy(l)

l,s At(Agent,l,s)Stench(s)=>Smelly(l)
Neither Breezy nor Smelly need situation arguments because pits and Wumpuses
do not move around.
We need to write some rules that relate various aspects of single world
states (as opposed to across states). There are two main kinds of such
rules:

Causal rules reflect the assumed direction of causality in the world:

l1,l2,s At(Wumpus,l1,s)Adjacent(l1,l2)=>Smelly(l2)

l1,l2,s At(Pit,l1,s)Adjacent(l1,l2)=>Breezy(l2)

Systems that reason with causal rules are called modelbased reasoning
systems.

Diagnostic rules infer the presence of hidden properties directly
from the perceptderived information. We have already seen two diagnostic
rules

l,s At(Agent,l,s)Breeze(s)=>Breezy(l)

l,s At(Agent,l,s)Stench(s)=>Smelly(l)
Why do we need both causal and diagnostic rules? It would seem that diagnostic
rules are enough. However, it is very tricky to ensure that they derive
the strongest possible conclusions from the available information. For
example, the absence of stench or breeze implies that adjacent squares
are OK:

x,y,g,u,c,s Percept([None,None,g,u,c],t)At(Agent,x,s)Adjacent(x,y)
=> OK(y)
but sometimes a square can be OK even when smells and breezes abound. The
modelbased rule

x,t (At(Wumpus,x,t)Pit(x))<=>OK(x)
is probably the best was to represent safety.
The important thing to remember about all this is that if the axioms
correctly and completely describe the way the world works and the way percepts
are produced, the inference procedure will correctly infer the strongest
possible description of the world state given the available percepts.
Preference Among Actions
A problem with the Wumpus world knowledge base that we have built so far
is that it is difficult to decide which action is best among a number of
possibilities. For example, to decide between a forward and a grab, axioms
describing when it is OK to move to a square would have to mention glitter.
This is not modular. We can solve this problem by separating facts about
actions from facts about goals. This way our agent can be reprogrammed
just by asking it to achieve different goals.
The first step is to describe the desirability of actions independent
of each other. In doing this we will use a simple scale: actions can be
Great, Good, Medium, Risky, or Deadly. Obviously, the agent should always
do the best action it can find:

a,s Great(a,s)=>Action(a,s)

a,s Good(a,s)
(b
Great(b,s)) => Action(a,s)

a,s Medium(a,s)
(b
Great(b,s) Good(b,s))=>Action(a,s)

...
We use this action quality scale in the following way. Up to the point
where it finds the gold, the basic strategy for our agent will be:

Great actions include picking up the gold when found and climbing out of
the cave with the gold.

Good actions include moving to a square that's OK and hasn't been visited
yet.

Medium actions include moving to a square that is OK and has already been
visited.

Risky actions include moving to a square that is not known to be deadly
or OK.

Deadly actions are moving into a square that is known to have a pit or
a Wumpus.
Once the gold is found the policy must change. At this point the agent
should have the goal of safely reaching square [1,1] as quickly as possible.

s Holding(Gold,s)=>GoalLocation([1,1],s)
The presence of an explicit goal allows the agent to work out a sequence
of actions that will achieve the goal. There are at least three ways to
find such a sequence:

Inference: this is what we are currently doing.

Search: We can use bestfirst search to find a path to the goal

Planning: This involves the use of specialpurpose reasoning engines
that reason about action.