《1 引言》
1 引言
粗糙集理论
近似空间中的分类问题是一个基本问题, 又是一个重要的中心问题。分类虽然可以作广泛的理解, 但它受到知识认知和行为原则的限制。波兰科学院院士, 数学家Pawlak在研究近似空间时, 基于二元等价关系, 提出了粗糙集概念
值得研究的问题是关于知识的理解及分类、信息系统的智能处理等问题, 在一定意义下, 都涉及一致性问题以及协议关系问题。更确切地说, 是粗糙集与条件属性的关系、信息系统 (或知识库) 与基于协议关系的粗糙分类代数的关系、知识分类的协议性等问题;上近似集与下近似集的关系构成一种代数结构的问题。
笔者引进了广义近似空间概念, 涉及量子逻辑分类、对策分类等;给出了有关的公理、原则, 提出并证明了几个定理, 还提出了一个猜想, 引进了一种新的空间, 展示了一些新观点, 讨论了集合元素 (或知识元) 间存在一种特殊性质的关系, 即代数的协议关系。实际上协议关系是代数结构的一种关系。笔者从选择公理和良序定理出发
《2 广义近似空间的基本理论》
2 广义近似空间的基本理论
设U<∞, U是论域, 近似空间是偶对 (U, R) , 其中R是U上的非空集合关系, 称为Pawlak近似空间。对于X⊆U定义2个子集:
上近似集:Au (X) ={X∈U| R (X) ∩X≠〉};
下近似集:Ad (X) ={X∈U|R (X) ⊆X}。
定义1 粗糙集R (X) 满足下列条件:
1) Au (X) , Ad (X) ≠〉;
2) Au (X) ∪Ad (X) ∈R (X) ;
3) 若α∈Au (X) , β∈Ad (X) , 则β<α。
对于粗糙集偶对 (Au (X) , Ad (X) ) , 称为R (X) 的极限分类, Au (X) 称为这个极限分类上近似集, Ad (X) 称为它的下近似集。
公理1 (粗近似公理) 对Pawlak近似空间 (U, R) 中的Au (X) 和Ad (X) , 下列4种情况, 必有一种情况发生:
1) Au (X) >Ad (X) ;2) Au (X) =Ad (X) ;
3) Au (X) <Ad (X) ;4) Au (X) ‖Ad (X) 。
其中“‖”表示不可比较关系。
原则1 (粗糙集的分类原则) Pawlak近似空间 (U, R) , 对于定义1, 存在粗糙集R (X) , 称为Au (X) 与Ad (X) 的无序对集合, 记为{Au (X) , Ad (X) };称为Au (X) 与Ad (X) 有序对集合, 记为{Au (X) , {Au (X) , Ad (X) }}。
原则2 (粗选原则) 对于Pawlak近似空间 (U, R) , 有下列原则:
1) 若选公理1中的Au (X) =Ad (X) , 则记为{Au (X) }, 即为近似对象Au (X) 的单元粗糙集合, 意味着含一个元素Au (X) , 称R (X) 为退化了的不可测粗糙集。
2) 若选公理1中的Au (X) ‖Ad (X) , 有
则称S (X) 为不可比较集或称互补集, 意味着上近似集与下近似集之间存在平行的真实关系, 即互补关系, 用图1的格图表示。
规定:0≤Au (X) ≤1;0≤Ad (X) ≤1, 则子格〈{1, Au (X) , 0}, ≤〉和子格〈{1, Ad (X) , 0}, ≤〉是U上的2个子格, 图1中虚线表示Au (X) 将U中的元素划分为2类。
为了表明不同概念在对策意义下的一致性, 引入对策分类定义。
定义2 设 (Au (X) , Ad (X) ) 是一个极限分类, 记为R (X) , 若存在平衡偶对 (min Au (X) , max Ad (X) ) 则称为对策分类, 记为K (X) 。
定义3 粗糙集R (X) 的bit空间集记为Rbit (X) , 它的空间 (U, Rbit) 由范数导出, 即
所形成的Banach空间记为Lb (U, R, Rbit) 。
定义4 (Au (X) , Ad (X) , S (X) ) 称为广义近似空间U的量子逻辑分类, 记为QU (X) , 其中S (X) 是基于半序关系的不确定集。
注1 Pawlak粗糙集的上近似集与下近似集是一种特殊情况下的分类。近似空间中粗糙集格性质的量子分类
定义5 设Au (X) , S (X) 是U上的2个等价关系。当 (a, b) ∈S (X) 时, 必有 (a, b) ∈Au (X) , 则称S (X) 确定的分类比Au (X) 确定的分类精细。
定义6 (Au (X) , S (X) ) 称为上投影分类, 记为Pu (X) ; (Ad (X) , S (X) ) 称为下投影分类, 记为Pd (X) 。
公理2 (干扰集公理) 广义近似空间 (U, R, S) 中, 存在U上的半序关系干扰集, 记为I (X) , 形如
对于定义3, 下列3种情况, 必有1种情况发生:
1) Rbit (X) <I (X) ;
2) Rbit (X) ≌I (X) ;
3) Rbit (X) >I (X) 。
其中 “≌”表示同构关系。
原则3 (不确定的偶集原则) 对于广义近似空间 (U, R, S) , 存在着Rbit (X) 与I (X) 的不确定偶集, 记为Ψ (X) , 即{Rbit (X) , I (X) }, 有
Ψ (X) ={X∈U|I (X) ∩X≠〉}。
原则4 (精选原则) 对不确定干扰集I (X) , 有下列原则:
1) 若选公理2中的Rbit (X) ≌I (X) , 则为定义3的bit空间集, 或称bit量子集, 记为{Rbit (X) };
2) 若选公理2中的Rbit (X) >I (X) , 则为广义近似空间的隐bit量子集, 记为{Rbit- (X) };
3) 若选公理2中的Rbit (X) <I (X) , 则为广义近似空间的显bit量子集, 记为{Rbit+ (X) }。
定义7 对于广义近似空间的bit空间集合 (U, Rbit) , x∈Rbit (X) , (Rbit- (X) , Rbit+ (X) ) 称为bit量子对称分类, 记为Y (X) 。
定义8 (Rbit- (X) , Rbit+ (X) , I (X) ) 称为广义近似空间的bit量子逻辑分类, 记为Tbit (X) , 其中I (X) 是基于半序关系的干扰集。
关于广义近似空间理论的上近似集元素的数目临界问题, 有下面定理:
定理1 (临界定理) 若Aui (X) ∩Auj (X) ≠〉, Aui (X) ∪Auj (X) ≠Au (X) , i≠j, Au (X) ={Au1 (X) , Au2 (X) , …, Aus (X) }, 1≤i, j≤s, 则
证明 设补集为A′u (X) ={A′u1 (X) , A′u2 (X) , …, A′us (X) }, 考虑Au (X) 。由于
Aui (X) ∩Auj (X) ≠〉, 于是
Aui (X) ⊈A′uj (X) , 且Aui (X) ⊉A′uj (X) , 得
Aui (X) ∩A′uj (X) ≠〉;由于
Aui (X) ∪Auj (X) ≠N, N={1, 2, …, n}, 于是
A′ui (X) ∩A′uj (X) ≠〉。
Au (X) 是n元集N的子集, 且{Au (X) , A′u (X) }分为2个集, Au (X) 中的集元数均≤n/2, 并且当|Aui (X) | =n/2时, Aui (X) 与A′ui (X) 仅有一个在Au (X) 中, |Aui (X) |≤k≤n/2, Aui (X) 可用每两个互补的k元集代替, 当|Aui (X) |=k, 有
显然, 当|Aui (X) |递增, C
∑1/C
其中Aui (X) ≤[n/2], 于是有
C
从而Au (X) 中的子集恰有s个, 即得s≤C
注2 从定理1可以看出, 广义近似空间的上近似集元素s的临界是可预测的。
定理2
定理3 对于广义近似空间, R (X) 中的任何量子对称分类N (X) , 都有N (X) ⊆QU (X) 成立。
证明 设N (X) 是任何分类, 当x∈N (X) , 且x∈Rbit (X) , 必有x的bit量子对称分类Y (X) , 使
Y (X) ⊆N (X) ⊆R (X) ,
由于x∈QU (X) , R (X) ⊆QU (X) , 于是得N (X) ⊆QU (X) 。证毕。
定理4 对于广义近似空间 (U, R, S) , R (X) 成为Tbit (X) 的充分必要条件:
证明 当Au (X) <I (X) , 由公理2和原理2, 生成
同理, 生成
{Ad (X) }≌{Rbit- (X) , I (X) }。
反之, 若
(Au (X) , Ad (X) ) ≌ (Rbit+ (X) , Rbit- (X) , I (X) ) ,
根据定理3, 在bit量子逻辑意义下, 则有
易推得Au (X) <I (X) <Ad (X) 成立。
猜想 设广义近似空间 (U, R, S) , 若存在干扰集I (X) , 则有
Ik (X) 中两两互不可比, 即Ii (X) ‖Ij (X) , i≠j。
新观点:
1) 相信的程度与知识分类的原则无关;
2) 知识是一种逻辑, 如量子逻辑;
3) 知识的所有近似描述组成的集, 称为知识的广义近似空间。对知识的分类就是广义近似空间的一个子集;
4) 知识的发现量可以用映射来表示。
《3 粗糙分类代数概念》
3 粗糙分类代数概念
定义9 设粗糙分类代数是一个对生 (opposite) R= (B, S) , 其中B是一个非空粗糙集构成的集合族, ∀A∈B, 称A是粗糙分类代数R的基集, S≠〉, ∀s∈S,
其中Ai1, Ai2, …, Ain, Ai∈B, n∈N, 称S是B上有限元运算的一个集合。
定理5 定义9中的S集可良序。
证明 由于每一个集合都是可以良序的
定理6 对于定义9中的集合S, S的基数
证明 1) 基数ωs有意义, 表明存在某个基数O, 使ωs与O等势, 记为EP (ωs, O) , 于是ωs=O, 设S集可良序, 且存在保序双射f∶S→O, 于是存在O到ωs的保序双射g∶O→ωs, O可良序, 从而诱导了ωs成为良序;
2) 若构造序数ωs的良序成为良序集, 在相同序结构的意义下, 则可推导出与ωs等势的最小序数
注3 定理6意味着, 可用与基数等势的方式计算ωs的元素个数。R= (B, S) 中的S为良序, 记作S={s0, s1, s2, …, si, …}, i<J, 其中J为一个序数。这样, S与J建立了一个同构对应, 从而建立S上的良序关系<s。
定义10 设R= (B, S) , 若si是ni元运算, 则称R为On型, 即
称J为On型的阶。
注4 对于定义10, 在一定意义下, ni=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+是非零正整数集, 若对非零协议数τ, 使
则称α协议于β, 记作α≈β (τ) 。
协议式 α与β是协议关系, α协议于β是由协议数τ诱导的结果。协议式为
定义14 设≈是集合B上的一个二元关系, ∀α, β∈B, τ是协议数, 若协议式满足
若α≤β且β≤α, 则蕴含
则称≈是B的一个协议关系。
注5 与半序关系比较, 协议关系是更为普遍的二元关系。显然, 所有半序关系都是协议关系。因此, 协议概念是半序概念的一种推广。
定义15 设≈是集合B上的一个二元关系, ∀a, b, c∈B, τ是协议数, 若协议式满足
则称≈是协议循环关系。
性质1 (置换性) 设R= (B, S) 为On型, 若对任意的x<On, Sx∈S, 且αi, βi∈B, ωs是B上的一个等价关系, 有
则称ωs为R上的一个协议关系。
性质2 (存在性) 对于任意的协议分类代数R, 若存在性质1 (置换性) , 则存在协议关系≈。
定义16 设R= (B, S) , 若协议关系≈对R中所有的运算都符合性质1和性质2, 则称≈是R上的协议关系, 且称B中关于≈的类为R上的协议类, 记作[α], 其中α1, α2, …, αn∈B, 称α为协议类[α]的代表元素。
定义17 设R= (B, S) , 若δ是粗集B上的一个等价关系, 且满足性质1, 则称δ为R上的一个协议关系。
对于定义17, 有下面2种情形:
情形1 (δⅠ定义) 设R= (B, S) , 若二元关系δⅠ是B上的一个等价关系, α与β对δⅠ的协议式定义为
如果满足性质1, 则称δⅠ是B上的一个完备协议关系。
情形2 (δⅡ定义) 设R = (B, S) , 若二元关系δⅡ是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的一个代数, 记作RG= (B, S, G) 。
注7 对于定义21, RG是粗糙分类代数结构中的一种情形。
例1 关系集G=POR (R) 。
例2 设R = (Ls, ∨, ∧) 是一个任意的粗糙格
则“≤”是定义9中B上的一个半序关系, R是“≤”的一个序代数R≤= (Ls, ∨, ∧, ≤) 。
定义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上有一个二元关系:
则ξψ, λ∈POR (R) , 称ξψ, λ是λ受ψ诱导的协议关系。
证明 显然, ξψ, λ是一个等价关系, 根据性质1和定义17可以证明定理8成立, (略) 。
例3 设ψ∶B→C是从 (B, S) 到 (C, S) 的一个同态映射, 运用情形1 (δⅠ定义) 给出δB或δC, 则
证明 设B中的任意元素α和α′, 根据定理8, 有
又从δC定义知
于是有
故ξΨ, δC=δB。
定理9 设ψ∶B→C是从 (B, S) 到 (C, S) 的一个同态映射, φ∶C→D是从 (C, S) 到 (D, S) 中一个同态映射。若
则hψ, hφ, d=
《图2》

