下载文档原格式
离散数学中的偏序关系是一个核心概念，它描述了集合中元素之间的一种特定关系。
与等价关系和全序关系不同，偏序关系允许集合中的元素之间只有部分元素之间存在比较关系，而不是全部元素之间都有比较关系。
偏序关系是一种二元关系，通常表示为集合上的一个小于或等于的符号（≤）。
这种关系满足两个基本性质：自反性和传递性。
自反性意味着集合中的每一个元素都小于或等于自己；传递性则意味着如果元素a小于或等于元素b，元素b小于或等于元素c，那么可以推出元素a小于或等于元素c。
偏序关系的一个重要特点是它允许集合中存在不可比较的元素对。
也就是说，对于某些元素a和b，我们不能确定a小于b，也不能确定b小于a。
这种不可比较性使得偏序关系比全序关系更加灵活和实用。
偏序关系在实际应用中有广泛的应用。
例如，在计算机科学中，偏序关系可以用于描述程序的执行顺序、任务之间的依赖关系等。
在数据结构中，偏序关系可以用于定义优先队列、堆等数据结构，从而实现对元素的快速排序和检索。
此外，偏序关系还与数学中的其他概念密切相关，如格、有向无环图等。
通过偏序关系，我们可以对集合中的元素进行排序、分类和比较，从而更好地理解和分析问题的本质。
总之，离散数学中的偏序关系是一种重要的二元关系，它描述了集合中元素之间的部分比较关系。
偏序关系具有自反性、传递性和不可比较性等特点，广泛应用于计算机科学、数据结构、数学等领域。
通过偏序关系的研究和应用，我们可以更好地理解和解决实际问题。
20XX年复习资料大学复习资料专业：班级：科目老师：日期：习题5.21. 确定具有下面图5.20XXXX 所示哈斯图的偏序集是否为格，图5.20XXXX 习题1的图解 图(a)是格，图(b)是格，图(c)是格。
2. 在一个公司里用信息流的格模型控制敏感信息，公司的每个部门都具有由有序对)(C A ，表示的安全类别，其中A 是权限级别，C 是种类。
这里，权限级别A 可以是0（非私有的），1（私有的），2（受限制的）或3（注册的）。
种类C 是集合{猎豹，黑鹰，美洲狮}的子集（在公司里常常使用动物的名字作为项目的代码名字）。
试问 （1）信息允许从（私有的，{猎豹，美洲狮}）流向（受限制的，{美洲狮}）吗？ （2）信息允许从（受限制的，{猎豹}）流向（注册的，{猎豹，黑鹰}）吗？ （3）信息从（私有的，{猎豹，美洲狮}）允许流向哪些安全类？（4）信息允许从那些安全类流向（受限制的，{黑鹰，美洲狮}）？ 解 略3. 证明每个有限格都有一个最小元素和一个最大元素。
解 略4. 给出一个无限格的例子，使得 （1）既没有最小元素也没有最大元素。
（2）有最小元素但没有最大元素。
（3）有最大元素但没有最小元素。
（4）有最小元素也有最大元素。
解 略dace fbbd f h g ce abd f hg ce ai(a)(b)(c)5. 设>< ，L 是格，其哈斯图如图5.20XXXX 所示，取图5.20XXXX 习题5的图}{1d c b a S ，，，=，}{2f d b a S ，，，=，}{3f e d c S ，，，=，}{4g f b a S ，，，=。
试问><11 ，S ，><22 ，S ，><33 ，S ，><44 ，S 中哪些是格，哪些是>< ，L 的子格，这里关系)(i i i S S ⨯= ，4321，，，=i 。
解 略6. 设><|，L 和≤><，S 是两个格，其中}16842{，，，=L ，}10321{，，，， =S ，“|”是数的整除关系，“≤”是数的小于等于关系。
习题5.1
1. 下面哪些集合是偏序集？
（1）=><，Z （2）≠><，Z （3）≥><，
Z
（4）>/<|，
Z 解 （1）是偏序集，（2）不是偏序集，（3）是偏序集，（4）不是偏序集
2. 确定由下面的关系图5.6表示的表示的3个关系是否为偏序？并列出这些关系中的所有序偶来进行验证。
解 略
图5.6 习题2的图
3.
确定由下面的关系矩阵表示的关系是否为偏序？
（1）⎪
⎭
⎪⎬⎫⎪⎩
⎪⎨⎧100011
101
（2）⎪
⎭⎪⎬⎫
⎪⎩
⎪⎨⎧101010001
（3）⎪⎪⎭⎪⎪⎬⎫⎪⎪⎩⎪⎪⎨⎧10
11
11000110010
1
解 略
4. 画出在下述集合上的整除关系的哈斯图。
（1）}87654321
{，，，，，，， （2）}131175321
{，，，，，， （3）}483624126321
{，，，，，，，
（4）}6432168421
{，，，，，， 解 （1）、（2）的哈斯图如下：
（3）、（4）略
5. 在下面偏序集中找出两个不可比的元素。
（1）⊆><，，，
})210{(p
（2）><|}86421{，，
，， 解 略
6. ><|}452415953{，，，，，，
是偏序集。
（1）求极大元素和极小元素。
（2）存在最大元素吗？存在最小元素吗？如果存在，请求出。
（3）找出子集}53{，的所有上界。
如果它的上确界存在的话，上确界。
（4）找出子集}4515
{，的所有下界。
如果它的下确界存在的话，求出下确界。
解 （1）极大元素为9，15，24和45，极小元素为3和5。
（2）不存在最大元素，也不存在最小元素。
（3）子集}53{，的上界有15和45，上确界是15。
（4）子集}4515
{，的下界有3，5和15，下确界是15。
7. ⊆><，，，，，，，，，，，，，，，，，
}}432{}431{}43{}42{}41{}21{}4{}2{}1{{是偏序集。
（1）求极大元素和极小元素。
（2）存在最大元素吗？存在最小元素吗？
（3）找出子集}}4{}2{{，
的所有上界。
如果它的上确界存在的话，上确界。
（4）找出子集}}432{}321
{{，，，，，的所有下界。
如果它的下确界存在的话，求出下确界。
解 略
8. 给出满足下列性质的偏序集。
（1）有一个极小元素但没有极大元素。
（2）有一个极大元素但没有极小元素。
（3）既没有极大元素也没有极小元素。
解 略
9. 设R 是集合X 上的半序。
（1）证明1
-R R 是等价关系。
（2）定义商集
)/(1
-=R R X Y 上的关系S ：Y D C ∈∀，，S D C >∈<，当且仅当在C 、D 中分别存在元素d c 、使得R d c >∈<，。
证明S 是商集Y 上的偏序。
解 略
10. 给出下面小写英文字母串的字典序。
（1）quack ，quick ，quicksilver ，quicksand ，quacking （2）open ，opener ，opera ，operand ，opened （3）zoo ，zero ，zoom ，zoology ，zoological 解 略
11. 给出二进制串0，01，11，001，010，011，0001和0101的基于10<的字典顺序。
解 略
12. 假设><11 ，X 和><22 ，X 是两个偏序集。
在笛卡儿积21X X ⨯上定义一个关系：><><2121b b a a ，， 当且仅当111b a 且222b a 。
证明这样定义的关系 是集合21X X ⨯上的偏序关系。
解 略
13. 求一个与集合}36241286321
{，，，，，，，上的整除关系相容的全序。
14. 如果表示建筑一座房子所需任务的哈斯图如下图5.7所示，通过制定这些任务的顺序来安排他们。
解 略
15. 对一个软件项目的任务进行排序，关于这个项目任务的哈斯图给在图5.8中。
图5.8 习题15的图
解对一个软件项目的任务排序如下：
确定用户需求，编写功能需求，开发系统需求，建立测试点，开发模块A，开发模块B，开发模块C，模块集成，写文档，α测试，β测试，完成。
