Ann Math Artif Intell manuscript No. (will be inserted by the editor)

A Series of Revisions of David Poole’s Specificity

Claus-Peter Wirth · Frieder Stolzenburg

Received: date / Accepted: date

Abstract In the middle of the 1980s, David Poole introduced a semantic, model-theoretic notion of specificity to the artificial-intelligence community. Since then it has found further applications in non-monotonic reasoning, in particular in defeasible reasoning. Poole tried to approximate the intuitive human concept of specificity, which seems to be essential for reasoning in everyday life with its partial and inconsistent information. His notion, however, turns out to be intricate and problematic, which — as we show — can be overcome to some extent by a closer approximation of the intuitive human concept of specificity. Besides the intuitive advantages of our novel specificity orderings over Poole’s specificity relation in the classical examples of the literature, we also report some hard mathematical facts: Contrary to what was claimed before, we show that Poole’s relation is not transitive in general. The first of our specificity orderings (CP1) captures Poole’s original intuition as close as we could get after the correction of its technical flaws. The second one (CP2) is a variation of CP1 and presents a step toward similar notions that may eventually solve the intractability problem of Poole-style specificity relations. The present means toward deciding our novel specificity relations, however, show only slight improvements over the known ones for Poole’s relation; therefore, we suggest a more efficient workaround for applications in practice.

Keywords artificial intelligence · non-monotonic reasoning · defeasible reasoning · specificity · positive-conditional specification 1 Introduction

Claus-Peter Wirth E-mail: wirth@logic.at Tel.: +49-160-2173333 Frieder Stolzenburg E-mail: fstolzenburg@hs-harz.de Tel.: +49-3943-659333 Harz University of Applied Sciences Dept. of Automation and Computer Sciences Friedrichstr. 57–59 38855 Wernigerode, Germany Fax: +49-3943-659399

A possible explanation of how humans manage to interact with reality — in spite of the fact that their information on the world is partial and inconsistent — mainly consists of the following two points:

1. Humans use a certain amount of rules for default reasoning and are aware that some arguments relying on these rules may be defeasible.

2. In case of the frequent conflicting or even contradictory results of their reasoning, they prefer more specific arguments to less specific ones.

An intuitive concept of specificity plays an essential rôle in this explanation, which is interesting because it seems to be highly successful in practice, even if it were just an epiphenomenon providing an ex eventu explanation of human behavior.

On the long way approaching the proven intuitive human concept of specificity, the first milestone marks the development of a semantic, model-theoretic notion of specificity having passed first tests of its usefulness and empirical validity. Indeed, at least as the first step, a semantic, model-theoretic notion will probably offer a broader and better basis for applications in systems for common-sense reasoning than notions that depend on peculiarities of special calculi or even on extra-logical procedures. This holds in particular if the results of these systems are to be accepted by humans.

David Poole has sketched such a notion as a binary relation on arguments and evaluated its intuitive validity with some examples in (?). Poole’s notion of specificity was given a more appropriate formalization in (?). The properties of this formalization were examined in detail in (?).

In §§ ?? and ??, we recall basic notions and notation and the elementary motivating examples.

In §??, we present a detailed analysis of the reasons behind our intuition that Poole’s specificity is a first step on the right way.

We expect that the results of this detailed analysis will carry us even beyond this paper to future improved concepts of specificity, especially w.r.t. efficiency, but also w.r.t. intuitive adequacy. We hope that the closer we get to human intuition, the more efficiently our concepts can be implemented, simply because they seem to run so well on the human hardware, which — by all that we know today — is pretty slow.

In §??, we specify formal requirements on any reasonably conceivable relation of specificity.

In §??, we disambiguate Poole’s specificity relation from slightly improved versions, such as the one in (?), and introduce a novel specificity ordering (CP1), a correction of Poole’s specificity in the sense that it removes a crucial shortcoming of Poole’s original relation (P1) and its slight improvements (P2, P3), namely their lack of transitivity.

In §??, we present several examples that are to convince the carefully contemplating reader of the superiority of our novel specificity relation CP1 w.r.t. human intuition.

In §??, we discuss efficiency issues. We introduce a further novel specificity ordering (CP2) (a variation of CP1) as a first step toward similar notions that may finally solve the intractability problem of Poole-style specificity relations. The present means toward deciding our novel specificity relations, however, show only slight improvements over the known ones for Poole’s relation; therefore, we suggest a more efficient workaround for applications in practice.

In §??, we draw some first conclusions.

2 Basic Notions and Notation

Definition 1 (Term, Atom) A term is inductively defined to be either a function symbol applied to a (possibly empty) list of terms or a symbol for a free variable. An atom consists of a predicate symbol applied to a (possibly empty) list of terms.

In what follows, we will mainly use nullary function symbols (“constants”), such as tweety, and singulary predicate symbols, such as bird, forming atoms such as bird(tweety), which states that tweety is a bird.

2.1 Specifying Rules and their Theories

For the remainder of this paper, let us narrow the general logical setting of specificity down to the concrete framework of defeasible logic with the restrictions of positive-conditional specification with an inactive negation symbol, as found e.g. in (?) and (?).

In effect, these restrictions give us the standard “definite rules” of positive-conditional specification (or Horn-clause logic). Positive-conditional specification differs from logic programming in Prolog (cf. e.g. (?), (?)) insofar as termination issues and the order of the definite clauses are irrelevant for the semantics, and insofar as there is no cut predicate (‘!’) and no negation as failure.

Such definite rules are implications of the following form: The conclusion is an atom; the condition is a (possibly empty) conjunction of (positive) atoms which may contain extra variables (i.e. free variables not occurring in the conclusion). This is can be seen as quantifier-free first-order logic with specifications restricted to implications of the mentioned form.

We ask the reader not to get confused on the mentioned effective form of our rules by the fact that — in place of the atoms — literals resulting from an inactive negation symbol are actually admitted in the rules of Definition ?? (see below). This special form of negation is standard in defeasible logic for convenience in the application context (such as an argumentation framework). In this paper, however, we can consider this negation just as a form of syntactic sugar (cf. Definition ??, Remark ??).

Definition 2 (Literal, Rule) A literal is an atom, possibly prefixed with the symbol “¬” for negation. A rule is a literal, but possibly suffixed with a reverse implication symbol “⇐” that is followed by a conjunction of literals, consisting of one literal at least.

Definition 3 (Theory, Derivation) Let Π be a set of rules. The theory of Π is the set �_{Π} inductively defined to contain

– all instances of literals from Π and

– all literals L for which there is a conjunction C of literals from �_{Π} such that L ⇐ C is an instance of a rule in Π.

For �⊆ �_{Π} , we also say that Π derives �, and write Π ⊢ �.

2.2 Secondary Aspects of our Logic

Remark 1 (Negation Symbol “¬”) The negation symbol “¬”, which occurs in Definition ?? and which seemingly gets us beyond the definite rules of positive-conditional specifications by admitting literals instead of just atoms, does not have any effect on the derivations and theories considered in this paper (cf. Definition ??). For instance, the literal ¬flies(edna) may actually be considered as the atom resulting from application of the predicate ¬flies to the constant symbol edna.

On the other hand, if we write an atom A as A= true, and a negated atom ¬A as the equational atom A= false, for the data type Boolean given by the constructors true and false, then the rules of our specification can be seen as positive-conditional equational specifications in the framework for positive/negative-conditional equational specification found in (?), and (?, ?; ?).

In the application context, of course, the literals ¬flies(edna) and flies(edna) will be considered to be contradictory (cf. Definition ??), but this is a secondary and non-essential notion built on top of our derivations and theories, which do not rely on this notion.

As a consequence, none of the results in this paper relies on this special negation symbol. To the contrary, in the weakness of our logical theories we see an indication for the generality of our results (cf. Remark ??).

To distinguish the inactive negation here from negation as failure and from any other form of negation playing an active rôle in derivation, the symbol “∼” is sometimes used in the literature of defeasible logic in place of our more standard symbol “¬”.

Definition 4 (Contradictory Sets of Rules) A set of rules Π is called contradictory if there is an atom A such that Π ⊢ {A,¬A}; otherwise Π is non-contradictory.

Remark 2 (Weakness of Our Logical Theories) On the one hand, {A, ¬A⇐ A} is contradictory according to Definitions ?? and ??. On the other hand, {A⇐ ¬A, ¬A⇐ A} is non-contradictory according to these definitions, although we can infer both A and ¬A from {A⇐ ¬A, ¬A⇐ A} in classical (i.e. two-valued) logic. For the case of our very limited formal language, our notions of consequence and contradiction are equivalent both to intuitionistic logic and to the three-valued logic where ¬ and ∧ are given as usual, but (following neither Kleene nor �ukasiewicz) implication has to be defined via (A⇐ TRUE)= A, (A⇐ FALSE)= TRUE, (A⇐ UNDEF)= TRUE.

2.3 Global Parameters for the Given Specification

Throughout this paper, we will assume a set of literals Π^{F} and two sets of rules Π^{G}, Δ (cf. Definition ??) to be given:

– A set Π^{F} of literals meant to describe the \underline{f}acts of the concrete situation under consideration,

– a set Π^{G} of \underline{g}eneral rules meant to hold in all possible worlds,^{1} and

– a set Δ of \underline{d}efeasible (or default) rules meant to hold in most situations.

The set Π := Π^{F}∪ Π^{G} is the set of strict rules that — contrary to the defeasible rules — are considered to be safe and are not doubted in the concrete situation.

2.4 Formalization of Arguments

Whether a rule is a strict one from Π or a defeasible one from Δ has no effect on theories and derivations (cf. Definition ??). If a contradiction occurs, however, we will narrow the defeasible rules from Δ down to a subset A of its ground instances (i.e. instances without free variables) — such that no further instantiation can occur. Such a subset, together with the literal whose derivation is in focus, is called an argument. With implicit reference to the given sets of rules Π and Δ, the formal definition is as simple as follows.

Definition 5 ([Contradictory] [Minimal] Argument) (A ,L) is an argument if A is a set of ground instances of rules from Δ and A ∪Π ⊢ {L}. (A ,L) is a minimal argument if A is an argument, but (A′,L) is not an argument for any proper subset A′⊊ A . An argument (A ,L) is contradictory if A ∪ Π is a contradictory set of rules.

Remark 3 (Non-Ground Arguments) From a refined standpoint, what we actually need is not exactly a set A of ground instances, but just of the instances applied in the derivation. Then, however, we have to freeze the variables in A because they must not be instantiated in the derivation A ∪Π ⊢ {L}. We avoid this refinement here until we come to §??, because it does not play an essential rôle before and because we want to stay within the traditional framework as long as possible to facilitate a more direct comparison.

Remark 4 (Minimality and Non-Contradiction of Arguments) Some authors (cf. e.g. (?), (?)) require all arguments

1. to be minimal arguments, and
2. to be non-contradictory.

Because non-minimal as well as contradictory arguments often occur in practical situations, there is no use-oriented justification for any of these requirements.

For requirement 1 there is no conceptual justification, because the non-minimal arguments become inessential by our preference on specific arguments, in the sense that for every argument there must be a minimal sub-argument that is at least as specific, cf. Corollaries ??, ??, and ??. Because being contradictory is only a secondary aspect of our logic (cf. §??), there is no conceptual justification for requirement 2, either.

To obtain a more general setting in the comparison of arguments, we omit these restrictions in the context of this paper, where they turned out to be completely superfluous. In particular, the omission of these requirements has no effect on the results of this paper.

1 In the approach of (?), the set Π^{G} must not contain mere literals (without suffixed condition), also called presumptions. To obtain a more general setting, we omit this additional restriction in the context of this paper, simply because it is neither intuitive nor required for our framework here. For the actual occurrence of a literal in Π^{G}, see the discussion of Example ?? in §??.

2.5 Quasi-Orderings

We will use several binary relations comparing arguments according to their specificity. For any relation written as ≲_{N} (“being more or equivalently specific w.r.t. N”), we set

