Innovations to Attribute Reduction of Covering Decision System Based on Conditional Information Entropy

Supposing that {π = A_i : i = 1, … m} be a set of covers of U, d is a decision attribute and U/d is a decision partition on U. If ∀ and ∃E_j ∈ U/d such that π_x ∈ d_j, then decision system S = (U, π, d) is called a consistent covering decision system, and recorded as H(d|π) = 0, i.e. otherwise, S = (U, π, d) is called an inconsistent covering decision system. (Appendix:H(d|π)=−1|U|∑x∈Ulog|[x]d∩πx|πx) \left({{\rm{Appendix}}:H(d|\pi) = - {1 \over {\left| U \right|}}\sum\limits_{x \in U} \log {{\left| {{{[x]}_d} \cap {\pi _x}} \right|} \over {{\pi _x}}}} \right)

The positive region of d relative to π is defined as POSπ(d)=∪X∈U/Dπ_(X) {POS}_\pi(d) = \mathop \cup \limits_{X \in U/D} \underline \pi (X) .

For ∀X ∈ U/d, if we believe every π¯X⇒X \bar \pi X \Rightarrow X to be the possible rule and every π − X ⇒ X to be a certain rule, then all the decision rules extracted from a consistent covering decision system are consistent.

Supposing that S = (U, π, d) be a consistent covering decision system and there exists A_i ∈ π if H(d|π − {A_i}) = 0, then A_i is called a superfluous relative to d in π; otherwise, A_i is known as a indispensable relative to d in π. For every B ⊆ π satisfying H(d|B) = 0, if every element in B is indispensable, i.e. for ∀A_i ∈ B,H(d|B − {A_i}) = 0 being not true, then B is called a reduction of π relative to d, in short known as relative reduction. The collection of all the indispensable elements in π is called the core of π relative to d, denoted as Core_d(π).

Suppose H(d|π) = 0, if and only if for every x, y ∈ U, if x ∈ π_y, then x ∈ [y]_d.

Since for every y ∈ U, H(d|π)=−1|U|∑y∈Ulog|[y]d∩πy||πy|=0 H(d|\pi) = - {1 \over {\left| U \right|}}\sum\limits_{y \in U} \log {{\left| {{{[y]}_d} \cap {\pi _y}} \right|} \over {\left| {{\pi _y}} \right|}} = 0 , such that π_y ⊆ [y]_D. If for every x, y ∈ U, x ∈ π_y, then x ∈ [y]_d. On the other hand, for every x, y ∈ U, if x ∈ π_y, we have x ∈ [y]_d, hence π_y ⊆ [y]_d. Therefore, for every y ∈ U, H(d|π) = 0.

Suppose H(d|π) = 0 if and only if POS_π (d) = U.

⇒ For every y ∈ POS_π (d), then π_y ⊆ [x]_d, therefore y ∈ [x]_d, and so we have [y]_d = [x]_d, i.e. π_y ∩ [y]_d ≠ ∅.

For every x ∈ π_y, then x ∈ [y]_d and by the Theorem 1, we get H(d|π) = 0.

⇐ Since POSπ(d)=∪X∈U/dπ_(X) {POS}_\pi(d) = \mathop \cup \limits_{X \in U/d} \underline \pi (X) , we have π(X) ⊆ X, hence ∪π(X) ⊆ ∪X = U, and so we get POS_π (d) ⊆ U. On the other hand, since POSπ(d)=∪X∈U/dπ_(X)=∪π_([x]d) {POS}_\pi(d) = \mathop \cup \limits_{X \in U/d} \underline \pi (X) = \cup \underline \pi ({[x]_d}) , for every y ∈ POS_π (d), then π_y ⊆ [x]_d. By Theorem 1, H(d|π) = 0 if and only if for every x, y ∈ U, x ∈ π_y, then x ∈ [y]_d; hence U ⊆ [y]_d; then by π_y ⊆ [x]_d and [y]_d ⊆ [x]_d, we have U ⊆ [x]_d; hence x ∈ POS_π (d) such that U ⊆ POS_π (d). So, the result is true.

