A General Framework for Reasoning about Inconsistency

1 Introduction

Inconsistency management has been intensely studied in various parts of AI, often in slightly disguised form [Poole, 1985; G. Pinkas, 1992; Rescher and Manor, 1970; Gardenfors, 1988]. For example, default logics [Reiter, 1980] use syntax to distinguish between strict facts and default rules, and identify different extensions of the default logic as potential ways of "making sense" of seemingly conflicting information. Likewise, inheritance networks [Touretzkey, 1984] define extensions based on analyzing paths in the network and using notions of specificity to resolve conflicts. Argumentation frameworks [Dung, 1995] study different ways in which an argument for or against a proposition can be made, and then determine which arguments defeat which other arguments in an effort to decide what can be reasonably concluded. All these excellent works provide an a priori conflict resolution mechanism. A user who uses a system based on these papers is more or less committed to the semantics implemented in the system, and has little say in the matter (besides which most users querying KBs are unlikely to be experts in even classical logic, let alone default logics and argumentation methods).

Leila Amgoud

IRIT - CNRS

118, route de Narbonne, 31062 Toulouse Cedex 9, France amgoud@irit.fr

The aims of the paper are:

1. to propose a unified framework for reasoning about inconsistency, which captures existing approaches as a special case and provides an easy basis for comparison.
2. to apply the framework using any logic (monotonic or nonmonotonic), including ones for which inconsistency management has not been studied before (e.g. temporal, probabilistic logics).
3. to allow end-users to bring their domain knowledge to bear, allowing them to voice an opinion on what works for them, not what a system manager decided was right for them., in other words, to take into account the preferences of the end-user.
4. to propose efficient algorithms for computing the preferred options.

We do this by building upon Dana Scott's celebrated notions of an abstract logic. We start with a simple example to illustrate why conflicts can often end up being resolved in different ways by human beings, and why it is important to allow end-users to bring their knowledge to bear when a system resolves conflicts.

Example 1 (Salary example) Suppose a university payroll system says that John's salary is 50K, while the university personnel database says it is 60K. In addition, there may be an axiom that says that everyone has exactly one salary. One simple way to model this is via the theory, denoted salbase , below.

salbase is obviously inconsistent. Suppose ( 3) is definitely known to be true. Then a bank manager considering John for a loan may choose the 50K number to determine a maximal loan amount that John qualifies for. But a national tax agency may use the 60K figure to send John a letter asking him why he underpaid his taxes.

Neither the bank manager nor the tax officer is making any attempt to find out the truth (thus far) - however, both of them are making different decisions based on the same facts.

The rest of this paper proceeds as follows. In Section 2, we recall Scott's notion of what a logic is [Scott, 1982]. Then, in Section 3, we define our general framework for reasoning about inconsistency for any Scott logic. Section 4 shows how to adapt the general framework to the particular case of inconsistent bases. In section 5, we show how existing works can be retrieved in our general framework. Section 6 presents some examples of how the general framework can be applied in other logics such as temporal and probabilistic logics. In Section 7, we develop algorithms to compute optimal options based on various types of monotonicity assumptions about the objective function. Note that due to lack of space, we only include a few proofs - the full version of this paper will contain all proofs.

2 Scott's Abstract Consequence Operation

Dana Scott [Scott, 1982] defines an abstract logic to consist of a set L (whose members are called well-formed formulas) and a consequence operator CN. CN is any function from 2L (the powerset of L) to 2L (intuitively, CN(X) returns the set of formulas that are logical consequences of X according to the logic in question) that satisfies the following axioms:

Expansion X ⊆ CN(X).

Idempotence CN(CN(X)) = CN(X).

Monotonicity X ⊆ Y ⇒ CN(X) ⊆ CN(Y ).

Coherence CN(∅) ̸= L.

It is easy to see that most well known monotonic logics (such as propositional logic [Shoenfield, 1967], first order logic [Shoenfield, 1967], modal logic, temporal logic, fuzzy logic, probabilistic logic [Bacchus, 1990], etc.) can be viewed as a special case of Scott's notion of an abstract logic. The nonmonotonic logics introduced in AI do not satisfy the monotonicity axiom, though Marek et. al. [Marek et al., 1990] have defined the notion of non-monotone rule systems that extend Scott's ideas to non-monotonic logics by dropping the Monotonicity Axiom above. In the remainder of this paper, we drop monotonicity axiom. Once (L, CN) are fixed, we can define a notion of consistency as follows:

