
## 6.1.1 Independence In Propositional Logic

There are other forms of independence in propositional logic that we have not considered in this article, especially, definability, controllability (Lang & Marquis, 1998b) as well as conditional independence (Darwiche, 1997).  If X, Y and Z are three disjoint sets of variables and Σ is a knowledge base then X and Y are conditionally independent w.r.t. Z knowing Σ if and only if for any Z-world ω Z, once we know ω Z (and Σ), learning something about X cannot make us learn anything new about Y (and vice versa ). The computational issues pertaining to conditional independence and to stronger notions as well as related notions such as relevance between subject matters (Lakemeyer, 1997) and novelty (Greiner & Genesereth, 1983), have been extensively studied in a companion paper (Lang, Liberatore, & Marquis, 2002).

## 6.1.2 Implicit And Explicit Dependence

Several approaches to belief change make use of a explicit dependence relation, which means that it is part of the input (while ours is implicit, i.e., derived from the input). Thus, computing independence relations from a knowledge base can be seen as an upstream task enabling us to specify the "core" (minimal) independence relation upon which the belief change operator is based; this core independence relation can then be completed by specifying explicitly some additional dependencies using knowledge about the domain.  Such an approach has been proposed for belief revision in (Fariñas del Cerro & Herzig, 1996),
for belief update in (Marquis, 1994) and (Herzig, 1996) and for reasoning about action in
(Herzig & Rifi, 1999).

## 6.1.3 Independence And Contexts

Contextual reasoning (Ghidini & Giunchiglia, 2001) has been introduced for formalizing domains in which knowledge can naturally be divided into parts (contexts).  Each context is characterized by its own language and alphabet. The knowledge base of a context contains what is relevant to a part of the domain. However, it is not guaranteed that the different parts of the domain do not interact, so inference in one context may be affected by the knowledge of some other context.

The main difference between contextual reasoning and independence is that the latter is a study of the relevance relation that can be drawn from a "flat" (i.e., not divided into contexts) knowledge base; whereas contextual reasoning is on knowledge about specific contexts, that is, knowledge is expressed by specifying which context it refers to. In other words, the relevance relation is a result of reasoning about knowledge in studying dependency; on the other hand, it is one of the data that has to be provided for reasoning about contexts.

## 6.1.4 The Definition Of Irrelevance By Levy Et Al.

The definition of irrelevance given by Levy, Fikes, and Sagiv (1997) aims at establishing which facts of a knowledge base are irrelevant to the derivation of a query. In particular, they consider a first-order logic with no function symbols and a set of inference rules. A
knowledge base is a set of closed formulas (formulas with no free variables). Derivation of a