《离散数学 Discrete Mathematics》课程教学资源（习题集）集合论与图论2007期中考试解答（部分）

《集合论与图论》期中考试 (2007年4月30日复旦大学计算机科学与工程系06级 学号 姓名 成绩 是非判断题 3.非空集合A上不存在二元关系R,使得R既是A上的等价关系,又是A上的偏序关系。 (假) 反例:恒等关系 4.设(A,≤)是偏序集,≠BA,若B有上界,则B必有上确界。 (假) 反例:({2,3,24,36},/) 、综合题 设R是集合A上的二元关系 1)求A上包含R的最小等价关系E的表达式; 2)证明E的最小性 3)以A={1,2,3,4,5,6},R={(1,2),(1,3),(4,4)(4,5)为例验证你的结果 (建议评分:15分,每小题5分) /*解题分析: 求A上包含R的最小等价关系,就是求R的自反、对称和传递闭包。 因为st(R)ts(R),所以E的表达式应该是E=ts(R=ts(R),而E=str(R=rst(R) 是不成立的。 最小性结合闭包的定义进行证明。* 解: 1) E=tsr(Rrts(R) 证明: 2)假设P是集合A上包含R的任一等价关系。 因为P是自反的,所以r(RP; 因为P是对称的,所以sr(R)≌P 因为P是传递的,所以ts(R)gP; 所以E≌P,从而保证了E的最小性 3)E=tsr(R=rts(R)=t((1,2),(2,1),(1,3),(3,1),(4,4),(4,5),(5,4)})=r({(1,2),(2 1),(1,3)(3,1),(2,3),(3,2),(4,5),(5,4),(1,1),(2,2),(3,3),(4,4),(5,5)}={(1,2), (2,1),(1,3),(3,1)(2,3),(3,2),(4,5),(5,4),(1,1)(2,2),(3,3),(4,4),(5,5),(6

《集合论与图论》期中考试 （2007 年 4 月 30 日 复旦大学计算机科学与工程系 06 级） 学号 姓名 成绩 一、是非判断题 3．非空集合 A 上不存在二元关系 R，使得 R 既是 A 上的等价关系，又是 A 上的偏序关系。 （假） 反例：恒等关系。 4．设（A，）是偏序集，BA，若 B 有上界，则 B 必有上确界。 （假） 反例：（{2，3，24，36}，/）。 二、综合题 设 R 是集合 A 上的二元关系 1）求 A 上包含 R 的最小等价关系 E 的表达式; 2）证明 E 的最小性; 3）以 A={1, 2, 3, 4, 5, 6}, R={(1, 2), (1, 3), (4, 4), (4, 5)}为例验证你的结果. （建议评分：15 分，每小题 5 分） /* 解题分析： 求 A 上包含 R 的最小等价关系，就是求 R 的自反、对称和传递闭包。 因为 st(R) ts(R)，所以 E 的表达式应该是 E=tsr(R)=rts(R)，而 E=str(R)=rst(R) 是不成立的。 最小性结合闭包的定义进行证明。*/ 解： 1） E=tsr(R)=rts(R) 证明： 2）假设 P 是集合 A 上包含 R 的任一等价关系。 因为 P 是自反的，所以 r(R)P； 因为 P 是对称的，所以 sr(R) P； 因为 P 是传递的，所以 tsr(R) P； 所以 EP，从而保证了 E 的最小性。 3) E=tsr(R)=rts(R)=rt({(1, 2), (2, 1), (1, 3), (3, 1), (4, 4), (4, 5), (5, 4)})=r({(1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3, 2), (4, 5), (5, 4), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5)})= {(1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3, 2), (4, 5), (5, 4), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6

/*考核知识点:等价关系* 计算中心安排领导和6名青年教师x,x2,x3,x4,ⅹs,x6值夜班,从周一到周六每个青年 教师值一晚,周日领导值班。其中x1不安排在周一值班,x不安排在周二值班,x3不安排 在周三值班。问:共有多少种不同的安排值班方法? 解:全集为U,A表示x1安排在周一值班的值班安排集合,B表示x2安排在周二值班的值 班安排集合,C表示x3安排在周三值班的值班安排集合 则安排值班方法=U- AUBUCl=U-(A+BH+C-A∩B-ACH-B∩CH+A∩BC) A=|B|=CF=S!=120 A⌒B=A⌒CH=B∩C|=4!=24 A⌒BCF=3!=6 安排值班方法=426 棒考核知识点:容斥原理,排列* 矩形被分为3×7=21个正方形,每个正方形用红色或黑色着色。证明存在非简单 子矩形(非1×k或k×1),4个角的正方形颜色相同 解:设共有3行,7列牌。将同一列的两个同色的牌称为“同色对”。根据鸽笼 原理,每一列至少有一个同色对,所以整个矩形含有7个同色对,每列一个。再 根据鸽笼原理,至少有4个同色对的颜色完全相同,不妨设有4个红色的同色对。 同色对在一列中有3种可能,再次根据鸽笼原理,这4个同色对至少有两个在列 中具有相同的位置。这两个同色对的4个牌确定的矩阵满足条件。 /*考核知识点:鸽笼原理* 平面上有n(n≥2)个圆,任何两个圆都相交但无3圆共点,问这n个圆把平面划分成多少个不 连通的区域? 解:n个圆把平面划分成an个不连通的区域 a=1,a1=2,a2=4,an=an1+2(n-1)(n /*考核知识点:递推关系*

6)} /*考核知识点：等价关系*/ 计算中心安排领导和 6 名青年教师 x1，x2，x3，x4，x5，x6 值夜班，从周一到周六每个青年 教师值一晚，周日领导值班。其中 x1 不安排在周一值班，x2 不安排在周二值班，x3 不安排 在周三值班。问：共有多少种不同的安排值班方法？ 解：全集为 U，A 表示 x1 安排在周一值班的值班安排集合，B 表示 x2 安排在周二值班的值 班安排集合， C 表示 x3 安排在周三值班的值班安排集合。 则安排值班方法=|U|-|ABC|=|U|-(|A|+|B|+|C|-|AB|-|AC|-|BC|+|ABC|) |U|=6!=720 |A|=|B|=|C|=5!=120 |AB|=|AC|=|BC|=4!=24 |ABC|=3!=6 安排值班方法=426 /*考核知识点：容斥原理，排列*/ 矩形被分为 37=21 个正方形，每个正方形用红色或黑色着色。证明存在非简单 子矩形（非 1k 或 k1），4 个角的正方形颜色相同。 解：设共有 3 行，7 列牌。将同一列的两个同色的牌称为“同色对”。根据鸽笼 原理，每一列至少有一个同色对，所以整个矩形含有 7 个同色对，每列一个。再 根据鸽笼原理，至少有 4 个同色对的颜色完全相同，不妨设有 4 个红色的同色对。 同色对在一列中有 3 种可能，再次根据鸽笼原理，这 4 个同色对至少有两个在列 中具有相同的位置。这两个同色对的 4 个牌确定的矩阵满足条件。 /*考核知识点：鸽笼原理 */ 平面上有 n(n2)个圆，任何两个圆都相交但无 3 圆共点，问这 n 个圆把平面划分成多少个不 连通的区域？ 解：n 个圆把平面划分成 an 个不连通的区域 a0=1, a1=2, a2=4, an= an-1+2(n-1) (n2) a1=n2 -n+2 (n2) /*考核知识点：递推关系*/