Reset reproduction of an article appearing in Fundamenta Informaticae Vol. 20, No. 1–3 (Spring 1994), pp. 35-73. Resetting prepared from submission of November, 1993. Submission \begin{matrix}c \\ ◯ \end{matrix}1993 Jon Doyle. All rights reserved. Available

via http://www.medg.lcs.mit.edu/doyle.

Reasoned Assumptions and Rational Psychology

Jon Doyle doyle@lcs.mit.edu Massachusetts Institute of Technology, Laboratory for Computer Science Cambridge, Massachusetts 02139, U.S.A.

Abstract

Logical epistemology unduly sways theories of thinking that formulate problems of nonmonotonic reasoning as issues of nondeductive operations on logically phrased beliefs, because the fundamental concepts underlying such reasoning have little to do with logic or belief. These formulations make the resulting theories inappropriately special and hide the characteristic structures of nonmonotonic reasoning amid many unrelated structures. We present a more direct mathematical development of nonmonotonic reasoning free of extraneous logical and epistemological assumptions, and argue that the insights gained in this way exemplify the benefits obtained by approaching psychology as a subject for mathematical investigation through the discipline of rational psychology.

For Joseph A. Schatz, teacher and friend

1. Reasoning, logic, and psychology

Nonmonotonic reasoning, the study of making and revising assumptions in a reasoned or principled way, needs little introduction in artificial intelligence today thanks to years of extensive exposition, analysis, and application. In spite of an admirable history of progress, however, the subject stands in need of some rethinking and redirection as the strengths and limitations of the accepted theories become clearer. This paper seeks to further this rethinking and redirection by presenting the foundations of nonmonotonic reasoning through a mathematical and philosophical approach closer to the concepts and methods of modern physics and rational mechanics than to the standard formulations of artificial intelligence. I believe these concepts and methods, which seek to find the most appropriate means for describing and understanding psychological structure and behavior, will prove productive for rethinking other parts of artificial intelligence as well. This introduction thus attempts to set out some of the motivations for this rethinking and to motivate the methods underlying the formal treatment.

This paper celebrates the twentieth volume of Fundamenta Informaticae. The year of its writing (1993) also marks the twentieth anniversary of my involvement in the field of artificial intelligence; the fifteenth anniversary of the appearance of the original nonmonotonic logic (McDermott & Doyle, 1980); and the tenth and fifth anniversaries (respectively) of the appearance of my mathematical monograph (Doyle, 1983c) and my foundational monograph (Doyle, 1988), from which the present paper derives and upon which it improves, and looking back from these anniversaries has led me to include some personal interpretations of their history in this introduction.

Doyle

1.1 Nonmonotonic reasoning

Though the reader will likely find the notion familiar, a few words about the term “nonmonotonic reasoning” should aid in understanding the discussion to follow.

Intuitively speaking, nonmonotonic reasoning refers to reasoning involving nonadditive changes in beliefs, preferences, intentions, and other mental attitudes. The intuitive notion, however, is meaningless on its own because reasoning is an activity, and activities are not inherently monotonic or nonmonotonic; any monotonicity and nonmonotonicity of reasoning must be relative to how we view the reasoning in terms of aspects of mental states. In the usual usage in theoretical artificial intelligence, one views mental states as consisting of sets of mental attitudes and reasoning as a process that fills out and changes these sets over time. One can thus identify two very different senses of nonmonotonicity of reasoning: temporal nonmonotonicity, in which mental attitudes may appear and vanish over time, and logical nonmonotonicity, in which filling out larger sets of attitudes may yield fewer conclusions than filling out smaller sets. Mathematically, temporal nonmonotonicity compares mental attitudes as time increases, while logical nonmonotonicity compares consequences as mental attitudes increase.

Temporal nonmonotonicity may occur routinely and unexceptionally, for example through direct temporal variation of mental attitudes by perceptual or cognitive systems that add and subtract attitudes to reflect changes or anticipated changes in the world (as might happen if some of the attitudes describe the contents of the retina). Logical nonmonotonicity may occur because the reasoner derives some attitudes as conclusions from others as long as the right circumstances obtain. In the canonical example, the reasoner infers that Tweety flies from the information that Tweety is a bird, but not from the information that Tweety is also a penguin, information that defeats or undercuts the usual conclusion. In general, however, the division between these two forms of nonmonotonicity is not sharp, as one may draw conclusions over time to convert logical nonmonotonicity into temporal nonmonotonicity, or replace mental simulations with atemporal reasoning or logics to convert temporal nonmonotonicity into logical nonmonotonicity (cf. (Makinson & Gärdenfors, 1991)).

Reasoned Assumptions and Rational Psychology

Theorists and practitioners in artificial intelligence recognized the need for logically nonmonotonic reasoning early on, motivated by problems of reasoning about knowledge and actions, by the desire to make plausible commonsense inferences, and by the desire to speed problem-solving searches by making quick decisions about where to search that would yield information useful for guiding the search even if proven wrong. They suggesting ways of expressing nonmonotonic reasoning rules (e.g., (McCarthy & Hayes, 1969; Sandewall, 1972)) and implementing reasoning systems that performed versions of these (e.g., (Sussman, Winograd, & Charniak, 1971)), but rigorous and formal theories appeared later, for unlike ordinary logic, in which one takes contradictions to indicate flawed axioms, useful commonplace rules of nonmonotonic reasoning can provide conflicting conclusions in some cases, conflicts that call for adjudication, perhaps case by case, rather than for abandonment or revision of the conflicting rules. In another canonical example, the reasoner infers that Nixon is a pacifist because Nixon is a Quaker, but also infers Nixon is not a pacifist because Nixon is a (US) Republican, and has to decide which of these reasonable conclusions to accept while keeping the rules that led to them. The early proposals offered no precise ways of treating such conflicts, even when anticipated, as identifying coherent notions of nonmonotonic conclusions proved a perplexing task.

I formulated perhaps the first rigorous solution to this problem in 1976 as the two fundamental principles of my original reason maintenance system or RMS (Doyle, 1976, 1979) (renamed so from “truth maintenance system” or TMS in (Doyle, 1980)), which introduced the now-familiar notion of nonmonotonic justification. (Some may also consider McCarthy’s (1977) probably contemporaneous early notion of circumscription a solution to this problem, or even credit the older logical theory of implicit definition (Doyle, 1985).) The RMS represents mental attitudes (or other representational or procedural items) by structures called nodes that the RMS labels as either in or out (of the current state). The RMS also records sets of justifications or reasons for each node, most of which express simple boolean combinations of the labelings of nodes we denote as “A \\ B ∥− c” and read as “A without B gives c”, meaning that the node c should be in if each node in the set A is in and each node in the set B is out. The RMS then seeks to construct labelings for the nodes from these justifications, labelings that satisfy two principles: a “stability” principle of labeling each node in if and only if one of its reasons is valid in the labeling (i.e., expresses hypotheses “A without B” that match the labeling), and a “groundedness” principle demanding that labelings provide each node labeled in with a noncircular argument in terms of valid reasons. The structure for justifications given above makes both of these principles perfectly unambiguous. Indeed, these principles convert nonmonotonic reasoning tasks into problems for algorithmic analysis, and different versions of RMS explored different graph-theoretic techniques for analyzing systems of nodes and justifications.

1.2 Logical formalizations

The fundamental RMS principles led, in time, to a variety of formalizations of the stability and groundedness notions. The initial and most abidingly popular formalizations clothed these principles in logical garb: nonmonotonic logic (McDermott & Doyle, 1980) and the logic of defaults (Reiter, 1980), together with the circumscription rule of inference (Mc-Carthy, 1977, 1980), which as a class of inference operators rather than a “logic” has a somewhat different character from nonmonotonic and default logics. Each of these theories formalizes nonmonotonic reasoning by encoding groundedness and the presence and absence of knowledge in terms of logical provability and unprovability, or in terms of logical consistency instead of provability. For example, the simplest transcription of the canonical example into nonmonotonic logic translates the inference as the implication b ∧ ¬L¬f → f, where L stands for the provability modality, b stands for Tweety’s birdness, and f for Tweety’s flying. A similar transcription of RMS justifications translates them into the form a_{1} ∧ … ∧ a_{m} ∧ ¬L¬b_{1} ∧ … ∧ ¬L¬b_{n} → c.

Formalizations, as mathematical characterizations of ideas, may be either good or bad characterizations. The initial formalizations of nonmonotonic reasoning, along with their monotonously logical subsequent variants, improvements, and extensions, proved very good as ways of making the theoretical problems of logically nonmonotonic reasoning both interesting and accessible to a wider audience than artificial intelligence theoreticians. This accessibility and advertisement encouraged the involvement of many brilliant thinkers in the problems of artificial intelligence, and produced a large and vigorous literature that has significantly increased our understanding of nonmonotonic reasoning. It seems doubtful we would understand as much today had these formalizations not been developed and explored as they have.

At the same time, the logical formalizations proved very bad as conceptual characterizations of nonmonotonic reasoning because the fundamental concepts of nonmonotonic reasoning have little to do with the concepts of logic, which in these formalizations obscure and mislead one from attending to the concepts of interest. Understand that this does not mean the logical formalizations have no value, even as conceptual characterizations, for a bad formalization may serve well enough. But the logical formalisms deserve reconsideration because they highlight and enshrine at their core things essentially unrelated to nonmonotonic reasoning. We enumerate only three of the most important inappropriate aspects of the logical formalizations.

In the first place, the logical formalizations convert what in many systems is a fast and computationally trivial check for presence and absence of attitudes into a computationally difficult or impossible check for provability, unprovability, consistency or inconsistency. This inaptness seems especially galling in light of the initial problem-solving motivations for nonmonotonic assumptions, for which assumptions served to speed inference, not to slow it (cf. (de Kleer, Doyle, Steele, & Sussman, 1977; Ginsberg, 1991)).

In the second place, the logical formalizations impede development of realistic approaches to reasoning about inconsistent information. Standard logics make inconsistent theories trivial, and the use of logical provability or consistency to encode inferential permissions and guidance means that nonmonotonic theories must be consistent as well in order to be useful. But in practice, reasoners must deal with inconsistent information all the time. They may try to remove some inconsistencies when they deem the inconsistencies important enough to warrant the effort, but even so may take time to remove them, occasionally even a long time, and must keep operating reasonably throughout this process. A theory of reasoning basing the very definition of mental state on logical consistency requirements makes representation of such processes impossible.

In the third place, the logical formalizations encourage the view that nonmonotonic rules and defaults express beliefs or factual information, even though reasoning, and nonmonotonic reasoning in particular, may involve desires, intentions, and other mental attitudes besides belief (cf. (de Kleer et al., 1977; Doyle, 1980; McCarthy & Hayes, 1969; McDermott, 1978)). Now no one disputes that some nonmonotonic rules carry or presume some beliefs, but taking this special case as the general one has proven very misleading. For example, some theories attempting to provide guidance about choosing from among the possible interpretations of complex sets of nonmonotonic rules interpret these rules as qualitative statements about highly likely conditions. While high conditional probabilities of the conclusions may motivate adoption of some defaults and thus deserve attention as a special case, this interpretation does not even make sense for rules reasoning with other mental attitudes, and might indicate the wrong conclusions for all we know now. But such theories have been proposed as theories of nonmonotonic reasoning in general, not as theories of special cases. Nonmonotonic theories based on logical consistency provide another example with the same character. These theories convert reasoning about reasoning generally into reasoning about the consistency of beliefs. Now while one may motivate a number of reasonable principles for guiding reasoning about beliefs in terms of avoiding inconsistency, these principles simply do not apply to reasoning about desires and some other attitudes. The conclusions thus motivated hardly seem appropriate for general use without much further argument.

It is tempting to point the finger of blame for these mistakes elsewhere, even back to McCarthy and Hayes’ (1969) original brief suggestion, but I bear much responsibility for these misleading formalizations due the initial nonmonotonic logic I developed with Drew McDermott in 1978 (McDermott & Doyle, 1980). I well understood the distinction between the underlying RMS ideas and the logical encoding, and was quite pleased when Reiter’s (1980) default logic later remedied a number of the unsatisfying characteristics of our original nonmonotonic logic through an approach closer to the RMS. Nevertheless, I was for years as encouraged as anyone in thinking that some logic would eventually provide the right formulation for these ideas—at least until I undertook in 1981 to develop logics capturing the RMS approach even more precisely. I soon found a great variety of possible schemes of reasoning, which suggested that the fundamental ideas were best isolated and pursued independently rather than attempting to formulate each variant as a special quirky logic. Mathematical classification seemed more appropriate than philosophical or metaphysical proposal, especially as many of the dozens (if not hundreds) of the schemes imaginable seemed well suited to some special purpose, rather than some logic dominating the rest.

1.3 Rational psychology

Eventually it became clear that in spite of the great progress made through exploiting logical tools and theories in artificial intelligence, one cannot expect a priori that the most appropriate theory of psychology should have much to do with logic or should necessarily make extensive use of logical concepts. Psychology, as a subject for investigation, includes the study of many aspects of thought, feeling, and behavior, while standard logic mainly idealizes only part of one sort of mental activity, reasoning about facts or beliefs, and clearly does not address notions like intent, desire, and preference, nor even the relations between such attitudes and reasoning in terms of beliefs (to say nothing about its silence on love, fear, and other feelings). This is not to say one cannot cast parts of these larger theories in logical terms too; this enterprise goes back to Aristotle, and has been investigated diligently in modern philosophical logic to good effect. But even here, one finds no reason a priori to suppose that ordinary logic provides the most appropriate basis for these investigations. The beautiful theories of modern mathematical logic constitute a triumph of conceptual analysis; but while logic is great, it isn’t psychology, and to use G. A. Miller’s (1986) vivid metaphor, instead of carving up the subject of psychology at its joints and clearly revealing the structure of psychology’s conceptual components, standard uses of logic may in fact dismember psychology, carving it up into ill-shapen lumps that reveal little of the attraction of the subject.

