《集合论与图论》课堂练习1 (2011年10月复旦大学计算机科学技术学院2010级) 学号 姓名 成绩 、填空题(30分,每格3分) 1.设A为一个集合,若 A为有限集。 则称A为可列集。 2.设R是A上的二元关系,R的自反(对称,传递)闭包,记为R',满足下列 3个条件 (3) 3.集合A的递归(归纳)定义由三部分组成: (2) 4.设R1是从A到B的二元关系,R2是从B到C的二元关系,则从A到C的 R1和R2的复合关系定义为 5.设f1是从A到B的函数,f是从B到C的函数,则从A到C的f和f的复 合函数定义为 是非判断题(18分,每题6分,其中判断3分,论述3分)
1 《集合论与图论》课堂练习 1 （2011 年 10 月 复旦大学计算机科学技术学院 2010 级） 学号 姓名 成绩 一、 填空题（30 分，每格 3 分） 1．设 A 为一个集合，若 A 为有限集。 若 ，则称 A 为可列集。 2．设 R 是 A 上的二元关系，R 的自反（对称，传递）闭包，记为 R’，满足下列 3 个条件： （1）_ _ _; （2）_ _ ; （3）_ _ _。 3．集合 A 的递归（归纳）定义由三部分组成： （1）_ _ _; （2）_ _ ; （3）_ _ _。 4．设 R1 是从 A 到 B 的二元关系，R2 是从 B 到 C 的二元关系，则从 A 到 C 的 R1 和 R2 的复合关系定义为_ _ _ 。 5. 设 f1 是从 A 到 B 的函数，f2 是从 B 到 C 的函数，则从 A 到 C 的 f1 和 f2的复 合函数定义为_ _ _ 。 二、是非判断题（18 分，每题 6 分，其中判断 3 分，论述 3 分）
1.A∩(BGC=(A∩B)(A⌒C) (真) 2. AU(BECF()E(AUC) (假) A={2,3},B={1,4,7},C={35} 3.设A,B是集合,若存在A到B的满射,则B (真) 设存在A到B的满射f,对任意b∈B,存在x∈A,fa)=b。 而由函数的定义,=b,fay)=b2,若bb,则aa。则B≤ 综合题(52分) 1.设R是A上的二元关系。证明R的自反闭包的对称闭包的传递闭包,是包含R的最小 的等价关系。(15分) 2.在1到1000000之间(包括1和1000000在内),有多少个整数既不是完全平方数,也 不是完全立方数?(15分) 解:S={x|x∈N并且1≤x≤100000A={(x|x∈S并且x是完全平方数},B={x|x∈S并 且x是完全立方数}。 S|=10000004=100,B=100,A⌒B=10 SHA∪B|=998910 3.格是一个偏序集,其中每对元素都有一个最大下界和最小上界 (1)证明一个集合上的所有划分的集合与关系≤构成一个格 (2)如果划分P1是P2的加细,则P1≤P2。(22分,每题11分) 设∏是集合S的所有划分的集合,如果划分P1是P2的加细,即如果P1中的每个 集合都是P2中某个集合的子集,则P1≤P2 首先证明(∏,≤)是偏序集。 由于P≤P,所以≤是自反的。 假设P1≤P2,并且P2≤P1。令T∈P1,因为P≤P2,存在集合T∈P2,使得TcT; 又因为P2≤P1,存在集合T∈P1,使得T'cT;从而TcT。但是因为P1是划分, 由T=T和T<TcT推出T'=T,于是T∈P2。反之,通过交换P1与P2同样得出 P2的每个子集也在P1中。因此P1=P2,并且≤是反对称的 假设P1≤P2并且P2≤P3。令T∈P1,存在集合T∈P2,使得TT;由于P2≤P3,存 在集合T"∈P3,使得TT;所以TcT,因此P1≤P3。所以≤是传递的。 划分P1和P2的最大下界是划分P,P的子集都是形如T∩T2的非空集合,其中T1∈P1,T2∈ P2,划分P1和P2的最小上界对应于等价关系的划分:x∈S等价于yeS,如果对某个非负整 数n存在序列xx,x,x2,…,xn=y,使得从1到n的每个i,x1和x在P1或者P2的同一元 素中
2 1．A (BC)=(AB) ( AC) （真） 2．A(BC)=(AB) ( AC) （假） A={2, 3}，B={1, 4, 7}，C={3,5} 3．设 A, B 是集合，若存在 A 到 B 的满射，则|B||A|。 （ 真 ） 设存在 A 到 B 的满射 f，对任意 bB，存在 xA，f(a)=b。 而由函数的定义，f(a1)=b1，f(a2)=b2，若 b1b2，则 a1a2。则|B||A|。 三、综合题（52 分） 1．设 R 是 A 上的二元关系。证明 R 的自反闭包的对称闭包的传递闭包，是包含 R 的最小 的等价关系。（15 分） 2．在 1 到 1000000 之间（包括 1 和 1000000 在内），有多少个整数既不是完全平方数，也 不是完全立方数？（15 分） 解：S={ x | xN 并且 1≤x≤1000000}，A={ x | xS 并且 x 是完全平方数}，B={ x | xS 并 且 x 是完全立方数}。 |S|=1000000，|A|=1000，|B|=100，|AB|=10 |S|-|AB|=998910 3．格是一个偏序集，其中每对元素都有一个最大下界和最小上界。 （1）证明一个集合上的所有划分的集合与关系≤构成一个格。 （2）如果划分 P1 是 P2 的加细，则 P1≤P2。（22 分，每题 11 分） 设是集合 S 的所有划分的集合，如果划分 P1 是 P2 的加细，即如果 P1 中的每个 集合都是 P2 中某个集合的子集，则 P1≤P2。 首先证明（，≤）是偏序集。 由于 P≤P，所以≤是自反的。 假设 P1≤P2，并且 P2≤P1。令 T P1，因为 P1≤P2，存在集合 T’P2，使得 TT’； 又因为 P2≤P1，存在集合 T”P1，使得 T’T”；从而 TT”。但是因为 P1是划分， 由 T=T”和 TT’T”推出 T’=T”，于是 TP2。反之，通过交换 P1 与 P2同样得出 P2的每个子集也在 P1中。因此 P1=P2，并且≤是反对称的。 假设 P1≤P2 并且 P2≤P3。令 T P1，存在集合 T’P2，使得 TT’；由于 P2≤P3，存 在集合 T”P3，使得 T’T”；所以 TT”，因此 P1≤P3。所以≤是传递的。 划分 P1 和 P2 的最大下界是划分 P，P 的子集都是形如 T1T2 的非空集合，其中 T1 P1，T2 P2，划分 P1 和 P2 的最小上界对应于等价关系的划分：xS 等价于 yS，如果对某个非负整 数 n 存在序列 x=x0, x1, x2, …, xn=y，使得从 1 到 n 的每个 i，xi-1和 xi 在 P1 或者 P2 的同一元 素中