广义近似空间与粗糙分类代数

摘要

提出了广义近似空间、粗近似公理、干扰集公理、粗糙集的分类原则、粗选原则、不确定偶集原则、精选原则、对策分类、量子逻辑分类、bit量子对称分类、不可比集、bit空间集、协议关系、粗糙集函数、粗糙分类代数和粗糙单代数等基本概念，并提出了一个猜想；展示了一些新观点；基于协议关系构造了粗糙商代数和粗糙子代数，给出了回避-归并算法及算例。

正文

《1 引言》

1 引言

粗糙集理论 ^[1,2,3] 是近10年来国际上信息科学和计算机科学的一个研究热点 ^{[4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28]}。近几年来, 其中近似空间和粗糙代数结构引起了一些学者的关注。

近似空间中的分类问题是一个基本问题, 又是一个重要的中心问题。分类虽然可以作广泛的理解, 但它受到知识认知和行为原则的限制。波兰科学院院士, 数学家Pawlak在研究近似空间时, 基于二元等价关系, 提出了粗糙集概念 ^[1]。但Pawlak意义下的粗糙集分类方法存在概念基础上的局限性。

值得研究的问题是关于知识的理解及分类、信息系统的智能处理等问题, 在一定意义下, 都涉及一致性问题以及协议关系问题。更确切地说, 是粗糙集与条件属性的关系、信息系统 (或知识库) 与基于协议关系的粗糙分类代数的关系、知识分类的协议性等问题;上近似集与下近似集的关系构成一种代数结构的问题。

笔者引进了广义近似空间概念, 涉及量子逻辑分类、对策分类等;给出了有关的公理、原则, 提出并证明了几个定理, 还提出了一个猜想, 引进了一种新的空间, 展示了一些新观点, 讨论了集合元素 (或知识元) 间存在一种特殊性质的关系, 即代数的协议关系。实际上协议关系是代数结构的一种关系。笔者从选择公理和良序定理出发 ^[29], 提出了协议分类代数、协议关系、粗糙单代数和协议关系粗糙函数等概念, 刻画了协议关系的粗糙分类代数性质, 构造了一个新代数, 即粗糙商代数, 提出了粗糙分类代数、粗糙子代数等概念, 讨论了粗糙子代数的性质, 给出了粗糙子代数的充要条件, 提出了粗糙子代数的同态映射、二重性定理等。最后还提出了回避-归并算法, 并给出了一个例子。

《2 广义近似空间的基本理论》

2 广义近似空间的基本理论

设U<∞, U是论域, 近似空间是偶对 (U, R) , 其中R是U上的非空集合关系, 称为Pawlak近似空间。对于X⊆U定义2个子集:

上近似集:A_u (X) ={X∈U| R (X) ∩X≠〉};

下近似集:A_d (X) ={X∈U|R (X) ⊆X}。

定义1 粗糙集R (X) 满足下列条件:

1) A_u (X) , A_d (X) ≠〉;

2) A_u (X) ∪A_d (X) ∈R (X) ;

3) 若α∈A_u (X) , β∈A_d (X) , 则β<α。

对于粗糙集偶对 (A_u (X) , A_d (X) ) , 称为R (X) 的极限分类, A_u (X) 称为这个极限分类上近似集, A_d (X) 称为它的下近似集。

公理1 (粗近似公理) 对Pawlak近似空间 (U, R) 中的A_u (X) 和A_d (X) , 下列4种情况, 必有一种情况发生:

1) A_u (X) >A_d (X) ;2) A_u (X) =A_d (X) ;

3) A_u (X) <A_d (X) ;4) A_u (X) ‖A_d (X) 。

其中“‖”表示不可比较关系。

原则1 (粗糙集的分类原则) Pawlak近似空间 (U, R) , 对于定义1, 存在粗糙集R (X) , 称为A_u (X) 与A_d (X) 的无序对集合, 记为{A_u (X) , A_d (X) };称为A_u (X) 与A_d (X) 有序对集合, 记为{A_u (X) , {A_u (X) , A_d (X) }}。

原则2 (粗选原则) 对于Pawlak近似空间 (U, R) , 有下列原则:

1) 若选公理1中的A_u (X) =A_d (X) , 则记为{A_u (X) }, 即为近似对象A_u (X) 的单元粗糙集合, 意味着含一个元素A_u (X) , 称R (X) 为退化了的不可测粗糙集。

2) 若选公理1中的A_u (X) ‖A_d (X) , 有

$S (X) = {A_{u} (X) ∥ A_{d} (X) | x \in A_{u} (X), A_{d} (X)} ‚$ $S (X) = {A_{u} (X) ∥ A_{d} (X) | x \in A_{u} (X), A_{d} (X)} ‚$

则称S (X) 为不可比较集或称互补集, 意味着上近似集与下近似集之间存在平行的真实关系, 即互补关系, 用图1的格图表示。

《图1》

图1格图

Fig.1 Lattice graph

规定:0≤A_u (X) ≤1;0≤A_d (X) ≤1, 则子格〈{1, A_u (X) , 0}, ≤〉和子格〈{1, A_d (X) , 0}, ≤〉是U上的2个子格, 图1中虚线表示A_u (X) 将U中的元素划分为2类。

为了表明不同概念在对策意义下的一致性, 引入对策分类定义。

定义2 设 (A_u (X) , A_d (X) ) 是一个极限分类, 记为R (X) , 若存在平衡偶对 (min A_u (X) , max A_d (X) ) 则称为对策分类, 记为K (X) 。

定义3 粗糙集R (X) 的bit空间集记为R_bit (X) , 它的空间 (U, R_bit) 由范数导出, 即

$∥ R_{b i t} ∥ = \sum_{k = 1}^{n} \max_{x \in U} | \min A_{u} (X) - \max A_{d} (X) | 。$ $∥ R_{b i t} ∥ = \sum_{k = 1}^{n} \max_{x \in U} | \min A_{u} (X) - \max A_{d} (X) | 。$

所形成的Banach空间记为L^b (U, R, R_bit) 。

定义4 (A_u (X) , A_d (X) , S (X) ) 称为广义近似空间U的量子逻辑分类, 记为Q_U (X) , 其中S (X) 是基于半序关系的不确定集。

注1 Pawlak粗糙集的上近似集与下近似集是一种特殊情况下的分类。近似空间中粗糙集格性质的量子分类 ^[28]与此量子逻辑分类一起, 成为广义近似空间一般的分类形式。

定义5 设A_u (X) , S (X) 是U上的2个等价关系。当 (a, b) ∈S (X) 时, 必有 (a, b) ∈A_u (X) , 则称S (X) 确定的分类比A_u (X) 确定的分类精细。

定义6 (A_u (X) , S (X) ) 称为上投影分类, 记为P_u (X) ; (A_d (X) , S (X) ) 称为下投影分类, 记为P_d (X) 。