≳_{N} := { (X,Y)| Y ≲_{N} X }  (“less or equivalently specific”),
≈_{N} := ≲_{N}∩ ≳_{N}  (“equivalently specific”),
<_{N} := ≲_{N}\ ≳_{N}  (“properly more specific”),
≤_{N} := <_{N} ∪ { (X,X)| X is an argument }  (“more specific or equal”),
△_{N} := { (X,Y) X,Y are arguments with X ≴_{N} Y and X ≵_{N} Y } (“incomparable w.r.t. specificity”).

A quasi-ordering is a reflexive transitive relation. An (irreflexive) ordering is an irreflexive transitive relation. A reflexive ordering (also called: “partial ordering”) is an anti-symmetric quasi-ordering. An equivalence is a symmetric quasi-ordering.

Corollary 1 If ≲_{N} is a quasi-ordering, then ≈_{N} is an equivalence, <_{N} is an ordering, and ≤_{N} is a reflexive ordering.

3 Motivating Examples

For ease of distinction, we will use the special symbol “←” as a syntactic sugar in concrete examples of defeasible rules from Δ, instead of the symbol “⇐”, which — in our concrete examples — will be used only in strict rules.

Moreover, in our graphical illustrations we will indicate membership in Π^{F} by double underlining.

Example 1 (Example 1 of (?))

Π??^{F} := \{ \begin{matrix}bird(tweety), \\ emu(edna) \end{matrix}\} ,
Π??^{G} := \{ \begin{matrix}bird(x) ⇐ emu(x), \\ ¬flies(x) ⇐ emu(x) \end{matrix}\} ,
Δ?? := { flies(x) ← bird(x)},
A_{2} := { flies(edna) ← bird(edna)}.

¬flies(edna)  flies(edna)  flies(tweety)

bird(edna)

bird(tweety)

\underline{\underline{emu(edna)}} A2

We have �_{Π??} = {bird(tweety),emu(edna),bird(edna),¬flies(edna)}, �_{Π??∪Δ??} = {flies(edna),flies(tweety)} ∪ �_{Π??} .

It is intuitively clear that we prefer the argument (∅,¬flies(edna)) to the argument (A_{2},flies(edna)), simply because the former does not use any defeasible rules. We will further discuss this in Example ??.

Let us see what happens to Example ?? if we are not so certain anymore that no emu can fly and turn the general rule (¬flies(x) ⇐ emu(x))∈ Π??^{G} into a defeasible one in the following example.

A Series of Revisions of David Poole’s Specificity  7

Example 2 (Example 2 of (?))

Π??^{F} := \{ \begin{matrix}bird(tweety), \\ emu(edna) \end{matrix}\} ,
Π??^{G} := { bird(x) ⇐ emu(x)},
Δ?? := \{ \begin{matrix}¬flies(x) ← emu(x), \\ flies(x) ← bird(x) \end{matrix}\} .
A_{1} := { ¬flies(edna) ← emu(edna) }.
A_{2} := { flies(edna) ← bird(edna)}.

¬flies(edna)  flies(edna)  flies(tweety)

bird(edna)

bird(tweety)

\underline{\underline{emu(edna)}} A2 A1

We have �_{Π??} = {bird(tweety),emu(edna),bird(edna)}, �_{Π??∪Δ??} = {¬flies(edna),flies(edna),flies(tweety)} ∪ �_{Π??} .

It is intuitively clear that we prefer the argument (A_{1},¬flies(edna)) to the argument (A_{2},flies(edna)), simply because the defeasible derivation of the former is based on emu(edna), and because this is more specific than bird(edna), on which the derivation of the latter argument is based. We will further discuss this in Example ??.

Let us see what happens to Example ?? if we doubt that emus are birds.

Example 3 (Renamed Subsystem of Example 3 of (?))

Π??^{F} := { emu(edna)},  Π??^{G} := ∅,
Δ?? := \{ \begin{matrix}¬flies(x) ← emu(x), \\ flies(x) ← bird(x), \\ bird(x) ← emu(x) \end{matrix} \} ,
A_{1} := { ¬flies(edna) ← emu(edna) }.
A_{2} := \{ \begin{matrix}flies(edna) ← bird(edna), \\ bird(edna) ← emu(edna) \end{matrix}\} .

¬flies(edna)  flies(edna)

bird(edna)

\underline{\underline{emu(edna)}} A1 A2 A2

We have

�_{Π??} = {emu(edna)}, �_{Π?? ∪Δ??} = {bird(edna),flies(edna),¬flies(edna)} ∪ �_{Π??} . Now it is not clear anymore whether we should prefer (A_{1},¬flies(edna)) to (A_{2},flies(edna)). Both arguments are now based on emu(edna), but it is not clear whether the less specific bird(edna) — because it has dropped out of �_{Π??} now — can still be considered as a basis for (A_{2},flies(edna)). We will further discuss this in Example ??.

Now suppose that we have a lovely grandma and a grouchy and noisy grandpa, stay at their house and hear that somebody is coming into the house noisily, but cannot see yet who it is.

Example 4

Π??^{F} := { somebody, noisy },
Π??^{G} := \{ \begin{matrix}lovely ⇐ grandma, \\ ¬lovely ⇐ grandpa \end{matrix} \} ,
Δ?? := A_{1} ∪ A_{2}.
A_{1} := { grandpa ← somebody∧noisy },
A_{2} := { grandma ← somebody }.

¬lovely  lovely

grandpa  grandma

\underline{\underline{noisy}}  \underline{\underline{somebody}}

A1

A1

A2

Let us compare the specificity of the arguments (A_{1},¬lovely) and (A_{2},lovely). We have �_{Π??} = {somebody,noisy}, �_{Π??∪Δ??} = {grandma,grandpa,lovely,¬lovely} ∪ �_{Π??} . Now, because there is somebody who is noisy according to the current situation given by Π??^{F}, it is probably grandpa because his characterization is more specific. Thus, it is intuitively clear that we would prefer (A_{1},¬lovely) as the more specific argument to (A_{2},lovely). We will further discuss this in Example ??.

4 Toward an Intuitive Notion of Specificity

4.1 The Common-Sense Concept of Specificity

It is part of general knowledge that a criterion is [properly] more specific than another one if the “class of candidates that satisfy it”is a [proper] subclass of that of the other one. Analogously — taking logical formulas as the criteria — a formula A is [properly] more specific than a formula B, if the model class of A is a [proper] subclass of the model class of B, i.e. if A ⊧ B [and B |̸= A].

If we consider a formula as a predicate on model-theoretic structures, its model class becomes the extension of this predicate. From this viewpoint, we can state A ⊧ B also as the syllogism “every A is B”, and also as the following Lambert diagram (?, Dianoiologie, §§ 173–194).

\begin{matrix}⟵−−−−−−−−−−−−−−−−−−−−−−− B−−−−−−−−−−−−−−−−−−−−−−−⟶ \\ ⟵−−−−−−−−−−−−− A−−−−−−−−−−−−−−→ \end{matrix}

4.2 Arguments as an Abstraction

To enable a closer investigation of the critical parts of a defeasible derivation, we have to isolate the defeasible parts in the derivation. From a concrete derivation of a literal L, let us abstract the set A of the ground instances of the defeasible rules that are actually applied in the derivation, and form the pair (A ,L), which we already called an argument in Definition ?? of §??.

4.3 The Intuitive Rôle of Activation Sets in the Definition of Specificity

If we want to classify a derivation with defeasible rules according to its specificity, then we have to isolate the defeasible part of the derivation and look at its input formulas, so that we can see how specific these input formulas are. The input formulas are the set of those literals on which the defeasible part of the derivation is based, called the activation set for the defeasible part of the derivation. In our framework of defeasible positive-conditional specification, the only relevant property of an activation set can be the conjunction of its literals which we can represent by the set itself.^{2}

For instance, in Example ?? of §??, the argument (A_{1},¬flies(edna)) is based only on the activation set {emu(edna)}, whereas the argument (A_{2},flies(edna)) can also be based on the activation set {bird(edna)}, or on the union of these sets.

Moreover, in Example ?? of §??, the argument (A_{1},¬lovely) is based only on the activation set {somebody,noisy}, whereas the argument (A_{2},lovely) can also be based on the less specific activation set {somebody}.

2 A formal definition of an activation set is not needed here and would be harmful to intuition. Several different formal notions of activation sets will be found in Definition ?? of §?? and also in Definition ??

of §??.

4.3.1 Modulo Which Theory are Activation Sets to be Compared?

Because all literals of an activation set have been derived from the given specification, it does not make sense to compare activation sets w.r.t. the models of the entire specification. Indeed, only a comparison w.r.t. the models of a sub-specification can show any differences between them.

Therefore, we have to find out which parts of a specification (Π^{F},Π^{G},Δ) are to be excluded from the comparison of activation sets.

We want to have the entire set Π^{G} available for our comparison of activation sets, for the following reasons: The general and strict part Π^{G} of our specification represents the necessary and stable kernel of our rules, independent of the concrete situation under consideration given by Π^{F}, and independent of the uncertainty of our default rules Δ. Moreover, it is hardly meaningful to exclude any proper rule from Π^{G} (i.e. any rule from Π^{G} that is not just a literal); the technical reason for this will be given right at the beginning of §??.

We have to exclude Π^{F} from this comparison, however. This exclusion makes sense because the defeasible rules are typically default rules not written in particular for the given concrete situation that is formalized by Π^{F}. Moreover, as indicated before, the inclusion of Π^{F} would typically eliminate all differences between activation sets, such as it is the case in all examples of §??.

Finally, as we want to compare the defeasible parts of derivations, we should exclude the set Δ of the defeasible rules when we compare activation sets. Thus, on the one hand, all we can take into account from our specification is a subset of the general rules Π^{G}, and, on the other hand, we do not want to exclude any of these general rules.

All in all, we conclude that Π^{G} is that part of our specification modulo which activation sets are to be compared.

4.3.2 A first Sketch of a Notion of Specificity

Very roughly speaking, if we have fewer activation sets for the defeasible part of a derivation, then these activation sets describe fewer models (i.e. their disjunction has fewer models), which again means that the defeasible part of the derivation is more specific. Accordingly, a first sketch of a notion of specificity can now be given as follows:

An argument (A_{1},L_{1}) is [properly] more specific than an argument (A_{2},L_{2}) if, for each activation set H_{1} for (A_{1},L_{1}), there is an activation set H_{2} ⊆ �_{H_{1}∪Π^{G}} for (A_{2},L_{2}) [but not vice versa].

Note that this notion of specificity is preliminary, and that the notion of an activation set for an argument has not been properly defined yet.

4.4 Isolation of the Defeasible Parts of a Derivation

If (A ,L) is an argument (cf. §??), then there is a derivation of L which is based only on those instances of defeasible rules which are contained in A . Such an argument ignores the concrete derivation, and therefore suits our model-theoretic intentions (cf. § 1). With such an argument as an abstraction of a derivation, however, we lose the possibility to isolate the actual defeasible parts of the derivation. Such a loss is typical for abstractions in general; in our case, however, the discussion of this loss in §?? will turn out to be conceptually crucial and result in several different formal notions of activation sets.^{3} 4.4.1 Isolation of Actual Defeasible Parts in And-Trees

Let us compare the set A with an and-tree of the derivation. Every node in such a tree is labeled with the conclusion of an instance of a rule, such that its children are labeled exactly with the elements of the conjunction in the condition of this instance.

Definition 6 (And-Tree) Let (Π^{F},Π^{G},Δ) be a defeasible specification (cf. §??), and let L be a literal. An and-tree T for L [and for the derivation of Φ ⊢ {L}] w.r.t. (Π^{F},Π^{G},Δ) is a finite, rooted tree, where every node is labeled with a literal, satisfying the following conditions:

1. The root node of T is labeled with L.

2. For each node N in T labeled with a literal L′, there is a strict or defeasible rule (L′′_{0}⇐ L′′_{1}∧ ...∧L′′_{k}) ∈ Π ∪ Δ, such that L′ = L′′_{0}σ for some substitution σ [with (L′′_{0}σ ⇐ L′′_{1}σ∧ ...∧L′′_{k}σ) ∈ Φ]. Moreover, the node N has exactly k child nodes, which are labeled with L′′_{1}σ,...,L′′_{k}σ, respectively.