Suppose H(d|π) = 0, B ⊆ π is a positive-region consistent set on S; then (U, B, d) is a consistent covering decision system.

Suppose H(d|π) = 0, B ⊆ π is a positive-region reduction on S; then B is a minimal set such that decision system (U, B, d) is a consistent covering decision system.

Suppose H(d|π) = 0, A_i ∈ π and Cov(π − {A_i}) = {B_x : x ∈ U}; then A_i is indispensable, i.e. H(d|π − {A_i}) = 0 is not true if and only if there exists x ∈ U such that B_x ⊆ [x]_D is not true.

If there exists x ∈ U such that B_x ⊆ [x]_D is not true, by x ∈ B_x, then for every y ∈ U such that B_x ⊆ [y]_D is not true. So H(d|π − {A_i}) = 0 is not true.

If H(d|π − {A_i}) = 0 is not true, then there exists, for ∀y ∈ U such that B_x ⊆ [y]_D is not true. Especially, B_x ⊆ [x]_D is also not true.

It should be indicated that B_x ⊆ [x]_D not being true means that (U, π − {A_i}, d) is an inconsistent decision system, i.e. H(d|π − {A_i}) ≠ 0, A_i is thus indispensable implies it is a key cover to ensure (U, π, d) is a consistent decision system, i.e. H(d|π) = 0.

Suppose H(d|π) = 0, A_i ∈ π, and Cov(π − {A_i}) = {B_x : x ∈ U}, then H({A_i}|π − {A_i}) > 0, i.e. A_i is absolutely indispensable.

In other words, H({A_i}|π − {A_i}) > 0 is not true if and only if A_i is called superfluous in B.

We assume that Cov(π − {A_i}) = {B_x : x ∈ U} and Cov({A_i}) = {A_ix : x ∈ U}, If A_i is called superfluous in B, for x ∈ U, B_x have equivalence values on A_i, i.e. for every B_x(x ∈ U) there is A_i(x ∈ U) such that B_x ⊆ A_ix, so H({Ai}|π−{Ai})=−1|U|∑x∈Ulog|Aix∩Px||Px|=0 H(\{{A_i}\} |\pi - \{{A_i}\}) = - {1 \over {\left| U \right|}}\sum\limits_{x \in U} \log {{\left| {{A_{ix}} \cap {P_x}} \right|} \over {\left| {{P_x}} \right|}} = 0 .

If H({A_i}|π − {A_i}) > 0 is not true, then H({Ai}|π−{Ai})=−1|U|∑x∈Ulog|Aix∩Bx||Bx| H(\{{A_i}\} |\pi - \{{A_i}\}) = - {1 \over {\left| U \right|}}\sum\limits_{x \in U} \log {{\left| {{A_{ix}} \cap {B_x}} \right|} \over {\left| {{B_x}} \right|}} , and for every x, i, 1|U|∑x∈Ulog|Aix∩Bx||Bx|≤0 {1 \over {\left| U \right|}}\sum\limits_{x \in U} \log {{\left| {{A_{ix}} \cap {B_x}} \right|} \over {\left| {{B_x}} \right|}} \le 0 and 1|U|>0 {1 \over {\left| U \right|}} > 0 , so ∑x∈Ulog|Aix∩Bx||Bx|≤0 \sum\limits_{x \in U} \log {{\left| {{A_{ix}} \cap {B_x}} \right|} \over {\left| {{B_x}} \right|}} \le 0 is true; if there exists a certain j such that 0<|Ajx∩Bx||Bx|<1 0 < {{\left| {{A_{jx}} \cap {B_x}} \right|} \over {\left| {{B_x}} \right|}} < 1 ; otherwise it implies H({Ai}|π−{Ai})=−1|U|∑x∈Ulog|Ajx∩Bx||Bx|>0 H(\{{A_i}\} |\pi - \{{A_i}\}) = - {1 \over {\left| U \right|}}\sum\limits_{x \in U} \log {{\left| {{A_{jx}} \cap {B_x}} \right|} \over {\left| {{B_x}} \right|}} > 0 , which is a contradiction. So for every x, i there is |Aix∩Bx||Bx|=1 {{\left| {{A_{ix}} \cap {B_x}} \right|} \over {\left| {{B_x}} \right|}} = 1 , i.e. P_x ⊆ A_ix, hence H({A_i}|π − {A_i}) > 0 such that H({A_i} π − {A_i}) > 0 is not true.