公理2 (干扰集公理) 广义近似空间 (U, R, S) 中, 存在U上的半序关系干扰集, 记为I (X) , 形如

$Ι (X) = {X \in U (S | X) \cap X \neq 〉} 。$ $Ι (X) = {X \in U (S | X) \cap X \neq 〉} 。$

对于定义3, 下列3种情况, 必有1种情况发生:

1) R_bit (X) <I (X) ;

2) R_bit (X) ≌I (X) ;

3) R_bit (X) >I (X) 。

其中 “≌”表示同构关系。

原则3 (不确定的偶集原则) 对于广义近似空间 (U, R, S) , 存在着R_bit (X) 与I (X) 的不确定偶集, 记为Ψ (X) , 即{R_bit (X) , I (X) }, 有

Ψ (X) ={X∈U|I (X) ∩X≠〉}。

原则4 (精选原则) 对不确定干扰集I (X) , 有下列原则:

1) 若选公理2中的R_bit (X) ≌I (X) , 则为定义3的bit空间集, 或称bit量子集, 记为{R_bit (X) };

2) 若选公理2中的R_bit (X) >I (X) , 则为广义近似空间的隐bit量子集, 记为{R_bit^- (X) };

3) 若选公理2中的R_bit (X) <I (X) , 则为广义近似空间的显bit量子集, 记为{R_bit⁺ (X) }。

定义7 对于广义近似空间的bit空间集合 (U, R_bit) , x∈R_bit (X) , (R_bit^- (X) , R_bit⁺ (X) ) 称为bit量子对称分类, 记为Y (X) 。

定义8 (R_bit^- (X) , R_bit⁺ (X) , I (X) ) 称为广义近似空间的bit量子逻辑分类, 记为T_bit (X) , 其中I (X) 是基于半序关系的干扰集。

关于广义近似空间理论的上近似集元素的数目临界问题, 有下面定理:

定理1 (临界定理) 若A_ui (X) ∩A_uj (X) ≠〉, A_ui (X) ∪A_uj (X) ≠A_u (X) , i≠j, A_u (X) ={A_u1 (X) , A_u2 (X) , …, A_us (X) }, 1≤i, j≤s, 则

$s \leq C_{n - 1}^{[n / 2] - 1} 。$ $s \leq C_{n - 1}^{[n / 2] - 1} 。$

证明设补集为A′u (X) ={A′_u1 (X) , A′_u2 (X) , …, A′_us (X) }, 考虑A_u (X) 。由于

A_ui (X) ∩A_uj (X) ≠〉, 于是

A_ui (X) ⊈A′_{_uj} (X) , 且A_ui (X) ⊉A′_uj (X) , 得

A_ui (X) ∩A′_uj (X) ≠〉;由于

A_ui (X) ∪A_uj (X) ≠N, N={1, 2, …, n}, 于是

A′_ui (X) ∩A′_{_uj} (X) ≠〉。

A_u (X) 是n元集N的子集, 且{A_u (X) , A′u (X) }分为2个集, A_u (X) 中的集元数均≤n/2, 并且当|A_ui (X) | =n/2时, A_ui (X) 与A′_ui (X) 仅有一个在A_u (X) 中, |A_ui (X) |≤k≤n/2, A_ui (X) 可用每两个互补的k元集代替, 当|A_ui (X) |=k, 有

$A_{u i} (X) = A^{'}_{u i} (X) 。$ $A_{u i} (X) = A^{'}_{u i} (X) 。$

显然, 当|A_ui (X) |递增, C $_{n - 1}^{| A_{u i} (X) | - 1}$ $_{n - 1}^{| A_{u i} (X) | - 1}$ 也会相应增强, 即满足

∑1/C $_{n - 1}^{| A_{u i} (X) | - 1}$ $_{n - 1}^{| A_{u i} (X) | - 1}$ ≤1, A_ui (X) ∈A_u (X) 。

其中A_ui (X) ≤[n/2], 于是有

C $_{n - 1}^{| A_{u i} (X) | - 1}$ $_{n - 1}^{| A_{u i} (X) | - 1}$ ≤C $_{n - 1}^{[n / 2] - 1}$ $_{n - 1}^{[n / 2] - 1}$ 。

从而A_u (X) 中的子集恰有s个, 即得s≤C $_{n - 1}^{[n / 2] - 1}$ $_{n - 1}^{[n / 2] - 1}$ 。

注2 从定理1可以看出, 广义近似空间的上近似集元素s的临界是可预测的。

定理2 ^[28] 在近似空间中 (Pawlak意义下的) , 不存在一般完全分类。 (证明略)

定理3 对于广义近似空间, R (X) 中的任何量子对称分类N (X) , 都有N (X) ⊆Q_U (X) 成立。

证明设N (X) 是任何分类, 当x∈N (X) , 且x∈R_bit (X) , 必有x的bit量子对称分类Y (X) , 使

Y (X) ⊆N (X) ⊆R (X) ,

由于x∈Q_U (X) , R (X) ⊆Q_U (X) , 于是得N (X) ⊆Q_U (X) 。证毕。

定理4 对于广义近似空间 (U, R, S) , R (X) 成为T_bit (X) 的充分必要条件:

$A_{u} (X) ＜ Ι (X) ＜ A_{d} (X), x \in U 。$ $A_{u} (X) ＜ Ι (X) ＜ A_{d} (X), x \in U 。$

证明当A_u (X) <I (X) , 由公理2和原理2, 生成

${A_{u} (X)} ≌ {R_{b i t}^{+} (X), Ι (X)} ；$ ${A_{u} (X)} ≌ {R_{b i t}^{+} (X), Ι (X)} ；$

同理, 生成

{A_d (X) }≌{R_bit^- (X) , I (X) }。

反之, 若

(A_u (X) , A_d (X) ) ≌ (R_bit⁺ (X) , R_bit^- (X) , I (X) ) ,

根据定理3, 在bit量子逻辑意义下, 则有

$A_{u} (X) \subseteq Ι (X) \subseteq A_{d} (X)) 。$ $A_{u} (X) \subseteq Ι (X) \subseteq A_{d} (X)) 。$

易推得A_u (X) <I (X) <A_d (X) 成立。

猜想设广义近似空间 (U, R, S) , 若存在干扰集I (X) , 则有

$S (X) = \cup_{k = 1}^{n} Ι_{k} (X) ‚$ $S (X) = \cup_{k = 1}^{n} Ι_{k} (X) ‚$

I_k (X) 中两两互不可比, 即I_i (X) ‖I_j (X) , i≠j。

新观点:

1) 相信的程度与知识分类的原则无关;

2) 知识是一种逻辑, 如量子逻辑;

3) 知识的所有近似描述组成的集, 称为知识的广义近似空间。对知识的分类就是广义近似空间的一个子集;

4) 知识的发现量可以用映射来表示。

《3 粗糙分类代数概念》

3 粗糙分类代数概念