证 设α, β∈B, 根据性质1, 则有
从而得hψ, hφ, d=
《图3》

定义24 设≈是集合A的一个协议关系, 令B⊆A, 任一αi∈B, i=1, 2, …, n, 若
则称B为≈的一个最大协议类。
定义25 若协议类个数有限, 则τ的不同协议类的个数称为τ的秩, 否则秩为无限。
定理10 设τ是非空有限集合A上的协议关系, 若B是一个协议类, 则存在一个最大协议类BP, 使B⊆BP。
证明 设A={α1, …, αn}, 构造协议类的序列:
B0⊆B1⊆B2⊆…,
使B0=B1, Bi+1=B∪{αj}, 且满足αj∈/Bi, 于是αj与Bj中各元素有≈关系的最小下标, 由于|A|=n, 从而至多经过n-|B|步就会停止, 且序列中的最后一个协议类为BP, 证毕。
定理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的完全协议覆盖, 记作BP (A) 。
定理12 对定义27, BP (A) 是惟一的。 (证明略)
推论1 设非空有限集合A, 非空最大协议类BP, 有BP={A1, …, An}, 若
则BP是A的协议覆盖。 (证明略)
注4 对推论1的反问, 即构造A的协议覆盖, 未必需要最大协议类。
《5 协议关系定义的粗糙商代数》
5 协议关系定义的粗糙商代数
基于定义9来考虑一类特殊的粗糙代数——具有协议关系的粗糙商代数。
定义28 设粗糙分类代数 (B, ·) 及其上的协议关系的粗糙商集上的运算“*”, 对任一[B1]τ, [B2]τ∈R/τ, 有
其中, B1, B2∈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) , 令
且sx∈S, 令
则R/τ≈ (B/τ, S) 称为R的一个粗糙商代数H, 且它是由τ生成的粗糙商代数。
证明 设αi≈βi (τ) , αi, βi∈B, 0≤i≤nx, 由于τ∈POR (R) , 有
这样, 保证sx的每一个运算都受协议关系τ的诱导, 从而H=R/τ≈ (B/τ, S) 。
定理14 设R= (B, S) , 若τ∈POR (R) , 令一个同态映射
则ψτ: (B, S) → (B/τ, S) , α→[α]τ。
证明 设α0, …, αnx-1∈B, sx∈S, 于是有
这样, 保证sx的每一个运算都受到协议关系的诱导, 从而定理成立, 证毕。
定理15 设H= (B/τ, S) , 若τ∈POR (R) , 而B中有一个协议关系, 记作ξΨt。令
则τ=ξΨt。
证明 设B中任意两个元素α, α′, 则有
从而τ=ξΨt。
定理16 设 (B, S) 和 (C, S) 是2个粗糙分类代数, 且φ∶B→C是从 (B, S) 到 (C, S) 的一个同态映射, 令
是同构映射。
证明 显然, ψ是一一到上的映射。设s′∈S, 若n=0, s′是0元运算, 则s′是B中一个指定元素α0, 于是β0=φ (α0) 也是B中一个指定0元运算s′。
若n>0, 设B/τφ中任意n个元素是[α1]τφ, [α2]τφ , …, [αn]τφ, 则有
故ψ是同构映射。
定理17 设φ∶B→C是 (B, S) 到 (C, S) 上的同态映射, 若λ∈POR (C) , 则
证明 类似定理16的证明方法, (略) 。
定义31 设H= (B/τ, S) , 若B1⊆B, τ1∈POR (B) , 且有μ∶B1/τ1→B/τ, [α]τ1→[α]τ, 则称μ是一个单射同态映射。
定理18 设R= (B, S) , 若H= (B/τ, S) , 且τ∈POR (R) , 则
PRF (R/τ) ≤PRF (R) 。
证明 若τ1∈POR (R/τ) , 令τ1诱导R上的一个协议关系ε1∶α≈α′ (ε1) , iff [α]τ≈[α′]τ (τ1) , 则τ⊆ε1, 且ε1∈POR (R) 。
若τ1, τ2∈POR (R/τ) , 且τ1≠τ2, 设 ([α]τ, [α′]τ) ∈τ1, 且 ([α]τ, [α′]τ) ∉τ2, 于是αα′ (ε2) , 则ε1≠ε2, 于是有一个单射同态映射
由定义23知
从而得 PRF (R/τ) ≤PRF (R) 。
推论2 RQF (H) ≤PRF (H) 。 (证明略)
定理19 协议关系上的粗糙商代数的运算结果, 具有分类意义。
证明 由性质1、性质2、定义16和定义 28可知, (略) 。
这种用协议关系刻画粗糙商代数, 事实上是协议关系在粗糙分类代数上的一个重要应用。
《6 协议关系定义的粗糙子代数》
6 协议关系定义的粗糙子代数
定义32 设上近似粗代数U= (Au (X) , S) , U∈PRC, 下近似粗代数D= (Ad (X) , S) , 若
Ad (X) ⊆Au (X) , 且Ad (X) ≠〉,
则称Ad (X) 是U的一个粗糙子代数, 或称Ad (X) 是Au (X) 的一个粗糙子代数。
定理20 设U= (Au (X) , S) ∈PRC, Ad (X) ≠〉, 且Ad (X) ⊆Au (X) , s∈S, 则Ad (X) 是Au (X) 的一个粗糙子代数的充要条件是, Ad (X) 对U中的s={*}是封闭的。 (证明略)
定理21 设U= (Au (X) , S) , D= (Ad (X) , S) , 其中Ad (X) 是U的一个粗糙子代数, 若Au (X) 上一个等价关系δ∈POR (U) , 令Ad (X) 上的一个协议关系ω, 使
则ω∈POR (D) 。
证明 对Ad (X) , 满足性质1, (略) 。
定义33 对于U= (Au (X) , S) , 且Ad (X) ⊆Au (X) , 由Au (X) 的每一子集构成的集称为幂集, 记作POW (Au (X) ) 。
定义34 对于U= (Au (X) , S) , 由U生成的所有粗糙子代数集, 记作RSS (U) , 形如
且称|RSS (U) |为RSS (U) 的基数。
原则5 (非空原则) RSS (U) ≠〉。
定理22 设〉≠U∈R, 则RSS (U) ⊆POW (Au (X) ) 。 (证明略)
定义35 一个粗糙子代数集函数
且RSF (U) 称为U的粗糙子代数集度数。
引理1 设U= (Au (X) , S) ∈PRC, 使
证明 设N={0, 1, 2, …, n, …}n<J, 其中J为一个序数, 且S={*}, 若m*n=0, ∀m, n∈N, 对任意一个Ad (X) ⊆N+={1, 2, …, n, …}n<J, 由于
故RSF (U) =2RSS (U) 。
定理23 设U∈PRC, 使
证明 由原则5, 定理22和引理1可知, (略) 。
对于R, 有下列3种情形:
情形3 (Rc定义) 设R= (B, S) , 若任何一个非空粗糙子集和它们的运算作成R的粗糙子代数, 则称R为紧粗糙子代数 (compact rough subalgebra) , 记作Rc。
情形4 (Ri定义) 设R= (B, S) , Au (X) , Ad (X) ∈R, 若Au (X) =Ad (X) , 或Ad (X) ={r} (表示单元素集) , 则称 (Ad (X) , S) 为R的同一粗糙子代数 (rough subalgebra of identity) , 记作Ri。
情形5 (Rci定义) 设R= (B, S) , 若Rc都是Ri, 则R称为紧同一粗糙子代数 (rough subalgebra of compact identity) , 记为Rci。
定义36 设R= (B, S) ∈PRC, 〉≠E⊆B, 若E生成一个粗糙子代数IE, 且E⊆IE, 称IE是R包含E的最小粗糙子代数, 记作min (IE) 。若IE={i}, i∈B, 则min ({i}) =min (i) 。
定义37 一个粗糙子代数的基数函数SBF SBF∶PRC→CNC, R→inf {|D||D∈RSS (U) }, 且SBF (U) 称为U的粗糙子代数下确界度数。
定理24 设U= (Au (X) , S) ∈SBF, 则有
证明 设n, m是2个粗糙子代数的下确界度数, 若令
再设C是U的任一粗糙子代数, 若C≠〉, 于是i∈C, 从而{i}⊆C, 因C是包含{i}的一个粗糙子代数, 则有min (IE) ⊆C, 于是
从而m≤SBF (U) 。
综上, 得到 n=m=SBF (U) 。
定理25 设U= (Au (X) , S) , D= (Ad (X) , S) , D到U的同态映射θ
则有下列性质:
1) 设A是D的一个粗糙子代数, 则θ (A) 是U的一个粗糙子代数, 且θ (Ad (X) ) 是U的一个粗糙子代数;
2) 设C⊆θ (Ad (X) ) ⊆Au (X) , 若C是U的一个粗糙子代数, 则θ-1 (C) 是D的一个粗糙子代数。若θ是满射, Au (X) =θ (Ad (X) ) , 则U的任一粗糙子代数的原像是D的一个粗糙子代数。
证明 1) 由于〉≠θ (Ad (X) ) ⊆Au (X) , 只证θ (Ad (X) ) 对U中所有的运算是封闭的。
若U中存在零元运算μ-, 则D中存在对应的零元运算μ, 且θ (μ) =μ-, 从而有μ-∈θ (Ad (X) ) , 再考虑U中的非零元运算s∈S, 对于θ (Ad (X) ) 中的任意k个元素β1, …, βk, 存在
2) 仅考察s。
对于C中的任意k个元素β1, …, βk, 存在α1, …, αk是θ-1 (C) 中的任意k个元素, 使θ (αj) =βj, j=1, …, k, 从而C是U的一个粗糙子代数有
于是 s (α1, …, αk) ∈θ-1 (C) , 从而θ-1 (C) 是D的一个粗糙子代数。
定理26 (二重性定理, 不一定定理) 设U =Au (X, S) , 则RSS (U) 在⊆下不一定存在最小粗糙子代数。
2) 在定义36有意义下, 由于Ad (X) ⊆B, 则称U具有最小粗糙子代数的代数, 且记作YMA。
3) 由原则5知, RSS (U) ≠〉, 则NMA, YMA≠〉。
综上所述, 定理26具有二重性。
《7 算法和应用》
7 算法和应用
算法1 (回避-归并算法)
//矩阵中的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所示。
协议关系矩阵为
《表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。