Disjunctive, Deductive and Active Knowledge Bases

Gerd Wagner

gw@inf.fu-berlin.de

Preprint Version 1.0 October 1994

Contents

1 General Introduction 4

2 Knowledge Representation and Reasoning 6 2.1 Knowledge Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Some Formal Properties of KSs . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.2.1 Basic Properties of Inference . . . . . . . . . . . . . . . . . . . . . . . 10 2.2.2 Basic Properties of Update . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2.3 Properties of Interaction . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2.4 Vivid Knowledge Representation and Reasoning . . . . . . . . . . . . 12

2.3 Nonmonotonicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3 Disjunctive Knowledge Bases 15 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.2 Belnap’s Epistemic States . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.2.1 Adding an S5-like Modal Operator for Definite Belief . . . . . . . . . . 19 3.2.2 Problems with Belnap’s KS . . . . . . . . . . . . . . . . . . . . . . . . 20

3.3 Disjunctive Databases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.3.1 Inclusive and Exclusive Disjunctive Information . . . . . . . . . . . . . 22 3.3.2 Adding an S5-like Modal Operator for Definite Belief . . . . . . . . . . 22

3.4 Disjunctive Fact Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.4.1 Adding an S5-like Modal Operator for Definite Belief . . . . . . . . . . 25 3.5 Exact Predicates and the Closed-World Assumption . . . . . . . . . . . . . . 26

3.5.1 Representing Three Kinds of Predicates . . . . . . . . . . . . . . . . . 27 3.6 The Disjunctive Extension of a KS . . . . . . . . . . . . . . . . . . . . . . . . 28

3.6.1 Efficient Representation . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

4 Towards an Operational Semantics of Rules 30 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.2 Deductive Knowledge Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

4.2.1 Stable Closures and Stable Models . . . . . . . . . . . . . . . . . . . . 36 4.2.2 The Immediate Consequence Operator . . . . . . . . . . . . . . . . . . 36 4.2.3 Operational and Relational Semantics of Rules . . . . . . . . . . . . . 37

4.3 Monotonic RKBs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.4 Persistent Ampliative RKBs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.5 Monotonic Ampliative RKBs . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.6 Ampliative RKBs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

4.6.1 Some Examples of Stable RKBs . . . . . . . . . . . . . . . . . . . . . 42

4.6.2 Unstable RKBs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.7 Non-Ampliative RKBs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

5 The Stable Closure Semantics for Active Knowledge Bases 45 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 5.2 Active Knowledge Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 5.3 Transforming Deductive into Active Databases . . . . . . . . . . . . . . . . . 49 5.4 Some Remarks on Update and Revision . . . . . . . . . . . . . . . . . . . . . 50 5.5 Event-Specific Action Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 5.6 Integrity Maintenance by Means of Action Rules . . . . . . . . . . . . . . . . 51

5.6.1 Enforcing Integrity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 5.6.2 Referential Integrity in RDBs . . . . . . . . . . . . . . . . . . . . . . . 52

5.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

6 Disjunctive Knowledge and Logic Programming 54

6.1 Three Fundamental Ambiguities in the Semantics of Disjunctive Logic Programs 54 6.1.1 Exclusive or Inclusive Disjunction ? . . . . . . . . . . . . . . . . . . . 54 6.1.2 Which Kind of Failure ? . . . . . . . . . . . . . . . . . . . . . . . . . . 54 6.1.3 Local versus Global Application of Rules . . . . . . . . . . . . . . . . 55

6.2 Extended Disjunctive Logic Programs . . . . . . . . . . . . . . . . . . . . . . 56 6.3 Epistemic Logic Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 6.4 The CWA in Answer Set Semantics . . . . . . . . . . . . . . . . . . . . . . . . 57 6.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

7 Solving the Steamroller, and Other Puzzles, with Extended Disjunctive Logic Programming 59 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 7.2 Introducing a First-Degree Conditional . . . . . . . . . . . . . . . . . . . . . . 60

7.2.1 Exact Predicates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 7.3 Schubert’s Steamroller . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

7.3.1 Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 7.3.2 Sketch of solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 7.3.3 The Usual Interpretation . . . . . . . . . . . . . . . . . . . . . . . . . 63

7.4 The Nonmonotonic Steamroller . . . . . . . . . . . . . . . . . . . . . . . . . . 64 7.4.1 Dealing with Exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . 64 7.4.2 Reasoning with Unknown Information . . . . . . . . . . . . . . . . . . 65 7.4.3 The Nonmonotonic Steamroller . . . . . . . . . . . . . . . . . . . . . . 65

7.5 Who killed Aunt Agatha ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 7.5.1 Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 7.5.2 Sketch of Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

7.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

8 Contraction and Revision in Vivid Knowledge Systems 68 8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 8.2 Contraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

8.2.1 Contraction in Fact Bases . . . . . . . . . . . . . . . . . . . . . . . . . 70 8.2.2 Contraction in Disjunctive Data Bases . . . . . . . . . . . . . . . . . . 70 8.2.3 Contraction in Extended Deductive Databases . . . . . . . . . . . . . 71 8.3 Consolidation and Revision . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

8.3.1 Inconsistency in Vivid Knowledge Systems . . . . . . . . . . . . . . . 72 8.3.2 Implicit Consolidation versus Consistency Maintenance . . . . . . . . 73

9 Further Topics, Open Problems 74 9.1 Planning in Active Knowledge Systems . . . . . . . . . . . . . . . . . . . . . . 74 9.2 Active Knowledge Systems and Formal Theories of Action . . . . . . . . . . . 74 9.3 Weighted Knowledge Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

Chapter 1

General Introduction

In this report, we present a collection of papers in preprint status on recent issues in the area of knowledge representation and logic programming, together with some preliminary material on related topics. Chapter 3 on the operational semantics of rules is based on joint work together with M.A. Khamsi and D. Misane. Large parts of the work presented here have been done during an extended stay at the Institut de Recherche en Informatique de Toulouse (IRIT) on invitation of Luis Farinas del Cerro and Andreas Herzig to whom I want to thank for their hospitality.

The common framework of disjunctive, deductive and active knowledge bases consists of the theory of knowledge representation and reasoning systems proposed in [Wag94a]. The following novel ideas are presented in our report:

• Show that nonmonotonicity in knowledge systems has two sources: non-persistent queries and non-ampliative inputs, and in order to formalize this, one needs an information ordering for knowledge bases.

• Explain the meaning of negation-as-failure as an operator of the input language: it corresponds to deletion, resp. contraction.

• Investigate the semantics of negation-as-failure and the CWA on the basis of disjunctive information without rules.

• Explain the relationship between extended (disjunctive) logic programs, resp. systems with strong negation, and classical logic by means of the well-motivated concept of exact predicates.

• Clarify the difference between definite and epistemic failure by introducing appropriate modal operators.

• Show how deduction rules can be interpreted as update functions operating on knowledge bases. Establish an operational semantics of rules in this way which also applies to action rules.

• Show that, mathematically, the general problem of a semantics for a set of (possibly nonmonotonic) rules does not depend on any specific logical operator, such as negationas-failure, but is rather a problem of defining appropriate common fixpoints for a set of (possibly nonmonotonic) functions. Therefore, the general version of the definition of the stable semantics should not refer to negation-as-failure (i.e. not use the Gelfond-Lifschitz transformation).

• Formalize the concept of action rules, and show its close relation to that of deduction rules.

Knowledge Representation and Reasoning

The language of knowledge systems consists of the logical operator symbols ∧, ∨, ∼, − and 1 standing for conjunction, disjunction, strong negation, weak negation and the verum, respectively; the predicate symbols p, q, r,…; the constant symbols c, d,… and variables x, y,. . .. For the sake of simplicity we shall not consider functional terms but only variables and constants.^{1} Further connectives, such as epistemic modalities, and the (possibly restricted) quantifiers ∃ and ∀ can be optionally added to the language.

An atom a is an atomic formula, it is called proper, if a ≠ 1. Literals are either atoms or strongly negated atoms, l = a|∼a. Extended literals are either literals or weakly negated literals, e = l|−l. We use a, b,…, l, k,…, e, f,…, and F, G, H,… as metavariables for atoms, literals, extended literals and formulas, respectively.^{2} A variable-free expression is called ground. The set of all proper ground atoms (resp. literals, resp. extended literals) of a given language is denoted by At (resp. Lit, resp. XLit). If not otherwise stated, a formula is assumed to be ground. If op-list is a set of logical operators, say op-list ⊆ {1, −, ∼, ∧, ∨, → , ∃, ∀,…}, then L(op-list) denotes the respective set of well-formed formulas.

With each negation a complement operation for the resp. type of literal is associated: ã = ∼a and ˜∼a = a, \overline{l} = −l and \overline{−l} = l. These complements are also defined for sets of resp. literals L ⊆ Lit, and E ⊆ XLit: L̃ = \{l̃: l ∈ L\}, resp. \overline{E} = \{\overline{e} : e ∈ E\}. We distinguish between the positive and negative elements of E ⊆ XLit by writing E^{+} := E ∩ Lit and E^{−} := {l : −l ∈ E}.

Formulas of partial logic (with two kinds of negation) can be normalized in the same manner as those of classical logic. For this purpose, DNS(F), the disjunctive normal set of a formula F, is defined as follows:

DNS(1)  = {∅}
DNS(e)  = {{e}}
DNS(F ∧ G) = {E ∪ D : E ∈ DNS(F), D ∈ DNS(G)}
DNS(F ∨ G) = DNS(F) ∪ DNS(G)

All other cases of compound formulas can be handled by the following DeMorgan-style rewrite rules:

1Therefore, we only deal with a finite Herbrand universe.

2I will frequently just say “literal” when I, precisely speaking, mean a proper ground literal.

∼(F ∨ G) ⟶ ∼F ∧ ∼G  −(F ∨ G) ⟶ −F ∧ −G
∼(F ∧ G) ⟶ ∼F ∨ ∼G  −(F ∧ G) ⟶ −F ∨ −G
∼∼F ⟶ F  − − F ⟶ F
−∼(F ∨ G) ⟶ −∼F ∨ −∼G  −∼∼F ⟶ −F
−∼(F ∧ G) ⟶ −∼F ∧ −∼G  ∼−F ⟶ F
−∼−F ⟶ −F

The disjunctive normal form of a formula G ∈ L(−, ∼, ∧, ∨) is obtained as

DNF(G) = ⋁_{E∈DNS(G)} ⋀ E

2.1 Knowledge Systems

The inference relation between knowledge bases and query formulas is not uniform, in general. Only certain formulas may make sense for representing knowledge, that is, there will be a specific representation language L_{Repr}, and a knowledge base (KB) will be a finite collection of elements of L_{Repr}, possibly constrained in some way determined by the set L_{KB} of all admissible KBs: KB ∈ L_{KB} ⊆ 2^{L_{Repr}}. Likewise, since not every formula may be appropriate as a sensible query, the set of admissible queries is specified by L_{Query}.

The basic scenario of a KS consists of two operations: an inference operation processing queries posed to the KB, and an update operation processing input formulas entered by users or by other (e.g. sensoric) information suppliers. A KS restricts the admissible inputs to elements of a specific input language L_{Input}, and an update is performed by processing the input formula in an appropriate way in order to add its information content to the KB.

In general, a KB can consist of any kind of data structures capable of representing knowledge, e.g. a set, or multiset, or sequence, of (logical) expressions, or a directed graph, etc. For the sake of simplicity, I will assume that a KB ∈ L_{KB} is a finite set of expressions from a representation language, i.e. L_{KB} ⊆ 2^{L_{Repr}}.

In order to compare knowledge bases in terms of their information content we assume that there is an information ordering ≤ between KBs such that

KB_{1} ≤ KB_{2} if KB_{2} contains at least as much information as KB_{1}.

The information ordering should be defined in terms of the structural components of knowledge bases and not in terms of higher-level notions (like derivability).^{3} The informationally empty KB will be denoted by 0. By definition, 0 ≤ KB for all KBs.

Hence, a KS is defined as a 7-tuple:^{4}

⟨ 0, ≤, L_{KB}, ⊢, L_{Query}, Upd, L_{Input} ⟩

where the inference relation ⊢ ⊆ L_{KB} × L_{Query}, together with the update operation Upd : L_{KB} × L_{Input} → L_{KB}, satisfy certain properties describing their interaction (see below), and it holds that (KS1) KB ⊢ 1, and Upd(KB, 1) = KB, for any KB ∈ L_{KB}.

3The usual way to compare the information content of two KBs in standard logic (see, e.g., the literature on belief revision), namely by means of checking the inclusion of consequences: KB_{1} ≤ KB_{2} if C(KB_{1}) ⊆ C(KB_{2}), does not work in a nonmonotonic setting.

4The formulation of a KS in terms of query and input processing was already implicitly present in Belnap’s [1977] view of a KS. In [Lev84] it was described as a ‘functional approach to knowledge representation’. In [Wag94a] the concept of KSs was further extended and proposed as an integrating framework offering a general perspective for knowledge representation and logic programming.

(KS2) Upd(KB, F) ⊢ F, for any KB ∈ L_{KB}, and for any F ∈ L_{Input} ∩ L_{Query} which is consistent with KB.

(KS3) ⟨L_{KB}, ≤, 0⟩ is a preorder (called information ordering) with least element 0 (called empty KB), satisfying the following adequacy condition:

KB_{1} ≤≥ KB_{2}  iff  ∀F ∈ L_{Input}∀G ∈ L_{Query} :
Upd(KB_{1}, F) ⊢ G ⇔ Upd(KB_{2}, F) ⊢ G

which requires that KBs are informationally indistinguishable iff they are update equivalent.^{5}

A consequence operation C is defined as usual: C(KB) = {F ∈ L_{Query} : KB ⊢ F }. Also an answer operation, taking a knowledge base and an open query, and providing the corresponding set of valid answers, can be defined in terms of the inference relation. If the knowledge base is definite, an answer is a tuple, and the set of answers to a query is a relation:

Ans(KB, F (x)) := {t : KB ⊢ F (t)}

where x is a variable (tuple) and t a term, resp. constant (tuple). In general, however, answers may be indefinite, i.e. sets of possible answer substitutions corresponding to minimal disjunctive consequences:

Ans(KB, F (x)) := min{T : KB ⊢ ⋁{F (t) : t ∈ T }}

Since it appears reasonable to require that any information entered to a KB can be queried afterwards, we shall assume that L_{Input} ⊆ L_{Query}.

We shall also allow for updates by (possibly infinite) sets of input formulas, i.e. use Upd also to denote the more general update operation

Upd : L_{KB} × 2^{L_{Input}} → L_{KB}

such that for any finite A ⊆ L_{Input}, Upd(KB, A) = Upd(KB, ⋀ A). We shall also write KB + F instead of Upd(KB, F), resp.

KB + ∑_{i=1}^{α} F_{i}

instead of (… ((KB + F_{1}) + F_{2}) + …) + F_{α}.

Example 1 (Relational Databases) A KB consisting of ground atoms corresponds to a relational database (RDB). For instance, X_{1} = {r(S), r(P), m(P, L)} may represent the information that both Peter and Susan are residents, and that Peter is married with Linda.

As a kind of natural deduction from positive facts an inference relation ⊢ between a RDB X ⊆ At and a ground formula F ∈ L(−, ∧, ∨) is defined in the following way:

(⊢ a)  X ⊢ a if a ∈ X
(⊢ −a)  X ⊢ −a if a ∉ X
(⊢ ∧) X ⊢ F ∧ G if X ⊢ F & X ⊢ G
(⊢ ∨) X ⊢ F ∨ G if X ⊢ F or X ⊢ G

5Notice that this is trivially the case whenever ≤ is antisymetric, i.e. a partial order.

This inductive definition is completed by the above DeMorgan-style rewrite rules. For instance,

Ans(X_{1}, m(x, y) ∧ r(x) ∧ −r(y)) = {⟨P, L⟩}

Updates are insertions, Upd(X, a) := X ∪ {a}, and deletions, Upd(X, −a) := X − {a}. For E ⊆ At ∪ \overline{At}, we have Upd(X, E) = X ∪ (E^{+} − E^{−}) − (E^{−} − E^{+}). For instance,

Upd(X_{1}, −m(P, L) ∧ m(P, S)) = {r(S), r(P), m(P, S)}

describes a possible transaction. The KS of relational databases, denoted by A^{−}, is then defined as

⟨∅, ⊆, 2^{At}, ⊢, L(−, ∧, ∨), Upd, At ∪ \overline{At} ⟩

If L_{Input} = At, the corresponding system will be denoted by A; if in addition L_{Query} = L(∧, ∨), the resulting system without weak negation will be denoted by A^{+}.

Example 2 (Fact Bases) A KB consisting of ground literals (viewed as positive and negative facts) is called a fact base. For instance, the fact base X = {∼b(S), m(P, L)} may represent the information that Susan is not blonde, and that Peter is married with Linda.

As a kind of natural deduction from positive and negative facts an inference relation ⊢ between a fact base X ⊆ Lit and a ground formula F ∈ L(∼, ∧, ∨) is defined in the following way:^{6}

(⊢ a)  X ⊢ a if a ∈ X
(⊢ ∼a)  X ⊢ ∼a if ∼a ∈ X
(⊢ ∧) X ⊢ F ∧ G if X ⊢ F & X ⊢ G
(⊢ ∨) X ⊢ F ∨ G if X ⊢ F or X ⊢ G

This inductive definition is completed by the DeMorgan-style rewrite rules presented above.

Updating by a literal is defined as insertion: Upd(X, l) := X ∪ {l}. The system of fact bases is then defined as

F^{+} := ⟨ ∅, ⊆, 2^{Lit}, ⊢, L(∼, ∧, ∨), Upd, Lit ⟩

If the query language does also allow for weak negation, i.e. if L_{Query} = L(−, ∼, ∧, ∨), and

(⊢ −l) X ⊢ −l if l ∉ X

the corresponding KS will be denoted by F.

In a more general setting, Upd can also be defined for weakly negated literals, namely as deletion: Upd(X, −l) := X − {l}, resp. for sets (corresponding to conjunctions) of extended literals, E ⊆ XLit, as

Upd(X, E) := X ∪ (E^{+} − E^{−}) − (E^{−} − E^{+})

The corresponding extension of F admitting extended literals as inputs, L_{Input} = XLit, will be denoted by F^{−}. For example, if we learn that Peter gets divorced from Linda and marries Susan, we perform the following update:

Upd({∼b(S), m(P, L)}, −m(P, L) ∧ m(P, S)) = {∼b(S), m(P, S)}

Such a sequence of basic inputs (insertions and deletions of atoms or literals) is also called a knowledge base transaction.

6Notice that according to (⊢ a) and (⊢ ∼a), both an atom and its complement are acceptable at the same time, and independently from each other.

Proof: We have to show that F^{+}, F and F^{−} satisfy KS1–KS3. KS1 ist satisfied by stipulation. It is easy to check that for any extended literal e ∈ XLit, Upd(X, e) ⊢ e. Hence, KS2 holds. Finally, KS3 holds trivially since the information ordering ⊆ is a partial order. □

Standard logics, such as classical or intuitionistic logic, can be viewed as special (very idealized) cases of KSs. Here, the KB consists of a (possibly infinite) set of arbitrary first order sentences, and is usually called a ‘theory’. The inference operation is monotonic. Updates are simple additions of formulas (corresponding to the extension of a set of premise formulas by adding a further premise formula separated by a comma), and the representation language is equal to the query and input language, L_{Repr} = L_{Query} = L_{Input}.

Observation 1 (Exclusive Disjunction) In addition to a standard disjunction ∨, an exclusive disjunction | can be defined in F:

F | G := (F ∧ −G) ∨ (G ∧ −F)

For instance, {p, q} ⊢ p ∨ q, but {p, q} ⊬ p | q.

2.2 Some Formal Properties of KSs

The following is a list of some fundamental properties a KS may have.

2.2.1 Basic Properties of Inference

Unique Representation

C(KB_{1}) = C(KB_{2}) ⇒ KB_{1} = KB_{2}

A standard logical system, where a KB is a set of well-formed formulas, does not enjoy the Unique Representation property. On the other hand, a relational database, for instance, is a unique representation.

In general, more information does not mean more consequences. In other words: answers are not necessarily preserved under growth of information. Queries, for which this is the case, are called persistent.

Definition 1 (Persistent Queries) A closed query formula F is called persistent if KB_{1} ⊢ F ⇒ KB_{2} ⊢ F, whenever KB_{1} ≤ KB_{2}. If all F ∈ L_{Query} are persistent, the KS and its inference relation ⊢ are called persistent. An operator of the query language is called persistent, if every query formed with it and with persistent subformulas is again persistent.

Weak negation, as an operator of the query language in F, as well as the exclusive disjunction |, are not persistent while, e.g., queries F ∈ L(∼, ∧, ∨) are persistent in F.

Constructive Inference Let L ⊆ Lit be an arbitrary set of ground literals, and ⌈L⌉ := Upd(0, L). Then ⊢ is called constructive if it satisfies (i) constructible truth, and (ii) constructible falsity, i.e. both of the following conditions,

\begin{matrix}(i) & ⌈L⌉ ⊢ F ∨ G ⇒ ⌈L⌉ ⊢ F or ⌈L⌉ ⊢ G \\ (ii) & ⌈L⌉ ⊢ ∼ (F ∧ G) ⇒ ⌈L⌉ ⊢ ∼F or ⌈L⌉ ⊢ ∼G \end{matrix}

Obviously, the first condition (of constructible truth) excludes the possibility of certain disjunctive tautologies such as the tertium non datur, F ∨∼F, whereas its negative counterpart excludes, for instance, the principle of contradiction, ∼ (F ∧ ∼F).

The next property (due to Urbas [1990]) excludes the possibility of trivial inferences, i.e. non-tautological inferences which are solely based on the form of a query and not on its content. F ∈ L_{Query} is called a non-tautology if KB ⊬ F for some KB ∈ L_{KB}.

Non-Explosive Inference ⊢ is called non-explosive if for every non-tautology F ∈ L_{Query}, and for every KB > 0, there is a variant F′ of F (obtained by uniform substitution of propositional constituents) such that KB ⊬ F′.

2.2.2 Basic Properties of Update

The first two conditions of Contraction and Permutation are well- known as so-called structural rules in Gentzen-style sequent systems. In a KS, they describe the behaviour of the update operation.

Contraction

Upd(Upd(KB, A), A) = Upd(KB, A)

Permutation

Upd(Upd(KB, A), B) = Upd(Upd(KB, B), A)

Both Contraction and Permutation follow from the property of

Update Synchronicity Upd(Upd(KB, A), B) = Upd(KB, A ∪ B)

which expresses the fact that two inputs in succession (i.e. at different time points) can be handled as one aggregated input implying that the order of inputs does not matter.

Update Monotonicity

KB_{1} ≤ KB_{2} ⇒ Upd(KB_{1}, A) ≤ Upd(KB_{2}, A)

Definition 2 (Ampliative Inputs) An input formula F is called (i) ampliative^{7} if KB ≤ Upd(KB, F), or (ii) reductive if KB ≥ Upd(KB, F). A KS and its update operation Upd are called ampliative, if all inputs F ∈ L_{Input} are ampliative.

For instance, F is ampliative while F^{−} is not simply because it may be the case that Upd(X, −l) ⊂ X. Ampliative updating can be viewed as the formal counterpart of persistent answering.

Input Completeness

∀KB_{1}, KB_{2} ∈ L_{KB}∃F ∈ L_{Input} : KB_{2} = Upd(KB_{1}, F)

A KS is input complete iff KBs are both input constructible and input destructible, i.e. both of the following conditions hold:

(i) ∀KB ∈ L_{KB}∃F ∈ L_{Input} : KB = Upd(0, F)
(ii) ∀KB ∈ L_{KB}∃F ∈ L_{Input} : Upd(KB, F) = 0

7The name is adopted from [Belnap 1977].

2.2.3 Properties of Interaction

Lemma Redundancy (alias: Cut, Transitivity)

KB ⊢ F & Upd(KB, F) ⊢ G ⇒ KB ⊢ G

Lemma Compatibility (alias Cautious Monotonicity, due to [Gab85])

KB ⊢ F & KB ⊢ G ⇒ Upd(KB, F) ⊢ G

Lemma Redundancy and Compatibility can be combined in the following condition of

Cumulativity KB ⊢ F ⇒ C(Upd(KB, F)) = C(KB)

Even stronger than Cumulativity is the following property proposed in [Gär88],

Vacuity KB ⊢ F ⇒ Upd(KB, F) = KB

2.2.4 Vivid Knowledge Representation and Reasoning

In a KS with a sophisticated inconsistency handling mechanism, it should be impossible that both a query F and its negation can ever be inferred from a KB even if the KB contains contradictory information. Let ¬ be a negation operator.

Inherent Consistency KB ⊢ ¬F ⇒ KB ⊬ F

