Next: Axioms for Knowledge Up: Agent Theories Previous: Representing Intentional Notions

Possible Worlds Semantics

The possible worlds model for logics of knowledge and belief was originally proposed by Hintikka [Hintikka, 1962], and is now most commonly formulated in a normal modal logic using the techniques developed by Kripke [Kripke, 1963]. Hintikka's insight was to see that an agent's beliefs could be characterized as a set of possible worlds, in the following way. Consider an agent playing a card game such as poker. In this game, the more one knows about the cards possessed by one's opponents, the better one is able to play. And yet complete knowledge of an opponent's cards is generally impossible, (if one excludes cheating). The ability to play poker well thus depends, at least in part, on the ability to deduce what cards are held by an opponent, given the limited information available. Now suppose our agent possessed the ace of spades. Assuming the agent's sensory equipment was functioning normally, it would be rational of her to believe that she possessed this card. Now suppose she were to try to deduce what cards were held by her opponents. This could be done by first calculating all the various different ways that the cards in the pack could possibly have been distributed among the various players. (This is not being proposed as an actual card playing strategy, but for illustration!) For argument's sake, suppose that each possible configuration is described on a separate piece of paper. Once the process was complete, our agent can then begin to systematically eliminate from this large pile of paper all those configurations which are not possible, given what she knows. For example, any configuration in which she did not possess the ace of spades could be rejected immediately as impossible. Call each piece of paper remaining after this process a world. Each world represents one state of affairs considered possible, given what she knows. Hintikka coined the term epistemic alternatives to describe the worlds possible given one's beliefs. Something true in all our agent's epistemic alternatives could be said to be believed by the agent. For example, it will be true in all our agent's epistemic alternatives that she has the ace of spades.

On a first reading, this seems a peculiarly roundabout way of characterizing belief, but it has two advantages. First, it remains neutral on the subject of the cognitive structure of agents. It certainly doesn't posit any internalized collection of possible worlds. It is just a convenient way of characterizing belief. Second, the mathematical theory associated with the formalization of possible worlds is extremely appealing (see below).

The next step is to show how possible worlds may be incorporated into the semantic framework of a logic. Epistemic logics are usually formulated as normal modal logics using the semantics developed by Kripke [Kripke, 1963]. Before moving on to explicitly epistemic logics, we consider a simple normal modal logic. This logic is essentially classical propositional logic, extended by the addition of two operators: `' (necessarily), and `' (possibly). Let be a countable set of atomic propositions. Then the syntax of the logic is defined by the following rules: (i) if then is a formula; (ii) if are formulae, then so are and ; and (iii) if is a formula then so are and . The operators `' (not) and `' (or) have their standard meanings. The remaining connectives of classical propositional logic can be defined as abbreviations in the usual way. The formula is read: `necessarily ', and the formula is read: `possibly '. The semantics of the modal connectives are given by introducing an accessibility relation into models for the language. This relation defines what worlds are considered accessible from every other world. The formula is then true if is true in every world accessible from the current world; is true if is true in at least one world accessible from the current world. The two modal operators are duals of each other, in the sense that the universal and existential quantifiers of first-order logic are duals:



It would thus have been possible to take either one as primitive, and introduce the other as a derived operator. The two basic properties of this logic are as follows. First, the following axiom schema is valid: . This axiom is called K, in honour of Kripke. The second property is as follows: if is valid, then is valid. Now, since K is valid, it will be a theorem of any complete axiomatization of normal modal logic. Similarly, the second property will appear as a rule of inference in any axiomatization of normal modal logic; it is generally called the necessitation rule. These two properties turn out to be the most problematic features of normal modal logics when they are used as logics of knowledge/belief (this point will be examined later).

The most intriguing properties of normal modal logics follow from the properties of the accessibility relation, , in models. To illustrate these properties, consider the following axiom schema: . It turns out that this axiom is characteristic of the class of models with a reflexive accessibility relation. (By characteristic, we mean that it is true in all and only those models in the class.) There are a host of axioms which correspond to certain properties of : the study of the way that properties of correspond to axioms is called correspondence theory. For our present purposes, we identify just four axioms: the axiom called T, (which corresponds to a reflexive accessibility relation); D (serial accessibility relation); 4 (transitive accessibility relation); and 5 (euclidean accessibility relation):

The results of correspondence theory make it straightforward to derive completeness results for a range of simple normal modal logics. These results provide a useful point of comparison for normal modal logics, and account in a large part for the popularity of this style of semantics.

To use the logic developed above as an epistemic logic, the formula is read as: `it is known that '. The worlds in the model are interpreted as epistemic alternatives, the accessibility relation defines what the alternatives are from any given world.

The logic defined above deals with the knowledge of a single agent. To deal with multi-agent knowledge, one adds to a model structure an indexed set of accessibility relations, one for each agent. The language is then extended by replacing the single modal operator `' by an indexed set of unary modal operators , where . The formula is read: ` knows that '. Each operator is given exactly the same properties as `'.

The next step is to consider how well normal modal logic serves as a logic of knowledge/belief. Consider first the necessitation rule and axiom K, since any normal modal system is committed to these. The necessitation rule tells us that an agent knows all valid formulae. Amongst other things, this means an agent knows all propositional tautologies. Since there are an infinite number of these, an agent will have an infinite number of items of knowledge: immediately, one is faced with a counter-intuitive property of the knowledge operator. Now consider the axiom K, which says that an agent's knowledge is closed under implication. Together with the necessitation rule, this axiom implies that an agent's knowledge is closed under logical consequence: an agent believes all the logical consequences of its beliefs. This also seems counter intuitive. For example, suppose, like every good logician, our agent knows Peano's axioms. Now Fermat's last theorem follows from Peano's axioms - but it took the combined efforts of some of the best minds over the past century to prove it. Yet if our agent's beliefs are closed under logical consequence, then our agent must know it. So consequential closure, implied by necessitation and the K axiom, seems an overstrong property for resource bounded reasoners.

These two problems - that of knowing all valid formulae, and that of knowledge/belief being closed under logical consequence - together constitute the famous logical omniscience problem. It has been widely argued that this problem makes the possible worlds model unsuitable for representing resource bounded believers - and any real system is resource bounded.

Next: Axioms for Knowledge Up: Agent Theories Previous: Representing Intentional Notions
Fri Nov 4 16:03:55 GMT 1994