定义9 设粗糙分类代数是一个对生 (opposite) R= (B, S) , 其中B是一个非空粗糙集构成的集合族, ∀A∈B, 称A是粗糙分类代数R的基集, S≠〉, ∀s∈S,

$s : A_{i 1} \times A_{i 2} \times \dots \times A_{i n} \to A_{i} ‚$ $s : A_{i 1} \times A_{i 2} \times \dots \times A_{i n} \to A_{i} ‚$

其中A_i1, A_i2, …, A_in, A_i∈B, n∈N, 称S是B上有限元运算的一个集合。

定理5 定义9中的S集可良序。

证明由于每一个集合都是可以良序的 ^[29], 这样, 定理5显然也成立。

定理6 对于定义9中的集合S, S的基数 $| ω_{s} |$ $| ω_{s} |$ 有意义, 当且仅当定理5成立。

证明 1) 基数ω_s有意义, 表明存在某个基数O, 使ω_s与O等势, 记为E_P (ω_s, O) , 于是ω_s=O, 设S集可良序, 且存在保序双射f∶S→O, 于是存在O到ω_s的保序双射g∶O→ω_s, O可良序, 从而诱导了ω_s成为良序;

2) 若构造序数ω_s的良序成为良序集, 在相同序结构的意义下, 则可推导出与ω_s等势的最小序数 $| ω_{s} | 。$ $| ω_{s} | 。$

注3 定理6意味着, 可用与基数等势的方式计算ω_s的元素个数。R= (B, S) 中的S为良序, 记作S={s₀, s₁, s₂, …, s_i, …}, i<J, 其中J为一个序数。这样, S与J建立了一个同构对应, 从而建立S上的良序关系<_s。

定义10 设R= (B, S) , 若s_i是n_i元运算, 则称R为On型, 即

$Ο n = (n_{0}, n_{1}, n_{2}, \dots, n_{i}, \dots), i ＜ J 。$ $Ο n = (n_{0}, n_{1}, n_{2}, \dots, n_{i}, \dots), i ＜ J 。$

称J为On型的阶。

注4 对于定义10, 在一定意义下, n_i=0, S是良定义的。

定义11 设R= (B, S) , 其中零元运算的集合是k⊆B, 若k对R中所有运算封闭, 则 (k, S) 是R的粗糙子代数, 且称这个子代数和R自身是R的平凡粗糙子代数。

定义12 设非零正整数集N⁺的子集S, 若S对N⁺的乘法运算封闭, 则称S为N⁺的一个粗糙子代数。

《4 协议关系》

4 协议关系

定义13 设Z是整数集, N⁺是非零正整数集, 若对非零协议数τ, 使

$τ = {α} \cap {β}, \forall α, β \in Ζ, \forall τ \in Ν^{+} 。$ $τ = {α} \cap {β}, \forall α, β \in Ζ, \forall τ \in Ν^{+} 。$

则称α协议于β, 记作α≈β (τ) 。

协议式 α与β是协议关系, α协议于β是由协议数τ诱导的结果。协议式为

$α \approx β (τ), i f f τ = {α} \cap {β} 。$ $α \approx β (τ), i f f τ = {α} \cap {β} 。$

定义14 设≈是集合B上的一个二元关系, ∀α, β∈B, τ是协议数, 若协议式满足

$α \approx α (τ), 自反性；$ $α \approx α (τ), 自反性；$

若α≤β且β≤α, 则蕴含

$α \approx β (τ), 反对称性。$ $α \approx β (τ), 反对称性。$

则称≈是B的一个协议关系。

注5 与半序关系比较, 协议关系是更为普遍的二元关系。显然, 所有半序关系都是协议关系。因此, 协议概念是半序概念的一种推广。

定义15 设≈是集合B上的一个二元关系, ∀a, b, c∈B, τ是协议数, 若协议式满足

$a \approx b (τ), b \approx c (τ), c \approx a (τ) ‚$ $a \approx b (τ), b \approx c (τ), c \approx a (τ) ‚$

则称≈是协议循环关系。

性质1 (置换性) 设R= (B, S) 为On型, 若对任意的x<On, S_x∈S, 且α_i, β_i∈B, ω_s是B上的一个等价关系, 有

$\begin{array}{l} α_{i} \approx β_{i} (ω_{s}), 0 \leq i \leq n_{x} ‚ 使 \\ s_{x} (α_{0}, \dots, α_{n_{x} - 1}) \approx s_{x} (β_{0}, \ :, β_{n_{x} - 1}) (ω_{s}), \\ \forall s_{x} (α), s_{x} (β) \in S ‚ \end{array}$ $\begin{array}{l} α_{i} \approx β_{i} (ω_{s}), 0 \leq i \leq n_{x} ‚ 使 \\ s_{x} (α_{0}, \dots, α_{n_{x} - 1}) \approx s_{x} (β_{0}, \ :, β_{n_{x} - 1}) (ω_{s}), \\ \forall s_{x} (α), s_{x} (β) \in S ‚ \end{array}$

则称ω_s为R上的一个协议关系。

性质2 (存在性) 对于任意的协议分类代数R, 若存在性质1 (置换性) , 则存在协议关系≈。

定义16 设R= (B, S) , 若协议关系≈对R中所有的运算都符合性质1和性质2, 则称≈是R上的协议关系, 且称B中关于≈的类为R上的协议类, 记作[α], 其中α₁, α₂, …, α_n∈B, 称α为协议类[α]的代表元素。

定义17 设R= (B, S) , 若δ是粗集B上的一个等价关系, 且满足性质1, 则称δ为R上的一个协议关系。

对于定义17, 有下面2种情形:

情形1 (δ_Ⅰ定义) 设R= (B, S) , 若二元关系δ_Ⅰ是B上的一个等价关系, α与β对δ_Ⅰ的协议式定义为

$α \approx β (δ_{Ⅰ}), \forall α, β \in B 。$ $α \approx β (δ_{Ⅰ}), \forall α, β \in B 。$

如果满足性质1, 则称δ_Ⅰ是B上的一个完备协议关系。

情形2 (δ_Ⅱ定义) 设R = (B, S) , 若二元关系δ_Ⅱ是B上的一个等价关系, α与β对δ_Ⅱ的协议式定义为

$α \approx β (δ_{Ⅱ}), i f f α = β, \forall α, β \in B ‚$ $α \approx β (δ_{Ⅱ}), i f f α = β, \forall α, β \in B ‚$

如果满足性质1, 则称δ_Ⅱ是B上的一个等价协议关系。

定义18 对R= (B, S) 上的所有协议关系构成的粗糙集, 称为粗糙分类代数的协议关系粗糙集, 记作POR (R) , 且称|POR (R) |为R的协议基数。

注6 对于情形1和情形2, 若δ_Ⅰ, δ_Ⅱ∈POR (R) , 且POR (R) ≠0, 可基于协议关系来定义一类比较简单的代数, 即定义19。