Notice that this does not hold for classical negation. In fact, Inherent Consistency is violated by any negation satisfying the classical principle ex contradictione sequitur quodlibet, {F, ∼F } ⊢ G.

Minimal Change for Literal Expansion KB + l := Upd(KB, l) is the least extension of KB such that l can be inferred, expressed by (+1) and (+2):

(+1) KB + l ≥ KB
(+2) KB′ ≥ KB & KB′ ⊢ l ⇒ KB + l ≤ KB′

Definition 3 (Basic VKS) A KS with standard operators ∼, ∧ and ∨, satisfying Constructive and Non-Explosive Inference, and the principle of Minimal Change for Literal Expansion is called a basic vivid knowledge system (VKS).

Concerning the weak negation ‘−’ (alias negation-as-failure) it is not sufficient, in general, that F fails in order to infer −F (it is sufficient, however, in the case of definite KBs). Rather, it is necessary, i.e. weak negation satisfies Inherent Consistency: KB ⊢ −F ⇒ KB ⊬ F. If weakly negated inputs are allowed, the following postulate should be satisfied:

Minimal Change for Literal Contraction KB − l := Upd(KB, −l) is the greatest reduction of KB such that −l can be inferred, expressed by (−1) and (−2):

(−1) KB − l ≤ KB
(−2) KB′ ≤ KB & KB′ ⊢ −l ⇒ KB − l ≥ KB′

Definition 4 (VKS) A VKS is a basic VKS extended by adding a weak negation operator ‘−’ such that Inherent Consistency and Minimal Change for Literal Contraction (if weak negation is admitted in the input language) hold, and the following Closed-World reasoning principle is stipulated:

(CWA) ⟨CWA, KB⟩ ⊢ ∼p(t) if p ∈ CWA & KB ⊢ −p(t)

where CWA denotes the set of those predicate symbols of a given language which are subject to the Closed-World Assumption (i.e. which are totally represented in the knowledge base).^{8}

Alternatively, we can also define inference from ⟨CWA, KB⟩ by means of the CWA completion of KB:

CWA(KB) := Upd(KB, {∼p(t) : p ∈ CWA & KB ⊢ −p(t)

Obviously, we have ⟨CWA, KB⟩ ⊢ F iff ⟨∅, CWA(KB)⟩ ⊢ F, resp. CWA(KB) ⊢ F.

Although we do not make it a strict requirement, it seems desirable for a VKS that the following coherence^{9} property, relating weak with strong negation, holds:

Negation Coherence If KB is consistent, then KB ⊢ ∼F ⇒ KB ⊢ −F

Using both kinds of negation one can express a vivid form of the well-known Rational Monotonicity postulate,^{10} namely

KB ⊢ F & Upd(KB, G) ⊢ ∼F ⇒ KB ⊢ −G

which is a two-fold weakening of the rather unrealistic original one,

KB ⊢ F & Upd(KB, G) ⊬ F ⇒ KB ⊢ ∼G

2.3 Nonmonotonicity

The following condition of Monotonicity captures the idea that a system is considered monotonic if all consequences of a KB are preserved after it is updated by some new piece of information.^{11}

Monotonicity C(KB) ⊆ C(Upd(KB, F))

Though fundamental in the theory of standard consequence operations due to Tarski, this is too strong a requirement for KSs in general.

There are two ‘parameters’ on which Monotonicity depends: the update operation must be ampliative, and the inference relation must be persistent. If either of these conditions is violated, the resp. KS is nonmonotonic.

Observation 2 A KS is monotonic iff it is ampliative and persistent (even if its update operation is nonmonotonic).

8The Closed-World Assumption, in a less general form, was originally proposed in [Rei78]. Notice that our form of the CWA relates explicit with default-implicit falsity, i.e. strong with weak negation: an atomic sentence formed with a totally represented predicate is (explicitly) false if it is false by default, i.e. its strong negation holds if its weak negation does. A dual version for establishing the truth of an atom via the CWA can be added, as discussed in [Wag94a].

9The name is adopted from [PA92].

10This was brought to my attention by David Pearce.

11Notice that Monotonicity implies Lemma Compatibility.

For instance, A is nonmonotonic since it allows for non-persistent queries. On the other hand, DF^{+}, admitting only for ampliative inputs and persistent queries, L_{Query} = Lit^{∧}, is monotonic even though its update operation, by virtue of the inconsistency handling principle mi, is nonmonotonic.

Disjunctive Knowledge Bases

Using the general concept of a knowledge representation and reasoning system proposed in [Wag94a] we show how Belnap’s system of epistemic states can be extended by adding a second negation in the style of Negation-as-Failure. We call the resulting nonmonotonic system with two kinds of negation Disjunctive Fact Bases. We also formalize Körner’s distinction between exact and inexact predicates for epistemic states and disjunctive fact bases, and show how to obtain classical logic by declaring all predicates as exact. In the system of disjunctive fact bases, it is possible to simplify the representation of exact predicates (and reduce the complexity created by them) by means of an appropriate form of Reiter’s Closed-World Assumption (CWA). Thus, we finally distinguish between three kinds of predicates: inexact predicates, exact predicates subject to the CWA, and exact predicates not subject to the CWA.

As opposed to Belnap’s epistemic states, in disjunctive fact bases one can distinguish between exclusive and inclusive disjunctive information, and express various kinds of incomplete information which can only be queried by means of appropriate epistemic modal operators. We therefore extend the query language of DF by introducing an S5-style modal operator for definite knowledge.

3.1 Introduction

In this paper, we shall address issues of disjunctive information processing, resp. disjunctive knowledge representation and reasoning, such as the interplay between disjunctive and negative information (concerning negation-as-failure and the Closed-World Assumption), and the notion of inclusive versus exclusive disjunctive information. These issues have first been discussed in the field of disjunctive logic programming (see, e.g. [Min82, RT88, GL91, LMR92]). However, there is no generally acknowledged semantics for disjunctive logic programs, and many proposals are not based on clear logical principles but seem to be rather ad-hoc. It appears that the non-rule-related issues of disjunctive information processing are complicated by the presence of deduction rules, and a semantical account for the interplay between disjunctive, negative and deductive knowledge is hard to find. Therefore, we believe it is methodologically preferable to settle these issues in a simpler framework without rules, and this is the approach taken here.

The concept of a knowledge representation and reasoning system, or shorter: knowledge system (KS), consists essentially of two main components: an inference and an update operation manipulating knowledge bases as abstract objects,^{1} together with a set of formal properties these operations may have. In general, there are no specific restrictions on the internal structure of a knowledge base. It appears, however, that a computational design can be achieved by ‘compiling’ incoming information into some normal form rather than leaving it in the form of arbitrarily complex formulas. This is the case, for instance, in Belnap’s KS which can be considered as the paradigm for KSs.

1This with respect to KR fundamental distinction was first proposed in [Lev84] where the resp. operations are called ASK and TELL.

The concept of a KS constitutes a useful framework for the classification and comparison of various computational systems and formalisms like, e.g., relational and deductive databases, logic programs and other rule-based systems. It is more general than that of a logic (i.e. a consequence relation). A standard logic can be viewed as a special kind of KS. On the other hand, by defining the inference and update operations procedurally, KSs can serve as the basis for the operational definition of logics. For instance, by appropriate settings of certain parameters in the system of disjunctive fact bases one can obtain three-valued and classical logic, in addition to Belnap’s four-valued logic.

Both relational and deductive databases can be considered as computational paradigms of real world knowledge systems. They implement a form of nonmonotonic reasoning caused by the use of negation-as-failure refering to default-implicit negative information. On the other hand, relational and deductive databases, as well as normal logic programs, are not capable of representing and processing explicit negative information. This shortcoming has led to the extension of logic programming by adding a second negation (in addition to negation-as-failure) as proposed independently in [GL90, GL91] and in [PW90, Wag91a]. We call the general concept of an operator expressing default-implicit negative information in the style of negation-as-failure weak negation, and denote it by ‘−’, while the concept of an operator expressing explicit negative information will be called strong negation, denoted by ‘∼’. Our concept of a vivid knowledge system (VKS) is a two-fold generalization:

1. it extends already known logics, such as Belnap’s 4-valued or Nelson’s constructive logic,^{2} by adding weak negation, and

2. it extends already known knowledge systems, such as relational or deductive database systems, by adding strong negation.

In the framework of a VKS, a specific meaning is assigned to the Closed-World Assumption: if the Closed-World Assumption holds for a predicate, its weak negation implies its strong negation, in other words, an atomic sentence formed with such a predicate is already false if it is false by default.

While negation-as-failure in logic programming is only defined as an operator of the query language, i.e. on the right hand side of the turnstile, we shall propose a kind of elimination rule for negation-as-failure, thus admitting it as well on the left hand side of the turnstile, resp. as an operator of the input language. The elimination rule is defined by means of the contraction KB − F of KB by F:

\frac{KB − F ⊢ G}{KB, −F ⊢ G}

The structure of the paper is as follows: in section 2 we shall present some basic concepts of the theory of knowledge representation proposed in [Wag94a], in section 3 we formulate Belnap’s epistemic states in terms of this theory, in section 4 the system of disjunctive fact bases is defined, and in section 5 the distinction between exact and inexact predcates and the Closed-World Assumption are formalized.

2See [Bel77], resp. [AN84].

3.2 Belnap’s Epistemic States

A KS, according to Belnap, answers queries by invoking some inference mechanism, and it accepts input from a variety of sources by using an appropriate update mechanism. In such circumstances inconsistency threatens. Mr. X tells the KS that A while Mrs. Y tells it that ∼ A. Or, in a different environment, an automatic measurement yields that m > 0.3 while the subsequent confirmation attempt yields that m < 0.3. What is the KS to do ?

Possibility 1: Refuse to accept inconsistent information. However: this is unfair either to Mr. X or to Mrs. Y. Also, contradictions may not lie on the surface.

Possibility 2: Revise current beliefs in the presence of contradictions. However: it seems to be difficult to determine the proper revision policy doing justice to both Mr. X and Mrs. Y, and it seems to be even more difficult to mechanize it in a satisfactory way.

Possibility 3: Just accept contradictions and report them exactly as they were told, so the user can make up her mind.

Belnap advocates possibility 3, but emphasizes that even if the ultimate goal is possibility 2, i.e. revision, possibilty 3 is a good first step towards that goal.

In order to be able to process arbitrary input formulas F ∈ L(∼, ∧, ∨), an epistemic state has to consist of a set of fact bases (corresponding to partial interpretations, called ‘set-ups’ by Belnap), i.e. an epistemic state Y is a finite subset of 2^{Lit}, the elements of Y representing different epistemic alternatives. Following Belnap, yet formulated differently, inputs are processed as follows:

Upd_{B}(Y, l) = {X ∪ {l} : X ∈ Y }
Upd_{B}(Y, F ∧ G) = Upd_{B}(Upd_{B}(Y, F), G)
Upd_{B}(Y, F ∨ G) = Upd_{B}(Y, F) ∪ Upd_{B}(Y, G)

All other cases of compound formulas are treated by DeMorgan-like rewriting (see the rules in chapter 2).

There are two other update operations differing from Upd_{B} with respect to inconsistency handling.

Upd_{ex}(Y, F) := {X ∈ Upd_{B}(Y, F) : X ∩ X̃ = ∅}
Upd_{mi}(Y, F) := {X ∈ Upd_{B}(Y, F) : ¬∃Z ∈ Upd_{B}(Y, F), such that
(Z ∩ Z̃) ⊂ (X ∩ X̃)}

While Upd_{B} accepts inconsistent inputs in a liberally paraconsistent manner, Upd_{ex} does not accept inconsistent inputs at all. It implements the ex contradictione sequitur quodlibet (ECSQ) principle of classical logic by discarding all inconsistent epistemic alternatives. A good compromise between the hypersensitive inconsistency handling mechanism of Upd_{ex} and the too liberal Upd_{B} is the principle of minimal inconsistency proposed in [Pri89], and implemented by Upd_{mi}.

A query formula F ∈ L(∼, ∧, ∨) can be inferred from an epstemic state Y if it can be inferred from every fact base X ∈ Y:

Y ⊢ F :⟺ for all X ∈ Y : X ⊢ F,

where X ⊢ F is the inference relation of F^{+} (see ex. 1).

The process of information growth can be captured by the following notion of informational extension. An epistemic state Y′ is called an (informational) extension of Y, symbolically Y ≤ Y′, if every epistemic alternative in Y′ extends one in Y:

Definition 5 (Information Ordering) Y ≤ Y′ :⟺ ∀X′ ∈ Y′ ∃X ∈ Y : X ⊆ X′

This ordering, used in [Bel77], was also suggested in domain theory for the semantics of parallel processes (see [Plo76, Smy78]), and is sometimes called ‘Smyth ordering’.

Observation 3 ⟨2^{2^{Lit}}, ≤⟩ is a preorder with least element 0 := {∅}.

Notice that while {Lit} is informationally larger than any non-empty epistemic state Y ⊆ 2^{Lit}, the empty epistemic state is still larger:

Y ≤ {Lit} < {}

Let min Y = {X ∈ Y : ¬∃X′ ∈ Y (X′ ⊂ X)} be the restriction of Y to its minimal elements. An epistemic state Y is called minimal if Y = min Y. The collection of all minimal epistemic states forms a lattice, as shown in [KM93].

Observation 4 ⟨{Y ⊆ 2^{Lit} : Y = min Y }, ≤⟩ is a lattice order. Meet and join can be defined by Y_{1} ⊓ Y_{2} := min(Y_{1} ∪ Y_{2}), and Y_{1} ⊔ Y_{2} := min{X_{1} ∪ X_{2} : X_{1} ∈ Y_{1}, X_{2} ∈ Y_{2}}.

Definition 6 (Belnap’s KS)

B := ⟨ {∅}, ≤, Fin(2^{2^{Lit}}), ⊢, L(∼, ∧, ∨), Upd_{B}, L(∼, ∧, ∨) ⟩

is called Belnap’s KS.

We have to show that KS1–KS3 are satisfied.

KS1: Notice that obviously Y ⊢ 1, and by stipulation, Upd(Y, 1) = Y. KS2: Reflexivity is proved by induction on input formulas. Clearly, Upd(Y, l) ⊢ l, since l is added to every element of Y. For conjunctive inputs we obtain Upd(Y, F ∧ G) = (Y + F) + G ⊢ G, by the induction hypothesis, and since B is monotonic it follows from Y + F ⊢ F that (Y + F) + G ⊢ F, and hence (Y + F) + G ⊢ F ∧ G. For disjunctive inputs, Upd(Y, F ∨ G) = (Y + F) ∪ (Y + G) ⊢ F ∨ G, since for every X ∈ (Y + F), it holds by the induction hypothesis that X ⊢ F, hence X ⊢ F ∨ G, and similarly for every X ∈ (Y + G). KS3: It suffices to show that Y_{1} ≤≥ Y_{2} iff C(Y_{1}) = C(Y_{2}). This follows from the facts that 1) Y_{1} ≤≥ Y_{2} iff both have the same minimal elements, i.e. iff min Y_{1} = min Y_{2}, and 2) C(Y) = C(min Y), as shown in [KM93]. □

Claim 1 Belnap’s KS satisfies Monotonicity, i.e. C(Y) ⊆ C(Upd(Y, F)).

Proof: see [Wag94a].

Observation 5 In B, ⊢ is persistent, i.e. if Y′ ≥ Y then Y′ ⊢ F whenever Y ⊢ F for all F ∈ L(∼, ∧, ∨).

When an update takes place, the current information never decreases, in other words, the update operation of B is ampliative:

Observation 6 Y ≤ Upd_{B}(Y, F) ≤ Upd_{mi}(Y, F) ≤ Upd_{ex}(Y, F)

Let DNS(F) denote the disjunctive normal set corresponding to the disjunctive normal form of F.

Observation 7

Upd(Y, F) = {X ∪ K : X ∈ Y, K ∈ DNS(F)}

Proof: See [Wag94a]. This observation implies that Contraction and Permutation hold in B.

Claim 2 (Four-Valued Logic) Let ⊧_{4}⊆ L^{2}(∼, ∧, ∨) denote the consequence relation determined by general partial (resp. four-valued) models wrt standard truth conditions (resp. tables)^{3}, then in B

F ⊧_{4} G iff Upd(0, F) ⊢ G

Proof: From the previous observation it follows that Upd(0, F) = DNS(F). A further observation from [Wag94a] says that DNS(F) = MinMod_{4}(F). Hence, Upd(0, F) = MinMod_{4}(F). This, together with the facts that 1) propositional entailment in partial logic is determined by minimal models M ⊆ Lit, and 2) for every M ∈ MinMod_{4}(F), M ⊧_{4} G iff Upd(0, M) = {M} ⊢ G, yields the assertion. □

3.2.1 Adding an S5-like Modal Operator for Definite Belief

The query language of B can be extended by adding the modal operator B for definite belief, yielding the S5 query extension B^{5}. For X ∈ Y ⊆ 2^{Lit}, we define:^{4}

(B) X ⊢ BF  if for all X′ ∈ Y : X′ ⊢ F
(∼B) X ⊢ ∼BF if for some X′ ∈ Y : X′ ⊢ ∼F

A corresponding ‘possibility’ operator is definable:

EF := ∼B ∼F

expressing that there is some evidence in favour of F. Thus we get the following system:

B^{5} := ⟨ {∅}, ≤, Fin(2^{2^{Lit}}), ⊢, L(∼, ∧, ∨, B, E), Upd_{B}, L(∼, ∧, ∨) ⟩

Observation 8 (Definite vs. Indefinite Existence) By means of B, indefinite existential queries can be distinguished from definite ones. For instance, if

X = {{p(c), q(d)}, {p(d), q(d)}}

we obtain X ⊢ ∃xp(x) as well as X ⊢ ∃xq(x), but only X ⊢ ∃x Bq(x), whereas X ⊬ ∃x Bp(x). Gelfond [1992] proposes to use such existential queries as integrity constraints requiring that a KB knows definitely, or indefinitely, certain entities satisfying certain predicates.

3See [Wag94a].

4Strictly speaking, we should rather write Y, X ⊢ F, specifying the set of ‘possible worlds’, Y, along with the ‘actual world’ X (as usual in possible worlds semantics), instead of X ⊢ F. We prefer, however, the more economic notation, keeping the context Y in the background whenever it is clear.

3.2.2 Problems with Belnap’s KS

We briefly discuss three problems with B.

No Unique Representation

In B, epistemic states are not unique representations: C(Y) = C(Y′) does not imply that Y = Y′. For instance,

C({{p}}) = C({{p}, {p, q}})

Only the minimal elements of an epistemic state count:

C(Y) = ⋂{C(X) : X ∈ Y } = ⋂{C(X) : X ∈ min Y }

Therefore, exclusive and inclusive disjunctive information cannot be distinguished, neither by comparing the resp. information content nor by being appropriately queried. For instance,

{{p}, {q}} ≤≥ {{p}, {q}, {p, q}}
C({{p}, {q}}) = C({{p}, {q}, {p, q}})

No Disjunctive Syllogism

For instance,

Upd_{B}(0, (p ∨ q) ∧ ∼p) = {{p, ∼p}, {q, ∼p}} ⊬ q

Notice that the resulting epistemic state contains an inconsistent epistemic alternative although the input itself was consistent.

The Disjunctive syllogism holds in B_{ex}, where all inconsistent epistemic alternatives are discarded. In this system, however, if Y ⊢ l then Upd(Y, l̃) = {} yields an ‘exploded’ KB in the sense that everything follows from {}, i.e. B_{ex} is explosive. A good compromise seems to be B_{mi} which is both non-explosive and satisfies the Disjunctive Syllogism.

No Input Completeness

Finite epistemic states are input constructible in B, i.e.

∀Y ∈ Fin(2^{Fin(2^{Lit})})∃F ∈ L_{Input} : Y = Upd(0, F)

but since they are not input destructible B does not satisfy Input Completeness.

3.3 Disjunctive Databases

A Disjunctive Database is a finite collection of sets of atoms (each one describing a possible situation). For instance, if we know that Susan is a resident and that Peter is married either with Linda or with Susan, we get the following disjunctive DB:

Y_{1} = {{r(S), m(P, L)}, {r(S), m(P, S)}}

Formally, the system of Disjunctive Databases is defined as:^{5}

DA^{−} := ⟨ {∅}, ≤, Fin(2^{2^{At}}), ⊢, L(−, ∧, ∨, |), Upd, L^{∗}(−, ∧, ∨) ⟩ where the input language L^{∗}(−, ∧, ∨) excludes those formulas where an atom occurs both in the scope of an odd and an even number of negations (i.e. potentially inconsistent inputs).

5We shall use the following notation: if K^{−} is a KS allowing for weakly negated input, K is the corresponding without weak negation in the input language, and in K^{+} weak negation is also dropped from the query language.

The information ordering between disjunctive databases Y_{1}, Y_{2} ⊆ 2^{At} is defined as

Y_{1} ≤ Y_{2} :⟺  ∀X_{2} ∈ Y_{2}∃X_{1} ∈ Y_{1} : X_{1} ⊆ X_{2}, and
either (i) Y_{1} ⊆ Y_{2},
or (ii) ∃X′_{1} ∈ Y_{1}∀X_{2} ∈ Y_{2} : X′_{1} ⊉ X_{2}

According to this definition, we obtain for instance,

\begin{aligned}\{\{p\}\} & ≤ & \{\{p\}, \{p, q\}\}, but \{\{p\}\} ≱ \{\{p\}, \{p, q\}\} \\ \{\{p\}\} & ≥ & \{\{p\}, \{p, q\}, \{q\}\} \\ \{\{p\}, \{q\}\} & ≤ & \{\{p\}, \{p, q\}, \{q\}\}, but \{\{p\}, \{q\}\} ≱ \{\{p\}, \{p, q\}, \{q\}\} \end{aligned}

For Y ⊆ 2^{At},

Y ⊢ F :⟺ for all X ∈ Y : X ⊢ F

where X ⊢ F is defined in the same way as in A. Inputs are processed as follows:

(Ua) Upd(Y, a)  = {X ∪ {a} : X ∈ Y }
(U−a) Upd(Y, −a)  = {X − {a} : X ∈ Y }
(U∧) Upd(Y, F ∧ G) = Upd(Upd(Y, F), G)
(U∨) Upd(Y, F ∨ G) = Upd(Y, F) ∪ Upd(Y, G) ∪ Upd(Y, F ∧ G)

For instance, if we have Y_{1}, and we then learn that Peter or Linda is a resident, we perform the following update:

Y_{2} := Upd(Y_{1}, r(P) ∨ r(L))
= {{r(P), r(S), m(P, L)}, {r(P), r(S), m(P, S)},
{r(L), r(S), m(P, L)}, {r(L), r(S), m(P, S)},
{r(P), r(L), r(S), m(P, L)}, {r(P), r(L), r(S), m(P, S)}}

As can be easily checked, there is no married couple such that not both are residents:

Ans(Y_{2}, m(x, y) ∧ −(r(x) ∧ r(y))) = ∅

There are two answers to the query “who is a resident or married with a resident ?”,

Ans(Y_{2}, r(x) ∨ ∃y(m(x, y) ∧ r(y))) = {S, P }

although one can neither infer that Peter is a resident nor that he is married with one.

Notice that compared to B we have changed three things in DA: 1) we have weak negation (and, by definition, exclusive disjunction) in the query language, 2) we have refined the information ordering, and 3) we have modified the update operation for disjunctive inputs in order to give them an inclusive meaning.

Observation 9 ⟨2^{2^{At}}, ≤⟩ is a partial order with least element 0 := {∅}.

Proof: (Transitivity) We have to show that Y_{1} ≤ Y_{2} and Y_{2} ≤ Y_{3} implies Y_{1} ≤ Y_{3}. We write Y_{1} ≤′ Y_{2} instead of ∀X_{2} ∈ Y_{2}∃X_{1} ∈ Y_{1} : X_{1} ≤ X_{2}. Notice that ≤′ is transitive, and that from x_{2} ≰ x_{1} and x_{2} ≤ x_{3}, we can conclude for any transitive relation ≤ that x_{3} ≰ x_{1}. Assuming that Y_{1} ≤ Y_{2} and Y_{2} ≤ Y_{3}, implying Y_{1} ≤′ Y_{2} ≤′ Y_{3}, we have to consider three cases.