The rational mechanics of Newton and its modern renewal by Truesdell (1958, 1977) and his contemporaries provide a model for a more productive approach. Rational mechanics is a part of mathematics, the conceptual investigation of mechanics. “Rational” here indicates investigations based on reason alone, rather than on experiment, engineering, or computation, the rational analysis of the concepts and theories whose applicability and feasibility are studied in experimental, engineering, and computational projects. We call the corresponding part of mathematics devoted to the study of psychology rational psychology (Doyle, 1983d) (a term used by James (1892) and earlier writers to refer to philosophical psychology). Rational psychology is not the study of rational agents, but instead the mathematical approach to the problems of agents and their actions, whether one thinks these agents and actions rational or irrational. It aims to understand psychological ideas through mathematical classification of all possible minds or psychological systems, to describe and study mental organizations and phenomena by the most fit mathematical concepts, seeking the best (most appropriate, illuminating, edifying, powerful, …) ways of formalizing psychology. It excludes the problem of identifying important psychological phenomena except as a byproduct of organizing ideas about psychologies into a coherent mathematical whole.

The mathematical formulation of nonmonotonic reasoning presented below resulted from this shift in focus from logic to conceptual analysis, with many of the central concepts and results of the new formulation first circulated in my monograph (Doyle, 1983c), a dense exposition short on explanation that revealed the mathematical structure of the subject but doubtless exceeded the tolerance of most potential readers. That monograph introduced the notion of simple reason, which resembles a RMS justification or a propositional default in the logic of defaults, but which appears as a conclusion as well as as a rule, and which so also resembles one of Minsky’s “K-lines” (Minsky, 1980). Simple reasons formed the focus of the original exposition, which deliberately presented the core of the development twice—once for simple reasons alone (no mention of any logical structure), and then again for states closed with respect to a compact abstract deducibility relation—to drive home the irrelevance of even minimal logical notions to the central mathematical structures of reasoned assumptions. That presentation also deviated from logic in embracing a wide conception of semantics and meaning as the theory of pure designation, without requiring the compositionality of meanings usually demanded by logical theories. It also hewed close to the RMS conception in making no assumptions that reasoned entities represented beliefs, or that presence or absence amounted to consistency or inconsistency, or that contrary beliefs should not be held indefinitely, or that any mental entities were inherently contradictory with any others. At the same time, it followed logic in aiming to describe reasoning agents regardless of computability, in seeking to describe the mind of God as well as the mind of Man. The present exposition also draws on my later monograph (Doyle, 1988), which provided better development of the motivation, better forms for some of the concepts, and better notation.

This paper omits treatment of many important topics addressed in (Doyle, 1983c) and (Doyle, 1988), in their numerous sequelae, and to some extent in (Doyle, 1980). We have omitted most discussion of the motivations for nonmonotonic reasoning in particular and the basic structures of mental architectures in general; of the nature of meaning and the structure of semantical theories; of “psycho-logics” derived from the state spaces of agents; of uniformly defeasible reasons; of the theory of denials and contradictions; of logical encodings of reasoning; of psychological attitudes; of conservatism and other topics concerning the evolution of mental states; of probabilistic constructions over trajectories and their relation to reasoning and the strength of mental attitudes; of the failings of practical systems like the RMS; of social, economic, and political structures within minds; of most connections with ideas from economics; and of reflection, deliberation, and action. The mathematical formulations of these topics presented in the earlier works sometimes need emendation, but generally fit well into the framework elaborated here.

This paper seeks to present the fundamental concepts and results about nonmonotonic reasoning in a setting free of unnecessary logical ornament. Section 2 introduces the notion of framings as different ways of viewing mental states, while Section 3 presents the underlying tools for describing the constitution or special structure of mental states, including the notion of satisfaction system used to express half of the RMS stability principle. Section 4 introduces simple reasons in semantic terms, as elements of mental states bearing certain constitutive meanings rather than as exhibiting specific structures, and develops canonical descriptions for them. Section 5 introduces constitutions for reasoning that express the other half of the RMS stability principle as well as the RMS groundedness principle, while Section 6 analyzes some of the structure of reasoned states.

2. Framings

We focus in this paper on aspects of mental states that shape or guide the course of reasoning. We do not presume to possess a full characterization of instantaneous mental states, nor do we make special assumptions about the nature of mental states. We instead cast the discussion instead in terms of representations of instantaneous states (mental or otherwise) that distinguish the structures of interest and focus on properties of structures with such representations. In doing so, we take care to differentiate between the activities of the reasoner and our descriptions of such actions, and to identify structures of reasoning in terms of their role in the reasoner’s activities rather than in terms of how we represent them. That is, how we choose to talk about the reasoner and its reasoning should not affect what these things actually are.

We write S to denote the set of all possible instantaneous states of the agent or agents in question: in particular, the set of states reflecting all and only those distinctions relevant to the reasoning activities of interest. Ordinarily we know more ways of distinguishing states, and conceive of a larger set Ω of all possible instantaneous states, so that each state in S covers one or more states in Ω. In practice, we have no direct access to or complete knowledge of S (or Ω), and must instead work with various representations of S chosen to reflect the essential characteristics of S in a way amenable to reasoning and analysis. We call such faithful representations framings.

Definition 1 (Framings) A framing of S is a one-to-one function ϕ : S → S′ taking states in S to representations in a set S′. We call ϕ exact just in case it is onto as well.

A framing thus provides a unique representation of each state, directly representing the chosen space of states without blurring distinctions or introducing new ones. It ensures that S captures only distinctions of interest since states in Ω differing only in irrelevant ways map to the same representation, and hence must be identified in S. An exact framing, moreover, indicates an isomorphism S ≅ S′, so that every difference among representations indicates a difference among states.

Two common types of framings provide the basic tools of our discussion: multiattribute and elemental framings. Multiattribute framings describe complex worlds in terms of several attributes at once, mapping each state s to a vector ϕ(s) = (ϕ_{1}(s), ϕ_{2}(s), …) of attribute values, where the component attribution functions ϕ_{i} : S → A_{i} map S to component attribute spaces A_{i}. For example, common framings of physiological states assign vectors of height, weight, blood pressure, heart rate, etc. to each person. Elemental framings, on the other hand, describe states as consisting of sets of state components. An elemental framing of S over a set of components D is then a function ϕ : S → P(D), representing each state s by a set ϕ(s) ⊆ D. For example, we often frame mental states in terms of a set of beliefs, desires, intentions, and other attitudes. Elemental framings may of course be viewed as particular multiattribute framings, with each state component corresponding to a distinct boolean attribute taking on the two values “present” and “absent”. Conversely, we may view any strictly boolean multiattribute framing as an elemental framing. But conceptually and notationally the set-theoretic view seems more apt in many cases.

Elemental framings are especially natural in artificial intelligence, which often constructs agents with mental states consisting of sets of representations (symbolic or otherwise), for example, sets of statements in a logical language, sets of data-structures, or sets of active “mental agents” in a society of mind (Minsky, 1980). In such cases, we may choose trivial elemental framings that simply consist of the representations explicitly contained in the state; that is, in such cases, elemental framings need not simply provide ways of viewing states, but may actually provide the states themselves.

3. Constitutions

As a practical matter, one ordinarily chooses attributes or state components on the basis of considerations independent of the details of the full state space, indeed, independent of the specific agent in question; one usually chooses these descriptors to facilitate characterization of agents in some general class. Consequently, convenient and useful multiattribute and elemental framings rarely prove exact, that is, not every set of state components represents a possible state of the agent. This inexactness poses problems, both for external analysts and for deliberative agents reasoning about their own states and actions, since reasoning that considers every attribute vector or set of state components a possible state will err in some cases. To avoid these errors, we need to distinguish those representations that actually correspond to states from those that do not.

One way to distinguish representations of actual states from imposters is to describe a constitution over the set of possible representations, a set of “laws” or restrictions on the constitutionally admissible combinations of attribute values or state components. For example, a constitution for an ideal psychological agent framed in terms of standard mental attitudes might restrict framings to those in which the set of beliefs is always deductively closed. We add these restrictions until only representations of actual states remain, until the framing between states and the constitutionally admissible representations is exact. While one may construct constitutions for mental states as a way of specifying the design of some agent, we here do not seek to prescribe some psychology, only to identify, understand, and classify special psychologies, with particular attention to the ones we find most interesting. These special mental constitutions thus correspond directly to the constitutive assumptions used in rational mechanics to identify special classes of physical materials (cf. (Truesdell, 1977)).

3.1 Bounding systems

At their most abstract, constitutions simply set out the image ϕ(S) of the framing under consideration. The map ϕ indicates an isomorphism of S with ϕ(S), so the constitution ϕ(S) permits one to ignore S itself and simply work with the representations in ϕ(S). Constitutive assumptions or systemic laws with respect to elemental framings then correspond to upper bounds on the image ϕ(S), which we formalize in the notion of bounding system.

Definition 2 (Bounding systems) A bounding system B on a set D consists of D together with a set B ⊆ P(D). If S ∈ B, we say S is bounded (with respect to B).

Thus using bounding systems B, B′, … over D to express constitutive assumptions means we require any admissible framing ϕ : S → P(D) to satisfy ϕ(S) ⊆ B_{B}∩B_{B′} ∩. . .. Naturally, we may collapse several bounding systems over a set to a single bounding system by taking the intersection of the several bounding sets as the combined bounding set.

We move beyond this abstract notion in three ways, each of which introduces new notions with which to describe bounding systems or constitutive assumptions with respect to elemental framings. The first way of expressing constitutional restrictions views state components as bearing an internal “logic”, with the constitutionally admissible states satisfying closure and consistency conditions with respect to this logic of state components. We formalize this method for expressing constitutional restrictions using the notion of information systems (Scott, 1982), which builds on Tarski’s theory of closure operators to abstract the structure of logical theories. The second way views at least some state components as having regulatory force, that is, as principles adopted by the agent for guiding its own reasoning, with the constitutionally admissible states satisfying the principles expressed by all the regulatory state components they contain. We formalize this in the notion of satisfaction system (Doyle, 1988), a clarified version of the original notion of “admissible state semantics” (Doyle, 1983c) developed to abstract traditional conceptions of deliberation and self-control. Finally, the third way of expressing constitutional restrictions views at least some state components as having motivational import, that is, as expressing the preferences, desires, or motivations of the agent in its reasoning to complement the intentional or regulatory import of satisfaction systems and logical import of information systems. We formalize this in the notion of preference systems, which bear some similarity to assignments of preferences to agents in political economy.

Though we employ abstract logics in describing the constitutions of agents, this serves to show the compatibility of logical notions with the theory of nonmonotonic reasoning rather than any necessity of logical notions for the theory. Indeed, the concepts of nonmonotonic reasoning make sense even for trivial abstract logics (nothing inconsistent and nothing new entailed), relying in essential ways on satisfaction and preference systems as the sources of theoretical structure.

3.2 Information systems

Many formal treatments of artificial intelligence systems employ logics to describe the beliefs of the agent by translating or rerepresenting the components of the agent’s states as sentences or formulas in a logical language when the states are not already constructed as sets of logical formulae. This step of translation introduces the extra complication of a second language and the chore of translation, and, since most logics yield infinite sets of conclusions from finite sets of axioms, may prove hard to invert, making it difficult to determine the composition of the agent’s state from axioms about it. We may avoid these unnecessary complications by seeking instead logics of states that capture their structure directly, that is, logics which characterize the important aspects of the structure of states that remain invariant under any rerepresentation in terms of different languages. Such logics, called information systems following Scott (1982), have already been developed for use in the theory of computational domains and data types.

Definition 3 (Information systems) An information system I over a set D consists of D together with a set C ⊆ P_{f} (D) of finite subsets of D (the “consistent” finite subsets), and a relation ⊢ on C × D (the “entailment” relation), such that for each x, y ∈ D and X, Y ⊆ D, C and ⊢ satisfy (writing X ⊢ y to mean (X, y) is in ⊢)

1. If X ⊆ Y ∈ C, then X ∈ C,

2. If y ∈ D, then {y} ∈ C,

3. If X ⊢ y, then X ∪ {y} ∈ C,

4. If x ∈ X, then X ⊢ x, and

5. If Y ⊢ x for all x ∈ X, and X ⊢ y, then Y ⊢ y.

We say that a set X ⊆ D is consistent iff each finite subset Y ⊆ X is consistent according to C; (deductively) closed iff x ∈ X whenever Y ⊆ X and Y ⊢ x; and an element of the information system iff both closed and consistent. We write E(I) to denote the set of elements of I. If ∅ ⊢ x, we say x is a tautology in I.

As we apply them here, each information system captures a logic of state components that we use to express closure and consistency constraints on state representations. Information systems view each element of D as a “proposition” about states, and each set of elements as a partial description of some state, with bigger sets representing better descriptions. The conditions on consistency and entailment state that subsets of consistent sets are consistent; that each element is itself consistent; that addition of entailed elements preserves consistency; that consistent sets entail their own members; and that entailment is transitive. This is clearer if we extend the notation of entailment in the natural way to say that X ⊢ Y iff X ⊢ y for each y ∈ Y, in which case the last condition can be rewritten as X ⊢ Z whenever X ⊢ Y and Y ⊢ Z. Clearly D is closed, as are intersections of closed sets. Each information system thus determines a bounding system, namely (D, E(I)), and we use such bounding systems below to require that admissible constitutional states correspond to “theories” (deductively closed and consistent sets) with respect to the constitutive information system.

Each information system gives rise to a closure operator Θ similar to the usual deductive closure operator Th of ordinary logic.

Definition 4 (Closures) We define Θ(X), the closure of X, by

Θ(X) =^{def} {x ∈ D | ∃Y ∈ C Y ⊆ X ∧ Y ⊢ x},

and broaden the notation X ⊢ x to mean x ∈ Θ(X).

The closure of a set is thus its the least closed superset. Domain theory usually restricts attention to closures of consistent sets, but we find it useful to employ the unrestricted notion as well. The operator Θ exhibits properties similar to those of Th, and one easily checks that Θ is monotonic (Θ(A) ⊆ Θ(B) whenever A ⊆ B ⊆ D), idempotent (Θ(Θ(A)) = Θ(A)), and identifies the closed sets as its fixed points (A is closed iff A = Θ(A)).

