Artificial Intelligence Review (1991) 5, 53-70

Logical foundations of nonmonotonic reasoning Nadim Obeid & Raymond Turner Department of Computer Science, University of Essex, Wivenhoe Park, Colchester C04 3SQ, UK

Abstract. In this paper we shall review the main approaches to nonmonotonic reasoning which we classify from the perspective of their underlying logical settings as classical, intuitionistic, three-valuedlpartial models, and conditional. We shall be placing special emphasis on some of the prominent approaches. We shall also give hints on potential future directions and emphasize that more theoretical work is still needed before a move to application is made.

1 Introduction Nonmonotonic reasoning is problematic, both technically and conceptually. The foundations are still controversial. However, some progress has been made. In this paper we shall review the main approaches to nonmonotonic reasoning from the perspective of their underlying logical settings. Broadly speaking, they can be classifed as (1)classical, (2) intuitionistic, (3) three-valuedtpartial models, and (4) conditional. Intuitively, each of the approaches seems to have adequate motivation and justification to warrant its consideration and, with some degree of mixed success, they all furnish some insights into the problem of incomplete knowledge in Artificial Intelligence (AI). Even within the classical framework, which is the most studied and in some sense the most prominent, there has not yet been found a comprehensive theory which captures all the benefits of the various approaches, although Shoham's work (Shoham, 1987; 1988) can be viewed as a first step in such a direction. What seems to be the case is that each of these approaches, irrespective of the framework under which it can be classified, suffers some drawbacks. Either the semantics is obscure or it fails to capture some important aspects, andtor it has problems with semi-decidability. We shall present a general review of each of these frameworks by placing special emphasis on what we consider to be representative approaches of each framework. We shall also give hints on potential future directions and emphasize that more theoretical work is still needed before a move to application is made.

54

N. Obeid & R. Turner

2 Formal background Throughout the paper, L, LM, L~, Lp and L~ denote the usual propositional classical, modal, intuitionistic, partial-model and conditional logics, respectively. LQ, LQM, LQI, LQp and LQ~ denote those of First-Order Predicate Calculus (FOPC), modal, intuitionistic, partial-model and conditional logic, respectively. As primary proposJ.tional connectives we take ~ (negation), & (conjunction), v (disjunction) and --+ (implication). In some of the above languages, e.g. in L, LM and Lp, A ~ B can be taken as an abbreviation for (~A v B) and A v B can be taken as an abbreviation for ~(-nA & ~B). Let M be the primary modal operator (possibility and, in nonmonotonic context, consistency, dual of belief/knowledge or plausible as appropriate). Let N be the dual of M and let, in all the above languages, A < - - > B be an abbreviation for (A -+ B) & (B ~ A). Let a be a logic, i.e. a collection of 'logical' axioms and inference rules. S }-0 A denotes that A is deducible from the set S of formulas by using the axioms and inference rules of o. If S and X are sets of formulas, then S }-o X means that for each A from X, S F-,, A holds. By Tho(S) we denote {A: S}-,,A}.

3 Classical-based approach Classical logic-based attempts to solve the problems presented by incomplete information fall into two categories. The first category, which we shall call the Closed-World Reasoning (CWR) approach, includes those which assume that all the relevant positive information (e.g. which individuals exist and which predicates are satisfied by which individuals) is known. From this assumption it follows that anything that is not known to be true must be false. Thus, negative facts need not be explicitly represented, since they can be inferred from the absence of their positive counterparts. Such assumptions of complete positive information underlie PLANNER's THNOT (Hewitt, 1972) and related negation operators in AI programming languages (PROLOG), semantic networks, and in databases (Reiter, 1978), as well as more formal reasoning systems such as predicate completion (Clark, 1978) and Circumscription (McCarthy, 1980, 1986). The main theme of the second category, to which we shall refer as the Nonmonotonic Logic (NML) approach, is that the reasoning system should somehow be allowed to make 'guesses' rather than reserving judgement or assuming that whatever is not available is false. Among the systems which embody this idea are: Default logic (Reiter, 1980), Nonmonotonic logic I (McDermott & Doyle, 1980), Nonmonotonic logic II (McDermott, 1982), Autoepistemic logic (Moore, 1983, 1984), Truth maintenance systems (Doyle, 1979; McAllester, 1978, 1980). It should be noted that the two categories mentioned above are not mutually exclusive. Each has been used to achieve the other.

Logical foundations of nonmonotonic reasoning

55

3.1 Closed-world reasoning The idea of this approach is that only positive (assumed as complete) information about a domain is explicitly represented. Negative facts then may simply be inferred from the absence of their positive counterparts. Reiter (1978) calls this assumption the Closed-World Assumption (CWA). CWA on a knowledge-base, KB, corresponds roughly to an inference rule of the form: if KB )~ P then infer -np applicable to positive facts, P. This rule can be read as 'if P is not provable from the knowledge-base, assume ~ P ' .