\underline{Case 1}: Y_{1} ⊆ Y_{2} ⊆ Y_{3}. Then obviously Y_{1} ⊆ Y_{3}, and hence Y_{1} ≤ Y_{3}. \underline{Case 2}: ∃X′_{1} ∈ Y_{1}∀X_{2} ∈ Y_{2} : X_{2} ≰ X′_{1}. Since ∀X_{3} ∈ Y_{3}∃X_{2} ∈ Y_{2} : X_{2} ≤ X_{3}, we obtain ∀X_{3} ∈ Y_{3} : X_{3} ≰ X′_{1}, and consequently, Y_{1} ≤ Y_{3}. \underline{Case 3}: ∃X′_{2} ∈ Y_{2}∀X_{3} ∈ Y_{3} : X_{3} ≰ X′_{2}. Since ∀X_{2} ∈ Y_{2}∃X_{1} ∈ Y_{1} : X_{1} ≤ X_{2}, there is X′_{1} ∈ Y_{1}, such that X′_{1} ≤ X′_{2}, and consequently ∃X′_{1} ∈ Y_{1}∀X_{3} ∈ Y_{3} : X_{3} ≰ X′_{1}, i.e. Y_{1} ≤ Y_{3}.

(Antisymmetry) It is easy to see that Y_{1} ≤ Y_{2} ≤ Y_{1} implies that Y_{1} ⊆ Y_{2} ⊆ Y_{1}, and hence Y_{1} = Y_{2}. □

3.3.1 Inclusive and Exclusive Disjunctive Information

Notice that (U∨) expresses inclusive disjunction in the following sense:

Upd(0, p ∨ q) = {{p}, {q}, {p, q}} ⊬ −p ∨ −q

Clearly, this corresponds to the standard meaning of a disjunction, expressing all three possibilities how it can be satisfied. By contrast, exclusive disjunction corresponds to

Upd(0, p|q) = {{p}, {q}} ⊢ −p ∨ −q

In DA, an inclusive disjunction contains more information than the corresponding exclusive one:

{{p}, {q}} < {{p}, {q}, {p, q}}

3.3.2 Adding an S5-like Modal Operator for Definite Belief

The query language of DA can be extended by adding the modal operator B for definite belief, yielding the S5 query extension D^{5}A. For X ∈ Y ⊆ 2^{At}, we define:

(B) X ⊢ BF  if for all X′ ∈ Y : X′ ⊢ F
(−B) X ⊢ −BF if for some X′ ∈ Y : X′ ⊢ −F

A corresponding ‘possibility’ operator is definable:

EF := −B − F

expressing that there is some evidence in favour of F. This yields

D^{5}A^{−} := ⟨ {∅}, ≤, Fin(2^{2^{At}}), ⊢, L(−, ∧, ∨, |, B, E), Upd, L^{∗}(−, ∧, ∨) ⟩

Observation 10 (Two Kinds of Failure) Besides the definite failure expressed by weak negation, KB ⊢ −F, there is also an epistemic failure in D^{5}A expressed by KB ⊢ −BF. For instance, for Y = {{p}, {p, q}}, we obtain Y ⊢ −Bq, while Y ⊬ −q.

Observation 11 (Honest and Dishonest Disjunctive Information) Knowing p∨q subsumes four cases, two of them ‘honest’ and two ‘dishonest’. In the case of a dishonest disjunction, more information is, in fact, known than expressed by the resp. disjunction:

• Honest disjunctive information:

– Only knowing p ∨ q, and nothing more about p or q.

{ {p}, {q}, {p, q} } ⊢ (p ∨ q) ∧ −Bp ∧ −Bq – Knowing that either p or q but not both, and not knowing which of them:

{{p}, {q}} ⊢ (p | q) ∧ −Bp ∧ −Bq

• Dishonest disjunctive information:

– Knowing exactly one of both items: either p, or q. This corresponds to the KB {{p}}, resp. {{q}}, and to the query p ∧ −q, resp. q ∧ −p.

– Knowing both p and q which corresponds to the KB {{p, q}}, and to the query p ∧ q.

3.4 Disjunctive Fact Bases

In a similar way as we have extended the monotonic system F^{+} to Belnap’s monotonic disjunctive KS in section 3, we now extend the nonmonotonic system F to a nonmonotonic disjunctive KS.

A disjunctive fact base is a finite collection of fact bases (each one describing a possible situation). For instance, if we know that Susan is not blonde and that Peter is married either with Linda or with Susan, we get the following KB:

Y_{1} = {{∼b(S), m(P, L)}, {∼b(S), m(P, S)}}

For Y ⊆ 2^{Lit}, inference is defined, as in B, elementwise:

Y ⊢ F :⟺ for all X ∈ Y : X ⊢ F

where X ⊢ F is inference in F, i.e. L_{Query} = L(−, ∼, ∧, ∨, |). For example,

Y_{1} ⊢ ∼b(S) ∧ (m(P, L)|m(P, S))

The information ordering between disjunctive fact bases Y_{1}, Y_{2} ⊆ 2^{Lit} is defined as

Y_{1} ≤ Y_{2} :⟺  ∀X_{2} ∈ Y_{2}∃X_{1} ∈ Y_{1} : X_{1} ⊆ X_{2}, and
either (i) Y_{1} ⊆ Y_{2},
or (ii) ∃X′_{1} ∈ Y_{1}∀X_{2} ∈ Y_{2} : X′_{1} ⊉ X_{2}

Inputs are processed as follows:

(Ul) Upd_{B}(Y, l)  = {X ∪ {l} : X ∈ Y }
(U−l) Upd_{B}(Y, −l)  = {X − {l} : X ∈ Y }
(U∧) Upd_{B}(Y, F ∧ G) = Upd_{B}(Upd_{B}(Y, F), G)
(U∨) Upd_{B}(Y, F ∨ G) = Upd_{B}(Y, F) ∪ Upd_{B}(Y, G) ∪ Upd_{B}(Y, F ∧ G)

We define the same additional update operations Upd_{mi}, and Upd_{ex}, as in B. The only difference with respect to update in B is the definition (U∨) for disjunctive inputs which renders disjunctive information now explicitly ‘inclusive’.

Example 3 If we have the above Y_{1}, and we then learn that Susan or Linda is blonde, the following update is performed:

Y_{2} := Upd_{mi}(Y_{1}, b(S) ∨ b(L))
= { {b(L), m(P, L), ∼b(S)}, {b(L), m(P, S), ∼b(S)} }
⊢ b(L)

Formally, the system of disjunctive fact bases is defined as

D_{B}F^{−} := ⟨{∅}, ≤, Fin(2^{2^{Lit}}), ⊢, L(−, ∼, ∧, ∨, |), Upd_{B}, L^{∗}(−, ∼, ∧, ∨) ⟩

Correspondingly, D_{mi}F^{−} is formed with L_{KB} = mi(Fin(2^{2^{Lit}})) and Upd_{mi}, and D_{ex}F^{−} with L_{KB} = ConsFin(2^{2^{Lit}}) and Upd_{ex}. In the sequel, if we simply write DF, resp. Upd, we mean all three systems.

The proof of KS1 and KS2 is as in the previous section for B. KS3 holds trivially since the information ordering of D_{B}F is a partial order (see the resp. observation below).

Observation 12 D_{B}F violates the principle of Coherence: if, e.g., Y = {{p, ∼p}}, then Y ⊢∼p, but Y ⊬ −p. On the other hand, Coherence holds in D_{mi}F and in D_{ex}F.

Observation 13 D_{mi}F is nonexplosive and coherent. It has (a restricted form of) the Disjunctive Syllogism. E.g.,

Upd_{mi}(0, (p ∨ q) ∧ ∼p) = {{q, ∼p}} ⊢ q, while
Upd_{mi}({{∼q}}, (p ∨ q) ∧ ∼p) = {{p, ∼p, ∼q}, {∼p, q, ∼q}} ⊬ q

This example also shows that neither Permutation nor Update Monotonicity hold in D_{mi}F.

Claim 3 (Collapse of weak and strong negation) Let Y ⊆ 2^{Lit} be consistent (i.e. contain at least one consistent possible situation description). Then, whenever Y ⊢ a ∨ ∼a, weak and strong negation coincide for a in D_{mi}F and D_{ex}F, but not in D_{B}F:

Y ⊢ ∼a iff Y ⊢ −a

Proof: Since Y is consistent, all possible situation descriptions X ∈ Y are consistent, and consequently, a ∨ ∼a is derivable from Y iff either a ∈ X or ∼a ∈ X for all X ∈ Y, subsuming three cases:

1. If all X ∈ Y contain a, then neither Y ⊢ ∼a nor Y ⊢ −a.

2. If all X ∈ Y contain ∼a, then both Y ⊢ ∼a and Y ⊢ −a.

3. Otherwise some X ∈ Y contain a, and all others contain ∼a, hence Y ⊬ ∼a, and Y ⊬ −a. □

Claim 4 A disjunctive fact base is a unique representation.

Proof: See [Wag94a].

Claim 5 DF is non-cumulative since it does not satisfy Lemma Compatibility.

Proof by a simple counter-example:

{{p}} ⊢ p ∨ q
but Upd({{p}}, p ∨ q) = {{p}, {p, q}} ⊬ −q
while {{p}} ⊢ −q  □

Notice that by the addition of weak negation to (the query and input language of) Belnap’s KS the inference operation is no longer persistent and the update operation no longer ampliative.

F^{+} F F^{−} B D_{B}F D_{ex}F D_{mi}F
Contraction √ √ √ √ √  √  √
Permutation √ √  √ √  √
Update Synchronicity √ √  √ √  √
Update Monotonicity √ √ √ √ √  √
input complete  √
Lemma Redundancy √ √ √ √ √  √  √
Lemma Compatibility √ √ √ √
ampliative √ √  √ √  √  √
persistent √  √
Unique Representation √ √ √  √  √  √
non-explosive √ √ √ √ √  √
coherent −  −  √  √
Disjunctive Syllogism − − −  √  √

Table 3.1: Properties of some KSs.

Claim 6 (Three-Valued Logic) Let ⊧_{3} denote the consequence relation determined by proper partial (resp. three-valued) models wrt standard truth conditions (resp. strong Kleene tables), and F, G ∈ L(∼, ∧, ∨). Then in D_{ex}F, it holds that

F ⊧_{3} G iff Upd(0, F) ⊢ G

Proof: If F does not have a proper partial model, then Upd(0, F) = {}, and the assertion holds trivially. Otherwise every minimal proper partial model of F corresponds to a consistent element of DNS(F), hence MinMod_{3}(F) = Upd(0, F), and the same argument as in claim 2 applies. □

3.4.1 Adding an S5-like Modal Operator for Definite Belief

The query language of DF can be extended by adding the modal operator B for definite belief, yielding the modal query extension D^{5}F. For X ∈ Y ⊆ 2^{Lit}, we define:

(B) X ⊢ BF  if for all X′ ∈ Y : X′ ⊢ F
(∼B) X ⊢ ∼BF  if for some X′ ∈ Y : X′ ⊢ ∼F
(−B) X ⊢ −BF  if for some X′ ∈ Y : X′ ⊢ −F
(−∼B) X ⊢ −∼BF if for all X′ ∈ Y : X′ ⊢ −∼F

In this setting, two different ‘possibility’ operators are definable:

EF := ∼B ∼F
CF := −B ∼F

EF captures the situation where there is some evidence in favour of F, whereas CF captures the situation where ∼F cannot be inferred, i.e. where F is – in this sense – consistent.

Formally,

D_{B}^{5}F^{−} := ⟨{∅}, ≤, Fin(2^{2^{Lit}}), ⊢, L(−, ∼, ∧, ∨, |, B, E, C), Upd_{B}, L^{∗}(−, ∼, ∧, ∨) ⟩

Observation 14 The modal operators B and E are persistent, whereas C is not.

Observation 15 (Representing and Querying the Unknown) While the problem whether some fact p is unknown in a fact base can be simply decided by answering the query −p∧−∼p this does not work in a disjunctive fact base. Instead, the indeterminacy query can be reformulated in three different versions which are also discussed in [Thi92] where they are named ‘simple’, ‘strong’, and ‘semi-strong ignorance’, respectively. In the following three examples we express complete knowledge, Bp, about p, and three different forms of incomplete knowledge, −Bq ∧ −B∼q, about q:

1. Complete ignorance wrt q represented by

{{p}} ⊢ p ∧ −q ∧ −∼q

2. Strong ignorance wrt q:

{{p}, {p, q}, {p, ∼q}} ⊢ Bp ∧ Eq ∧ E ∼q

3. Semi-strong ignorance wrt q:

{{p}, {p, ∼q}} ⊢ Bp ∧ E ∼q

or symmetrically,

{{p}, {p, q}} ⊢ Bp ∧ Eq

3.5 Exact Predicates and the Closed-World Assumption

In a VKS, three kinds of predicates can be distinguished. The first distinction, proposed by Körner in [Kör66], reflects the fact that many predicates (especially in empirical domains) have truth value gaps: neither p(c) nor ∼p(c) has to be the case for specific instances of such inexact predicates, like, e.g., color attributes which can in some cases not be determined because of vagueness.

Other predicates, e.g. from legal or theoretical domains, are exact, and we then have, for instance, m(S) ∨ ∼m(S) and even(1) ∨ ∼even(1), stating that Susan is either married or unmarried and that 1 is either an even or an uneven number. Only exact predicates can be totally represented. Therefore, the predicates subject to the CWA in a KB form a subset of EXACT, the set of all predicates declared as exact in KB. For an exact predicate p and any term t from its domain, the resp. instance of the tertium non datur (TND) holds:

KB ⊢ p(t) ∨ ∼p(t)

no matter whether p is subject to the CWA or not. For a non-CWA predicate p, this can only be achieved by adding the resp. TND instances to the KB (which is not possible in definite KSs where the input language does not allow for ∨).

Definition 7 (VKB) A vivid KB, in its general form, is a quadruple

⟨ EXACT, CWA, KB, IC ⟩

where EXACT is the set of exact predicates, CWA ⊆ EXACT specifies the predicates subject to the Closed-World Assumption, and IC ⊆ L_{Query} is a set of integrity constraints which have to be satisfied by any evolving state of the VKB.^{6} A query F is inferable from a VKB if it can be derived from the TND completion of CWA(KB) wrt EXACT and CWA. Formally,

⟨ EXACT, CWA, KB ⟩ ⊢ F :⟺
Upd(CWA(KB), {p(t) ∨ ∼p(t) : p ∈ EXACT − CWA, t ∈ dom(p)}) ⊢ F

where dom(p) denotes the domain of the predicate p.

Notice that in KBs of definite KSs, like fact bases, it is not possible to declare exact predicates not subject to the CWA. Therefore, in definite KSs, EXACT = CWA.

Claim 7 (Classical Logic) If all predicates are assumed to be exact, the resp. TND completion of a disjunctive fact base leads half way to classical logic. Let F, G ∈ L(∼, ∧, ∨), and ⊧_{2} denote classical consequence. Then, if all predicates occuring in F and G are exact, EXACT = Pred(F, G), and CWA is empty,

F ⊧_{2} G iff ⟨ EXACT, ∅, Upd(0, F) ⟩ ⊢ G

holds in D_{ex}F, and it also holds in D_{mi}F provided that F is consistent.

3.5.1 Representing Three Kinds of Predicates

Among the exact predicates one can further distinguish between those which are totally represented in a KB and those which are not. Exact and totally represented predicates are subject to the CWA. For example, the local KB of some city knows all residents of the city, i.e. the CWA holds for resident, but it does not know of every resident whether (s)he is married or not because (s)he might have married in another city and this information is not present. Consequently, the CWA does not apply to married in this KB.

The CWA helps to reduce disjunctive complexity which is exponential in the number of exact non-CWA predicates: if n is the number of unknown ground atoms which can be formed by means of predicates declared as exact but not subject to the CWA in VKB, then VKB contains implicitly 2^{n} possible situation descriptions.

We illustrate these distinctions with an example. Let m, r, b, l denote the predicates married, resident, blonde and is looking at, and let M, P, S stand for the individuals Mary, Peter and Susan.