Suppose H(d|π) = 0, A_i ∈ π, then A_i is superfluous relative tod in π if and only if H(d|π − {A_i}) = H(d|π) = 0.

Assume that H(d|π) = 0, B ⊆ π is called a reduction of π relative tod if and only if

H(d|B) = H(d|π), and

Assume that H(d|π) = 0,A_i ∈ π,A_i is then indispensable, i.e. H(d|π − {A_i}) = 0 is not true if and only if there is at least a pair of x_i, x_j ∈ U satisfying f_d(π_xi) ≠ f_d(π_xj), and the factor which has the foremost relation to π transfers behind A_i and is removed from π.

⇒ We note that if Cov(π − {A_i}) = {B_x : x ∈ U}, if H(d|π − {A_i}) = 0 is not true, then there are x₀, y₀ ∈ U such that y₀ ∈ B_x0 and y₀ ∉ [x₀]_d, which implies B_y0 ⊆ B_x0 and π_x0 ⊄ π_y0,π_y0 ⊄ π_x0, respectively, and x₀, y₀ satisfying f_d(π_x0) ≠ f_d(π_y0), so the factor that has the foremost relation of x₀, y₀ with regard to π transfers behind A_i and is removed from π.

⇐ Suppose x₀, y₀ ∈ U satisfying f_d(π_xi) ≠ f_d(π_xj), which implies [x₀]_d ∩ [y₀]_d = ∅, and π_x0 ⊄ π_y0,π_y0 ⊄ π_x0, if their foremost relation x₀, y₀ with regard to π transfers behind A_i removing from π, which implies B_x0 ⊄ B_y0 or B_y0 ⊄ B_x0 is not effective. Thus if B_y0 ⊄ B_x0, then B_y0 ⊆ [y₀]_d is not effective, otherwise it points out x₀ ∈ [y₀]_d which is a contradiction; if B_x0 ⊇ B_y0, then B_x0 ⊆ [x₀]_d is not virtual; if B_x0 = B_y0 then B_y0 ⊆ [y₀]_d and B_x0 ⊆ [x₀]_d are not effective. Hence H(d|π − {A_i}) = 0 is not true.

Suppose H(d|π) = 0, B ⊆ π, then H(d|B) = 0 if and only if for every x_i, x_j ∈ U satisfying f_d(π_x0) ≠ f_d(π_y0), the relation x_i, x_j with regard to π is equivalent to their relation with regard to B, i.e. π_xi ⊄ π_xj, π_xj ⊄ π_xi ⇔ B_xi ⊄ B_xj, B_xj ⊄ B_xi.

Since the proof is similar, here there is no need to repeat it.

Supposing (U, π, d) be a consistent decision system. Assume U = {x₁, x₂, … x_n}; by M(U, π, d), we mark a n × n matrix (m_ij), called the discernibility matrix of (U, π, d), and defined as follows: A ∈ π : (A_xi ≠ A_xj) ∧ (A_xi ⊄ A_xj) ∧ (A_xj ⊄ A_xi), f_d(π_xi) ≠ f_d(π_xj)=m_ij π, f_d(π_xi) = f_d(π_xj) for .x_i, x_j ∈ U

Supposing (U, π, d) be a consistent covering decision system, then we obtain

(1) For every B ⊆ π, B ∩ m_ij ≠ ∅ is a valid result for every i, j ≤ n if and only if H(d|π) = 0.