定义19 若POR (R) ={δ_Ⅰ, δ_Ⅱ}, 且满足自同态映射Ψ∶B→B, 则称为粗糙单代数 (rough simple algebra) , 记作R_δ= (B, S) 。

定义20 广义近似空间上所有粗糙分类代数构成的类记作PRC。

定义21 设R= (B, S) , 如果在B上定义了若干关系, 且这些关系构成了一个集合G, 则称为关系集G的一个代数, 记作R_G= (B, S, G) 。

注7 对于定义21, R_G是粗糙分类代数结构中的一种情形。

例1 关系集G=POR (R) 。

例2 设R = (L_s, ∨, ∧) 是一个任意的粗糙格 ^[28], 其中L_s是一个非空半序关系粗集, 令∀α, β∈L_s, 有

$α \leq β, i f f α \lor β = β, i f f α \land β = α ‚$ $α \leq β, i f f α \lor β = β, i f f α \land β = α ‚$

则“≤”是定义9中B上的一个半序关系, R是“≤”的一个序代数R_≤= (L_s, ∨, ∧, ≤) 。

定义22 设CNC表示R的基数的类, R的基数函数

CNF∶PRC→CNC, R→CNF (R) 。

定义23 一个协议关系粗集函数

PRF∶PRC→CNC, R→|POR (R) |,

且称PRF (R) =|POR (R) |为R的协议粗糙集基数。

定理7 若R∈PRC, 则粗糙单代数R_δ有

PRF (R) =|POR (R) |=1, 2。 (证明略) 。

定理8 设ψ: B→C是从R= (B, S) 到V= (C, S) 的一个同态映射, 令λ∈POR (V) , B上有一个二元关系:

$ξ_{ψ, λ} ∶ α \approx β (ξ_{ψ, λ}), i f f ψ (α) \approx ψ (β) (λ), α, β \in B,$ $ξ_{ψ, λ} ∶ α \approx β (ξ_{ψ, λ}), i f f ψ (α) \approx ψ (β) (λ), α, β \in B,$

则ξ_{ψ, λ}∈POR (R) , 称ξ_{ψ, λ}是λ受ψ诱导的协议关系。

证明显然, ξ_{ψ, λ}是一个等价关系, 根据性质1和定义17可以证明定理8成立, (略) 。

例3 设ψ∶B→C是从 (B, S) 到 (C, S) 的一个同态映射, 运用情形1 (δ_Ⅰ定义) 给出δ_B或δ_C, 则

$ξ_{Ψ, δ_{C}} = δ_{B} 。$ $ξ_{Ψ, δ_{C}} = δ_{B} 。$

证明设B中的任意元素α和α′, 根据定理8, 有

$α \approx α^{'} (ξ_{Ψ, δ_{C}}), i f f ψ (α) \approx ψ (α^{'}) (δ_{C}),$ $α \approx α^{'} (ξ_{Ψ, δ_{C}}), i f f ψ (α) \approx ψ (α^{'}) (δ_{C}),$

又从δ_C定义知

$ψ (α) \approx ψ (α^{'}) (δ_{C}) ‚$ $ψ (α) \approx ψ (α^{'}) (δ_{C}) ‚$

于是有

$α \approx α^{'} (ξ_{Ψ ‚ δ_{C}}) ‚ α ‚ α^{'} \in B ‚$ $α \approx α^{'} (ξ_{Ψ ‚ δ_{C}}) ‚ α ‚ α^{'} \in B ‚$

故ξ_{Ψ, δ_C}=δ_B。

定理9 设ψ∶B→C是从 (B, S) 到 (C, S) 的一个同态映射, φ∶C→D是从 (C, S) 到 (D, S) 中一个同态映射。若

$\begin{array}{l} d \in D (D) ‚ h_{φ, d} \in D (C) ‚ h_{ψ, h_{φ, d}} \in D (B) ‚ \\ h_{φ ˚ ψ, d} \in D (B) ‚ \end{array}$ $\begin{array}{l} d \in D (D) ‚ h_{φ, d} \in D (C) ‚ h_{ψ, h_{φ, d}} \in D (B) ‚ \\ h_{φ ˚ ψ, d} \in D (B) ‚ \end{array}$

则h_{ψ, h_{φ, d}}=

《图2》

证设α, β∈B, 根据性质1, 则有

$\begin{array}{l} α \approx β (h_{ψ, h_{φ, d}}), i f f ψ (α) \approx ψ (β) (h_{φ, d}) ‚ \\ i f f φ (ψ (α)) \approx φ (ψ (β)) (d), \\ i f f (φ ˚ ψ) (α) \approx (φ ˚ ψ) (β) (d), \\ i f f α \approx β (h_{φ ˚ ψ, d}) ‚ \end{array}$ $\begin{array}{l} α \approx β (h_{ψ, h_{φ, d}}), i f f ψ (α) \approx ψ (β) (h_{φ, d}) ‚ \\ i f f φ (ψ (α)) \approx φ (ψ (β)) (d), \\ i f f (φ ˚ ψ) (α) \approx (φ ˚ ψ) (β) (d), \\ i f f α \approx β (h_{φ ˚ ψ, d}) ‚ \end{array}$

从而得h_{ψ, h_{φ, d}}=

《图3》

定义24 设≈是集合A的一个协议关系, 令B⊆A, 任一α_i∈B, i=1, 2, …, n, 若

$\begin{array}{l} α_{i} \approx α_{1}, \dots, α_{i - 1}, α_{i + 1}, \dots, α_{n} (τ) ‚ 且 \\ β_{j} \in A - B, j = 1, 2, \dots, m ‚ 有 \\ β_{j} ≉ α_{1}, \dots, α_{n} (τ) ‚ \end{array}$ $\begin{array}{l} α_{i} \approx α_{1}, \dots, α_{i - 1}, α_{i + 1}, \dots, α_{n} (τ) ‚ 且 \\ β_{j} \in A - B, j = 1, 2, \dots, m ‚ 有 \\ β_{j} ≉ α_{1}, \dots, α_{n} (τ) ‚ \end{array}$

则称B为≈的一个最大协议类。

定义25 若协议类个数有限, 则τ的不同协议类的个数称为τ的秩, 否则秩为无限。

定理10 设τ是非空有限集合A上的协议关系, 若B是一个协议类, 则存在一个最大协议类B_P, 使B⊆B_P。

证明设A={α₁, …, α_n}, 构造协议类的序列:

B₀⊆B₁⊆B₂⊆…,

使B₀=B₁, B_i+1=B∪{α_j}, 且满足α_j∈/B_i, 于是α_j与B_j中各元素有≈关系的最小下标, 由于|A|=n, 从而至多经过n-|B|步就会停止, 且序列中的最后一个协议类为B_P, 证毕。

定理11 设τ是非空集合A的协议关系, τ的协议类集合{[α]_τ|α∈A}是A的一个分类。 (证明略)

