Agents that reason logically

We will now look at knowledge-based agents; these implement a view of agents in which they can be seen as knowing about their world and reasoning about their possible courses of action.

A knowledge-based agent needs to know: the current state of the world, how to infer unseen properties from percepts, how the world evolves over time, what it wants to achieve, and what its own actions do in various circumstances.

The basic elements of a reasoning agent's design are: a formal language in which knowledge can be expressed and a means of carrying out reasoning in such a language. These two elements constitute a logic.

A knowledge-based agent

The central component of a knowledge-based agent is its knowledge base (KB). A KB is a set of representations of facts about the world. Often the individual units of a KB are called sentences.

There must be a way to add new sentences to the knowledge base and a way to query what is known. We will call these standard functions TELL and ASK, respectively.

Determining what follows from a KB is the job of the inference mechanism.

Like all other agents, this agent takes a percept as input and returns an action.

The agent maintains a KB which may initially contains some background knowledge.

In the process of answering this query, logical reasoning is used to prove which action is better than all others, given what the agent knows and what its goals are.

Make-percept-sentence takes a percept and a time and returns a sentence representing the fact that the agent perceived the percept at time t.

Make-action-query takes a time and returns a sentence that is suitable for asking what action should be performed at that time.

At any point, we can describe a knowledge-based agent at three levels:

The agents initial program is built by adding sentences one at a time to the knowledge base. Provided that the representation language makes it easy to express this knowledge in the form of sentences, this simplifies the construction problem significantly. This is called the declarative approach to system building.

The Wumpus World

We now provide a simple world.  We must explore a cave consisting of rooms connected by passageways. Lurking somewhere in the cave is a beast (the wumpus)  that eats anyone who enters his room. Some rooms contain bottomless pits, but another contains gold.

The agents task is to find the gold and return to square [1,1].

The percepts, actions and goals in the wumpus world are as follows: The agent must do well over a class of wumpus problems. We will assume a 4x4 grid surrounded by walls. The location of the gold and the wumpus are chosen randomly, with a uniform distribution from the squares other than [1,1]. In addition, each square other than the start can be a pit, with probability .2.

In most environments in this class, it is possible for the agent to return successfully with the gold. However, in some the agent must choose between going home empty handed or taking a chance that could lead to death or the gold. And in about 21% of the environments, there is no way the agent can get a positive score.

Acting and reasoning in the wumpus world

Why does an agent that is successful in this world need to be able to reason? The following figure shows the state of the agent's knowledge after it has received its initial percept in the world above.

From the fact that there was no stench or breeze in [1,1], the agent can infer that [1,2] and [2,1] are free of dangers. From the fact that it is still alive, it can infer than [1,1] is also OK. A cautious agent will only move into a square that it knows is OK. Let us suppose the agent moves to [2,1], giving us (b) above.

The agent detects a breeze in [2,1], so there must be a pit in a neighbouring square, either [2,2] or [3,1]. (The notation P? indicates a possible pit.) The pit cannot be in [1,1] because the agent has already been there and did not fall in. At this point, there is only one known square that is OK and has not yet been visited. So the prudent agent turns back and goes to [1,1] and then [1,2], giving us (a) below:

The agent detects a stench in [1,2], which means there must be a Wumpus near by. But the wumpus cannot be in [1,1] and it cannot be in [2,2] (or the agent would have detected a stench when it was in [1,3]). More interesting is the lack of a breeze in [1,2] means that there must be a pit in [2,2]. ...

Representation, Reasoning and Logic

Together representation and reasoning support the operation of a knowledge-based agent. The object of a knowledge representation is to express knowledge in computer-manipulatable form such that it can be used to help agents perform well. A knowledge representation language has two aspects: Languages with precisely defined syntax and semantics are called logics. In a logic, we can develop inference mechanisms for an agent that uses the language. A sentence inside of a computer is not a fact, it is a representation of a fact. An inference mechanism must ensure that it allows new sentences to be derived from existing ones only when the new fact is true just when the existing ones are.

We want to generate sentences that are necessarily true given that the old sentences are true. This relationship between sentences is called entailment.

How do we build sound inference procedures? By examining the semantics of logical languages, we can extract what is called a proof theory of the language.