VKB = \{ \begin{matrix}EXACT = \{m, r\} \\ CWA = \{r\} \\ m(M), r(M), b(M), ∼m(S), ∼b(S), l(M, P), l(P, S) \end{matrix}

The interesting queries we can ask this VKB and the resp. answers are:

1. Does a married person look at an unmarried one ? Yes, but the KB does not know who:

VKB ⊢ ∃x, y : l(x, y) ∧ m(x) ∧ ∼m(y)
Ans(VKB, l(x, y) ∧ m(x) ∧ ∼m(y)) = {{⟨M, P ⟩, ⟨P, S⟩}}
VKB ⊬ ∃x, y : B(l(x, y) ∧ m(x) ∧ ∼m(y))

6We shall not discuss integrity constraints in this paper, and therefore drop the IC component.

2. Does a resident look at a non-resident ? Yes, Mary at Peter.

Ans(VKB, l(x, y) ∧ r(x) ∧ ∼r(y)) = {{⟨M, P ⟩}}

3. Does a blonde person look at a non-blonde one ? No. The VKB is completely ignorant about the blondeness of Peter: neither is he blonde, nor is he non-blonde, nor is he blonde or non-blonde (he might be in-between):

Ans(VKB, l(x, y) ∧ b(x) ∧ ∼b(y)) = ∅

Notice that the explicit TND completion of KB wrt EXACT would yield 2^{3} = 8 possible situation descriptions, which are reduced to 2^{1} = 2 by the CWA declaration of resident.^{7}

3.6 The Disjunctive Extension of a KS

We now generalize the previous discussion of specific disjunctive knowledge systems. The disjunctive extension DK of a definite knowledge system

K = ⟨ 0, ≤, L_{KB}, ⊢, L_{Query}, Upd, L_{Input} ⟩

is defined as the KS

D_{B}K = ⟨ {0}, ≤_{d}, Fin(2^{L_{KB}}), ⊢_{d}, L_{Query}^{d}, Upd_{B}, L_{Input}^{d}⟩

where the information ordering is given by

Y_{1} ≤_{d} Y_{2} :⟺  ∀X_{2} ∈ Y_{2}∃X_{1} ∈ Y_{1} : X_{1} ≤ X_{2}, and
either (i) Y_{1} ⊆ Y_{2},
or (ii) ∃X′_{1} ∈ Y_{1}∀X_{2} ∈ Y_{2} : X′_{1} ≱ X_{2}

and for finite Y ⊆ L_{KB},

Y ⊢_{d} F :⟺ for all X ∈ Y : X ⊢ F

In the sequel, we will ommit d as superscript, resp. subscript if it is clear from context. An element X ∈ Y of a disjunctive KB Y is called a possible situation description.

Observation 16 If ⟨L_{KB}, ≤⟩ is a preorder, then ⟨2^{L_{KB}}, ≤_{d}⟩ is a partial order.

Conjunction and disjunction can be added to the input language of K, L_{Input}^{d} := L_{Input}^{∗}(∧, ∨), excluding again inputs with literals being in the scope of both an even and an odd number of weak negations,^{8} and the update operation can be inductively extended in the following way:^{9}

(Ue) Upd_{B}(Y, e)  = {Upd(X, e) : X ∈ Y }
(U∧) Upd_{B}(Y, F ∧ G) = Upd_{B}(Upd_{B}(Y, F), G)
(U∨) Upd_{B}(Y, F ∨ G) = Upd_{B}(Y, F) ∪ Upd_{B}(Y, G) ∪ Upd_{B}(Y, F ∧ G)

Besides the liberally paraconsistent system D_{B}K we also get D_{mi}K and D_{ex}K by using the update operations Upd_{mi}(Y, F) := mi(Upd_{B}(Y, F)), and Upd_{ex}(Y, F) := Cons(Upd_{B}(Y, F)).

7Without the CWA there are 3 tertium non datur disjunctions formed with m(P), r(S), and r(P), while with the CWA there is only one such disjunction: m(P) ∨ ∼m(P).

8This guarantees that Permutation holds, and consequently that (U∧) is well-defined.

9Recall that e stands for an extended literal (l or −l). All other inductive cases are handled by the above rewrite rules for complex formulas.

3.6.1 Efficient Representation

In ‘real world’ KBs the amount of disjunctive information can be expected to be small (and for reasons of computational efficiency has to be small) compared to the amount of definite information. Therefore, one should seek for possible optimizations, such as representing a disjunctive KB as a pair ⟨X, Y ⟩ where X ∈ L_{KB} contains the definite and Y ⊆ L_{KB} the disjunctive information, and for any persistent query formula F,

⟨X, Y ⟩ ⊢ F :⟺ (i) X ⊢ F, or
(ii) X ∪ X′ ⊢ F for all X′ ∈ Y

Thus, if Y ⊆ L_{KB} is a disjunctive KB, then it can be ‘folded’ into

⟨ ⋂ Y, {X − ⋂ Y : X ∈ Y } ⟩

3.7 Conclusion

We have presented natural extensions of Belnap’s system of epistemic states. First, the addition of weak negation to the query language leads to unique representations and renders it possible to express exclusive disjunctive information. Second, the adoption of the principle of minimal inconsistency leads to Coherence and the Disjunctive Syllogism. Third, the addition of exactness declarations for specific predicates leads to a kind of local Reasoning by Cases.

Towards an Operational Semantics of Rules

We develop a general closure semantics for deduction rules in knowledge bases, using the concepts of a (rule) knowledge representation and reasoning system proposed in [Wag94a] where rules are interpreted as update functions operating on knowledge bases. We define the notion of a supported closure, and we show that every ampliative rule knowledge base has a supported closure. Choosing those supported closures which satisfy a certain stability condition as the preferred (or intended) ones we obtain the stable closure semantics for rule knowledge bases (including normal, extended, disjunctive, and other logic programming and rule-based systems). The stable closure semantics can be viewed as a generalization of the stable model semantics of [GL88], since the stable closures of a normal logic program coincide with its stable models.

This chapter is based on joint work together with M.A. Khamsi and D. Misane.

4.1 Introduction

While reasoning on the basis of rule knowledge has turned out to be essential in AI, standard logics do not allow for rules as expressions of the representation language. The only possibility to process rule knowledge in a standard logic is to translate a rule expression F ← G into an implicational formula G → F of the resp. language.^{1} Such a translation, however, is only faithful in special cases. For instance, in the case of positive logic programming rules a_{0} ← a_{1} ∧ … ∧ a_{n}, it is possible to process them as implications a_{1} ∧ … ∧ a_{n} → a_{0} in classical or intuitionistic logic, or even as definite clauses ¬a_{1} ∨ … ∨ ¬a_{n} ∨ a_{0} in classical or three-valued logic, without making any difference. This is no longer the case when the rule language is more expressive, i.e. when the conclusion or the premise of a rule contain additional logical operators, such as disjunction, or negation.

Historically, this difficulty is reflected in the recent shift in logic programming semantics, abandonning earlier classical logic approaches, such as the Horn clause reading for positive logic programs, or Clark’s completion semantics for positive and normal logic programs, and seeking for new rule-oriented semantics, such as the answer set semantics of [GL90], or the partial semantics of [Wag91b], for extended logic programs. In the latter proposals, and in the proposal to be presented below, the semantics of rules does not imply the Contraposition principle, which would allow to infer ∼q from {p, ∼p ← q}. Contraposition, however, is essential in most standard semantics of implication, such as in classical, intuitionistic, or relevance logic. A notable exception where Contraposition does not hold is Nelson’s constructive logic with strong negation N, and indeed, as shown in [Pea93], a rule of an extended logic program can be interpreted as a constructive implication in N. However, rules operating on disjunctive information, such as in

1Another possibility, in the spirit of Gödel’s translation ∗ of intuitionistic logic into S4, is the explicit epistemic interpretation of a rule F ← G as □(G^{∗} → F^{∗}).

{ p ∨ q, r ← p, r ← q }

differ from constructive implication: in N, we would obtain r (the corresponding inference principle is called ‘Disjunction in the Premise’), whereas a genuine rule-oriented semantics would not allow this inference.

In this paper, we present a new and direct approach to the semantics of deduction rules.^{2} The key concepts for this approach are that of a knowledge representation and reasoning system, and that of a rule knowledge base (RKB), or deductive knowledge base, proposed in [Wag94a]. Inspired by Belnap’s notion of an information state [Bel77], rules are interpreted as update functions operating on knowledge bases, and the semantics of a deductive knowledge base is determined by the existence of preferred closures being common fixpoints of all rules. Our theory, therefore, is both a fixpoint theory for certain nonmonotonic functions, and a semantical theory for the concept of deductive knowledge bases comprising various deductive database and logic programming systems. It is conceptually simpler than many other (quite technical) proposals on the semantics of logic programming rules, and it is at the same time more general.

While monotonic ampliative RKBs have a unique minimal closure which is naturally the intended one, one has to find an appropriate preference criterion in order to define the intended closures of a nonmonotonic RKB. Such a preference criterion then selects from the supported closures the intended ones in a conservative fashion: in the special case of a monotonic ampliative RKB this has to be the unique minimal closure.

Since nonmonotonic rules do not necessarily contain negation-as-failure (there are other non-persistent operators, such as exclusive disjunction, or certain modal operators), a general semantics for RKBs cannot refer to negation-as-failure, or any other specific logical operator. Rather, it has to account for the way in which the application (successive detachment) of a set of rules yields an intended closure. It turns out that the notion of a stable closure is a key for the semantics of RKBs. While certain ‘well-behaved’ RKBs have a unique stable closure, there may be several stable closures, or none, in the general case.^{3}

Stable closures generalize stable models [GL88], resp. answer sets [GL90], in essential respects: they are not only defined for logic programs with negation-as-failure, but for a far more general class of non-monotonic rule-based systems. Thus, the stable model semantics can be viewed as the proper specialization of the stable closure semantics for normal logic programs. It is not clear at the moment whether a similar generalization is possible for the competing well-founded semantics. If such a generalization is not possible for the wellfounded semantics, this would be a strong argument in favour of the stable model semantics by indicating that it is the theoretically more general, and in this sense superior concept.

2We do not identify ‘semantics’ with model theory. There are also proof-theoretic semantics of logical systems. Only in ‘nice’ cases, e.g. in classical logic, it is clear that model theory is more fundamental (conceptually simpler and more ‘declarative’) than proof theory. There are other cases, however, where this is not clear (e.g. relevance logics, or default logic). Our definition of a knowledge system does not require a model-theoretic semantics, but neither does it preclude one.

3We shall present a generalization of the logic programming concept of stratification for rule knowledge bases in a sequel paper where we show that, mathematically, the notion of stratification is not related to negation-as-failure, but rather to the problem of the computational stability of a set of nonmonotonic rules and the uniqueness of the resp. closure.

The structure of the paper is as follows: in section 2 we present some basic concepts of the theory of knowledge representation proposed in [Wag94a]. In section 3, the concept of a deductive knowledge base is introduced, and the stable closure semantics is defined. It is shown that the stable closures of a normal logic program are exactly its stable models. Also, a generalization of the immediate consequence operator is presented, and the proposed operational semantics of rules is compared with the more common ‘relational’ semantics. In sections 4–6, various cases of RKBs satisfying certain conditions are discussed. In section 7, we show that every ampliative RKB has a supported closure. We then present a variety of examples illustrating the problem of stratification. Finally, in section 9, we briefly discuss the question of non-ampliative rules by means of two examples.

4.2 Deductive Knowledge Bases

Rule knowledge bases, or deductive knowledge bases, as we prefer to call them here, were defined in [Wag94a]. Every KS K = ⟨ 0, ≤, L_{KB}, ⊢, L_{Query}, Upd, L_{Input} ⟩ can be naturally extended to an deduction-rule-based system RK. In RK, a knowledge base X ∈ L_{KB} is supplemented by a set R ⊆ L_{Input}^{x} × L_{Query}^{x} of deduction rules r = ⟨F, G⟩ with conclusions F ∈ L_{Input}^{x} and premises G ∈ L_{Query}^{x}, also written as ‘F ← G’, such that Free(F) ⊆ Free(G). Rules of this form are called range-restricted,^{4} the set of such rules will be denoted by R(L_{Input} ← L_{Query}). They can be viewed as mappings between KBs, r : L_{KB} → L_{KB}, since their application is defined as^{5}

r(X) := Upd(X, {F σ : σ is a ground substitution for G such that X ⊢ Gσ})

Notice that in the case of a non-applicable rule, we get r(X) = Upd(X, ∅) = Upd(X, ⋀ ∅) = Upd(X, 1) = X.

Let [R] denote the instantiation of R. If r = F ← G we will also write C_{r} instead of the conclusion F, and P_{r} instead of the premise G. If r ∈ [R], then

r(X) = \{ \begin{matrix}Upd(X, C_{r}) & if X ⊢ P_{r} \\ X & otherwise \end{matrix}

In the sequel, if not otherwise noted, we shall identify R with its instantiation [R].

Observation 17 If the ‘facts’ X of a deductive knowledge base ⟨X, R⟩ consist of a set of compiled input formulas A_{X} ⊆ L_{Input}, X = Upd(0, A_{X}), then the deductive knowledge base can be rewritten as a set of rules:

⟨X, R⟩ ⟶ ⟨ 0, R ∪ {F ← 1 : F ∈ A_{X}} ⟩

where those ‘improper’ rules with a trivially true premise, F ← 1, represent the ‘facts’.

4In fact, we also need to require that the premise of a rule can be sensibly evaluated. Query formulas with this property are called domain independent, resp. evaluable. See [vGT91]. In the special case of normal logic programs it means that every free variable occuring in the scope of negation-as-failure occurs as well in a positive literal.

5Notice that r(X) = Upd(X, {F (t) : {t} ∈ Ans(X, G)}). A generalized definition of rule application would be r(X) = Upd(X, {⋁_{t∈T} F (t) : T ∈ Ans(X, G)}). This is a topic of future research.

Definition 8 (Deductive Closure) Z ∈ L_{KB} is a deductive closure of ⟨X, R⟩ if it extends X, Z ≥ X, and if it is closed under all rules of R: r(Z) = Z for all r ∈ R.^{6}

Instead of ‘deductive closure’ we shall also just say ‘closure’.

Observation 18 A ground rule is idempotent, r(r(X)) = r(X), iff Upd satisfies Contraction.

Proof: If X ⊬ P_{r}, then by definition, r(r(X)) = r(X) = X. Otherwise, r(r(X)) = r(Upd(X, C_{r})). Then if Upd(X, C_{r}) ⊬ P_{r}, we get

r(r(X)) = r(Upd(X, C_{r})) = Upd(X, C_{r}) = r(X)

Otherwise, by Contraction,

r(r(X)) = Upd(Upd(X, C_{r}), C_{r}) = Upd(X, C_{r}) = r(X) □

The semantics of a deductive knowledge base ⟨X, R⟩ is determined by the definition of the notion of a preferred closure. In general, there may be several preferred closures, or none. We denote their collection by R(X), and write R(X) ⊢ F as an abbreviation of ∀Z ∈ R(X) : Z ⊢ F. If ⟨X, R⟩ has several preferred closures, a valid consequence must be inferrable from all of them:

⟨X, R⟩ ⊢_{r} F :⟺ R(X) ⊢ F

In the specific case where all rules r ∈ R are monotonic and ampliative, there is exactly one preferred closure of ⟨X, R⟩, namely the informationally least one. In the general case, we will assume that the stable closures (see below) are the preferred ones. All these cases will be treated separately in the following sections.

The input language of RK is the same as that of K, and we have

Upd_{r}(⟨X, R⟩, F) := ⟨Upd(X, F), R⟩

Formally,

RK := ⟨ ⟨0, ∅⟩, ≤_{r}, L_{KB} × 2^{R(L_{Input}←L_{Query})}, ⊢_{r}, L_{Query}, Upd_{r}, L_{Input} ⟩

Since we do not need it here, we will not discuss the definition of ≤_{r}.^{7} In the sequel, we will omit the subscript r.

Example 4 (Normal Logic Programs) Deductive knowledge bases of RA correspond to deductive databases, resp. normal logic programs. For instance, the program

Π_{1} = {r(S), m(P, L), m(y, x) ← m(x, y)},

corresponding to the deductive knowledge base ⟨X_{1}, R_{1}⟩ with

X_{1} = {r(S), m(P, L)}, and R_{1} = {m(y, x) ← m(x, y)},

resp. to ⟨X_{2}, R_{2}⟩ with

X_{2} = {}, and R_{2} = {r(S) ← 1, m(P, L) ← 1, m(y, x) ← m(x, y)},

has the unique informationally minimal closure

R_{1}(X_{1}) = R_{2}(X_{2}) = {r(S), m(P, L), m(L, P)} Example 5 (EDLPs) An extended disjunctive logic program (EDLP) corresponds to a deductive knowledge base of RDF. For instance,

6Notice that the notion of a closure is more general than a ‘model’. In specific cases, such as for normal or extended logic programs, closures can be viewed as ‘models’.

7Possibly: ⟨X, R⟩ ≤_{r} ⟨X′, R′⟩ :⟺ ∀F ∈ L_{Input} : R(Upd(X, F)) ≤ R′(Upd(X′, F)).

Π_{2} = {b(L), l(P, L) ∨ l(P, S), ∼b(S), b(x) ← l(P, x)}

corresponds to the deductive knowledge base ⟨Y_{2}, R_{2}⟩, where Y_{2} is as in example 3, and R_{2} = {b(x) ← l(P, x)}, expressing that every woman Peter likes is blonde, and thus, R_{2}(Y_{2}) = {{b(L), l(P, L), ∼b(S)}}.

Definition 9 A mapping f : A → A from a preorder ⟨A, ≤⟩ into itself is called monotonic if f(x) ≤ f(y) whenever x ≤ y. It is called ampliative if x ≤ f(x). A rule is called monotonic (resp. ampliative) if it is a monotonic (resp. ampliative) mapping. A rule is called persistent if its premise is a persistent query formula. A rule knowledge base ⟨X, R⟩ is called persistent (ampliative, monotonic) if all rules r ∈ R are persistent (ampliative, monotonic).

Observation 19 If Update Monotonicity holds in a KS, a rule is monotonic whenever its premise is persistent.

Proof: Let X_{1} ≤ X_{2}. We have to distinguish two cases: If r is not applicable in X_{1}, then – since it is persistent – it is neither applicable in X_{2}, and hence

r(X_{1}) = X_{1} ≤ X_{2} = r(X_{2})

Otherwise, by Update Monotonicity,

r(X_{1}) = Upd(X_{1}, C_{r}) ≤ Upd(X_{2}, C_{r}) = r(X_{2}) □

Rules of positive logic programs, for instance, are persistent, ampliative and monotonic. Normal logic programs consist of ampliative rules, while active databases, resp. production rule systems such as OPS5 where the application of rules may cause the deletion of information, allow also for non-ampliative rules.

Definition 10 (Supported Closure) A closure Z of a deductive knowledge base ⟨X, R⟩ is called supported if there is an ordinal α and a sequence of rules (r_{i})_{1≤i<α}, such that its composition, r = ◯_{α>i≥1}r_{i}, computes Z: Z = r(X).^{8}

We have to explain how the composition r = ◯_{α>i≥1}r_{i} is defined in the infinite case, i.e. when α is an infinite ordinal. In this case we shall make two restrictive assumptions: 1) that the information ordering ⟨L_{KB}, ≤⟩ is a complete lattice, and 2) that all rules in R are ampliative (both conditions are satisfied, for instance, in RA, and RF). We now inductively define (X_{i})_{1≤i<α} ⊆ L_{KB} as follows:

1. X_{1} := X.

2. Assume that X_{i} has been defined for i < β, and X_{i} ≤ X_{j} whenever i ≤ j < β.

(a) If β is a successor ordinal, then X_{β−1} exists and we can define

X_{β} := r_{β−1}(X_{β−1})

Since r_{β−1} is ampliative, X_{β−1} ≤ X_{β}.

8Notice that this definition of supportedness differs from that one introduced in [ABW88] by capturing a kind of grounded bottom-up support rather than the non-grounded top-down support captured there.

(b) If β is a limit ordinal, then we define

X_{β} := sup_{i<β} X_{i}

This supremum exists since it is assumed that the information ordering is a complete lattice.

Thus, in the infinite case, under the above assumptions, we get

◯_{α>i≥1}r_{i}(X) = sup_{i<α} X_{i}

as a supported closure, while in the finite case we have

◯_{α>i≥1}r_{i}(X) = r_{α−1} ∘… ∘ r_{2} ∘ r_{1}(X)

If Z = ◯_{α>i≥1}r_{i}(X) is a supported closure of ⟨X, R⟩, then we may assume (without loss of generality) that for every i < α, we have r_{i} ∘… ∘ r_{2} ∘ r_{1}(X) ⊢ P_{r_{i+1}}, and

Z = X + ∑_{1≤i<α} C_{r_{i}}

respectively, if Update Synchronicity holds,

Z = Upd(X, {C_{r_{i}} : 1 ≤ i < α})

In general, however, we may not conclude that Z ⊢ P_{r_{i}} for all i ∈ [1, α).

Not all supported closures are acceptable. There are even cases of minimal supported closures which do not correspond to our intuition of an acceptable, or, in other words, intended closure as the following example shows.

Example 6 Let X = {s}, and R = {r ← s, q ← −r, p ← −q}. Both {q, r, s}, and {p, r, s} are minimal supported closures, but only the latter one is an intended closure.

We shall prefer closures which are stable in the sense that each rule application within the computation sequence preserves the applicability of all previously applied rules.

Definition 11 (Stable Closure) A closure Z of a deductive knowledge base ⟨X, R⟩ is called stable if there is a sequence of rules {r_{i} ∈ R : 1 ≤ i < α}, such that its composition, r = ◯_{α>i≥1}r_{i}, forms a stable computation of Z in the following sense: Z = r(X), and

If r_{k−1} ∘… ∘ r_{1}(X) ⊢ P_{r_{k}}, then r_{n} ∘… ∘ r_{1}(X) ⊢ P_{r_{k}}, for all n with α > n ≥ k.

If Z = ◯_{α>i≥1}r_{i}(X) is a stable closure of ⟨X, R⟩, then we may assume (without loss of generality) that for every i < α, and j ≤ i + 1,

r_{i} ∘… ∘ r_{2} ∘ r_{1}(X) ⊢ P_{r_{j}}

implying that Z ⊢ P_{r_{j}} for all j ∈ [1, α).

Definition 12 (Preferred Closures) We define the preferred, or intended, closures of a deductive knowledge base to be the stable ones:^{9}

R(X) := {Z ∈ L_{KB} : Z is a stable closure of ⟨X, R⟩}

In the sequel, we shall identify the singleton R(X) = {Z} with its single element Z, i.e. we shall write R(X) instead of Z.

9In fact, if there is the possbility of inconsistent KBs in K, then the preferred closures will be the minimally inconsistent stable closures according to some measure of inconsistency associated with K.

4.2.1 Stable Closures and Stable Models

Claim 8 A stable model of a normal logic program is a stable closure of the corresponding RA knowledge base.

Proof: Let M be a stable model of Π, i.e.

M = Π^{M}(∅) = ◯_{α>i≥1}r_{i}(∅)

for certain rules r_{i} ∈ Π^{M} = {a ← F^{+} : a ← F ∈ Π & F^{−} ∩ M = ∅}. Each of these rules r_{i} is of the form a ← F^{+}, such that it is expandable to a rule r′_{i} = a ← F ∈ Π, and F^{−} ∩ M = ∅. Therefore, M is also a supported closure of Π: M = ◯_{α>i≥1}r′_{i}(∅). It remains to show that this closure is stable. Abbreviating M^{i} := r_{i} ∘… ∘ r_{1}(∅), we have to show for arbitrary k ∈ [1, α) that M^{n} ⊢ P_{r_{k}} for all n ∈ [k, α). Since P_{r_{k}}^{+} ⊆ M^{k−1} ⊆ M^{n}, it holds that M^{n} ⊢ P_{r_{k}}^{+}. On the other hand, since M ∩ P_{r_{k}}^{−} = ∅, it also holds that M^{n} ∩ P_{r_{k}}^{−} = ∅. Consequently, M^{n} ⊢ P_{r_{k}}. □

Claim 9 A stable closure of a RA knowledge base ⟨X, R⟩ is a stable model of the corresponding normal logic program Π.

Proof: Let Z = ◯_{α>i≥1}r_{i}(X) be a stable closure of ⟨X, R⟩. For every k ∈ [1, α), r′_{k} = C_{r_{k}} ← P_{r_{k}}^{+} ∈ Π^{Z}, since Z ⊢ P_{k} implies that P_{k}^{−} ∩ Z = ∅. Consequently, Z ⊆ Π^{Z}(∅).

Now, assume that Π^{Z}(∅) ⊃ Z, i.e. that there are further applicable rules {r_{α}, r_{α+1},…} ⊆ Π^{Z}, such that Π^{Z}(∅) = ◯_{β>i≥α}r_{i}(Z). Then Z ⊢ P_{r_{α}}, but C_{r_{α}} ∉ Z, i.e. Z is not closed under r_{α} which contradicts the fact that Z is a closure of Π. Consequently, Π^{Z}(∅) ⊆ Z. □

4.2.2 The Immediate Consequence Operator

Definition 13 For any deductive knowledge base ⟨X, R⟩, and any Z ∈ L_{KB}, we define

T_{X,R}(Z) := Upd(X, {F : F ← G ∈ [R] & Z ⊢ G})

and its cumulative version

T_{R}(Z) := T_{Z,R}(Z)

for which the following iteration sequence can be formed:

X^{0} = X, X^{i+1} = T_{R}(X^{i}) (i ≥ 0)

In the case of positive logic programs, i.e. for RA^{+}, one obtains the classical T_{P} -operator : let ⟨X, R⟩ be the RKB corresponding to a program P, i.e. X = {a : a ← ∅ ∈ P }, and R = {a ← A ∈ P : A ≠ ∅}, then for I ⊆ At,

T_{P} (I) = {a : a ← A ∈ [P] & I ⊧ A}

as defined by Van Emden and Kowalski in [vEK76], is equal to T_{X,R}(I).

Observation 20 If Update Synchronicity holds, the fixpoints of T_{R} are exactly the KBs closed under R.

Proof: Let Z be a closure, then for any rule r ∈ R we have r(Z) = Z. Let us show that

Upd(Z, {C_{r} : Z ⊢ P_{r}}) = Z

For every r such that Z ⊢ P_{r}, we have Upd(Z, C_{r}) = Z. Therefore, by Update Synchronicity, we get the desired conclusion.

Conversely, if Z is a fixpoint of T_{R}, then Upd(Z, {C_{r} : Z ⊢ P_{r}}) = Z. This clearly implies, by Update Synchronicity, that Upd(Z, C_{r}) = Z, whenever Z ⊢ P_{r}. Therefore, Z is closed under R. □

Observation 21 If Contraction holds, the fixpoints of T_{X,R} are also fixpoints of T_{R}.

Proof: Let Z be a fixpoint of T_{X,R}, then we have

Z = T_{X,R}(Z) = Upd(X, {C_{r} : r ∈ R & Z ⊢ P_{r}})

By Contraction we get

Upd(Z, A) = Upd(Upd(X, A), A) = Upd(X, A) = Z

where A = {C_{r} : r ∈ R & Z ⊢ P_{r}}. □

Observation 22 If Z is closed under R such that for some A ⊆ {C_{r} : r ∈ R & Z ⊢ P_{r}}, Z = Upd(X, A), then Z is a fixpoint of T_{X,R}.

Proof: Let Z be closed under R such that Z = Upd(X, A) where A ⊆ {C_{r} : r ∈ R & Z ⊢ P_{r}}. Let B = {C_{r} : r ∈ R & Z ⊢ P_{r}} − A. By Update Synchronicity, we get

Z = Upd(Z, B) = Upd(Upd(X, A), B) = Upd(X, {C_{r} : r ∈ R & Z ⊢ P_{r}})

and consequently, Z = T_{X,R}(Z). □

Claim 10 If Update Synchronicity holds, then every stable closure is a fixpoint of T_{X,R} and T_{R}.

Proof: Let Z be a stable closure of ⟨X, R⟩. Then for some set of rules {r_{i} : 1 ≤ i < α} ⊆ R,

Z = Upd(X, {C_{r_{i}} : 1 ≤ i < α})

By observation 22, Z is a fixpoint of T_{X,R}. By observation 21, Z is also a fixpoint of T_{R}. □

4.2.3 Operational and Relational Semantics of Rules

Traditionaly, rules have been interpreted by means of model-theory in a similar way as conditionals, or even as material implication. Starting with some notion of a model-theoretic interpretation of formulas, one says that a rule is satisfied by an interpretation if its conclusion is satisfied whenever its premise is. An interpretation is called a model of a set of rules R if it satisfies all r ∈ R. As usual, one can then define a formula to be a consequence of R, if it is satisfied by all (preferred) models of R. In the same spirit can we now define a relational closure of a deductive knowledge base.

Definition 14 (Relational Closure) A relational closure of ⟨X, R⟩ is a KB Z ≥ X, such that for all r ∈ R, Z ⊢ C_{r} whenever Z ⊢ P_{r}. We denote the set of all relational closures of ⟨X, R⟩ by R^{⊢}(X).

One might ask now: under which conditions does the relational semantics of rules aggree with the operational one proposed above ?

Observation 23 A relational closure is an operational (deductive) closure if Vacuity holds.

Proof: Let Z be a relational closure of ⟨X, R⟩, and let r ∈ R. It suffices to show that r(Z) = Z. If Z ⊬ P_{r}, then, by definition, r(Z) = Z. On the other hand, if Z ⊢ P_{r}, then Z ⊢ C_{r}, and by Vacuity, r(Z) = Upd(Z, C_{r}) = Z. □

Observation 24 An operational closure is a relational closure if Reflexivity, i.e. Upd(KB, F) ⊢ F for all F ∈ L_{Input}, holds.

Proof: Let Z be an operational closure of ⟨X, R⟩, and let r ∈ R such that Z ⊢ P_{r}. Then r(Z) = Upd(Z, C_{r}) = Z, and by Reflexivity, Z ⊢ C_{r}. □

Reflexivity does not hold in general in knowledge systems because certain inconsistency handling mechanisms may exclude inconsistent inputs from reflexivity. Vacuity and Reflexivity hold, e.g., in A, and therefore our operational semantics of rules aggrees with the relational semantics of [GL88] in the case of normal logic programs. For more complicated KSs, however, such as DF, where Vacuity does not hold, no such aggreement can be expected.

Our concept of an operational closure seems to have some advantages when compared with the concept of a relational closure, resp. the traditional model-theoretic semantics of rules:

• In the operational semantics of rules we have a general straightforward notion of supported closure. In the relational semantics, the concept of a supported closure – in the form of supported models as proposed in [ABW88] – is only possible for simple structures (like classical, or partial models); it does, however, not guarantee ‘groundedness’, i.e. an atom can support itself.

• The operational semantics allows for the notion of a stable closure as a preference criterion (without having to refer to any specific operator, such as negation-as-failure) while the relational semantics can only distinguish the minimal (relational) closures as the preferred ones which is not sufficient.

On the other hand, the relational semantics seems to be, in some sense, more general: it allows for query expressions in the conclusion of a rule, while the operational semantics is restricted to input expressions.

Example 7 There are cases where only a relational, but no operational, closure exists; e.g. the relational closure of the RDF 1 knowledge base ⟨{{p}}, {p|q ← 1}⟩ is {{p}}, while it has no operational closure.

4.3 Monotonic RKBs

Recall that a deductive knowledge base ⟨X, R⟩ is monotonic if all r ∈ R are monotonic mappings. This is, e.g., the case if Update Monotonicity holds, and all r ∈ R have persistent premise formulas (see observation 19).^{10} Claim 11 A monotonic RKB has at most one supported closure which is its least closure.

10Notice that we do not require in this section that the KS is monotonic, i.e. persistent and ampliative, but only that the RKB is monotonic.

Proof: Assume that X̂ = ◯_{α>i≥1}r_{i}(X) is a supported closure of ⟨X, R⟩. Let Z be any deductive closure of ⟨X, R⟩. Since r_{1} is monotone, we get

r_{1}(X) ≤ r_{1}(Z) = Z

It is obvious that we can get

◯_{β≥i≥1}r_{i}(X) ≤ Z

for every β < α in this way. Consequently, X̂ ≤ Z. □

4.4 Persistent Ampliative RKBs

Let R be persistent, and Z_{1} and Z_{2} be two fixpoints of T_{X,R}, such that Z_{1} ≤ Z_{2}. Because of Persistence, Z_{1} ⊢ P_{r} implies that Z_{2} ⊢ P_{r}. Therefore,

{C_{r} : r ∈ R & Z_{1} ⊢ P_{r}} ⊆ {C_{r} : r ∈ R & Z_{2} ⊢ P_{r}}

and consequently, provided that Update Synchronicity holds,

Z_{2} = Upd(X, {C_{r} : r ∈ R & Z_{2} ⊢ P_{r}})
= Upd(X, {C_{r} : Z_{1} ⊢ P_{r}} ∪ {C_{r} : Z_{2} ⊢ P_{r} & Z_{1} ⊬ P_{r}})
= Upd(Upd(X, {C_{r} : Z_{1} ⊢ P_{r}}), {C_{r} : Z_{2} ⊢ P_{r} & Z_{1} ⊬ P_{r}})
= Upd(Z_{1}, {C_{r} : Z_{2} ⊢ P_{r} & Z_{1} ⊬ P_{r}})

Claim 12 For a monotonic KS with Update Synchronicity, the operator T_{X,R} is monotone.

Proof: Let Z_{1} ≤ Z_{2}. Because of Persistence we have

{C_{r} : r ∈ R & Z_{1} ⊢ P_{r}} ⊆ {C_{r} : r ∈ R & Z_{2} ⊢ P_{r}}

which implies

T_{X,R}(Z_{2}) = Upd(X, {C_{r} : r ∈ R & Z_{2} ⊢ P_{r}})
= Upd(T_{X,R}(Z_{1}), {C_{r} : r ∈ R & Z_{2} ⊢ P_{r} & Z_{1} ⊬ P_{r}})