Definition 1 (Consistency) Let X ⊆ L. X is consistent in logic (L, CN) iff CN(X) ̸= L.

This says that X is consistent iff its set of consequences is not the set of all well formed formulas. Note that the coherence requirement characterizing CN forces ∅ to always be consistent - this is reasonable for pretty much any reasonable logic as saying nothing should intuitively be consistent.

3 A general framework for handling inconsistency

This section proposes a general framework for handling inconsistency under any logic. Reasoning with inconsistent knowledge bases is a process which follows three steps:

1. Constructing consistent subbases,
2. Selecting among all the subbases the preferred ones, called preferred subbases,
3. Applying classical entailment on a choice of the preferred subbases.

Throughout the rest of this paper, we assume that we have an arbitrary, but fixed (monotonic or non-monotonic) logic (L, CN).

The basic idea behind our framework is to construct what we call options, and then to define a preference relation on these options. The preferred options are intended to support the conclusions to be drawn from the inconsistent knowledge base. Intuitively, an option is a set of formulas that is both consistent and closed w.r.t. the consequence in logic (L, CN).

Definition 2 (Options) An option is any set O of elements of L such that:

• O is consistent.
• O is closed, i.e. O = CN(O).

Let Opt(L) be the set of all options that can be built from (L, CN).

Les us illustrate the above concept.

Example 2 Let L be a propositional language, and let K ⊆ L be the knowledge base K = {a, a → b, ¬b}. The following options, for instance, can be built from K: O1 = CN({a}), O2 = CN({¬b}), O3 = CN({a → b}), O4 = CN({a, a → b}), O5 = CN({a, ¬b}), O6 = CN({a, b}).

The framework for reasoning about inconsistency has three components: a set of all options that can be built from the considered logic, a preference relation between the options, and an entailment mechanism.

Definition 3 (General framework) Let (L, CN) be a fixed logic. A general framework for reasoning about inconsistency in the logic (L, CN) is a triple 〈Opt(L),⪰, |∼〉 such that:

• Opt(L) is the set of options built from (L, CN)
• ⪰⊆ Opt(L)×Opt(L). ⪰ is a partial (or total) preorder, that is, it is reflexive and transitive.
• |∼ : 2Opt(L) →Opt(L) is an entailment mechanism.

The second important concept of the above general framework is the preference relation ⪰ between options. Indeed, O1 ⪰ O2 means that the option O1 is at least as preferred as O2. This relation captures the idea that some options are better than others because, for instance, the user has decided that, or because those preferred options satisfy the requirements imposed by the developer of a conflict management system. For instance, in Example 1, the user chooses certain options (e.g. the options where the salary is minimal or where the salary is maximal based on his needs). In most approaches for handling inconsistency, maximal consistent subsets of the inconsistent knowledge base have an important role. However, if we consider a KB such as K = {(a ∧ b); a → c; b → ¬c}, there are three maximal consistent subsets. One of these is MCS1 = {a → c; b → ¬c}. If we represent this KB as the default theory Δ = (W,D) where W = ∅ and D = { :(a∧b) (a∧b) ; :a→c a→c ; :b→¬c b→¬c }, we would get three extensions corresponding to the three maximal consistent subsets. However, one could argue that MCS1 (and the extension corresponding to it) are too weak - we could have included either a or b by weakening the formula (a ∧ b) instead of dropping it altogether.

The third component of the framework is a mechanism for selecting the inferences to be drawn from the knowledge base. In our framework, the set of inferences is itself an option. Thus, it should be consistent. This requirement is of great importance, since it ensures that the framework delivers safe conclusions.

The set of inferences is generally computed from the different preferred options. Let O⪰ be the set of all preferred options, i.e. O⪰ = {Oi ∈ Opt(L) | ∄Oj ∈ Opt(L) with Oj ⪰ Oi}. Different entailment mechanisms can be defined for selecting the inferences to be drawn. Here are some examples of such mechanisms.

Definition 4 Let 〈Opt(L),⪰, |∼〉 be a framework, and O⪰ the set of its preferred options. Let ψ be an element of L.

Universal criterion: L |∼ ψ iff ψ ∈ Oi, ∀Oi ∈ O⪰. ψ is called a universal consequence of L.

Argumentative criterion: L |∼ ψ iff ∃Oi ∈ O⪰ such that ψ ∈ Oi, and ∄Oj ∈ O⪰ such that ¬ψ ∈ Oj . ψ is called an argumentative consequence of L.