Example Consider the sentence E=mc2. The syntax of the "equation language" allows two expressions to be connected by =. An expression can be a symbol or a number, a concatenation of two expressions, two expressions joined by +, and so on.

The semantics of the language says that the two expressions on each side of the = refer to the same quantity; that the concatenation of two expressions refers to the quantity that is the product of the two quantities referred to by each of the expressions; and so on.

From the semantics, we can show that a new sentence can be generated by, for example, concatenating the same expression to both sides of the equation. ET=mc2T.


Representations need to be good at the job for which they are intended, but what does this mean? We start by looking at some more familiar examples than representation languages.

Programming languages are good for describing algorithms and concrete data structures. It is easy to imagine using a 4x4 array to represent the wumpus world and world[2,2]<-pit is a natural way to place a pit in square [2,2] of a world. However, when we want to say less specific things, we run into trouble. For example, "there is a pit in [2,2] or [3,1]" or "there is a wumpus somewhere."

The reason we run into this problem is that programming languages are designed to completely describe the state of the computer and how it changes as a program executes. But we would like to be able to describe situations where complete information is not available. A language that does not allow us to do this is not sufficiently expressive.

A good knowledge representation language should be expressive and concise so that what we say today will still be understandable tomorrow. It should be unambiguous and independent of context. Also, it should be possible to design an inference procedure for it.


In logic, the meaning of a sentence is what it states about the world. So, how do we establish the correspondence between facts and sentences? In order to say what a sentence means, an interpretation must be provided to say what fact is corresponds to. Without an interpretation, a sentence is meaningless. This idea is easiest to see in fabricated languages.

The languages that we will deal with are all compositional - the meaning of a sentence is a function of the meaning of its parts. Just as the meaning of x2 + y2 is determined from the meanings of x2 and y2, we want the meaning of "s1 and s2" to be determined from the meanings of "s1" and "s2".

A sentence is true under a particular interpretation if the state of affairs it represents is the case. Hence, truth depends both on the interpretation and the actual state of affairs in the world.


"S1,2" would be true under the interpretation in which it means that there is a stench in [1,2], in the world we explored earlier, but it would be false in worlds that do not have a stench in [1,2]. Also it would be false in our example world if its interpretation were "there is a breeze in [1,2]."


We are concerned with sound inference which is called logical inference or deduction. Logical inference is a process that implements the entailment relation between sentences. We begin with the idea of necessary truth.

Validity and satisfiability

A sentence is valid or necessarily true if and only if it is true under all possible interpretations in all possible worlds.

Example "There is a stench at [1,1] implies there is a stench at [1,1]." By contrast, "There is an open area in the square in front of me or there is a wall in the square in front of me" is not valid.

A sentence is satisfiable if and only if there is some interpretation in some world that makes it true, e.g., "there is a wumpus at [1,2]". If there is no interpretation and no world in which a sentence is true, it is called unsatisfiable.

Example There is a wall in front of me if and only if there is no wall in front of me.

Inference in computers

It turns out that validity and unsatisfiability are crucial to the ability of a computer to reason logically.

Computers do not know the interpretation you are using for the sentences in the knowledge base, nor does it know anything more than what appears on the knowledge base (it has no direct experience with the world).

Example Suppose we ask if it is OK to move to square [2,2]. The computer does not know what OK means, nor does it know what a wumpus a a pit is. So it cannot reason informally as we do. All it can do is see if KB"[2,2] is OK". The inference procedure must show that the sentence, "If KB is true then [2,2] is OK" is a valid sentence. If it can show this then [2,2] is OK under any interpretation and model.

Hence, the powerful thing about formal inference is that it can be used to derive valid conclusions even if the reasoner does not know the intended interpretation.


As we have said, logics consist of the following:

We will look first at propositional logic (0-order logic) and then at first-order logic with equality.

In propositional logic symbols represent whole propositions (what we have been calling facts), e.g., D might have the interpretation, "the wumpus is dead". These symbols can be combined into more complicated sentences using boolean connectives.

First-order logic commits to the representation of the world in terms of objects and predicates on those objects as well as connectives (as in propositional logic) and quantifiers.