Since Upd is ampliative, we get T_{X,R}(Z_{1}) ≤ T_{X,R}(Z_{2}). □

Claim 13 Any supported closure of a persistent ampliative RKB is stable.

Proof: Let Z = ◯_{α>i≥1}r_{i}(X) be a supported closure of ⟨X, R⟩. Assume that the rules (r_{i})_{1≤i<α} are ampliative and persistent. Abbreviating X_{j} := ◯_{j>i≥1}r_{i}(X), we can assume, without loss of generality, that for every j < α, we have X_{j} ⊢ P_{r_{j}}. Clearly, this implies that

X_{j+1} = Upd(X_{j}, C_{r_{j}}) = X + ∑_{1≤i≤j} C_{r_{j}}

Since all inputs C_{r_{j}} are ampliative, we get X_{j} ≥ X_{i} for all i ≤ j. Because all premises P_{r_{j}} are persistent, X_{j} ⊢ P_{r_{i}}, for all i ≤ j. □

Assume that r_{1} and r_{2} are ampliative and persistent, and Z ⊢ P_{r_{i}} for i = 1, 2. If Update Synchronicity holds, we get

r_{1} ∘ r_{2}(Z) = r_{2} ∘ r_{1}(Z) = Upd(Z, {C_{r_{1}}, C_{r_{2}}})

Therefore, we conclude that if the rules (r_{i})_{1≤i<α} are ampliative and persistent, and Z ⊢ P_{r_{i}} for 1 ≤ i < α, then to compute ◯_{α>i≥1}r_{i}(Z), the order in which the rules are applied is not important. Therefore, under the assumption of Update Synchronicity, if ⟨X, R⟩ is ampliative and persistent and

R′ ⊆ R_{Z} := {r ∈ R : Z ⊢ P_{r}}

we can write ◯R′(Z) for the composition of all the rules in R′ applied to Z without specifying the order in which these rules are applied. Moreover we have ◯R′(Z) = Upd(Z, {C_{r} : r ∈ R′}).

Since for a persistent and ampliative RKB ⟨X, R⟩ the operator T_{X,R} is monotone, the

1 corresponding fixpoint set F ix(T_{X,R}) is a complete sublattice. Hence there exists a least 2 fixed point of T_{X,R} denoted X̂. The general theory implies that

X̂ = lim T_{X,R}^{i}(X)

It is easy to show then, under the assumption of Update Synchronicity, that the iterates of T_{X,R} are equal to the iterates of T_{R}, i.e. for every i we have

T_{X,R}^{i}(X) = T_{R}^{i}(X) = X^{i}

First notice that by definition, T_{X,R}(X) = T_{R}(X) = X^{1}. We want to prove that X^{i+1} = Upd(X, {C_{r} : X^{i} ⊢ P_{r}}). Let us show it for i = 2. We have X ≤ X^{1} (because of ampliativity), then if X ⊢ P_{r}, we have X^{1} ⊢ P_{r}. Hence

X^{2} = T_{R}(X^{1}) = Upd(X^{1}, {C_{r} : X^{1} ⊢ P_{r}})
= Upd(Upd(X, {C_{r} : X ⊢ P_{r}}), {C_{r} : X^{1} ⊢ P_{r}})
= Upd(X, {C_{r} : X ⊢ P_{r}} ∪ {C_{r} : X^{1} ⊢ P_{r}})
= Upd(X, {C_{r} : X^{1} ⊢ P_{r}})
= T_{X,R}(X^{1})

since {C_{r} : X ⊢ P_{r}} ⊂ {C_{r} : X^{1} ⊢ P_{r}}. In the general case the proof is identical using the fact that the sequence X^{i} is monotone. Consequently, we get the following:

Claim 14 Let ⟨X, R⟩ be a persistent ampliative RKB. Then, if Update Synchronicity holds,

X̂ = lim T_{X,R}^{i}(X) = lim X^{i} = sup X^{i}

We may ask if there is a relationship between X̂ and the supported closures. The answer is given by the following result.

Claim 15 In a KS satisfying Update Synchronicity and where the information ordering is a partial order, any supported closure of a persistent ampliative RKB is equal to X̂. Therefore every persistent ampliative RKB has a unique supported closure.

Proof: Let Z be a supported closure of a persistent ampliative RKB ⟨X, R⟩. We know that Z is stable. Write

Z = ◯_{α>i≥1}r_{i}(X) = Upd(X, {C_{r_{i}} : i < α})

with Z ⊢ P_{r_{i}} for every i < α. Since Z is stable, then Z is a fixpoint of T_{X,R}. Therefore we have X̂ ≤ Z. Let us prove that Z ≤ X̂. Since X ⊢ P_{r_{1}} and X^{1} = Upd(X, {C_{r} : X ⊢ P_{r}}), then r_{1}(X) ≤ X^{1}. Using the properties of the sequence X^{i}, one can easily prove that

◯_{β≥i≥1}r_{i}(X) ≤ X^{β}

for every β < α. Therefore

Z = sup_{β<α} ◯_{β≥i≥1}r_{i}(X) ≤ X̂ □

Notice that X̂ is not the least closure, in general. However if the rules are monotone, it is the least closure.

4.5 Monotonic Ampliative RKBs

Observation 25 The composition of two monotonic ampliative mappings r_{1} and r_{2} will always provide an upper bound for both of them: r_{1} ∘ r_{2} ≥ r_{1}, r_{2}, resp.

r_{1}(r_{2}(X)) ≥ r_{i}(X) for all X ∈ L_{KB}, and i = 1, 2

Proof: Because r_{1} is ampliative, r_{1}(r_{2}(X)) ≥ r_{2}(X). It remains to show that r_{1}(r_{2}(X)) ≥ r_{1}(X). If r_{2} is not applicable, then r_{1}(r_{2}(X)) = r_{1}(X) ≥ X = r_{2}(X). Otherwise, since r_{2} is ampliative, r_{2}(X) ≥ X, and by monotonicity,

r_{2}(X) ≥ X ⇒ r_{1}(r_{2}(X) ≥ r_{1}(X) □

Therefore, the set of all compositions of rules from a monotonic ampliative rule set R is a directed set. This can be used, under the further assumption of continuity, to apply Scott’s theory of continuos lattices [Sco72] in order to obtain the intended closure of ⟨X, R⟩, as proposed in [Bel77]. We are, however, more interested here to study the existence of intended closures under assumptions weaker than continuity.

Claim 16 A monotonic ampliative RKB has a unique supported closure which is the least closure.

Proof: Let ⟨X, R⟩ be a monotonic ampliative RKB. Since the rules are ampliative, there exists a supported closure X̂. Let Z be a closure such that X ≤ Z. Then for any rule r we have r(X) ≤ r(Z) = Z. Therefore, we have X̂ ≤ Z. □

We do not know whether X̂ is stable. It is clear that X̂ is the least fixpoint of T_{R} since the fixpoints of T_{R} are exactly the closures. But we do not know whether X̂ is the least fixpoint of T_{X,R}. Notice that in this case it is unclear whether T_{X,R} is monotone while it is obvious for T_{R}. Therefore, we have two theories: one for persistent ampliative RKBs and the other one for monotonic ampliative RKBs. They can be combined in the case of persistent ampliative RKBs of a KS satisfying Update Monotonicity.

4.6 Ampliative RKBs

Typical examples for non-persistent ampliative RKBs are normal logic programs with negationas-failure. Positive logic programs (without negation-as-failure) are monotonic, persistent and ampliative RKBs. Extended disjunctive logic programs without weak negation (corresponding to RKBs of RDF) are persistent and ampliative, but not monotonic RKBs.

Claim 17 Every ampliative deductive knowledge base has a supported closure if Update Synchronicity holds (in the infinite case we also need to assume that the information ordering is a complete lattice).

Proof: Let ⟨X, R⟩ be an ampliative RKB. Set X_{1} := X. If for all r ∈ R we have r(X_{1}) = X_{1}, we set r_{1} := Id (the identity map). Otherwise we choose r_{1} ∈ R such that r_{1}(X_{1}) ≠ X_{1}. Assume that (r_{i})_{1≤i<α} has been constructed. We set

X_{α} := ◯_{α>i≥1}r_{i}(X)

where α is an ordinal. If for all r ∈ R we have r(X_{α}) = X_{α}, we set r_{α} := Id. Otherwise we choose r_{α} ∈ R such that r_{α}(X_{α}) ≠ X_{α}. Since all r ∈ R are ampliative, (X_{α}) is monotonically increasing, and according to ZF set theory, there is an ordinal β < γ, such that X_{β} = X_{β+1}, and γ corresponds to the well-ordering type of R.

It remains to show that X_{β} is closed under r_{i} for i ≤ β, since it is closed trivially under all other rules r ∈ R − {r_{i} : 1 ≤ i ≤ β}, being not applicable. Clearly, for every i < β, we have X_{i+1} = r_{i}(X_{i}) = Upd(X_{i}, C_{r_{i}}). Therefore, if X_{β} ⊬ P_{r_{i}}, then X_{β} is trivially closed under r_{i}. Otherwise,

r_{i}(X_{β}) = r_{i}(Upd(X, {C_{r_{j}} : 1 ≤ j < β}))
= Upd(Upd(X, {C_{r_{j}} : 1 ≤ j < β}), C_{r_{i}})
= Upd(X, {C_{r_{j}} : 1 ≤ j < β})
= X_{β}  □

Thus, the situation of ampliative RKBs is similar to that of normal logic programs. Although they always have supported, resp. minimal models, we are rather interested in their stable models. Therefore, an important question is: under which conditions does an ampliative RKB have a unique stable closure ? Can we generalize the logic programming notions of acyclicity [AB90] and stratification [ABW88, Prz88, PP90, BF91] for deductive knowledge bases ? This will be the subject of the second part of our paper.

We call a RKB unstable if it has no stable model, otherwise it is called stable.

4.6.1 Some Examples of Stable RKBs

Example 8 The program Π_{2} = {p ← −q, q ← −p} has two stable closures, {p} and {q}, and thus is indefinite, i.e. it represents the disjunctive information p|q. This aggrees with the stable semantics.

Example 9 The RDF knowledge base ⟨{{∼p}, {s}}, {p ← −q, q ← −p}⟩ has two stable closures, {{p, s}} and {{∼p, q}, {q, s}}, which represent exactly the three answer sets of the corresponding EDLP {∼p ∨ s, p ← −q, q ← −p}.

Example 10 The normal program Π_{3} = {p ← −p, p ← −q, q ← −p} has two supported closures, {p} and {p, q}. Its unique stable closure is {p}.

Example 11 The normal program Π_{6} = {p ← −q, p ← q, r ← −q, q ← −r} has two supported closures: {p, q}, and {p, r}, which are also its stable closures and its stable models.

4.6.2 Unstable RKBs

We only discuss some typical examples of unstable RKBs. Normal (resp. consistent extended) logic programs without stable models (resp. answer sets) are also called ‘incoherent’ in the literature.

Example 12 The RA knowledge base ⟨∅, {p ← −p}⟩, corresponding to the well-known call-inconsistentlogic program Π_{1} = {p ← −p}, has the unique supported closure {p}, but no stable closure. In the logic programming literature Π_{1} is considered to be either empty (according to the well-founded semantics) or even ‘incoherent’ (according to the stable semantics). The unique minimal model of Π_{1} is {p}.

Example 13 The RDF knowledge base ⟨{∅}, {∼p ∨ q ← 1, p ← −p}⟩ has the unique supported closure {{p, q}}, while it does not have a stable closure, and the corresponding EDLP does not have an answer set.

Example 14 The program Π_{4} = {p ← −q, q ← p} has exactly one supported closure: {p, q}. It has neither a stable closure nor a stable model.

Example 15 The unique supported closure of Π_{5} = {p ← q, p ← −q, q ← p, q ← −p} is {p, q}. Π_{5} has neither a stable closure nor a stable model.

4.7 Non-Ampliative RKBs

Little is known on non-ampliative RKBs. And it does not seem to be clear whether nonampliative inference rules can be useful at all in knowledge representation. We only discuss some examples.

Example 16 (Reductive Rules) Rules in RA^{−} can have weakly negated conclusions, representing reductive input. For instance, we could have r_{1} = −q ← p, r_{2} = s ← p, and R = {r_{1}, r_{2}}. If applied to X = {p}, we obtain R(X) = {p, s}. The non-ampliative rule r_{1} is redundant in this case: R(X) = r_{2}(X).

On the other hand, certain non-ampliative RKBs with reductive rules, like

⟨X, R⟩ = ⟨{p, q}, {−q ← p}⟩

do not have any closure, and are in this sense inconsistent. Reductive rules, therefore, do not seem to make sense in rule knowledge bases: either they are redundant, or inconsistent.

Example 17 (Non-Ampliative Non-Reductive Rules) In DF^{−}, a set of extended literals, E ⊆ XLit, as input is processed according to

(UE) Upd(Y, E) = {X ∪ (E^{+} − E^{−}) − (E^{−} − E^{+}) : X ∈ Y }

A disjunction ⋁_{i=1}^{n} E_{i} of concjunctions of extended literals E_{i} is processed according to

(U ⋁) Upd(Y, ⋁_{i=1}^{n} E_{i}) = ⋃_{E∈E^{∗}} Upd(Y, E)

where E^{∗} = mi(2^{E_{1}∪...∪E_{n}}), and for E ⊆ 2^{XLit},

mi(E) = \{E ∈ E : (F ∩ \overline{F}) ⊄ (E ∩ \overline{E}) for all F ∈ E\}

Exclusive disjunction can be defined in DF^{−} as F |G := (F ∧ −G) ∨ (G ∧ −F). We could then have the following non-ampliative rule set R = {q|r ← −p}, which is non-redundant in cases like Y = {∅},

R({∅}) = {{q}, {r}}

and inconsistent in certain other cases like Y = {{q, r}}, which cannot be closed under R.

4.8 Conclusion

We have presented a general semantical framework for (possibly nonmonotonic) deduction rules in knowledge bases. Although several problems had to be left open, we have provided the theoretical foundations for many new extensions of logic programming and deductive database systems. In the next chapter, it will be shown how the stable closure semantics can be adapted to active knowledge bases, thus establishing a link between deduction and action rules.

The Stable Closure Semantics for Active Knowledge Bases

Abstract Active knowledge bases result from the addition of action rules to ordinary knowledge bases, like relational or deductive databases and their (for instance, disjunctive) extensions. Action rules provide, e.g., for knowledge base updates on certain conditions, thus beeing able to enforce integrity constraints. But they can also call procedures, like running certain diagnostic tests, or turning switches on and off. In this paper, we will focus on update actions. When updating an active KB, all action rules have to be checked and fired if their condition is satisfied, leading to subsequent updates triggering further action rules. This recursive process is captured declaratively by the notion of an active closure of a KB, being an appropriately updated KB closed under all action rules. Since there might be several closures, we define the notion of a stable closure of an active knowledge base in order to distinguish the preferred, resp. intended, ones from the non-intended ones. We are then able to show that an effectively stratified deductive database under the stable model semantics can be faithfully transformed into an active database under the stable closure semantics.

5.1 Introduction

The idea of active database management systems has arisen from different practical considerations, such as meeting the requirements of non-standard applications, or providing an effective means for the automatic enforcement of integrity constraints.^{1} However, although the concept of action rules (‘triggers’) has gained considerable attention and widespread acceptance both in the academic and the industrial community, there seems to be a lack of formal foundation for it. In this paper, we present formal definitions of action rules and active knowledge bases which are more general than other approaches since they allow the addition of action rules to all kinds of ordinary knowledge bases, like relational or deductive databases and their (for instance, disjunctive) extensions. We also define a general semantics for active knowledge bases in terms of stable closures, and show that an effectively stratified deductive database under the stable model semantics of [GL88] can be faithfully transformed into an active database under the stable closure semantics. Our formalization and semantics relates action with deduction rules, and thus facilitates the further investigation of their resp. potential as components of advanced information systems.

1See, e.g., [Cha91].

46CHAPTER 5. THE STABLE CLOSURE SEMANTICS FOR ACTIVE KNOWLEDGE BASES

In [Wag94a], the formal concept of a knowledge representation and reasoning system (KS) was introduced. A KS consists of two main components: an answer and an update operation manipulating knowledge bases as abstract objects. Based on this formal framework it was shown how with every KS K an active KS AK can be associated. The semantics of AK differs from K with respect to the update operation. When updating an active knowledge base, the updated KB has to be closed again under all action rules.

In some approaches to the formalization of updates and action rules, updates are explicitly recorded by means of two meta-predicates inserted and deleted, sometimes even in combination with explicit time stamps providing a full history of the knowledge base evolution (e.g., [Bry90], [LPS93], [Zan93]). Since this not only may obscure the semantics of a KB but also clearly creates a vast overhead of historic and meta-data, a more conservative approach where the result of an update is again a plain KB without any meta-data, as in our model of a KS, seems to be preferrable.

The concept of a production rule system, which has been widely used in AI for building ‘expert systems’, seems to be a special case of an active KS. In the literature on production rule systems (e.g. [Ras94]) and active databases (e.g. [Zan93]), update actions in the conclusion of a rule have been expressed by means of special operators like add/delete, or assert/retract, and the like. We propose a conceptually simpler, and more elegant, alternative. Instead of

retract(p) ← q ∧ −r

we use the negation-as-failure operator ‘−’ also in the head of a rule in order to express deletion, resp. contraction:

−p ← q ∧ −r

In this way, we obtain purely logical (and uniform) expressions both in the premise and the conclusion of a rule.

The paper has the following structure: in section 2, we present the basic concepts of the theory of knowledge representation proposed in [Wag94a]; in section 3, we present a formal semantics for action rules; in section 4, we show how deductive databases can be faithfully transformed into active databases, and in section 5, we illustrate the use of action rules for automatic integrity maintenance.

5.2 Active Knowledge Bases

Active knowledge bases (AKBs) were originally defined in [Wag94a] as a generalization of active databases. Here we improve and extend that presentation, and we define the stable closure semantics for AKBs.

AKBs result from the addition of action rules to ordinary KBs. Action rules have the form

Action ← Condition

In this paper we shall restrict our attention to rules with update actions and purely epistemic conditions. In general, however, actions will not be restricted to updates but also include other private actions, like turning certain switches on and off, and communicative and further cooperative actions, like informing other KBs, or requesting certain actions from other active KBs. Moreover, general conditions will not only refer to the current knowledge state (i.e.

X) but also to the occurence of certain events (such rules are called event-condition-action rules).

An active KB can be modeled as a pair ⟨X, R⟩ where X ∈ L_{KB} is a knowledge base from some KS K = ⟨ 0, ≤, L_{KB}, ⊢, L_{Query}, Upd, L_{Input} ⟩, and R ⊆ L_{Input}^{x} × L_{Query}^{x} is a set of action rules r = ⟨F, G⟩ with conclusions F ∈ L_{Input}^{x} and premises G ∈ L_{Query}^{x}, also written as ‘F ← G’, such that Free(F) ⊆ Free(G), and G can be sensibly evaluated.^{2} Rules of this form are called range-restricted, the set of such rules will be denoted by R(L_{Input} ← L_{Query}). They can be viewed as mappings between KBs, r : L_{KB} → L_{KB}, since their application is defined as

r(X) := Upd(X, {F σ : σ is a ground substitution for G such that X ⊢ Gσ})

Notice that in the case of a non-applicable rule, we get r(X) = Upd(X, ∅) = Upd(X, ⋀ ∅) = Upd(X, 1) = X.

Let [R] denote the instantiation of R. If r = F ← G we also write C_{r} instead of the conclusion F, and P_{r} instead of the premise G. If r ∈ [R], then

r(X) = \{ \begin{matrix}Upd(X, C_{r}) & if X ⊢ P_{r} \\ X & otherwise \end{matrix}

In the sequel, if not otherwise noted, we shall identify R with its instantiation [R].

An active knowledge base ⟨X, R⟩ is closed under all action rules: X = r(X) for all r ∈ R. When updating an AKB, all action rules have to be checked and fired if their condition is satisfied, leading to subsequent updates. This recursive process is captured declaratively by the notion of an active closure of a KB. The action-rule-based extension of K is defined in the following way:

AK := ⟨ ⟨0, ∅⟩, ≤_{a}, L_{AKB}, ⊢_{a}, L_{Query}, Upd_{a}, L_{Input} ⟩

where

L_{AKB} = {⟨X, R⟩ ∈ L_{KB} × 2^{R(L_{Input}←L_{Query})} : X = R(X)}

The active update operation Upd_{a} is defined by means of the active closure R(Upd(X, F)) of an updated knowledge base Upd(X, F):

Upd_{a}(⟨X, R⟩, F) := ⟨R(Upd(X, F)), R⟩

In an active KB, an update event may cause additional (secondary) updates by triggering action rules. Therefore Upd_{a} has to close again the updated KB.

For the sake of simplicity, we assume that every X ∈ L_{KB} has a unique preferred active closure, denoted by R(X), according to the following definitions.^{3}

Definition 15 (Active Closure) Z ∈ L_{KB} is called an active closure of X ∈ L_{KB} under a set of action rules R, if

1. Z is closed under all rules r ∈ R, i.e. r(Z) = Z for all r ∈ R, and

2. Z is supported, i.e. for some sequence of rules (r_{i})_{1≤i≤n} ⊆ R, Z = r_{n} ∘… ∘ r_{1}(X).

2Query formulas with this property are called domain independent, resp. evaluable. See [vGT91]. In the special case of a conjunction of negation-as-failure literals, it means that every free variable occuring in the scope of negation-as-failure occurs as well in a positive literal.

3The general case of possibly several preferred active closures will be treated in a future paper.

In the sequel, we shall also simply say ‘closure’ instead of ‘active closure’.

Example 18 Let X = ∅, and R = {−p ← −r, r ← q} form an AKB of AA^{−}, and p ∧ q be a new input. Upd(X, p ∧ q) = {p, q} has two closures under R:

{q, r} = (r ← q)(−p ← −r)({p, q})  (5.1)
{p, q, r} = (r ← q)({p, q})  (5.2)

However, only the latter is preferred, since it is the only stable closure in the sense that each rule application within the computation sequence preserves the applicability of all previously applied rules.

Definition 16 (Stable Closure) A closure Z of a knowledge base X ∈ L_{KB} under a set of action rules R is called stable if there is a sequence of rules (r_{i})_{1≤i≤n} ⊆ R, such that its composition, r = r_{n} ∘ … ∘ r_{1}, forms a stable computation of Z in the following sense: Z = r(X), and

If r_{i−1} ∘… ∘ r_{1}(X) ⊢ P_{r_{i}}, then r_{j} ∘… ∘ r_{1}(X) ⊢ P_{r_{i}}, for all j with i ≤ j ≤ n.

If Z = r_{n} ∘… ∘ r_{1}(X) is a stable closure of X under R, then we may assume (without loss of generality) that for every i ≤ n, and j ≤ i,

r_{i} ∘… ∘ r_{2} ∘ r_{1}(X) ⊢ P_{r_{j}}

implying that Z ⊢ P_{r_{j}} for all j = 1,…, n.

In this paper, we shall restrict our considerations to the case where a unique stable closure exists, and R(X) is identified with its single element, i.e. we write R(X) = Z instead of R(X) = {Z}. In general, however, there may be several (or no) stable closures, as the following example shows.^{4}

Example 19 Let X = ∅, and R = {−p ← q, −q ← p} form an AKB of AA^{−}, and p ∧ q be a new input. Upd(X, p ∧ q) = {p, q} has two stable closures under R: {q} and {p}.

Definition 17 (Preferred Closures) We define the preferred (intended) closures of an active knowledge base to be the stable ones:^{5}

R(X) := {Z ∈ L_{KB} : Z is a stable closure of X under R}

Since the epistemic component X of an AKB ⟨X, R⟩, is always ‘saturated’, X = R(X), the answering of a query does not involve the active component R:

⟨X, R⟩ ⊢_{a} F :⟺ X ⊢ F

Notice that while the deductive closure of a rule knowledge base such as a deductive database, is an auxiliary object of the semantics (and only temporarily, or partially, computed) in order to determine the answer to a query, the active closure of an active knowledge base is effectively carried out as an essential part of the update operation of an active KS. In short: deduction rules help to answer queries, whereas action rules help to perform updates.

4Notice that there are four kinds of ‘satisfiability’: an AKB can have 1) a unique stable closure, 2) several stable closures, 3) a closure but no stable one, and 4) no closure at all, like for instance ⟨∅, {p ← −p, −p ← p}⟩.

5In fact, if there is the possbility of inconsistent KBs in K, then the preferred closures will be the minimally inconsistent stable closures according to some measure of inconsistency associated with K.

5.3 Transforming Deductive into Active Databases

