Suppose one wishes to reason about intentional notions in a logical framework. Consider the following statement (after [Genesereth and Nilsson, 1987]):
A naive attempt to translate (1) into first-order logic might result in the following:
Unfortunately, this naive translation does not work, for two reasons. The first is syntactic: the second argument to the predicate is a formula of first-order logic, and is not, therefore, a term. So (2) is not a well-formed formula of classical first-order logic. The second problem is semantic, and is potentially more serious. The constants and , by any reasonable interpretation, denote the same individual: the supreme deity of the classical world. It is therefore acceptable to write, in first-order logic:
Given (2) and (3), the standard rules of first-order logic would allow the derivation of the following:
But intuition rejects this derivation as invalid: believing that the father of Zeus is Cronos is not the same as believing that the father of Jupiter is Cronos. So what is the problem? Why does first-order logic fail here? The problem is that the intentional notions - such as belief and desire - are referentially opaque, in that they set up opaque contexts, in which the standard substitution rules of first-order logic do not apply. In classical (propositional or first-order) logic, the denotation, or semantic value, of an expression is dependent solely on the denotations of its sub-expressions. For example, the denotation of the propositional logic formula is a function of the truth-values of and . The operators of classical logic are thus said to be truth functional. In contrast, intentional notions such as belief are not truth functional. It is surely not the case that the truth value of the sentence:
is dependent solely on the truth-value of . So substituting equivalents into opaque contexts is not going to preserve meaning. This is what is meant by referential opacity. Clearly, classical logics are not suitable in their standard form for reasoning about intentional notions: alternative formalisms are required.
The number of basic techniques used for alternative formalisms is quite small. Recall, from the discussion above, that there are two problems to be addressed in developing a logical formalism for intentional notions: a syntactic one, and a semantic one. It follows that any formalism can be characterized in terms of two independent attributes: its language of formulation, and semantic model [Konolige, 1986a].
There are two fundamental approaches to the syntactic problem. The first is to use a modal language, which contains non-truth-functional modal operators, which are applied to formulae. An alternative approach involves the use of a meta-language: a many-sorted first-order language containing terms that denote formulae of some other object-language. Intentional notions can be represented using a meta-language predicate, and given whatever axiomatization is deemed appropriate. Both of these approaches have their advantages and disadvantages, and will be discussed in the sequel.
As with the syntactic problem, there are two basic approaches to the semantic problem. The first, best-known, and probably most widely used approach is to adopt a possible worlds semantics, where an agent's beliefs, knowledge, goals, and so on, are characterized as a set of so-called possible worlds, with an accessibility relation holding between them. Possible worlds semantics have an associated correspondence theory which makes them an attractive mathematical tool to work with [Chellas, 1980]. However, they also have many associated difficulties, notably the well-known logical omniscience problem, which implies that agents are perfect reasoners. A number of variations on the possible-worlds theme have been proposed, in an attempt to retain the correspondence theory, but without logical omniscience. The commonest alternative to the possible worlds model for belief is to use a sentential, or interpreted symbolic structures approach. In this scheme, beliefs are viewed as symbolic formulae explicitly represented in a data structure associated with an agent. An agent then believes if is present in its belief data structure. Despite its simplicity, the sentential model works well under certain circumstances [Konolige, 1986a].
In the subsections that follow, we discuss various approaches in some more detail. We begin with a close look at the basic possible worlds model for logics of knowledge (epistemic logics) and logics of belief (doxastic logics).