准则1 (方向判定准则, 方向判定定理) 若一个偶对集P协议于2个或2个以上偶对集的协议类, 且满足定义15, 则舍去P的方向;否则, 为所求的方向。 (证明略)

准则2 (极小化的协议图判别准则) 对于准则1, 舍去P的方向, 删去弧 (或边) 。 (证明略)

不等式1 (协议图不等式) 设协议图有n个结点, 且结点的自回路定义为空回路〉, 若有向弧 (或边) 数k满足

1≤k≤n,

则称协议图为极小化的协议图。

定义26 设非空集合A, 若存在集合Θ满足

1) 〉∈/Θ;

2) (∀x) (x∈Θ→x⊆A) ;

3) ∪Θ=A。

则称Θ是A的一个协议覆盖, 且称Θ中的元素是Θ的协议覆盖块。

定义27 对非空集合A上的协议关系, 最大协议类的集合是A的一个协议覆盖Θ, 则称为A的完全协议覆盖, 记作B_P (A) 。

定理12 对定义27, B_P (A) 是惟一的。 (证明略)

推论1 设非空有限集合A, 非空最大协议类B_P, 有B_P={A₁, …, A_n}, 若

$A = \cup_{i = 1}^{n} A_{i},$ $A = \cup_{i = 1}^{n} A_{i},$

则B_P是A的协议覆盖。 (证明略)

注4 对推论1的反问, 即构造A的协议覆盖, 未必需要最大协议类。

《5 协议关系定义的粗糙商代数》

5 协议关系定义的粗糙商代数

基于定义9来考虑一类特殊的粗糙代数——具有协议关系的粗糙商代数。

定义28 设粗糙分类代数 (B, ·) 及其上的协议关系的粗糙商集上的运算“*”, 对任一[B₁]_τ, [B₂]_τ∈R/τ, 有

$[B_{1}]_{τ} * [B_{2}]_{τ} = [B_{1} \cdot B_{2}]_{τ} 。$ $[B_{1}]_{τ} * [B_{2}]_{τ} = [B_{1} \cdot B_{2}]_{τ} 。$

其中, B₁, B₂∈B, 从而构成了一个新的代数 (R/τ, *) , 称为粗糙分类代数 (B, ·) 的商代数。

定义29 设R= (B, S) 是一个粗糙商代数, 由R生成的所有粗糙商代数集, 记作RQA (H) , 即RQA (H) ={R/τ|τ∈POR (H) }。且称|RQA (H) |为RQA (H) 的基数。

定义30 一个粗糙商代数集函数

RQF∶PRC→CNC, H→|RQA (H) |,

称RQF (H) 为H的粗糙商代数集度数。

定理13 设R= (B, S) , τ=POR (R) , 令

$\begin{array}{l} B / τ = {[α]_{τ} | α \in β} ‚ \\ [α]_{τ} = {β \in B | β \approx α (τ)} ‚ \end{array}$ $\begin{array}{l} B / τ = {[α]_{τ} | α \in β} ‚ \\ [α]_{τ} = {β \in B | β \approx α (τ)} ‚ \end{array}$

且s_x∈S, 令

$s_{x} ([α_{0}]_{τ}, \dots, [α_{n_{x} - 1}]_{τ}) = [s_{x} (α_{0}, \dots, α_{n_{x} - 1})]_{τ} ‚$ $s_{x} ([α_{0}]_{τ}, \dots, [α_{n_{x} - 1}]_{τ}) = [s_{x} (α_{0}, \dots, α_{n_{x} - 1})]_{τ} ‚$

则R/τ≈ (B/τ, S) 称为R的一个粗糙商代数H, 且它是由τ生成的粗糙商代数。

证明设α_i≈β_i (τ) , α_i, β_i∈B, 0≤i≤n_x, 由于τ∈POR (R) , 有

$\begin{array}{l} s_{x} (α_{0}, \dots, α_{n_{x} - 1}) \approx s_{x} (β_{0}, \dots, β_{n_{x} - 1}) (τ) 。于是 \\ s_{x} ([α_{0}]_{τ}, \dots, [α_{n_{x} - 1}]_{τ}) = [s_{x} (α_{0}, \dots, α_{n_{x} - 1})]_{τ} = \\ [s_{x} (β_{0}, \dots, β_{n_{x} - 1})]_{τ} = \\ s_{x} ([β_{0}]_{τ}, \dots, [β_{n_{x} - 1}]_{τ}) 。 \end{array}$ $\begin{array}{l} s_{x} (α_{0}, \dots, α_{n_{x} - 1}) \approx s_{x} (β_{0}, \dots, β_{n_{x} - 1}) (τ) 。于是 \\ s_{x} ([α_{0}]_{τ}, \dots, [α_{n_{x} - 1}]_{τ}) = [s_{x} (α_{0}, \dots, α_{n_{x} - 1})]_{τ} = \\ [s_{x} (β_{0}, \dots, β_{n_{x} - 1})]_{τ} = \\ s_{x} ([β_{0}]_{τ}, \dots, [β_{n_{x} - 1}]_{τ}) 。 \end{array}$

这样, 保证s_x的每一个运算都受协议关系τ的诱导, 从而H=R/τ≈ (B/τ, S) 。

定理14 设R= (B, S) , 若τ∈POR (R) , 令一个同态映射

$ψ_{τ} : B \to B / τ, α \to [α]_{τ} ‚$ $ψ_{τ} : B \to B / τ, α \to [α]_{τ} ‚$

则ψ_τ: (B, S) → (B/τ, S) , α→[α]_τ。

证明设α₀, …, α_{n_x-1}∈B, s_x∈S, 于是有

$\begin{array}{l} ψ_{τ} (s_{x} (α_{0}, \dots, α_{n_{x} - 1})) = [s_{x} (α_{0}, \dots, α_{n_{x} - 1})]_{τ} = \\ s_{x} ([α_{0}]_{τ}, \dots, [α_{n_{x} - 1}]_{τ}) = \\ s_{x} (ψ_{τ} (α_{0}), \dots, ψ_{τ} (α_{n_{x} - 1})) 。 \end{array}$ $\begin{array}{l} ψ_{τ} (s_{x} (α_{0}, \dots, α_{n_{x} - 1})) = [s_{x} (α_{0}, \dots, α_{n_{x} - 1})]_{τ} = \\ s_{x} ([α_{0}]_{τ}, \dots, [α_{n_{x} - 1}]_{τ}) = \\ s_{x} (ψ_{τ} (α_{0}), \dots, ψ_{τ} (α_{n_{x} - 1})) 。 \end{array}$

这样, 保证s_x的每一个运算都受到协议关系的诱导, 从而定理成立, 证毕。

定理15 设H= (B/τ, S) , 若τ∈POR (R) , 而B中有一个协议关系, 记作ξ_{Ψ_t}。令

$ψ_{τ} ∶ (B, S) \to (B / τ, S), α \to [α]_{τ} ‚$ $ψ_{τ} ∶ (B, S) \to (B / τ, S), α \to [α]_{τ} ‚$

则τ=ξ_{Ψ_t}。

证明设B中任意两个元素α, α′, 则有

$\begin{array}{l} α \approx α^{'} (τ), i f f [α]_{τ} = [α^{'}]_{τ}, i f f s_{τ} (α) = s_{τ} (α^{'}) ‚ \\ i f f α \approx α^{'} (ξ_{Ψ_{t}}) ‚ \end{array}$ $\begin{array}{l} α \approx α^{'} (τ), i f f [α]_{τ} = [α^{'}]_{τ}, i f f s_{τ} (α) = s_{τ} (α^{'}) ‚ \\ i f f α \approx α^{'} (ξ_{Ψ_{t}}) ‚ \end{array}$

从而τ=ξ_{Ψ_t}。

定理16 设 (B, S) 和 (C, S) 是2个粗糙分类代数, 且φ∶B→C是从 (B, S) 到 (C, S) 的一个同态映射, 令

$\begin{array}{l} τ_{φ} ∶ α \approx β (τ_{φ}), i f f φ (α) = φ (β), α, β \in B ‚ 则 \\ ψ ∶ (B / τ_{φ}, S) \to (C, S), [α]_{τ_{φ}} \to φ (α), \forall α \in B \end{array}$ $\begin{array}{l} τ_{φ} ∶ α \approx β (τ_{φ}), i f f φ (α) = φ (β), α, β \in B ‚ 则 \\ ψ ∶ (B / τ_{φ}, S) \to (C, S), [α]_{τ_{φ}} \to φ (α), \forall α \in B \end{array}$

是同构映射。

证明显然, ψ是一一到上的映射。设s′∈S, 若n=0, s′是0元运算, 则s′是B中一个指定元素α₀, 于是β₀=φ (α₀) 也是B中一个指定0元运算s′。

若n>0, 设B/τ_φ中任意n个元素是[α₁]_{τ_φ}, [α₂]_{τ_φ} , …, [α_n]_{τ_φ}, 则有

$\begin{array}{l} ψ (s^{'} ([α_{1}]_{τ_{φ}} ‚ \dots ‚ [α_{n}]_{τ_{φ}})) = \\ φ (s^{'} ([α_{1}]_{τ_{φ}}, \dots ‚ [α_{n}]_{τ_{φ}})) = \\ s^{'} (φ (α_{1}), \dots, φ (α_{n})) = \\ s^{'} (ψ ([α_{1}]_{τ_{φ}}), \dots, ψ ([α_{n}]_{τ_{φ}})) 。 \end{array}$ $\begin{array}{l} ψ (s^{'} ([α_{1}]_{τ_{φ}} ‚ \dots ‚ [α_{n}]_{τ_{φ}})) = \\ φ (s^{'} ([α_{1}]_{τ_{φ}}, \dots ‚ [α_{n}]_{τ_{φ}})) = \\ s^{'} (φ (α_{1}), \dots, φ (α_{n})) = \\ s^{'} (ψ ([α_{1}]_{τ_{φ}}), \dots, ψ ([α_{n}]_{τ_{φ}})) 。 \end{array}$

故ψ是同构映射。

定理17 设φ∶B→C是 (B, S) 到 (C, S) 上的同态映射, 若λ∈POR (C) , 则

$\begin{array}{l} ψ ∶ (B / t_{φ, λ}, S) \to (C / s, S), [α]_{τ_{φ ‚ λ}} \to \\ [φ (α)]_{λ}, \forall α \in B 。 \end{array}$ $\begin{array}{l} ψ ∶ (B / t_{φ, λ}, S) \to (C / s, S), [α]_{τ_{φ ‚ λ}} \to \\ [φ (α)]_{λ}, \forall α \in B 。 \end{array}$

证明类似定理16的证明方法, (略) 。

定义31 设H= (B/τ, S) , 若B₁⊆B, τ₁∈POR (B) , 且有μ∶B₁/τ₁→B/τ, [α]_τ₁→[α]_τ, 则称μ是一个单射同态映射。

定理18 设R= (B, S) , 若H= (B/τ, S) , 且τ∈POR (R) , 则

PRF (R/τ) ≤PRF (R) 。

证明若τ₁∈POR (R/τ) , 令τ₁诱导R上的一个协议关系ε₁∶α≈α′ (ε₁) , iff [α]_τ≈[α′]_τ (τ₁) , 则τ⊆ε₁, 且ε₁∈POR (R) 。

若τ₁, τ₂∈POR (R/τ) , 且τ₁≠τ₂, 设 ([α]_τ, [α′]_τ) ∈τ₁, 且 ([α]_τ, [α′]_τ) ∉τ₂, 于是αα′ (ε₂) , 则ε₁≠ε₂, 于是有一个单射同态映射

$\begin{array}{l} μ ∶ Ρ Ο R (R / τ) \to Ρ Ο R (R), τ_{1} \to ε_{1} 。于是 \\ | Ρ Ο R (R / τ) | \leq | Ρ Ο R (R) | 。 \end{array}$ $\begin{array}{l} μ ∶ Ρ Ο R (R / τ) \to Ρ Ο R (R), τ_{1} \to ε_{1} 。于是 \\ | Ρ Ο R (R / τ) | \leq | Ρ Ο R (R) | 。 \end{array}$

由定义23知

$\begin{array}{l} Ρ R F (R) = | Ρ Ο R (R) | ‚ \\ Ρ R F (R / τ) = | Ρ Ο R (R / τ) | ‚ \end{array}$ $\begin{array}{l} Ρ R F (R) = | Ρ Ο R (R) | ‚ \\ Ρ R F (R / τ) = | Ρ Ο R (R / τ) | ‚ \end{array}$

从而得 PRF (R/τ) ≤PRF (R) 。

推论2 RQF (H) ≤PRF (H) 。 (证明略)

定理19 协议关系上的粗糙商代数的运算结果, 具有分类意义。

证明由性质1、性质2、定义16和定义 28可知, (略) 。

这种用协议关系刻画粗糙商代数, 事实上是协议关系在粗糙分类代数上的一个重要应用。

《6 协议关系定义的粗糙子代数》

6 协议关系定义的粗糙子代数

定义32 设上近似粗代数U= (A_u (X) , S) , U∈PRC, 下近似粗代数D= (A_d (X) , S) , 若

A_d (X) ⊆A_u (X) , 且A_d (X) ≠〉,

则称A_d (X) 是U的一个粗糙子代数, 或称A_d (X) 是A_u (X) 的一个粗糙子代数。

定理20 设U= (A_u (X) , S) ∈PRC, A_d (X) ≠〉, 且A_d (X) ⊆A_u (X) , s∈S, 则A_d (X) 是A_u (X) 的一个粗糙子代数的充要条件是, A_d (X) 对U中的s={*}是封闭的。 (证明略)

定理21 设U= (A_u (X) , S) , D= (A_d (X) , S) , 其中A_d (X) 是U的一个粗糙子代数, 若A_u (X) 上一个等价关系δ∈POR (U) , 令A_d (X) 上的一个协议关系ω, 使

$\begin{array}{l} ω : α_{1} \approx α_{2} (ω), i f f α_{1} \approx α_{2} (δ), \\ α_{1}, α_{2} \in A_{d} (X) ‚ \end{array}$ $\begin{array}{l} ω : α_{1} \approx α_{2} (ω), i f f α_{1} \approx α_{2} (δ), \\ α_{1}, α_{2} \in A_{d} (X) ‚ \end{array}$

则ω∈POR (D) 。

证明对A_d (X) , 满足性质1, (略) 。

定义33 对于U= (A_u (X) , S) , 且A_d (X) ⊆A_u (X) , 由A_u (X) 的每一子集构成的集称为幂集, 记作POW (A_u (X) ) 。

定义34 对于U= (A_u (X) , S) , 由U生成的所有粗糙子代数集, 记作RSS (U) , 形如

$R S S (U) = {A_{d} (X) | A_{d} (X) \in Ρ Ο W (A_{u} (X))} ‚$ $R S S (U) = {A_{d} (X) | A_{d} (X) \in Ρ Ο W (A_{u} (X))} ‚$

且称|RSS (U) |为RSS (U) 的基数。

原则5 (非空原则) RSS (U) ≠〉。

定理22 设〉≠U∈R, 则RSS (U) ⊆POW (A_u (X) ) 。 (证明略)

定义35 一个粗糙子代数集函数

$R S F : Ρ R C \to C Ν C, U \to | R S S (U) | ‚$ $R S F : Ρ R C \to C Ν C, U \to | R S S (U) | ‚$

且RSF (U) 称为U的粗糙子代数集度数。

引理1 设U= (A_u (X) , S) ∈PRC, 使

$R S F (U) = 2^{R S S (U)} 。$ $R S F (U) = 2^{R S S (U)} 。$

证明设N={0, 1, 2, …, n, …}_n<J, 其中J为一个序数, 且S={*}, 若m*n=0, ∀m, n∈N, 对任意一个A_d (X) ⊆N⁺={1, 2, …, n, …}_n<J, 由于

$\begin{array}{l} A_{d} (X) \cup {0} \in R S S (U) ‚ 于是 \\ | R S S (U) | = | 2^{Ν} | = 2^{R S S (U)} ‚ 由于 \\ R S F (U) = | R S S (U) | ‚ \end{array}$ $\begin{array}{l} A_{d} (X) \cup {0} \in R S S (U) ‚ 于是 \\ | R S S (U) | = | 2^{Ν} | = 2^{R S S (U)} ‚ 由于 \\ R S F (U) = | R S S (U) | ‚ \end{array}$

故RSF (U) =2^{RSS (U)}。

定理23 设U∈PRC, 使

$0 ＜ R S F (U) \leq 2^{R S S (U)} 。$ $0 ＜ R S F (U) \leq 2^{R S S (U)} 。$

证明由原则5, 定理22和引理1可知, (略) 。

对于R, 有下列3种情形:

情形3 (R_c定义) 设R= (B, S) , 若任何一个非空粗糙子集和它们的运算作成R的粗糙子代数, 则称R为紧粗糙子代数 (compact rough subalgebra) , 记作R_c。

情形4 (R_i定义) 设R= (B, S) , A_u (X) , A_d (X) ∈R, 若A_u (X) =A_d (X) , 或A_d (X) ={r} (表示单元素集) , 则称 (A_d (X) , S) 为R的同一粗糙子代数 (rough subalgebra of identity) , 记作R_i。

情形5 (R_ci定义) 设R= (B, S) , 若R_c都是R_i, 则R称为紧同一粗糙子代数 (rough subalgebra of compact identity) , 记为R_ci。

定义36 设R= (B, S) ∈PRC, 〉≠E⊆B, 若E生成一个粗糙子代数I_E, 且E⊆I_E, 称I_E是R包含E的最小粗糙子代数, 记作min (I_E) 。若I_E={i}, i∈B, 则min ({i}) =min (i) 。

定义37 一个粗糙子代数的基数函数SBF SBF∶PRC→CNC, R→inf {|D||D∈RSS (U) }, 且SBF (U) 称为U的粗糙子代数下确界度数。

定理24 设U= (A_u (X) , S) ∈SBF, 则有

$\begin{array}{l} S B F (U) = \inf {| \min (Ι_{E}) | 〉 \neq Ι_{E} \subseteq A_{u} (X)} = \\ \inf {| \min (i) | | i \in A_{u} (X)} 。 \end{array}$ $\begin{array}{l} S B F (U) = \inf {| \min (Ι_{E}) | 〉 \neq Ι_{E} \subseteq A_{u} (X)} = \\ \inf {| \min (i) | | i \in A_{u} (X)} 。 \end{array}$

证明设n, m是2个粗糙子代数的下确界度数, 若令

$\begin{array}{l} n = \inf {| \min (Ι_{E}) | | 〉 \neq Ι_{E} \subseteq A_{u} (X)} ‚ \\ m = \inf {| \min (i) | | i \in A_{u} (X)} ‚ 则有 \\ {| \min (i) | | i \in A_{u} (X)} \subseteq \\ \inf {| \min (Ι_{E}) | | 〉 \neq Ι_{E} \subseteq \\ A_{u} (X)} \subseteq R S S (U) ‚ 于是 \\ S B F (U) \leq n \leq m 。 \end{array}$ $\begin{array}{l} n = \inf {| \min (Ι_{E}) | | 〉 \neq Ι_{E} \subseteq A_{u} (X)} ‚ \\ m = \inf {| \min (i) | | i \in A_{u} (X)} ‚ 则有 \\ {| \min (i) | | i \in A_{u} (X)} \subseteq \\ \inf {| \min (Ι_{E}) | | 〉 \neq Ι_{E} \subseteq \\ A_{u} (X)} \subseteq R S S (U) ‚ 于是 \\ S B F (U) \leq n \leq m 。 \end{array}$

再设C是U的任一粗糙子代数, 若C≠〉, 于是i∈C, 从而{i}⊆C, 因C是包含{i}的一个粗糙子代数, 则有min (I_E) ⊆C, 于是

$\begin{array}{l} | \min (i) | \leq | C | ‚ 由于 \\ m = \inf {| \min (j) | | j \in A_{u} (X)} ‚ 且 \\ m \leq | \min (i) | \leq | C | ‚ \end{array}$ $\begin{array}{l} | \min (i) | \leq | C | ‚ 由于 \\ m = \inf {| \min (j) | | j \in A_{u} (X)} ‚ 且 \\ m \leq | \min (i) | \leq | C | ‚ \end{array}$

从而m≤SBF (U) 。

综上, 得到 n=m=SBF (U) 。

定理25 设U= (A_u (X) , S) , D= (A_d (X) , S) , D到U的同态映射θ

$θ : A_{u} (X) \to A_{d} (X) ‚$ $θ : A_{u} (X) \to A_{d} (X) ‚$

则有下列性质:

1) 设A是D的一个粗糙子代数, 则θ (A) 是U的一个粗糙子代数, 且θ (A_d (X) ) 是U的一个粗糙子代数;