A deductive database Π consists of a set of ground atoms X_{Π} ⊆ At, and a set R_{Π} of rangerestricted deduction rules of the form a ← A where a ∈ At^{x} is an atom, and A ⊆ At^{x} ∪ \overline{At^{x}} a set, resp. conjunction, of atoms and weakly negated atoms, such that Free(a) ⊆ Free(A), and Free(A^{−}) ⊆ Free(A^{+}).

M ⊆ At is a stable model of Π, if M = α(Π^{M}), where Π^{M} = X_{Π} ∪ R_{Π}^{M}, and

R_{Π}^{M} = {a ← A^{+} : a ← A ∈ R_{Π} & A^{−} ∩ M = ∅}

and α assigns the least model to a positive program.

Claim 18 A stable model of a deductive database Π is a stable closure of X_{Π} under R_{Π}.

Proof: Let M be a stable model of Π, i.e. M = α(Π^{M}) = r_{n} ∘… ∘ r_{1}(X_{Π}), for certain rules r_{i} ∈ R_{Π}^{M} = {a ← A^{+} : a ← A ∈ R_{Π} & A^{−} ∩ M = ∅}. Each of these rules is expandable to a rule r′_{i} = a ← A ∈ R_{Π}, and since A^{−} ∩ M = ∅, M is an active closure of X_{Π} under R_{Π}: M = r′_{n} ∘ … ∘ r′_{1}(X_{Π}). It remains to show that this closure is stable. Abbreviating M^{i} := r_{i} ∘ … ∘ r_{1}(X_{Π}), we have to show for arbitrary j = 1,…, n that M^{i} ⊢ P_{r_{j}} for all i = j,…, n. Since P_{r_{j}}^{+} ⊆ M^{j−1} ⊆ M^{i}, it holds that M^{i} ⊢ P_{r_{j}}^{+}. On the other hand, since M ∩ P_{r_{j}}^{−} = ∅, it also holds that M^{i} ∩ P_{r_{j}}^{−} = ∅. Consequently, M^{i} ⊢ P_{r_{j}}. □

Claim 19 A stable closure of X ⊆ At under a set R of action rules of the form a ← A is a stable model of the corresponding deductive database Π = X ∪ R.

Proof: Let Z = r_{n} ∘ … ∘ r_{1}(X) = X ∪ {C_{r_{i}} : 1 ≤ i ≤ n} be a stable closure of X under R. For every i = 1,…, n, r′_{i} = C_{r_{i}} ← P_{r_{i}}^{+} ∈ R_{Π}^{Z}, since Z ⊢ P_{i} implies that P_{r_{i}}^{−} ∩ Z = ∅. Consequently, Z ⊆ α(Π^{Z}).

Now, assume that α(Π^{Z}) ⊃ Z, i.e. that there are further applicable rules {r_{n+1},…, r_{m}} ⊆ R_{Π}^{Z}, such that α(Π^{Z}) = r_{m} ∘ … ∘ r_{n+1}(Z). Then Z ⊢ P_{r_{n+1}}, but C_{r_{n+1}} ∉ Z, i.e. Z is not closed under r_{n+1} which contradicts the fact that Z is a closure of X under R. Consequently, α(Π^{Z}) ⊆ Z. □

Claim 20 An effectively stratified^{6} deductive database Π can be faithfully transformed into an active database A_{Π} = ⟨R_{Π}(X_{Π}), R_{Π}⟩, such that Π and A_{Π} are dynamically equivalent, i.e. for all p, q ∈ At,

Π ∪ {p} ⊢ q iff Upd(A_{Π}, p) ⊢ q

Proof: An effectively stratified deductive database has a unique stable model. Since Π ∪ {p} is effectively stratified whenever Π is effectively stratified, it suffices to show that every stable model of Π is a stable closure of X_{Π} under R_{Π}, and vice versa, as has been done in the previous two claims. □

6Effective stratification has been defined in [BF91]. For an effectively stratified normal logic program, the wellfounded ‘model’ is equal to the unique stable model.

5.4 Some Remarks on Update and Revision

Traditional logics, like classical or intuitionistic first order logic, do not account for the dynamics of information processing which is most obvious in the case of the update operation associated with database and knowledge-based systems. Therefore, the semantics of updates has attracted considerable attention in recent years, both in the field of logics and AI (e.g., [Win 86+90], [Gär88], [KM91]), and in database and logic programming theory (e.g., [FUV83], [Abi88], [Rei92], [LPS93], [LPR93]). In logics and AI the primary concern seems to be quite theoretical, namely a formalization (or even axiomatization) of contraction and revision in terms of classical logic, resp. two-valued model theory. In contrast, in database and logic programming theory the primary concern is the operational modelling of insertion and deletion subsumed under the concept of update (as opposed to the more theoretical concept of revision which is based on a notion of inconsistency involving explicit negative information).

Observation 26 (AGM Update Postulates) The following postulates for updates in a KS are adapted from analogues in [Gär88] where they have been formulated separately for knowledge base expansion and contraction.

(Success)  Upd(KB, F) ⊢ F
(Vacuity)  KB ⊢ F ⇒ Upd(KB, F) = KB
(Extensionality) F ⊢ G & G ⊢ F ⇒ Upd(KB, F) = Upd(KB, G)

The postulate of Success corresponds to the reflexivity condition from Tarskis axioms for consequence relations, and also to KS2. Extensionality, in [Gär88], is a kind of soundness condition with respect to classical logic, whereas here we propose that every KS defines its own logic (whether classical or not).

In a positive KS (not allowing for explicit negative information), Success holds for both insertion, e.g. Upd({p}, q) ⊢ q, and for deletion, e.g. Upd({p, q}, −q) ⊢ −q. This shows the conceptual advantage of treating weak negation (alias negation-as- failure) in an input formula as deletion, resp. contraction. In general, there may be KSs where Success does not hold for inconsistent inputs. Also, since not all KSs are cumulative, Vacuity does not hold in general. Extensionality, however, holds in all ‘reasonable’ systems.

5.5 Event-Specific Action Rules

In real life, many actions are caused by events. Also for action rules in a knowledge base it appears essential that they may be triggered by the occurence of certain events. Actions and events are closely related to each other: if some agent (say an AKB) performs an action (e.g. an update action), this creates an event (an update event). Since updates are basic actions, they are also basic events.^{7}

We assume that an active KB can access information about those events it has to deal with by querying an event buffer. This event buffer is accessible by means of two system predicates PEvt and NEvt both taking an expression from an event language L_{Evt} ⊇ L_{Input} as an argument. When a new event occurs, say an update, its description in the form of an event expression Event is placed in the event buffer where it must wait to be processed.

7For the sake of simplicity, we shall not distinguish between an action attempt and the (successfull) action itself.

Immediately before, resp. after, it is processed it can be accessed as by means of NEvt(Event), resp. PEvt(Event). At any system time point, PEvt is satisfied by the previous event, and NEvt is satisfied by the next event in the event buffer. After all action rules have been satisfied, Event is processed and the buffer pointer moves on to the next entry.

An event expression is either an elementary event, a compound event, a concurrent event (i.e. a set of compound events), or a sequence of events. For instance, in ADA^{−}, elementary event expressions are extended literals corresponding to insertions and deletions, and compound events are compound input formulas. Extended action rules then have the form:

Input ← PEvt(PreviousEvent), NEvt(NextEvent), Query

where the premise is a conjunctive combination of an event query and an epistemic query from L_{Query} (each of which can be empty), such that update actions can depend both on the knowledge state of a KB and the information about currently occuring events.

The formal semantics for extended actions rules, i.e. the appropriate notion of a closure of a set of such rules, is a topic of future research.

5.6 Integrity Maintenance by Means of Action Rules

We shall discuss now the application of action rules for automatic integrity maintenance. In general, there are various kinds of integrity constraints defining the admissible KBs, and thus controlling knowledge base evolution, in a certain knowledge domain. Formally, an integrity constraint is a closed query formula G ∈ L_{Query}, such that an input F, and the corresponding update, is legal only if Upd(KB, F) ⊢ G.

In certain cases of updates Upd(KB, F), if an integrity constraint G is violated, one does not want to reject the update but rather to provide for an appropriate change of KB such that the cause of the violation is eliminated. This can be done by means of action rules, and one major application seems to be referential integrity maintenance.

5.6.1 Enforcing Integrity

We illustrate the use of action rules for automatic integrity maintenance by means of an example. Assume we have the information that Peter (P) is enrolled (enr) in math (m) or in philosophy (ph), and that it is not possible to do a master of science (msc) in philosophy. This is expressed in the following AKB:

\begin{aligned}⟨Y, R⟩ & := & ⟨ \{\{enr(P, m)\}, \{enr(P, ph)\}, \{enr(P, m), enr(P, ph)\}\}, \\ & & \{−enr(x, ph) ← msc(x)\} ⟩ \end{aligned}

If we then learn that Peter is doing a master of science, and update the AKB correspondingly, we have to compute

R(Upd(Y, msc(P))) = {{enr(P, m)}}

and consequently, Upd(⟨Y, R⟩, msc(P)) ⊢ enr(P, m).

5.6.2 Referential Integrity in RDBs

SQL databases allow for the specification of a particular form of action rule enforcing referential integrity by automatically deleting all dependent tuples when a master tuple, to which these dependent tuples still refer, is deleted.

Example 20 Consider the following relational database X consisting of 3 tables employee, lecturer and course,

employee

EmpNo Name Salary
1  Peter 2000
2  Mary 2100
3  Tom 1800

lecturer

EmpNo Topic
1  pascal
1  prolog
2  pascal
2  c

course

CrsNo Topic EmpNo
cs001 prolog  1
cs002 prolog  1
cs003 pascal  1
cs004 c 2

and a referential integrity specification requiring the deletion of corresponding lecturer tuples as soon as a resp. employee tuple is deleted, and causing the deletion of corresponding course tuples as soon as a resp. lecturer tuple is deleted, which is expressed in SQL by the following ALTER commands:

ALTER TABLE lecturer FOREIGN KEY (EmpNo) REFERENCES employee
ON DELETE CASCADE;
ALTER TABLE course FOREIGN KEY (EmpNo,Topic) REFERENCES lecturer
ON DELETE CASCADE

A first attempt to express corresponding action rules yields:

(r_{1}) −lect(EmpNo, Topic) ← −emp(EmpNo, Name, Salary)
(r_{2}) −crs(CrsNr, Topic, EmpNo) ← −lect(EmpNo, Topic)

Notice however that such deletion rules of the form −q(x) ← −p(x) are not admissible action rules since their premise is not an evaluable query. We could try to remedy this problem by adding the ‘neutral’ positive literal q(x) to the premise yielding −q(x) ← q(x) ∧ −p(x). But now we have another problem: an ‘instable’ rule for which there is no stable closure. Therefore, we have to use extended action rules in order to express referential integrity:

(r_{1}) −lect(EmpNo, Topic) ← NEvt(−emp(EmpNo, Name, Salary))
(r_{2}) −crs(CrsNr, Topic, EmpNo) ← NEvt(−lect(EmpNo, Topic))

If, for instance, Mary quits her job, we would get the following update (using obvious abbreviations, and where R = {r_{1}, r_{2}}):

X′ = R(Upd(X, −emp(2, mary, 2100)))
= r_{2}(r_{1}(X − {emp(2, mary, 2100)}))
= r_{2}(X − {emp(2, mary, 2100), lect(2, pascal), lect(2, c)})
= X − {emp(2, mary, 2100), lect(2, pascal), lect(2, c), crs(cs004 , c, 2 )}

While in SQL it is not possible to specify insertion rules in order to maintain referential integrity,^{8} this is straightforward in our formalism. Let the above set of action rules be extended by adding

(r_{3}) lect(EmpNo, Topic) ← NEvt(crs(CrsNo, Topic, EmpNo))

8SQL databases simply issue an error message when a new tuple refering to some non-existing master tuple is to be inserted.

If then, for instance, a new course in logic is established by inserting crs(cs005,logic,3), we get the following update:

X′′ = R(Upd(X′, crs(cs005 , logic, 3 ))
= r_{3}(X′ ∪ {crs(cs005 , logic, 3 )})
= X′ ∪ {crs(cs005 , logic, 3 ), lect(3, logic)}

This example suggests that the automatic maintenance of referential integrity can best be achieved by using resp. symmetric action rules, i.e. a pair consisting of a deletion and an insertion rule, providing for the necessary deletions when a master tuple is deleted and providing for the insertion of a new master tuple (with default assignments) when a new tuple depending on a non-existing master tuple is inserted.

5.7 Conclusion

We have presented a general semantics for action rules in knowledge representation systems. Unlike other work, we stress that action rules can be used not only in relational databases but in all kinds of knowledge bases.

We have also shown that the formalism of active databases is more general than that of deductive databases since the latter can be embedded in the former. In practice, however, one would hardly transform deduction into action rules because this would transform all intensional relations into extensional ones, and the economic advantage of using deduction rules for expressing derived relations implicitly would get lost. Practical systems, therefore, will combine both deduction rules (e.g. for expressing subsumption relationships) and action rules (e.g. for expressing integrity maintenance policies).

It is only natural to consider then, in a next step, communicative actions as an option for active KBs. An active KB may communicate some newly acquired fact to another KB within the communication network it belongs to. E.g., for the supervision of a large technical system several specialized active KBs may periodically run specific diagnostic tests on the resp. hardware components they are connected with, and report the resp. outcomes on certain conditions to a supervisor KB which in turn may inform a human engineer if the incoming messages sufficiently suggest some problem. Such a distributed diagnostic system consists of cooperative KBs which will be the topic of a future paper.

Disjunctive Knowledge and Logic Programming

6.1 Three Fundamental Ambiguities in the Semantics of Disjunctive Logic Programs

We discuss three ambiguities in the semantics of normal disjunctive logic programs, namely:

1. Exclusive or inclusive disjunction ?

2. Which kind of failure ?

3. Local or global application of rules, resp. Disjunction in the Premise ?

6.1.1 Exclusive or Inclusive Disjunction ?

Many proposals on the semantics of disjunctive logic programs, since guided by the idea of minimal models, account only for an exclusive type of disjunction where

{p ∨ q} ⊢ −p ∨ −q

which seems to be an unjustified stipulation.

In DA, on the other hand, exclusive disjunction can be defined in a straightforward manner as p|q := (p ∧ −q) ∨ (q ∧ −p). This seems preferrable to any exclusive semantics where one cannot express standard disjunctive information being obviously inclusive.

The issue of an inclusive versus exclusive interpretation of disjunction in logic programming was already stressed in [RT88] and [Sak89]. The possible model semantics of the latter, which is elaborated in [SI94], seems to come close to the semantics of disjunctive KBs presented here, since – in a way – ‘possible models’ are produced by (U∨).

6.1.2 Which Kind of Failure ?

As opposed to definite programs, the notion of failure is no longer clear in disjunctive programs. Various suggestions have been been made for failure definitions, often in the form of ‘closed-world assumptions’. The basic idea for the notion of definite failure is the GCWA of [Min82], requiring the failure in all ‘epistemic alternatives’ the disjunctive KB consists of. In most work following [Min82], however, only minimal sets were admitted as epistemic alternatives, but since failure on the basis of minimal epistemic alternatives is not 6.1. THREE FUNDAMENTAL AMBIGUITIES IN THE SEMANTICS OF DISJUNCTIVE LOGIC PROGRAMS55

adequate (see also the previous section), various rather technical *CWA definitions (where

* is some string like ‘E’,‘EG’) have been proposed to remedy this.

In the framework of disjunctive knowledge systems, epistemic alternatives (or possible situation descriptions) are not restricted to minimal ones, and therefore the basic idea of definite failure is adequate. We have also argued above that it seems methodologically preferrable to separate the issue of failure on the basis of disjunctive knowledge from the more complicated problem of failure on the basis of disjunction and rules.

6.1.3 Local versus Global Application of Rules

In the case of a disjunctive KB Y ⊆ L_{KB}, a local closure of ⟨Y, R⟩, corresponding to the local application of rules, can be defined as the set of all informationally minimal X ∈ L_{KB} satisfying the rules of R as constraints:

R_{loc}(Y) := ⋃{min R^{⊢}(X) : X ∈ Y }
= min{X′ ∈ L_{KB} : X′ ≥ X for some X ∈ Y, such that
for all rules F ← G ∈ R, X′ ⊢ F whenever X′ ⊢ G}

Syntactically, a normal disjunctive logic program can be interpreted either as a KB of RDA, or as a KB of DRA. In the latter case, rules are local, while in the former case they are global. For instance, the program Π = {p ∨ q, r ← p, r ← q} has two readings:

1. As a KB of DRA, i.e. as

Y_{1} = { {p, r ← p, r ← q}, {q, r ← p, r ← q}, {p, q, r ← p, r ← q} }

from which r is inferrable: Y_{1} ⊢ r, since R(X) ⊢ r, for all ⟨X, R⟩ ∈ Y_{1}.

2. As a KB of RDA, i.e. as

⟨Y_{2}, R_{2}⟩ = ⟨{{p}, {q}, {p, q}}, {r ← p, r ← q}⟩

from which r cannot be inferred, since R_{2}(Y_{2}) = Y_{2}, i.e. no rule from R_{2} is applicable. However, using the local closure one obtains

(R_{2})_{loc}(Y_{2}) = {{p, r}, {q, r}, {p, q, r}}

and, as in DRA, r can be inferred.

It is conceivable that a disjunctive KB uses both local and global rules, like KBs of RDRA.

Observation 27 (Disjunction in the Premise) The following property,

(DP) Upd(KB, F) ⊢ H & Upd(KB, G) ⊢ H ⇒ Upd(KB, F ∨ G) ⊢ H

holds in DRK, but not in RDK, where K is any KS.

In most proposals on the semantics of disjunctive logic programs,^{1} rules are interpreted locally in a model-theoretic fashion, like implications, and therefore DP holds. However, one could argue that a genuine semantics of deduction rules does not imply DP.

1See, e.g., [GL91], or [LMR92].

6.2 Extended Disjunctive Logic Programs

Minker and Ruiz, in [MR93], have shown in a systematic way how various semantics for normal disjunctive programs can be extended to allow for strong negation, thus inducing a semantics for extended disjunctive programs (EDLP). Starting with a semantics for normal disjunctive programs in the form of a preferred model operator Sem, and somewhat simplifying the presentation,^{2} the basic steps are as follows:

• Define the transformation Π′ of an EDLP Π eliminating all occurences of strong negation by introducing new predicate symbols, and its inverse Π^{∼}, reintroducing the strongly negated predicates. Notice that bot transformations apply also to (sets of) sets of literals, resp. atoms.

• Then the set of preferred (partial) models of an EDLP Π induced by Sem is defined as

XSem(Π) := (Cons(Sem(Π′)))^{∼}

Notice that this construction corresponds to our definition of D_{ex}RF where also only consistent possible situation descriptions are accepted, thus leading to an explosive semantics which does not work in the case of contradictory information. Therefore, we prefer the non-explosive system D_{mi}RF.

It seems that in D_{ex}RF we can emulate the answer set semantics of [GL91] for EDLPs where disjunction is called ‘epistemic’ and denoted by or. Using a special compilation clause for or,

(Uor) Upd(Y, F or G ← H) := Upd(Y, F ← H) ∪ Upd(Y, G ← H)

we have the following conjecture. Let Y_{Π} = Upd({∅}, Π) consist of the ‘split collection’ of extended logic programs forming Π. Then, Π ⊢ l under the answer set semantics of [GL91] iff Y_{Π} ⊢ l in D_{ex}RF.

6.3 Epistemic Logic Programs

Gelfond [1992] has proposed to extend the framework of EDLPs by adding epistemic modal operators in the premise of rules. An epistemic logic program (see [BG93]) consists of rules of the form:

⋁ L ← F_{1} ∧… ∧ F_{m} ∧ ⋀ E

where L ⊆ Lit, E ⊆ XLit, and the F ’s are ‘subjective literals’, i.e. are of the form Bl, −Bl, El, or −El.

Clearly, such rules are special cases of rules in RD_{mi}^{5}F, resp. D_{mi}^{5}RF. An epistemic logic program specifies an epistemic state, called world view in [Gel92], as a collection of answer sets: Y ⊆ 2^{Lit} is an epistemic state specified by an epistemic logic program Π if each X ∈ Y is an answer set of Π^{Y}, where

Π^{Y} := {⋁ L ← ⋀ E : Y ⊢ ⋀ F_{i}}

It will be an issue for future work to show how inference from epistemic logic programs in this sense corresponds to inference in D_{mi}^{5}RF.

2Minker and Ruiz distinguish between incoherent programs, where XSem(Π) = ∅, and inconsistent programs, where XSem(Π) = {Lit}. It is not clear to me, however, what is the difference, semantically ?

6.4 The CWA in Answer Set Semantics

The above account of the CWA reducing the derivability of a strongly negated atom formed with a CWA predicate to the derivability of its weak negation applies to every KS with strong and weak negation in a uniform way. It is, therefore, more general than the definition of the CWA given in [GL90, GL91] for extended logic programs which was modified in [Gel92] in order to account properly for disjunctive information. Thus, in the answer set semantics, there are two different forms of the CWA: one for the definite case, and another one (using an epistemic modal operator) for the disjunctive case. We shall discuss this by means of an example.

In [GL90, GL91] it was proposed to express the CWA for a predicate p by the rule

∼p(x) ← −p(x)

Consider the following example. A member of the scientific council must be both a lecturer and an active researcher. Suppose we know that Peter is a lecturer, l(P), and we also know that Tom is a lecturer or a researcher, l(T) ∨ r(T), and for both predicates the CWA holds, then, according to [GL91] we get the following EDLP:

Π_{1} = \{ \begin{matrix}l(P) \\ l(T) ∨ r(T) \\ ∼l(x) ← −l(x) \\ ∼r(x) ← −r(x) \end{matrix}

which has two answer sets,^{3} namely {l(P), ∼r(P), l(T), ∼r(T)} and {l(P), ∼r(P), r(T), ∼l(T)}, and consequently, ∼r(P) as well as ∼l(T)∨∼r(T) can be inferred, that is, we get the answer no not only to the query ‘Does Peter belong to the scientific council ?’ but also to ‘Does Tom belong to the scientific council ?’.

However, as Gelfond argues in [Gel92], the fact that r(T) does not hold in some answer set, does not guarantee that a rational reasoner does not have a reason to belief r(T). Such a reason may be given by the existence of another answer set containing r(T). Gelfond, therefore, proposes to express the CWA for a predicate p in the presence of disjunctive information by means of an epistemic modality in the following way:

∼p(x) ← −Ep(x)

where the premise requires that there is no possible evidence for p(x) in none of the answer sets. We thus obtain the following epistemic logic program as the correct formalization of our problem:

Π_{2} = \{ \begin{matrix}l(P) \\ l(T) ∨ r(T) \\ ∼l(x) ← −El(x) \\ ∼r(x) ← −Er(x) \end{matrix}

Π_{2} has the unique world view

{{l(P), ∼r(P), l(T)}, {l(P), ∼r(P), r(T)}} yielding the conclusion that ∼r(P), but not that ∼l(T) ∨ ∼r(T), and hence as desired only the query ‘Does Peter belong to the scientific council ?’ gets the answer no, while the same query with respect to Tom gets the answer unknown now.

3Recall that S ⊆ Lit is an answer set of an EDLP Π if S ∈ α(Π^{S}) where Π^{S} is the Gelfond-Lifschitz transformation eliminating negation-as-failure from Π, and α(Π) collects all minimal literal closures of Π.

This is exactly the same result as in the corresponding disjunctive fact base obtained by stipulating the CWA for the predicates l and r, and compiling the facts that Peter is a lecturer and that Tom is a lecturer or a researcher:

Y = \{ \begin{matrix}CWA = \{l, r\} \\ Upd(0, l(P) ∧ (l(T) ∨ r(T))) \\ = \{\{l(P), l(T)\}, \{l(P), r(T)\}, \{l(P), l(T), r(T)\}\} \end{matrix}

We get the following closure:

CWA(Y) = {{l(P), l(T), ∼r(P)}, {l(P), r(T), ∼r(P)}, {l(P), l(T), r(T), ∼r(P)}

yielding the same answers as above to the queries whether Peter and Tom belong to the scientific council.

6.5 Conclusion

The framework of normal logic programs can be extended with respect to at least four big logical issues: explicit negative information, disjunctive information, modal queries (resp. subjective knowledge), and conditional queries. In all these extensions there are different design options how to model the interaction of negations and the other operators. And it is not obvious at all what is the ‘right’ generalization of negation-as-failure in these settings. We hope, however, that the proposed framework of vivid knowledge representation systems helps to realize and evaluate the different options and modelings.

Solving the Steamroller, and Other Puzzles, with Extended Disjunctive Logic Programming

Abstract: We show how to solve the classical ATP benchmark test problem Schubert’s Steamroller, and other puzzles, in the nonclassical framework of extended disjunctive logic programming (EDLP) where neither Contraposition nor Reasoning by Cases are valid principles of inference. While the ‘Steamroller’ can be solved using only Detachment and Disjunctive Syllogism, another puzzle, ‘Who killed aunt Agatha ?’, needs in addition a local form of Contraposition, resp. Reasoning by Cases, which is achieved by declaring certain predicates as exact in the sense of [Kör66]. Besides being able to solve certain classical ATP problems in a monotonic reasoning mode, EDLP can as well treat commonsense reasoning problems by employing its intrinsic nonmonotonic inference capabilities. This will be illustrated by means of a nonmonotonic variant of the ‘Steamroller’ problem. EDLP thus proves itself as a powerful general-purpose AI reasoning system.

7.1 Introduction

Logic programs with both strong negation and disjunction are called extended disjunctive logic programs (EDLP).^{1} Despite their comparable expressiveness they do not lead to classical first order logic. In EDLPs, neither the Tertium Non Datur (resp. Reasoning by Cases) nor the Contraposition principle hold. Our conjecture is, however, that these classical principles in their full generality are not needed in many cases of natural inferences, especially in knowledge-based reasoning (as opposed to theoretical reasoning). The ‘Steamroller’ is an example for this. Although it has been formulated as a challenging benchmark test for classical automated theorem proving (ATP) systems by L. Schubert,^{2} it can be naturally represented and efficiently solved as an EDLP. In contrast to ATP systems using full classical first order logic, however, EDLPs are evaluated by means of only two logical principles: Detachment, i.e. rule application, and some form of the Disjunctive Syllogism. They seem to be more efficient therefore.

60CHAPTER 7. SOLVING THE STEAMROLLER, AND OTHER PUZZLES, WITH EXTENDED DISJUNCTIVE LOGIC PROGRAMMING

We do not suggest that EDLPs, resp. the underlying framework of vivid knowledge representation systems, are an alternative to classical ATP systems. Rather we would like to argue that purely theoretical, notably mathematical, reasoning should be distinguished from practical reasoning such as embodied in databased and knowledge-based inferences. While classical ATP seems appropriate for the former, vivid knowledge representation systems, such as extended logic programming, seem to be more appropriate for the latter.

1See, e.g., [GL91], or [MR93].

2For a comprehensive description of it including historical remarks see [Sti86].

The main purpose of the paper is not to present and discuss a new theory (although we will have to do that to some extent), but rather to demonstrate the subtle interaction between theoretical modeling and practical KR requirements arising from the treatment of relevant and, to some extent, generic examples (such like the ‘Steamroller’ and ‘Aunt Agatha’). We apologize to those readers looking in vain for more explanation and justification of our formalism. But we believe that the thourough discussion of non-trivial examples is interesting and substantial by itself.

The structure of the paper is as follows: in section 2 we will present some basic concepts of the theory of knowledge representation proposed in [Wag94a], notably the concept of a rule knowledge base and its closure semantics. A new general construction for disjunctive knowledge bases is presented in section 3. It is the basis for showing then in section 4 how to represent and solve the ‘Steamroller’ as a monotonic EDLP. In section 5, a nonmonotonic version of the ‘Steamroller’ where certain rules express defaults, and thus may have exceptions, is discussed. Finally, the concept of exact predicates and the related pinciple of local Reasoning by Cases, resp. local Contraposition, is used to solve the ‘Aunt Agatha’ problem.

The main contributions of the paper are: a) a short introduction of conditionals to the language of rules in section 2.3, b) the new concept of a disjunctive KRS^{3} in section 3, and c) the demonstration how to treat puzzles requiring the language of first order logic as EDLPs in the framework of vivid knowledge representation systems.

7.2 Introducing a First-Degree Conditional

In knowledge-based reasoning, universal quantification is always restricted, i.e. we never have expressions like ∀x(q(x)) as queries or inputs, but only extensional subsumption formulas like ∀x(p(x) ⊃ q(x)) as queries, or intensional subsumption formulas like ∀x(p(x) → q(x)) as queries and inputs. We shall omit the quantifier symbol ∀ in such conditionals and interpret all free variables of the premise as implicitly universally quantified.

Extensional subsumption is expressed by means of a ‘material implication’-style operator ⊃ which can be added to the query language of any KRS according to the following definition:

X ⊢ F ⊃ G :⟺ X ⊢ ⋀_{{σ:X⊢F σ}} Gσ

where F, G ∈ L_{Query}^{x} such that Free(F) ⊇ Free(G).^{4} For an example see the rule (F 2) in 5.2.

Intensionl subsumption can be expressed by means of a conditional operator → which can be added both to the input and to the query language of any rule knowledge representation system. Let RK be the rule-based extension of a KRS K. Then the conditional extension R⃗K of RK is defined by 1) the input language

L⃗_{Input} := {F → G : F ∈ L_{Query}^{x} & G ∈ L_{Input}^{x}, such that Free(G) ⊆ Free(F)} 2) the update opertion