Supposing (U, π, d) be a consistent covering decision system. Suppose E₁ ⊆ E,E = π − Core_d(π), then H(d|π − {E_i}) = 0 is true if and only if m_ij ⊆ E₁ for all m_ij,1 ≤ j ≤ i ≤ n.

⇐ Since E₁ ⊆ E, then any element of E cannot contain in Core_d(π), or in other words, it could be reduced. m_ij ⊄ E₁ for all m_ij, 1 ≤ j ≤ i ≤ n means that we could guarantee H(d|π − {E_i}) = 0 after the attributes on E₁ are reduced.

⇒ If the attributes on E₁ could be reduced at the same time, and there also exists a m_ij such that m_ij ⊆ E₁, then we obtain m_ij = ∅ after the attributes on E₁ are reduced at the same time, which point out the attributes on E₁ could not be reduced at the same time.

Suppose U is a finite universal set and π = A_i : i = 1, ..., m is a family of covers of U, A_i ∈ π, d is a decision attribute relative to π on U and f_d : U → V_d is the decision function, denoted by f_d(x) = [x]_d, then, Icds = U, π, d is an inconsistent covering decision system, i.e. H(d|π) ≠ 0 or POS_π (d) ≠ U.

Suppose Icds = U, π, d is an inconsistent covering decision system. For B ⊆ π, we define the limitary entropy, d, and limitary conditional entropy, π, as to attribute decision by LH(d|π)=−1|K|∑x∈Klog|[x]d∩πx||πx|;LH(d)=−1|K|∑x∈Klog[x]d|K|; \matrix{{LH(d|\pi) = - {1 \over {\left| K \right|}}\sum\limits_{x \in K} \log {{\left| {{{[x]}_d} \cap {\pi _x}} \right|} \over {\left| {{\pi _x}} \right|}};} \cr {LH(d) = - {1 \over {\left| K \right|}}\sum\limits_{x \in K} \log {{{{[x]}_d}} \over {\left| K \right|}};} \cr} the limitary mutual information of B and d is defined as follows LI(B;d)=LH(d)−LH(d|B)=−1|K|∑x∈Klog[x]d|K|−1|K|∑x∈Klog|[x]d∩Bx||Bx| LI(B;d) = LH(d) - LH(d|B) = - {1 \over {\left| K \right|}}\sum\limits_{x \in K} \log {{{{[x]}_d}} \over {\left| K \right|}} - {1 \over {\left| K \right|}}\sum\limits_{x \in K} \log {{\left| {{{[x]}_d} \cap {B_x}} \right|} \over {\left| {{B_x}} \right|}} where K = {x ∈ U : π_x ⊆ [x]_d}.

Suppose Icds = U, π, d is an inconsistent covering decision system. For every A_i ∈ π and LH(d|π − {A_i}) = LH(d|π), then A_i is superfluous relative to d in π. For every and, then is independent relative to in.

Suppose is an inconsistent covering decision system. For every B ⊆ π, if two following conditions are met:

LI(B; d) = LI(π; d),

Then B is a reduct of π relative to d, denoted by B ∈ Red_π (d).

Supposing Icds = (U, π, d) be an inconsistent covering decision system. For every W ⊆ B ⊆ π, then POS_W (d) ⊆ POS_B(d).

Suppose Cov(B) = {B_x : x ∈ U} and Cov(W) = {W_x : x ∈ U}. For every x ∈ POS_W (d), then there exists X ∈ U/d, such that x ∈ W (X). There exists y ∈ W_x, for every x such that W_x ⊆ X. Suppose B = W ∪ {b₁, …, b_t}, then the following attribute sets are made: B1=W∪{b1};B2=B1∪{b2};…Bt=Bt−1∪{bt}; \matrix{{{B_1} = W \cup \{{b_1}\} ;} \cr {{B_2} = {B_1} \cup \{{b_2}\} ;} \cr \ldots \cr {{B_t} = {B_{t - 1}} \cup \{{b_t}\} ;} \cr}

