离散数学（第五版）清华大学出版社第4章习题解答
4．1 A：⑤； B：③； C：①； D：⑧； E：⑩ 4．2 A：②； B：③； C：⑤； D：⑩； E：⑦ 4．3 A：②； B：⑦； C：⑤； D：⑧； E：④
分析 题4.1-4.3 都涉及到关系的表示。先根据题意将关系表示成集合表达式，然后再进行相应的计算或解答，例如，题4.1中的 Is ={<1,1>,<2,2>}, Es ={<1,1>,<1,2>,<2,1>,<2,2>} Is ={<1,1>,<1,2>,<2,2>}; 而题4.2中的
R={<1,1>,<1,4>,<2,1>,<3,4>,<4,1>}.
为得到题4.3中的R须求解方程x+3y=12，最终得到 R={<3,3>,<6,2>,<9,1>}.
求RoR有三种方法，即集合表达式、关系矩阵和关系图的主法。下面由题4.2的关系分别加以说明。 1°集合表达式法
将domR,domRUran,ranR的元素列出来，如图4.3所示。然后检查R的每个有序对，若
如果求FoG，则将对应于G中的有序对的箭头画在左边，而将对应于F中的有序对的箭头画在右边。对应的三个集合分别为domG,ranUdomF,ranF，然后，同样地寻找domG到ranF的2步长的有向路径即可。 2° 矩阵方法
若M是R的关系矩阵，则RoR的关系矩阵就是M·M，也可记作M，在计算2 48
乘积时的相加不是普通加法，而是逻辑加，即 0+0=0，0+1=1+0=1+1=1，根据已知条件得
?1 0 0 1? ?1 0 0 1? ?1 0 0 1? ?1 0 0 0? ?1 0 0 0? ?1 0 0 1?
2 ?? ?? ?? M =?????=??
?0 0 0 1? ?0 0 0 1? ?1 0 0 0? ?1 0 0 0? ?1 0 0 0? ?1 0 0 1? M2中含有7个1，说明RoR中含有7个有序对。 图4.3 图4.4 3°关系图方法 n''
设G是R的关系图。为求R 的关系图G ，无将G的结点复制到G 中，然后依次检查G的每个结点。如果结点x到y有一条n步长的路径，就在G'中从x到y加一条有向边。当所有的结点检查完毕，就得到图G'。以题4.2为例。图4.4（1）表示R的关系图G。依次检查结点1，2，3，4。从1出发，沿环走2步仍回到1，所以，G'中有过1的环。从1出发，经<1,1>和<1,4>，2步可达4，所以， '中有从1到4的边。结点1检查完毕。类似地检查其他3个结点，2 G
步长的路径还有2→1→1，2→1→4，3→4→1，4→1→1，4→1→4。将这些路径 '2
对应的边也加到G 中，最终得到R 的关系图。这个图给在图4.4(2). 4．4 A：④； B：⑧； C：⑨； D：⑤； E：⑩
分析 根据表4.1中关系图的特征来判定R1,R2,LR5的性质，如表4.2所示。 表4.2 49
自反 反自反对称 反对称 传递 R√ 1 R2 R√ 3√ √ √ √ R4 R5√ √ √ √
从表中可知R1,R2和R3不是传递的，理上如下：在R1中有边<3,1>和<1,2>，但缺少边<3,2>.在R2中有边<1,3>和<3,2>，但缺少边<1,2>。在R3中有边<1,2>和<2,1>，但缺少过1的环。
4.5 A：①； B：③； C：⑧； D：⑨； E：⑤
分析 等价关系和划分是两个不同的概念，有着不同的表示方法，等价关系是有序对的集合，而划分是子集的集合，切不可混淆起来，但是对于给定的集合A，A上的等价关系R和A的划分π中一一对应的，这种对应的含义是
拘句话说，等价说系R的等价类就是划分π的划分块，它们表示了对A中元素的同一种分类方式。
给定划分π，求对应的等价关系R的方法和步骤说明如下：
1°设π中含有两个以上元素的划分块有l块，记作B1,B2,L.Bt。若Bi ={x1,x2,L,xj}，j≥2，则
本题中的π 的划分块都是单元集，没有含有个以上元素的划分块，所以， 1
R=IA,π2含有两个划分块，故对应地等价关系含有两个等价类。π3中只有一个划分块Z+.Z+包含了集合中的全体元素，这说明
这个划分块对应的关系R就Z+上的全域关系，从而得到R=R UI 也是Z+上的 11A 全域关系。
4．6 A：③； B：⑩； C：⑤； D：⑩； E：⑤ 50
分析 画哈斯图的关键在于确定结点的层次和元素间的盖住关系，下面讨论一下画图的基本步骤和应该注意的问题。 画图的基本步骤是：
1° 确定偏序集中的极小元，并将这些极小元放在哈斯图的最底层，记为第0层。
2° 若第n层的元素已确定完毕，从A中剩余的元素中选取至少能盖住第n层中一个元素的元素，将这些元素放在哈斯图的第n+1层。在排列第n+1层结点的位置时，注意把盖住较多元素的结点放在中间，将只盖住一个元素的结点放在两边，以减少连绩的交叉。
3° 将相邻两层的结点根据盖住关系进行连线。
以本题的偏序集为例，1可以整除S中的全体整数，故1是最小元，也是唯一的极小元应该放在第0层。是1的倍数，即2，3，5，7，S中剩下的元素是4，6，8，9，10。哪些应该放在第2层呢？根据盖住关系，应该是4，6，9和10。因为4盖住，2，6盖住2和3，9盖住3，10盖住2和5. 8不盖住2，3，5，7中的任何一个元素，最后只剩下一个8放在第3层。图4.5给出了最终得到的哈斯图。在整除关系的哈斯图中，盖住关系体现为最小的倍数或最小的公倍数关系。 如果偏序集是
1°哈斯图中不应该出现三角形，如果出现三角形，一定是盖住关系没有找 51
对。纠正的方法是重新考察这3个元素在偏序中的顺序中的顺序，然后将不满足盖住关系的那条边去掉。请看图 4.6(1)中的哈斯图。图中有两个三角形，即三角形abc和abd。根据结点位置可以看出满足如下的偏序关系： apb,apc,bpc,apd,bpd
从而得到apbpc和apbpd。这就说明c和d不盖住a，应该把ac边和ad边从图中去掉，从而得到正确的哈斯图，如图4.6(2)所示。
2° 哈斯图中不应该出现水平线段。根据哈斯图的层次结构，处在同一水平位置的结点是同一层的，它们没有顺序上的“大小”关系，是不可比的。出现这种错误的原因在于没有将“较大”的元素放在“较小”元素的上方。纠正时只要根据“大小”顺序将“较大”的元素放到更高的一层，将水平线改为斜一就可以了。
3° 哈斯图中应尽量减少线的交叉，以使得图形清晰、易读，也便于检查错误，图形中线的交叉多少主要取决于同一层结点的排列顺序，如果出现交叉过多，可
以适当调正结点的排列顺序，注意变动结点时要同时移动连线。
最后谈谈怎样确定哈斯图中的极大元、极小元、最大元、最小元、最小上界和最大下界，具体的方法是：
1° 如果图中有孤立结点，那么这个结点既是极小元，也是极大元，并且图中既元最小元，也元最大元（除了图中只有唯一孤立结点的特殊情况）。
2° 除了孤立结点以外，其他的极小元是图中所有向下通路的终点，其他的极大元是图中所有向上通路的终点。
3° 图中唯一的极小元是最小元，唯一的极大元是最大元；否则最小元和最大元不存在。
4° 设B为偏序集的子集，若B中存在最大元，它就是B的最小上界；否则从A-B中选择那些向下可达B中每一个元素的结点，它们都是B的上界，其中的最小元是B的最小上界。类似地可以确定B的最大下界。
观察图4.5,1是所有向下通路的终点，是极小元，也是最小元，向上通路的终点有9，6，8，10和7，这些是极大元。由于极大元不是唯一的，所以，没有最在元。地于整个偏序集的最小上界和最大下界，就是它的最在元和最小元，因此，该偏序集没有最小上界，最大下界是1。 52
4.7 A：④； B：⑤； C：③； D：①； E：⑦ 4.8 A：②； B：①； C：④； D：②； E：⑨
分析 给定函数f:A→B，怎样判别它是否满足单射性呢？通常是根据函数的种类采取不同的方法。
1° 若 f:A→B是实数区间上的连续函数，那么，可以通过函数的图像来判别它的单射性。如果f的图像是严格单调上升（或下升）的，则f是单射的。如果在f的图像中间有极大或极小值，则f不是单射的。
2° 若f不是通常的初等函数。那么，就须检查在f的对应关系中是否存在着多对一的形式，如果存在x1,x2∈A,x1≠x2但f(x1)= f(x2)，这就是二对一，即两个自变量对应于一个函数值，从而判定f不是单射的。
下面考虑满射性的判别，满射性的判别可以归结为f的值域ranf的计算。如果ranf =B，则f :A→B是满射的，否则不是满射的。求ranf 的方法说明如下：