习题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）有最小元素也有最大元素. 解略
5. 设?L，??是格，其哈斯图如图5.12所示，取
f b a d c g 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
9. 设?L，??是有界格，证明：
（1）若|L|?2，则L中不存在以自身为补元的元素.
（2）若|L|?3，且?L，??是链（全序集），则?L，??不是有补格. 解略
|?是分配格吗？试分析之. 10. 格?Z，解略
11. 给出一个不是分配格的例子. 解略
12. 试证明，在有界分配格中，所有具有补元的元素组成的集合构成子格. 解略
?
《应用离散数学》方景龙版本格