Many notions of entailment and consistency fit within the framework of information systems. The ordinary logical notions of consistency and entailment clearly satisfy these axioms. To model agents with no ability to reject inconsistencies, we may take the minimal notion of consistency which considers all finite sets, and hence all sets, as consistent. Similarly, to model agents with no (automatic) inferential powers, we may take entailment to be simple containment (X ⊢ y iff y ∈ X), a minimal notion that considers all sets deductively closed. When both C and ⊢ are minimal, every set is closed and consistent, that is, E(I) = P(D). Alternatively, if some elements x have explicit contraries that we denote ¬x, one may choose C to capture only lack of overt inconsistency, so that X ∈ C iff X is finite and there is no x ∈ X such that ¬x ∈ X as well. Similarly, presuming some notion of logical structure of elements one may choose ⊢ to capture only propositional deduction, or only Modus Ponens (X ⊢ y iff either y ∈ X or there is some x ∈ D such that x ∈ X and x → y ∈ X), or only ground instantiation (X ⊢ y iff either y ∈ X or y is a ground instance of some y′ ∈ X), or entailment in modal, relevance, or probabilistic logics, or logics of partial data structures, for which deductive closure amounts to filling in missing but implied “fields” to complete the data structure. In addition, one may always choose ⊢ so that some set of attitudes is present in every state as an unchangeable background to the agent’s reasoning. These tautologies need not just be real logical tautologies, but instead may be substantial attitudes or “axioms”.

Efficient mechanizability of a constitution (in the physical sense as well as the computational sense) often depends on the “locality” of the conditions imposed on states by constitutions, since local conditions involving a small or bounded set of state components often can be checked by a simple circuit or computational procedure with bounded effort, while global conditions on states may require unbounded effort to verify. We therefore usually seek to find constitutions that express conditions as locally as possible. We will not develop a precise theory of local and global properties or their relation to mechanizability in this paper (see, for example, (Abelson, 1978) for one such theory). We do, however, make use of the related notion of compactness already familiar in logic and topology.

Definition 5 (Compact information systems) We call an information system compact just in case whenever A ⊢ {e} in it, there exists a finite C ⊆ A such that C ⊢ {e}.

Not all information systems are compact since logics correspond to information systems and some logics, such as dynamic logic, are not compact. Clearly, though, any information system with a trivial entailment relation (X ⊢ x iff x ∈ X) is compact.

3.3 Satisfaction systems

Standard constitutions for physical systems consist of the physical laws of nature, and we ordinarily view these laws as quite separate from the entities they relate. In psychological systems, however, it seems natural to employ laws of a somewhat different character, laws represented by state components themselves. That is, we interpret some state components as restrictions on possible states, as indicating bounds on the composition of the states in which the components occur, so that the states themselves set out part of their own constitution. This same point of view applies to physical systems as well, but it seems most natural for the intentional systems of psychology, especially in formulating constitutions for deliberating agents that restrict or guide their future behavior by adoption of plans or intentions regarding that behavior. Both senses fit (retrospectively, at least) within Boole’s notion of “laws of thought”, with state-inspecific restrictions capturing fixed legal constitutions of the agent, and state-specific restrictions capturing variable laws and amendments to the fixed constitution. To formalize interpretations of some mental components as bearing constitutive meaning, we employ the notion of satisfaction system.

Definition 6 (Satisfaction systems) A satisfaction system S over D consists of D together with a meaning function [[ ]] : D → P(P(D)) that we extend to a function over subsets of D by [[∅]] = P(D) and [[X]] = ⋂_{x∈X}[[x]] for each nonempty X ⊆ D. We say that a set X ⊆ D is satisfying or component-admissible iff X ∈ [[x]] for each x ∈ X, and write Q(S) for the set of all satisfying sets.

Intuitively, the meaning [[x]] of an element x is the set of possible states that satisfy the constitutive intent, if any, of the element. If x has no constitutive import and places no restrictions on possible states containing it, we may take [[x]] = P(D). Satisfying sets are then just sets that satisfy the constitutive import of each of the elements they contain, that is, sets X ⊆ D such that X ∈ [[X]]. Note that the definition permits unsatisfiable elements (elements x such that [[x]] = ∅) which may not appear in any satisfying state. Each satisfaction system S over D thus determines a bounding system, namely (D, Q(S)).

The theory of nonmonotonic reasons elaborated below provides an important example of self-specification, interpreting a reason A \\ B ∥− C as requiring satisfying states to contain each element of C if they contain each element of A and contain no element of B.

In practice, most interesting satisfaction systems concern only local conditions on finite portions of states, even when the states themselves may be infinite, much as many traditional logical consistency and closure conditions exhibit compactness properties. We define an analogous notion of compactness for satisfaction systems as follows.

Definition 7 (Compact satisfaction systems) If G ⊆ D, we write π_{G} : P(D) → P(G) to denote both the natural projection function of subsets of D onto subsets of G and its lifting to sets of subsets. We say that [[d]] has basis G ⊆ D just in case S ∈ [[d]] iff π_{G}(S) ∈ π_{G}([[d]]) for every S ⊆ D, and that [[ ]] has basis G iff [[d]] has basis G for each d ∈ D. We then say that a satisfaction system is compact iff for each d ∈ D, whenever [[d]] has basis G there exists a finite G′ ⊆ G such that [[d]] has basis G′.

Clearly, every meaning has basis D, so every component meaning of a compact satisfaction systems has a finite basis. Not all interesting meanings have finite basis; in particular, the meaning P(D)\{∅} expressing only nonemptiness of states does not have finite basis if D is infinite. However, the trivial meaning P(D) has finite (indeed, empty) basis, so the trivial satisfaction system assigning this meaning to each element is compact.

3.4 Preference systems

In addition to interpreting some elements of mental states as expressing intentional information about the agent’s commitments (or its designer’s), psychological theories also commonly interpret some elements as expressing evaluative information conveying the agent’s (or designer’s) desires and preferences (relative desires). We treat some of this information through the notion of preference system, which formalizes the interpretation of state components as expressing preference information.

Preference systems build on a notion of preference related to the notion standard in economics and decision theory.

Definition 8 (Preferences) A partial preference preorder ∼ ≻ over a set X is a reflexive (x ∼ ≻ x) and transitive ( x ∼ ≻ z whenever x ∼ ≻ y and y ∼ ≻ z) binary relation on X. If x ∼ ≻ y, we say that x is weakly preferred to y. If x and y are weakly preferred to each other, we write x ∼ y and say that x and y are indifferent. If x is weakly preferred to y but y is not weakly preferred to x, we write x ≻ y and say that x is strictly preferred to y. If none of these cases hold, we say that x and y are preferentially unrelated.

Clearly, indifference is an equivalence relation, and partitions the base set into a set of indifference classes. The identity relation is the smallest preference preorder on a set. It leaves all distinct elements preferentially unrelated, and hence has the largest number of indifference classes of elements (one for each element). The complete relation is the largest preference preorder. It makes all elements indifferent, and has the smallest number of indifference classes (just one).

Definition 9 (Preference system) A preference system P over D consists of D together with a mapping ∼ ≻ taking each d ∈ D to a partial preference preorder ∼ ≻_{d} =^{def} ∼ ≻(d) over P(D).

We take constitutional preferences to have a quite different character than the constitutive intentions of satisfaction systems. Satisfaction systems capture the notion of aiming to satisfy all one’s intentions at once, and define satisfying states as those states satisfying all of the intentions they contain. That is, satisfying states must express consistent sets of intentions. In contrast, we view the preferences expressed via preference systems as forms of desires, which need not be all consistent or satisfied, even in rational agents. In consequence, one cannot reasonably require that constitutionally admissible states satisfy (in some sense) all the preferences they express, and must settle for states that are optimal in the sense of satisfying as many preferences as possible.

Definition 10 (Optimal sets) If S ⊆ D and R ⊆ P(D), we say that S is (Pareto) optimal in the range R with respect to a preference system ∼ ≻ over D just in case whenever we have S′ ≻_{d} S for some S′ ∈ R and d ∈ S′, we also have S ≻_{e} S′ for some e ∈ S.

That is, S is optimal in R if every preference for some set in R expressed by the other set can be countered by a preference for S expressed by S. Clearly, if R′ ⊆ R and S is optimal in R, then S is also optimal in R′. Thus if S is optimal in P(D), it is optimal in every range.

We do not identify any standard constitutional restriction based on optimality due to the variability of range within one judges optimality, and instead consider optimality with respect to specific classes of preferences and specific ranges. We hope further investigation either identifies natural choices of range for constitutional restrictions, or explains why such choices do not exist.

3.5 Basic constitutions

Our basic notion of constitution combines bounds expressed by satisfaction and information systems with general bounds.

Definition 11 (Basic constitution) A basic constitution Σ over D consists of an information system I = (D, ⊢, C), satisfaction system S = (D, [[ ]]), and bounding system B = (D, B) over D, with the admissible states A(Σ) of the constitution being the states jointly characterized by E(I), Q(S), and B(B), that is, the sets S ⊆ D such that P_{f} (S) ⊆ C, S = Θ(S), S ∈ [[S]], and S ∈ B.

The notion of basic constitution recasts the notion of admissible state semantics of (Doyle, 1983a, 1983c) in simpler terms. The treatment in (Doyle, 1983c) assigned constitutive intentional meaning to elements and judged states satisfying or not just as in the present treatment, and also provided what we now call a bounding system through an arbitrary restriction set R ⊆ P(D). The main difference in formulation concerned the background logic, which was not distinguished explicitly in an information system. The specific theories developed in (Doyle, 1983c) instead defined restriction sets consisting of the sets closed with respect to a compact closure operator, ignoring any notion of consistency not expressed by the satisfaction system meanings.

In many cases, we do not need the full generality of basic constitutions, and characterize states in terms of only one or two of the information, satisfaction, or bounding systems of a basic constitution. We give names to these special constitutions as follows, summarizing the nomenclature in Table 1.

Definition 12 (Special constitutions) We call a basic constitution over D logical just in case its information system characterizes its admissible states; satisfying just in case its satisfaction system characterizes its admissible states; logically satisfying just in case its information and satisfaction systems jointly characterize its admissible states; unstructured just in case its bounding system characterizes its admissible states, and trivial just in case all subsets of D are admissible states. We call a state space S logical, satisfying, logically satisfying, or trivial with respect to an elemental framing ϕ over D if ϕ(S) can be characterized by a logical, satisfying, logically satisfying, or trivial constitution over D.

Satisfying constitutions, in which the states themselves explicitly express all restrictions on states, have a certain philosophical attraction, and recall efforts in artificial intelligence towards constructing completely “self-descriptive” machines (e.g., (de Kleer et al., 1977; Doyle, 1980; McDermott, 1978; Minsky, 1965)).

Although the different parts of basic constitutions sometimes permit one to shift restrictions from one subsystem to another, different subtypes of constitutions have different expressive powers. We begin by characterizing the simplest constitutions, the trivial ones.

if A(Σ) is  then Σ is
E(I(Σ))  logical
Q(S(Σ))  satisfying
E(I(Σ)) ∩ Q(S(Σ))  logically satisfying
B(B(Σ))  unstructured
P(D)  trivial

Table 1: Special constitutions

Theorem 13 (Trivial constitutions) A basic constitution Σ is trivial iff

1. B(Σ) = P(D),

2. C = P_{f} (D) and ⊢ is ∋ (i.e., ∈^{−1}), and

3. {X ⊆ D | d ∈ X} ⊆ [[d]] for every d ∈ D.

Proof: Suppose Σ is a basic constitution over D.

(If) Suppose conditions (1)–(3) hold. The first part of condition (2) implies that all sets are consistent, while the second part implies that all sets are closed, hence E(I(Σ)) = P(D). Furthermore, condition (3) implies that x ∈ [[d]] for each d ∈ X ⊆ D, so every X ⊆ D is satisfying, hence Q(S(Σ)) = P(D). Thus A(Σ) = P(D).

(Only if) Suppose A(Σ) = P(D). Since A(Σ) = B(Σ) ∩ E(I(Σ)) ∩ Q(S(Σ)), we clearly have B(Σ) = P(D), which is condition (1), as well as E(I(Σ)) = Q(S(Σ)) = P(D). Since every set is consistent, so is every finite subset of D, so we have C = P_{f} (D). Next, if we have X ⊆ D and X ⊢ e for some e ∉ X, then X is not closed, hence X ∉ E(I(Σ)). Since every X is closed, this means ⊢ is ∋. Finally, if d ∈ X ∉ [[d]], then X is not satisfying, hence Q(S(Σ)) ≠ P(D). But every X is satisfying, so X ∈ [[d]] whenever d ∈ X, hence {X ⊆ D | d ∈ X} ⊆ [[d]]. □

We may characterize the expressive power of satisfying constitutions quite easily.

Theorem 14 (Satisfying constitutions) A state space S is satisfying with respect to an elemental framing ϕ over D iff ∅ ∈ ϕ(S).

Proof: Let ϕ be an elemental framing of S over D. If ∅ ∈ ϕ(S), define [[ ]] over D so that [[d]] = ϕ(S) for every d ∈ D. Then nonempty subsets of D are satisfying iff they are in ϕ(S), and ∅ is both satisfying and in ϕ(S), hence ϕ(S) is exactly the set of satisfying states, so S is satisfying with respect to ϕ. Conversely, if S is satisfying with respect to ϕ, then ∅ ∈ ϕ(S) since ∅ is always satisfying. □

Thus satisfaction systems alone cannot characterize all interesting elemental framings, since they cannot express bounding systems that require nonemptiness of state representations. More generally, even if ∅ ∉ ϕ(S), the meaning function constructed in the proof of Theorem 14 yields ϕ(S) ∪ {∅} as the set of satisfying sets (though this encoding makes all restrictions global and may convert meanings of finite basis into meanings of infinite basis since ϕ(S) also need not have finite basis). In consequence, any state space may be characterized by a satisfaction system together with the bounding system consisting of all nonempty sets of state components, that is (D, P(D) \ {∅}). Unfortunately, one cannot always achieve the same effect using logical restrictions instead of general bounds.

Theorem 15 (Nonemptiness) If ϕ(S) = P(D) \ {∅} and D has at least two elements, then ϕ(S) is not logically satisfying.

Proof: Suppose ϕ(S) is jointly characterized by a satisfaction and information system, D has at least two elements, and ∅ ∉ ϕ(S). Since ∅ is always satisfying, we must have ∅ ≠ Θ(∅). Now the set of tautologies Θ(∅) either contains at least two state components or does not. If it contains at least two, then no set {d} consisting of only one tautology is closed, hence ϕ(S) ≠ P(D) \ {∅}. On the other hand, if there is just one tautology {d}, then no {d′} is not closed when d ≠ d′, so again ϕ(S) ≠ P(D) \ {∅}. □

Thus basic constitutions for some state spaces must have nontrivial bounding systems expressing at least the condition of nonemptiness, that is, (D, P(D) \ {∅}).

We have no complete characterization of how logical and satisfying constitutions differ in expressive power. One observes immediately that some logical state spaces are not satisfying, since the empty set is always satisfying, but if a state space is characterized by an information system containing tautologies, then ∅ ∉ ϕ(S). Conversely, some satisfying state spaces are not logical, since a satisfaction system may assign [[d]] = ∅, in which case no state contains d, even though we must have {d} ∈ C by the axioms for information systems. We also observe without proof that if [[d]] ≠ ∅ for every d ∈ D, then one can construct an information system from [[ ]] by defining C to contain those finite sets X ⊆ D such that [[X]] ≠ ∅, and by defining X ⊢ x to hold just in case [[X]] ⊆ [[x]]. Unfortunately, the elements of this constructed information system have no particular relation to the satisfying sets of the original satisfaction system. While satisfying states must be consistent in the constructed information system, they need not be closed, and conversely, consistent closed sets need not be satisfying.

3.6 Preferential constitutions

We obtain a larger conception of constitution by augmenting basic constitutions with preference systems to obtain preferential constitutions.

Definition 16 (Preferential constitutions) A preferential basic constitution combines a basic constitution Σ over D with a preference system ∼ ≻ over D.

Unlike the way in which the information, satisfaction, and bounding systems of basic constitutions restrict the states admissible with respect to the constitution, we do not require that the preference system of a preferential basic constitution yields any restrictions on admissible states, though specific preferential basic constitutions may in fact restrict admissible states to those satisfying certain preferential conditions. The most natural candidates for such preferential restrictions are optimality with respect to specific classes of preferences and ranges. Accordingly, we define optimality of constitutions with respect to specific classes of preferences by considering whether all admissible states are optimal among admissible states.

Definition 17 (Constitutional optimality) A basic constitution Σ over D is optimal with respect to a preference system ∼ ≻ over D just in case each S ∈ A(Σ) is optimal in A(Σ) with respect to ∼ ≻.

Clearly, one can always find constitutions optimal with respect to any preference system, since if ∼ ≻ is a preference system over D, the unstructured basic constitution Σ over D such that B(Σ) = {S} for some S ⊆ D is trivially optimal.

Preference systems preferring satisfying states to unsatisfying states provide natural connections between satisfying constitutions and optimal constitutions.

Definition 18 (Satisfaction preferences) The pure satisfaction preference system corresponding to a satisfaction system (D, [[ ]]) is the preference system (D, ∼ ≻) such that for each d ∈ D and S, S′ ⊆ D, we have S ≻_{d} S′ just in case S ∈ [[d]] and S′ ∉ [[d]], and S ∼_{d} S′ just in case S ∈ [[d]] iff S′ ∈ [[d]]. The weak present satisfaction preference system defines S ≻_{d} S′ just in case d ∈ S ∈ [[d]] but not d ∈ S′ ∈ [[d]] (that is, either d ∉ S′ or S′ ∉ [[d]]), while the strong present satisfaction preference system defines S ≻_{d} S′ just in case d ∈ S ∈ [[d]] but d ∈ S′ ∉ [[d]]. We call sets optimal in some range with respect to the (weak, strong present) satisfaction preference system (weakly, strongly present) satisfaction optimal in the range.

We then have the following result.

Theorem 19 (Satisfaction optimality) Every satisfying constitution is optimal with respect to the corresponding strong present satisfaction preference system.

Proof: Let Σ be a satisfying constitution over D, and let ∼ ≻ be the strong present satisfaction preference system over D corresponding to the satisfaction system of Σ. Strong present satisfaction optimality of S means that whenever d ∈ S′ ∈ [[d]] and d ∈ S ∉ [[d]] for S′ ∈ Q(Σ), then for some e ∈ S ∈ [[e]] we have e ∈ S′ ∉ [[e]]. But since S is satisfying, d ∈ S ∉ [[d]] never obtains, so S is trivially optimal among Q(Σ). □

Thus every satisfying state is strongly present satisfaction optimal among satisfying states. The converse, however, does not hold in general. For example, if D = {d} and [[d]] = {∅}, then ∅ is the only satisfying state, and D is trivially strongly present satisfaction optimal in {∅} since there is no x ∈ ∅ ∈ [[x]].

4. Reasons

We may use the notions of satisfaction and preference systems to identify the entities we call reasons, which cover all or part of familiar notions of monotonic and nonmonotonic justifications of reason maintenance systems, default rules of default logic, and modal default rules of nonmonotonic logics, as well as some notions of taxonomic inference and virtual context mechanisms. We identify reasons by their constitutive import, in terms of the role they play in the agent’s constitution, rather than in terms of mere overt structural or syntactic appearances, which vary far too much to accommodate other concerns to serve as useful guides to understanding. That is, reasons need not reflect any overt structures in the unframed states themselves. They instead form part of the metalanguage in which we discuss agent states. The agent’s “language of thought”, if any, need not express reasons in the same way, and we may thus find reasons in neural networks, business organizations, or even literary works, as well as in traditional sentential or computational systems representing them as straightforward data-structures that directly suggest their characteristic interpretation.

We will not develop the theory of reasons here in its full generality. Instead we focus attention on simple reasons, which we denote by expressions of the form A \\ B ∥− C, read “A without B gives C”, meaning roughly that if the “antecedent” items in A are present in a state but the “qualification” items in B are not, then the “conclusion” items in C should be present as well. One can extend much of the development below to cover more general reasons that also specify a set of conditionally “denied” items D, notated A \\ B ∥− C \\ D, but we generally avoid that additional complexity here.

4.1 Ranges and range conditionals

Our analytical language expresses reasons in terms of the notions of propositional ranges and range conditionals. Propositional ranges provide a simple way of identifying a restricted range of sets of state components to consider, namely those sets that lie between a “lower bound” set and an “upper bound” set (expressed in terms of its complement).

Definition 20 (Propositional ranges) A propositional range over D is a set R ⊆ P(D) such that for some A, B ⊆ D and every S ⊆ D we have S ∈ R iff A ⊆ S and S ∩ B = ∅ (alternatively written S ⊆ \overline{B}, where \overline{B} =^{def} D \ B), in which case we write A \\ B (read “A without B”) to denote the range, that is,

A \\ B =^{def} \{S ⊆ D | A ⊆ S ⊆ \overline{B}\}.

We call an element d ∈ D a propositional range with respect to a satisfaction system (D, [[ ]]) iff [[d]] is a propositional range over D.

Algebraically, of course, a range consists of the full sublattice of P(D) between two points of P(D), which we may think of as the set {A ∪ S | S ⊆ D \ (A ∪ B)}. In particular, ∅ \\ ∅ represents the complete range P(D).

We first observe that expressions like A \\ B characterize ranges pretty well. Empty ranges admit some variability of expression, but a variability easily recognized, as seen in the following theorem.

Theorem 21 (Empty ranges) A range A \\ B is empty iff A and B intersect.

Proof: Clearly, if A ∩ B ≠ ∅, then A \\ B is empty. Conversely, if A \\ B = ∅, then by definition for each S ⊆ D we have either A ⊈ S or S ∩ B ≠ ∅. If we choose S = A, then A ⊆ S, so we have A ∩ B ≠ ∅ as desired. □

Nonempty ranges, in contrast, have exactly one expression of the form A \\ B.

Theorem 22 (Unique representation) If A \\ B = A′ \\ B′ ≠ ∅, then A = A′ and B = B′.

Proof: Suppose A \\ B = A′ \\ B′ ≠ ∅. By Theorem 21 we have A ∩ B = A′ ∩ B′ = ∅. Thus A ∈ A \\ B, so A ∈ A′ \\ B′, so A′ ⊆ A. But we also have A′ ∈ A′ \\ B′, so A′ ∈ A \\ B, so A ⊆ A′, hence A = A′. We next observe that B \ B′ must be empty, since if x ∈ B \ B′, we would have A ∪ {x} ∈ A′ \\ B′ but A ∪ {x} ∉ A \\ B, contrary to hypothesis. A similar argument shows that B′ \ B must be empty, so B = B′. □

To summarize, all propositional ranges have unique representations in terms of disjoint lower and upper bounds, except for the empty range, for which any overlapping bounds provide a representation.

In addition to ranges themselves, our analysis also makes heavy use of conditionals formed from ranges, which we call range conditionals.

Definition 23 (Range conditionals) A range conditional is a set R ⊆ P(D) such that for some A, B, C, D ⊆ D, we have S ∈ R iff either S ∉ A \\ B or S ∈ C \\ D, in which case we write A \\ B ∥− C \\ D (read “A without B gives C without D”) to denote the range conditional, that is,

A \\ B ∥− C \\ D =^{def} {S ⊆ D | S ∈ A \\ B → S ∈ C \\ D}.

If R = A \\ B ∥− C \\ ∅ for some A, B, C, we call the range conditional simple and abbreviate it A \\ B ∥− C. We call an element d ∈ D a (simple) range conditional with respect to a satisfaction system (D, [[ ]]) iff [[d]] is a (simple) range conditional over D.

That is, range conditionals stipulate that the “conclusions” C must be held and the “denials” D must not be held if the “antecedents” A are held and none of the “qualifiers” B are held. Putting together the definitions of propositional ranges and range conditionals, we see that the range conditional A \\ B ∥− C \\ D means \{S ⊆ D | A ⊆ S ⊆ \overline{B} → C ⊆ S ⊆ \overline{D}\}, and the simple range conditional A \\ B ∥− C means \{S ⊆ D | A ⊆ S ⊆ \overline{B} → C ⊆ S\}. We also observe that if A = B = ∅, the range conditional A \\ B ∥− C \\ D reduces to the range C \\ D, that is A \\ B ∥− C \\ D = C \\ D.

In contrast to the unique representations of nonempty ranges, different range conditional expressions may mean the same thing. The most obvious variability is that antecedents (qualifications) may be added to or subtracted from the conclusions (denials) without changing the meaning.

Theorem 24 (Range reduction) For each A, B, C, D ⊆ D, A \\ B ∥− C \\ D = A \\ B ∥− (C \ A) \\ (D \ B).

Proof: Suppose A \\ B ∥− C \\ D = A \\ B ∥− (C \ A) \\ (D \ B) for A, B, C, D ⊆ D. If S ∉ A \\ B, then S is in both conditional ranges, so suppose S ∈ A \\ B, that is, A ⊆ S ⊆ \overline{B}. If S ∈ A \\ B ∥− C \\ D, then S ∈ C \\ D, hence we have C \ A ⊆ C ⊆ S ⊆ \overline{D} ⊆ \overline{D \ B}, so S ∈ A \\ B ∥− (C \ A) \\ (D \ B). And if S ∈ A \\ B ∥− (C \ A) \\ (D \ B), then C \ A ⊆ S ⊆ \overline{D \ B}. But since A ⊆ S ⊆ \overline{B}, we have A ∪ C ⊆ S and S ⊆ \overline{B ∪ D}, hence C ⊆ S ⊆ \overline{D}, so S ∈ A \\ B ∥− C \\ D. Thus A \\ B ∥− C \\ D = A \\ B ∥− (C \ A) \\ (D \ B). □

Accordingly, we call a range conditional expression A \\ B ∥− C \\ D reduced just in case neither A and C nor B and D overlap, that is, C \ A = C and D \ B = D. To avoid the complications introduced by this variability, we ordinarily assume reduced expressions in the following.

As with trivial ranges, we may characterize trivial simple range conditionals in a simple way.

Theorem 25 (Trivial conditionals) For each A, B, C, D ⊆ D, we have A \\ B ∥− C \\ D = P(D) iff either A ∩ B ≠ ∅ or C \ A = D \ B = ∅.

Proof: Since A \\ B ∥− C \\ D = \{S ⊆ D | A ⊆ S ⊆ \overline{B} → C ⊆ S ⊆ \overline{D}\}, it is clear that A \\ B ∥− C \\ D = P(D) if either A ∩ B ≠ ∅ or C \ A = D \ B = ∅ hold. So suppose A \\ B ∥− C \\ D = P(D) and that C \ A ≠ ∅ or D \ B ≠ ∅. If C \ A ≠ ∅, then C ⊈ A, and since A ∈ A \\ B ∥− C \\ D, we know that A ∉ A \\ B. But this can happen only if A \\ B = ∅, which by Theorem 21 occurs only if A∩B ≠ ∅. On the other hand, if D\B ≠ ∅, then D ⊈ B, so \overline{B} ⊈ \overline{D}, and since \overline{B} ∈ A \\ B ∥− C \\ D, we know that \overline{B} ∉ A \\ B. Again, this can happen only if A \\ B = ∅, which by Theorem 21 occurs only if A ∩ B ≠ ∅. Thus in either case we have A ∩ B ≠ ∅. □

In particular, this means that a reduced simple range conditional A \\ B ∥− C is trivial iff either A ∩ B = ∅ or C = ∅.

Unlike nontrivial ranges, which have unique representations, some nontrivial simple range conditionals have different representations: for example, ∅ \\ {a, b} ∥− {c} = ∅ \\ {a, c} ∥− {b} = ∅ \\ {b, c} ∥− {a}. However, the following characterization of nontrivial simple range conditionals shows that such ambiguity occurs only when some reduced representation has just one consequent and some qualifiers, as in this example, and that the antecedents of any alternative representations must coincide in any case.

Theorem 26 (Nontrivial conditionals) If A \\ B ∥− C = A′ \\ B′ ∥− C′ ≠ P(D), A, B, and C are mutually disjoint, and A′, B′, and C′ are mutually disjoint, then A = A′ and either (1) B = B′ and C = C′, or (2) |C| = |C′| = 1, B \ B′ = C′, and B′ \ B = C.

Proof: Suppose A \\ B ∥− C = A′ \\ B′ ∥− C′ ≠ P(D), A, B, and C are mutually disjoint, and A′, B′, and C′ are mutually disjoint.

By nontriviality, we know that neither C nor C′ is empty. Thus A ∉ A \\ B ∥− C, so A ∉ A′ \\ B′ ∥− C′, hence A′ ⊆ A. Similarly, A′ ∉ A′ \\ B′ ∥− C′, so A′ ∉ A \\ B ∥− C, hence A ⊆ A′. Thus A = A′.

