A Logical Account of Relevance
Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence. Knowledge Representation. Pages 853-860.
© 1995 International Joint Conferences on Artificial Intelligence
Abstract
The study of relevance has gained considerable attention recently in areas as diverse as machine learning and knowledge representation. In this paper, we focus on one particular area, namely relevance in the context of logical theories. We are interested in answering questions like: when is a sentence (or theory) relevant to a set of propositions, or, when is one set of propositions relevant to another given some background theory? The answers are given semantically in terms of a logic of belief and syntactically in terms of prime implicates . Furthermore, rather than merely adding yet another set of definitions of relevance to the many that already exist, we also show close connections to two others that were recently proposed, thus pointing to some common ground at least as far as logical relevance is concerned.
- Da.r94
- Da.rwiche, A., A logical notion of conditional inde- pendence: properties a.nd applications, in Proc. of the AAAI Fall Symposium on Relevance, New Or- leans, 1994, pp. 36-40.
- Da.rwiche, A. a.nd Pearl, J., Symbolic Causal Net- works, in Proc. AAAI-94, AAAI-Press, 1994, pp. 238-244.
- de Kleer, J., An assumption-based TMS. Artificial Intelligence, 28(2), 1986, pp. 127-162.
- Greiner, R. a.nd Subra.ma.nia.m, D. (Eds.), Proceed- ings of the AAAI Fall Symposium on Relevance, New Orleans, 1994.
- Halpern, J. Y. a.nd Moses, Y. 0., A Guide to com- pleteness a.nd complexity for modal logics of knowl- edge a.nd belief, Artificial Intelligence, 54, pp. 319- 379, 1992.
- Hintikka., J., Knowledge and Belief: An Introduction to the Logic of the Two Notions. Cornell University Press, 1962.
- Kripke, S. A., Sema.ntical considerations on modal logic. Acta Philosophica Fennica 16, 1963, pp. 83- 94.
- La.k92] La.kemeyer, G., All You ever Wanted to Know about Tweety, in Proc. of the Srd International Confer- ence on Principles of Knowledge Representation and Reasoning (KR '92}, Morgan Kaufmann, Sa.n Mateo, CA, 1992, pp. 639-648.
- La.k93] La.kemeyer, G., All They Know About, Proc. of the 11th National Conference on Artificial Intelligence {AAAI-99}, MIT Press, Cambridge, MA, 1993, pp. 662-667.
- La.k94] La.kemeyer, G., Relevance in a. Logic of Only Know- ing About a.nd its Axioma.tiza.tion, in Proc. of the AAAI Fall Symposium on Relevance, New Orleans, 1994, pp. 149-153.
- La.k95] La.kemeyer, G., Relevance in a. Logic of Only- Knowing-About and its Axiornatization, to appear in: A. La.ux a.nd H. Wa.nsing ( eds.) Know ledge and Belief in Philosophy and Artificial Intelligence, Aka.demie-Verlag, Berlin, 1995.
- Levesque, H. J., All I Know: A Study in Autoepis- temic Logic. Artificial Intelligence, North Holland, 42, 1990, pp. 263-309.
- Levy, A., Fikes, R., a.nd Sa.giv, Y., A Proof- Theoretic Approach to Irrelevance: Foundations a.nd Applications, in Proc. of the AAAI Fall Sympo- sium on Relevance, New Orleans, 1994, pp. 149-153.
- Lin, Fa.ngzhen a.nd Reiter, R., Forget It!, in Proc. of the AAAI Fall Symposium on Relevance, New Or- leans, 1994, pp. 154-159.
- Pea.
- Pearl, J ., Probabilistic Reasoning in Intelligent Sys- tems: Networks of Plausible Inference. Morgan Kaufmann Publishers, Sa.n Francisco, 1988.
- Reiter, R. und de Kleer, J., Foundations of assumption-based truth maintenance systems: pre- liminary report. Proceedings of the Sixth National Conference on Artificial Intelligence {AAAI-87}, Seattle, WA, 1987, pp. 183-188.
- Subra.ma.nia.m, D. a.nd Genesereth, M. R., The Rel- evance of Irrelevance, in Proc. of the 10th Int. Joint Conf. on Artificial Intelligence (IJCAI-87}, Morgan Kaufmann, 1987, pp. 416-422. IJCAI
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
The study of relevance has gained considerable atten tion recently in areas as diverse as machine learning and knowledge representation [GS94]. In this paper, we focus on one particular area, namely relevance in the context of propositional logical theories. We are interested in answering questions like: when is a sentence (or theory) relevant to a set of propositions, or, when is one set of propositions relevant to another given some background theory?
In order to get a better feel for what we are get ting at, let us consider the following example adapted from [DP94] .
Here rain, 'ilet, and sprinkler ...on stand for the proposi tions "it rains", "the ground is wet", and ''the sprinkler is on", respectively. a clearly seems to tell us some thing relevant about the proposition rain (as well as sprinkler ...on and 'ilet). On the other hand, a seems ir relevant to anything else like Jack..is..happy. When we look a little closer, not everything a conveys is relevant to rain because the sentence contains the extraneous information (sprinkler....on :J 'ilet). On the other hand, everything a tells us is about the ground being wet and, hence, we want to call a strictly relevant to 'ilet.
It also makes sense to talk about relevance between propositions relative to a background theory. For exam ple, given a, rain should count as relevant to 'ilet since the latter is true whenever the former is. On the other hand, there really is no connection between rain and sprinkler ...on, since they are either forced to both be false by some other condition (the ground is not wet) or their truth values can vary independently of each other. Therefore, rain and sprinkler ...on are not relevant to each other given a.
If we view relevance with regard to what a sen tence (or theory) tells us about the world, as is done in this paper, then logically equivalent formulations should not change the relevance relation. For exam ple, given a' = (rain:) 'ilet) 1\ rain, rain and 'ilet are not considered relevant to each other, since a' is logi cally equivalent to (1ilet 1\ rain). In this respect, our approach is quite different from work such as [SG87; LFS94], where relevance has a distinct syntactic flavor. There, rain is viewed as relevant to 'ilet since rain is used in the syntactic derivation of 'ilet.
The formalization of logical relevance chosen in this paper is based on a logic of belief developed ear lier [Lak92], which allows us to express that a sentence is believed about a set of proposition (also called the subject matter) and, more importantly, that a sentence is all that is known 1 about a subject matter (only-knowing-about for short). With these concepts we say that a sentence a is relevant top just in case it is impossible to know noth ing about p assuming a is all that is known. Going back to our initial example, a is then found to be relevant to rain because knowing only a implies that we know something nontrivial about rain, namely (rain:::> wet). Note the importance of assuming that only o: is believed and nothing else. For if we merely require o: to be be lieved, we do not rule out believing wet as well, in which case o: 1\ wet reduces to wet and all relevance to rain disappears.
1 For the purpose of this paper the distinction between knowledge and belief is irrelevant.
Given a logic of only-knowing-about, it is perhaps not surprising that we are able to express this form of rele vance in such a direct manner, since the logic has a built in primitive notion of relevance in the sense of aboutness. It is perhaps more interesting that this primitive notion suffices to provide a reasonable semantics to other vari eties of relevance as well. For instance, rain is relevant to wet relative to o: because what is known about rain, viewed as a sentence, is relevant to wet.
Besides defining various forms of relevance seman tically in terms of only-knowing-about, we also pro vide syntactic characterizations in terms of prime im plicates in each case. Furthermore, rather than merely adding yet another set of definitions of relevance to the many that already exist, we also show close connec tions to two others that were recently proposed [DP94; LR94], thus pointing to some common ground at least as far as logical relevance is concerned.
The rest of the paper is organized as follows. In Sec tion 2, we define the semantics of only-knowin~-about, which is a variant of the semantics presented in [Lak92]. Section 3 contains our various definitions of relevance using the logic of the previous section. In Sections 4 and 5, we compare our work to that of Darwiche and Pearl on the one hand and Lin and Reiter on the other. We end the paper with a summary and some concluding remarks.
2 The Logic of Only-Knowing-About
The logic of only-knowing-about, which was origi nally introduced in [Lak92], extends earlier work by Levesque [Lev90], who formalized what it means to only know a sentence, which can be thought of as the limit-case of only-knowing-about, where the subject matter includes everything the agent has any informa tion about. The semantic framework for all these in vestigations is possible-world semantics [Kri63; Hin62; HM92].
2.1 From Only-Knowing to Only-Knowing-About
Before introducing the semantics for "all the agent knows about x is y," we start out with the simpler case of Levesque's only-knowing. There an agent knows a sen tence o:, denoted as Lo:, just in case o: is true in all the worlds which the agent thinks are possible (or accessi ble). The reader should think of a world simply as a truth assignment for the atomic propositions. (Formal definitions are deferred to Section 2.3 below.) To define only-knowing, Levesque considers another modality N, where No: means that o: is true in all the impossible (or inaccessible) worlds. 2 While Lo: is best understood as "the agent knows at least that o: is true," No: should be read as "the agent knows at most -,a." With that only knowing o:, denoted as Oo:, reduces to knowing at least o: and at most o:, that is, Oo: holds just in case both Lo: and N...,o: hold.
Let us now consider how to extend these ideas to in clude a subject matter. Since we confine ourselves to propositional logic, we define a subject matter 1r as a finite set of atomic propositions. For each such 1r we introduce new modal operators L(1r}, N(1r}, and 0(1r}, where L(1r}o: is read as "the agent knows at least o: about 1r," N(1r}o: as "the agent knows at most that o: is false about 1r," and 0(1r)o: as "all the agent knows about 1r is o:." As in the case of only-knowing, 0(1r}o: can be viewed as shorthand for L(1r)o: 1\ N(1r)...,o:.
As for the semantics of these modalities, suppose the beliefs of the agent are given by the set of worlds M the agent thinks possible. To find out what the agent knows about 1r we construct a set of worlds Ml,.. which, intu itively, represents what the agent knows after forgetting everything that is not relevant to 1r. With that the oper ators L(7r),N(7r), and 0(1r} are interpreted just like L,N, and 0 except that we are using Ml,.. instead of M. For example, an agent believes o: about p at a set of worlds M just in case she believes o: at Ml{p}·
The loe;ic is a slight variant of the one presented in [Lak92j. In particular, we ignore nested modalities, which are not essential for our purposes. The operators L(1r} and N(1r} were not used in the previous version of the logic.
2.2 The Language and Other Notation
The primitives of the language are a countably infinite set P of atomic propositions (or atoms), the connectives V, ...,, and the modal operators L,N,O, L(1r}, N(1r}, and 0(1r} for every every finite set of atomic propositions 1r with the restriction that none of the rriodal opera tors occurs within the scope of another modal opera tor. Sentences are formed in the usual way from these primitives. 3
Notation: As usual, literals are either atoms or negated atoms and clauses are disjunctions of literals. We write false as an abbreviation for (p 1\ ...,p), where pis some atom, and true for -,false. Given an atomic proposi tion p and and a clause c, we say that c mentions p just in case either p or ...,p occurs in c.
It is often convenient to identify a clause with the set ofliterals occurring in the clause. A clause cis contained in a clause c' ( c ~ c') if every literal in c occurs in c'.
2 Note that here impossible does not mean that these worlds are logically impossible. They are merely incompati ble with the agent's knowledge.
3 We will freely use other connectives like /\, :) and ::, which should be understood as syntactic abbreviations of the usual kind.
We write c S c' instead of c ~ c' and c' ~ c. Given a finite set of sentences r' A.,er I denotes the conjunction of all the sentences occurring in r . If r is empty, A.,er I denotes true. For notational convenience, we sometimes use r itself instead of A.,er I within a sentence.
When referring to singleton subject matters, we usu ally omit the curly brackets. For example, given an atom p, we write O(p) instead of O({p}) and Mlp instead of Ml{p} ·
Finally, a sentence is called objective if it contains no modal operator and subjective if every atom occurs within the scope of a modal operator.
2.3 A Formal Semantics
Worlds are defined extensionally as propositional truth assignments. Hence for any given set of worlds M (the possible worlds) its complement (the impossible worlds) is always well defined.
Definition 1 (Worlds)
A world w is a function w : P ----+ { t, f}.
We begin by reviewing the semantics of Levesque's logic of only-knowing. Let w be a world and M a set of worlds.
M , wl=p {::::} w(p) = t, where pis an atom
M,wl=-.~ {::::} M, w!Jt~
M, wl=~ V ,8 {::::} M, wl=~ or M, wi=,B
M, wi=L~ {::::} for all w' EM, M , w'l=~
M,wi=N~ {::::} for all w' (/. M, M, w'l=~
M,wi=O~ {::::} M, wi=L~ and M , wi=N-.~
For a given set of worlds M and a subject matter 1r, we define Ml,. as the set of all worlds that satisfy precisely the known objective sentences that are about 7r . Since we are dealing with propositional beliefs only, we can, first of all, confine ourselves to clauses instead of arbitrary objective sentences. The idea to get at only those beliefs that are about 1r is to consider the smallest clauses which are believed and which mention at least one of the atoms in 1r . Ml,. is then simply the set of all worlds that satisfy all of these clauses. Formally:
Definition 2
Let M be a set of worlds and 1r a subject matter.
- A clause c is called M-minimal iff MI=Lc and for all clauses c' S c, MIJtLc'.
- A clause c is called M -p-minimal iff c zs M -minimal and, in addition, c mentions p.
- rM,. = { c 1' c is an M -p-minimal clause for some p E 1r.}
- Ml,.={wlwl=cforallcEfM,,.}.
By restricting ourselves to M-p-minimal clauses, we rule out clauses that mention the subject matter but do not really tell us anything about it . For example, let the subject matter be p and assume all we know is q, that is, M = { w I w l=q}. Then we certainly also know (p V
q), which is not M-minimal because q is known as well . While (p V q) mentions the subject matter p, it does so, in a sense, only accidentally, since it does not convey us what is really known about p , namely nothing. The only M-minimal clause mentioning pis (p V -.p) , which gives us the right information.
Given these definitions of what it means to forget ir relevant things, we obtain the following semantic rules for knowing and only-knowing about .
Note:
In
the original definition of 0(1r) in [Lak92], M, wi=0(7r)~ was defined as Ml,., wi=O~ and M, wi=L~ . The restric tion "M, wi=L~" was necessary to prevent unintuitive properties in the case of nested beliefs. In the unnested case, as in this paper, these problems do not occur and we get by with the simpler definition. In the following we often write wl=~ instead of M, wl=~ if~ is objective and Ml=~ if~ is subjective.
Logical implication, validity, and satisfiability are de fined as usual: A set of sentences r logically implies a sentence ~ (fl=~) iff for all worlds w and for all sets of worlds M, if M,wl=1 for all 1 E f , then M , wl=a . a is valid (l=a) iff {}l=a. a is satisfiable iff -.a is not valid. 4
2.4 Prime implicates
Given all an agent knows, her knowledge about a sub ject matter can be characterized succinctly using prime implicates. Given a sentence a (the agent 's knowledge) , the prime implicates of a are simply the smallest clauses (in terms of set inclusion) that are logically implied by a . Formally:
Definition 3 (Prime Implicates)
Let a be an objective sentence. A clause c zs called a prime implicate of a iff
For any atom p, let P( a , p) = { c I c is a prime impli cate of a mentioning p} and P(a) = Upe a P(a,p) . 5
For example, if a = (p V q) 1\ (p V r V s) 1\ -.s, then P (a, p) = { (p V q), (p V r), (p V -.p)} . In cases like a = q, where pis not contained in a at all , P( a , p) = { (p V -.p)} .
It is easy to see that for any given a and p, P( a , p) and P(a) are finite assuming we identify clauses with sets of literals and hence eliminate redundancies. What is known about 1r relative to a sentence (background the ory) a has a simple characterization in terms of prime implicates of a, as the following theorem shows. 6
4 In his original definition of only-knowing [Lev90]. Levesque considers only what he calls maximal sets of worlds instead of arbitrary ones. Here we simply ignore this issue since it is not important for the purpose of this paper.
5 p E a stands for p occurs in a.
Lemma 1 Let MI=Oa. Then for any atom p, c E 'P( a, p) iff c is an M -p-minimal clause.
show that MI=0(1r}/3*. Together with the fact that a sentence that is only-believed about 1r is unique up to equivalence, the theorem follows.
To show that MI=0(1r}/3*, consider MI.,. { w I wl=c for all c E rM,7r} with rM,7r { c I c is an M -p-minimal clause for some p E 1r}. By Lemma 1, rM,7r = {c I c E 'P(a,p) for some p E 7r}. Therefore, MI.,.I=0/3* and thus MI=0(1r}/3*. ·
3 Varieties of Relevance
In this section, we will see how logical relevance in the sense we introduced in Section 1 can be captured in a natural way using only-knowing-about. 7 We begin by defining what it means for a sentence to be relevant to some subject matter. The intuition behind a being rel evant to 1r is that a must contain nontrivial information about 1r . Our logic allows us to express this directly.
Definition 4 An objective sentence a is relevant to a subject matter 1r iff I=Oa :::> -.0(1r)(p V -.p).
Example 1 While -.p and (p :::> q) /\ ( q :::> r) are relevant top, (q :::> r) and p :::> (q :::> p) are not.
Theorem 3 a is relevant to 1r iff there is some 1 E 'P( a) such that i:f'Y and 1 mentions some p E 1r.
Proof : The theorem follows immediately from Theo rem 2. ·
While the previous definition, in a sense, only requires part of the sentence to be about 1r, we can be even more restrictive and require that everything a tells us is about 1r in a relevant way and hence arrive at the notion of strict relevance. 8
Definition 5 An objective sentence a is strictly rele vant to a subject matter 1r iff !:fa and 0(1r)a is satisfi able.
6 While the result follows from Theorem 2 in [Lak92], where it is shown how to compute what is only-known about 1r using deKleer's ATMS[deK86; RdK87], we give a much simpler direct proof here.
7 Some of the material of this section appeared in [Lak94] . 8 This definition was first introduced in [Lak93].
Example 2 (p :::> q) /\ ( q :::> r) is not strictly relevant top because (q :::> r) is not about p. However, (p = q)/\(q :::> r) is strictly relevant top. This time ( q :::> r) is recognized as being about p since p and q are assumed to be equivalent.
Theorem 4 Let a be an objective sentence such that !:fa. Then the following statements are equivalent.
1. a is strictly relevant to 1r.
- I=Oa :::> 0(1r)a.
- 3· l=a = /\pe.,.A,e'P(a,p) 'Y·
Proof: The equivalence of (2) and (3) follows immedi ately from Theorem 2. We now show that (1) iff (2) . If direction: By assumption, !:fa. Also, Oa is satisfiable for any objective a. Since I=Oa :::> 0(1r)a by assump tion, 0(1r)a is satisfiable as well .
Only-if direction: Let 0(1r)a be satisfiable. Hence there is an M such that MI.,.I=Oa, that is, MI.,. = {w I wl=a}. To show that I=Oa :::> 0(1r)a, let M*I=Oa . Hence M* = MI.,. . One can easily show that MI.,. = (MI.,.)I.,. for any M. Thus M* = M*l.,. and, therefore, M*I.,.I=Oa, which immediately implies M*I=0(1r)a. ·
Next we want to express that a subject matter is relevant to another relative to some background theory.
Definition 6 Let 1r1 and 1r2 be sets of atoms and a and f3 objective sentences such that I=Oa :::> 0 ( 1r2) f3. 1r1 is relevant to 1r2 with respect to a {Ra( 1r1, 1r2)] iff 1r1 n 1r2 # {} or f3 is relevant to 1r1.
In other words, 1r1 is relevant to 1r2 if whatever is known about 1r2 contains some nontrivial information about 1r1.
Example 3
Let a = (p V q) /\ (q V r). Since I=Oa :::> O(q)a and I=Oa :::> O(p)(p V q), we obtain immediately that p is relevant to q. Similarly, q is relevant to r . However, p is not relevant to r, since I=Oa :::> O(r)(q V r) and I=O(q V r) :::> O(p)(p V -.p).
Theorem 5 Let 1r1 and 1r2 be disjoint sets of atoms. Ra( 1r1, 1r2) iff there is a 1 E 'P( a) such that 1 mentions atoms from both 1r1 and 1r2.
Proof: Let f3 be such that I=Oa :::> 0(1r2}/3.
If direction: Let 1 E 'P( a) such that 1 mentions both 1r1 and 1r2. Then 1 is also a prime implicate of /3. Since 1 mentions atoms from both 1r1 and 1r2, 1 is not a tau tology. Thus, by Theorem 3, f3 is relevant to 1r1 . '
Only-if direction: Let Ra ( 1r1, 1r2). Then f3 is relevant
to 1r1 and by Theorem 3, there is a c E 'P(/3) such that c mentions some atom in 1r1. Also l=/3 = 1\ 1\ 1. pE.,., rE'P(a,p)

Assume none of these 1 mentions 1r1 . Then none of the prime implicates of f3 mentions atoms from 1r1, a contra diction. ·
The relation Ra( 1r1, 1r2) is obviously reflexive by defini tion. While symmetry is not obvious from the definition, it nevertheless follows immediately from Theorem 5, that is, if 1r1 is relevant to 1r2 with respect to a, then 1r2 is relevant to 1r1. Note, however, that transitivity does not hold. Example 3 provides a counterexample.
While the previous definition requires 1r1 and 1r2 only to be weakly connected to each other, the following and last definition forces this connection to be much stronger. In particular , we require that whatever is known about 1r1 is also known about 1r2 .
Definition 7
1r1 is subsumed by 1r2 with respect to a {1r1 -<a 1r2} iff f:Oa :J (L(1r1),8 :J L(1r2),8) for all objective ,B. 1r1 and 1r2 are equivalent with respect to a {1r1 ::::ia 1r2} iff 1r1 -<a 1r2 and 11"2 -<a 11"1.
It is easy to see that f:a :J (p = q) implies p :::::a q. Note, however, that the converse does not hold. For example, p :::::a q holds even for a= (p :J q). With Theorem 2 we obtain the following
As an aside, while the syntactic characterizations of our definitions of relevance do not appeal to modal logic at all , which may be a consolation for those wary of non classical logic, the modal characterization has its advan tages. For one, it provides a model theoretic account of relevance. For another, characterizing relevance as certain valid sentences opens the door to reason about relevance within the logic itself. (See also [Lak95] for a proof theoretic characterization of relevance using only knowing-about.)
Besides the four definitions of relevance given above others are plausible as well. For example, we could re place relevant by strictly relevant in Definition 6. How ever, we won't pursue this issue further at this point. Instead we take a closer look at how our definitions, in particular, Definition 6, relate to other work on relevance in the literature.
4 Conditional independence
Recently Darwiche and Pearl (DP) defined condi tional independence for disjoint sets of atomic propo sitions [DP94] in the context of a logical theory. This notion was proposed in close analogy to conditional in dependence in the probabilistic literature, where it is recognized as being of central importance, in particu lar in areas such as Bayesian Networks [Pea88]. Dar wiche [Dar94] has pointed out how (logical) conditional independence gives rise to a natural notion of relevance, or better, irrelevance.
In this section we will show a close connection between DP's notion of relevance and ours, in particular, Defini tion 6, where we define relevance between two sets of atoms relative to a given background theory.
Notation: Following DP, we use capital letters X, Y, and Z to denote (disjoint) sets of atoms. An instantiation X of X denotes a consistent set of literals over the atoms X, that is, X contains p or ·p for ev ery p E X. For any instantiation X of X, X denotes the set of literals which are complements of literals in X. For example. if X = {p, q, r} and X = { ·p, q, ·r }, then X = {p, ·q, r}. Given sets of literals X and Y, we write {X, Y} instead of XU Y. Also, depending on the context, a set of literals denotes a disjunction of literals or a conjunction. As a rule, whenever the set is added to a theory, it is understood conjunctively. Whenever it appears on the right-hand-side of f:, it is understood disjunctively. Finally, all sentences and sets of sentences are objective unless noted otherwise.
Definition 8 (Conditional Independence)
Let X, Y, and Z be disjoint sets of atomic propositions and ~ a finite set of sentences. ~ finds X independent of Y given Z [h(X, Z, Y)} iff for every instantiation X, Y, and Z of X, Y, and Z, respectively, the logical consistency of~ U {X, Z} and~ U {Y, Z} implies the logical consistency of~ U {X, Y, Z}.
Intuitively, X is independent of Y given Z wrt. ~ if, given full information about Z (namely Z), adding infor mation about X to ~ in no way effects the information about Y. 9 Using one of DP's examples,
finds {rain} independent of {sprinkler _on}, but finds them dependent given {wet}.
While our notion of relevance between sets of atoms is only a two-place relation, there is nevertheless a tight connection with conditional independence. This is best seen using our example from Section 1 rephrased as ~ = {(rain :J wet), (sprinkler ..on :J wet)}. Clearly, rain and sprinkler _on are not relevant to each other, that is, Rt!. ( {rain}, {sprinkler ..on}) does not hold. On the other hand, we obtain that for all possible Z, namely {} and {wet}, h ( {rain}, Z, {sprinkler ..on}) holds. In tuitively, this says that not being relevant to one another is the strongest case of conditional independence, where one quantifies over all possible Z. It turns out that this property holds in general.
Theorem 7 Let X and Y be disjoint sets of atoms and ~ a finite set of sentences. Then Rt!.(X, Y) iff there exists a Z such that·h(X,Z,Y). 10
Proof : (Here we only prove the only-if direction.) Thus, if we assume Rt!.(X, Y), then, by Theorem 5, there is acE P(~) such that c mentions atoms from both X and Y. Thus c = { Z, X 1, YI} for some X 1 , Y1, and Z such that X1 ~ X, Y1 ~ Y, X1 "# {}, andY1 "# {}. We will now show that ·h(X, Z, Y).
9 This definition is also used in the relational database lit erature to characterize what they call embedded multivalued dependencies.
10 -,h,(X, Z, Y) is short for h(X, Z, Y) does not hold.
Since c E P(.6.), Ll~{Z, Xt} and .6.~{Z, Yt} , but .6.f={Z,X1,Yt}. If we choose z, .X1, and ¥1 as instan tiations ~ Z, X 1, and _!'i .!....!espectively, we obtain that .6. U {~,X t} ~nd .6. U { Z, Yt} are both consistent, while .6.U{Z,X1,Yt} is inconsistent . Hence ..,h(X1,Z,Yl).
Since .6. U {Z, Xt} and~ U {Z, Yt} are consistent, there are x and ¥ with x1 ~ x and ¥1 ~ Y such that .6. U { Z, X} and .6. U { Z, Y} are consistent. Since .6.U{Z,X1, Yt} is inconsistent, then so is .6.U{Z,X, Y}. Hence ..,h(X, Z, Y). ·
5 Relevance according to Lin and Reiter
In [LR94], Lin and Reiter (LR) introduce a form of for getting all the information about a proposition in a given set of sentences, which they use, among other things, to define notions of remembering and (ir-)relevance. 11
Our first task will be to show that LR's remembering is related, but not identical to only-knowing-about. The difference arises because LR define remembering what is known about an atomic proposition p in terms of forget ting everything about propositions other than p, which may have the side effect of erasing information about p as well. For example, if .6. = {(p V q)}, then nothing is remembered about p since forgetting everything about q in the LR sense removes the clause (p V q). On the other hand, according to the logic of only-knowing-about, if all you know is .6., then all you know about pis still .6.. De spite these differences, Theorem 9 below characterizes a special case where only-knowing-about and remembering coincide. We begin by formally introducing LR's notion of forgetting.
Definition 9 (Forgetting)
Let .6. be a set of sentences and p an atomic proposition. Let .6.% be the result of replacing every occurrence of p in .6. by true and let D.; be the result of replacing every occurrence of p in .6. by false.
Then forget(.Ll;p) = (.6.% v .6.;).12
Example 4 If .6. {(p V q),(-,p V r),s}, then forget(.Ll;p) = {(q V r), s}.
The following lemma should help to get a better feel for the LR notion of forgetting.
Lemma 8 forget(.Ll;p) is logically equivalent to {c E P(.6.) I c does not mention p}.
11 While LR treat first-order formulas, we restrict ourselves to the propositional case.
12 LR first introduce a semantic definition of forget(~; p) and then show that this syntactic characterization coincides with the semantic one. For simplicity, we ignore the semantic part .
For atoms P1, ... , Pk, LR define forget( .6.; p1, ... , Pk) as forget(forget(.6.; Pl. ... , Pk-d; Pk)· (They show that the order of the atoms does not matter.)
Given forget, LR define remember(.6.;p1, ... ,pk) as a function, which forgets all information about atoms other than P1, ... , Pk.
Definition 10 (Remembering)
Let .6. be a set of sentences such that the only atoms occurring in .6. are P1, .. . , Pk and Pk+1, . . . , Pn. Then remember(.6.; P1, ... , Pk)= forget(.6.; Pk+1, ... , Pn)·
While remember looks a lot like only-knowing-about, there are important differences as the following exam ple demonstrates.
Example 5
Let us consider the same .6. as in Example 4. It is easy to see that f=0(.6.) :::> O(p)[(p V q) 1\ (-,p V r)]. On the other hand, remember(D.;p) =true!
The problem is that remember(.Ll;p), when forgetting about q and r, also removes the clauses (p V q) and (-,pVr). The O(p)-operator, on the other hand, is more sensitive, and hangs on to those clauses since they tell us something about p.
However, if we add q and r to the subject matter, both remember(.6.; p, q, r) and O(p, q, r) produce the same re sult.
The last remark can be generalized as follows.
Theorem 9 Let .6. be a set of sentences and 1r = {P1, ... , pk}. If every prime implicate of .6. that men tions some p E 1r mentions only atoms in 1r, then
Based on forget LR go on to define a notion of (ir-)relevance relative to answering a query posed to a knowledge base and the sentences that could possibly be learned ( = added to the knowledge base) in the fu ture. Ignoring future information for a moment, an atom p is said to be irrelevant for answering q in the knowl edge base .6. just in case .6. and forget(.Ll;p) produce the same answer for q. Consider the following exam ple, where .6. = {(p :::> q), r} and q is the query. Intu itively, while r seems clearly irrelevant to answering q, p should somehow count as relevant. However , both .6. and forget(.Ll;p) = {r} produce the same answer when asking whether q holds, namely unknown. This is where possible future extensions of .6. come in. For example, if p is among the sentences that could be added at some point, then .6. U {p} and forget(.Ll;p) U {p} differ with respect to q, since the former would produce the answer yes and the latter unknown. On the other hand, .6. and forget(.6.; r) would always produce the same answers for q no matter what information is added to them. Hence by considering future extensions of a knowledge base, LR obtain a reasonable notion of distinguishing relevant from irrelevant information when answering a query.
After defining the LR notion of relevance formally, We will show how Ra(7r1 , 7r2 ) can be expressed within this framework.
Definition 11 Let ~1 and ~2 be two finite sets of sen tences, .C a set of learnable sentences and a a sentence.
- ~1 and ~2 are equivalent wrt. a (~1~a~2) iff (a) ~d=a iff ~2f=a and (b) ~1f=...,a iff ~2f=-,a.
- ~1 and ~2 are equivalent wrt. a and .C (~1 ~a.c ~2) iff for all.C' ~ .C, ~1 U.c' ~a ~2 U.C' whenever ~1 U .c' and ~2 U .C' are consistent.
Definition 12 Let ~ be a finite set of sentences, .C a set of learnable sentences (not necessarily finite), p an atomic proposition, and a a sentence.
Then p is irrelevant for answering a in ~ iff ~ ~a,c forget(~;p).
Theorem 10 Let ~ be a set of sentences, 1f'1 and 1f'2 disjoint sets of atoms, and .C the set of all literals. Ra ( 7r1 , 7r2 ) does not hold iff for all sentences a mention ing only atoms in 1f'2 and for all p E 7r1 , p is irrelevant for answering a in~.
6 Conclusion
In this paper we proposed various definitions of relevance within a logic of only-knowing-about. We showed that the semantic definitions have simple characterizations in terms of prime implicates. Furthermore, we demon strated tight connections between our work and that of Darwiche and Pearl on the one hand and Lin and Reiter on the other. While all three approaches evolved inde pendently with different motivations in mind, this pa per suggests that there is common ground among them. However, more work is needed to map out their exact relationships.
In future work, our investigations of logical relevance should be extended to the first-order case, which would require a first-order version of the logic of only-knowing about. This would allow an even better comparison with LR's work, which is already first-order. Judging from LR's experience, though, there may well be nasty sur prises along the way. For example, the result of for getting a predicate the LR way is not always first-order representable.
Acknowledgements
I would like to thank Adna.n Da.rwiche, Adam Grove, Fa.ngzhen Lin, a.nd Ra.y Reiter for discussions, which helped clarify many ideas presented in this paper. I a.m also grate ful to the anonymous referees, whose suggestions helped to improve the presentation of the paper.
@inproceedings{ijcai1995p111,
title = {A Logical Account of Relevance},
author = {Lakemeyer, Gerhard},
booktitle = {Proceedings of the Fourteenth International Joint Conference on
Artificial Intelligence, {IJCAI-95}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Chris S. Mellish},
pages = {853--860},
year = {1995},
note = {Knowledge Representation},
url = {https://ijcai.org/proceedings/1995/111},
}
TY - CPAPER TI - A Logical Account of Relevance AU - Lakemeyer, Gerhard T2 - Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, IJCAI-95 PB - International Joint Conferences on Artificial Intelligence PY - 1995 SP - 853 EP - 860 UR - https://ijcai.org/proceedings/1995/111 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: