Towards a Logic of Dilation

Abstract

We investigate the notion of dilation of a propositional theory based on neighbourhoods in a generalized approximation space. We take both a semantic and a syntactic approach in order to define a suitable notion of theory dilation in the context of approximate reasoning on the one hand, and a generalized notion of forgetting in propositional logic on the other hand. We place our work in the context of existing theories of approximation spaces and forgetting, and show that neighbourhoods obtained by combining collective and selective dilation provide a suitable semantic framework within which to reason computationally with uncertainty in a classical setting.

Keywords

• dilation
• indiscernibility
• rough sets
• forgetting

1 Introduction

The formalization of resemblance between objects (or sets of objects) in rough set theory [ 38, 40, 41 ] is based on the notion of an approximation space, defined by a partition on, or covering of, object attributes. Knowledge about objects is granular, with the partition of equivalence classes or covering of neighbourhoods providing the only discerning measure between objects and determining the granularity of object descriptions.

A related problem is that of information approximation in formal logic. Given a knowledge base K, we ask when a sentence follows from K, subject to some degree of tolerance on a given subsignature S. This yields a parameterized supra-classical consequence relation. On the one hand, the (atomic features described by) elements of S may be considered collectively irrelevant. This case has been studied in depth in various guises, such as forgetting [ 33 ] and rough set theory [ 40 ]. On the other hand, each element of S may be deemed individually irrelevant. This case has also been studied in rough set data analysis [ 53 ]. Variation between these two extremes gives rise to an increasingly refined granularity of neighbourhoods, applicable to a range of problems in knowledge representation, approximate pattern matching and information retrieval, yet remaining discrete and qualitative in nature.

In this paper we first present a detailed account of selective propositional theory dilation and its syntactic counterpart of selective forgetting. We then generalize and internalize the notion of dilation, which gives rise to a logic of theory dilation. Semantically, our approach is based on neighbourhoods in a generalized approximation space; computationally, it is based on a generalization of the forgetting operator allowing for both collective and selective dilation.

Similarity and tolerance relations have been studied extensively in knowledge representation, notably in knowledge base merging [ 3 ], where they are used as measures to assist in dealing with inconsistencies [ 28, 43 ], in approximate reasoning about indiscernible information [ 42 ], and as an alternative to nonmonotonic reasoning [ 16, 17, 30 ]. More generally, they have been studied in the context of vagueness or incompleteness in information theory [ 34, 41, 48 ]. Fuzzy rough information theory has also been studied extensively in this context [ 45, 49 ]. (Pawlak and Skowron [ 41 ] give a broad overview of rough set theory and applications, including an extensive list of references.)

Although we only consider the propositional case in the present paper, our aim is to extend the work to more expressive knowledge representation formalisms such as modal logics [ 13 ], as well as description logics [ 1 ] and fragments thereof, by building upon existing modal perspectives on generalized rough sets [ 32, 50 ].

The remainder of the present text is structured as follows. In Section 2 we set up the notation used in the paper, and give some background on rough set theory [ 40, 41 ] and forgetting [ 33 ]. We then show how selective indiscernibility can be defined semantically (Section 3), and syntactically (Section 4). This provides us with the handle needed to define a logic to express dilation at the object level, which we present in Section 5. We then present an outline of the generalization of our work to the infinite case (Section 6), and conclude with a discussion and directions for future investigation. 2 2.1

Background

Formal Preliminaries