We also observe that if |C| > 1, then C = C′. To see this, suppose |C| > 1. If x ∈ C, then since C has other elements, we have A∪{x} ∉ A \\ B ∥− C, so A∪{x} ∉ A′ \\ B′ ∥− C′, and thus x ∉ B′. Since this holds for all x in C, we have C ∩B′ = ∅. Since A∪C ∈ A \\ B ∥− C, so A ∪ C ∈ A′ \\ B′ ∥− C′. Since C ∩ B′ = ∅, this means C′ ⊆ A ∪ C, and since A and C′ are disjoint, this means C′ ⊆ C. But we also have A ∪ C′ ∈ A′ \\ B′ ∥− C′, so A ∪ C′ ∈ A \\ B ∥− C as well. But A ∪ C′ ∈ A \\ B, since C′ ⊆ C and C ∩ B′ = ∅. Thus C ⊆ A ∪ C′, so C ⊆ C′, so C = C′.

We now prove the assertion by cases.

If C = C′, suppose by way of contradiction that B \ B′ ≠ ∅, and let z ∈ B \ B′. Then A ∪ {z} ∈ A \\ B ∥− C, so A ∪ {z} ∈ A′ \\ B′ ∥− C′. Since z ∈ B, the disjointness and equality assumptions imply z ∉ C′, so C′ ⊈ A ∪ {z}, thus A ∪ {z} ∉ A′ \\ B′, hence z ∈ B′, contrary to hypothesis. A symmetric argument shows that we cannot have B′ \ B ≠ ∅, so we conclude B = B′.

If C ≠ C′, we must have |C| = |C′| = 1, since |C| > 1 or |C′| > 1 imply that C = C′. Now if z ∈ B \ B′, then A ∪ {z} ∈ A \\ B ∥− C, so A ∪ {z} ∈ A′ \\ B′ ∥− C′, and since A ∪ {z} ∈ A′ \\ B′, we have C′ ⊆ A ∪ {z}, which by the disjointness assumptions means C′ = {z}. Since this holds for every such z, we see that B \ B′ = C′. A similar argument about elements of B′ \ B shows that B′ \ B = C.

Summarizing, if C = C′, then B = B′ as well, while if C ≠ C′, we have |C| = |C′| = 1, B \ B′ = C′, and B′ \ B = C. These constitute the two cases claimed in the statement of the theorem. □

While simple range conditionals prove important in the theory and practice of artificial intelligence, they cannot express all interesting state specifications. In particular, they cannot exclude any state component from admissible states.

Theorem 27 (Inclusivity) If D contains only simple range conditionals, then D is satisfying.

Proof: If D contains only simple range conditionals and d ∈ D with [[d]] = A \\ B ∥− C, then A ⊆ D ⊆ \overline{B} → C ⊆ D is trivially true, so D ∈ [[d]]. Since this holds for every d ∈ D, D is satisfying. □

Expressing more state spaces thus requires state components that do not represent simple range conditionals (even trivial ones).

We earlier saw that the strongly present satisfaction optimal sets include the satisfying states. Simple range conditionals, however, yield an exact correspondence between these notions.

Theorem 28 (Conditional satisfaction optimality) If D contains only simple range conditionals and S ⊆ D is strongly present satisfaction optimal in P(D), then S is satisfying.

Proof: We prove the contrapositive. Suppose S ⊆ D is unsatisfying, that is, for some d ∈ D, d ∈ S ∉ [[d]]. Now by Theorem 27, D ∈ [[d]], but for all e ∈ S, D ∈ [[e]] as well, so S is not satisfaction optimal. □

In light of Theorem 19, we conclude that when all state components are simple range conditionals, sets are satisfying iff they are strongly present satisfaction optimal.

4.2 Simple reasons

We now define simple reasons in terms of range conditionals and preference systems.

Definition 29 (Simple Reasons) An element d ∈ D is a (finite) simple reason with respect to a satisfaction system (D, [[ ]]) and preference system (D, ∼ ≻) iff there are (finite) disjoint sets A, B, C ⊆ D such that

1. [[d]] = A \\ B ∥− C, and

2. For each S, S′ ∈ [[d]] such that A ⊆ S, S′, if S ⊆ \overline{B} and S′ ⊈ \overline{B}, then S ≻_{d} S′.

We call each triple of sets A, B, C satisfying these conditions a simple reason interpretation of d, and (abusing the notation slightly) write A \\ B ∥− C to indicate their order. We say that a simple reason d is trivial if [[d]] = P(D), and that it is nontrivial otherwise.

Thus a simple reason indicates both a range conditional stipulating that the “conclusions” C must be held if the “antecedents” A are held and none of the “qualifiers” B are held, and a preference for not holding any qualifiers if the antecedents are held. The preference order required of a reason in this definition is both partial and considerably weaker than the total preference order assigned to the corresponding default rule in (Doyle & Wellman, 1991). The present development does not require us to stipulate a total order since the range conditional rules out some of the states compared by the total preference order. The two interpretations agree, however, in that the the total order contains the preference comparisons needed to identify simple reasons.

The constitutive preference employed in identifying reasons provides the simple range conditional with a canonical form, which we see as follows. The first step towards this end comes directly from our analysis of trivial range conditionals, which we use to characterize trivial reasons as ones placing no restrictions on states.

Theorem 30 (Trivial reasons) [[d]] = P(D) iff d is a simple reason with reason interpretation ∅ \\ ∅ ∥− ∅.

Proof: Clearly, if d is a simple reason with reason interpretation ∅ \\ ∅ ∥− ∅, then [[d]] = P(D), so suppose [[d]] = P(D). Then we clearly have [[d]] = ∅ \\ ∅ ∥− ∅. Furthermore, d vacuously satisfies the second part of the definition of simple reason no matter what preference order it indicates since there is no S′ with S′ ⊈ \overline{∅} = D. Thus d can be interpreted as the simple reason ∅ \\ ∅ ∥− ∅. □

Note well that different trivial reasons may bear different preferential interpretations, for as the proof of Theorem 30 noted, their preference interpretations cannot alter their interpretation as reasons.

For nontrivial reasons, we have a stronger characterization.

Theorem 31 (Nontrivial reasons) If d is a nontrivial simple reason, it has a unique simple reason interpretation.

Proof: Suppose [[d]] = A \\ B ∥− C = A′ \\ B′ ∥− C′ ≠ P(D), A, B, and C are mutually disjoint, A′, B′, and C′ are mutually disjoint, and for all S, S′ ⊆ D we have

1. If A ⊆ S, S′, S ⊆ \overline{B}, and S′ ⊈ \overline{B}, then S ≻_{d} S′, and

2. If A′ ⊆ S, S′, S ⊆ \overline{B′}, and S′ ⊈ \overline{B′}, then S ≻_{d} S′.

We first prove C = C′. Suppose, by way of contradiction, that C ≠ C′. Theorem 26 then indicates that B \B′ and B′ \B are nonempty, so let S = A∪(B \B′) and S′ = A∪(B′ \B). Clearly, S ≠ S′, and we have S ⊆ \overline{B′} and S ⊈ \overline{B} and S′ ⊆ \overline{B} and S′ ⊈ \overline{B′}. Applying the two enumerated hypotheses above, this yields S ≻_{d} S′ ≻_{d} S, contradicting the properties of preference systems. Thus we must have C = C′, so by Theorem 26, we also have A = A′ and B = B′. □

In other words, the preferential content of simple reasons disambiguates the associated range conditional in those cases in which several range conditional expressions are possible. Putting these results together gives us a useful canonical form for simple reasons.

Definition 32 (Canonical forms) The canonical form or representation of a simple reason d is ∅ \\ ∅ ∥− ∅ if d is trivial and is the unique interpretation A \\ B ∥− C otherwise. We write d ⇒ A \\ B ∥− C to mean that A \\ B ∥− C is the canonical representation of d.

Clearly, the sets representing the canonical form of a finite simple reason are themselves finite.

The notation A \\ B ∥− C permits us to speak of the “same” reason even when we extend D to a larger domain, since if A, B, C ⊆ D and D ⊆ D′, we also have A, B, C ⊆ D′. This property greatly simplifies mechanizations of agents based on simple reasons expressed in this way, since the domain of state components can be extended indefinitely without necessitating changes in the representations of previously expressed reasons, even though their meanings change with each enlargement of the set of state components.

The preferences associated with reasons would not deserve much attention if their only purpose was to distinguish one reason from others indicating the same range conditional. In fact, their main purpose lies in choosing among the alternative conclusions demanded by the constitutive meaning of valid reasons.

Definition 33 (Validity) We say that a simple reason d ∈ D is valid in S ⊆ D (alternatively, S validates d) if the antecedent conditions of its canonical interpretation hold, that is, if d ⇒ A \\ B ∥− C and S ∈ A \\ B, and that d is invalid in S (or S invalidates d) otherwise. We say that d is presently valid in S (or S presently validates d) if d is valid in S and d ∈ S, and that d is presently invalid in S (or S presently invalidates d) if d is invalid in S and d ∈ S. We write V (d) to mean the set of all S ⊆ D such that d is presently valid in S. Using the same symbol, we write V (S) to mean the set of all d ∈ S such that d is presently valid in S, and \overline{V} (S) to mean the set S \ V (S) of all d presently invalid in S.

The notions of validity and invalidity employed in (Doyle, 1983c) correspond to the notions of present validity and present invalidity introduced here. These notions permit us to rephrase the preference condition used to identify reasons in Definition 29 as saying that states validating the reason are strictly preferred to states invalidating it when attention is restricted to sets in [[d]] ∩ (A \\ ∅). The constitutive preference thus provides the simple range conditional with a sense of direction. Note that even presently invalid reasons can be satisfied; that is, we can have d invalid in S even though S ∈ [[d]]. Clearly, if d ⇒ A \\ B ∥− C is valid in S ∈ [[d]], then C ⊆ S. More generally, we use the notion of validity to identify the cases in which the reason yields its conclusions.

Definition 34 (Yields) If c, d ∈ D and S ⊆ D, we say that d (finitely) yields c in S just in case d is a (finite) simple reason valid in S and has canonical representation A \\ B ∥− C with c ∈ C. We say that S yields c just in case d yields c in S for some d ∈ S. We write θ(d, S) to mean the set of all elements yielded by d in S, and θ(S) =^{def} ⋃_{d∈S} θ(d, S) for the set of all elements yielded by elements of S in S.

Thus if d ∈ V (S) and S ∈ [[d]], we have θ(d, S) ⊆ S. We also note that one never needs conclusions to yield themselves; they are independent of whether the state contains them or not.

if A \\ B ∥− C has  the reason is
C = ∅  trivial
B = ∅  monotonic
A = B = ∅  a premise reason
B ≠ ∅  nonmonotonic or defeasible
A = ∅, B ≠ ∅  a basic assumption

Table 2: Special simple reasons

Theorem 35 (Conclusion independence) If c ∈ θ(d, S), then c ∈ θ(d, S \ {c}).

Proof: If c ∈ θ(d, S), then d must have canonical representation A \\ B ∥− C and must be valid in S with c ∈ C. Since c ∉ A and c ∉ B, this means d is also valid in S \ {c}, hence c ∈ θ(d, S \ {c}). □

However, we cannot strengthen this to conclude that c ∈ θ(S \ {c}) whenever c ∈ θ(S), since the only reason yielding c in S may be c itself.

It appears one can alternatively define simple reasons by replacing preference for validity by preference for yielding conclusions, or possibly reduced conclusions. Such an approach would represent an “altruistic” interpretation of reasons as opposed to the “self-interested” approach presented here, with reasons concerned about the “ends” of the reason (the conclusions being held) rather than about the “means” by which these conclusions are held (this reason or some other). However, this alternate definition also appears to introduce unnecessary distinctions among reasons due to antecedents repeated in the conclusions. We do not explore it here.

We may identify several important special forms of simple reasons in terms of the canonical form, defined here and summarized in Table 2.

Definition 36 (Special simple reasons) If a simple reason has canonical form A \\ B ∥− C, we call the reason trivial just in case C = ∅; monotonic just in case B = ∅; nonmonotonic or defeasible just in case B ≠ ∅; a premise reason just in case A = B = ∅; and a basic assumption just in case A = ∅ ≠ B.

Monotonic reasons yield conclusions that cannot be defeated by enlarging the state, while nonmonotonic reasons yield conclusions that can be defeated by enlarging the state. Trivial reasons never yield any conclusions at all, and are both finite and monotonic. Basic assumption reasons yield defeasible assumptions that do not depend on the presence of any other assumptions in the state, while premise reasons yield conclusions that do not depend on the presence or absence of anything else in the state.

5. Reasoned constitutions

We identified reasons in part in terms of constraints they place on the states in which they appear. But the constraints used to identify reasons capture only part of the full constitutional role of reasons. Recall that the original RMS stability principle requires labeling a node in if and only if the recorded reasons contain a valid reason for the node. The meanings imputed to reasons so far ensure that each consequence of a valid reason is in the state, but do nothing to ensure that every element of the state has a valid reason for its presence, much less the RMS groundedness principle that one can identify a set of valid reasons providing a well-founded argument for the element.

The RMS could require grounding arguments for nodes because it distinguished nodes and reasons. In the present setting, we view reasons as state components that may appear as conclusions like other state components. We therefore do not wish to require that every state component has a valid reason for its presence, since all reasons themselves would then need reasons themselves, and we would wind up with either infinite states containing infinite regresses or finite states containing circular reasoning structures. To express less comprehensive formulations of this part of the role of reasons, as well as to express the other half of the stability principle, we expand the notions of framings and constitutions employed in the preceding to notions that permit one to consider some elements of states as given and others as derived from the givens.

5.1 Constructive framings

Though quite apt for describing many computational systems, elemental framings consisting simply of the representations explicitly contained in a state are not always the most useful framings of states for analyzing sophisticated reasoning agents, as the set of components explicitly contained in a state mainly serves to represent an “implicitly contained” state description upon which the agent (or more precisely, the agent’s action-taking mechanisms) bases its actions. For example, one views some frame-based and taxonomic representational systems as indicating “virtual” representations in addition to those frames or statements actually present in the state (Doyle, 1983b; Fahlman, 1979; Touretzky, 1986); one sometimes also views states consisting of sets of logical statements as indicating their deductive closure (or their closure under a set of inference rules) (Konolige, 1985). To analyze such agents, one does better to frame states in terms of two sets of state components; a set of manifest components explicitly contained or represented in the state, and a set of constructive components implicitly stored or represented in the state and computed or derived from the manifest components (Doyle, 1989).