This standard and very simple formal notion of an and-tree is meant to capture a single derivation for a single argument. It must not be confused with the compact multi-graphs that come as a synopsis with our examples (such as the ones in §??).^{4}

An isolation of the defeasible parts of an and-tree of the derivation may now proceed as follows:

– Starting from the root of the tree, we iteratively erase all applications of strict rules. This gives us a set of trees, each of which has the application of a defeasible rule at the root.

– Starting now from the leaves of these trees, we again erase all applications of strict rules. This gives us a set of trees with the following property holding for every node: If all children of a node (if there are any) are leaves, then this node results from an application of a defeasible rule.

4.4.2 A first approximation of Activation Sets

In a first approximation, we may now take the activation set for the original derivation to be the set of all labels L of all leaves of all resulting trees, unless the literal L is an unconditional rule from A .

The motivation for this notion of an activation set is that the conjunction of its literals is a weakest precondition for all defeasible parts of the concrete original derivation. If such a logically weakest precondition satisfies the specificity notion of §?? as an activation set for an argument (A_{1},L_{1}) w.r.t. a second argument (A_{2},L_{2}), then any other precondition for all defeasible parts of the given and-tree will satisfy this notion w.r.t. (A_{2},L_{2}) a fortiori.^{5} 4.4.3 Growth of the Defeasible Parts toward the Leaves

3 See Definition ?? of §?? and also Definition ?? of §??.

4 These sophisticated multi-graphs illustrate several derivations for several arguments in parallel, share sub-graphs, and may have =-edges between occurrences of the same literal L to represent alternative derivations of L (cf. Example ?? in §?? as well as Examples ?? and ?? in §??). Because these synopses are redundant in all examples, we do not provide a formalization for these multi-graphs.

5 Note that a further dissection of the isolated defeasible parts would not in general result in activation sets that can be inferred from the strict rules in Π. Where this inference is possible, however, a further dissection leads to the special notion of activation sets given in Definition ?? of §??.

Note that in the set of trees resulting from the procedure described at the end of §??, there may well have remained instances of rules from Π^{G} connecting a defeasible root application with the defeasible applications right at the leaves. Thus — to cover the whole defeasible part of the derivation in our abstraction — we have to consider the set A ∪ Π^{G} instead of just the set A .

More precisely, we have to include all proper rules (i.e. those with non-empty conditions) from Π^{G}, and may also include the literals in Π^{G} because they cannot do any harm.^{6}

As a consequence, in the modeling via our abstraction A, we cannot prevent the isolated defeasible sub-trees resulting from the procedure described in §?? from using the rules from Π^{G} to grow toward the root and toward the leaves again. Only the growth toward the leaves, however, can affect our activation sets (which are still taken to be the labels of all leaves of all resulting trees) and thereby our notion of specificity. Indeed, a growth toward the root can add to the conjunction of the given leaves only its super-conjunctions, which are irrelevant because of our focus on weakest preconditions (explained in §??).

Let us have a closer look at the effects of such a growth toward the leaves in the most simple case. In addition to a given activation set {Q(a)}, in the presence of a general rule

Q(x)⇐ P_{0}(x)∧ ··· ∧P_{n−1} (x)

from Π^{G}, we will also have to consider the activation set { P_{i}(a) | i∈ {0,...,n− 1} }. This has two effects, which we will discuss in §§ ?? and ??.

4.4.4 First Effect: Simplified Second Sketch of a Notion of Specificity

The first effect is that we immediately realize that every model of Π^{G} in the model class that is represented by the activation set { P_{i}(a) | i∈ {0,...,n− 1} } is also in the model class represented by the activation set {Q(a)}.

Indeed, this growth toward the leaves will immediately add { P_{i}(a) | i∈ {0,...,n− 1} } as a further activation set for every argument with the activation set {Q(a)}. By this effect it is just made explicit that an argument that can be based on the activation set {Q(a)} can also be based on the activation set { P_{i}(a) | i∈ {0,...,n− 1} }. Thus — provided that there are no other activation sets — an argument that can be based on the activation set {Q(a)} is less or equivalently specific compared to any argument that can be based on { P_{i}(a) | i∈ {0,...,n− 1} }.

Therefore — if we admit the effect of a growth toward the leaves on our activation sets — we may simplify^{7} the comparison of activation sets in our first sketch of a notion of specificity of §?? as follows:

An argument (A_{1},L_{1}) is [properly] more specific than an argument (A_{2},L_{2}) if, for each activation set H_{1} for (A_{1},L_{1}), this set H_{1} is also an activation set for (A_{2},L_{2}) [but not vice versa].

6 The need to include all proper rules and to exclude the literals from Π^{F} provides a motivation for simply defining Π^{G} to contain exactly the proper rules of Π, such as found in (?).

7 Note that we have replaced here the option to choose some activation set H_{2} ⊆ �_{H_{1}∪Π^{G}} of the first sketch with the restrictive determination H_{2} := H_{1}. This simplifying restriction applies here for the following reason: If H_{2} ⊆ �_{H_{1}∪Π^{G}} is an activation set for (A_{2},L_{2}), then H_{1} is an activation set for (A_{2},L_{2}) as well, provided that we admit the first effect of a growth toward the leaves via Π^{G} on our activation sets.

4.4.5 Second Effect: Preference of the “More Concise”

The second effect, however, is that an argument (A_{2},L_{2}) that gets along with {Q(a)} becomes even properly less specific than an argument (A_{1},L_{1}) that actually requires { P_{i}(a) | i∈ {0,...,n− 1} } and does not get along with {Q(a)}, simply because (A_{2},L_{2}) has the additional activation set {Q(a)}.

The resulting preference of (A_{1},L_{1}) to (A_{2},L_{2}) as being properly more specific is usually called preference of the “more concise”, cf. e.g. (?, p. 94), (?, p.108). Although — to the best of our knowledge — this notion has never been formally defined, roughly speaking it is — for an instantiated rule Q(a) ⇐ P_{0}(a)∧ ··· ∧P_{n−1} (a) of the specification — the preference of an argument that gets along with the conclusion {Q(a)} of the instantiated rule as an activation set, instead of actually requiring the condition { P_{i}(a) | i∈ {0,...,n− 1} }.

For instance, in Example ?? of §??, an argument that gets along with {bird(edna)} is properly less specific than one that actually requires {emu(edna)}, in the sense that emu(edna) is more concise than bird(edna).

The problem now is that the statement Q(a) |̸= P_{0}(a)∧ ··· ∧P_{n−1} (a) — which is required to justify this preference — is not explicitly given by the specification (Π^{F},Π^{G},Δ) .

Nevertheless — if we do not just want to see it as a matter-of-fact property of notions of specificity in the style of Poole — we could justify the preference of the “more concise” by imposing the following best practice on positive-conditional specification:

If we write an implication in form of a rule

Q(x)⇐ P_{0}(x)∧ ··· ∧P_{n−1} (x)

into a positive-conditional specification Π of strict (i.e. non-defeasible) knowledge, and if we do not intend that the implication is proper in the sense that its converse does not hold in general, then we ought to specify the full equivalence by adding the rules P_{i}(x)⇐ Q(x) (i∈ {0,...,n− 1}) to the specification.^{8}

Under this best practice of specification, if we find such a rule without the specification of its full equivalence, then it is not intended to exclude models where Q holds for some object a, but not all of the P_{i} do. This means that if we find such a rule in the strict and general part Π^{G} of a specification, then it is reasonable to assume that the implication is proper w.r.t. the intuition captured in the defeasible rules in Δ.

As a consequence, it makes sense to consider a defeasible argument based on { P_{i}(a) | i∈ {0,...,n− 1} } to be properly more specific than an argument that can get along with Q(a).

⟵−−−−−−−−−−−−−−−−−−−−−− Q(a)−−−−−−−−−−−−−−−−−−−−−−⟶

⟵−−−−−−−−−− ⋀_{i}P_{i}(a)−−−−−−−−−−⟶
⟵−−−−−−−−−−−−−−−−−−−−−− P_{k}(a)−−−−−−−−−−−−−−−−−−−−−−−→

Remark 5 (Justification for Preference of the “More Concise” Not Valid for Defeasible Rules) Note that our justification for the preference of the “more concise” does not apply, however, if Q(x)⇐ P_{0}(x)∧ ··· ∧P_{n−1} (x) is a defeasible rule instead of a strict one, because we then have the following three problems when trying to justify preference of the “more concise”:

– The implication given by the rule is not generally intended (otherwise the rule should be a strict one).

– Moreover, we cannot easily describe the actual instances to which the default rule is meant to apply (otherwise this more concrete description of the defeasible rule should be stated as strict rules).

– The direct treatment of a defeasible equivalence neither has to be appropriate as a default rule in the given situation, nor do we have any means to express a defeasible equivalence in the current setting.

Accordingly, there is, for instance, no clear reason to prefer the first argument of Example ?? in §?? to the second one. This will be discussed in more detail in Example ??.

4.4.6 Preference of the “More Precise”

If we consider an argument requiring an activation set { P_{i}(a) | i∈ {0,...,n} } to be properly more specific than an argument that gets along with a proper subset { P_{i}(a) | i∈ I } for some index set I ⊊ {0,...,n}, then the resulting preference is usually called preference of the “more precise”, cf. e.g. (?, p. 94), (?, p.108). An example for the preference of the “more precise” is Example ?? of §??.

There is, however, an exception from this preference to be observed, namely the case that we can actually derive the set from its subset with the help of Π^{G}. In this case, the abovementioned growth toward the leaves with rules from Π^{G} again implements the approximation of the subclass relation among model classes via the one among activation sets.^{9}

Apart from this exception, there is again a problem, namely that it is not the case that

⋀_{i∈I} P_{i}(a) |̸= ⋀_{i∈{0,...,n}} P_{i}(a)

would be explicitly given by the specification via (Π^{F},Π^{G},Δ) .

Nevertheless — if we do not just want to see it as a matter-of-fact property of notions of specificity in the style of Poole — we could justify also the preference of the “more precise” by imposing the following best practice on positive-conditional specification:

If we want to exclude the above non-consequence, then we ought to specify, for each j ∈ {0,...,n}\I, a rule like P_{j}(x)⇐ ⋀_{i∈I} P_{i}(x).

⟵−−−−−−−−−−−−−−− ⋀_{i∈I} P_{i}(a)−−−−−−−−−−−−−−−−→
⟵−−−−−−− ⋀_{i∈{1,...,n}} P_{i}(a)−−−−−−−⟶
⟵−−−−−−−−−−−−−−−−−−−−−− P_{k}(a)−−−−−−−−−−−−−−−−−−−−−−−→

4.4.7 Conclusion on the Preferences

Let us finally point out that an acceptance of our justifications of the preferences of the “more concise” and the “more precise” is not at all a prerequisite for following our investigations on Poole’s model-theoretic notion of specificity and our correction of this notion in the following sections.

8 There is one exception to this justification, however, in the practice of logic programming: If Q(x) ⇐ P_{0}(x)∧ ··· ∧P_{n−1} (x) is the only rule of the specification with Q as the predicate symbol of the conclusion, then it is standard in Prolog to consider this implication as an implementation of a full equivalence defining the predicate Q.

This is different in our context of positive-conditional specification here, however, where we can add and ought to add the rules P_{i}(x) ⇐ Q(x) (i∈ {0,...,n− 1}) to our specification, simply because we are not concerned with the non-termination problem of logic programming resulting from such a specification of the full equivalence (cf. §??).

An alternative which is given also in logic programming is to omit the rule indicated above and to replace each occurrence of each Q(t) with P_{0}(t)∧ ··· ∧P_{n−1} (t), respectively.

Moreover, in the frequent case that several cases of the definition of a predicate are spread over several rules, the implications definitely tend to be proper also in logic programming, because, roughly speaking, the defined predicate is given as the proper disjunction of the conditions of the several rules.

9 This approximation was discussed in §?? and will be demonstrated in Example ?? of §??.

5 Requirements Specification of Specificity in Positive-Conditional Specification