It is illuminating to consider logics in the light of their ontological and epistemological commitments. Ontological commitments have to do with the nature of reality. For example, propositional logic assumes that there are facts that either hold or do not hold in the world. First-order logic further assumes that the world consists of objects with certain relationships between them that either hold or do not hold. Special purpose logics make further commitments.

Epistemological commitments have to do with the possible states of knowledge an agent can have using various types of logics. In propositional and first-order logic, a sentence represents a fact and the agent either believes the sentence to be true, believes it to be false or cannot make a determination. Hence, these logics have three possible states of belief about any sentence. Systems using probability theory can have any degree of belief in a sentence, ranging from 0 (false) to 1 (true).

Propositional Logic


The symbols are True and False, propositional symbols such as P or Q, the logical connectives, ,,<=>,=>, and parentheses. All sentences are made by putting these symbols together using the following rules:

BNF for propositional logic:
  Precedence of operators is: ,,,=>,<=>.


A propositional symbol can be interpreted as any fact. The propositional constants have the obvious interpretations.

For a complex sentence the meaning (as a function of the truth values of the constituent parts, is given by truth tables.

The truth table for => may be confusing at first. This is because, in English, "if P then Q" has a causal interpretation, i.e., P causes Q. This is not the case in propositional logic, where, "if P then Q" means that when P is the case I claim that Q is also. When P is not the case, I am making no claim.

Validity and inference

Truth tables can also be used to test the validity of sentences.


Since we can check validity of a sentence using truth tables, we can check whether a conclusion follows from some premises by checking whether or not Premises => Conclusion is valid.



Any world in which a sentence is true under a particular interpretation is called a model of that sentence under that interpretation.

The more we claim, the fewer models there will be of those claims, e.g., there are fewer models of "There is a pit in [1,2] and there is a Wumpus in [4,2]" than of "There is a pit in [1,2]."

Models are very important in logic because of the relationship between models and entailment. If KB, then every model of KB is also a model of . Hence, whenever KB is true so also is .

We could define the meaning of a sentence by means of set operations on sets of models. For example, the set of models of PQ is the intersection of the models of P and the models of Q.

Rules of inference for propositional logic

The process by which the soundness of an inference rule is established through truth tables can be extended to entire classes of inferences. There are certain patterns of inferences that occur over and over, and their soundness can be shown once and for all. Then the pattern can be captured in what is called an inference rule. Once this has been done, the rule can be used to make inferences without going through the tedious process of building truth tables.

We have already seen the notation  to say that  can be derived from  by inference. An alternate notation emphasizes that this is not a sentence, but rather an inference rule:

Here  and  match sentences.

Whenever something in the knowledge base matches the pattern above the line, the inference rule concludes the sentence below the line.

An inference rule is sound if the conclusion is true in all cases in which the premises are true.

Some example inference rules:

Modus Ponens

Double-Negation Elimination
Unit Resolution
Complexity of Propositional Inference

Since there are 2n rows in a truth table, one might suspect that the complexity of propositional inference is exponential. One might wonder if there is a polynomial-time procedure for propositional inference. This very problem was the motivation for the class of NP-complete problems.

There is a useful class of sentences for which polynomial-time inference procedure exists. This is a class called Horn sentences. These sentences have the form:

Where each of the Pi and Q are nonnegative literals.

An Agent for the Wumpus World

Let S1,1 mean there is a stench in [1,1].

Let B1,1 mean there is a breeze in [1,1].

Let W1,1 mean there is a Wumpus in [1,1].

Let P1,1 mean there is a pit in [1,1].

what we know about the wumpus world is:
How can we express the rules about Wumpuses and Pits?

r1: S1,1=>W1,1W1,2W2,1

r2: S2,1=>W1,1W2,1W2,2W3,1

r3:    S1,2=>W1,3W1,2W2,2W1,1

Now to find the wumpus using the inference rules:

modus ponens with S1,1 and r1 gives


and elimination gives:


modus ponens followed by and elimination with S2,1 and r2 gives:


modus ponens with S1,2 and r3 gives:


apply unit resolution where  is W1,3W1,2W2,2 and  is W1,1 gives:


apply unit resolution where  is W1,3W1,2 and  is W2,2 gives:


apply unit resolution where  is W1,3W1,2 and is W1,2 gives:


We have found the wumpus!!