Accordingly, we define a constructive framing to be a multiattribute framing ϕ : S → S_{m} × S_{c} interpreting each state as a manifest state in a set S_{m} and a constructive state in a set S_{c}, and write ϕ_{m} : S → S_{m} and ϕ_{c} : S → S_{c} to mean the corresponding projections of this mapping onto these spaces. The most useful constructive framings for many artificial intelligence systems are constructive elemental framings that combine a constructive framing of S with elemental framings of S_{m} and S_{c} to yield a framing ϕ : S → P(D_{m}) × P(D_{c}). We say that a constructive elemental framing is component compatible if manifest state components may also be constructive state components, that is, if D_{m} ⊆ D_{c}, and is extensional if in addition constructive states always contain their corresponding manifest states, that is, if ϕ_{m}(s) ⊆ ϕ_{c}(s) for every s ∈ S. We call the framing uniform if D_{m} = D_{c}.

Constructive framings may interpret distinct states as containing the same manifest or constructive states. Distinct states sharing their constructive portions need not seem problematic except to lawyers and others seeking to find intentional interpretations of behavior, as we may view the manifest parts of one or both states as containing “redundant” components that do not change the constructive part. But distinct states sharing their manifest parts indicate that the construction process involves nondeterminism, and so may pose problems for mechanizations of agents characterized in this way. Theories of nonmonotonic reasoning provide good examples of this, for one ordinarily permits nonmonotonic reasoning rules to conflict (recall the earlier example involving conflicting rules about Quakers and Republicans), which gives rise to multiple possible interpretations of or constructions from the manifest representations. We say a constructive framing ϕ is constructively deterministic just in case |ϕ_{m}^{−1}(ϕ_{m}(s))| = 1 for every s ∈ S, and is manifestly deterministic just in case |ϕ_{c}^{−1}(ϕ_{c}(s))| = 1 for every s ∈ S.

5.2 Constructive constitutions

Basic constitutions do not apply directly to state spaces framed with elemental constructive framings, since these map states to pairs of sets rather than to single sets of state components. We therefore extend the notion of basic constitution to that of constructive constitution by adding in context-dependent or contextual constitutions that describe how manifest and constructive states restrict each other.

Definition 37 (Contextual constitutions) A contextual constitution Σ over D relative to D′ is a map Σ : P(D′) → Σ(D) taking each set S′ ⊆ D′ to a basic constitution Σ(S′). We write the varying parts of a contextual constitution Σ(S′) in the form C(S′), ⊢(S′), [[ ]](S′), and B(S′), and define the set of elements A(Σ) to contain just those pairs (S′, S) ∈ P(D′) × P(D) such that S ∈ A(Σ(S′)).

Clearly, we may use unstructured contextual constitutions to describe any construction relation whatsoever.

Theorem 38 (General constructions) If R ⊆ P(D′) × P(D), there is a contextual constitution Σ over D relative to D′ such that A(Σ) = R.

Proof: For each S′ ⊆ D′, take Σ(S′) to be the unstructured basic constitution such that B(Σ(S′)) = {S ⊆ D | (S′, S) ∈ R}. Then we clearly have (S′, S) ∈ A(Σ) iff (S′, S) ∈ R. □

We may also embed basic constitutions in contextual constitutions over the same set.

Theorem 39 (Embedding constitutions) If Σ is a basic constitution over D and Σ′ a contextual constitution over D relative to D′, then there is a contextual constitution Σ′′ over D relative to D′ such that (S′, S) ∈ A(Σ′′) iff (S′, S) ∈ A(Σ′) and S ∈ A(Σ).

Proof: Define Σ′′ to be just like Σ′ except that B(Σ′′(S′)) = B(Σ′(S′)) ∩ A(Σ) for every S′ ⊆ D′. Then we clearly have (S′, S) ∈ A(Σ′′) iff (S′, S) ∈ A(Σ′) and S ∈ A(Σ). □

Other embeddings weave the notions of consistency, etc. together in a more natural way, but we do not pursue these here.

We obtain constructive constitutions by combining sub-constitutions describing the manifest and constructive states with contextual sub-constitutions describing the ways each of these relate to each other.

Definition 40 (Constructive constitutions) A constructive constitution Σ over manifest state components D_{m} and constructive state components D_{c} consists of basic constitutions Σ_{m} over D_{m} and Σ_{c} over D_{c}, together with contextual constitutions Σ_{mc} over D_{m} relative to D_{c} and Σ_{cm} over D_{c} relative to D_{m}. We define the elements A(Σ) to be those pairs (S, E) ∈ P(D_{m}) × P(D_{c}) such that S ∈ A(Σ_{m}), E ∈ A(Σ_{c}), (E, S) ∈ A(Σ_{mc}), and (S, E) ∈ A(Σ_{cm}). If (S, E) ∈ A(Σ) we also write S ⊴ E, and we define the admissible constructions of S, written ACons(S), to consist of just those sets E such that S ⊴ E.

Thus the various satisfaction systems of constructive constitutions interpret each manifest (constructive) state component both as a restriction on the manifest (constructive) states in which it can occur, and as a restriction on the ways it can yield (derive from) the constructive (manifest) states.

The four sub-constitutions provided for constructive constitutions clearly represent definitional overkill. Theorem 39 implies the two contextual constitutions may absorb the two basic constitutions, and Theorem 38 implies that each of the contextual constitutions can absorb the resultant restriction of the other in its bounding set. Thus we really only need use one contextual constitution to represent a constructive constitution. In spite of this, however, we keep the definition given above. In the first place, amalgamating all the constitutions in this way may obscure the different restrictions: even though the amalgamation does not change the states so characterized, it may impede exposition and understanding. In the second place, amalgamating the two contextual constitutions into one may yield a constitution with very different locality properties than the original ones, since local logical or satisfaction conditions in the absorbed constitution turn into unstructured general conditions in the absorbing constitution. Again, this does not change the objects so characterized, but it may impede understanding.

These hesitations to amalgamate separate constitutions in the general definition need not, however, prevent us from doing so for the sake of convenience in one important special case, that of the extensional constitutions appropriate to extensional framings.

Definition 41 (Extensional constitutions) An extensional constitution Σ is a constructive constitution over manifest state components D_{m} and constructive state components D_{c} such that D_{m} ⊆ D_{c} and S ⊆ E whenever S ⊴ E, and a preferential extensional constitution adds a preference system ∼ ≻ over D_{c}. If S ⊴ E, we call E an admissible extension of S. We also write AExts(S) to mean ACons(S).

Thus a preferential extensional constitution yields a preferential basic constitution over the constructive state components for each set of manifest state components. Note that the preference system of a preferential extensional constitution does not depend on the manifest state; a more general treatment would permit contextual variation of it as well.

We can express the extensionality condition of extensional constitutions by means of the contextual constitution Σ_{cm} by taking this constitution to map each context S ⊆ D_{m} to the satisfying constitution over D_{c} that sets [[d]](S) = {E ⊆ D_{c} | d ∈ S → d ∈ E} for each d ∈ D_{c}. These highly local meanings then imply the global condition that E ∈ [[E]](S) iff S ⊆ E. But rather than go through this exercise when this condition is all that is desired of this contextual constitution, we adopt the shortcut of simply making the bounding set of the other contextual constitution correspond to a subset of the subset relation, that is, making B(S) ⊆ {E ⊆ D_{c} | S ⊆ E}.

We extend the notion of constitutional optimality to extensional constitutions in the obvious way.

Definition 42 (Optimal extensional constitutions) An extensional constitution Σ over D_{m} and D_{c} is optimal with respect to a preference system ∼ ≻ over D_{c} just in case E is optimal in AExts(S) with respect to ∼ ≻ whenever S ⊴ E.

5.3 Reasoned constitutions

As noted earlier, the meanings associated with reasons in Definition 29 capture half of the RMS stability principle, but do not require that each element of a constructive state possess either a valid reason or a well-founded argument for its presence. We now capture the second half of the basic RMS stability principle, that nodes be labeled in only if they have a valid reason, by applying the requirement of local groundedness, or local logical and reasoned derivability, to all constructive state components.

Definition 43 (Local groundedness) An element d ∈ D is (finitely) locally grounded in E with respect to S ⊆ E in a preferential basic constitution iff either

1. d ∈ S,

2. E′ \ {d} ⊢ d for some (finite) E′ ⊆ E, or

3. E \ {d} (finitely) yields d.

When this happens, we write S <_{l}^{d} E. We write S <_{l} E just in case S <_{l}^{d} E for each d ∈ E.

If we say d is given in E with respect to S ⊆ E just in case d ∈ S, then a state component is locally grounded just in case it is either given, logically derivable from other state components, or yielded by some other state component. We then define reasoned constitutions as follows.

Definition 44 (Reasoned constitutions) A reasoned constitution Σ is a uniform preferential extensional constitution such that every element of every admissible extension is locally grounded with respect to the manifest state, that is, S <_{l} E with respect to Σ(S) and the preference system whenever S ⊴ E.

We can express this condition of universal local grounding in a variety of ways. The most natural and local formulation places it in the contextual constitution Σ_{cm} to require that for every d ∈ D_{c} we have

[[d]]_{cm} ⊆ {(S, E) ∈ P(D_{m}) × P(D_{c}) | d ∈ E → S <_{l}^{d} E}.

That is, each element requires that it be locally grounded whenever it appears in an admissible extension.

The definition of reasoned constitution stipulates only that constructive state components must be locally grounded, not that they must possess any more complex arguments for their presence. Since constructive constitutions already require states to satisfy the reasons they contain, this definition identifies reasoned constitutions as those which enforce the RMS stability principle. We omit any requirement corresponding to the RMS grounding principle from the definition of reasoned constitutions so that we may consider reasoning systems that employ a variety of patterns of grounding of conclusions. For example, because humans do not appear to remember or enforce reasons for most of their beliefs, some authors (e.g., (Gärdenfors, 1990; Harman, 1986); cf. (Doyle, 1992)) criticize the RMS for requiring extensive grounding of all elements (although people do appear excellent at effortlessly constructing rationalizations or supporting arguments—sometimes spurious—for their beliefs (Gazzaniga, 1985)). Our definition of reasoned constitution accommodates these concerns both by taking manifest state components as givens needing no supporting reasons (though not forbidding such supporting reasons), and by encompassing reasoned constitutions that require different levels of grounding for different state components, for example, constitutions requiring only minimal local grounding of elements of long-term memory, for which people seem especially prone to ignore reasons, but requiring stricter grounding patterns for elements of short-term memories, for which people seem more aware of their reasons for thinking things. We thus identify reasoned constitutions by the minimal requirement that everything not given must have a reason or immediate derivation, and then examine special reasoned constitutions that impose stronger grounding requirements for some or all constructive state components.

The most natural stronger grounding condition, which we simply call groundedness (or strict groundedness) strengthens the immediate derivability of local groundedness to derivability by an argument mixing entailment and reasons that traces back to givens, such that each step of the argument makes the same assumptions as all the others.

Definition 45 (Groundedness) We say that e is (finitely) grounded in E with respect to S ⊆ E in a preferential basic constitution iff there is a (finite) grounding set G ⊆ E and a well-ordering <_{G} of G such that e ∈ G and whenever d ∈ G, either

1. d ∈ S,

2. G_{<d} ⊢ d, where G_{<d} =^{def} {g ∈ G | g <_{G} d}, or

3. there is some (finite) simple reason f ∈ G_{<d} yielding d in E such that f ⇒ A \\ B ∥− C and A ⊆ G_{<f}.

When this happens, we write S <_{g}^{d} E (S <_{f}^{d} E). We write S <_{g} E (S <_{f} E) just in case S <_{g}^{d} E (S <_{f}^{d} E) for each d ∈ E.

Note well that the qualifications of reasons yielding conclusions must be checked against the whole set E, while the antecedents must precede the reason in the grounding order. Also, as one might expect, groundedness implies local groundedness.

Theorem 46 (Local grounding) If e is (finitely) grounded in E with respect to S ⊆ E, then e is (finitely) locally grounded in E with respect to S.

Proof: Suppose e is (finitely) grounded in E with respect to S ⊆ E with (finite) grounding set G ⊆ E \ {e}. Then by definition, either e ∈ S, or there is a (finite) set A ⊆ G such that A ⊢ {e}, or some presently valid (finite) reason in E \ {e} yields e. □

The notions of groundedness and local groundedness, however, represent extremes along a dimension rather than the only two possibilities. For example, as (Doyle, 1983b; Doyle & Wellman, 1990) suggest one might employ intermediate notions of groundedness with respect to grounding neighborhoods or locales defined to be strict grounding for elements of the neighborhoods or locales, but only local grounding for elements outside them. This paper does not pursue intermediate notions of groundedness or nonuniform degrees of grounding of admissible extensions. We instead focus on the special cases of uniformly grounded reasoned constitutions, named as follows.

Definition 47 (Special reasoned constitutions) We say a reasoned constitution is (finitely) grounded just in case it requires every element of every admissible extension to be (finitely) grounded with respect to the manifest state.

6. Grounded extensions

We now turn to analyzing the structure of admissible extensions in grounded reasoned constitutions, and for simplicity of analysis ignore the structure of manifest states. The manifest states of RMS and many other systems really consist of sets of stipulated state components, which may be stipulated one by one, resulting in arbitrary sets of stipulated components. The reasoned constitutions corresponding to these systems thus employ trivial constitutions for manifest states and purely extensional contextual constitutions for manifest states relative to constructive states, so the analysis of their admissible extensions mirrors the analysis of extensions that ignore the internal structure of manifest states to focus only on the constitutions of constructive states and the contextual constitutions specifying how each constructive element is grounded in the manifest state.