With implicit reference to a defeasible specification (Π^{F},Π^{G},Δ) (cf. §??), let us designate Poole’s relation of being more (or equivalently) specific by “≲_{P1}”. Here, “P1” stands for “Poole’s original version”.

The standard usage of the symbol “≲” is to denote a quasi-ordering (cf. §??). Instead of the symbol “≲”, however, (?) uses the symbol “≤”. The standard usage of the symbol “≤” is to denote a reflexive ordering (cf. §??). We cannot conclude from this, however, that Poole intended the additional property of anti-symmetry; indeed, Poole gives a concrete example specification where the lack of anti-symmetry of ≲_{P1} is made explicit.^{10}

The possible lack of anti-symmetry of quasi-orderings — i.e. that different arguments may have an equivalent specificity — cannot be a problem because any quasi-ordering ≲_{N} immediately provides us with its equivalence ≈_{N}, its ordering <_{N}, and its reflexive ordering ≤_{N} (cf. Corollary ?? of §??).

By contrast to the non-intended anti-symmetry, transitivity is obviously a conditio sine qua non for any useful notion of specificity. Indeed, if we have to make a quick choice among the three mutually exclusive actions Propose, Kiss, Smile, and if we already have an argument (A_{2},Kiss) that is more specific than another argument (A_{3},Smile), and if we come up with yet another argument (A_{1},Propose) that is even more specific than (A_{2},Kiss), then, by all means, (A_{1},Propose) should be more specific than the argument (A_{3},Smile) as well. It is obvious that a notion of specificity without transitivity could hardly be helpful in practice.

A further conditio sine qua non for any useful notion of specificity is that the conjunctive combination of respectively more specific arguments results in a more specific argument. Indeed, if a square is more specific than a rectangle and a circle is more specific than an ellipse, then a square inscribed into a circle should be more specific than a rectangle inscribed into an ellipse. This property is called monotonicity of conjunction, which we will discuss in §??. Already in (?), we find an example^{11} where ≲_{P1}violates this monotonicity property of the conjunction, which is described there as “seemingly unintuitive”.^{12}

Further intricacies of computing Poole’s specificity in concrete examples are described in (?),^{13} which will make it hard to implement ≲_{P1} or its minor corrections as efficiently as required in the practice of answer computation and SLD-resolution w.r.t. positive-conditional specifications.

6 Formalizations of Specificity

6.1 Activation Sets

A derivation from the leaves to the root can now be split into three phases of derivation of literals from literals. This splitting follows the discussion in §?? on how to isolate the defeasible parts of a derivation (phase 2) from strict parts that may occur toward the root (phase 3) and toward the leaves (phase 1):

10 Here we refer to the last three sentences of § 3.2 on Page 145 of (?).

11 Here we refer to Example 6 of (?, § 3.5, p.146), see our Example ?? in §??.

12 See our Example ?? in §?? and the references there.

13 Here we refer to § 3.2ff. of (?), where it is demonstrated that, for deciding Poole’s specificity relation (actually ≲_{P2} instead of ≲_{P1}, but this does not make any difference here) for two input arguments, we sometimes have to consider even those defeasible rules which are not part of any of these arguments. See also our Example ?? in §??.

(phase 1) First we derive the literals that provide the basis for specificity considerations. In our approach we derive the set �_{Π} here. Poole takes the set �_{Π∪Δ} instead.

(phase 2) On the basis of – a subset H of the literals derived in phase 1,

– the first item A of a given argument (A ,L), and

– the general rules Π^{G},

we derive a further set of literals �: H ∪ A ∪ Π^{G} ⊢ �.

(phase 3) Finally, on the basis of �, the literal of the given argument (A ,L) is derived:

�∪ Π ⊢ {L}. In Poole’s approach, phase 3 is empty and we simply have �= {L}. In our approach, however, it is admitted to use the facts from Π^{F} in phase 3, in addition to the general rules from Π^{G}, which were already admitted in phase 2.

With implicit reference to our sets Π = Π^{F}∪ Π^{G} and Δ, the phases 2 and 3 can be more easily expressed with the help of the following notions.

Definition 7 ([Minimal] [Simplified] Activation Set) Let A be a set of ground instances of rules from Δ, and let L be a literal. H is a simplified activation set for (A ,L) if L ∈ �_{H ∪ A ∪ Π^{G}} . H is an activation set for (A ,L) if L ∈ �_{�∪Π} for some �⊆ �_{H ∪ A ∪ Π^{G}} . H is a minimal [simplified] activation set for (A ,L) if H is an [simplified] activation set for (A ,L), but no proper subset of H is an [simplified] activation set for (A ,L).

Corollary 2 Let A be a set of ground instances of rules from Δ, and let L be a literal. Every simplified activation set for (A ,L) is an activation set for (A ,L).

Roughly speaking, an argument is now more (or equivalently) specific than another one if each of its activation sets is also an activation set for the other argument. Note that this follows the simplified second sketch of a notion of specificity displayed in §??, not the first one displayed in §??.

Activation sets that are not simplified differ from simplified ones by the admission of facts from Π^{F} (in addition to the general rules Π^{G}) after the defeasible part of the derivation is completed.^{14}

Our introduction of activation sets that are not simplified is a conceptually important correction of Poole’s approach: It must be admitted to use the facts besides the general rules in a purely strict derivation that is based on literals resulting from completed defeasible arguments, simply because the defeasible parts of a derivation (as isolated in §??) should not get more specific by the later use of additional facts that do not provide input to the defeasible parts.^{15} Note that the difference between simplified and non-simplified activation sets typically occurs in real applications, but — except Example ?? in §?? — not in our toy examples of §??, which mainly exemplify the differences in phase 1.

14 This can be seen in Example ?? of §??, and in Example ?? of §??. See also the variable F in Figure ??.

15 We do not further discuss this obviously appropriate correction here and leave the construction of examples that make the conceptual necessity of this correction intuitively clear as an exercise. Hint: Have a look at the proof of Theorem ?? in §??. Then present two different sets of strict rules with equal derivability, where only one needs the facts in phase 3 and where the additional specificity gained by these facts violates the intuition.

F ∪ Π^{G} ... A A ∪ Π^{G} H A A ∪ Π^{G} H

H ⊆ ...  F = ...
Poole’s Approach (P1, P2, P3)  �_{Π^{F}∪Π^{G}∪Δ}  H ^{16}
Our Approach (CP1, CP2)  �_{Π^{F}∪Π^{G}}  Π^{F} ^{17}

Fig. 1 And-Tree with Phases 1, 2, 3.^{18}

6.2 Poole’s Specificity Relation P1 and its Minor Corrections P2, P3

In this section we will define the binary relations ≲_{P1}, ≲_{P2}, ≲_{P3} of “being more or equivalently specific according to David Poole” with implicit reference to our sets of facts and of general and defeasible rules (i.e. to Π^{F}, Π^{G}, and Δ, respectively).

The relation ≲_{P1} of the following definition is precisely Poole’s original relation ≥ as defined at the bottom of the left column on Page 145 of (?). See §?? for our reasons to write “≳” instead of “≥” as a first change. Moreover, as a second change required by mathematical standards, we have replaced the symbol “≳” with the symbol “≲” (such that the smaller argument becomes the more specific one), so that the relevant well-foundedness becomes the one of its ordering < instead of the reverse >.

Definition 8 (≲_{P1}: David Poole’s Original Specificity) (A_{1},L_{1})≲_{P1}(A_{2},L_{2}) if (A_{1},L_{1}) and (A_{2},L_{2}) are arguments, and if, for every H ⊆ �_{Π∪Δ} that is a simplified activation set for (A_{1},L_{1}) but not a simplified activation set for (A_{2},L_{1}), H is also a simplified activation set for (A_{2},L_{2}).

The relation ≲_{P2} of the following definition is the relation ⪰ of (?, Definition 10, p.94) (attributed to ?). Moreover, the relation >_{spec} of (?, Definition 2.12, p.132) (attributed to ? as well) is the relation <_{P2} := ≲_{P2}\ ≳_{P2}.

16 Look at Note ?? of Example ?? in §?? to see that it may really matter for the definition of P1, P2, P3 that we do not have F ⊆ �_{Π^{F}∪Π^{G}} in general in Poole’s approach.

17 Although we do not have H⊆ Π^{F} in general in our approach, the replacement of Π^{F} with H in this table would result in fewer derivable roots for our approach, simply because we always have �_{H∪Π^{G}} ⊆ �_{Π^{F}∪Π^{G}} in our approach.

18 From the leaves to the root: phase 1 (H), phase 2 (sub-trees of the defeasible parts of a derivation, with explicit defeasible root steps), phase 3 (root sub-tree). For Poole’s approach, however, the root sub-tree is still part of phase 2, whereas phase 3 is empty.

Definition 9 (≲_{P2}: Standard Version of David Poole’s Specificity) (A_{1},L_{1})≲_{P2}(A_{2},L_{2}) if (A_{1},L_{1}) and (A_{2},L_{2}) are arguments, and if, for every H ⊆ �_{Π∪Δ} that is a simplified activation set for (A_{1},L_{1}) but not a simplified activation set for (∅,L_{1}), H is also a simplified activation set for (A_{2},L_{2}). The only change in Definition ?? as compared to Definition ?? is that “(A_{2},L_{1})” is replaced with “(∅,L_{1})”. We did not yet encounter any example where any difference results from this correction toward “(∅,L_{1})”, which is standard in the publications of the last two decades and which is intuitively more appropriate in the sense of a weight or measure function. The relations ≲_{P1}and ≲_{P2}were not meant to compare arguments for literals that do not need any defeasible rules — or at least they do not show an intuitive behavior on such arguments, as shown in Example ??. Example 5 (Minor Flaw of ≲_{P1} and ≲_{P2})

Π??^{F} := {thirst}, Π??^{G} := {drink ⇐ thirst},
Δ?? := A_{2}.
A_{2} := { beer ← thirst }.

drink  beer

\underline{\underline{thirst}} A2

Let us compare the specificity of the arguments (A_{2},beer) and (∅,drink), meaning that we should have a beer or else an arbitrary drink at our own choice, respectively. We have �_{Π??} = {thirst,drink}, �_{Π??∪Δ??} = {beer} ∪ �_{Π??} . We have (A_{2},beer) ≲_{P2} (∅,drink) because for every H ⊆ �_{Π??∪Δ??} that is a simplified activation set for (A_{2},beer), but not a simplified activation set for (∅,beer), we have thirst ∈ H, so H is a simplified activation set also for (∅,drink). We have (∅,drink) ≲_{P2} (A_{2},beer) because there cannot be a simplified activation set for (∅,drink) that is not a simplified activation set for (∅,drink). All in all, we get^{19} (A_{2},beer) ≈_{P2} (∅,drink), although (∅,drink) should be strictly preferred to (A_{2},beer) according to intuition, simply because an argument that does not require any defeasible rules should always be strictly preferred to a comparable argument that does actually require defeasible rules. To overcome this minor flaw, which consists in the inconvenience of not in general preferring a non-defeasible argument to a comparable defeasible one, we finally add an implication as an additional requirement in Definition ??. This implication guarantees that no argument that requires defeasible rules can be more or equivalently specific than an argument that does not require any defeasible rules at all. Definition 10 (≲_{P3}: Rather Unflawed Version of David Poole’s Specificity) (A_{1},L_{1}) ≲_{P3}(A_{2},L_{2}) if (A_{1},L_{1}) and (A_{2},L_{2}) are arguments, L_{2}∈ �_{Π} implies L_{1}∈ �_{Π} , and if, for every H ⊆ �_{Π∪Δ} that is a [minimal]^{20} simplified activation set for (A_{1},L_{1}) but not a simplified activation set for (∅,L_{1}), H is also a simplified activation set for (A_{2},L_{2}).

Corollary 3 If (A_{1},L_{1}), (A_{2},L_{2}) are arguments with A_{1}⊆ A_{2}, then any of the following conditions is sufficient for (A_{1},L_{1}) ≲_{P3}(A_{2},L_{2}):

1. L_{1}= L_{2}.

2. L_{2} ∈ �_{Π} ⇒ L_{1} ∈ �_{Π} and {L_{1}} ∪ A_{2}∪ Π^{G} ⊢ {L_{2}},

