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:
-.2ex=0.9ex
.
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.