Definition 48 (Extensions) If Σ is a basic constitution over D, we say that E is an extension of (or a state extending) S ⊆ D iff S ⊆ E ∈ A(Σ), and write S ⊲ E to indicate that E extends S, and Exts(S) to denote the set of extensions of S. If Σ is an extensional constitution over D_{m} and D_{c}, we say that E is an extension of S iff S ∈ A(Σ_{m}), E ∈ A(Σ_{c}), and S ⊆ E. If S ⊲ E and S <_{g} E (S <_{l} E, S <_{f} E), we write S ⊲_{g} E (S ⊲_{l} E, S ⊲_{f} E). We write GExts(S), LExts(S), and FGExts(S) to mean, respectively, the sets of grounded, locally grounded, and finitely grounded extensions of S.

Finitely grounded extensions are grounded extensions by definition, and we see that grounded extensions are locally grounded as an immediate corollary of Theorem 46.

6.1 Stratification

We first examine an important alternate characterization of the notions of grounded and finitely grounded extensions. Here and in the following we assume a fixed reasoned constitution.

Definition 49 (Levels) Let S, E ⊆ D. Then the sequence ⟨Λ_{α}⟩ (α an ordinal), the levels from S in E, are defined for all ordinals by 1. Λ_{0}(S, E) = S,

2. Λ_{α+1}(S, E) = Θ(Λ_{α}(S, E)) ∪ θ(Λ_{α}(S, E)), and

3. Λ_{λ}(S, E) = ⋃_{α<λ} Λ_{α}(S, E) for limit ordinals λ.

We define Λ(S, E) = ⋃_{α} Λ_{α}(S, E) to be the sum of all levels.

Note how each level includes the deductive closures of the preceding levels of inference via valid reasons. We also easily observe that if α ≤ β, then S ⊆ Λ_{α}(S, E) ⊆ Λ_{β}(S, E) ⊆ Λ(S, E), and that if Λ_{α} = Λ_{α+1}, then Λ_{α} = Λ (here and in the following, we sometimes omit the level parameters (S, E) when the meaning is clear).

Theorem 50 If α > |D|, then Λ(S, E) = Λ_{α}(S, E).

Proof: If D has fewer than α elements, it must be that for some β + 1 ≤ α no new element is introduced in Λ_{β+1}, in other words, Λ_{β} = Λ_{β+1}. But then Λ_{β} = Λ, and since Λ_{β} ⊆ Λ_{α} ⊆ Λ, we have Λ = Λ_{α}. □

As this result suggests, the division of extensions into levels naturally leads to ranking elements according to the first level at which they appear.

Definition 51 (Rank) If e ∈ Λ(S, E), the rank of e in Λ(S, E) is the least ordinal α such that e ∈ Λ_{α}(S, E). If A ⊆ Λ(S, E), the rank of A in Λ(S, E) is the least ordinal not less than the rank of any element of A.

With the notion of rank, we first observe that the sum of all levels is closed.

Lemma 52 (Closure) For every S, E ⊆ D, Λ(S, E) = Θ(Λ(S, E)).

Proof: Suppose A ⊆ Λ. A has rank, say α, so if A ⊢ B, then B ⊆ Λ_{α+1} ⊆ Λ. Since Λ ⊆ Θ(Λ), we have Λ = Θ(Λ). □

In addition, extensions contain the sum of all their levels.

Lemma 53 (Containment) If S ⊲ E, then Λ(S, E) ⊆ E.

Proof: Let S ⊲ E. Clearly Λ_{0} ⊆ E, so assume Λ_{β} ⊆ E for each β < α. If α is a limit ordinal, then by definition Λ_{α} ⊆ E. If α is a successor ordinal, say α = β + 1, let e ∈ Λ_{α}. If e ∈ S, then e ∈ E, so suppose e ∉ S. If e ∈ Θ(Λ_{β}), then e ∈ E since E is closed. If e ∉ Θ(Λ_{β}) there is a d ∈ Λ_{β} with d ⇒ A \\ B ∥− C, A ⊆ Λ_{β}, E ⊆ \overline{B}, and e ∈ C. Since E is satisfying, this means C ⊆ E, so e ∈ E. Hence Λ_{α} ⊆ E, so Λ ⊆ E. □

Moreover, grounded extensions equal the sum of all their levels.

Theorem 54 (Stratification) If S ⊲_{g} E then Λ(S, E) = E.

Proof: Suppose S ⊲_{g} E. Since S ⊲ E, by Lemma 53 we have Λ ⊆ E. To see that E ⊆ Λ, suppose e ∈ E. Since E is a grounded extension of S, there is a grounding set G ⊆ E for e from S in E. We show G ⊆ Λ by <_{G}-induction. Let f ∈ G have no predecessors in <_{G}. Clearly f is the minimum of G, and by definition of G, we must have f ∈ S, hence f ∈ Λ. Now suppose that f ∈ G and for each d <_{G} f, either d ∈ S or there is a grounding subargument G′ ⊆ G for d. If f ∈ S, then f ∈ Λ. If {g ∈ G | g <_{G} f} ⊢ {f}, then f ∈ Λ since Λ is closed. Otherwise there is a d ∈ G such that d ⇒ A \\ B ∥− C, A <_{G} d <_{G} f, E ⊆ \overline{B}, and f ∈ C. By the inductive hypothesis, A ⊆ Λ and d ∈ Λ, so there is some ordinal α such that A ⊆ Λ_{α} and d ∈ Λ_{α}. But then by construction C ⊆ Λ_{α+1}, so f ∈ Λ. Hence E ⊆ Λ, so E = Λ. □

Obviously, If S ⊲_{g} E and α > |E|, then E = Λ_{α}(S, E), and if S ⊲_{g} E and α is the rank of E, then E = Λ_{α}(S, E). We thus easily see that finitely grounded extensions equal the sum of their finite levels.

Corollary 55 (Countable stratification) If S ⊲_{f} E, then E = Λ_{ω}(S, E).

Proof: Let S ⊲_{f} E and e ∈ E. Since e has a finite grounding set G, the rank of e is at most |G|, hence e ∈ Λ_{ω}(S, E). Thus E ⊆ Λ_{ω}(S, E), so by Lemma 53, E = Λ_{ω}(S, E). □

The second main result shows that fixed points of the level operator are grounded extensions, assuming they are consistent, bounded, and satisfy all their non-simple-reason elements (by this we mean that the set satisfies each of its elements that is not a simple reason).

Theorem 56 (Fixed point) If E is consistent, bounded, satisfies its non-simple-reason elements and E = Λ(S, E), then S ⊲_{g} E.

Proof: Suppose E is consistent, bounded, satisfies its non-simple-reason elements, and Λ = E. Since S ⊆ Λ, S ⊆ E. Let e ∈ E with e ⇒ A \\ B ∥− C, and suppose A ⊆ E. Then there is an ordinal α such that e ∈ Λ_{α} and A ⊆ Λ_{α}, so by construction if E ⊆ \overline{B} as well, then C ⊆ Λ_{α+1} ⊆ E. Thus E is satisfying. Similarly, if A ⊢ B, A ⊆ Λ, and A has rank α, then B ⊆ Λ_{α+1} ⊆ Λ. Thus E is closed, and therefore an extension. We prove E is a grounded extension of S by induction on rank. Specifically, we prove that each element of E has a rank-preserving grounding set, a set G ⊆ E such that the rank of a does not exceed the rank of b whenever a ≤_{G} b. Let e ∈ E have rank α. If α = 0, then e ∈ S and we are done since {e} is a rank-preserving grounding argument for e from S in E. Now assume that α > 0 and all elements of rank less than α have rank-preserving grounding arguments. Necessarily, α is a successor ordinal, since no elements are introduced at limit ordinals, so suppose α = β + 1. If e ∈ Θ(Λ_{β}), then there is some G ⊆ Λ_{β} such that G ⊢ {e}, and otherwise there is some d ∈ Λ_{β} such that d ⇒ A \\ B ∥− C, A ⊆ Λ_{β}, E ⊆ \overline{B}, and e ∈ C. Then by inductive hypothesis each element of G or {d} ∪ A has a rank-preserving grounding argument, so merge these arguments preserving rank-order, and add e to the end, so producing a rank-preserving grounding argument for e. Thus S ⊲_{g} E. □

Putting these results together, we arrive at our main characterization of grounded extensions.

Corollary 57 (Grounded extensions) If E is consistent, bounded, and satisfies its nonsimple-reason elements, then S ⊲_{g} E iff E = Λ(S, E).

From this we derive a corresponding characterization of finitely grounded extensions.

Theorem 58 (Finitely grounded extensions) If E is consistent, bounded, satisfies its non-simple-reason elements, ⊢ is compact, and every simple reason in D is finite, then S ⊲_{f} E iff E = Λ_{ω}(S, E).

Proof: Suppose E is consistent, bounded, satisfies its non-simple-reason elements, ⊢ is compact, and every simple reason in D is finite. By Corollary 55, we need only show that Λ_{ω} = E implies S ⊲_{f} E. Suppose Λ_{ω} = E. We first show Λ_{ω} = Λ. Suppose, by way of contradiction, that Λ ≠ Λ_{ω}. Then there must be a least ordinal α ≥ ω such that for some e ∈ D, e ∈ Λ_{α+1} \ Λ_{α}. Since α is minimal, Λ_{ω} = Λ_{α}, for otherwise Λ_{ω} = Λ_{ω+1} and hence Λ_{ω} = Λ. If e ∈ Θ(Λ_{ω}) then there is some G ⊆ Λ_{ω} such that G ⊢ {e}. Since ⊢ is compact, there is a finite G′ ⊆ G such that G′ ⊢ {e}. But then the rank of G′ is finite, say β, so e ∈ Λ_{β+1}, a contradiction. If e ∉ Θ(Λ_{ω}), then by construction, there is some f ∈ Λ_{ω}, f ⇒ A \\ B ∥− C, A ⊆ Λ_{ω}, E ⊆ \overline{B}, and e ∈ C. Since A is finite, this means the rank of A is also finite. Thus there is some β < ω such that A ⊆ Λ_{β} and f ∈ Λ_{β}, so e ∈ Λ_{β+1} ⊆ Λ_{ω}, a contradiction. Thus Λ = Λ_{ω}, and since Λ_{ω} = E, by Theorem 56 E is a grounded extension of S. We see that E is finitely grounded by induction on rank. Clearly, if e ∈ Λ_{0}, then e ∈ S, hence {e} is a rank-preserving grounding set. Now suppose the rank of e is α + 1 < ω. If e ∈ Θ(Λ_{α}), then there is a finite G ⊆ Λ_{α} such that G ⊢ {e}. If e ∉ Θ(Λ_{α}), then by construction there is some f ∈ Λ_{α} with f ⇒ A \\ B ∥− C, A ⊆ Λ_{α}, E ⊆ \overline{B}, and e ∈ C. By inductive hypothesis, each of G or f ∪ A have finite rank-preserving grounding sets, so merge these preserving rank-order, add e to the end, and the result is a finite rank-preserving grounding order for e. □

Theorem 59 (Monotonic determinism) If D contains only monotonic simple reasons, every subset of D has a unique grounded extension.

Proof: Suppose each element of D is a monotonic simple reason, and let S ⊆ D. Consider E = Λ(S, ∅). Since all simple reasons are monotonic, Λ(S, ∅) = Λ(S, X) for each X ⊆ D. In particular, E = Λ(S, ∅) = Λ(S, E), so S ⊲_{g} E by Theorem 56. Now if S ⊲_{g} E′, then E′ = Λ(S, E′) = E by the previous observation, so E is the only grounded extension. □

As a corollary, if D contains only finite monotonic simple reasons, every subset of D has a unique finitely grounded extension.

We also find that grounded extensions are minimal among locally grounded extensions.

Theorem 60 (Grounded minimality) If S ⊲_{g} E, S ⊲_{l} E′, and E′ ⊆ E, then E = E′.

Proof: Suppose S ⊲_{g} E, S ⊲_{l} E′, and E′ ⊆ E. We first show Λ(S, E) ⊆ Λ(S, E′) by induction. Clearly Λ_{0}(S, E) ⊆ Λ_{0}(S, E′) since each equals S. Assume Λ_{β}(S, E) ⊆ Λ_{β}(S, E′) for each β < α. If α is a limit ordinal, then by definition Λ_{α}(S, E′) ⊆ Λ_{α}(S, E). If α is a successor ordinal, say α = β +1, let e ∈ Λ_{α}(S, E). If e ∈ S or e ∈ Θ(Λ_{β}(S, E)), then e ∈ E′, and otherwise there is a d ∈ Λ_{β}(S, E) with d ⇒ A \\ B ∥− C, A ⊆ Λ_{β}(S, E), E ⊆ \overline{B}, and e ∈ C. But since E′ ⊆ E ⊆ \overline{B}, this means e ∈ Λ_{α}(S, E′). Hence Λ(S, E) ⊆ Λ(S, E′). But by Theorem 54 and Lemma 53, E = Λ(S, E) ⊆ Λ(S, E′) ⊆ E′, hence E = E′. □

Obviously, this result means that grounded extensions are minimal among grounded extensions, and that finitely grounded extensions are minimal among finitely grounded extensions.

Our earlier treatment (Doyle, 1983c) also explores a different means for decomposing extensions. Where stratification partitions elements according to how many steps (logical or reasoned) they take to derive, one may instead partition the underlying set D according to which state components each state component mentions, in the following sense.

Definition 61 (Reasoned decomposition) Suppose S ⊆ D and d ∈ D. The set S mentions d iff for some e ∈ S, e ⇒ A \\ B ∥− C and d ∈ A ∪ B ∪ C. Two sets A, B ⊆ D have disjoint mention sets iff A mentions no b ∈ B and B mentions no a ∈ A. A subset A ⊆ S is an isolated subset of S iff A and S \ A have disjoint mention sets. A set S ⊆ D is called simple iff S has no isolated subsets other than itself and ∅. The universe U(S) of a set S is the smallest set containing S and containing the mention sets of each of its elements, that is, S ⊆ U(S) and if d ∈ U(S) and d ⇒ A \\ B ∥− C, then A, B, C ⊆ U(S).

For example, S and ∅ are isolated subsets of S, and if D = {a}, then D is simple, while if D = {a, b} where both elements have trivial interpretations, then D is not simple, since each of {a} and {b} is. In addition, if D is finite, then every subset has a finite universe. Moreover, if S ⊆ D has a finite universe, then all simple reasons in S are finite. Sets with disjoint universes have disjoint mention sets, though the converse need not be true.

