第2期 胡霞，等：集族等价与基于粒的下近似算子研究 ·329· 证明 1)初始化，minimal(C)=O,将集族c中的元素按 1)如果C是C-{C的可约元，则C可以用 基数从小到大排序： C-{C,C'中若干个元之并表示出来，那么当然也可 2)基数最小的元素一定是极小元，设其基数为 表示成C-{C)中若干个元之并，因此C是C的可 i,将其从集族c中移除并加人极小元集合minimal(C: 约元。 3)=+1: 2)反之，如果C是C的可约元，则C可用 4)如果集族C中已没有基数大于等于i的元 C-{C}中的若干元C1,C2,…,Cn表示出来。如果C, 素，则转5)，如果集族C中元素的基数均大于i,则 都有C:≠C,则C已经用C-{C中的若干个不等于 转3)：否则逐个检测基数为i的元素，如果任何一个 C的元之并表示出来了，因此C是C-{C的可约元。 极小元均不是它的真子集，则它是极小元，将其从 要是其中有一个元等于C,不妨设为C,由于C是 集族C中移除并加入极小元集合minimal(C),转3)： C中的可约元，于是C可以表示成C-{C的若干元 5)算法结束，minimal(C)即为所求。 D,D2,,Dm的并。于是，C'=C1UC2UUCn=DU 2.2 由极小元再求集族的非极小既约元 D2 J...UD.uc2U…UCn,其中D,D2,…,Dm,C2,… 算法2求集族的非极小既约元。 Cn既不等于C,也不等于C',这样证明了C是C-{C 输入算法I结束时所得的集族c及minimal(C: 中的可约元。 输出非极小既约元的集合irreducible(C)。 由命题(1)、(2)得证。 I)初始化，irreducible(C=O; 由定理1和定理2可以得出，在一个集族中删 2)逐个扫描集族c的元素C,找出minimal(C)中 除其中的一个可约元，并不会改变其余元素是既约 每一个满足条件mccC的极小元mC; 元还是可约元的性态。由此，我们可以逐个删除集 3)如果C≠UmC,则C是一个既约元，加入集 族中的所有可约元，只剩下既约元。 合irreducible(C); 定义2设C是论域U上的一个集族，如果C中 4)算法结束，irreducible(C)即为所求。 的每一个元都是既约元，则称C是约简的。否则，称 最后，将两步的结果并起来reduct(C)=minimal(C)U C是可约的。 irreducible(C就是所求的集族C的约简。 定义3对于U的一个集族C,通过删除集族 例2设论域U={x1,2,5,4,5,6,x7,g,,10, 中的所有可约元，就得到了一个约简的集族，我们 x1,x12,x13,x14,x15,x16,x,x18,x19,30,计算集族C=C1, 将其称为集族C的约简，记为reduct(C)。 C2,C3,C4,C5,C6,C7,C8,Cg,Co的约简，其中C1={x1,xl, 定理1和定理2实际上还保证了集族的约简是 C2={x2,x3},C3={x1,2,X3},C4={x1,X2,x3,x4},Cs={x4 唯一的。 X5,x6,x7,Xg},C6={xg,X10,X11,X12,X13,X14},C7={x4,X5,X6 定义4设C、C2是论域U上的两个集族，如果 x,xg,x9,x10,11,12,x3,14},C8={9,x10,11,x12,13,x14, reduct(C)=reduct(C2),则称集族C,与C,等价，记为 x15,x16,x17},Cg={15,x16,x1},C10={x13,14,x15,x6,7, C1~C20 X18,X19}o 集族等价形成集族空间心={CC是论域U上的 2.3根据求集族约简的算法，先求集族的极小元 集族上的等价关系，其中的等价类可记为[C]= 由算法1，将集族C中的元素按基数从小到大排 X∈CK~C,表示与集族C等价的所有集族的集合。 序为 C1={x1,x2},C2={x2,3】 2集族约简的算法 C3={,x,x3l,Cg={5,x6,x17} C4={x1,x2,x3,x4} 根据上节的结论，我们可以给出求一个集族约 C5={x4,X5,X6,x7,X8} 简的算法，该算法分为如下两大步骤： C6={9,x0,1,x2,X13,x14} C10={13,x14,15,x16,17,18,x19 1)求集族的极小元（极小元必定是既约元）： Cg={xg,x10,x,x2,x3,x14,x15,x16,x1n} 2)由极小元求集族的非极小既约元。 基数最小的元素C1={x,C2={2,3是极小 将步骤1)、2)的结果并起来，就是该集族的 元。继续算法1，求得其余的极小元分别是C,= 约简。 {X15,x16,x17,X18},C5={x4,X5,X6,x7,X8},C6={xg,x10,x1, 2.1求集族的极小元 X12,X13,X14}。 算法1求集族的极小元。 2.4。根据算法2由极小元再求集族的非极小既约元 输入论域U的一个集族C={C1,C2,…,C C4={1,2,,x4},Ci0={x3,x14,x15,x16,x7,x18,x19, 输出C的极小元集合minimal(C)。 最后结果为reduct(C)={C1,C2,C4,Cs,C6,Cg,C10lo证明 C ′ C −{C} C ′ C −{C,C ′ } C −{C ′ } C ′ C 1) 如 果 是 的可约元，则 可以用 中若干个元之并表示出来，那么当然也可 表示成 中若干个元之并，因此 是 的可 约元。 C ′ C C ′ C −{C ′ } C1,C2,···,Cn ∀Ci Ci , C C ′ C −{C} C ′ C ′ C −{C} C C −{C} D1,D2,···,Dm C ′ = C1 ∪C2 ∪ ··· ∪Cn = D1∪ D2 ∪ ··· ∪ Dm ∪C2 ∪ ··· ∪Cn D1,D2,··· ,Dm,C2,···, Cn C ′ C ′ C −{C} 2) 反之，如果 是 的可约元，则 可 用 中的若干元 表示出来。如果 ， 都有 ，则 已经用 中的若干个不等于 的元之并表示出来了，因此 是 的可约元。 要是其中有一个元等于 C，不妨设为 C1，由于 C 是 中的可约元，于是 C 可以表示成 的若干元 的并。于是， ，其中 既不等于 C，也不等于 ，这样证明了 是 中的可约元。 由命题 (1)、(2) 得证。 由定理 1 和定理 2 可以得出，在一个集族中删 除其中的一个可约元，并不会改变其余元素是既约 元还是可约元的性态。由此，我们可以逐个删除集 族中的所有可约元，只剩下既约元。 C C C C 定义 2 设 是论域 U 上的一个集族，如果 中 的每一个元都是既约元，则称 是约简的。否则，称 是可约的。 C C reduct(C) 定义 3 对于 U 的一个集族 ，通过删除集族 中的所有可约元，就得到了一个约简的集族，我们 将其称为集族 的约简，记为 。 定理 1 和定理 2 实际上还保证了集族的约简是 唯一的。 C1 C2 reduct(C1) = reduct(C2) C1 C2 C1 ∼ C2 定义 4 设 、 是论域 U 上的两个集族，如果 ，则称集族 与 等价，记为 。 C = { C|C是论域U上的 集族} [C]R = {X ∈ C|X ∼ C} C 集族等价形成集族空间 上的等价关系，其中的等价类可记为 ，表示与集族 等价的所有集族的集合。 2 集族约简的算法 根据上节的结论，我们可以给出求一个集族约 简的算法，该算法分为如下两大步骤： 1) 求集族的极小元 (极小元必定是既约元)； 2) 由极小元求集族的非极小既约元。 将步骤 1)、2) 的结果并起来，就是该集族的 约简。 2.1 求集族的极小元 算法 1 求集族的极小元。 输入 论域 U 的一个集族 C = {C1,C2,··· ,Cn} ； 输出 C 的极小元集合 minimal(C)。 1) 初始化， minimal(C) =Ø，将集族 C 中的元素按 基数从小到大排序； C minimal(C) 2) 基数最小的元素一定是极小元，设其基数为 i，将其从集族 中移除并加入极小元集合 ； 3) i=i+1； C C C minimal(C) 4) 如果集族 中已没有基数大于等于 i 的元 素，则转 5)，如果集族 中元素的基数均大于 i，则 转 3)；否则逐个检测基数为 i 的元素，如果任何一个 极小元均不是它的真子集，则它是极小元，将其从 集族 中移除并加入极小元集合 ，转 3)； 5) 算法结束， minimal(C) 即为所求。 2.2 由极小元再求集族的非极小既约元 算法 2 求集族的非极小既约元。 输入 算法 1 结束时所得的集族 C 及 minimal(C) ； 输出 非极小既约元的集合 irreducible (C)。 1) 初始化， irreducible (C) =Ø； C minimal(C) mC ⊂ C 2) 逐个扫描集族 的元素 C，找出 中 每一个满足条件 的极小元 mC； C , ∪mC irreducible (C) 3) 如果 ，则 C 是一个既约元，加入集 合 ； 4) 算法结束， irreducible (C) 即为所求。 reduct(C)=minimal(C)∪ irreducible (C) C 最后，将两步的结果并起来 就是所求的集族 的约简。 U = {x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20} C = {C1, C2,C3,C4,C5,C6,C7,C8,C9,C10} C1 = {x1, x2} C2 = {x2, x3} C3 = {x1, x2, x3} C4 = {x1, x2, x3, x4} C5 = {x4, x5, x6, x7, x8} C6 = {x9, x10, x11, x12, x13, x14} C7 = {x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14} C8 = {x9, x10, x11, x12, x13, x14, x15, x16, x17} C9 = {x15, x16, x17} C10 = {x13, x14, x15, x16, x17, x18, x19} 例 2 设论域 ，计算集族 的约简，其中 ， ， ， ， ， ， ， ， ， 。 2.3 根据求集族约简的算法，先求集族的极小元 由算法 1，将集族 C 中的元素按基数从小到大排 序为 C1 = {x1, x2}, C2 = {x2, x3} C3 = {x1, x2, x3}, C9 = {x15, x16, x17} C4 = {x1 , x2 , x3 , x4} C5 = {x4 , x5 , x6 , x7 , x8} C6 = {x9, x10, x11, x12, x13, x14} C10 = {x13, x14, x15, x16, x17, x18, x19} C8 = {x9, x10, x11, x12, x13, x14, x15, x16, x17} C1 = {x1, x2} C2 = {x2, x3} C9 = {x15, x16, x17, x18} C5 = {x4, x5, x6, x7, x8} C6 = {x9, x10, x11, x12, x13, x14} 基数最小的元素 ， 是极小 元。继续算法 1，求得其余的极小元分别是 ， ， 。 2.4 根据算法 2 由极小元再求集族的非极小既约元 C4 = {x1, x2, x3, x4} C10 ={x13, x14, x15, x16, x17, x18, x19} reduct(C) = {C1,C2,C4,C5,C6,C9,C10} ， ， 最后结果为 。 第 2 期 胡霞，等：集族等价与基于粒的下近似算子研究 ·329·