2) 设C⊆θ (A_d (X) ) ⊆A_u (X) , 若C是U的一个粗糙子代数, 则θ^-1 (C) 是D的一个粗糙子代数。若θ是满射, A_u (X) =θ (A_d (X) ) , 则U的任一粗糙子代数的原像是D的一个粗糙子代数。

证明 1) 由于〉≠θ (A_d (X) ) ⊆A_u (X) , 只证θ (A_d (X) ) 对U中所有的运算是封闭的。

若U中存在零元运算μ^-, 则D中存在对应的零元运算μ, 且θ (μ) =μ^-, 从而有μ^-∈θ (A_d (X) ) , 再考虑U中的非零元运算s∈S, 对于θ (A_d (X) ) 中的任意k个元素β₁, …, β_k, 存在

$\begin{array}{l} α_{1}, \dots, α_{k} \in A_{d} (X), 使 \\ θ (α_{j}) = β_{j}, j = 1, \dots, k 。于是 \\ s (β_{1}, \dots, β_{k}) = s (θ (α_{1}), \dots, θ (α_{k})) = \\ θ (s (α_{1}, \dots, α_{k})) \in θ (A_{d} (X)) 。 \end{array}$ $\begin{array}{l} α_{1}, \dots, α_{k} \in A_{d} (X), 使 \\ θ (α_{j}) = β_{j}, j = 1, \dots, k 。于是 \\ s (β_{1}, \dots, β_{k}) = s (θ (α_{1}), \dots, θ (α_{k})) = \\ θ (s (α_{1}, \dots, α_{k})) \in θ (A_{d} (X)) 。 \end{array}$