3A preliminary report on disjunctive KRSs has been presented in [Wag93b]. A more elaborate report containing some highlighting theoretical results is in preparation.

4Notice that this definition contains the special case where F and G are ground, and hence X ⊢ F ⊃ G iff X ⊢ −F ∨ G.

Upd(⟨X, R⟩, F → G) := \{ \begin{matrix}⟨Upd(X, G), R⟩ & if F = 1 \\ ⟨X, R ∪ \{G ← F \}⟩ & otherwise \end{matrix}

3) the query language

L⃗_{Query} := {F → G : F ∈ L_{Input}^{x} & G ∈ L_{Query}^{x}, such that Free(G) ⊆ Free(F)}

4) the inference relation

⟨X, R⟩ ⊢ F → G :⟺ ⟨Upd(X, F ν), R⟩ ⊢ Gν

where ν is a special substitution replacing each free variable of F with a fresh constant symbol.

We shall not consider negated conditionals in this paper.

Example 21 The following RR⃗F rule, r = [∼b(x) → r(x)] ← l(P, x), may express that every woman Peter likes has red hair if she is not blonde. If applied to the R⃗F rule knowledge base

⟨X_{1}, R_{1}⟩ = ⟨{l(P, S), ∼b(S)}, {l(P, x) ← b(x)}⟩,

one obtains

r(⟨X_{1}, R_{1}⟩) = ⟨{l(P, S), ∼b(S)}, {l(P, x) ← b(x), r(S) ← ∼b(S)}⟩

7.2.1 Exact Predicates

Observation 28 In consistent KBs of DK, weak and strong negation coincide for exact predicates. Let KB be consistent, p be exact, t be any ground term from its domain, then

KB ⊢ ∼p(t) iff KB ⊢ −p(t)

Observation 29 (Weak Contraposition) In DRK there is a weak form of contraposition: if Y is consistent, then

Y ⊢ ∼F & Y ⊢ G → F implies Y ⊢ −G

Therefore, if q ∈ EXACT, and p(x) ← q(x) ∈ ⋂{[R] : ⟨X, R⟩ ∈ Y }, contraposition may be used in DRK, Y ⊢ ∼p(t) ⇒ Y ⊢ ∼q(t).

7.3 Schubert’s Steamroller

In Schubert’s Steamroller all universal quantifications are restricted, and hence can be expressed by open conditionals, resp. rules. The representation as an EDLP is much more natural (and readable) than the standard clausal representation used in classical ATP systems. In order to solve the ‘Steamroller’ neither Reasoning by Cases nor Contraposition is needed.

7.3.1 Representation

Wolves, foxes, birds, caterpillars, and snails are animals, and there are some of each of them:^{5}

\begin{matrix}(S1) & a(x) ← w(x) ∨ f(x) ∨ b(x) ∨ c(x) ∨ s(x) \\ (S2) & w(w_{1}) ∧ f(f_{1}) ∧ b(b_{1}) ∧ c(c_{1}) ∧ s(s_{1}) \end{matrix}

Also, there are some grains, and grains are plants:

\begin{matrix}(S3) & g(g_{1}) \\ (S4) & p(x) ← g(x) \end{matrix}

Caterpillars and snails are much smaller than birds, which are much smaller than foxes, which in turn are much smaller than wolves:

\begin{matrix}(S5) & sm(x, y) ← b(y) ∧ (c(x) ∨ s(x)) \\ (S6) & sm(x, y) ← b(x) ∧ f(y) \\ (S7) & sm(x, y) ← f(x) ∧ w(y) \\ (S8) & sm(x, y) ← sm(x, z) ∧ sm(z, y) \end{matrix}

Wolves do not like to eat foxes or grains, while birds like to eat caterpillars but not snails:

\begin{aligned}(S9) & ∼l(x, y) & ← w(x) ∧ (f(y) ∨ g(y)) \\ (S10) & ∼l(x, y) & ← b(x) ∧ s(y) \\ (S11) & l(x, y) & ← b(x) ∧ c(y) \end{aligned}

Caterpillars and snails like to eat some plants:

\begin{matrix}(S12) & l(x, p_{2}(x)) ∧ p(p_{2}(x)) ← c(x) \\ (S13) & l(x, p_{3}(x)) ∧ p(p_{3}(x)) ← s(x) \end{matrix}

Every animal either likes to eat all plants or all animals much smaller than itself that like to eat some plants, yielding the following (nested) rule:

(S14) [p(y) → l(x, y)] ∨ [a(z) ∧ sm(z, x) ∧ p(u) ∧ l(z, u) → l(x, z)] ← a(x)

Conclusion: there is an animal that likes to eat a grain-eating animal,

∃x∃y∃z : a(x) ∧ a(y) ∧ g(z) ∧ l(x, y) ∧ l(y, z).

The RDR⃗F rule^{6} (S14) can be transformed into the (not quite equivalent) RDF rule

(S14′) l(x, y) ∨ l(x, z) ← a(x) ∧ p(y) ∧ a(z) ∧ sm(z, x) ∧ p(u) ∧ l(z, u)

The difference between them, however, is not significant for the solution of the ‘Steamroller’.

5Existential information is represented by means of ‘null values’, resp. skolem functions. For instance, ∃xw(x) is transformed into w(n_{k}^{w}) where n_{k}^{w} is a newly introduced null value associated with the domain of the predicate w and enumerated by k = 1, 2, 3,. . .. In order to simplify notation we write w_{k} instead of n_{k}^{w}.

6F denotes the system of fact bases, R⃗F denotes its rule-based extension (i.e. extended logic programs)

allowing for conditional input formulas, DR⃗F denotes the disjunctive extension of R⃗F where KBs consist of a collection of extended logic programs, and finally RDR⃗F allows to add rules operating on DR⃗F such as (S14).

7.3.2 Sketch of solution

We shall present a solution in RDR⃗F, using (S14), rather than with (S14′) in RDF, because it leads to less ‘disjunctiveness’ and hence seems to be more efficient. In RDR⃗F, the solution is obtained from the rule knowledge base ⟨Y, R⟩ where

Y = {⟨{S2, S3}, ∅⟩}

and R = {S1, S4, S5,…, S13, S14}. The rules of R are successively applied in the bottomup computation of R(Y). In the case of branching into different possible situation descriptions, i.e. when evaluating (S14), their consistency has to be checked in order to apply the Disjunctive Syllogism, i.e. discarding the inconsistent ones.

The 5 disjunctions on what each animal likes to eat yield, in the first calculation step, 2^{5} possible combinations, i.e. 32 different rule knowledge bases as elements of R(Y). Each of them contains in addition to the definite information common to all of them, including all facts involving the predicates a, p, g, sm, among others:

p(p_{2}(c_{1})), p(p_{3}(s_{1})), sm(c_{1}, w_{1}), sm(s_{1}, w_{1}), sm(b_{1}, w_{1}),

and some facts invloving l and ∼ l, such as, among others:

l(b_{1}, c_{1}), ∼l(w_{1}, g_{1}), ∼l(b_{1}, s_{1}),

a certain combination of the likes-plants resp. likes-animals rules such as

l(b_{1}, x)) ← p(x)

l(w_{1}, x) ← a(x) ∧ sm(x, w_{1}) ∧ p(y) ∧ l(x, y)

l(f_{1}, x)) ← p(x) l(c_{1}, x)) ← p(x) l(s_{1}, x)) ← p(x) …

The number of 2^{5} such combinations is reduced to 2^{3} by the Disjunctive Syllogism, namely:

1. Birds definitely like to eat all plants since they dislike snails.

2. Wolves definitely like all smaller animals that like to eat some plants (i.e. caterpillars, snails and birds) since they dislike grain.

Consequently all 8 possible situation descriptions contain the facts that a bird likes to eat a grain, l(b_{1}, g_{1}), and that a wolf likes to eat a bird, l(w_{1}, b_{1}). Hence the answer: yes, there is an animal that likes to eat a grain-eating animal (and, moreover, both the species of this animal and of its prey are known: it is a wolf and a bird).

7.3.3 The Usual Interpretation

In the literature on the problem, the predicate smaller has not been transitively closed, and therefore it has not been concluded that birds are smaller than wolves (blocking the conclusion that wolves like to eat birds).^{7} Instead, it has been concluded (by an instance of Reasoning by Cases, and the Disjunctive Syllogism) that, since foxes either like to eat all plants or not and wolves like all smaller plant-eating animals but not foxes, foxes do not like to eat all plants, implying (again by DS) that they like all smaller animals that like to eat some plants, in particular birds, and consequently the answer: yes, namely l(f_{1}, b_{1}).

7We wonder why, since it is certainly part of the natural meaning of smaller that it is transitive.

This kind of solution can also be obtained in our framework, by deleting the transitive closure rule for smaller, (S8), and adding an appropriate instance of the Tertium Non Datur, e.g. l(f_{1}, g_{1}) ∨ ∼l(f_{1}, g_{1}) ← 1, which is not automatically available in a disjunctive KB but only if the resp. predicate is declared to be exact as explained in section 6. However, in the case of the predicate likes one can hardly assume it to be exact (i.e. without truth value gaps), since it is an empirical predicate which may be neither verifiable nor falsifiable for specific instances.^{8}

7.4 The Nonmonotonic Steamroller

We will now interpret the statements S9–S13 about animals liking or disliking to eat other animals or plants as a kind of default: normally they do so. In many cases, this seems to be more natural for empirical predicates, such as likes, than their strict interpretation.

First notice that default rules cannot be expressed in standard first order logic, and therefore classical ATP systems cannot handle such commonsense puzzles. There are at least two possibilities how to obtain default reasoning in extended logic programming: 1) by means of exception handling, and 2) by means of interpreting rules as defeasible using the semantical principles of neutralization and preemption. While the exception-handling approach requires the addition of an exception check to the premise of a rule, the syntactic form of a rule needs not to be changed in the defeasible reasoning approach (which may require a priority ordering of the rules, however).^{9} In the sequel we will focus on the exception handling method proposed in [BG93]. It would be interesting, however, to compare both approaches in terms of expressiveness and efficiency.

7.4.1 Dealing with Exceptions

In [BG93], a default rule r like ‘Normally F if G‘ is expressed by a program rule with an additional premise requiring that individuals (resp. tuples) to which the rule is applicable are not known to be ‘weak exceptions’ for which the rule does not hold (recorded by means of a predicate ex_{r}), or ‘strong exceptions’ for which even the contrary holds:

(r) F (x) ← G(x) ∧ −ex_{r}(x) ∧ −∼F (x)

According to this representation method we obtain the following modifications of S9–S13 :

\begin{aligned}(S9′) & ∼l(x, y) & ← & w(x) ∧ (f(y) ∨ g(y)) ∧ −ex_{9}(x, y) ∧ −l(x, y) \\ (S10′) & ∼l(x, y) & ← & b(x) ∧ s(y) ∧ −ex_{10}(x, y) ∧ −l(x, y) \\ (S11′) & l(x, y) & ← & b(x) ∧ c(y) ∧ −ex_{11}(x, y) ∧ −∼l(x, y) \\ (S12′) & l(x, p_{2}(x)) ∧ p(p_{2}(x)) & ← & c(x) ∧ −ex_{12}(x) ∧ (p(y) → −∼l(x, y)) \\ (S13′) & l(x, p_{3}(x)) ∧ p(p_{3}(x)) & ← & s(x) ∧ −ex_{13}(x) ∧ (p(y) → −∼l(x, y)) \end{aligned}

It is easy to see that with (S9)–(S13) replaced by their resp. exception handling modification (S9′)–(S13′) we still get the same positive answer as before simply because the available null values are not known to be exceptional. Only by introducing explicit exceptions we can change the picture. Therefore, we add to the above story that there is a special bird, called Tweety, for which the rule (S10′) does not hold with respect to any snail, i.e.

8We doubt that wilderness biologists would give a yes-or-no answer to the question whether all foxes eat grain or not.

9Defeasible reasoning with logic programming rules is based on a non-standard semantics of rule application (resp. Detachment) such as proposed, e.g., in [Nut88], or [Wag93a].

\begin{matrix}(T 1) & b(T) \\ (T 2) & ex_{10}(T, x) ← s(x) \end{matrix}

Also we introduce a strong exception to (S11′), namely Opus, a special bird which dislikes caterpillars:

\begin{matrix}(O1) & b(O) \\ (O2) & ∼l(O, x) ← c(x) \end{matrix}

7.4.2 Reasoning with Unknown Information

As an example of reasoning on the basis of unknown information we add that there is a special fox, called Foxy, which likes to eat all smaller animals for which it is (definitely) not known that they eat other animals.

\begin{matrix}(F 1) & f(F) \\ (F 2) & l(F, x) ← a(x) ∧ sm(x, F) ∧ (l(x, y) ⊃ −a(y)) \end{matrix}

It is easy to see that, according to (F 2), Foxy would like to eat Opus since there is no evidence that Opus likes to eat any animals, and as Opus dislikes caterpillars and therefore likes all plants, including grain, a second solution to the query asking for all animals that like to eat a grain-eating animal is obtained.

7.4.3 The Nonmonotonic Steamroller

We propose the following nonmonotonic reasoning problem as a benchmark test for automated reasoning systems:

Wolves, foxes, birds, caterpillars, and snails are animals, and there are some of each of them. Specifically, Tweety and Opus are birds, and Foxy is a fox. Also, there are some grains, and grains are plants. Caterpillars and snails are much smaller than birds, which are much smaller than foxes, which in turn are much smaller than wolves. Wolves do normally not like to eat foxes or grains. Birds normally like to eat caterpillars; however, Opus dislikes them. Except Tweety, birds normally do not like snails. Caterpillars and snails like to eat some plants (under normal conditions). Every animal either likes to eat all plants or all animals much smaller than itself that like to eat some plants. Foxy likes to eat all smaller animals for which it is not known that they eat other animals. Query: which animals like to eat a grain-eating animal ?

In RDR⃗F, this yields the KB ⟨Y, R⟩ with

Y = {⟨{S2, S3, T 1, O1, F 1}, ∅⟩}

and R = {S1, S4, S5, S6, S7, S8, S9′, S10′, S11′, S12′, S13′, S14, T 2, O2, F 2}, from which we can conclude that Opus likes to eat some grain, and that both a wolf and Foxy like to eat Opus:

R(Y) ⊢ l(O, g_{1}) ∧ l(w_{1}, O) ∧ l(F, O).

7.5 Who killed Aunt Agatha ?

The following problem, due to L. Schubert, is borrowed from [Pel86]. Its solution in DRF is obtained by using (in addition to the basic principles Detachment and Disjunctive Syllogism) the posibility to declare certain predicates as exact, thus enabling local Reasoning by Cases, resp. local Contraposition.

7.5.1 Representation

Someone who lives in Dreadsbury Mansion, killed aunt Agatha. Agatha, the butler, and Charles live in Dreadsbury Mansion, and are the only people who live therein:^{10}

(A1) k(A, A) ∨ k(B, A) ∨ k(C, A)

A killer always hates her victim, and is never richer than her victim:

(A2) h(x, y) ∧ ∼r(x, y) ← k(x, y)

Charles hates no one that aunt Agatha hates:

(A3) ∼h(C, x) ← h(A, x)

Agatha hates everyone except the butler, and no one the butler does not hate:^{11}

\begin{aligned}(A4) & h(A, x) & ← ∼e(x, B) \\ (A5) & ∼h(A, x) & ← ∼h(B, x) \end{aligned}

The butler hates everyone not richer than aunt Agatha:

(A6) h(B, x) ← ∼r(x, A)

No one [in Dreadsbury Mansion] hates everyone:

(A7) ∼h(A, h_{1}(A)) ∧ ∼h(B, h_{1}(B)) ∧ ∼h(C, h_{1}(C))

Agatha is not the butler:

(A8) ∼e(A, B)

Who killed aunt Agatha: k(x, A) ?

7.5.2 Sketch of Solution

As opposed to the predicate hates which may be undetermined in certain cases, it seems plausible to declare the predicates kills, richer and equals as exact, i.e. assuming that they do not have truth value gaps, or in other words, that for all ground instances of them it can be determined whether they are true or false:

EXACT(k, r, e)

While in DRF the solution is found by ‘brute force’ bottom-up computation, we will construct here only the essential reasoning steps using the weak contraposition principle. Two arguments can be found why neither Charles nor the butler killed Agatha, and hence, by the Disjunctive Syllogism, she must have killed herself.

10We reduce this information, namely k(k_{1}, A), lDM(k_{1}), lDM(A), lDM(B), lDM(C), together with CWA = {lDM}, to the disjunction k(A, A) ∨ k(B, A) ∨ k(C, A).

11Notice that we use e as an equality predicate. In the case of (A5) we use the contraposition of Schubert’s original formulation ‘The butler hates everyone Agatha hates.’

From (A4) and (A8) we get immediately that Agatha hates herself, consequently by (A3), Charles does not hate Agatha, and hence with the contraposition of (A2), he did not kill her, ∼k(C, A).

From (A5) and (A7) we obtain ∼h(A, h_{1}(B)). Using the contraposition of (A4) we get e(h_{1}(B), B), and hence from (A7) by simple equality reasoning, ∼h(B, B). By the contraposition of (A6), this implies r(B, A), and consequently, by the contraposition of (A2), ∼k(B, A).

7.6 Conclusion

We have shown by means of some non-trivial examples that extended disjunctive logic programs, resp. vivid rule knowledge bases, can be used to express and solve puzzles which require the language of first order logic. We believe that the rule language of rule-based VKRSs is more natural than the language of standard clauses used in ATP systems. We also believe, and hope to substantiate this belief by experimental results in the final version of this paper, that extended logic programmig, since non-classical, is in many cases more efficient than classical ATP systems.

In addition to these advantages, extended logic programming and VKRSs offer a flexible and powerful framework for nonmonotonic forms of commonsense reasoning as we have illustrated here, and as is also argued in [BG93].

Contraction and Revision in Vivid Knowledge Systems

A vivid knowledge system (VKS) has, in addition to a standard negation ‘∼’, a second negation in the style of negation-as-failure, called weak negation, denoted by ‘−’. In a VKS a contraction operation is definable as updating by weakly negated inputs: KB − F := Upd(KB, −F). Thus, contraction is a particular form of update. Recency-preferring revision can be defined according to KB ∗ F := Upd(Upd(KB, −∼F), F).^{1}

We present appropriate modifications of the rationality postulates for contraction and revision and compare them to the original ones proposed in the AGM theory^{2} and by Hansson [1991]. We also discuss the application of our notions to several VKSs, including fact bases, disjunctive fact bases and their rule-based extensions.

8.1 Introduction

In contrast to standard logics, where dynamic aspects of reasoning are largely neglected, belief change operations, such as update, contraction and revision, are essential components of KSs. The term ‘belief revision’ is used in at least two ways: in its broader sense belief revision subsumes any systematic approach to the question of how to change a KB when new information comes in, and in its narrower sense it denotes the specific change operation axiomatised by the AGM postulates. In [GR 92] the goal of consistency maintenance is considered the dominating motive for belief revision. We would like to point out that there are reasonable systems, however, not maintaining consistency but nevertheless employing a revision operation.^{3}

The main principles for belief change operations, according to Gärdenfors and Rott, are:

1. The beliefs in a KB should be kept consistent (whenever possible).

2. The amount of information lost in a belief change should be kept minimal.

3. In so far as some beliefs are considered more important than others, one should retract the least important ones.

1This definition of revision in terms of contraction is due to Levi [1977].

2Called after its originators: C. Alchourrón, P. Gärdenfors and D. Makinson. See [Gär88].

3E.g., [CT92].

The first principle is called minimal inconsistency here, and the second one minimal change. Notice that the formulation “whenever possible” in the first principle can be interpreted in different ways. In the AGM theory, the only case where consistency cannot be avoided is when the input itself is inconsistent. In another approach (proposed by Pries [1989]), the principle of minimal inconsistency means that the beliefs in a KB should be kept ‘as consistent as possible’ in the sense that only the minimally inconsistent ‘possible worlds’ are accepted, and if there are only inconsistent ‘possible worlds’ left, no trivial inferences are drawn.