3.1.1 Naive closure. Reiter (1978) provides the following syntactic realization (Naive Closure) of the CWA. Given a knowledge-base, KB, we define EKB', the negative extension of KB, as follows: EKB' = {~P(u'): P is a n-ary predicate letter, c( is an n-tuple of ground terms, and KB }-Pc~'} Then the naive closure of KB is defined as those formulae provable from KB U EKB'. We write KB F-NcA when A follows from KB O EKB'. It should be noted that the naive closure extends the knowledge-base by adding a set of ground literals. However, universal statements capturing the CWA for particular predicates do not generally follow from the naive closure of the knowledgebase. A semantic characterization of this type of closed-world reasoning can be given in terms of minimal Herbrand models, Van Emden & Kowalski (1976). However, it can be s h o w n that a minimal Herbrand model K is the only model (up to isomorphism) for KB U EKB' only if KB determines the set of individuals. Also, there is no room for genuinely incomplete knowledge under this approach. Consider a database containing only Block(A) v Block(B). It is easy to see that such a situation leads to inconsistent conclusions. Furthermore, FOPC together with CWA is not effectively computable. Thus, Negation As Failure adopts a weakened form of CWA because the }- relation is not fully implemented.

3.1.2 Database completion. The CWA allows a reasoning system to act on the assumption that 'the objects that can be shown to have a certain property by reasoning from certain facts are all the objects that have that property'. It does not, however, allow the system to derive this assumption. Database Completion by Clark (1978), remedies this shortcoming by making the completeness assumptions explicit in the database. The idea is that all of the information about a particular relation in the database, DB, is gathered together and a 'completion axiom' is added to DB. The axiom states that a particular tuple satisfies the relation only in those cases where DB says it must. Applying this process to all the relations in DB yields the completed database [Comp(DB)]. One of the drawbacks of this approach is that to preserve consistency there is no need for weakened conjectures (Reiter, 1982).

56

N. Obeid & R. Turner

However, Shepherdson (1984) shows that even weakened conjectures do not guarantee consistency.

3.1.3 Circumscription. Circumscriptive formalisms (McCarthy, 1977, 1980, 1986) add new axioms which force minimal interpretations on particular aspects of the partially specified world. These axioms, which represent some rules of conjectures, are based on syntactic manipulations rather than consistency. The most widely studied circumscriptive formalism is predicate circumscription. It allows explicit completeness assumptions, similar to Clark's completion axioms, to be conjectured as required. The idea is to restrict the domain of a predicate to those objects which are required to satisfy the theory at hand. This idea is formalized by means of a second-order axiom schema. Let P be an n-ary predicate and x' be an abbreviation for (xl, x2 ..... xn). Let A(~) be the result of replacing all occurrences of P in A by the predicate expression ~. Then the circumscription of P in A, circum(A,P), is the schema: A(~)&(Vx')((~(x') -~ P(x')) --~ (P(x') --* q~(x'))) Circumscriptive inference, ~-e, is then defined as A }-pB iff A & circum(A,P) [- B. McCarthy (1980) provides a 'soundness' result which shows that any instance of the schema resulting from circumscribing a single predicate in a sentence S in which P occurs is true in all {P}-minimal models of Davis (1980) argues that no general 'completeness' result can be obtained by identifying the 'circumscriptive theorems' with only those formulas true in all minimal models of the theory. However, Minker & Perlis (1983, 1984, 1986) prove a 'finitary' completeness result. Doyle (1985) observed that circumscription is related to the idea of implicit definability as it occurs in mathematical logic. However, circumscription does not always result in an implicit definition for a predicate P. In general, it is not even decidable whether P is implicitly defined. There are still more limitations on the applicability and efficacy of predicate circumscription (Etherington, 1988). It is believed that many of the limitations of predicate circumscription are due to the fact that only those predicates being minimized are allowed to vary. This has led McCarthy (1986) to develop a more general form of circumscription, formula circumscription. For further discussion of circumscription, see Sections 3.5 and 6.2 of Sheridan's paper in this issue.

3.2 Nonmonotonic logics Default logic, Reiter (1980), attempts to capture nonmonotonicity by introducing an operator M, where MA can be interpreted as 'it is consistent to assume A', and by introducing rules (defaults) which can be viewed as meta-rules representing instructions about how to create extensions to incomplete first order theories. Because default rules operate at the meta-level and they are not expressed within the

Logical foundations of nonmonotonic reasoning

57

language of the theory, concern is expressed about their representational power and the meaning of the operator 'M'. More homogeneous approaches, where nonmonotonic rules are expressed within the language, are NMLI and NMLII which attempt to capture nonmonotonicity by a consistency operator. Logically speaking, such an operator is better understood as an extensional operator rather than an intensional one. This should explain the proof-theoretic difficulties (i.e. which formulas should be proven) which faced NMLI and the model-theoretic difficulties (cf. Turner, 1984) which faced NMLII. Also, it should explain why autoepistemic logic appeared to have done better. Before we present these systems we introduce some relevant formal notations. Let a be a logic, i.e. a collection of 'logical' axioms and inference rules. Let S be a set of formulas of L or LM (which are considered as non-logical axioms). X is said to be a a-fixed point of the nonmonotonic theory S if, and only if, X = Tho(S U {MA:-hA q~ S}). Fixed Points (FPs) may be considered as candidates for the set of nonmonotonic theorems of S. A theory may have exactly one FP, no FP or more than one FP (cf. McDermott & Doyle, 1980, for examples). The intersection of all a-FP of S is denoted by THo(S).

3.2.1 Default logic. Default rules (or defaults), which can be viewed as meta-rules representing instructions about how to create extensions to incomplete first order theories, are expressions of the form: A: MB1 ..... MBn/C where A, Bi (0 i n), and C are first order sentences which share a c o m m o n set of variables and M is to be interpreted as 'it is consistent to believe'. We shall restrict the discussion to closed defaults. In the general case, defaults can contain formulas with free variables. A default theory is a pair where D is a set of defaults and W is a set of first order sentences. An extension E of represents an acceptable set of beliefs that one may hold about the incompletely specified world W. E should satisfy the following conditions: (1) E contains W; (2) E is deductively closed; (3) E is faithful to the default rules: if A: B1 ..... Bn/C is in D, A E E and -~Bi E E, then C E E; (4) E is a minimal set with properties (1)-(3).

Definition 3.1 Let A = be a default theory. Then for any set of sentences S let F(S) be a minimal set which satisfies the following conditions: (1) W ~_ F(S) (2) Th(F(S))=F(S) where Th(S) is the deductive closure of S (3) if A: B1 ..... Bn/C E D, A E F(S) and -nBi ~ F(S) (0 i n), then C E F(S).

58

N. Obeid & R. Turner

Then E is an extension for A iff F(E) = E. We end this section by pointing out some characteristics of and problems with default theories. Some default theories may have multiple extensions, where no extension is a proper subset of another, and some may have none. A default theory has an inconsistent extension iff W is inconsistent. While an extension is an internally consistent theory of the world, the union of two extensions may well be inconsistent. This leads Reiter to describe default reasoning as the process of selecting one extension of a theory and reasoning within this extension until the evidence forces revision of those beliefs, in which case a switch to another extension is needed. This forces Reiter's proof theory to consist of a procedure for determining, for a sentence B and theory T, whether B is in some extension of T, which amounts to testing whether B is in the union of all extensions of T. But this is not what is required by the above view of default reasoning. Also, as extensions are defined non-constructively, there is no way of 'isolating' a single extension of a theory, and thus no way of testing for theoremhood within an extension. Furthermore, Hanks & McDermott (1986) point out that any definition of default reasoning based on discrimination between extensions is actually beyond the expressive power of default logic, because there is no way of referring to an extension within the language of default logic. Because default rules operate at the meta-level and they are not expressed within the language of the theory, Konolige (1987) raises questions about the representational power of defaults, e.g. can defaults be nested and do conditional defaults exist? Also there is some concern over the meaning of 'M' since defaults are expressed as inference rules operating in conjunction with a fixed point construction.

3.2.2 Fixed point modal theories. McDermott & Doyle (1980) present a nonmonotonic modal logic 'NMLI'. They extend LQ by adding the modal operator M. MA is intended to be read as 'A is consistent'. The intended idea is to have a 'nonmonotonic' inference rule, NMIR, as follows: infer MA from the failure to infer ~A. Obviously, NMIR is a nonmonotonic inference rule. The inferences it allows depends on the context in which it is used; if the context is appropriately extended then some of the previously permitted conclusions may no longer be warranted. NMIR is characterized by means of FPs. For a given set S of premises, X is its fixed point if and only if X = Th(S U {MA: ~ A q~ S}) Following Moore (1983), the above definition may be made simpler as follows: X is a FP of S if, and only if, for any sentence A,

x = {c: s u {MA: ~ A ~ X} ~- C}. The above definition is non-constructive as X occurs on both sides of the equation. A set of premises S may have more than one FP. For example, the set {MA --+ ~C,

Logical foundations of nonmonotonic reasoning 59 MC - , ~A} has two FPs; one containing ~ C but not ~ A and the other containing ~ A but not -nC. Also, some sets, like the set (MC ~ ~C), have no FPs. Such possibilities lead McDermott & Doyle to define their non-monotonic derivability notion as follows: S ~-NML1Aiff A E TH(S). NMLI, as McDermott & Doyle point out, fails to capture a coherent notion of consistency. For example, MA does not follow from M(A & B) and the set {MA, ~A} has a FP. McDermott (1982) attempts to remedy the weakness of NMLI by basing NMLII on one of the standard modal systems T, $4 or $5. Following NMLI and Boolos (1979), MA is interpreted as 'A is consistent', and its dual LA is interpreted as 'A is provable'. The idea is that one of the above standard modal systems would provide the needed axioms and rules for M. NMLII accounts for nonmonotonic inference in the same way as NMLI does, except that the underlying notion of monotonic inference is defined in terms of }-T, }-s, or }-s5 instead of F-FoP(:. The attempt to strengthen the base logic is not conclusively successful. Nonmonotonic $5 collapses to monotonic $5. Doubts are raised about the consistency of n o n m o n o t o n i c T and $4 (cf. Turner, 1984) although McDermott proves the consistency of propositional non-monotonic T and $4. Also, it is questionable whether (a5) MA--~ LMA should be dropped out. Boolos (1979) presents a logic of provability, G, which captures the provability notion of formal arithmetic. The theorems of G are those sentences which, if appropriately translated, are the theorems of formal arithmetic. G consists of modal K together with (G) L(LA --+ A) --+ LA. Boolos also shows that if (T) LA--* A is added to G, inconsistency arises. What is rather curious to notice is that, although McDermott indicates his awareness of Boolos' logic G, he does not consider using it as a basis for a n o n m o n o t o n i c system, or consider systems without (T). This is in fact what Moore (1983) partially argued for. Another difficulty with McDermott's approach concerns the intuitions underlying the operator M. According to the semantic clause for M, MA is true at a world b just in case A is true at some world consistent with (accessible to) b. Turner (1984) argues that the accessibility relation R in the semantic framework is a relation between possible worlds (complete descriptions of states of affairs), but S, where MA may be assumed if ~ A cannot be monotonically inferred, does not fit the description of a possible world. That is, R cannot be a relation on theories such as S.

60

N. Obeid & R. Turner

3.2.3 Autoepistemic logic (AE). AE (Moore, 1983, 1984) is a logic for modelling the beliefs of agents who reflect on their own beliefs. Such reasoning may permit an agent to adopt beliefs on the basis of what it does not believe. 2 The autoepistemic analogue of a fixed point is a stable expansion. $1 is a stable expansion of S if, and only if, $1 = Th(S U {LA: A E S} U {-qLA: A ~ S}). A stable expansion $1 simply satisfies Stalnaker's conditions: (sl) $1 contains all truth-functional tautologies (s2) if A1 ..... A,, ~ $1 and A 1 ..... An }- B then B E $1 (~- means ordinary logical consequence) (s3) if A ~ $1 then LA E $1. (s4) if A ~ $1 then ~ L A E $1. In the original paper (Moore, 1983) Moore has provided a simple intuitive semantics. The type of objects which are of primary interest in AE are sets of sentences that can be interpreted as the beliefs of agents reflecting upon their own beliefs. Such sets are called AE theories. In the sequel we use $1 to refer to an AE theory. Note that, I is an interpretation of $1 if I is a truth assignment that conforms to the usual truth recursion, and I is a model of $1 if I makes all of the sentences in $1 true.

Definition 3.2 An AE interpretation I of $1 is an interpretation of $1 that satisfies the condition: I ~ LA iff A E $1.

Definition 3.3 An AE model of $1 is an AE interpretation of $1 in which all sentences in $1 are true.

Definition 3.4 $1 is semantically complete iff $1 contains every sentence that is true in every AE model of $1. A semantically complete set of beliefs is a set that contains everything that must be true, given that the set of beliefs is true and that it is the set of beliefs that is being reasoned about.

Definition 3.5 $1 is sound with respect to a set of premises S iff every AE interpretation of $1 that is a model of S is a model of $1. $1 is sound with respect to a set of premises S just in case all the beliefs in $1 must be ti ..le given that all the premises in S are true and S is the set of beliefs being reasoned about.

Definition 3.6 $1 is stable iff $1 satisfies Stalnaker's conditions, that is, if {C: SU{LA: A E Sl} U {-nLA: A ~ $1} }- C} _c $1.

Logical foundations of n o n m o n o t o n i c reasoning

61

Theorem 3.1 (Completeness) $1 is semantically complete iff $1 is stable. Stability of an agent's beliefs guarantees their semantic completeness, but it does not ensure soundness with respect to its premises. This is because the stability conditions do not tell us what an agent should not believe. As such, the agent may come to believe propositions that are not grounded in its premises. Therefore, there is a need for an additional constraint specifying that the only beliefs which an ideal agent has are the initial premises and those which are required by the stability conditions. This is what the next definition aims at expressing. Definition 3.7 $1 is grounded in a set of premises S iff $1 c_ {C: S © (LA: A ~ $1} O {~LA: A ~ $1} k C}).

Theorem 3.2 $1 is sound with respect to a set of premises S iff $1 is grounded in S. This theorem shows that the syntactic constraints on S and $1 capture the semantic notion of soundness. Definition 3.8 $1 is a stable expansion of S iff $1 is a superset of S that is grounded in S; that is, $1 = {C: S U {LA: A ~ $1} U {~LA: A ~ $1} k C}. That is, the beliefs of an ideally rational agent must be both semantically complete and grounded in its premises.

3.3 Possible world semantics Moore (1984) presents a possible worlds semantics for AE for ideally rational agents. Let K-- be a complete S5-model; that is, w R w' for every w and w' in W. The truth of a sentence is defined relative to a world and conforms to the usual truth recursion for propositional sentences. A sentence of the form LA is true at a world w if, and only if, A is true at every world w' accessible from w. Let L(k), the set of all facts which are believed in K, be the set {A: K,w k A for all w ~ K}. Then, the sets of all sentences that are true in every world of some complete S5-model are exactly the st'able AE-theories (Moore, 1984). The major outcome is that the sets of sentences which are true in every world in some complete S5-model are exactly the stable autoepistemic theories.

Theorem 3.3 $1 = L(K) for some complete S5-model iff $1 is stable, This result was also obtained by Halpern & Moses (1984). It states that an AE interpretation of a stable AE theory can be characterised by an ordered pair consisting of a complete S5-model, which specifies the agent's beliefs, and a propositional truth assignment, which specifies what is true in the actual world.

62

N. Obeid & R. Turner

Definition 3.9 If K is a complete S5-model and v is a propositional truth assignment, both defined on the base sentences of $1, then < K , v > is a possible-world interpretation of $1 iff $1 -- L(K). An atomic sentence p is true according to < K , v > iff v(p)=true. The truth conditions for the truth-functional connectives follow the usual recursion. Finally, < K , v > ~- LA iff A E L(K). Definition 3.10 < K , v > is a possible-world model of $1 iff < K , v > is a possibleworld interpretation of $1 and every sentence of $1 is true in < K , v > . Theorem 3.4 If < K , v > is an AE interpretation of $1, then < K , v > is an AE model of S1 iff v is consistent with the truth assignment for one of the worlds in K (Moore, 1984). This, intuitively, means that a set of beliefs is true only if the actual world is one of the worlds the agent thinks it may be so. Theorems 3.3 and 3.4 ensure that for every AE interpretation (model) of a stable theory there is a corresponding possible-world interpretation (model) and vice versa. As we are only interested in consistent stable expansions it seems appropriate, following Halpern & Moses (1984), to add the following condition to Stalnaker's conditions: (s5) $1 is propositionally consistent (s5) simply states that the whole language is not an acceptable belief state. The axiom which corresponds to (s5) is: (D) L A - + MA. Therefore, the underlying modal logic of AE is KD45. Levesque [1987) develops a modal logic with modalities both for 'believe' and for 'believe only'. The latter modality is intended to capture the fact that some theory and its consequences capture the sum of an agent's knowledge. Levesque shows that augmenting a theory containing the believe only operator with lack of knowledge defaults makes it possible to do certain kinds of default reasoning. For further details, see Section 8 of Measor's paper in this issue. Levesque also shows that the logic is a quantificational generalization of Moore's (1985) propositional autoepistemic logic, with a similar semantic basis in stable expansions.

4 Intuitionistic-based approach Unlike most of the formalisms which have been suggested to capture nonmonotonicity, Gabbay (1983) presents an approach which employs intuitionistic rather than classical models. It does not employ the fixed-point construction as in NMLI and NMLII. Instead nonmonotonic deduction steps are applied iteratively as with ordinary monotonic deduction. The rule of nonmonotonic inference which is

Logical foundations of nonmonotonic reasoning 63 e m p l o y e d in g is just the transitive closure of Reiter's default rule (Reiter, 1980). As such, in g it is not the case that a proposition is either true or false, but rather a p r o p o s i t i o n is either established as true or not. None the less, failure to establish the truth value of a p r o p o s i t i o n is not the same as saying that it is false. Intuitively Gabbay considers situations w h e r e an agent's k n o w l e d g e of the actual state of affairs is o n l y partial. The agent at any m o m e n t m a y k n o w that certain propositions are true and that some others are false, but it does not k n o w everything. As time proceeds, the agent's k n o w l e d g e increases w h i c h m a y lead to some of these previously u n k n o w n propositions being d e c i d e d one w a y or the other. Formally, a Gabbay's m o d e l structure, Fitting (1969), is a triple G = < T , -<, h > w h e r e T is a n o n - e m p t y set (moments of time), -< (the before/after relation) is reflexive and transitive, h is a function with d o m a i n T. For each t E T and an atomic well-formed formula (wff) p, h assigns the value 0 or I (0 -<' 1). The relation _<' is an ordering on the truth values). A first constraint on h is its m o n o t o n i c i t y with respect to T. (C1) (Vt, t' E T)(} atomic wff P)((t -< t') ~ (h(t,P) -<' h(t,P))). The extension of h to all wffs (of the propositional part of the language L supp l e m e n t e d with the u n a r y operator M) is done recursively as follows: (al) (a2) (a3) (a4) (a5)

h(T, A & B) = 1 iff h(T, A v B) = 1 iff h(t, mA) = 1 iff h(t, A ---, B) = 1 iff h(t, MA) = 1 iff

h(t, A) = h(t, A) = (V tl) (tl ('v' tl) (tl (3 tl) (tl

1 and h(t, B) = 1 lorh(t,B) = 1 -> t)(h(tl, A) = 0) -> t)(h(tl,A) = 1::9 h(tl, B) = 1) -> t)(h(tl, A) = 1).

Thus, the s y s t e m has a n o n m o n o t o n i c flavour in that: wffs containing M, and only these, do not preserve their truth values, i.e. it is possible to have a case where at a m o m e n t t, M A is true but at a later m o m e n t t', ~ A is true ( ~ M A is true). As a c o n s e q u e n c e of w e a k e n i n g the base logic to an intuitionistic one, not all the classical tautologies are sustained by the semantics. For instance, the following principles: (LEM)

A v ~A

(CtP)

(~A----, qB)--. (B--~ A)

w h i c h are classically valid, fail in ~t. There seem to be some naturally good reasons for basin n o n m o n o t o n i c reasoning on an intuiti0nistic basis. However, Gabbay's system is too constrained as it only allows m o d a l i z e d (preceded by M) formulae to change their truth values. This can be relaxed if one takes n o n m o n o t o n i c i t y to be inherent rather than build on a m o n o t o n i c system, Obeid (1987). Also, it m a y be w o r t h w h i l e investigating h o w the i n t r o d u c t i o n of M affects intuitionistic models and in particular the m e a n i n g of--~. Obeid (1989) s h o w s that the notion of intuitionistic truth and c o n s i s t e n c y m a y be represented within a three-valued based n o n m o n o t o n i c system.

64

N. Obeid & R. Turner

5 Three-valued based approach Despite the general agreement among AI researchers that complete information is hard to obtain, even in the most manageable situations, and that there will always be propositions whose truth status cannot be decided, most of the earlier approaches which are classically based nonmonotonic formalisms seem to resort to adding intermediary truth values between truth and falsity. This, in fact, is one of the basic and most important features which distinguishes three-valued logics from classical logic. Such a difference is reflected semantically by partial models (partial states of information) for three-valued logics as opposed to possible worlds (complete states of knowledge) for classical logic. Turner (1984) advocates what he calls 'an alternative basis for non-monotonic inference'. He proposes that partial states of knowledge are to be represented by partial models and presents the following semantics which enlists Kleene's strong three-valued connectives. Definition 5.1 A model structure for L~, is K = where B is a non-empty set, R is a binary relation on B and g is a truth assignment function for atomic wffs. The interpretation of R may be thought of as a 'plausible' extension between states. Given b, bl are members of B, we shall write b R bl to mean that the state bl is a 'plausible' extension of the state b. We employ the notion K ~ g A (resp. K ~ g A) to mean that A is accepted as true (resp. false) in K with respect to g. For convenience, reference to g will be omitted except where confusion may arise. Let A, B be wffs then, the truth '~' and the falsity '~' notions are recursively defined as follows: Definition 5.2

(i) (ii) (iii) (iv) (v)

K,b ~ T K,b ~ p K,b~A&B K,b p 1A K , b p MA

iff iff iff iff

g(b,p) = true for p atomic K,b~AandK,b~ B K,b ~ A 3b1~ B)(bRblandK,bl~A)

(i') (ii') (iii') (iv') (v')

K,b ~ F K,b ~ p K,b~A&b K,b 4 ~ A K,b~MA

iff iff iff iff

g(b,p) = false for p atomic K,bgAorK,b~ B K,b ~ A (VblEB)(ifbRblthenK,bl~A).

Ginsberg (1987) has argued that the extensions to classical logic (referring to the technique used by classically-based formalisms) share two properties: (1) the formal addition of truth values encoding intermediate levels of validity between truth and falsity, and (2) the addition of truth values encoding intermediate levels of certainty between a state of complete information (true/false) and a state of complete ignorance or no information (unknown). Ginsberg also shows that each of

Logical foundations of nonmonotonic reasoning

65

the above mentioned properties can be described by associating lattice structures to the collection of truth values involved. He also describes a general framework in w h i c h both Default Logic and Truth Maintenance Systems (TMSs) are only special cases. Thus, one advantage of using partial models to represent partial states of knowledge is that intermediary levels of validity and certainty are naturally encoded in the object language. As such, nonmonotonicity is not added on to some base logic, but rather it is natural and inherent in the make-up of the system. Obeid (1989) follows Turner's intuition and takes his idea a step further to develop a sound a n d c o m p l e t e system, to be referred to as K l e e n e - T u r n e r ' s system (K-T), which allows a distinction between two modal notions, 'epistemic possibility' and 'plausibility', to be made. The work is taken a step further to develop sound and complete modal KK-t, TK-T and S4-KT which are the analogues of standard modal K, T and $4. To obtain the language, LMp, for Modals K - T , Lp is extended with a modal operator 'P', where for a wff A, PA is to be read as 'A is epistemically possible'. Let L be the dual of P, i.e. LA = = ~ P ~ A .

Definition 5.3 A model structure for LMp is K = where B is a none m p t y set, R, R' are binary relations on B and g is a truth assignment function g for atomic wffs. The interpretation of R (resp. R') may be thought of as a 'plausible' (resp. an 'epistemic possible') extension between states. Given b, b l are members of B, we shall write b R b l (resp. b R' bl) to mean that the state bl is a 'plausible' (resp. an 'epistemic possible') extension of the state b.

Definition 5.4 (i)

K,b ~ T

(ii) (iii) (iv) (v) (v)

K,b ~ p K,b ~ A & B K,b p ~ A K,b~MA K , b ~ PA

(i')

K,b ~ F

(ii') (iii') (iv') (v') (vi')

K,b ~ p K,b-~A&B K,b ~ ~ A K,b{MA K,b 4 PA

iff iff iff iff iff

g(b,p) = true for p atomic K,bpAandK,bpB K,b ~ A (3b1@ B)(bRblandK,bl~ (3blE B)(bR'blandK,bl~

iff iff iff iff iff

g(b,p) = false for p atomic K,b~AorK,b~ B K,b p A (Vbl~ B)(ifbRblthenK,bl~A) (V bl E B)(if b R' b l then K,bl ~ ~A).

A) ~A)

It should be noted that, in using a three-valued approach to inference in states of incomplete information, there is no need to resort to fixed-point operators and the like to chaacterize the extension of a set of premises.

66

N. Obeid & R. Turner

6 Conditional-based approach Although the philosophical foundations and motivations for conditionals and n o n m o n o t o n i c reasoning are different, it is surprising that AI researchers did not first look at conditional logics to capture nonmonotonic reasoning. For both conditional and nonmonotonic inference seem to embody similar patterns of revision along with deduction, though at different levels (Van Benthem, 1984). The only serious work we know of that has been done on relating conditional and n o n m o n o t o n i c reasoning is that of Bell (1988) and Delgrande (1987, 1988). In this section, we shall look at Shoham's semantic framework, to which Bell presented an axiomatization. First, however, we shall look at theory preference, even though it has arguably little to do with conditionals.

6.1 Theory preference Preference started in semantic networks systems. The idea is to prefer whichever conclusion that can be reached by traversing the smallest n u m b e r of network arcs. Etherington (1982) shows how to construct networks that defeat the shortest path heuristics. Touretzky (1986) presents a more sophisticated ambiguity resolution device, the inferential distance topology. Despite its limited success, Touretzky's work could be taken to suggest that it may be possible to find some set of general principles that avoid the necessity of ad hoc manipulation of knowledge bases. Poole (1985) presents a preference criterion for default theories. This is motivated by the view that defaults are not to be used to construct theories but rather to find explanations for particular conjectures. For instance, a rule is more specific than another if there is no situation which makes it applicable without also making the less-specific rule applicable.

6.2 Shoham's framework and preference logics Shoham (1987) claims that m a n y of the formalisms which have been put forward for n o n m o n o t o n i c reasoning are only superficially very different• He suggests a general semantic framework which subsumes m a n y of these formalism. Among these formalisms are: circumscription, default logic, autoepistemic logic (Halpern & Moses, 1984), and Halpern & Moses's logic of knowledge. Let Z be a standard logic (propositional or first order predicate calculus) and ' < ' be a strict partial order on the class I of interpretations. Intuitively, i' > i means that the interpretation i is preferred over the interpretation i'. L and < define a new logic £< called a preference logic. The syntax of E< is identical to that of Z. As for the semantics, the notions of satisfaction, validity and entailment are defined in terms of those of L as follows.

Definition 6.1 i p> A iff i ~- A and not[(3 i')(i < i' and i' ~ A) An interpretation i preferentially satisfies A in the frame for E< iff i ~ A and there is no i'such that (i < i' and i'~ A). We say that i is a preferred model of A.

Logical foundations of nonmonotonic reasoning

67

Bell noticed that for the above definition to make sense, < must be well-founded.

Definition 6.2 A H> B iff {V i} {if i ~> A then i ~ B}. A preferentially entails B if, and only if, any interpretation i such that i ~> A is such that i H B; that is, if the models of B are a superset of the preferred models of A. Shoham defines the preference relation (minimality criterion) for three nonmonotonic formalisms, namely: predicate circumscription, K45-models of autoepistemic logic and default logics. Bell has put forward the claim that the conditional logic C is the logic of nonmonotonicity. We give a brief proof-theoretic account of Bell's system. The language, Lc, of C, is the language of propositional calculus (resp. first-order predicate calculus), whose connectives are - , &, v and + (resp. - , &, v, -+, V and 3), extended with the intensional conditional operator ' ~ ' . The conditional logic C is the smallest subset of Lc that is closed under the following axiom schemas and inference rules.

Axiom schemas:

{pc} (ID}

{cs} (MP}

{co} (AD}

{CE}

Truth-functional Tautologies A~A A&B --+ (A ~ B) (A ~ B) ~ (A ~ B) {A ~ B}&(A ~ C) --~ {A ~ B&C} (A ~ C)&(B ~ C)--+ (AvB ~ C) (A ~ B)&(B ~ A) --+ ((A ~ C) --+ (B ~ C)).

Inference rules: (Mp) (RCM)

From A and A -+ B infer B from B -+ C infer (A ~ B)-+ (A ~ C].

In fact, C is equivalent to Lewis's counterfactual logic VC, Lewis (1973), without the axiom: (AS)

-n(A ~ ~B)&(A ~ C) ~ (A&B ~ C).

6.3 Normality conditional In an attempt to capture (some aspects of) default reasoning Delgrande (1987, 1988) suggests using conditionals. His logic is called N. He interprets a conditional 'A B' as is 'if A then normally B', and 'A ~ B' is true just in case B is true in the least exceptional worlds in which A is true. Quantified conditional sentences are then taken to express generic conditionals. Delgrande takes his normality conditionals to be like most known conditionals in failing to satisfy contraposition, monotonicity (strengthening of antecedent) and transitivity. In addition, Modus Ponens should also fail for the normality conditional.

68

N. Obeid & R. T u r n e r

D e l g r a n d e i n t e r p r e t s c o n d i t i o n a l s t a t e m e n t s as e x p r e s s i n g defaults. T h i s l e a d s h i m to p r o p o s e the f o l l o w i n g t e n t a t i v e n o n m o n o t o n i c i n f e r e n c e rule. Let T = < D , W > w h e r e D is a set of defaults of the form (Vx)(A ~ B) a n d W is a set of c o n t i n g e n t l y true facts. T h e n T J-~, A iff D [-~. W ~ A. H o w e v e r , this rule as it s t a n d s fails to give the i n t e n d e d r e s u l t for a large class of s i m p l e cases. This l e a d s h i m to suggest two e q u i v a l e n t w a y s of r e m e d y i n g this. T h e first a p p r o a c h i n v o l v e s e x t e n d i n g D, the set of defaults, by a d d i n g d e f a u l t s w h i c h state that a p p a r e n t l y i r r e l e v a n t facts are irrelevant. T h e s e c o n d a p p r o a c h i n v o l v e s e x t e n d i n g W on the a s s u m p t i o n that the a c t u a l w o r l d is one of the m o s t n o r m a l . T h e i m p a c t of this s e c o n d a p p r o a c h is to a d d i n s t a n t i a t i o n s of the a x i o m s c h e m a (A ~ B) --~ (A --~ B) w h i c h fails for the n o r m a l i t y c o n d i t i o n a l . N o n e the less, we can p r o v e that the n o r m a l i t y c o n d i t i o n a l c o l l a p s e s to entailment. This d r a w s D e l g r a n d e ' s a p p r o a c h a s t e p nearer to P o o l e ' s (Poole, 1984, 1988). T h e f a i l u r e of D e l g r a n d e ' s a p p r o a c h leaves us w i t h no s e r i o u s c o n d i t i o n a l - b a s e d a p p r o a c h at the object level for n o n m o n o t o n i c reasoning. H o w e v e r , it is w o r t h w h i l e p u r s u i n g a n d w e are in the p r o c e s s of doing just that. For further d e t a i l s of D e l g r a n d e ' s a p p r o a c h , see S e c t i o n 3 of Clarke's p a p e r in this issue.

Acknowledgment We w o u l d like to t h a n k M a r i s a B o s t o c k for p r o o f - r e a d i n g the m a n u s c r i p t .

Notes 1. For the connections between default logic and circumscription (cf. Etherington, 1987); between default logic and autoepistemic logic (cf. Konolige, 1987); and between autoepistemic logic and circumscription (cf. Konolige, 1989). Also, Shoham (1987) suggests that most of the above formalisms and similar ones are only superficially very different. 2. Stalnaker (1981) has observed that nonmonotonicity in AE arises because the meaning of an AE-statement is context-sensitive: the meaning of the belief operator L depends on all of the agent's beliefs: its meaning changes if the agent's beliefs change. Moore puts it as follows: 'the operator L functions like an indexical such as 'T', "now", whose meanings change with context'. In fact. similar such remarks apply to the operator M in NMLI and NMLII.

References Bell, J. (1989) Predictive Conditionals, Nonmonotonicity and Reasoning about the Future. Ph.D. Thesis, University of Essex, Colchester, UK. Benthem, J. Van (1984) Partiality and Nonmonotonicity in Classical Logic. Center for the Study of Language and Information, Report No. CSLI-84-12. Boolos, G. (1979) The Unprovability of Inconsistency. Cambridge University Press, London. Clark, K. L. (1978) Negation as Failure. In Logic and Databases (eds H. Gallaire & J. Minker). Plenum Press, New York, pp.293-322.

Logical f o u n d a t i o n s of n o n m o n o t o n i c reasoning

69

Davis, H. (.1980) The Mathematics of Non-Monotonic Reasoning. Artificial Intelligence, 13, 73-80. Delgrande, J. P. (1987) A First-Order Logic for Prototypical Reasoning. Artificial Intelligence, 33, 105-130. Delgrande, J. P. (1988) An Approach to Default Reasoning Based on a First-Order Conditional Logic: Revised Report. Artificial Intelligence, 36, 63-90. Doyle, J. (1979) A Truth Maintenance System. Artificial Intelligence. 12~ 231-272. Doyle, J. (1985) Circumscription an Implicit Definability. Journal of Automated Reasoning, 1, 391-405. Emden, M. H. Van and Kowalski, R. A. (1976) The Semantics of Predicate Logic as a Programming Language. JACM, 23, 723-742. Etherington, D. W, (1982) Finite Default Theories. M.Sc. Thesis, Department of Computer Science, University of British Columbia. Etherington, D. W. (1986) Reasoning with Incomplete Information: Investigation of Non-Monotonic Reasoning. Ph.D. Thesis, Department of Computer Science, University of British Columbia. Etherington, D. W. (1987) Relating Default Logic and Circumscription. Proceedings lOth International Conference on Artificial Intelligence~ pp.489-494. Etherington, D. W. (1988) Reasoning with Incomplete Information. Research Notes in Artificial Intelligence. Pitman, London. Fitting, M. (1969) Intuitionistic Logic, Model Theory and Forcing. North-Holland, Amsterdam. Gabbay, D. (1983) Intuitionistic Basis for Non-Monotonic Reasoning. In Proceedings of the Conference on Automated Deduction. Lecture Notes in Computer Science, No. 6~ pp.260-273. Ginsberg; M. L. (ed.) (1987) Multi-valued logics. In Readings in Nonmonatonic Reasoning, Morgan Kaufmann Publishers, Inc., 252-255. Halpern, J. & Moses, Y. (1984) Towards a Theory of Knowledge and Ignorance, Preliminary Report. Technical Report RJ 4448 48316~ IBM Research Laboratory. San Jose. Hanks~ S. & McDermott, D. (1986) Default Reasoning, Non-Monotonic Logics and the Frame Problem. AAAI-86, 328-333. Hewitt, C. (1972) Description and Theoretical Analysis lUsing Schemata) of PLANNER: A Language for Proving Theorems and Manipulating Models in a Robot. AI Memo 251. MIT Project MAC, Cambridge, Mass. Konolige, K, (1987) On the Relation between Default Theories and Autoepistemic Logic, Proceedings lOth International Conference on Artificial Intelligence, pp.394-401. Konolige, K. (1989) On the Relation between Autoepistemic Logic and Circumscription, Proceedings 12th International Conference on Artificial Intelligence, pp.1213-1218. Levesque, H. (1987) All I Know: An Abridged Report. AAAI-87, Seattle, WA, pp.426-431. Lewis, D. (1973) Counterfactual. BlackwelL Oxford. McAllester, D. A. (1978) A three-Valued Truth Maintenance System. AI Memo 473, MIT, Cambridge, Mass. McAllester, D. A. (1980) An Outlook On Truth Maintenance. AI Memo 551, MIT, Cambridge, Mass. McCarthy, J. (1977) Epistemological Problems of Artificial Intelligence. Proceedings of the Fifth International Joint Conference on Artificial Intelligence, 1083-1044. McCarthy, J. (1980) C i r c u m s c r i p t i o n - A Form of Non-Monotonic Reasoning. Artificial Intelligence, 13, 27-39. McCarthy, J. (1986) Application of Circumscription to Formalizing Commonsense Knowledge. Artificial Intelligence, 28, 89-116. McDermott, D. & Doyle, J. (1980) Non-Monotonic Logic I. Artificial Intelligence, 13, 41-72. McDermott, D. (19821 Non-Monotonic Logic II: Non-Monotonic Modal Theories. JACM, 29 (1), 35-57. Minker~ I. & Perils, D. (1983) On the semantics of Circumscription. Technical Report, University of Maryland. Minker, J. & Perils, D. (1985) Circumscription: Finitary Completeness Result. Unpublished Draft. University of Maryland.

70

N. Obeid & R. T u r n e r

Minsky, M. (1975) A Framework for Representing Knowledge. In The Psychology of Computer Vision. (ed. P. Winston), McGraw-Hill, New York, pp.211-277. Moore, R. (1983) Semantical Consideration of Non-Monotonic Logic, International Joint Conference on Artificial Intelligence, pp.272-279. Moore, R. (1984) Possible World Semantics for Autoepistemic Logic, Workshop on Non-Monotonic Reasoning, New Paltz, New York, pp.344-354. Moore, R. (1985) Semantical Consideration of Nonmonotonic Logic, Artificial Intelligence, 25, 75-94. Obeid, N. (19871 Towards a Model of Information Growth. Ph.D. Thesis, Department of Computer Science, University of Essex, Colchester, UK. Obeid, N. (1989) Partial Models Basis far Non-monotonic Reasaning, Research Note CSM-140. Department of Computer Science, University of Esex, Colchester, UK. Perils, D. & Minker, J. (1986) Completeness Results for Circumscription, Artificial Intelligence, 28, 29-42. Poole, D. L. (1984) A Logical System for Default Reasoning. AAAI Workshop on Nan-Monotonic Reasoning, NY, 373-384. Poole, D. L. (1985) On the comparison of Theories: Preferring the Most Specific Explanation, Proceedings of the 9th International Joint Conference on Artificial Intelligence, pp.144-147. Poole, D. L. (1988) A Logical Framework for Default Reasoning, Artificial Intelligence, 36, 27-47. Reiter, R. (1978) On Closed-World Data Bases. In Logic and Data Bases (eds H. Gallaire & J. Minker/, Plenum Press, New York, pp.55-76. Reiter, R. (1980) A Logic for Default Reasoning. Artificial Intelligence, 13, 81-132. Reiter, R. (1982) Circumscription hnplies Predicate Completion (Sometimes). Proceedings of the American Association fl~r Artificial Intelligence, pp.418-420. Shepherdson, J. (1984) Negation as Failure: A Comparison of Clark's Complete Data Base and Reiter's Closed-World Assumption. Journal of Logic Programming, 1, 51-79. Shoham, Y. (1987) Nonmonotouic Logics: Meaning and Utility. Proceedings of the lOth International Conference on Artificial Intelligence, pp.388-393. Shoham, Y. (1988) Reasoning about Change: Time and Causation from the Standpoint of Artificial Intelligence, MIT Press. Cambridge. MA. Stalnaker, R. (1981) A Note on Non-monotonic Modal Logic. Unpublished Manuscript, Department of Philosophy, Cornell University. Touretzky, D. S. (1986) The Mathematics oJ Inheritance Systems. Pitman, London. Turner, R. (1984) Logics for Artificial Intelligence. Ellis Horwood Limited. Chichester. pp.59-76.