Obviously, we can get W ⊆ B₁ ⊆ … ⊆ B_t = B. For ∀b ∈ B, there exists B_x ⊆ (B − {b})_x such that B_x = B_tx ⊆ B_(t−1)x ⊆… ⊆ B_1x ⊆ W_x, i.e. B_x ⊆ W_x. Based on the covering lower approximation, we can have x ∈ B(X), then x ∈ POS_B(d). So for every W ⊆ B, then POS_W (d) ⊆ POS_B(d).

Supposing Icds = (U, π, d) be an inconsistent covering decision system. For B ⊆ π,|POS_π (d)| = |POS_B(d)| is true if and only if POS_π (d) = POS_B(d).

Here we will not prove it.

Suppose Icds = (U, π, d) is an inconsistent covering decision system, for every B ⊆ π, if b is a superfluous attribute relative to d in π, then Core_B(d) ⊆ Core_B−{b}(d) is true.

If a ∈ Core_B(d) and B − {a} ⊂ B ⊆ π, then POS_π (d) ⊇ POS_B−{a}(d). Since a is an indispensable attribute, then POS_π (d) ≠ POS_B−{a}(d), thus we can get x₁ ∉ POS_B−{a}(d) such that x₁ ∉ B−{a}(X, we can further get (B−{a})_x1 ⊄ X. For every (B − {a})_x1 ⊄ X and (B − {a})_x1 ⊆ ((B − {a}) − {b})_x1, then ((B−{b}) − {a})_x1 ((B−{a}) − {b})_x1 ⊄ X, which shows that x₁ ∉ POS_{(B−{b})−{a}}(d). Since X have arbitrary, x₁ ≠ POS_{(B−{b})−{a}}(d), thus POS_{(B−{b})−a}(d) ≠ POS_B−{a}(d). By the given condition, we will get Core_B−{b}(d) = POS_π (d) and a ∈ Core_B−{b}(d). Thus Core_B(d) ⊆ Core_B−{b}(d).

Supposing Icds = (U, π, d) be an inconsistent covering decision system. For B, Q ⊆ π and POS_B(d) = POS_Q(d), then LI(B; d) = LI(Q; d).

For every X ∈ U/d, by the definition of positive region, we get POSπ(d)=∪X∈U/dB_(X) {POS}_\pi(d) = \mathop \cup \limits_{X \in U/d} \underline B (X) . If every y in U, there exists x_i ∈ U then B_y ⊆ [x_i]_d⇔ Q_y ⊆ [x_i]_d. Since B(x) = {x : ∀y ∈ U (x ∈ B_y → B_y ⊆ X)}, Q(X) = {x : ∀y ∈ (x ∈ Q_y → Q_y ⊆ X)} and POS_B(d) = POS_Q(d), thus we obtain B(X) = π(X). Clearly, we get LD(d|B) = LD(d|Q). By the definition of mutual information, we can obtain I(B; d) = I(Q; d).

Suppose Icds = (U, π, d) is an inconsistent covering decision system. For every B ⊆ Q ⊆ π, if LI(B; d) = LI(Q; d) is true, then POS_B(d) = POS_Q(d).

The same is true; here we will not prove it.

Supposing Icds = (U, π, d) be an inconsistent decision system. For every B ⊆ Q ⊆ π, if LI(B; d) = LI(Q; d) is true if and only if POS_B(d) = POS_Q(d).

Suppose Icds = (U, π, d) is an inconsistent covering decision system, for every A_i ∈ π, A_i is a superfluous element relative to d in π, if and only if LH(d|π) = LH(d|π − {A_i}).

If A_i is a superfluous element relative to d in π, by the definition of positive region, we can get POS_π (d) = POS_π−{Ai}(d). And by Lemma 2, we have LI(π − {A_i}; d), thus LH(d|π − {A_i}) = LH(d|π).

If LI(π − {A_i}; d) = LH(d|π) ⇒ I(π; d) = I(π − {A_i}; d) and π − {A_i} ∈ π, by Theorem 10, we can obtain POS_π (d) = POS_π−{Ai}. Therefore, A_i is a superfluous element relative to d in π.

Supposing Icds = (U, π, d) be an inconsistent decision system. For every A_i ∈ π, A_i is dispensable relative to d in π, if and only if LH(d|C) < LH(d|π − {A_i}).

Supposing Icds = (U, π, d) be an inconsistent decision system. For every A_i ∈ π, A_i is independent relative to d in π, if and only if LH(d|C) < LH(d|π − {A_i}).

Suppose Icds = (U, π, d) is an inconsistent decision system, for every B, Q ⊆ π, if B ≺ Q, then LH(d|B) > LH(d|Q).

Suppose Cov(B) = {B_x : x ∈ U} and Cov(Q) = {Q_x : x ∈ U}. If B precQ, there exists B_x ⊆ Q_x for every x ∈ U.

Since (1) LH(d|B)−LH(d|Q)=−1|K|∑x∈Klog|[x]d∩Bx||Bx|−1|K|∑x∈Klog|[x]d∩Qx||Qx|=−1|K|2∑x∈Klog|[d]d∩Bx||Bx|×|[x]d∩Qx||Qx| LH(d|B) - LH(d|Q) = - {1 \over {|K|}}\sum\limits_{x \in K} \log {{|{{[x]}_d} \cap {B_x}|} \over {|{B_x}|}} - {1 \over {|K|}}\sum\limits_{x \in K} \log {{|{{[x]}_d} \cap {Q_x}|} \over {|{Q_x}|}} = - {1 \over {|K{|^2}}}\sum\limits_{x \in K} \log {{|{{[d]}_d} \cap {B_x}|} \over {|{B_x}|}} \times {{|{{[x]}_d} \cap {Q_x}|} \over {|{Q_x}|}}

If (1) met B_x ⊆ [x]_d, Q_x ⊆ [x]_d and B_x ⊆ Q_x, then LH(d|B) = LH(d|Q).

If (1) only met B_x ⊆ Q_x, we obviously can get LH(d|B) > LH(d|Q).

Therefore, LH(d|B) ≥ LH(d|Q).

Supposing Icds = (U, π, d) be an inconsistent covering decision system, if B precQ for every B, Q ⊆ π, then LI(B; d) ≥ LI(Q; d).

Here we will not prove it.

Supposing Icds = (U, π, d) be an inconsistent covering decision system. For every B, Q ⊆ π, if LH(d|B) > LH(d|Q) and LH(Q|B) = 0, then B ≺ 0.

Suppose Cov(B) = {B_x : x ∈ U} and Cov(Q) = {Q_x : x ∈ U}. If LH(d|B) > LH(d|Q) is true, then B_x ⊃ Q_x must be wrong (If B_x ⊃ Q_x is true, then LH(d|B) ≤ LH(d|Q) by Theorem 13, which is contradiction!), thus we could obtain B_x ⊆ Q_x or B_x ⊄ Q_x. If B_x ⊄ Q_x is true, there at least exists B_x1(x₁ ∈ U), for every Q_y1(y₁ ∈ U), then B_x1 ⊄ Q_y1, if B_x ∩ Q_x ≠ ∅ is true for every x ∈ U, then H(Q|B)=−1|K|∑x∈K|Qx∩Bx||Bx|>0 H(Q|B) = - {1 \over {|K|}}\sum\nolimits_{x \in K} {{|{Q_x} \cap {B_x}|} \over {|{B_x}|}} > 0 , which implies a contradiction, thus B_x ⊆ Q_x is true.

Suppose Icds = (U, π, d) is an inconsistent covering decision system. If LI(B; d) ≥ LI(Q; d) and LH(Q B) = 0, B, Q ⊆ π, then B ≺ Q.

Suppose Icds = (U, π, d) is an inconsistent covering decision system, all subjects on universe, U, are divided into consistent covering sub-table π|U₁ → d|U₁ and inconsistent covering sub-table π|U₂ → d|U₂. We denote a x× n matrix (m_ij), called the discernibility matrix of Icds, such that if x_u, x_j ∈ U satisfies {A∈π:(Axi⊂Axj)∧(Axj⊂Axi)}∨{Ap∧Aq:(Apxi⊂Apxj)∧(Aqxj⊂Aqxi)} \{A \in \pi :({A_{xi}} \not\subset {A_{xj}}) \wedge ({A_{xj}} \not\subset {A_{xi}})\} \vee \{{A_p} \wedge {A_q}:({A_{pxi}} \subset {A_{pxj}}) \wedge ({A_{qxj}} \subset {A_{qxi}})\}

Supposing Icds = (U, π, d) be an inconsistent covering decisive system, denoted by IM(π) = {m_ij} where m_ij is a single attribute, IM(π) = Core_d(π) is true if and only if ∃m_ij ∈ a single attribute such that m_ij ∈ Core_d(π).

We denote Cov(π − {A_i}) = {B_x : x ∈ U}, if A_i ∈ IM(π) is true, then there exists m_ij = {A_i} for every A_j ∈ π − {A_i} such that A_yj = A_xj is true.

Suppose x_j ∈ π([x_s]_d)(s ∈ [1, l]), we will divide them to two parts for further discussion: first we prove IM(π) ⊆ Core_d(π). If y_j ∈ U 1 and f_d(x_j) ≠ f_d(y_j) are true, then there exists t ∈ [1, l] and t ≠ s such that y_j ∈ π([x_y]_d) and B_xj ∩ π([x_t]_d) ≠ ∅.

By Definition 12, A_i is indispensable. If y_j ∈ U 2 is true, then B_xj ∩ U 2 = ∅ is true such that a_i is indispensable. So IM(π) ⊆ Core_d(π) is true.

On the other hand, if A_i ∈ Core_d(π) is true, then there exists x_s ∈ π([x_i]_d)(i ∈ [1, k]) such that one of the following conditions is true:

(1) there exists j ∈ [1, k] and j ≠ i such that B_xs ∩ [x_j]_d ≠ ∅;

If Condition (1) is true, then there exists x_t [x_j]_d and A_j ∈ π − {A_i} such that A_xsj = A_xij and A_xsi ≠ A_xti, and because of x_s ∈ ([x_i]_d), x_t ∈ ([x_t ]_d), then we can obtain f_d(x_s) ≠ f_d(x_t) for x_s ∈ U 1, x_t ∈ U 2 such that m_st ∈ {A_i}.

If Condition (2) is true, then there exists x_r ∈ U 2, for every A_j ∈ − π − {A_i} such that A_xsj = A_xrj and A_xsi ≠ A_xri for x_s ∈ U 1, x_y ∈ U 2, therefore we could get m_sr = {A_i}. So Core_d(π) ⊆ IM(π) is true.

Supposing Icds = (U, π, d) be an inconsistent covering decision system, denoted by subset E = π − Core(π), E₁ ⊆ E, then POS_π (d) = POS_{π−{E1}(d1)} is true if and only if for every m_ij(1 ≤ j ≤ i ≤ n) such that m_ij ⊄ E₁ is true.

If there exists E₁ ⊆ E such that any element of E₁ does not belong to Core_d(π), so E₁ can be reduced. If for every m_ij and 1 ≤ j ≤ i ≤ n, then we could get m_ij ⊄ E₁, which still ensure POS_π (d) = POS_π−{E1}(d₁) after reduction of properties on E₁ at the same time.

If there exists m_ij after reduction by properties on E₁ contemporarily such that m_ij and m_ij = ∅ is true, which implies properties on E₁ cannot be reduced at the same time.

Theorem 18 implies that as long as there is a simple observation and treatment for discernibility matrix, we will have cores and reducts in the inconsistent covering decision system. The following Corollary 7 can be founded in the literature [21, 25].

Suppose B ⊆ π, then B is a relative reduct of π if and only if it is the minimal set satisfying B ∩ m_ij ≠ ∅ for m_ij ≠ ∅, i, j ≤ n.