We can show that the set of inferences made using the universal criterion is itself an option of the language L, thus it is an entailment mechanism. Moreover, it is included in every preferred option.

Proposition 1 Let 〈Opt(L),⪰, |∼〉 be a framework built from a monotonic logic (L, CN).

• The set {ψ| ψ is a universal consequence of L} is an option of Opt(L).
• ∀Oi ∈ O⪰, {ψ| ψ is a universal conseq. of L} ⊆Oi.

Proof (Sketch) Let C = {ψ| ψ is a universal consequence of L}. By definition, any element in C belongs to all the options in O⪰. Consequently, C ⊆ Oi, ∀Oi ∈ O⪰.

As each Oi ∈ O⪰ is an option, Oi is consistent. Thus, C (which is a subset of Oi) is also consistent. Similarly, since C ⊆ Oi, thus CN(C) ⊆ Oi as well, ∀Oi ∈ O⪰. Consequently, CN(C) ⊆ C (according to the above definition of universal consequences). Thus, C is closed, and consequently it is an option.

Similarly, we can show that the set of argumentative consequences is an option. Thus, it is a valid entailment mechanism.

Proposition 2 Let 〈Opt(L),⪰, |∼〉 be a framework built from a monotonic logic (L, CN). The set {ψ| ψ is an argumentative consequence of L} is an option of Opt(L).

However, the following criterion is not a valid entailment mechanism since the set of consequences returned by it may be inconsistent, thus it is not an option.

Example 3 L |∼ ψ iff ∃Oi ∈ O⪰ such that ψ ∈ Oi.

4 Optimal Options that Handle Inconsistency

In the preceding section, we have developed the concepts of an option and a preferred option for any logic (L, CN). However, this has been defined in a way that is independent of a knowledge base K. This section shows how to associate a set of preferred options with an inconsistent knowledge base K.

Definition 5 We say an option O handles K iff there is a subset K′ ⊆ K such that O = CN(K′ ). Let Base be a function that returns for any option O, the subbase K′ . Thus, Base(O) = K′ .

Intuitively, an option handles K iff it is the closure of some subset of K. Clearly, such a subset K′ must be consistent because O is consistent (by virtue of being an option) and as O = CN(K′ ).

Example 4 (Handling inconsistent default logic theories)

Let us consider default logic as our base logic, and suppose we consider the default theory Δ = (W, D) where W = {p} and D = { :p ¬p }. Most researchers in default logic would consider this theory to be inconsistent as it has no extension. However, it has two valid options: Δ1 = (∅, ∅) and Δ2 = ({p}, ∅). A user may specify a preference relation that prefers Δ2. This shows how our framework can be applied to default logic.

Definition 6 Suppose (Opt(L),⪰, |∼) is a general framework for reasoning about inconsistency in logic (L, CN) and suppose K is an inconsistent knowledge base. An optimal option for K is any member O ∈ Opt(L) such that:

• O handles K and
• there is no other option O′ ∈ Opt(L) that handles K such that O′ ⪰ O.

What this definition says is that when reasoning about an inconsistent knowledge base K, we always look at the set of optimal options that handle K.

Example 5 Let us return to Example 1. Suppose we use O1 = {(1), (2)},O2 = {(1), (3)},O3 = {(2), (3)}}. Of course, we assume all of these options are also closed under usual first order consequence. First, let us say that these three options are preferred to all other options in the language.

• Suppose the score sc(Oi) of option Oi is the sum of the multiset {S|sal(John, S) ∈ Oi}. In this case, the score of O1 is 50K, that of O2 is 110K, and that of O3 = 60K. We could now say that Oi ⪰ Oj if sc(Oi) ≤ sc(Oj). In this case, the only option that handles K is O1 which corresponds to the bank manager's viewpoint.
• On the other hand, suppose we say that Oi ⪰ Oj iff sc(Oi) ≥ sc(Oj). In this case, the only optimal option that handles K is O2 - this corresponds to the view that the rule saying everyone has only one salary is wrong (perhaps the database has John being paid out of two projects simultaneously and 50K of his salary is charged to one project and 60K to another).
• Now consider the case where we change our scoring method and say that sc(Oi) = min{S | sal(John, S) ∈ Oi}. In this case, sc(O1) = 50K, sc(O2) = 60K, sc(O3) = 50K. Let us suppose that the preference relation says that Oi ⪰ Oj iff sc(Oi) ≥ sc(Oj). Then the only optimal option is O2 which corresponds exactly to the tax agency's viewpoint.

