离散数学第四版课后答案(第4章).doc

第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中的 而题4.2中的 为得到题4.3中的R须求解方程，最终得到 求有三种方法，即集合表达式、关系矩阵和关系图的主法。下面由题4.2的关系分别加以说明。 1°集合表达式法 将的元素列出来，如图4.3所示。然后检查R的每个有序对，若，则从中的x到中的y画一个箭头。若中的x经过2步有向路径到达中的y，则。由图4.3可知 如果求，则将对应于G中的有序对的箭头画在左边，而将对应于F中的有序对的箭头画在右边。对应的三个集合分别为，然后，同样地寻找到的2步长的有向路径即可。 2° 矩阵方法 若M是R的关系矩阵，则的关系矩阵就是M·M，也可记作M2，在计算乘积时的相加不是普通加法，而是逻辑加，即0+0=0，0+1=1+0=1+1=1，根据已知条件得 中含有7个1，说明中含有7个有序对。 图4.3 图4.4 3°关系图方法 设G是R的关系图。为求的关系图，无将G的结点复制到中，然后依次检查G的每个结点。如果结点x到y有一条n步长的路径，就在中从x到y加一条有向边。当所有的结点检查完毕，就得到图。以题4.2为例。图4.4（1）表示R的关系图G。依次检查结点1，2，3，4。从1出发，沿环走2步仍回到1，所以，中有过1的环。从1出发，经1,1和1,4，2步可达4，所以，中有从1到4的边。结点1检查完毕。类似地检查其他3个结点，2步长的路径还有2→1→1，2→1→4，3→4→1，4→1→1，4→1→4。将这些路径对应的边也加到中，最终得到的关系图。这个图给在图4.4(2). 4．4 A：④； B：⑧； C：⑨； D：⑤； E：⑩ 分析 根据表4.1中关系图的特征来判定的性质，如表4.2所示。 表4.2 自反 反自反 对称 反对称 传递 √ √ √ √ √ √ √ √ √ √ 从表中可知和不是传递的，理上如下：在中有边3,1和1,2，但缺少边3,2.在中有边1,3和3,2，但缺少边1,2。在中有边1,2和2,1，但缺少过1的环。 4.5 A：①； B：③； C：⑧； D：⑨； E：⑤ 分析 等价关系和划分是两个不同的概念，有着不同的表示方法，等价关系是有序对的集合，而划分是子集的集合，切不可混淆起来，但是对于给定的集合A，A上的等价关系R和A的划分中一一对应的，这种对应的含义是 和y在的同一划分块里。 换句话说，等价说系R的等价类就是划分的划分块，它们表示了对A中元素的同一种分类方式。 给定划分，求对应的等价关系R的方法和步骤说明如下： 1°设中含有两个以上元素的划分块有块，记作。若，，则求出。 2° 本题中的的划分块都是单元集，没有含有个以上元素的划分块，所以，含有两个划分块，故对应地等价关系含有两个等价类。中只有一个划分块包含了集合中的全体元素，这说明因此，这个划分块对应的关系就上的全域关系，从而得到也是上的全域关系。 4．6 A：③； B：⑩； C：⑤； D：⑩； E：⑤ 分析 画哈斯图的关键在于确定结点的层次和元素间的盖住关系，下面讨论一下画图的基本步骤和应该注意的问题。 画图的基本步骤是： 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给出了最终得到的哈斯图。在整除关系的哈斯图中，盖住关系体现为最小的倍数或最小的公倍数关系。 如果偏序集是，那么哈斯图的结构将呈现出十分规则的形式。第0层是空集，第1层是所有的单元集，第2层是所有的2元子集，…，直到最高层的集合A。这里的盖住关系就体现为包含关系。 在画哈斯图时应该注意下面几个问题。 1°哈斯图中不应该出现三角形，如果出现三角形，一定是盖住关系没有找对。纠正的方法是重新考察这3