In what follows, we assume a classical propositional language L built up from at most denumerably many variables (or atoms) P, the special constants ? and >, and the usual connectives. We shall use p; q; : : : (possibly with subscripts) as meta-variables for the atomic propositions, and ; ; : : : to denote the sentences of our language. Given 2 L, atm( ) denotes the set of propositional variables occurring in . A literal is an atom or the negation of an atom and is denoted by `. Given 2 L, lit( ) denotes the set of literals occurring in . A term (or diagrammatic sentence) is a conjunction of literals and is denoted by . A term 0 is a subterm of if lit( 0) lit( ).

We denote propositional valuations (or interpretations, or worlds) by u; v; : : : : P ! f0; 1g, with 0 denoting falsity and 1 truth. We shall sometimes represent valuations as sequences of 0s and 1s, and with the obvious implicit ordering of atoms. Thus, for the logic generated from p and q, the valuation in which p is true and q is false will be represented as 10. For a given 2 L, Mod( ) := fv j v g denotes the set of all models of , where v denotes the standard classical satisfaction of by v. We say that is valid (denoted j= ) if v for every valuation v.

A theory is a (possibly infinite) set of sentences T L. A knowledge base K is a finite theory. Our primary focus in this paper is on knowledge bases, although some of the definitions and results are also applicable to infinite theories (cf. Section 6). We make the restriction to knowledge bases explicit in all cases. The set of variables occurring in T is denoted atm(T ). T entails , written T j= , if and only if Mod(T ) Mod( ). Theories T and T 0 are logically equivalent, written T T 0, if and only if Mod(T ) = Mod(T 0).

2.2 Indiscernibility

The basic building block of rough set theory is the notion of an approximation space of the form hU ; i, where U is a set of objects and an equivalence relation on U . The intuition is that elements of U can only be distinguished up to their respective equivalence classes, while objects from the same equivalence class are indistinguishable.

Relaxation of the symmetry and transitivity conditions on has been studied in a number of different contexts, amongst which is the study of tolerance relations, which may fail transitivity [ 36, 42, 44 ]. Our building blocks are now tolerance spaces of the form hU ; i, where U is a set and is a reflexive and symmetric tolerance relation on U . As before, the intuition is that elements of U can only be differentiated if they are not -related to each other. The set (x) := fy j (x; y) 2 g is referred to as the neighbourhood of x [ 48 ].

With each tolerance space hU ; i we associate two operators: If X U , then X := fx 2 U j (x) \ X 6= ;g is the dilation of X, and its erosion is X := fx 2 U j (x) Xg. If is also transitive, the dilation and erosion operators coincide with the upper and lower approximation operators of an approximation space.

From now on, let U denote the set of all propositional valuations. It then immediately follows that, for any S P and

S := f(u; v) j u hU ; S i is an approximation space.

Not every tolerance (or approximation) space defines some theory T . In Section 3 we describe a class of tolerance spaces that do arise syntactically from some notion of indiscernibility amongst atoms. We next present some background on an elegant way to capture indiscernibility syntactically. Lin and Reiter [ 33 ] introduced the notion of forgetting a set of predicates in a firstorder theory in the context of cognitive robotics. We present a propositional version of forgetting here, which has since been studied extensively, especially in the context of modal logics [ 15, 51 ] and description logics [ 47 ]. Intuitively, the result of forgetting a set of atoms S should be weaker than the original knowledge base, but still entail the same set of sentences that are irrelevant to the signature S. As pointed out by Lin and Reiter, the notions of forgetting, irrelevance, and equivalence of interpretations are strongly related.

Definition 1. Let K be a knowledge base and S P. Let hU ; S i be the approxima

tion space with S := f(u; v) j u p if and only if v p; for all p 2 P n Sg. A knowledge base K0 is a result of (conjunctively) forgetting about S in K if and only if Hence the K0-models are all the worlds that are indistinguishable from some K-model with respect to S. Theorem 1 (Lin & Reiter [ 33 ]). The result of forgetting always exists and is unique modulo logical equivalence.

This result allows us to write ForgetS (K) for the semantically unique result of forgetting all the atoms in S in the knowledge base K. If K is a singleton set, say K = f g, we write ForgetS ( ) as shorthand for ForgetS (f g), some set of sentences that has the intended set of models.

Definition 2. Let T L and S P. S is (collectively) irrelevant to T if and only if there exists a theory T 0, logically equivalent to T , such that atm(T 0) \ S = ;.

Theorem 2 (Lin & Reiter [ 33 ]). Let K be a knowledge base and S

P. Then

ForgetS (K) f j K j=

and S is irrelevant to g:

A closely related notion to irrelevance is that of essential atoms [ 39 ]. We say that an atom p is essential to a theory T if and only if p 2 atm(T 0) for every T 0 such that T T 0. For instance, p is essential to T = f:p; :p _ qg. Given T , atm!(T ) denotes the set of essential atoms of T . (If T is not contingent, i.e., T is tautological or contradictory, then atm!(T ) = ;.)

Given a theory T , let T ! := f j T j= and atm( ) atm!(T )g: Clearly, atm(T !) = atm!(T !). Moreover, for every 2 L such that T , atm!(T ) = atm!( ) and T ! = f g!.

Theorem 3 (Least Atom-Set Theorem [ 39 ]). Let T such that T f g, atm(T !) atm( ).

L. Then T

T !, and for every A proof of this theorem is given by Makinson [ 35 ]. Essentially, it establishes that, for every theory T , there is a unique least set of elementary atoms such that T may be expressed equivalently using only atoms from that set. Hence, T T !.

In general, theories may be infinite, and the semantic characterization of forgetting of Definition 1 may therefore not be applicable. (See Section 6 for the infinite case.) If T is finite, there are only finitely many atoms essential to T , and only these atoms affect the result of forgetting S in T . 3

Selective Indiscernibility

We have seen that any set of atoms naturally yields an indiscernibility relation on valuations which is an equivalence relation. By weakening the transitivity condition, we now replace the equivalence relation with a range of increasingly fine-grained neighbourhood relations.

Definition 3. Let be a reflexive and symmetric binary relation on U , and let 0 be the identity relation on U . For n 1, the n-transitive closure of is the smallest relation n such that (i) n, and (ii) if (x0; x1); (x1; x2); : : : ; (xn 1; xn) 2 , then (x0; xn) 2 Equivalently, n := Sf j and j j = ng, where is the transitive closure of . From a morphological perspective [ 4 ], n is a structuring element, which can also be defined as a neighbourhood function n : U ! 2U based on the Manhattan distance measure, with n(x) = fy j (x; y) 2 ng the image of x under the relation n.

The n-transitive closure of a reflexive and symmetric binary relation provides a mechanism to describe neighbourhood-based rough sets whose upper and lower bounds are determined by a tolerance relation that exhibits only a limited degree of transitivity. As we shall see in Section 4, it also provides a semantic characterization for an operation akin to forgetting.

We next show how a theory and a set of atoms give rise to a range of tolerance spaces. First, we consider all functions CS picking out n elements from a given set S : CDSne,fiwnihteiorenC4Sn. LetSSand jPCS,nCjS= :nf. 0; : : : ; jS jg Lemma 1. Let S

P and 0 n jS j. For this fixed S and n, let

! 2S is a function such that CS (n) 7! n :=

[ f(u; v) j u CSn S p if and only if v

n : p; for all p 2 P n CS g Then hU ; and for n ni is a tolerance space. Moreover, if n = 0, 1, n is the n-transitive closure of 0 is the identity relation on U , := f(u; v) j for some q 2 S ; u

Example 1. Let P = fp; q; r; sg and let S = fp; q; rg. Then CS0 = ;, CS1 is one of the singleton sets fpg, fqg or frg, CS2 is one of the sets fp; qg, fp; rg or fq; rg, and vCaS3lu=atiofnps; qth;artga. gre0e iesvethryewidheenretiteyxcreeplattioonnaot nmUos,t on1eiselethmeesnettooffSa,ll t2hoissethpeasirest ooff all those pairs of valuations that agree everywhere except on at most two elements of S , and 3 is the set of all those pairs of valuations that agree on the proposition s. Note that 0 and 3 are equivalence relations, but that 1 and 2 are not. 4

Selective Forgetting

Forgetting, as traditionally studied in the literature, is conjunctive, in the sense that all the elements of a given set of atoms are forgotten, or deemed irrelevant. Syntactically, forgetting S from K yields a knowledge base in which none of the atoms from S occur. Semantically, forgetting S yields an approximation space with indiscernibility relation S as outlined in Section 2.2.

We now define the more general problem of forgetting any n atoms from S in K, and show that this describes the syntactic counterpart of tolerance spaces in the same way as standard forgetting is the syntactic counterpart of approximation spaces. The term ‘forgetting’ is not really appropriate here, since our aim is not to forget atoms but rather to dilate theories semantically, but we retain it because of the computational link with forgetting that we shall establish.

Definition 5. Let K be a knowledge base, S

tolerance space with n =

[ f(u; v) j u CSn S

A knowledge base K0 is a result of selective forgetting at most n atoms from S in K iff Mod(K0) = fw j Mod(K) \

We are now ready to state the most important result of this section.

Theorem 4. The result of selective forgetting always exists and is unique modulo logical equivalence.

Proof. We know that, for a fixed S and 0 n jSj, Mod(ForgetCSn (K)) = fw j Mod(K) \ CSn (w) 6= ;g from Definition 1. On the lefthand side of this equality, letting CSn range over all possible choices from S, we obtain WCSn S V ForgetCSn (K) syntactically, while on the righthand side, we obtain fw j Mod(K) \ n(w) 6= ;g for some CSn S semantically. Therefore, lent (Kw0):6== ;fgW. CSn S V ForgetCSn (K)g. Then it follows that Mod(K0) = fw j Mod(K) \ tu

This result allows us to write SForgetSn (K) for the (semantically unique) result of selective forgetting any n atoms from S in K. It then follows from Lemma 1 that SForgetn (K) arises from a tolerance space hU ; ni in which n has a particular struc

S ture, namely, it is the n-transitive closure of the tolerance relation associated with SForget1S (K).

Corollary 2. Let hU ; ni be the tolerance space with Mod(SForgetSn (K)) = Mod(K). n as in Definition 5. Then

The semantic intuition of selective forgetting is that Mod(K) represents the weakest knowledge base resembling K, with indiscernibility determined by a given set of atoms S and degree of transitivity n.

As in the case of forgetting, we obtain a syntactic characterization of selective forgetting when K is written as a single sentence : Corollary 3. Let 2 L, S P and 0 n jSj. SForgetSn ( ) can be characterized as the singleton set SForgetSn ( ) := nWCSn S V ForgetCSn ( ) . o

With this result, together with Theorem 5 below, we obtain a method to compute selective forgetting via disjunctive normal form (DNF). Although computing the DNF of a sentence is itself computationally expensive, once preprocessing has been done, it provides an attractive alternative to computing forgetting directly.

Definition 6. Let

be a term and let S

Let [p=?] and [p=>] denote the sentences obtained from atom p with ? and >, respectively. by replacing the

Lemma 2 (Lang et al. [31]). Let

[p=>] _ [p=?]: be a consistent term and let p 2 P. Then fpg

Let DNF( ) denote (some) DNF representation of as a set of terms. The proof of the theorem below then follows from iterative applications of Lemma 2. Theorem 5 (Lang et al. [ 31 ]). ForgetS ( ) nW 2DNF( ) S

Corollary 4. Let

2 L, S

P and 0 n

jSj. Then SForgetn ( )

S nWCSn S W

o 2DNF( ) CSn :

If has been pre-compiled as a disjunction of its prime implicants [ 37 ], the size of SForgetn ( ) is at most jSjn times the size of . Some post-processing may be required

S to remove redundant clauses to rewrite the result as a disjunction of prime implicants, but it is not hard to see that this does not affect the overall complexity of computation.

As an example, we consider the special case where n = 1. Given a knowledge base K and a set of atoms S, our aim is to define K0, first semantically and then syntactically, obtained from K by non-deterministically disregarding one atom from S. The semantic characterization of K0 follows directly from Definition 5. The tolerance space induced by S is hU ; i, with the set of all pairs of valuations that differ on at most one atom from S. The upper approximation of Mod(K) is Mod(K0):

Mod(K) = Mod(K0) = [f (w) j (w) \ Mod(K) 6= ;g: Finally, if K = f g, then K0 may be characterized syntactically as follows: SForget1 ( ) := nW

S p2S

o [p=?] _ [p=>] :

We illustrate these relationships in a simple concrete example: Example 2. Let P = K = fp; q; r; sg and S = fp; q; rg. ForgetS (K) = SForget3S (K) = fsg, SForget2S (K) = fp _ q _ r; sg, SForget1S (K) = f(p ^ q) _ (p ^ r) _ (q ^ r); sg, and SForget0 (K) = fp; q; r; sg. Clearly, selective forgetting does not eliminate the atoms

S that are forgotten syntactically from a knowledge base. Its effect is best thought of semantically: In our example, Mod(K) = f1111g. To obtain Mod(SForget1 (K)), add all S worlds that differ from 1111 in at most one atom, which must be from S. This gives Mod(SForget1 (K)) = f1111; 1101; 1011; 0111g. Similarly, to get Mod(SForget2 (K)),

S S add all worlds that differ from 1111 in at most two atoms, which must be from S, and to obtain Mod(ForgetS (K)), add all worlds that differ from 1111 only on S.

A Neighbourhood Semantics for a Logic of Dilation

Both standard forgetting and selective forgetting are operators at the meta-level in the sense that we cannot refer to or explicitly use them in the logical language. In this section we turn our attention to internalizing the notion of dilation in the object level, which gives rise to a logic within which one can explicitly express and reason about dilation. (Our motivation is similar to that of internalizing belief revision [ 21 ] in modal logic [ 46 ] or the notions of typicality [ 5, 6, 20 ] and relative normality [ 2, 7, 9, 11, 12 ] in nonmonotonic reasoning.)

We have seen in the previous sections that dilation is carried out relative to a given set of atoms and that these can be considered either collectively or selectively. Hence, operators internalizing the notion of dilation should be parameterized by a given signature and in this way inform the operation. Moreover, they should also allow for more complex operations involving both collective and selective dilation, as in e.g. “dilate a theory by p and q or by r and s”.

We first define the grammar of the dilation operators. Below, " denotes the empty string and p 2 P. With and + we denote, respectively, collective and selective dilation as motivated above.

o ::= " j p j (o o) j (o + o)

Assuming P = fp; q; rg, examples of dilation operators generated by the above grammar are (p (q + p)) and ((p p) + (q (p + r))). (For the sake of readability, in what follows we shall assume that has precedence over + and therefore we shall omit some unnecessary parentheses. We shall also omit the outermost parentheses in operators.) We shall use o; %; ; : : : to denote operators generated by the grammar. With O we denote the operator language generated as above. Given p 2 P and o 2 O, with p 2 o we denote the fact that p appears in (is a symbol of) the operator o.

An atomic dilation operator in O is either an atom p 2 P or it is ". A primitive collective dilation operator is any operator of the form %1 : : : %k, k 1, where each %i is an atomic dilation operator. A dilation operator is in dilation normal form if it has the form 1 + : : : + n, n 1, where each i is a primitive collective dilation operator.

Given the set of all dilation operators O as defined above, we can extend our underlying propositional language in the following way: ::= p j : j ^ j o All the other Boolean truth-functional connectives (_, !, $, . . . ) are defined in terms of : and ^ in the usual way. We use > as an abbreviation for p _ :p and ? as an abbreviation for p ^ :p, for some p 2 P. With LO we denote the set of all sentences of our extended language.

A sentence of the form o is read “the dilation of by o”. The semantics of sentences of LO is in terms of neighbourhoods, which we define more precisely below. Definition 7. The neighbourhood space of LO is a mapping : O ! 2U U s.t.: – – " = f(v; v) j v 2 U g; p = f(v; w) j v(q) = w(q) for all q 2 P n fpgg; – – – – % %+ = ( % [ = It is not hard to see that distributivity of over + and of + over do not hold in general. However, we have the following additional properties:

Lemma 3 (Normal Form).

– For every %; 2 O, there exists some primitive collective dilation operator o such that % = o; – For every % 2 O there exists 2 O in dilation normal form such that % = .

Armed with the notion of neighbourhood functions we can give a precise and elegant semantics to the sentences of LO: Definition 8 (Satisfaction). Given w 2 U : – w – w – w – w p if and only if w(p) = 1; : if and only if w 6 ; ^ if and only if w and w o if and only if, for some v 2 U , v ; and w 2 o(v).

Given 2 LO, we say that is valid if Mod( ) = U and we denote it j=o . The next lemma shows that our neighbourhood semantics preserves the validity of all propositional tautologies.

Lemma 4. Let

2 L (i.e., is a propositional sentence). Then j= iff j=o .

From the perspective of knowledge representation and reasoning, it becomes important to address the question of what it means for a sentence (or a theory T ) to entail a sentence . For now we suffice with a standard (Tarskian) definition of logical consequence (at the end of the present section we shall define an alternative notion of entailment for LO): given ; 2 LO, entails (denoted j=LO ) if and only if Mod( ) Mod( ). (This notion of entailment can be extended to theories in the usual way.) We shall use LO as an abbreviation for j=LO and j=LO . It then follows that, for every %; 2 O, ( %) LO % .

The following result generalizes Theorem 4, and its proof is similar:

Theorem 6. Let

n 1. Then o 2 L and o 2 O be in dilation normal form, with o = LO W1 i n Forgetfpjp2 ig( ). 1 + : : : + n,

Theorem 6 establishes that reasoning with LO can be reduced to reasoning in classical propositional logic together with the standard forgetting operator. From this it then becomes easy to analyze the complexity of reasoning within LO.

Conversely, both standard and selective forgetting can be captured in the extended lapnqgru,aSgFeorLgOet1Sp(res)entLedO abpo+vqe+.rFoarndexSaFmoprglee,t2Sle(t S) =LfOp; qp;qr+gp.r+Tqhre.nHFoowrgeevteSr,( th)e nLewO language allows us to express dilations directly in the language, and it allows us to express more — the sentence p+qr can, for example, not be expressed using the metalanguage of selective forgetting.

Thus far, we have only considered the neighbourhoods defined in terms of collective and selective dilation. The grammar can in principle be extended to allow for the construction of erosion, opening and closing operators, to name a few [ 4 ].

We shall now turn our attention to an alternative notion of entailment for the extended language LO. We start by observing that the dilation operation is a uniform weakening operator in the sense of Britz et al. [ 10 ]. That is, given ; 2 L and o 2 O, the following properties are satisfied: – – If j=LO j=LO o , then o j=LO o (Weakening) (Uniformity)

It then follows that, given o 2 O, the operator CnLO : LO ! 2LO , defined by CnLO ( ) 7! f 2 LO j j=LO og, is a parameterized supra-classical Tarskian consequence operator. We extend CnLO to a consequence operation on knowledge bases in the standard way.

Given o 2 O, CnLO defines a tolerant entailment relation j , allowing pairs K j for which K 6j= , and applicable in approximate reasoning where additional consequences that do not follow classically, but which resemble some classical consequences, are sought. (Note that j is a monotonic consequence relation.) Given a knowledge base K and 2 LO, entailment checking of K j can then be reduced to standard forgetting, courtesy of Theorem 6 above. 6

Weak Selective Forgetting

We now turn to the syntactic characterization of weak selective forgetting in infinite theories. Of course, the finite characterization of selective forgetting then collapses. Nor does syntactic irrelevance suffice as vehicle for its representation, as in the case of forgetting [ 33 ].

The following alternative syntactic characterization of forgetting suggests a possible course of action. It holds for finite as well as infinite theories, and can therefore be used to obtain a syntactic representation of weak forgetting as proposed by Zhang and Zhou [ 52 ]: Lemma 5. Let T L and p 2 P. Let T1 = f j T j= T2 = f [p=?] _ [p=>] j ; 2 T g: Then T1 T2.

Proof. Routine, using compactness to deal with the infinite case. and p is irrelevant to g and

tu Definition 9. Let T follows:

L, and S

P be a finite set of atoms. Define TS recursively as

(i) T; = T ; (ii) TS0[fpg = f [p=?] _ [p=>] j ; 2 TS0 g, for S0 S.

Theorem 7. Let T L, S P a finite set of atoms, and TS as in Definition 9. If T is

finite, then TS ForgetS (T ). If T is infinite, then

TS f j T j= Proof. From Lemma 5 and Theorem 2. tu

The result above warrants us to call TS the result of weakly forgetting S in T , or WForgetS (T ) in the terminology of Zhang and Zhou [ 52 ]. We use this to define weak selective forgetting as a generalization of weak forgetting in the power set algebra associated with the propositional language L. Brink [ 8 ] gives a general account of power structures in the context of logic.

Definition 10. Let f : An ! A be an n-ary operation on the set A and let X1; : : : ; Xn A. Then f + : (2A)n ! 2A is the power operation of f on 2A defined by: f +(X1; : : : ; Xn) := fy 2 A j (9x1 2 X1) : : : (9xn 2 Xn)[f (x1; : : : ; xn) = y]g:

Definition 11. Let T L, S P a finite set of atoms and 0

selective forgetting of n atoms from S in T is the theory n jSj. The weak

WSForgetSn (T ) := WC+Sn S WForgetCSn (T ); where W+ denotes the power operation of _.

In other words, if T1; : : : ; Tk is an enumeration of the theories WForgetCSn (T ) for all

W values of CSn, then WSForgetn (T ) = f 1 j k j j for each j; j 2 Tj g.

It is not difficult to see thSat, for n as in Definition 5, fw j Mod(T ) \ n(w) 6= ;g

Mod(WSForgetSn (T )):

Finally, our definition is further supported by the fact that, for knowledge bases, selective forgetting and weak selective forgetting produce the same results. 7

Concluding Remarks

The main contributions of the present paper can be summarized as follows: (i) defining a notion of selective indiscernibility, (ii) showing how to compute it via selective forgetting, and (iii) presenting a logic in which to express and reason with dilation at the object level and for which the reasoning problem can be reduced to entailment in classical propositional logic plus standard forgetting.

Syntactically, selective forgetting is measured in terms of the number and selection of atoms on which disagreement is allowed. It therefore provides a range of increasingly tolerant upper bounds to a given theory, which can be applied to approximate reasoning and nonmonotonic reasoning. To witness, we can define a belief contraction operator based on the following observation:

Lemma 6. Let K be a knowledge base. For every non-tautological

atm!( ), then there exists an n such that SForgetSn (K) 6j= . 2 L, if ; 6= S Hence, given appropriate S and n, selective forgetting of atoms in K delivers a weaker knowledge base not entailing sentence . The results in Section 5 together with Lemma 6 suggest we can also bring such a contraction operator into the object language.

The present paper also opens up a number of avenues for future research: An investigation of the dual case of selective remembering, and its relationship with its semantic counterpart of lower approximations in a tolerance space, as well as the corresponding operators of erosion, remain to be done. Likewise, lifting the propositional results obtained here to knowledge forgetting in modal logics [ 15 ] and to concept and role forgetting in description logics [ 47 ] are worth investigating.

Another avenue for future exploration is the definition of different alternative notions of entailment for LO and their relationship with various forms of reasoning.

Finally, from a knowledge representation and reasoning perspective, when one deals with knowledge bases, issues related to modularization [ 14, 19, 22–24 ], knowledge base revision and update [ 21, 25, 26 ] as well as knowledge base maintenance and versioning [ 18, 27, 29 ] show up. These are tasks that also make sense in the setting studied in this paper. When moving beyond the classical case, though, such tasks have to be reassessed and specific methods and techniques redesigned. This constitutes a thread worthy of exploration.

Acknowledgements

The work of Ivan Varzinczak was partially supported by the Conselho Nacional de Desenvolvimento Cient´ıfico e Tecnolo´gico (CNPq) under Grant 302002/2014-6. This work was partially funded by the National Research Foundation (NRF) under Grant numbers 81225 and 85482.

References

1. Baader , F. , Calvanese , D. , McGuinness , D. , Nardi , D. , Patel-Schneider , P . (eds.): The Description Logic Handbook . Cambridge University Press, 2 edn . ( 2007 )

2. Baltag , A. , Smets , S.: A qualitative theory of dynamic interactive belief revision . In: Bonanno, G., van der Hoek, W., Wooldridge , M. (eds.) Logic and the Foundations of Game and Decision Theory (LOFT7) . pp. 13 - 60 . No. 3 in Texts in Logic and Games, Amsterdam University Press ( 2008 )

3. Bloch , I. , Hunter , A. : Fusion: General concepts and characteristics . International Journal of Intelligent Systems 16 ( 10 ), 1107 - 1134 ( 2001 )

4. Bloch , I. , Lang , J.: Towards mathematical morpho-logics . In: Bouchon-Meunier , B. , Gutie´ rrez-R´ıos, J., Magdalena , L. , Yager , R . (eds.) Technologies for Constructing Intelligent Systems , Studies in Fuzziness and Soft Computing , vol. 90 , pp. 367 - 380 . Physica-Verlag HD ( 2002 )

5. Booth , R., Meyer, T., Varzinczak , I. : PTL: A propositional typicality logic . In: Farin˜as del Cerro , L. , Herzig , A. , Mengin , J . (eds.) Proceedings of the 13th European Conference on Logics in Artificial Intelligence (JELIA) . pp. 107 - 119 . No. 7519 in LNCS , Springer ( 2012 )

6. Booth , R., Meyer, T., Varzinczak , I.: A propositional typicality logic for extending rational consequence . In: Ferme´, E. , Gabbay , D. , Simari , G . (eds.) Trends in Belief Revision and Argumentation Dynamics , Studies in Logic - Logic and Cognitive Systems , vol. 48 , pp. 123 - 154 . King's College Publications ( 2013 )

7. Boutilier , C. : Conditional logics of normality: A modal approach . Artificial Intelligence 68 ( 1 ), 87 - 154 ( 1994 )

8. Brink , C. : Power structures . Algebra Universalis 30 , 177 - 216 ( 1993 )

9. Britz , K. , Casini , G., Meyer, T., Varzinczak , I. : Preferential role restrictions . In: Proceedings of the 26th International Workshop on Description Logics . pp. 93 - 106 ( 2013 )

10. Britz , K. , Heidema , J. , Varzinczak , I. : Constrained consequence . Logica Universalis 5 ( 2 ), 327 - 350 ( 2011 )

11. Britz , K. , Varzinczak , I. : Defeasible modes of inference: A preferential perspective . In: Proceedings of the 14th International Workshop on Nonmonotonic Reasoning (NMR) ( 2012 )

12. Britz , K. , Varzinczak , I. : Defeasible modalities . In: Proceedings of the 14th Conference on Theoretical Aspects of Rationality and Knowledge (TARK) . pp. 49 - 60 ( 2013 )

13. Chellas , B. : Modal logic: An introduction . Cambridge University Press ( 1980 )

14. Cuenca Grau , B. , Parsia , B. , Sirin , E. , Kalyanpur , A. : Modularity and web ontologies . In: Doherty, P. , Mylopoulos , J. , Welty , C. (eds.) Proceedings of the 10th International Conference on Principles of Knowledge Representation and Reasoning (KR) . pp. 198 - 208 . Morgan Kaufmann ( 2006 )

15. van Ditmarsch, H. , Herzig , A. , Lang , J. , Marquis , P. : Introspective forgetting . Synthese 169 ( 2 ), 405 - 423 ( 2009 )

16. Dubois , D. , Prade , H.: Similarity versus preference in fuzzy set-based logics . In: Orlowska, E . (ed.) Modelling Incomplete Information: Rough Set Analysis , pp. 441 - 461 . PhysicaVerlag ( 1998 )

17. Dubois , D. , Prade , H. , Esteva , F. , Garcia , P. , Godo , L. : A logical approach to interpolation based on similarity relations . International Journal of Approximate Reasoning 17 ( 1 ), 1 - 36 ( 1997 )

18. Franconi , E., Meyer, T., Varzinczak , I. : Semantic diff as the basis for knowledge base versioning . In: Proceedings of the 13th International Workshop on Nonmonotonic Reasoning (NMR) ( 2010 )

19. Garson , J.: Modularity and relevant logic . Notre Dame Journal of Formal Logic 30 ( 2 ), 207 - 223 ( 1989 )

20. Giordano , L. , Olivetti , N. , Gliozzi , V. , Pozzato , G.: A non-monotonic description logic for reasoning about typicality . Artificial Intelligence 195 , 165202 ( 2012 )

21. Hansson , S.: A Textbook of Belief Dynamics: Theory Change and Database Updating . Kluwer Academic Publishers ( 1999 )

22. Herzig , A. , Varzinczak , I. : Domain descriptions should be modular . In: Lo´pez de Ma´ntaras, R., Saitta , L . (eds.) Proceedings of the 16th European Conference on Artificial Intelligence (ECAI) . pp. 348 - 352 . IOS Press ( 2004 )

23. Herzig , A. , Varzinczak , I. : On the modularity of theories . In: Schmidt, R. , Pratt-Hartmann , I. , Reynolds , M. , Wansing , H. (eds.) Advances in Modal Logic. pp. 93 - 109 . 5, King's College Publications ( 2005 )

24. Herzig , A. , Varzinczak , I.: A modularity approach for a fragment of ALC . In: Fisher, M. , Hoek , W. , Konev , B. , Lisitsa , A . (eds.) Proceedings of the 10th European Conference on Logics in Artificial Intelligence (JELIA) . pp. 216 - 228 . No. 4160 in LNAI , Springer-Verlag ( 2006 )

25. Katsuno , H. , Mendelzon , A. : Propositional knowledge base revision and minimal change . Artificial Intelligence 3 ( 52 ), 263 - 294 ( 1991 )

26. Katsuno , H. , Mendelzon , A. : On the difference between updating a knowledge base and revising it . In: Ga¨rdenfors, P. (ed.) Belief revision , pp. 183 - 203 . Cambridge University Press ( 1992 )

27. Konev , B. , Walther , D. , Wolter , F. : The logical difference problem for description logic terminologies . In: Armando, A. , Baumgartner , P. , Dowek , G . (eds.) Proceedings of the 4th International Joint Conference on Automated Reasoning (IJCAR) . pp. 259 - 274 . No. 5195 in LNAI , Springer-Verlag ( 2008 )

28. Konieczny , S. , Lang , J. , Marquis , P.: DA2 merging operators . Artificial Intelligence 157 , 49 - 79 ( 2004 )

29. Kontchakov , R. , Wolter , F. , Zakharyaschev , M. : Can you tell the difference between DL-Lite ontologies ? In: Lang, J. , Brewka , G . (eds.) Proceedings of the 11th International Conference on Principles of Knowledge Representation and Reasoning (KR) . pp. 285 - 295 . AAAI Press/MIT Press ( 2008 )

30. Kraus , S. , Lehmann , D. , Magidor , M. : Nonmonotonic reasoning, preferential models and cumulative logics . Artificial Intelligence 44 , 167 - 207 ( 1990 )

31. Lang , J. , Liberatore , P. , Marquis , P. : Propositional independence: Formula-variable independence and forgetting . Journal of Artificial Intelligence Research (JAIR) 18 , 391 - 443 ( 2003 )

32. Liau , C.J.: An overview of rough set semantics for modal and quantifier logics . International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 8(1) , 93 - 118 ( 2000 )

33. Lin , F. , Reiter , R.: Forget it! In : Proceedings of the AAAI Fall Symposium on Relevance . pp. 154 - 159 ( 1994 )

34. Lin , T. : Neighborhood systems: A qualitative theory for fuzzy and rough sets . Advances in Machine Intelligence and Soft Computing 4 , 132 - 155 ( 1997 )

35. Makinson , D. : Friendliness and sympathy in logic . In: Be´ziau, J.Y. (ed.) Logica Universalis , vol. 2 , pp. 195 - 224 . Springer-Verlag ( 2007 )

36. Marcus , A. : Tolerance rough sets, Cˇ ech topologies, learning processes . Bulletin of the Polish Academy of Sciences, Technical Sciences 42(3) , 471 - 487 ( 1994 )

37. Marquis , P. : Consequence finding algorithms . In: Gabbay, D. , Smets , P. (eds.) Handbook on Defeasible Reasoning and Uncertainty Management Systems , vol. 5 , chap . 2, pp. 41 - 145 . Kluwer ( 2000 )

38. Pagliani , P. , Chakraborty , M.: A Geometry of Approximation: Rough Set Theory Logic, Algebra and Topology of Conceptual Patterns, Trends in Logic , vol. 27 . Springer Publishing Company ( 2008 )

39. Parikh , R.: Beliefs, belief revision, and splitting languages . In: Moss, L . (ed.) Logic , Language and Computation, pp. 266 - 278 . No. 96 in CSLI Lecture Notes, CSLI Publications ( 1999 )

40. Pawlak , Z. : Rough sets: Theoretical Aspects of Reasoning About Data . Kluwer Academic Publishers ( 1991 )

41. Pawlak , Z. , Skowron , A. : Rudiments of rough sets . Information Sciences 177 , 3 - 27 ( 2007 )

42. Peters , J. , Wasilewski , P. : Tolerance spaces: Origins, theoretical aspects and applications . Information Sciences 195 , 211 - 225 ( 2012 )

43. Schockaert , S. , Prade , H.: Solving conflicts in information merging by a flexible interpretation of atomic propositions . Artificial Intelligence 175 , 1815 - 1855 ( 2011 )

44. Skowron , A. , Stepaniuk , J.: Tolerance approximation spaces . Fundamenta Informaticae 27 ( 2- 3 ), 245 - 253 ( 1996 )

45. Skowron , A., S´ winiarski, R., Synak , P. : Approximation spaces and information granulation . In: Peters, J. , Skowron , A . (eds.) Transactions on Rough Sets , vol. III, pp. 175 - 189 . SpringerVerlag ( 2005 )

46. van Ditmarsch, H., van der Hoek, W., Kooi , B. : Dynamic Epistemic Logic. Springer ( 2007 )

47. Wang , K. , Wang , Z. , Topor , R. , Pan , J. , Antoniou , G.: Concept and role forgetting in ontologies . In: Proceedings of the 8th International Semantic Web Conference (ISWC) . pp. 666 - 681 . No. 5823 in LNCS , Springer-Verlag ( 2009 )

48. Yao , Y. : Relational interpretations of neighborhood operators and rough set approximation operators . Information Sciences 111 ( 1-4 ), 239 - 259 ( 1998 )

49. Yao , Y. : Probabilistic approaches to rough sets . Expert Systems 20 , 287 - 297 ( 2003 )

50. Yao , Y. , Lin , T. : Generalization of rough sets using modal logics . Intelligent Automation and Soft Computing 2 , 103 - 120 ( 1996 )

51. Zhang , Y. , Zhou , Y. : Knowledge forgetting: Properties and applications . Artificial Intelligence 173 ( 16 - 17 ), 1525 - 1537 ( 2009 )

52. Zhang , Y. , Zhou , Y. : Forgetting revisited . In: Proceedings of the 12th International Conference on Principles of Knowledge Representation and Reasoning (KR) . pp. 602 - 604 . AAAI Press ( 2010 )

53. Zhao , Y. , Yao , Y. , Luo , F. : Data analysis based on discernibility and indiscernibility . Information Sciences 177 ( 22 ), 4959 - 4976 ( 2007 )