Thus, we see that our general framework for optimally handling inconsistency is very powerful - it can be used to handle inconsistencies in different ways based upon how the preference relation between options is defined.

5 Link with existing approaches

Two kinds of approaches have been proposed in the literature for solving the problem of inconsistency. The first one consists of revising the knowledge base and restoring its consistency. The second approach accepts inconsistency and copes with it. The first approach initiated in [Rescher and Manor, 1970] proposes to give up some formulas of the knowledge base in order to get one or several consistent subbases of the original base. Then plausible conclusions may be obtained by applying classical entailment on these subbases. In what follows, we consider the case of propositional bases. When the knowledge base is flat, i.e. its formulas are not weighted, maximal consistent subbases are built.

Let K be a knowledge base that may be inconsistent, and S = {S1, . . ., Sn} its set of maximal (for set inclusion) consistent subbases. We can show that these subbases correspond to the preferred options of the above framework when the preference relation ⪰ between options is monotonic. Let us first define that notion of monotonicity.

Definition 7 (Monotonic relation) The relation ⪰ is said monotonic iff for any X, Y ⊆ L, if X ⊆ Y , then Y ⪰ X. ⪰ is said anti-monotonic iff, if X ⊆ Y , then X ⪰ Y .

Proposition 3 Let 〈Opt(L),⪰, |∼〉 be a framework such that ⪰ is monotonic. Let K be an inconsistent knowledge base, and O⪰ be the set of preferred/optimal options for K.

• ∀Si, ∃ O ∈O⪰, such that O = CN(Si).
• ∀Oi ∈ O⪰, ∃ S such that Oi = CN(S).

In the case of prioritized knowledge bases, Brewka has proposed in [Brewka, 1989] a definition of the preferred subbases. The basic idea behind those bases is to take as many important information into account as possible. In this context, a knowledge base K is supposed to be stratified into K1, . . ., Kn (K = K1∪. . .∪Kn) such that the formulas in the same strata are equally preferred, whereas formulas in a strata Ki are preferred to formulas in Kj with i < j.

Definition 8 Let K = K1 ∪ . . . ∪ Kn be a knowledge base. S = S1 ∪ . . . ∪ Sn is a preferred subbase of K if and only if ∀j = 1, . . . , n, S1 ∪ . . . ∪ Sj is a maximal (for set-inclusion) consistent subbase of K1 ∪ . . . ∪ Kj .

INCL(K) denotes the set of preferred subbases of K.

We show that in order to capture the results of the above approach, one needs to define the appropriate preference relation between options.

Definition 9 Let K be an inconsistent knowledge base, and OK be the set of all options that handle K. Let O1, O2 ∈ OK. O1 ⪰O2 iff Base(O1) ∈ INCL(K), and Base(O2) /∈ INCL(K).

Proposition 4 Let 〈Opt(L),⪰, |∼〉 be a framework such that ⪰ is defined as in Definition 9. Let K be an inconsistent knowledge base, and O⪰ be the set of preferred/optimal options for K.

• ∀Si ∈ INCL(K), ∃ O ∈ O⪰, such that O = CN(Si).
• ∀Oi ∈ O⪰, ∃ S ∈ INCL(K) such that Oi = CN(S).

6 New applications of the framework

In this section we show through the two following examples that the above abstract framework can be used for reasoning about inconsistency using temporal logic and even probabilistic logic.

Example 6 Consider the temporal logic theory T. The © operator denotes the "next time instant" operator. Thus, the first rule says that if a is true at time t, b is true at time (t+1). Under standard temporal logic model theory, T is inconsistent.

We may choose to consider just three options: O1 = CN({ 4, 5}),O2 = CN({ 4, 6}),O3 = CN({ 5, 6}). Suppose now that we can associate a numeric score with each formula, describing the weight of the source that provided the formula. Let us say these scores are 3,1,2 respectively, and the weight of an option Oi is the sum of the scores of the formulas in T ∩ Oi. Oi ⪰ Oj iff the score of Oi is greater than or equal to the score of Oj. In this case, the best option is O2.

Example 7 Consider the probabilistic logic [Bacchus, 1990] theory T consisting of three formulas p : [0.3, 0.4], p : [0.44, 0.6], p : [0.41, 0.43]. Suppose we only consider options that assign a single non-empty probability interval to p. For two atoms A1 = p : [L,U] and A2 = p : [L′ ,U ′ ], let diff(A1,A2) = abs(L1 - L2) + abs(U1 - U2). Let us say that the score of an option O = {A} is given by KA′∈Tdiff(A,A′ ). Suppose we say that option Oi ⪰ Oj iff score(Oi) ≤ score(Oj). Intuitively, this means that we are preferring options that change the lower and upper bounds in T as little as possible. In this case, [0.3, 0.6] is a preferred option.

