习题5.2
1. 确定具有下面图5.11所示哈斯图的偏序集是否为格,
文档收集自网络,仅用于个人学习
(a) b c a d e f i h f d b g e c a (b) 图5.11 习题1的图
解 图(a)是格,图(b)是格,图(c)是格。
2. 在一个公司里用信息流的格模型控制敏感信息,公司的每个部门都具有由有序对
f d b h g e c a (c) (A,C)表示的安全类别,其中A是权限级别,C是种类。这里,权限级别A可以是0(非
私有的),1(私有的),2(受限制的)或3(注册的)。种类C是集合{猎豹,黑鹰,美洲狮}的子集(在公司里常常使用动物的名字作为项目的代码名字)。试问文档收集自网络,仅用于个人学习
(1)信息允许从(私有的,{猎豹,美洲狮})流向(受限制的,{美洲狮})吗? (2)信息允许从(受限制的,{猎豹})流向(注册的,{猎豹,黑鹰})吗? (3)信息从(私有的,{猎豹,美洲狮})允许流向哪些安全类? (4)信息允许从那些安全类流向(受限制的,{黑鹰,美洲狮})? 解 略
3. 证明每个有限格都有一个最小元素和一个最大元素。 解 略
4. 给出一个无限格的例子,使得 (1)既没有最小元素也没有最大元素。 (2)有最小元素但没有最大元素。 (3)有最大元素但没有最小元素。 (4)有最小元素也有最大元素。 解 略
1 / 3
5. 设?L,??是格,其哈斯图如图5.12所示,取
f b d c g a e 图5.12 习题5的图
S1?{a,b,c,d},S2?{a,b,d,f},S3?{c,d,e,f},S4?{a,b,f,g}。
试问?S1,?1?,?S2,?2?,?S3,?3?,?S4,?4?中哪些是格,哪些是?L,??的
,2,3,4。 子格,这里关系?i???(Si?Si),i?1解 略 6.
|?和?S,??是两个格,其中L?{2,4,8,16},设?L,S?{1,2,3,?,10},“|”是数的整除关系,“?”是数的小于等于关系。试给出从L到S上的两个不同的格同态映射。文档收集自网络,仅用于个人学习 解 略
7. 设?是从格?L1,?1?到格?L2,?2?的满同态映射,若?L1,?1?是有界格,证明?L2,?2?也是有界格。
解 略
8. 给出一个有限格的例子,其中至少1个元素有多于1个的补元,且至少1个元素没有补元。
解 如下哈斯图所示的偏序集是一个格,元素e有补元a和d,元素a有补元e和d,元素d有补元a和e,但元素b和c都没有补元。
0 e a c b d 1 2 / 3
9. 设?L,??是有界格,证明:
(1)若|L|?2,则L中不存在以自身为补元的元素。
(2)若|L|?3,且?L,??是链(全序集),则?L,??不是有补格。 解 略
10. 格?Z,|?是分配格吗?试分析之。 解 略
11. 给出一个不是分配格的例子。 解 略
12. 试证明,在有界分配格中,所有具有补元的元素组成的集合构成子格。 解 略
?3 / 3