3. A_{1}= ∅ (which implies L_{1}∈ �_{Π} by Definition ??).^{21} As every simplified activation set that passes the condition of Definition ?? also passes the one of Definitions ?? and ??, we get the following corollary of these three definitions.

19 Note that by Corollary ??, we will get (A_{2},beer) ≈_{P1} (∅,drink) as well. Moreover, note that this problem does not occur in the similar Example ?? of §??.

20 Note that the omission of the optional restriction to minimal simplified activation sets for (A_{1},L_{1}) in Definition ?? has no effect on the extension of the defined notion, simply because the additional non-minimal simplified activation sets (A_{1},L_{1}) will then be simplified activation sets for (A_{2},L_{2}) a fortiori.

Corollary 4 ≲_{P3} ⊆ ≲_{P2} ⊆ ≲_{P1}.

By Corollaries ?? and ??, ≲_{P1}, ≲_{P2}, and≲_{P3} are reflexive relations on arguments, but — aswe will show in Example ?? and state in Theorem ?? — not quasi-orderings in general.

Example 6 (Counterexample to the Transitivities: “Choose one action!”) Suppose you meet the sexy girl Jo in a lift for a very short time, you smile at her, and she smiles back with a head akimbo. Since smiling, kissing, and proposing are mutually exclusive actions of your mouth, you have to make up your mind quickly what to do next, depending on your current level of boldness.^{22}

Π??^{F} := { Bold, HAkimbo(Jo), Smiles(Jo), Sexy(Jo)},
Π??^{G} := { Kiss ⇐ Promising(G)},

Δ?? := \{ \begin{matrix}Smile ← Sexy(G), \\ Kiss ← Bold∧ Smiles(G)∧ Sexy(G), \\ Promising(G)← HAkimbo(G)∧ Smiles(G)∧ Sexy(G), \\ Propose & ← & Promising(G) & ∧ & Bold \end{matrix} \} .

A_{1} := \{ \begin{matrix}Promising(Jo) & ← & HAkimbo(Jo) & ∧ & Smiles(Jo) & ∧ & Sexy(Jo) \\ Propose & ← & Promising(Jo) & ∧ & Bold \end{matrix} \} ,
A_{2} := { Kiss ← Bold∧ Smiles(Jo)∧ Sexy(Jo)},
A_{3} := { Smile ← Sexy(Jo)}.

Compare the specificity of the arguments (A_{1},Propose), (A_{2},Kiss), (A_{3},Smile) !

Propose  Kiss  Kiss  Smile

Promising(Jo)  \underline{\underline{Bold}}

\underline{\underline{HAkimbo(Jo)}}  \underline{\underline{Smiles(Jo)}}  \underline{\underline{Sexy(Jo)}}

A1

A1

A1

A1

A1

A2

A2

A2

A3

Lemma 1 There are

– a specification (Π??^{F},Π??^{G},Δ??) without any negative literals (i.e., a fortiori, Π??^{F} ∪ Π??^{G} ∪ Δ?? is non-contradictory), and

– minimal arguments (A_{1},L_{1}), (A_{2},L_{2}), (A_{3},L_{3}),

such that (A_{1},L_{1}) ≲_{P3} (A_{2},L_{2}) ≲_{P3} (A_{3},L_{3}) ≵_{P1} (A_{1},L_{1})
and (A_{1},L_{1}) ≵_{P1} (A_{2},L_{2}) ≵_{P1} (A_{3},L_{3}).

Proof of Lemma ?? Looking at Example ??, we see that only the quasi-ordering properties in the last two lines of Lemma ?? are non-trivial. We have

21 Exercise: Find a counterexample, however, for the conjecture that L_{1}∈ �_{Π} implies (A ,L_{1})≲_{P3}(A ,L_{2}).

22 The nullary predicate Bold could actually be removed from all rules and facts of this example, which would still remain a counterexample to the transitivities; to the contrary, it would even improve its status by becoming a minimal counterexample. A renaming of the resulting minimal counterexample was presented as Example 5.8 in (?, ?; ?).

�_{Π??}  = {Bold, HAkimbo(Jo), Smiles(Jo), Sexy(Jo)},
�_{Π??∪Δ??} = {Promising(Jo), Propose, Kiss, Smile} ∪ �_{Π??} .

Thus, regarding the arguments (A_{1},Propose), (A_{2},Kiss), (A_{3},Smile), the implication added in Definition ?? as compared to Definitions ?? and ?? is always satisfied, simply because its condition is always false. \underline{(A_{3},Smile) ≵_{P1}(A_{1},Propose) ≲_{P3}(A_{2},Kiss) :} The minimal simplified activa-

tion sets for (A_{1},Propose) that

are subsets of �_{Π??∪Δ??} and no simplified activation sets for (∅,Propose) (or, without any difference, no simplified activation sets for (A_{3},Propose)) are {Bold,HAkimbo(Jo),Smiles(Jo),Sexy(Jo)} and {Bold,Promising(Jo)}, which are simplified activation sets for (A_{2},Kiss) — but {Bold,Promising(Jo)} is no simplified activation set for (A_{3},Smile). \underline{(A_{1},Propose) ≵_{P1}(A_{2},Kiss) ≲_{P3}(A_{3},Smile) :} The only simplified activation set for

(A_{2},Kiss) that is a subset of �_{Π??∪Δ??} and

no simplified activation set for (∅,Kiss) (such as {Promising(Jo)}) (or, without any difference, no simplified activation set for (A_{1},Kiss)) is {Bold,Smiles(Jo),Sexy(Jo)}, which is a simplified activation set for (A_{3},Smile), but not for (A_{1},Propose). \underline{(A_{2},Kiss) ≵_{P1}(A_{3},Smile) :} The only minimal simplified activation set for (A_{3},Smile) that

is a subset of �_{Π??∪Δ??} and no simplified activation set for

(A_{2},Smile) is {Sexy(Jo)}, which is not a simplified activation set for (A_{2},Kiss). Q.e.d. (Lemma ??)

6.3 Main Negative Result: Not Transitive!

The relations stated in Lemma ?? hold not only for the given indices, but — by Corollary ?? — actually for all of P1, P2, P3; and so we immediately get: Theorem 1 There is a specification (Π??^{F},Π??^{G},Δ??), such that Π??^{F} ∪Π??^{G} ∪Δ?? is non-contradictory, but none of ≲_{P1}, ≲_{P2}, ≲_{P3}, <_{P1}, <_{P2}, <_{P3} is transitive. Moreover, the counterexamples to the transitivity of all these relations can be restricted to minimal arguments. As a consequence of Theorem ??, the respective relations in (?), (?), and (?) are not transitive. This means that these relations are not quasi-orderings, let alone reflexive orderings.

This consequence is immediate for the relation ≥ at the bottom of the left column on Page 145 of (?). Moreover, note that the consequence does not depend on the contentious question on whether our interpretation of the negation symbol ¬ essentially differs from its interpretation in (?). Indeed, our counterexample to transitivity occurs in the negation-free definite-rule fragment of Poole’s original language.

Moreover, this consequence is also immediate for the relation ⪰ (?, Definition 10, p. 94) and for the relation >_{spec} (?, Definition 2.12, p.132), simply because we can replace ⪰ and >_{spec} with ≲_{P2} and <_{P2} in the context of Example ??, respectively.

Although transitivity of these relations is strongly suggested by the special choice of their symbols and seems to be taken for granted in general, we found an actual statement of such a transitivity only for the relation ⊒ of (?, Definition 2.22, p.134), namely in “Lemma 2.23”(?, p.134).^{23}

Finally, note that those readers who do not see a proper conflict in our counterexample just should add to Example ?? some general rules such as Execute ⇐ Kiss, Execute ⇐ Smile, ¬Execute ⇐ Propose, say to model the situation in one of the areas of today’s planet Earth where an unmarried woman who raises the wish to smile or kiss has to be executed.

6.4 Our Novel Specificity Ordering CP1

In the previous section, we have seen that minor corrections of Poole’s original relation P1 (such as P2, P3) do not cure the (up to our finding of Example ??) hidden or even denied deficiency of these relations, namely their lack of transitivity. Our true motivation for a major correction of P3 was not this formal deficiency, but actually an informal one, namely that it failed to get sufficiently close to human intuition, which will become clear in §??.

For these reasons, we now define our major \underline{c}orrection of \underline{P}oole’s specificity — the binary relation ≲_{CP1}— with implicit reference to our sets of facts and of general and defeasible rules (i.e. to Π^{F}, Π^{G}, and Δ, respectively) as follows.

Definition 11 (≲_{CP1}: 1^{st}Version of our Specificity Relation) (A_{1},L_{1}) ≲_{CP1}(A_{2},L_{2}) if (A_{1},L_{1}) and (A_{2},L_{2}) are arguments, and we have

1. L_{1}∈ �_{Π} or

2. L_{2} ∉ �_{Π} and every H ⊆ �_{Π} that is an [minimal]^{24} activation set for (A_{1},L_{1}) is also an activation set for (A_{2},L_{2}).

Corollary 5 If (A_{1},L_{1}), (A_{2},L_{2}) are arguments with A_{1}⊆ A_{2}, then any of the following conditions is sufficient for (A_{1},L_{1}) ≲_{CP1}(A_{2},L_{2}) :

1. L_{1}= L_{2}.

2. L_{2} ∈ �_{Π} ⇒ L_{1} ∈ �_{Π} and {L_{1}} ∪ Π ⊢ {L_{2}}. ^{25}

3. L_{1} ∈ �_{Π} (which is implied by A_{1}= ∅ by Definition ??).

The crucial change in Definition ?? as compared to Definition ?? is not the technically required emphasis it puts on the case “L_{1}∈ �_{Π} ”, which will be discussed in Remark ?? of §??. The crucial changes actually are

(A) the replacement of “H ⊆ �_{Π∪Δ} ” with “H ⊆ �_{Π} ” (as explained already in phase 1 of §??),

and the thereby enabled (B) omission of the previously technically required,^{26} but unintuitive negative condition on

derivability (of the form “but not a simplified activation set for (∅,L_{1})”).

An additional minor change, which we have already discussed in §??, is the one from simplified activation sets to (non-simplified) activation sets.

23 According to the rules of good scientific and historiographic practice, we pinpoint the violation of this “lemma” now as follows. Non-transitivity of ⊒ follows here immediately from the non-transitivity of the relation ≥_{spec} of Definition 2.15, which, however, is not identical to the above-mentioned relation ⪰, but actually a subset of ⪰, because it is defined via a peculiar additional equivalence ≈_{spec} introduced in Definition 2.14 (?, p.132), namely via ≥_{spec} := >_{spec} ∪ ≈_{spec} (?, Definition 2.15, p.132f.). Directly from Definition 2.14 of (?), we get ≈_{spec} ⊆ ≈_{P2} . Thus, by Corollary ??, we get ≥_{spec} ⊆ ≲_{P2} ⊆ ≲_{P1}; and so (recollecting <_{P2} ⊆ >_{spec} ⊆ ≥_{spec} ) the result

(A_{1},L_{1}) <_{P2}(A_{2},L_{2}) <_{P2}(A_{3},L_{3}) ≵_{P1}(A_{1},L_{1})

of Lemma ?? gives us the following counterexample to transitivity:

(A_{1},L_{1}) ≥_{spec} (A_{2},L_{2}) ≥_{spec} (A_{3},L_{3}) ≰_{spec} (A_{1},L_{1}).

24 Note that the omission of the optional restriction to minimal activation sets for (A_{1},L_{1}) in Definition ??

has no effect on the extension of the defined notion, simply because the additional non-minimal activation sets for (A_{1},L_{1}) will then be activation sets for (A_{2},L_{2}) a fortiori.

25 Note that, in general — contrary to Corollary ??(2) — A_{2} must not participate in the derivation of L_{2} from L_{1}, say in the form that there is a set of literals � with {L_{1}} ∪ A_{2} ∪ Π^{G} ⊢ � and �∪ Π ⊢ {L_{2}}, because rules from Π^{F} may have participated in the derivation of L_{1} from an activation set. The source of this difference between P3 and CP1 is the replacement of simplified activation sets in Definition ?? with (non-simplified) activation sets in Definition ??.