The reader may be tempted to think that given a K that is inconsistent, an optimal option may always exist because in the worst case, CN(∅) seems to be an option. However, this is not correct because we do not require that CN(∅) be in Opt(L).

7 Algorithms to Compute Optimal Options that Handle Inconsistency

In this section, we develop procedures to find optimal options for any logic (L, CN) under a varying set of assumptions. We first define what it means for a formula to be compatible with a given set of formulas.

Definition 10 Given a consistent set X ⊆ L and a formula F ∈ L, we say that F is compatible with X iff X ∪ {F} is consistent. We use the notation Comp(X) to denote the set of all formulas that are compatible with X.

We now develop an iterative fixpoint computational procedure to find an optimal option.

Definition 11 Suppose (L, CN) is a logic, K is a subset of L, and ⪰ is a preference relation on options. We define an operator ΓK associated with K that maps sets of options to sets of options as follows.

In other words, ΓK(X) works as follows:

• First, it picks a set Y in X to expand.
• It then finds an F ∈ Comp(Y ) ∩ K.
• It then closes Y ∪ {F} and adds this to the answer, i.e. into ΓK(X).

Clearly, the operator ΓK is monotone under inclusion - moreover, the repeated application of ΓK yields a fixpoint. This is defined as follows.

Proposition 5 Suppose (L, CN) is a logic and K is a subset of L. Then:

1. ΓK is monotonic.
2. ΓωK is a fixpoint of γK.
3. Every set in ΓωK is consistent.

Note that the least fixpoint of Γk is the empty set and not ΓωK because the latter starts its iteration not with the empty set, but with the set containing the empty set! Fortunately, we can make some concrete statements about ΓωK.

Proposition 6 Suppose (L, CN) is a logic, (Opt(L),⪰, |∼) is a general framework for handling inconsistency, and K is a set of wffs. O is an optimal option that handles K iff:

1. O ∈ Opt(L) ∩ ΓωK and
2. there is no O′ ∈ Opt(L) ∩ ΓωK such that O′ ⪰ O.

The above result suggests an immediate algorithm to find an optimal option for S regardless of whether the preference relation is monotonic or not.

procedure COO-Naive(L, CN, F , K, Opt(L), ⪰)

1. X = ΓωK; 2. X =X ∩ Opt(L);

1. Return any O ∈ X such that there is no O′ ∈ X such that O′ ⪰ O.

One reason for the inefficiency of COO-Naive is that it makes no assumptions about the preference relation. However, if the preference relation is known, for example, to be monotone or anti-monotone, then we can do better. COO-Anti below shows that when ⪰ is assumed to be anti-monotone, we can do better than COO-Naive.

procedure COO-Anti(L, CN, Opt(call), ⪰, K) 1. TODO = {CN(∅)} 2. SOL = {}; 3. while TODO ̸= ∅ do 4. Pick X ∈ TODO s.t. ̸ ∃Y ∈ TODO s.t. CN(Y ) ⪰ CN(X). 5. T ODO = T ODO - {X} 6. if X ∈ Opt(L) then 7. SOL = (SOL - {Y ∈ SOL | X ⪰ Y }) ∪ {X}; 8. else TODO = TODO ∪ { 9. CN(X ∪ {F}) | F ∈ Comp(X) ∩ K)}; 10. end-while

1. return any ⪰-preferred member of SOL.

Intuitively procedure COO-Anti generates ⊆-inclusion minimal closed and consistent subsets that are in Opt(L) using a bottom up procedure and then chooses the best ones. It starts by checking if CN(∅) is in Opt(L) - if so, it can be returned because of the anti-monotonicity of ⪰. Otherwise, it finds all formulas compatible with it and for each such formula, it finds the logical consequences. Whenever it finds an option that handles K, it adds it to SOL and deletes any option in SOL that is worse than it (according to ⪰). This procedure is continued.

Pruning occurs in step (8) of the algorithm where the antimonotonicity of ⪰ is exploited. Moreover, the algorithm proceeds in a greedy fashion, always choosing the best (or one of the best) sets from TODO to expand in step (4).