Gärdenfors and Rott also include the principle that KBs should be deductively closed, because this is essential for the formulation of the AGM theory. We will not adopt this principle, since it seems to be inappropriate for KSs where KBs are always finite objects. Therefore, we will rather be concerned with change operations for ‘belief bases’ instead of infinite ‘belief sets’, as KBs are called in the AGM terminology. Hansson [1991] has proposed postulates for belief bases. The main difference to the AGM postulates seems to be that Hansson does not require recovery which indeed fails in disjunctive KSs (see below).

In summary, our approach differs from the AGM approach (and related ones) in several respects:

1. KBs are not deductively closed.

2. Contraction is more fundamental than revision. In a VKS, contraction is nothing else as weak negation on the left, i.e. the negative counterpart of ampliative updating,

3. We prefer direct constructive notions (such as strong negation ‘∼’) to indirect and nonconstructive ones (such as classical negation ‘¬’, or K⊥F, or K_{⊥}).

4. The preferred form of a KB is not a set of formulas, but rather some form of ‘compiled’ information (since every input formula can be compiled, this is no loss of generality). Contraction in such KBs is syntax-independent: e.g. ⌈p∧q⌉−p = ⌈p, q⌉−p. Also, KBs are not compared by means of set inclusion, ⊆, but rather by means of an informational ordering ≤.

5. The basic pieces of information in a KS are atoms, resp. literals, and not arbitrary formulas. We are, therefore, most interested in the formalization of contraction and revision for atoms, resp. literals, whereas disjunctions and conditionals may be included in the picture as optional extensions in a second step.

6. Vacuity and Recovery do not hold in general. In many cases, however, they hold for literals.

7. Consistency has not to be maintained under all circumstances in a VKS. Paraconsistency (e.g. in the form of minimal inconsistency) is more realistic. This implies that our logics do not contain the concept of absurdity (expressed by ⊥ and K_{⊥}) as a fundamental ingredient.

8. Strong negation does not satisfy the inference rule of (Negation as Inconsistency). Therefore, it is not possible to express that F is inconsistent with KB by the condition KB ⊢ ∼F. This affects the formulation of the resp. proviso of several of the rationality postulates for revision.

We use the following abbreviations: KB+F := Upd(KB, F) for expansion, and KB−F := Upd(KB, −F) for contraction.

70CHAPTER 8. CONTRACTION AND REVISION IN VIVID KNOWLEDGE SYSTEMS

Definition 18 (Entailment) For F ∈ L_{Input} and G ∈ L_{Query} define

F ⊢ G :⟺ Upd(KB, F) ⊢ G for any KB ∈ L_{KB}

Definition 19 (Answer Equivalence) KB_{1} and KB_{2} are answer equivalent, symbolically KB_{1} ≃ KB_{2}, if they produce the same answers at the moment, i.e. if for any query formula F,

Ans(KB_{1}, F) = Ans(KB_{2}, F)

Definition 20 (Update Equivalence) KB_{1} and KB_{2} are update equivalent, symbolically KB_{1} ≅ KB_{2}, if they produce the same answers in all circumstances, i.e. if for any input formula F,

Upd(KB_{1}, F) ≃ Upd(KB_{2}, F)

8.2 Contraction

We present a list of rationality postulates for contraction in KSs. They are appropriate modifications of postulates originally proposed in [Gär88] as an axiomatization of contraction for belief sets. In our direct approach, however, these postulates are not axioms, but rather expressing interesting properties the contraction operation defined in a KS may or may not have.

(Success)  ⊬ F ⇒ KB − F ⊢ −F
(Inclusion)  If F is ampliative, then KB − F ≤ KB
(Vacuity)  KB ⊢ −F ⇒ KB − F ≅ KB
(Extensionality) F ⊢ G & G ⊢ F ⇒ KB − F ≅ KB − G
(Recovery)  KB ⊢ F ⇒ (KB − F) + F ≅ KB
(Conjunction 1) C(KB − F) ∩ C(KB − G) ⊆ C(KB − (F ∧ G))
(Conjunction 2) KB − (F ∧ G) ⊬ F ⇒ KB − (F ∧ G) ≤ KB − G

Notice that in our formulation of Vacuity and Success we have used KB ⊢ −F instead of the original KB ⊬ F. Because of KB ⊢ −F ⇒ KB ⊬ F, this strengthens the original formulation.

While Recovery is a condition on the interaction between contraction and expansion, the postulates of success, vacuity and extensionality describe properties of the update operation.

8.2.1 Contraction in Fact Bases

Claim 21 In F, where only literals, resp. extended literals are admitted as input, the contraction operation ‘−’ satisfies inclusion, vacuity, success, relevance, extensionality and recovery.

8.2.2 Contraction in Disjunctive Data Bases

Observation 30 (Failure of Vacuity) Vacuity fails in many cases of compound formulas:

{{p}} ⊢ −(p ∧ q), but {{p}} − p ∧ q = {{}, {p}} ≅ {{p}}

Observation 31 (Failure of Recovery) Recovery fails in the case of disjunctions:

{{p, q}} − p ∨ q + p ∨ q = {∅} + p ∨ q = {{p}, {q}, {p, q}} ≱ {{p, q}}

Claim 22 In DA, the contraction operation ‘−’ satisfies inclusion, atomic vacuity, success, relevance, extensionality and atomic recovery.

8.2.3 Contraction in Extended Deductive Databases

Extended deductive databases (XDBs) correspond to rule knowledge bases of RF.

Updating by a weakly negated ground literal in an extended deductive database is defined as follows:

Definition 21 (Literal Contraction) Let l be a ground literal. Then Upd(Π, −l) denotes the XDB obtained from Π by making the following changes:

1. If Π contains l as a fact (resp. a rule l ← F such that Π ⊢ F), then l (resp. l ← F) is deleted from Π.

2. If l = p(c), resp. l = ∼p(c), and Π contains the rule p(x) ← F (x), resp. ∼p(x) ← F (x), such that Π ⊢ F (c), then this rule is replaced by p(x) ← x ≠ c ∧ F (x), resp. ∼p(x) ← x ≠ c ∧ F (x).

Example 22 We can now apply this contraction operation to an example given in [GR 92]. Let

Π = {p, q, r ← q, s ← p ∧ r}

According to Gärdenfors and Rott, it is not clear which element of Π has to be given up in order to obtain the contraction Π − s. According to our approach, however, this is clear: only the deletion of the rule s ← p ∧ r leads to an informationally minimal change. The deletion of q, which is supposed to be an equally good candidate according to Gärdenfors and Rott, violates the minimal change principle (−2):

C^{l}({p, r ← q, s ← p ∧ r}) = {p} ⊂ C^{l}({p, q, r ← q}) = {p, q, r}

Example 23 (View Updates) In the literature on ‘view updates’ in deductive databases it is common to ignore the minimal change principle in favour of the (hardly justifiable) idea that only facts should be changed but not rules. For instance, in order to ‘delete’ q(c) from the database

Π = {p(c), r(d), q(x) ← p(x) ∧ r(d), s(x) ← p(x) ∨ r(x)}

two possibilities are considered: in the first one, p(c) is deleted, and in the second one, r(d) is deleted. Both changes are not minimal: clearly,

Π − {p(c)} < Upd(Π, −q(c))

as well as

Π − {r(d)} < Upd(Π, −q(c))

8.3 Consolidation and Revision

While the axiomatization of revision in the AGM theory is inspired by the kind of theory revision investigated in the philosophy of science, our prime concern is revision in knowledge bases where we have quite a different situation. This concerns, for instance, the success postulate giving top-priority to new inputs, so that all new information will have to be accepted no matter how much of the already represented information is compatible with it – something we do not want, in general, in a KS. Instead of the AGM revision operator, a non-prioritized revision operator seems to be more fundamental for a KS. Such a belief change operation is called consolidation in [Han91]. It proceeds in two steps: first KB is updated by the new input F, and then, if necessary, KB + F is consolidated, i.e. made consistent (or minimally inconsistent) by appropriate contractions.

In the sequel, we will simply say revision for a non-prioritized consolidating update operation, while we call the special AGM concept of revision, based on the Success postulate, recency-preferring revision. Thus, we will deal with three kinds of update operations differing in their method of minimizing, resp. eliminating, newly imported contradictory information:

1. Simple update, denoted by Upd(KB, F), or in short, KB + F, tolerating inconsistent KBs according to the principle of

(Minimal Inconsistency) KB + F is minimally inconsistent.

2. Consistent revision, denoted by KB ⊕ F, and described by

(Consistency Preservation) KB ⊕ F is consistent

3. Recency-preferring revision, denoted by KB ∗ F, and characterized by the postulate of success, and a restricted consistency preservation postulate:

(Success)  If F is consistent, then KB ∗ F ⊢ F
(Consistency Preservation) KB ∗ F is only inconsistent if F is inconsistent

The AGM postulates for a revision operator ∘ = ⊕, ∗, supplemented with Hansson’s relevance postulate and adapted to the KS framework are:^{4}

(Inclusion)  KB ∘ F ≤ KB + F
(Vacuity)  If F is consistent with KB, then KB ∘ F ≅ KB + F
(Extensionality) F ⊢ G & G ⊢ F ⇒ KB ∘ F ≅ KB ∘ G
(Relevance) KB ⊢ G & KB ∘ F ⊬ G ⇒ (KB ∘ F) + G is inconsistent
(Conjunction 1) KB ∘ (F ∧ G) ≤ (KB ∘ F) + G
(Conjunction 2) If G is consistent with KB ∘ F, then (KB ∘ F) + G ≤ KB ∘ (F ∧ G)

8.3.1 Inconsistency in Vivid Knowledge Systems

Notice that strong negation does not satisfy the following (classically valid) condition of

(Negation as Inconsistency) KB ⊢ ¬F iff KB + F is inconsistent Therefore, in contrast to classical logic, KB ⊬ ∼F does not guarantee that F is consistent with KB. Consider the extended logic program Π = {p, ∼p ← q}. Clearly, Π ⊬ ∼q. However, Π ∗ q = Π + q is inconsistent. This means that several conditions for recencypreferring revision, notably (Consistency Preservation) and (Success), do not hold if it is defined according to the Levi identity,

4In [GR 92], (Inclusion) is called (Expansion 1), and (Vacuity) is called (Expansion 2).

KB ∗ F := (KB − ∼F) + F

We have two options to remedy this problem. They are associated with the preferred approach to inconsistency handling: either consistency maintenance or paraconsistency, resp. minimal inconsistency. If we want consistency maintenance we could look for a definition of revision capturing the spirit of Levi’s definition (something like: first make KB consistent with F, and then add F).

If, on the other hand, paraconsistency (resp. minimal inconsistency) is preferred, the Levi definition has to be modified in order to prevent the inconsistency of F in KB ∗ F, e.g. in the following way:

KB ∗ F := KB − (F → ∼F) + F

For instance, if Π = {p, ∼q ← q}, this gives Π ∗ q = {p, q} instead of {p, ∼q ← q, q}, where the new input q is inconsistent.

8.3.2 Implicit Consolidation versus Consistency Maintenance

There is a computationally attractive alternative to global consistency maintenance: nonexplosive inference operations based on mutual neutralization of contradictory information. Such inference operations^{5} always yield consistent conclusions only. Thus, they can be viewed as implicit consolidation. While explicit consolidation is characterised by Consistency Preservation,

KB ⊕ F is always consistent,

implicit consolidation by means of a resp. neutralization-based inference operation C^{⊕} is characterised by the postulate of Inherent Consistency,

C^{⊕}(KB + F) is always consistent.

The following question arises: Given a revision operation ⊕, and standard inference operation C which only works for consistent KBs, is there an inherently consistent inference operation C^{⊕} such that

C^{⊕}(KB + F) = C(KB ⊕ F)

In a KS, both ⊕ and C^{⊕} make sense depending on the specific requirements of an application. If a KB has to process a lot of queries, and only a few inputs, then consistency maintenance by means of a revision operation seems to be feasible. If, on the other hand, a KB has to process a lot of inputs, and only a few queries, then revision may be not feasible due to the fact that global inconsistency detection is hard to compute, and an inherently consistent inference operation might be the better choice.

5Investigated, e.g., in the logic of argumentation, and the area of defeasible inheritance. In [Wagner 1993a], neutralization-based top-down reasoning procedures have been proposed for extended logic programming.

Further Topics, Open Problems

9.1 Planning in Active Knowledge Systems

A planning problem in an active knowledge system AK is a triple ⟨X_{0}, O, G⟩ consisting of

1. an initial state, i.e. a knowledge base X_{0} ∈ L_{KB} of a KS K,

2. a set of admissible operators O ⊆ R(L_{Input}^{x} ← L_{Query}^{x}), i.e. a set of action rules in AK, and

3. a goal G ∈ L_{Query}, being a closed query formula.

A successful plan is a sequence of admissible actions, resp. instantiated operators, o_{1}, o_{2},…, o_{n}, such that its application to the intial state yields the desired goal:

o_{n} ∘… ∘ o_{2} ∘ o_{1}(X_{0}) ⊢ G

Obviously, STRIPS is a special case of planning in AA.

Example 24 (Blocks World)  X_{0} = {on(a, b), on(b, c), on(c, t), clear(a)}

O = \{ \begin{matrix}putonblock(x, y) : \\ on(x, y) ∧ clear(z) ∧ −on(x, z) ∧ −clear(y) \\ ← on(x, z) ∧ clear(x) ∧ clear(y) ∧ x ≠ y ∧ y ≠ z ∧ x ≠ t ∧ y ≠ t \\ putontable(x) : \\ on(x, t) ∧ clear(z) ∧ −on(x, z) \\ ← on(x, z) ∧ clear(x) ∧ x ≠ t ∧ z ≠ t \end{matrix}

In order to have b on a, and c not clear, we can perform the following sequence of actions:

puton(b, a) ∘ puton(a, c) ∘ putontable(b) ∘ putontable(a)(X_{0}) ⊢ on(b, a) ∧ −clear(c)

9.2 Active Knowledge Systems and Formal Theories of Action

Many action formalism may be mapped into active knowledge systems. We only illustrate this by means of examples.

Example 25 (Yale Shooting) In [GL93], action domains like the following are formalized:

D = \{ \begin{matrix}initially ∼loaded, alive \\ load causes loaded \\ shoot causes ∼alive if loaded \\ shoot causes ∼loaded \end{matrix}

This can be expressed with extended action rules (refering to previous events by means of PEvt) as follows:

X = {∼loaded, alive}

R = \{ \begin{matrix}loaded ← PEvt(load) \\ ∼alive ← PEvt(shoot), loaded \\ ∼loaded ← PEvt(shoot) \end{matrix}

9.3 Weighted Knowledge Bases

In a weighted knowledge base, an information unit is a weighted atom, resp. literal, i.e. inputs are correspondingly labelled. This allows reasoning with uncertain information. Various uncertainty formalisms could be employed for this purpose. A particular interesting one with respect to its treament of negative information seems to be the possibility theory of Dubois and Prade.

Bibliography

[Abi88] S. Abiteboul: Updates – a New Frontier, Proc. ICDT-88, Springer LNCS, 1988.

[AN84] A. Almukdad and D. Nelson: Constructible Falsity and Inexact Predicates, JSL 49:1 (1984), 231–233.

[ABW88] K.R. Apt, H. Blair and A. Walker: Towards a Theory of Declarative Knowledge, in J. Minker (Ed.), Foundations of Deductive Databases and Logic Programming, Morgan Kaufmann, 1988.

[AB90] K.R. Apt and M. Bezem: Acyclic Programs, Proc. ICLP 1990, MIT Press, 1990.

[BG93] C. Baral and M. Gelfond: Logic Programming and Knowledge Representation, Technical Report, University of Texas at El Paso, 1993.

[Bel77] N.D. Belnap: A Useful Four-valued Logic, in G. Epstein and J.M. Dunn (Eds.), Modern Uses of Many-valued Logic, Reidel 1977, 8–37.

[BF91] N. Bidoit and C. Froidevaux: Negation By Default and Unstratifiable Logic Programs, Theoretical Computer Science 78 (1991), 85–112.

[Bry90] F. Bry: Intensional Updates – Abduction via Deduction, Proc. Int. Symp. on Logic Programming, 1990.

[Cha91] S. Chakravarthy: Active Database Management Systems – Requirements, State-of-the-art, and an Evaluation, in H. Kangassalo (Ed.), Entity-Relationship Approach: The Core of Conceptual Modelling, Elsevier Science Publishers, 1991.

[CT92] C.B. Cross and R.H. Thomason: Conditionals and Knowledge Base Update, in P. Gärdenfors (Ed.), Belief Revision, Cambridge University Press, 1992, 247–275.

[vEK76] M.H. van Emden and R.A. Kowalski: The Semantics of Predicate Logic as a Programming Language, J. of the ACM 23:4 (1976), 733–742.

[FUV83] R. Fagin, J.D. Ullman and M. Vardi: On the Semantics of Updates in Databases, Proc. ACM PODS 83, 1983.

[Fit93] M. Fitting: Metric Methods, Three Examples and a Theorem, J. Logic Programming, 1993.

[Gab85] D. Gabbay: Theoretical Foundations for Nonmonotonic Reasoning in Expert Systems, in K.R. Apt (Ed.), Proc. NATO Advanced Study Institute on Logics and Models of Concurrent Systems, Springer Verlag, 1985, 439–457.

[Gär88] P. Gärdenfors: Knowledge in Flux, MIT Press, Cambridge, 1988. [GR 92] P. Gärdenfors and H. Rott: Belief Revision, Report 30, Konstanzer Berichte zur Logik und

Wissenschaftstheorie, Universität Konstanz, 1992.

[vGT91] A. van Gelder and R.W. Topor: Safety and Translation of Relational Calculus Queries, ACM Transactions on Database Systems 16:2 (1991), 235–278.

[Gel92] M. Gelfond: Logic Programming and Reasoning with Incomplete Information, Proc. Workshop on Extensions of Logic Programming 1992, to appear in Annals of Mathematics and AI.

[GL88] M. Gelfond and V. Lifschitz: The Stable Model Semantics for Logic Programming, Proc. ICLP 1988, MIT Press, 1988.

[GL90] M. Gelfond and V. Lifschitz: Logic Programs with Classical Negation, Proc. ICLP 1990, MIT Press, 1990.

[GL91] M. Gelfond and V. Lifschitz: Classical Negation in Logic Programs and Disjunctive Databases, J. New Generation Computing 9 (1991), 365–385.

[GL93] M. Gelfond and V. Lifschitz: Representing Actions in Extended Logic Programming, J. Logic Programming 17 (1993), 301–322.

[Han91] S.O. Hansson: Belief Base Dynamics, dissertation, Uppsala University, 1991.

[KM93] Y. Kaluzkuy and A.Y. Muravetsky: A Knowledge Representation Based on the Belnap’s Four-Valued Logic, J. of Applied Non-Classical Logics 3:2 (1993), 189–203.

[KM91] H. Katsuno and A.O. Mendelzon: On the Difference between Updating a Knowledge Base and Revising It, Proc. KR’91, Morgan Kaufmann, 1991.

[Kör66] S. Körner: Experience and Theory, Kegan Paul, London, 1966.

[LPS93] D. Laurent, V. Phan Luong and N. Spyratos: Updating Intensional Predicates in Deductive Databases, Proc. 9th IEEE ICDE 93, 1993.

[LPR93] N. Leone, L. Palopoli and M. Romeo: Updating Logic Programs, Proc. ISMIS’93, Springer LNAI, 1993.

[Lev84] H.J. Levesque: Foundations of a Functional Approach to Knowledge Representation, AI 23:2, 1984, 155-212.

[Lev86] H.J. Levesque: Making Believers out of Computers, AI 30 (1986), 81-107.

[Lev88] H.J. Levesque: Logic and the Complexitiy of Reasoning, J. Philosophical Logic 17 (1988), 355–389.

[LMR92] J. Lobo, J. Minker and A. Rajasekar: Foundations of Disjunctive Logic Programming, MIT Press, 1992.

[Min82] J. Minker: On Indefinite Databases and the Closed-World Assumption, Proc. of CADE-82, 1982, 292–308.

[MR93] J. Minker and C. Ruiz: Semantics for Disjunctive Logic Pograms with Explicit and Default Negation, Proc. of ISMIS’93, Springer LNAI, 1993. 16–26.

[Nut88] D. Nute: Defeasible Reasoning and Decision Support Systems, Decision Support Systems 4 (1988), 97–110.

[Pea93] D. Pearce: ‘Answer Sets and Constructive Logic, II: Extended Logic Programs and Related Nonmonotonic Formalisms, in L.M. Pereira and A. Nerode (Eds.), Logic Programming and Nonmonotonic Reasoning, MIT Press, 1993.

[PW90] D. Pearce and G. Wagner: Reasoning with Negative Information I – Strong Negation in Logic Programs, LWI Technical Report, Freie Universität Berlin, 1989. Also in L. Haaparanta, M. Kusch and I. Niiniluoto (Eds.), Language, Knowledge, and Intentionality, Acta Philosophica Fennica 49, 1990.

[Pel86] F.J. Pelletier: Seventy-Five Problems for Testing Automatic Theorem Provers, J. Automated Reasoning 2 (1986), 191–216.

[PA92] L.M. Pereira and J.J. Alferes: Wellfounded Semantics for Logic Programs with Explicit Negation, Proc. ECAI’92, Wiley, 1992.

[Plo76] G.D. Plotkin: A Powerdomain Construction, SIAM J. Comp. 5:3 (1976), 452–487.

[Pri89] G. Priest: Reasoning about Truth, AI 39 (1989), 231–244.

[PP90] H. Przymusinska and T.C. Przymusinski: Weakly Stratified Logic Programs, Fundamenta Informaticae 13 (1990), 51–65.

[Prz88] T.C. Przymusinski: On the Declarative Semantics of Logic Programs with Negation, in J. Minker (Ed.), Foundations of Deductive Databases and Logic Programming, Morgan Kaufmann, 1988.

[Ras94] L. Raschid: A Semantics for a Class of Stratified Production System Programs, J. Logic Programming (1994).

[Rei78] R. Reiter: On Closed-World Databases, in J. Minker and H. Gallaire (Eds.): Logic and Databases, Plenum Press, 1978.

[Rei92] R. Reiter: On Formalizing Database Updates – Preliminary Report, Proc. EDBT-92, 1992.

[RT88] K.A. Ross and R.W. Topor: Inferring Negative Information from Disjunctive Databases, J. Automated Reasoning 4:2 (1988), 397–424.

[Sak89] C. Sakama: Possible Model Semantics for Disjunctive Databases, Proc. 1st Int. Conf. on Deductive and Object-Oriented Databases (DOOD’89), North-Holland, 39–383, 1989.

[SI94] C. Sakama and K. Inoue: An Alternative Approach to the Semantics of Disjunctive Logic Programs and Deductive Databases, J. Automated Reasoning, forthcoming.

[Sco72] D. Scott: ‘Continous Lattices: Toposes, Algebraic Geometry and Logic’, Springer Lecture Notes in Mathematics 274 (1972), 97–136.

[Smy78] M. Smyth: Powerdomains, J. Comp. Syst. Sci. 16:1 (1978), 23–36.

[Sti86] M. Stickel: Schubert’s Steamroller, J. Automated Reasoning 1 (1986), 89–101.

[Thi92] E. Thijsse: Partial Logic and Knowledge Representation, dissertation, Tilburg University, 1992.

[Wag91a] G. Wagner: Logic Programming with Strong Negation and Inexact Predicates, J. Logic and Computation 1:6 (1991), 835–859.

[Wag91b] G. Wagner: A Database Needs Two Kinds of Negation, in H.-D. Gerhard and B. Thalheim (Eds.), Proc. 3rd Int. Symp. on Mathematical Fundamentals of Database and Knowledge Base Systems MFDBS-91, Springer LNCS 495 (1991), 357–371.

[Wag93a] G. Wagner: Neutralization and Preemption in Extended Logic Programming, in A. Voronkov (Ed.), Logic Programming and Automated Reasoning, Proc. LPAR’93, Springer LNAI 698 (1993).

[Wag93b] G. Wagner: Disjunctive Fact Bases and Logic Programming – Preliminary Report, in C. Baral and M. Gelfond (Eds.), Proc. ILPS’93 Workshop on Logic Programming with Incomplete Information, 1993.

[Wag94a] G. Wagner: Vivid Logic – Knowledge-Based Reasoning with Two Kinds of Negation, Springer LNAI 764 (1994).

[Wag94b] G. Wagner: Belnap’s Epistemic States and Negation-as-Failure, Proc. of the Analyomen 2 Workshop on Negation, Leipzig 1994, to appear with de Gruyter.

[Zan93] C. Zaniolo: On the Unification of Active Databases and Deductive Databases, in M. Worboys and A.F. Grundy (Eds.), Advances in Databases, Proc. of BNCOD-11, Springer LNCS 696, 1993.