These definitions permit an interesting analysis of the structure, computability, and complexity of extensions when the information system under consideration is trivial, and in particular allow one to avoid assumptions about the finiteness of D in favor of assumptions of finite universes of sets of manifest components. We do not know if these definitions may be generalized to provide useful results when the constitution involves a nontrivial information system.

6.2 Optimality

We saw in Section 4.1 that simple range conditionals, and therefore simple reasons, prove interesting with respect to the defined notion of strong present satisfaction preference. However, we defined simple reasons with respect to that portion of an arbitrary preference system related to the validity of reasons. Investigating optimality with respect to this portion of the given preference system provides further insight into conclusions drawn from simple reasons.

Definition 62 (Validity preferences) The pure validity preference system corresponding to a basic constitution Σ over D is the preference system (D, ∼ ≻) such that for each d ∈ D and S, S′ ⊆ D, we have S ∼_{d} S′ iff either S = S′ or d is not a simple reason, and have S ≻_{d} S′ just in case d is a simple reason valid in S and invalid in S′. The weak present validity preference system instead defines S ≻_{d} S′ just in case d is a simple reason presently valid in S but not presently valid in S′ (either d ∉ S′ or d is presently invalid in S′). The strong present validity preference system instead defines S ≻_{d} S′ just in case d is a simple reason presently valid in S and presently invalid in S′. We call any set optimal in some range with respect to the pure, weak, or strong present validity preference systems (respectively) purely, weakly, or strongly present validity optimal in the range.

Thus a set S is weakly present validity optimal in R iff for each d ∈ D and S′ ∈ R, if S′ presently validates d but S does not, then there is some e presently valid in S but not presently valid in S′; phrased differently, if d ∈ V (S′) but d ∉ V (S), then there is some e ∈ V (S) with e ∉ V (S′). Similarly, a set S is strongly present validity optimal in R iff for each d ∈ D and S′ ∈ R, if S′ presently validates d while S presently invalidates d, then there is some e presently valid in S but presently invalid in S′, or equivalently, if \overline{V} (S′)∩V (S) ≠ ∅ whenever V (S′) ∩ \overline{V} (S) ≠ ∅. Obviously, if S is strongly present validity optimal in R, then S is weakly present validity optimal in R. The notions of weakly present validity optimality and strongly present validity optimality correspond to the notions of validity optimality and strong validity optimality of (Doyle, 1983c).

As one might expect, since the varieties of validity optimality involve an arbitrary preference system which may bear no relation to satisfaction systems, validity optimality proves very different from satisfaction optimality. For example, satisfying sets need not be weakly present validity optimal among satisfying sets. To see this, let D = {d}, and [[d]] = P(D). Then both ∅ and D are satisfying, D presently validates d, but ∅ presently validates no element not in D, so ∅ is not weakly present validity optimal in P(D). In addition, unsatisfying sets may be weakly present validity optimal in P(D). We see this by letting D = {d, e}, d ⇒ ∅ \\ {d} ∥− {e}, and e ⇒ ∅ \\ {e} ∥− {d}. Then {d} and {e} are unsatisfying, but every set in P(D) is validity optimal since no set validates any of its own elements.

We now use these optimality notions to show that grounded extensions make as many assumptions as possible given the reasons they contain.

Theorem 63 (Weak optimality) Grounded constitutions are optimal with respect to weak present validity preferences.

Proof: Suppose, by way of contradiction, that S ⊴ E, S ⊴ E′ and that there is a d is valid in E′ but not valid in E, but no e valid in E is not valid in E′. That is, there is a d ∈ E′, d valid in E and either d ∉ E or d invalid in E′, and V (E) ⊆ V (E′). The element d shows E ≠ E′, so by the minimality of E and E′ among grounded extensions, E \ E′ ≠ ∅. Let e ∈ E \ E′. Since S ⊆ E′, e ∉ S. But since E is locally grounded, there must be some f ∈ E, f valid in E, and e a consequence of f. But then f is valid in E′ as well, so e ∈ E′, a contradiction. Thus E must be weakly present validity optimal in AExts(S), which means that the constitution is optimal with respect to weak present validity preference. □

We interpret this result as indicating the preferential orthogonality of grounded extensions, an orthogonality that appears in nonmonotonic and default logics as the logical inconsistency of alternative extensions. We take this to demonstrate that one can sensibly speak of psychological incompatibility without requiring notions of logical inconsistency. We do not know whether preferential orthogonality characterizes grounded extensions, that is, whether any set is validity optimal among admissible extensions is itself an admissible extension. We can, however, strengthen the result somewhat for finitely grounded constitutions.

Theorem 64 (Strong optimality) Finitely grounded constitutions in which all reasons are finite are optimal with respect to strong present validity preferences.

Proof: Suppose S ⊴ E in a finitely grounded constitution in which all reasons are finite, and that E is not strongly present validity optimal. Then there is some E′ such that S ⊴ E′ and some d ∈ E such that d is valid in E′ but invalid in E, and if e is valid in E, then either e ∉ E′ or e is valid in E′ as well. The differing properties of d show E ≠ E′, so by the minimality of E and E′ among grounded extensions, E \ E′ ≠ ∅. Now E = Λ_{ω}(S, E), E′ = Λ_{ω}(S, E′), and S = Λ_{0}(S, E) = Λ_{0}(S, E′), so there is a least α ≥ 0 such that Λ_{α+1}(S, E) ≠ Λ_{α+1}(S, E′) but Λ_{α}(S, E) = Λ_{α}(S, E′). Without loss of generality, suppose e ∈ Λ_{α+1}(S, E) \ Λ_{α+1}(S, E′). Then there is some f ∈ Λ_{α} with f ⇒ A \\ B ∥− C, A ⊆ Λ_{α}, E ⊆ \overline{B}, and e ∈ C. Since e ∉ Λ_{α+1}(S, E′), there must be some g ∈ E′ ∩ B, so f is invalid in E′. This contradicts the previous conclusion that since f is valid in E, either f ∉ E′ or f is valid in E′. Hence E must be strongly present validity optimal in AExts(S). □

7. Conclusion

This paper presented elements of a mathematical theory of nonmonotonic reasoning based on concepts chosen to isolate the fundamental structures of the subject rather than to exhibit a conventional logical appearance. The approach taken here makes no special assumptions about the makeup of minds, but instead interprets given structures naturalistically, identifying reasons and their conclusions by the roles they play in the makeup of psychological states. It avoids special assumptions about how minds realize or compute these roles, so encompassing the computationally trivial activities of reason maintenance systems as well as the unbounded reasoning powers of ideal rational agents, and treats nonmonotonic reasoning as applicable to all sorts of mental attitudes, not as forms of reasoning specific to or justified only for beliefs, thus sidestepping the artificial consistency requirements attendant in logical encodings that limit reasoning about conflicting information or attitudes. The resulting theory thus exhibits the essential properties of traditional logical theories of nonmonotonic reasoning, but makes optional the more specific (or dubious) properties of the logical theories.

By avoiding the unnecessary concomitants of logical encodings of reasoning, the approach here applies directly to a wide variety of psychological structures. While the particular formulation presented here may not adequately serve the analysis of all interesting psychological structures, I believe it provides a good basis for studying an important range of questions, and that many further investigations will require only additions and refinements to the concepts presented here rather than wholesale replacement.

The formulation of ideas presented here arose through the deliberate pursuit of a mathematical understanding of the subject, and through deliberate practice of the essentially mathematical methodology of rational psychology sketched in the introduction and at somewhat greater length in (Doyle, 1983d). Rational psychology offers benefits to all of artificial intelligence and the cognitive sciences, not just to the theory of nonmonotonic reasoning. The preceding development exhibits some of the benefits of this approach, and I hope the reader will have come to agree on the merits of this project, even if unsatisfied with the specific formulations presented above.

Peregrinus expectavi pedes meos in cymbalis. S. Prokofiev, Alexander Nevsky

Acknowledgements

Preparation of this paper was supported in part by the USAF Rome Laboratory and ARPA under contract F30602-91-C-0018, and by National Institutes of Health Grant No. R01 LM04493 from the National Library of Medicine. The author gratefully acknowledges this support, and has also benefited over the years from the invaluable advice and encouragement of Joseph Schatz, Gerald Sussman, Dana Scott, and Richmond Thomason, as well as the productive environments of MIT, Stanford, and Carnegie Mellon University.

References

Abelson, H. (1978). Towards a theory of local and global in computation. Theoretical Computer Science, 6, 41–67.

de Kleer, J., Doyle, J., Steele, G. L. Jr., & Sussman, G. J. (1977). Amord: Explicit control of reasoning. In Proceedings of the ACM Symposium on Artificial Intelligence and Programming Languages, pp. 116–125.

Doyle, J. (1976). The use of dependency relationships in the control of reasoning. Tech. rep. Working Paper 133, MIT AI Laboratory.

Doyle, J. (1979). A truth maintenance system. Artificial Intelligence, 12 (2), 231–272.

Doyle, J. (1980). A model for deliberation, action, and introspection. Ai-tr 581, Massachusetts Institute of Technology, Artificial Intelligence Laboratory, 545 Technology Square, Cambridge, MA, 02139.

Doyle, J. (1983a). Admissible state semantics for representational systems. IEEE Computer, 16 (10), 119–123.

Doyle, J. (1983b). A society of mind: Multiple perspectives, reasoned assumptions, and virtual copies. In Proceedings of the Eighth International Joint Conference on Artificial Intelligence, pp. 309–314.

Doyle, J. (1983c). Some theories of reasoned assumptions: An essay in rational psychology. Tech. rep. 83-125, Department of Computer Science, Carnegie Mellon University, Pittsburgh, PA.

Doyle, J. (1983d). What is rational psychology? toward a modern mental philosophy. AI Magazine, 4 (3), 50–53.

Doyle, J. (1985). Circumscription and implicit definability. Journal of Automated Reasoning, 1, 391–405.

Doyle, J. (1988). Artificial intelligence and rational self-government. Tech. rep. CS-88-124, Carnegie-Mellon University Computer Science Department.

Doyle, J. (1989). Constructive belief and rational representation. Computational Intelligence, 5 (1), 1–11.

Doyle, J. (1992). Reason maintenance and belief revision: Foundations vs. coherence theories. In Gärdenfors, P. (Ed.), Belief Revision, pp. 29–51. Cambridge University Press, Cambridge.

Doyle, J., & Wellman, M. P. (1990). Rational distributed reason maintenance for planning and replanning of large-scale activities. In Sycara, K. (Ed.), Proceedings of the DARPA Workshop on Planning and Scheduling, pp. 28–36 San Mateo, CA. Morgan Kaufmann.

Doyle, J., & Wellman, M. P. (1991). Impediments to universal preference-based default theories. Artificial Intelligence, 49 (1-3), 97–128.

Fahlman, S. E. (1979). NETL: A System for Representing and Using Real-World Knowledge. The MIT Press, Cambridge, MA.

Gärdenfors, P. (1990). The dynamics of belief systems: Foundations vs. coherence theories. Revue Internationale de Philosophie, 172, 24–46.

Gazzaniga, M. S. (1985). The Social Brain: Discovering the Networks of the Mind. Basic Books, New York.

Ginsberg, M. L. (1991). The computational value of nonmonotonic reasoning. In Allen, J., Fikes, R., & Sandewall, E. (Eds.), Proceedings of the Second International Conference on Principles of Knowledge Representation and Reasoning, pp. 262–268 San Mateo, CA. Morgan Kaufmann.

Harman, G. (1986). Change in View: Principles of Reasoning. MIT Press, Cambridge, MA.

James, W. (1892). Psychology. Henry Holt & Co., New York.

Konolige, K. (1985). Belief and incompleteness. In Hobbs, J. R., & Moore, R. C. (Eds.), Formal Theories of the Common-Sense World, pp. 359–403. Ablex, Norwood.

Makinson, D., & Gärdenfors, P. (1991). Relations between the logic of theory change and the nonmonotonic logic. In Fuhrmann, A., & Morreau, M. (Eds.), The Logic of Theory Change, pp. 185–205. Springer-Verlag, Berlin.

McCarthy, J., & Hayes, P. J. (1969). Some philosophical problems from the standpoint of artificial intelligence. In Meltzer, B., & Michie, D. (Eds.), Machine Intelligence 4, pp. 463–502. Edinburgh University Press.

McCarthy, J. (1977). Epistemological problems of artificial intelligence. In Proceedings of the Fifth International Joint Conference on Artificial Intelligence, pp. 1038–1044.

McCarthy, J. (1980). Circumscription — a form of non-monotonic reasoning. Artificial Intelligence, 13 (1), 27–38.

McDermott, D. (1978). Planning and acting. Cognitive Science, 2, 71–109.

McDermott, D., & Doyle, J. (1980). Non-monotonic logic—I. Artificial Intelligence, 13, 41–72.

Miller, G. A. (1986). Dismembering cognition. In Hulse, S. H., & Green, Jr., B. F. (Eds.), One Hundred Years of Psychological Research in America, pp. 277–298. Johns Hopkins University Press, Baltimore.

Minsky, M. (1965). Matter, mind, and models. In Proceedings of the IFIP Congress, pp. 45–49.

Minsky, M. (1980). K-lines: a theory of memory. Cognitive Science, 4, 117–133.

Reiter, R. (1980). A logic for default reasoning. Artificial Intelligence, 13, 81–132.

Sandewall, E. (1972). An approach to the frame problem, and its implementation. In Machine Intelligence 7, pp. 195–204. University of Edinburgh Press.

Scott, D. S. (1982). Domains for denotational semantics. In Nielsen, M., & Schmidt, E. M. (Eds.), Automata, Languages, and Programming: Ninth Colloquium, Vol. 140 of Lecture Notes in Computer Science, pp. 577–613 Berlin. Springer-Verlag.

Sussman, G. J., Winograd, T., & Charniak, E. (1971). Micro-planner reference manual, (revised). Aim 203A, Massachusetts Institute of Technology, Artificial Intelligence Laboratory, 545 Technology Square, Cambridge, MA, 02139.

Touretzky, D. S. (1986). The Mathematics of Inheritance Systems. Morgan Kaufman, Los Altos, CA.

Truesdell, C. (1958). Recent advances in rational mechanics. Science, 127, 729–739.

Truesdell, C. (1977). A First Course in Rational Continuum Mechanics, Vol. 1. Academic Press, New York.