26 See the discussion in Example ?? in §?? on why this condition is technically required for P1, P2, and P3.

Theorem 2 ≲_{CP1}is a quasi-ordering on arguments.

Proof of Theorem ?? ≲_{CP1}is a reflexive relation on arguments because of Corollary ??. To show transitivity, let us assume (A_{1},L_{1}) ≲_{CP1}(A_{2},L_{2}) and (A_{2},L_{2}) ≲_{CP1}(A_{3},L_{3}). According to Definition ??, because of (A_{1},L_{1}) ≲_{CP1}(A_{2},L_{2}), we have L_{1}∈ �_{Π} — and then immediately the desired (A_{1},L_{1}) ≲_{CP1}(A_{3},L_{3}) — or we have L_{2} ∉ �_{Π} and every H ⊆ �_{Π} that is an activation set for (A_{1},L_{1}) is also an activation set for (A_{2},L_{2}). The latter case excludes the first option in Definition ?? as a justification for (A_{2},L_{2}) ≲_{CP1}(A_{3},L_{3}), and thus we have L_{3} ∉ �_{Π} and every H ⊆ �_{Π} that is an activation set for (A_{2},L_{2}) is also an activation set for (A_{3},L_{3}). All in all, we get that every H ⊆ �_{Π} that is an activation set for (A_{1},L_{1}) is also an activation set for (A_{3},L_{3}). Thus, we get the desired (A_{1},L_{1}) ≲_{CP1} (A_{3},L_{3}) also in this case. Q.e.d. (Theorem ??)

Obviously, an argument is ranked by ≲_{CP1}firstly on whether its literal is in �_{Π} , and, if not, secondly on the set of its activation sets, which is an element of the power set of the power set of �_{Π} . So we get:

Corollary 6 If �_{Π} is finite, then <_{CP1}is well-founded.

6.5 Relation between the Specificity Relations P3 and CP1

Theorem 3 Let Π^{<2} be the set of rules from Π that are unconditional or have exactly one literal in the conjunction of their condition. Let Π^{≥2} be the set of rules from Π with more than one literal in their condition. ≲_{P3}⊆ ≲_{CP1}holds if one (or more) of the following conditions hold:

1. For every H ⊆ �_{Π} and for every set A of ground instances of rules from Δ, and for �:= �_{H∪A ∪Π^{G}} , we have �_{�∪Π} ⊆ �∪ �_{Π} .

2. For each instance L ⇐ L′_{0}∧ ...∧L′_{n+1} of each rule in Π^{≥2} with L∉ �_{Π^{<2}} , we have L′_{j} ∉ �_{Π^{<2}} for all j ∈ {0,...,n+ 1}.

3. For each instance L ⇐ L′_{0}∧ ...∧L′_{n+1} of each rule in Π^{≥2}, we have L′_{j} ∉ �_{Π} for all j ∈ {0,...,n+ 1}.

4. We have Π^{≥2} = ∅.

Note that if we had improved ≲_{P3}only w.r.t. phase 1 of §??, but not w.r.t. phase 3 in addition, then Theorem ?? would not require any condition at all (see the proof!). This means that a condition becomes necessary by our correction of simplified activation sets to non-simplified ones, but not because of the major changes (A) and (B) of §??.

Proof of Theorem ?? First let us show that condition 2 implies condition 1. To this end, let H ⊆ �_{Π} , let A be a set of ground instances of rules from Δ, and set � := �_{H∪A ∪Π^{G}} . For an argumentum ad absurdum, let us assume �_{�∪Π} ⊈ �∪ �_{Π} . Because of Π^{F}⊆ �_{Π^{<2}} , we have �∪ Π = �∪ Π^{F}∪ Π^{G} ⊆ �∪ �_{Π^{<2}} ∪ Π^{G}, and thus �_{�∪Π} ⊆ �_{�∪�_{Π^{<2}} ∪Π^{G}} , and thus �_{�∪�_{Π^{<2}} ∪Π^{G}} ⊈ �∪ �_{Π^{<2}} (because otherwise �_{�∪Π} ⊆ �_{�∪�_{Π^{<2}} ∪Π^{G}} ⊆ �∪ �_{Π^{<2}} ⊆ �∪ �_{Π} ). Now � is closed under Π^{G} by definition. Moreover, �_{Π^{<2}} is closed under Π^{<2} by definition and under Π^{≥2} by condition 2. Because both of the sets of literals � and �_{Π^{<2}} are closed under Π^{G} — but nevertheless their union is not closed under Π^{G} according to �_{�∪�_{Π^{<2}} ∪Π^{G}} ⊈ �∪ �_{Π^{<2}} — there must be an inference step essentially based on both sets in parallel. More precisely, this means that there must be an instance L ⇐ L′_{1}∧ ...∧L′_{n} of a rule from Π^{G} with L ∉ �∪ �_{Π^{<2}} , and some i,j ∈ {1,...,n} with L′_{i}∈ �\�_{Π^{<2}} and L′_{j} ∈ �_{Π^{<2}} \�. Then L ⇐ L′_{1}∧ ...∧L′_{n} must actually be an instance of a rule from Π^{≥2}, and L∉ �_{Π^{<2}} , but L′_{j}∈ �_{Π^{<2}} in contradiction to condition 2.

As condition 2 implies condition 1, condition 3 trivially implies condition 2, and condition 4 trivially implies condition 3, it now suffices to show the claim that (A_{1},L_{1}) ≲_{CP1} (A_{2},L_{2}) holds under condition 1 and the assumption of (A_{1},L_{1}) ≲_{P3} (A_{2},L_{2}). By this assumption, (A_{1},L_{1}) and (A_{2},L_{2}) are arguments and L_{2}∈ �_{Π} implies L_{1}∈ �_{Π} . If L_{1}∈ �_{Π} holds, then our claim holds as well. Otherwise, we have L_{1},L_{2} ∉ �_{Π} , and it suffices to show the sub-claim that H is an activation set for (A_{2},L_{2}) under the additional sub-assumption that H ⊆ �_{Π} is an activation set for (A_{1},L_{1}). Under the sub-assumption we also have H ⊆ �_{Π∪Δ} because of �_{Π} ⊆ �_{Π∪Δ} , and, for �:= �_{H∪A_{1}∪Π^{G}} , we have L_{1}∈ �_{�∪Π} , and then, by condition 1, L_{1} ∈ �∪ �_{Π} . Then, by our current case of L_{1},L_{2} ∉ �_{Π} , we have L_{1}∈ �. Thus, H is a simplified activation set for (A_{1},L_{1}).

Let us now provide an argumentum ad absurdum for the assumption that H is a simplified activation set also for (∅,L_{1}): Then we would have L_{1}∈ �_{H∪Π^{G}} , and because of H ⊆ �_{Π} and Π^{G}⊆ Π we get L_{1}∈ �_{�_{Π} ∪Π} = �_{Π} — a contradiction to our current case of L_{1},L_{2} ∉ �_{Π} .

All in all, by our initial assumption, H must now be a simplified activation set for (A_{2},L_{2}) and, a fortiori by Corollary ??, an activation set for (A_{2},L_{2}), as was to be shown for our only remaining sub-claim. Q.e.d. (Theorem ??)

6.6 Checking Up the Previous Examples

With the help of Theorem ??, we can now analyze the examples of §??, and also check how our relation CP1 behaves in case of our counterexample to transitivity. Note that condition 4 of Theorem ?? is satisfied for all of these examples.

Example 7 (continuing Example ?? of §??) We have (A_{2},flies(edna)) ≴_{CP1}(∅,¬flies(edna))

because flies(edna)∉ �_{Π??} and ¬flies(edna)∈ �_{Π??} .

We have (∅,¬flies(edna)) ≲_{P3}(A_{2},flies(edna)) by Corollary ??(3).

All in all, by Theorem ??, we get (∅,¬flies(edna))<_{CP1}(A_{2},flies(edna)) and (∅,¬flies(edna)) <_{P3} (A_{2},flies(edna)).

Remark 6 One may ask why we did not define an additional quasi-ordering, say ≲_{CP0}, simply by replacing the two conditions of Definition ?? with the single condition

“L_{2}∈ �_{Π} implies L_{1}∈ �_{Π} , and every H ⊆ �_{Π} that is an [minimal] activation set for (A_{1},L_{1}) is also an activation set for (A_{2},L_{2}).”

This would be more in the style of Definition ?? for ≲_{P3}, and would also avoid the singular behavior of the first alternative condition of Definition ??, and so offer continuity advantages.^{27} Moreover, for ≲_{CP0} instead of ≲_{CP1}, items 1 and 2 (but not item 3) of Corollary ?? still hold, as well as Theorem ?? and its Corollary ??. Furthermore, we get ≲_{CP0} ⊆ ≲_{CP1}. It is fatal for ≲_{CP0}, however, that this subset relation may be proper. For instance, ≲_{CP0} does not in general satisfy Theorem ??. Even worse, ≲_{CP0} does not show the proper behavior of ≲_{CP1}in Example ?? of §??, as discussed in Example ?? of §??:

27 Cf. the discussion of such a continuity advantage in §?? for the monotonicity w.r.t. conjunction.

We get (∅,¬flies(edna)) △_{CP0}(A_{2},flies(edna)) instead of (∅,¬flies(edna)) <_{CP1} (A_{2},flies(edna)).

This can be seen by considering the activation set ∅ for (∅,¬flies(edna)), which is not an activation set for (A_{2},flies(edna)).

Such a behavior is obviously unacceptable in practice, and so we do not think that it makes sense to consider ≲_{CP0}any further.

Example 8 (continuing Example ?? of §??) We have (A_{2},flies(edna)) ≴_{CP1}(A_{1},¬flies(edna)) because flies(edna)∉ �_{Π??} and because {bird(edna)} ⊆ �_{Π??} is an activation set for (A_{2},flies(edna)), but not for (A_{1},¬flies(edna)).

We have (A_{1},¬flies(edna)) ≲_{P3}(A_{2},flies(edna)), because flies(edna)∉ �_{Π??} and because, if H ⊆ �_{Π?? ∪Δ??} is a simplified activation set for (A_{1},¬flies(edna)), but not for (∅,¬flies(edna)), then we have emu(edna)∈ H, and thus H is a simplified activation set also for (A_{2},flies(edna)).

All in all, by Theorem ??, we get (A_{1},¬flies(edna)) <_{CP1}(A_{2},flies(edna)) and (A_{1},¬flies(edna)) <_{P3} (A_{2},flies(edna)).

Example 9  (continuing Example ?? of §??)

We have (A_{2},flies(edna)) ≲_{CP1}(A_{1},¬flies(edna)) because ¬flies(edna)∉ �_{Π??} and, for every activation set H ⊆ �_{Π??} for (A_{2},flies(edna)), we get emu(edna)∈ H, and so H is an activation set also for (A_{1},¬flies(edna)).

Nevertheless, we have (A_{2},flies(edna)) ≴_{P3}(A_{1},¬flies(edna)) , because {bird(edna)} ⊆ �_{Π?? ∪Δ??} is a simplified activation set for (A_{2},flies(edna)), but neither for (∅,flies(edna)), nor for (A_{1},¬flies(edna)).

We have (A_{1},¬flies(edna)) ≲_{P3}(A_{2},flies(edna)), because of flies(edna)∉ �_{Π??} and because, if H ⊆ �_{Π?? ∪Δ??} is a simplified activation set for (A_{1},¬flies(edna)), but not for (∅,¬flies(edna)), then we have emu(edna)∈ H and thus H is a simplified activation set also for (A_{2},flies(edna)).

All in all, by Theorem ??, we get (A_{1},¬flies(edna)) ≈_{CP1}(A_{2},flies(edna)) and (A_{1},¬flies(edna)) <_{P3} (A_{2},flies(edna)).

From a conceptual point of view, we have to ask ourselves, whether we would like the two defeasible rule instances in A_{2} = { flies(edna)← bird(edna), bird(edna)← emu(edna) } to reduce the specificity of (A_{2},flies(edna)) as compared to a system that seems equivalent for the given argument for flies(edna), namely the argument ({flies(edna)← emu(edna)},flies(edna)).

