={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>,<3,4>,<3,5>,<4,3>,<4,4>,<4,5>,<5,3>,<5,4>,<5,5>}
b)
上图是相容关系图（简单一些）
Mρ= 1 2 3 4 5 1| 1 1 0 0 0 | 2| 1 1 0 0 0 | 3| 0 0 1 1 1 | 4| 0 0 1 1 1 | 5| 0 0 1 1 1 |
只画黄色部分也可以。
________________________________________
6、设正整数的序偶集合A，在A上定义二元关系R如下： <
(1)因为xv=yu，则有x/y=u/v 且有x/y=x/y,u/v=u/v
因此有<
(2)因为xv=yu,则有x/y=u/v ，且有u/v=x/y,
因此有<
(3)设有s,t,?A
若有x/y=u/v且u/v=s/t 则s/t=x/y, 则有x/y=s/t 因此有<
因而R是一个等价关系。
________________________________________
7、设集合A有4个元素，那么，A中有多少个划分？A上有多少个等价关系？ 解：有下列几种划分： { { } ,{ } ,{ },{ } }
四个元素的划分有 1个
{ { } ,{ } ,{ } } 三个元素的划分有 12种 { { } ,{ } } 二个元素的划分有 6种
{ { } } 一个元素的划分有 1种 总共有 20种划分。
20种划分对应20种等价关系
阮允准提醒说划分只有15种，晓津现给出确定的结果，三个元素的划分只有6种，二个元素的划分有7种。总共15种。
16
________________________________________
8、设П1与П2是非空集合A的划分，问：П1∪П2、П1∩П2、和П1-П2是A的划分吗?在什么条件下，它们能构成A的划分。
解：П1∪П2：不是A的划分。 П1∩П2：不是划分。 П1-П2: 不是划分。
在 П1=П2 的情况下，它们能构成A的划分 晓津补充证明： (1)
П1∪П2不一定是A的划分：
若有S1?Π1 ，S2?Π2， 有a?A 且 a?S1且a?S2 , 则S1∪S2 A ,S1∪S2?Π1∪Π2 但S1∩S2≠φ 所以， Π1∪Π2不一定是A的划分 其他类似。
3.8节习题参考答案
(本节习题答案由jhju提供，晓津补充。旨在抛砖引玉，不同意见请到分课论坛发表) http://jjzk.yeah.net 题号：1 2 3 4 5 6
________________________________________
1、画出A={3,9,27,54}上整除关系的哈斯图，并说明是否为全序关系。 解：
/={<3,3>,<3,9>,<3,27>,<3,54>,<9,9>,<9,27>,<9,54>,<27,27>,<27,54>,<54,54>}
哈斯图见上。其不是全序关系。
晓津认为这个关系应是全序关系,因为对于任意两个元素a,b,必有a<=b 或b<=a。 ________________________________________
2、设 A={1,2,3,4,5,6},R为A上的整除关系，试求： a) A的极大元、极小元、最大元和最小元。
b) 子集 A1={2,3,6} 和A2={2,3,5}的上界、下界、上确界、下确界。 解：
R={<1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<2,4>,<2,6>,<3,6>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<6,6>} COVA={<1,2>,<1,3>,<1,5>,<2,4>,<2,6>,<3,6>}
a) 其极大元为 {4,5,6} 极小元 { 1 } 最大元不存在.最小元 { 1 }
从哈斯图上看出 最大元、最小元、极小元、极大元的方法:以下均就A是一个偏序集而言，B包含于A，求B中的极大元、极小元、最大元、最小元。
(1)极大元：在B的哈斯图中每一个孤立结点或只有下方连线的结点都是B的极大元。
17
(2)极小元：在B的哈斯图中每一个孤立结点或只有上方连线的结点都是B的极小元。
(3)最大元和最小元：首先找出B的极大元和极小元。若极大元或极小元只有一个，则这个极大元或极小元就是B的最大元或最小元；若不止一个，则B的最大元或最小元不存在。
b) A1的上界、上确界为 { 6 } 下界、下确界为 { 1 } A2的上界、上确界不存在， 下界、下确界为 { 1 }
从哈斯图上看出 上界、上确界、下界、下确界的方法:A是一个偏序集，B包含于A，在哈斯图中，求B的上界、上确界，下界、下确界。
在A的哈斯图中，标出B中的结点，则不低于(不高于)其中最高结点(最低结点)并有与它们均相连且只通过下方( 上方)直线相连(包括环)的结点都为B的上界(下界)；在上界集(下界集)中距B中最高结点(最低结点)路径最短的结点是上确界(下确界)。
________________________________________
3、设集合R是A上的二元关系，证明：
a) 如果R是A上拟序关系，则 r(R)=R∪IA是偏序关系。 b) 如果R是一偏序关系，则 R-IA是拟序关系。 证明：
a) R是A上拟序关系，则有：R是反自反和传递的。 R∪IA
{
{
R具有传递性，则
可见R∪IA 具有传递性
根据定理3.8.1 R是拟序，则R必有反对称性 => R={
{
{
18
得证：r(R)=R∪IA是偏序关系
b) 如果R是一偏序关系，则 R-IA是拟序关系。
简略证明：偏序关系与拟序关系相比，区别在于自反性和反自反性 而 R
一旦失去了IA，则自反性也就丢失了。故R-IA是拟序关系 阮允准同学认为上述证明不够规范，给出证明如下： a) 如果R是A上拟序关系，则 r(R)=R∪IA是偏序关系。
a)对于任意x?A,有＜x,x>?IA ∴
对于任意
∵R是A上的拟序关系 ∴
∴r(R)是反对称的
设x,y,z?A,且
________________________________________
4、设R是集合S上的关系，S'是S的子集，定义S'上关系R'如下： R'=R∩(S'×S')
确定下述每一条断言是真还是假
a) 如果R在S上是传递的，那么R'在S'上是传递的。 b) 如果R是S上偏序关系，那么R'是S'上的偏序关系。 c)
如果R是S上的拟序关系，那么R'是S'上的拟序关系。 d) 如果R是S上的线序关系，那么R'是S'上线序关系。 解： a)
为真，因为S'×S'在S'是传递的，而R在S上是传递的，经过∩运算后仍具有传递性 b) 为假 因为S'×S'在S'是对称的 c) 为假
d) 为真
19
阮允准同学认为：a,b,c,d都是正确的 b)证明：
显然R′是自反的，传递的 现证反对称
∵R是偏序关系 ∴
∴R是反对称的 其它证法类似。
________________________________________
5、设偏序集 ,若有B A，如B中存在最大元（最小元），则必为惟一。 晓津证明：
设若B中有最大元a,b,则对于B中任一元素x有x a ,x b ， 对于a为最大元，应有b a 对于b为最大元,应有a b，如果a≠b,则表明B上关系不是反对称的，这个结论与B A且A上关系是偏序集的前提相矛盾，因此必有a=b，即最大元只能有一个。推广到更多的情况也是如此。对于最小元，其情形与之相同，因此最小元也只能是唯一的。
________________________________________
6、证明每一个良序集合一定是一个全序集合；反之成立吗？试说明理由？ 晓津证明：
根据定义，设为全序集,如果A的任何非空子集都含有最小元,则为良序集合,所以良序集必为全序集。 反之不一定成立，如果一个全序集合A中有一非空子集不含有最小元，则该全序集就不是良序集。 ________________________________________
阮允准同学认为书中的定义是错误的
良序的定义是：设＜A，?＞为偏序集......
现证明：设＜A，?＞为良序集，对任意的a,b?A，构造集合 ｛a,b},显然｛a,b}包含于A,
∴{a,b}有最小元，故必有a?b或b?a ∴＜A，?＞是全序集
反之也成立，因为全序集中任意两个元素都可比 所以对每一个非空子集，必有最小元
（事实上，全序的哈斯图是一条直线，从哈斯图中不难看出对每一个非空集合都有最小元） 3.9习题参考答案
(本节习题答案由jhju提供，晓津,阮允准补充。旨在抛砖引玉，欢迎到分课论坛发表不同意见) http://jjzk.yeah.net 题号：1 2 3 4
________________________________________
1、下列集合条件分别确定f是否从X到Y上的函数，并对f:X->Y指出哪些是入射，哪些是满射，哪些是双射？ a) X={1,2,3,4,5}, Y={6,7,8,9,10},
f={<1,8>,<3,10>,<2,6>,<4,9>}; 其不是满射、是入射。
20
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库离散数学复习资料(4)在线全文阅读。
相关推荐：