The reader may think that the first solution found by this bottom up procedure is optimal. Unfortunately, this may not be the case because anti-monotonicity merely states that O1 ⊆ O2 → O1 ⪰ O2. It is possible for O1 ⪰ O2 to hold even if O1 ̸⊆ O2 and hence, in the anti-monotonic case, one has to generate all ⊆-minimal options before deciding which one is the best.

Proposition 7 Suppose (L, CN) is a logic, (Opt(L),⪰, |∼) is a general framework for reasoning about inconsistency, and K is a set of wffs. Further, suppose ⪰ is anti-monotonic.

1. If there is an optimal option to handle K, then COOAnti(L, CN, Opt(L), ⪰, K) will return one.
2. If COO-Anti(L, CN, Opt(L),⪰,K) returnsO, thenO is an optimal option that handles K.

Just as in the case of anti-monotonic ⪰ preference relations, we can also improve on the COO-Naive algorithm when ⪰ is monotonic. The COO-Mon algorithm assumes monotonicity of ⪰ and works in a similar manner as for COO-Anti but starts top down and eliminates members of CN(K) instead of starting the iteration from the empty set. The Coo-Mon algorithm uses the notion of a deletion candidate.

Definition 12 Suppose (L, CN) is a logic and K is a set of wffs. A set Y ⊆ K is a deletion candidate for K iff

1. CN(K-Y ) ⊂ K and
2. CN(K-Y ) is consistent

1. and there is no set Y ′ ⊂ Y that satisfies the previous two conditions.

In other words, a deletion candidate for S is a wff F whose removal from S causes at least one formula to no longer be inferrable from S. We use the notation DelCand(X) to denote the set of all deletion candidates of a set X.

procedure COO-Mon(L, CN, Opt(L), ⪰, S, χ) 1. TODO = {CN(K)}; 2. SOL = {∅}; 3. while TODO ̸= ∅ do 4. Pick X ∈ TODO s.t. ̸ ∃Y ∈ TODO Y ⪰ X; 5. T ODO = T ODO - {X}; 6. If CN(X) ∈ Opt(L) ∧ CN(X) ̸= L then 7. SOL = (SOL - ({ Y ∈ SOL | CN(X) ⪰ Y })) ∪ {CN(X)}; 8. else 9. TODO = TODO ∪ DelCand(X); 10. end while 11. return ⪰-preferred members of SOL.

The COO-Mon algorithm works as follows. It starts with CN(K) and checks if it is consistent. If so, it adds it to SOL and halts. Otherwise, it deletes every possible deletion candidate (minimal set of elements from K that restore consistency). If any of the resulting options are valid options, then the best one according to ⪰ is returned. Otherwise, a set from TODO is selected and further deletion candidates are found. This is repeated until we either find an optimal option that handles K or there is none.

Proposition 8 Suppose (L, CN) is a logic, (Opt(L),⪰, |∼) is a general framework for reasoning about inconsistency, and K is a set of wffs. Further, suppose ⪰ is monotonic.

1. If there is an optimal option to handle K, then COOAnti(L, CN, Opt(call), ⪰, K) will return one.
2. If COO-Anti(L, CN, Opt(call),⪰,K) returnsO, thenO is an optimal option that handles K.

8 Conclusion

In the literature, there are several proposals for handling inconsistency in knowledge bases. These proposals differ in i) the logic to which they apply, and (ii) the criteria used to draw inferences.

In this paper, we have proposed a general and unified framework for reasoning about inconsistency in a wide variety of logics. Indeed, the proposed framework is based on an abstract logic as suggested by Scott in [Scott, 1982]. The framework has three basic components: a set of options that are consistent and closed subsets of well-founded formulas of the logic, a preference relation between the options and en entailment mechanism. The preference relation between options is a general notion. It may capture the requirements used in the literature, such as the maximality, but also other criteria maybe provided by the user for choosing among the options. We have shown that by defining an appropriate preference relation on options, we can capture several existing works such as the subbases defined in [Rescher and Manor, 1970], default logic and Brewkas subtheories. The third component of the framework consists of an entailment mechanism that allows the selection of the inferences to be drawn from the knowledge base. Such mechanism should return an option. This enforces the system to make safe inferences. We have also shown through examples how this abstract framework can be used in different logics such as temporal and probabilistic logics. Another important contribution of the paper is the set of algorithms provided for computing most preferred options.

Acknowledgments. This work was partly supported by AFOSR grants FA95500610405 and FA95500510298, ARO grant DAAD190310202 and by the Joint Institute for Knowledge Discovery.