Does the specificity of a defeasible reasoning step really reduce if we introduce intermediate literals (such as bird(edna) between flies(edna) and emu(edna)) ?

According to human intuition, this question has a negative answer, as we have already explained in Remark ?? at the end of §??.^{28}

Example 10  (continuing Example ?? of §??)

We have (A_{2},lovely)≴_{CP1}(A_{1},¬lovely) because lovely∉ �_{Π??} and because {somebody} ⊆ �_{Π??} is an activation set for (A_{2},lovely), but not for (A_{1},¬lovely).

We have (A_{1},¬lovely)≲_{P3}(A_{2},lovely) because of lovely∉ �_{Π??} and because, if H ⊆ �_{Π??∪Δ??} is a simplified activation set for (A_{1},¬lovely), but not for (∅,¬lovely), then we have {somebody,noisy} ⊆ H, and so H is also a simplified activation set for (A_{2},lovely).

28 Moreover, Examples ?? and ?? will exhibit a strong reason to deny this question: the requirement of monotonicity w.r.t. conjunction. Furthermore, see Example ?? for another example that makes even clearer why defeasible rules should be considered for their global semantic effect instead of their syntactic fine structure.

All in all, by Theorem ??, we get (A_{1},¬lovely)<_{CP1}(A_{2},lovely) and (A_{1},¬lovely) <_{P3} (A_{2},lovely).

Note that we can nicely see here that the condition that H is not a simplified activation set for (∅,¬lovely) is relevant in Definition ??. Without this condition we would have to consider the simplified activation set {grandpa} for (A_{1},¬lovely), which is not an activation set for (A_{2},lovely); and so, contrary to our intuition, (A_{1},¬lovely) would not be more specific than (A_{2},lovely) w.r.t. ≲_{P3} anymore.

Example 11 (continuing Example ?? of §??) The following holds for our specification of Example ?? by Lemma ?? and Corollary ??:

(A_{1},Propose) <_{P3}(A_{2},Kiss) <_{P3}(A_{3},Smile) ≵_{P3}(A_{1},Propose).

For our corrected relation CP1 we have:

(A_{1},Propose) <_{CP1}(A_{2},Kiss) <_{CP1}(A_{3},Smile) >_{CP1}(A_{1},Propose)

simply because the trouble-making set {Bold, Promising(Jo)} is not to be considered here. Indeed, this set is not a subset of �_{Π??} . The checking of the details is left to the reader. Note that, because of Lemma ??, Theorem ??, Theorem ??, and Corollary ??, all that is actually left to show is (A_{1},Propose) ≵_{CP1}(A_{2},Kiss) ≵_{CP1}(A_{3},Smile).

7 Putting Specificity to Test w.r.t. Human Intuition

Before we will go on with further conceptual material and efficiency considerations in §??, let us put our two main notions of specificity — as formalized in the two binary relations ≲_{P3} and ≲_{CP1} — to test w.r.t. our changed phase 1 of §?? in a series of further examples.

Note that we can freely draw the consequence ≲_{P3}⊆ ≲_{CP1} of Theorem ?? because at least one^{29} of its conditions is satisfied in all the following examples except Example ??, which is the only example in §?? with an activation set that actually is not a simplified one.

Besides freely applying Theorem ?? — to enable the reader to make his own selection of interesting examples — we are pretty explicit in all of the following examples.

7.1 Monotonicity of the Specificity Relations w.r.t. Conjunction

Monotonicity w.r.t. conjunction is the following property for a binary relation R on argu-

ments: In case of  (A_{1}^{i},L_{1}^{i}) R(A_{2}^{i},L_{2}^{i})  for i∈ {1,2}, we always have (A_{1}^{1}∪A_{1}^{2},L′_{1}) R(A_{2}^{1}∪A_{2}^{2},L′_{2})

for fresh constant literals L′_{j} with rules L′_{j}⇐ L_{j}^{1}∧L_{j}^{2} added to the general rules Π^{G}(j ∈ {1,2}). In this case, we will call (A_{j}^{1}∪A_{j}^{2},L′_{1}) the conjunction of the arguments (A_{j}^{1},L_{j}^{1})and (A_{j}^{2},L_{j}^{2}).

This property is obviously given for ≲_{CP1}in case of L_{1}^{1},L_{1}^{2}∈ �_{Π} (which implies L′_{1}∈ �_{Π} ) and also in case of L_{1}^{1},L_{1}^{2} ∉ �_{Π} (where we get L_{2}^{1},L_{2}^{2},L′_{1},L′_{2} ∉ �_{Π} ). Note that the latter case — where both arguments are defeasible — is certainly the most important one.

For the remaining borderline case of L_{1}^{i} ∉ �_{Π} ∋ L_{1}^{3−i} (for some i∈ {1,2}), however, monotonicity cannot be expected in general for ≲_{CP1}, simply because then we get L′_{1} ∉ �_{Π} , but do not necessarily have any activation set for L_{2}^{3−i}. This non-monotonicity, however, is part and parcel of our decision to prefer arguments whose literals are elements of �_{Π} , as expressed in item 1 of Definition ?? of §??. As explained in Remark ?? of §??, there does not seem to be an alternative to this technically required preference.

29 Condition 4 of Theorem ?? is satisfied for Examples ??, ??, ??, and ??. Condition 3 (but not condition 4)

is satisfied for Examples ??, ??, ??, ?? and ??.

For ≲_{P1}, however, monotonicity is not even given for the case we just realized to be the most important one. This was already noted in (?), using the following example.

Example 12 (Example 6 of (?))

Π??^{F} := { a, d },
Π??^{G} := \{ \begin{matrix}g_{1} ⇐ ¬c∧¬f, \\ g_{2} ⇐ c∧f \end{matrix} \} ,
Δ?? := A_{1} ∪ A_{2}.
A_{1} := \{ \begin{matrix}¬c ← a, \\ ¬f ← d \end{matrix} \} .

A_{2} := \{ \begin{matrix}b ← a, \\ c ← b, \\ e ← d, \\ f ← e \end{matrix} \} .

g_{1}

g_{2}

¬c  c  f  ¬f

\underline{\underline{a}}  b  e  \underline{\underline{d}} A1 A1 A2 A2 A2 A2

Let us compare the specificity of the arguments (A_{1},g_{1}) and (A_{2},g_{2}).

We have (A_{1},g_{1}) ≈_{CP1} (A_{2},g_{2}) because H ⊆ �_{Π??} = {a,d} is an activation set for (A_{i},g_{i}) if and only if H = {a,d}.

We have (A_{1},g_{1})△_{P3}(A_{2},g_{2}) for the following reasons: {a,¬f} ⊆ �_{Π??∪Δ??} is a simplified activation set for (A_{1},g_{1}), but neither for (∅,g_{1}), nor for (A_{2},g_{2}). {a,f} ⊆ �_{Π??∪Δ??} is a simplified activation set for (A_{2},g_{2}), but neither for (∅,g_{2}), nor for (A_{1},g_{1}).

? considers the same result for ≲_{P1} as for ≲_{P3} to be “seemingly unintuitive”, because, as we have seen for the isomorphic sub-specification in Example ?? of §??, we have both (A_{1},¬c) <_{P3}(A_{2},c) and (A_{1},¬f) <_{P3}(A_{2},f).

Indeed, as already listed as an essential requirement in §??, the conjunction of two respectively more specific arguments should be more specific.

On the other hand, considering ≲_{CP1}instead of ≲_{P3}, the conjunctions of two respective arguments that are pairwise equivalently specific are equivalently specific — exactly as one intuitively expects. Indeed, from the isomorphic sub-specifications in Example ??, we know that (A_{1},¬c) ≈_{CP1}(A_{2},c) and (A_{1},¬f) ≈_{CP1}(A_{2},f).

By turning the defeasible rule b← a of Example ?? into a strict general rule, we obtain the following example.

Example 13 (1^{st}Variation of Example ??)

Π??^{F} := { a, d },
Π??^{G} := \{ \begin{matrix}g_{1} ⇐ ¬c∧¬f, \\ g_{2} ⇐ c∧f, \\ b ⇐ a \end{matrix} \} ,
Δ?? := A_{1} ∪ A_{2}.
A_{1} := \{ \begin{matrix}¬c ← a, \\ ¬f ← d \end{matrix} \} .
A_{2} := \{ \begin{matrix}c ← b, \\ e ← d, \\ f ← e \end{matrix} \} .

g_{1}

g_{2}

¬c  c  f  ¬f

\underline{\underline{a}}  b  e  \underline{\underline{d}} A1 A1 A2 A2 A2

Let us compare the specificity of the arguments (A_{1},g_{1}) and (A_{2},g_{2}).

We have (A_{2},g_{2}) ≴_{CP1}(A_{1},g_{1}) because {b,d} ⊆ �_{Π??} = {a,b,d} is an activation set for (A_{2},g_{2}), but not for (A_{1},g_{1}).

We have (A_{1},g_{1}) ≲_{CP1} (A_{2},g_{2}) because, for every activation set H ⊆ �_{Π??} for (A_{1},g_{1}), we have {a,d}⊆ H; and so H is also an activation set for (A_{2},g_{2}).

We again have (A_{1},g_{1}) △_{P3}(A_{2},g_{2}), for the same reason as in Example ??. Thus, the situation for ≲_{P3} is just as in Example ??, and just as “seemingly unintuitive” for exactly the same reason.

We have (A_{1},g_{1}) <_{CP1}(A_{2},g_{2}), which is intuitively correct because the conjunction of a more specific and an equivalently specific argument, respectively, should be more specific. Indeed, from the isomorphic sub-specifications in Examples ?? and ??, we know that (A_{1},¬c) <_{CP1}(A_{2},c) and (A_{1},¬f) ≈_{CP1}(A_{2},f), respectively.

All in all, the relation ≲_{P3} fails in this example again, whereas the quasi-ordering ≲_{CP1} works according to human intuition and satisfies monotonicity w.r.t. conjunction.

7.2 Implementation of the Preference of the “More Precise”

As primary sources of differences in specificity, all previous examples — except Example ?? of §??, continued in Example ?? of §?? — illustrate only the effect of chains of implications. According to our motivating discussion of §??, we should consider also examples where the primary source of differences in specificity is an essentially required condition that is a super-conjunction of the condition triggering another rule. We will do so in the following examples.

As we have already shown in Example ??, both relations ≲_{P3} and ≲_{CP1} produce the intuitive result if the “more precise” super-conjunction is directly the condition of a rule. Let us see whether this is also the case if the condition of the rule is derived from a superconjunction.

By removing the second condition literal ¬f in the strict general rule g_{1}⇐ ¬c∧¬f of Example ??, we obtain the following example.

Example 14 (2^{nd}Variation of Example ??)

Π??^{F} := { a, d },
Π??^{G} := \{ \begin{matrix}g_{1} ⇐ ¬c, \\ g_{2} ⇐ c∧f \end{matrix} \} ,
Δ?? := A_{1} ∪ A_{2}.
A_{1} := { ¬c ← a }.

A_{2} := \{ \begin{matrix}b ← a, \\ c ← b, \\ e ← d, \\ f ← e \end{matrix} \} .

g_{1}  g_{2}

¬c  c  f

\underline{\underline{a}}  b  e  \underline{\underline{d}} A1 A2 A2 A2 A2

Let us compare the specificity of the arguments (A_{1},g_{1}) and (A_{2},g_{2}).

We have (A_{1},g_{1}) ≴_{CP1}(A_{2},g_{2}) because {a} ⊆ �_{Π??} = {a,d} is an activation set for (A_{1},g_{1}), but not for (A_{2},g_{2}).

We have (A_{2},g_{2}) ≲_{CP1}(A_{1},g_{1}) because any activation set for (A_{2},g_{2}) that is a subset of �_{Π??} includes a, and so is also an activation set for (A_{1},g_{1}).

Considering Theorem ?? as well as the the activation set {b,d} for (A_{2},g_{2}),