2) 仅考察s。

对于C中的任意k个元素β₁, …, β_k, 存在α₁, …, α_k是θ^-1 (C) 中的任意k个元素, 使θ (α_j) =β_j, j=1, …, k, 从而C是U的一个粗糙子代数有

$\begin{array}{l} θ (s (α_{1}, \dots, α_{k})) = s (θ (α_{1}), \dots, θ (α_{k})) = \\ s (β_{1}, \dots, β_{k}) \in C ‚ \end{array}$ $\begin{array}{l} θ (s (α_{1}, \dots, α_{k})) = s (θ (α_{1}), \dots, θ (α_{k})) = \\ s (β_{1}, \dots, β_{k}) \in C ‚ \end{array}$

于是 s (α₁, …, α_k) ∈θ^-1 (C) , 从而θ^-1 (C) 是D的一个粗糙子代数。

定理26 (二重性定理, 不一定定理) 设U =A_u (X, S) , 则RSS (U) 在⊆下不一定存在最小粗糙子代数。

证明 1) 先承认选择定理 ^[29], 再由半序关系粗糙集知 ^[28], 必含有极大理想元, 但不一定存在最小理想元。这里, 称U为不具有最小粗糙子代数的代数, 且记为作NMA。

2) 在定义36有意义下, 由于A_d (X) ⊆B, 则称U具有最小粗糙子代数的代数, 且记作YMA。

3) 由原则5知, RSS (U) ≠〉, 则NMA, YMA≠〉。

综上所述, 定理26具有二重性。

《7 算法和应用》

7 算法和应用

算法1 (回避-归并算法)

$/ / \begin{matrix} 有向关系图 \end{matrix} \overset{符号化}{\to} \begin{matrix} 协议关系矩阵 \end{matrix} / /$ $/ / \begin{matrix} 有向关系图 \end{matrix} \overset{符号化}{\to} \begin{matrix} 协议关系矩阵 \end{matrix} / /$

//矩阵中的W表示三个方面:1) 回避自反;2) 反对称的一种不可能的状态;3) 舍去的协议偶对。//

//矩阵中的x^←, x^→表示待定方向的偶对。若定出了方向, 则x^←或x^→置换为1。//

Step 1 扫描协议关系矩阵的最上一行, 且从左开始, 向右进行扫描:

1.1) 若发现W, 则扫描向右移;

1.2) 若发现x^←, x^→, 则根据准则1求出方向, 并在协议矩阵中置换为1, 且标记相应的协议偶对集;

1.3) 若发现1, 则标记相应的协议偶对集;

1.4) 若发现偶对集组成的集合中有重复的元素, 则等价为自身的一个元素;

1.5) 将这些集合归并到协议类中。

Step 2 扫描移向下一行, 且从左开始, 向右进行扫描:

2.1) 重复Step 1中的1.1, 1.2, 1.3;

2.2) 与Step 1的协议类进行比对, 若发现重复的元素, 则删去;

2.3) 将这些新的集合归并到协议类中, 于是得到了一个扩充的协议类。

Step 3 重复Step 2, 直到扫描完矩阵的第n行第n列的元素为止。

Step 4 从协议矩阵的第n行开始, 向上扫描, 若发现仅有一个W, 其他元素全为0, 它是一个孤立结点, 则扩充到协议类中。

Step 5 将上述得到的协议类及孤立元素合起来, 从而得到了最大协议类。

注7 协议矩阵中的符号x^←, x^→表示待定偶对集, 它对应协议关系图上弧的方向, 由反对称性知, x^←和x^→两者必居其一, 即W或1。

例4 一个协议关系有向图如图2所示。

《图4》

图2协议关系有向图

Fig.2 Protocol relation digraphs

协议关系矩阵为

《表1》

a	W	1	1	1	0	W	0
b	W	W	1	1	1	0	0
c	W	W	W	1	0	1	0
d	W	W	W	W	x^←	0	0
e	0	W	0	x^→	W	1	0
f	1	0	W	0	W	W	0
g	0	0	0	0	0	0	W
	a	b	c	d	e	f	g

1) 判断协议矩阵中x^←, x^→, 并求最大协议类;

2) 找出极小化的协议图;

3) 求协议关系矩阵的秩。

解:

1) 根据算法1 (回避-归并算法) , 运算结果:

{a, b, c, d};

{a, b, c, d}, {b, e};

{a, b, c, d}, {b, e}, {c, f};

{a, b, c, d}, {b, e}, {c, f}, x^←⇒1, {d, e};

{a, b, c, d}, {b, e}, {c, f}, {d, e}, x^→⇒W, {e, f};

{a, b, c, d}, {b, e}, {c, f}, {d, e}, {e, f}, {f, a};

{a, b, c, d}, {b, e}, {c, f}, {d, e}, {e, f}, {f, a}, {g}

为最大协议集。

2) 根据协议图不等式和准则2, 易得极小化的协议图, (略) 。

3) 根据协议类, 协议关系矩阵的秩为7。

展示更多