we get  (A_{1},g_{1}) △_{P3} (A_{2},g_{2}),
contrary to (A_{1},g_{1})>_{CP1} (A_{2},g_{2}).

Thus, ≲_{CP1} realizes the intuition that the super-conjunction a∧d — which is essential to derive c∧f according to A_{2} — is more specific than the “less precise” a.

Just like Example ?? of §??, this example shows again that ≲_{P3} does not properly implement the intuition that — in a model-theoretic approach to specificity — defeasible rules should be considered for their global semantic effect instead of their syntactic fine structure.

28  Claus-Peter Wirth, Frieder Stolzenburg

Example 15 (Example 11 from (?, p. 96))

Π??^{F} := { c, d, e },
Π??^{G} := { x ⇐ a∧f },
Δ?? := A^{1} ∪ A^{2} ∪ A^{3} ∪ A^{4}∪ A^{5}.
A^{1} := { x ← a∧b∧c }.
A^{2} := { ¬x ← a∧b }.
A^{3} := { f ← e }.

\begin{aligned}A^{4} & := & \{ a ← d \}. \\ A^{5} & := & \{ b ← e \}. \end{aligned}

x  x

¬x

a  b  f

\underline{\underline{d}}  \underline{\underline{c}}  \underline{\underline{e}} A 1 A 1 A 1 A 2 A 2 A 3 A 4 A 5

Compare the specificity of the arguments (A^{1}∪A^{4}∪A^{5},x), (A^{2}∪A^{4}∪A^{5},¬x), (A^{3}∪A^{4},x) !

We have (A^{1}∪A^{4}∪A^{5},x) <_{CP1}(A^{2}∪A^{4}∪A^{5},¬x) ≈_{CP1}(A^{3}∪A^{4},x), because of x,¬x∉ �_{Π??} , and because any activation set H ⊆ �_{Π??} = {c,d,e} for any of (A^{1}∪A^{4}∪A^{5},x), (A^{2}∪A^{4}∪A^{5},¬x), (A^{3}∪A^{4},x) contains {d,e}, which is an activation set only for the latter two.

This matches our intuition well, because the first of these arguments essentially requires the “more precise” c∧d∧e instead of the less specific d∧e.

We have (A^{1}∪A^{4}∪A^{5},x) △_{P3} (A^{2}∪A^{4}∪A^{5},¬x) △_{P3} (A^{3}∪A^{4},x) △_{P3} (A^{1}∪A^{4}∪A^{5},x), however. This means that ≲_{P3} cannot compare these counterarguments and cannot help us to pick the more specific argument.

What is most interesting under the computational aspect is that, for realizing

(A^{1}∪A^{4}∪A^{5},x) ≴_{P3}(A^{2}∪A^{4}∪A^{5},¬x),

we have to consider the simplified activation set {d,f}⊆ �_{Π??∪Δ??} for (A^{1}∪A^{4}∪A^{5},x). This means that here — to realize that f ∈ �_{Π??∪Δ??} — we have to take into account the

defeasible rule of A^{3}, which is not part of any of the two arguments under comparison.^{30}

Note that such considerations are not required, however, for realizing the properties of ≲_{CP1}, because defeasible rules not in the given argument can be completely ignored when calculating the minimal activation sets as subsets of �_{Π} instead of �_{Π∪Δ} . In particular, the complication of pruning — as discussed in detail in (?, § 3.3) — does not have to be considered for the operationalization of ≲_{CP1}.

By turning the defeasible rule f← e of Example ?? into a strict general rule, we obtain the following example.

Example 16 (Variation of Example ??)

30 Have a look at Figure ?? in §?? to see that the effect of f proceeds here only via the set F, but not via the usage of the set H at the bottom of Figure ??.

A Series of Revisions of David Poole’s Specificity  29

Π??^{F} := { c, d, e },
Π??^{G} := \{ \begin{matrix}x ⇐ a∧f, \\ f ⇐ e \end{matrix} \} ,
Δ?? := A^{1} ∪ A^{2} ∪ A^{4}∪ A^{5},
A^{1} := { x ← a∧b∧c }.
A^{2} := { ¬x ← a∧b }.
A^{4} := { a ← d },
A^{5} := { b ← e }.

x  x

¬x

a  b  f

\underline{\underline{d}}  \underline{\underline{c}}  \underline{\underline{e}} A 1 A 1 A 1 A 2 A 2 A 4 A 5

Compare the specificity of the arguments (A^{1}∪A^{4}∪A^{5},x), (A^{2}∪A^{4}∪A^{5},¬x), (A^{4},x) !

Obviously, x,¬x ∉ �_{Π??} = {c,d,e,f}. Moreover, {d} ⊆ �_{Π??} is an activation set for (A^{4},x) (but not a simplified one!) and, a fortiori (by Corollary ??(1)), for (A^{1}∪A^{4}∪A^{5},x), but not for (A^{2}∪A^{4}∪A^{5},¬x). Furthermore, every activation set H ⊆ �_{Π??} for (A^{2}∪A^{4}∪A^{5},¬x) satisfies {d,e}⊆ H, which is an activation set for (A^{4},x) and (A^{1}∪A^{4}∪A^{5},x). Finally, every activation set H ⊆ �_{Π??} for (A^{1}∪A^{4}∪A^{5},x) satisfies {d} ⊆ H which is an activation set for (A^{4},x).

All in all, we have (A^{4},x) ≈_{CP1}(A^{1}∪A^{4}∪A^{5},x) >_{CP1}(A^{2}∪A^{4}∪A^{5},¬x).

This is intuitively sound because (A^{2}∪A^{4}∪A^{5},¬x) is activated only by the more specific d∧e, whereas (A^{4},x) is activated also by the “less precise” d.

Moreover, c∧d∧e is not essentially required for (A^{1}∪A^{4}∪A^{5},x), and so this argument is tantamount to (A^{4},x). The reason for this remarkable effect is not the lack of minimality of the argument (A^{1}∪A^{4}∪A^{5},x), but our semantic, model-theoretic approach, which simply ignores the fact that the derivation via A^{1} requires the more precise activation set. Indeed, we primarily consider consequence, not derivation.

We have (A^{4},x) <_{P3} (A^{1}∪A^{4}∪A^{5},x) △_{P3} (A^{2}∪A^{4}∪A^{5},¬x) △_{P3} (A^{4},x), however. This means that ≲_{P3} fails here completely w.r.t. Poole’s intuition, as actually in most non-trivial examples.

7.3 Conflict between the “More Concise” and the “More Precise”

By removing the second condition literal ¬f in the strict general rule g_{1}⇐ ¬c∧¬f of Example ??, we obtain the following example.

Example 17 (Variation of Example ??)

Π??^{F} := { a, d },
Π??^{G} := \{ \begin{matrix}g_{1} ⇐ ¬c, \\ g_{2} ⇐ c∧f, \\ b ⇐ a \end{matrix} \} ,
Δ?? := A_{1} ∪ A_{2}.
A_{1} := { ¬c ← a }.
A_{2} := { c ← b, e ← d, f ← e }.

g_{1}  g_{2}

¬c  c  f

\underline{\underline{a}}  b  e  \underline{\underline{d}} A1 A2 A2 A2

�_{Π??} = {a,b,d}. Let us compare the specificity of the arguments (A_{1},g_{1}) and (A_{2},g_{2}). We have (A_{1},g_{1})△_{CP1}(A_{2},g_{2}) for the following reasons: {a} ⊆ �_{Π??} is an activation set for for (A_{1},g_{1}), but not for (A_{2},g_{2}); {b,d} ⊆ �_{Π??} is an activation set for (A_{2},g_{2}), but not for (A_{1},g_{1}).

By Theorem ?? we also get (A_{1},g_{1}) △_{P3}(A_{2},g_{2}).

In this example the two intuitive reasons for specificity — super-conjunction (preference of the “more precise”) and implication via a strict rule (preference of the “more concise”) — are in an irresolvable conflict, which goes well together with the fact that neither ≲_{CP1}nor ≲_{P3} can compare the two arguments.

7.4 Global Effect matters more than Fine Structure

The following example nicely shows that any notion of specificity based only on single defeasible rules (without considering the context of the general strict rules as a whole) cannot be intuitively adequate.

A Series of Revisions of David Poole’s Specificity  31

Example 18 (Example from Page 95 of (?))

Π??^{F} := { q(a)},
Π??^{G} := { s(x) ⇐ q(x)},
Δ?? := \{ \begin{matrix}p(x) ← q(x), \\ ¬p(x) ← q(x)∧s(x) \end{matrix}\} ,
A_{1} := { ¬p(a) ← q(a)∧s(a) },
A_{2} := { p(a) ← q(a)}

¬p(a)  p(a)

s(a)

\underline{\underline{q(a)}} A1 A1 A2

Let us compare the specificity of the arguments (A_{1},¬p(a)) and (A_{2},p(a)).

We have (A_{1},¬p(a)) ≈_{P3}(A_{2},p(a)), because of p(a),¬p(a) ∉ �_{Π??} = {q(a),s(a)}, and because, for H ⊆ �_{Π??∪Δ??} , i ∈ {1,2}, L_{1} := ¬p(a), and L_{2} := p(a), we have the logical equivalence of H = {q(a)} on the one hand, and of H being a minimal simplified activation set for (A_{i},L_{i}) but not for (∅,L_{i}), on the other hand.

By Theorem ??, we also get (A_{1},¬p(a)) ≈_{CP1}(A_{2},p(a)).

This makes perfect sense because q(a)∧ s(a) is not at all strictly “more precise” than q(a) in the context of Π??^{G}.

Note that nothing is changed here if s(x) ⇐ q(x) is replaced by setting Π??^{G} := {s(a)}. If s(x) ⇐ q(x) is replaced by setting Π??^{G} := ∅ and Π??^{F} := {q(a),s(a)}, however, then we get both (A_{1},¬p(a)) <_{P3}(A_{2},p(a)) and (A_{1},¬p(a)) <_{CP1}(A_{2},p(a)).

This also speaks for our admission of literals (i.e. unconditional rules) to Π^{G}.^{31}

8 Efficiency Considerations and the Specificity Ordering CP2

The specificity relations P1, P2, P3, and CP1^{32} share several efficiency features, which we will highlight in this section. Moreover, we will introduce the specificity ordering CP2, a minor variation of CP1 toward more efficiency and intuitive adequacy. Finally, we will discuss further steps toward more efficiency following Herbrand’s Fundamental Theorem.

8.1 A Slight Gain in Efficiency

A straightforward procedure toward deciding the specificity relations ≲_{CP1} and ≲_{P3} between two arguments is to consider all possible activation sets from the literals in the sets �_{Π} and �_{Π∪Δ} , respectively. The effort for computing ≲_{CP1} is lower than that of ≲_{P3} because of �_{Π} ⊆ �_{Π∪Δ} , though not w.r.t. asymptotic complexity: In both cases already the number of possible (simplified) activation sets is exponential in the number of literals in the respective sets �_{Π} and �_{Π∪Δ} , because each possible subset has to be tested.

31 Cf. Note ?? of §??.

32 P1 follows (?) and can be found in this paper in Definition ?? of §??. P2 follows (?) and can be found in Definition ?? of §??. P3 respects non-defeasible arguments and can be found in Definition ?? of §??.

CP1 is our transitive relation found in Definition ?? of §??.

8.2 Comparing Derivations

To lower the computational complexity, more syntactic criteria for computing specificity were introduced in (?). These criteria refer to the derivations for the given arguments. More precisely, they refer to the and-trees of Definition ?? in §??.

8.2.1 No Pruning Required

The concept of pruning and-trees is introduced in (?, Definition 12) in this context, because, for the case of ≲_{P2}, attention cannot be restricted to derivations which make use only of the instances of defeasible rules given in the arguments. The reason for this is that the specificity notions according to (?) and (?) admit literals L in activation sets that cannot be derived solely by strict rules, i.e. L ∈ �_{Π∪Δ} \�_{Π} . Since this is not possible with the relation ≲_{CP1}, this problem vanishes with our corrected version of specificity. This problem and its vanishing are discussed in Example ?? of §??.

8.2.2 Sets of Derivatio