《集合论与图论》课堂练习1 (2013年10月23日13:30-15:00复旦大学计算机科学技术学院2012级) 学号 姓名 成绩 、填空题(30分,每格3分) 1.设A为一个集合,若 A为有限集 若 则称A为可列集 2.设R是A上的二元关系,R的自反(对称,传递)闭包,记为R,满足下列 3个条件: (2) (3) 3.集合A的递归(归纳)定义由三部分组成 (2) 4.设R1是从A到B的二元关系,R是从B到C的二元关系,则从A到C的 R1和R2的复合关系定义为 5.设f是从A到B的函数,是从B到C的函数,则从A到C的f和的复合 函数定义为
1 《集合论与图论》课堂练习 1 （2013 年 10 月 23 日 13:30-15:00 复旦大学计算机科学技术学院 2012 级） 学号 姓名 成绩 一、 填空题（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.自然数集合的幂集是不可列集 () 2.A∽(BGC=(A∪B)⊕(AC) 3.设A,B是集合,若存在A到B的满射,则Bl
2 二、是非判断题（18 分，每题 6 分，其中判断 3 分，论述 3 分） 1．自然数集合的幂集是不可列集。 （ ） 2．A(BC)=(AB) ( AC) （ ） 3．设 A, B 是集合，若存在 A 到 B 的满射，则|B||A|。 （ ）
综合题(52分) 1.设R是A上的二元关系。证明R的自反闭包的对称闭包的传递闭包,是包含R的最小 的等价关系。(15分)
3 三、综合题（52 分） 1．设 R 是 A 上的二元关系。证明 R 的自反闭包的对称闭包的传递闭包，是包含 R 的最小 的等价关系。（15 分）
2.R是集合A上的等价关系,|=n,R=s。对于A关于R的商集A/R,MA/R=r 证明:rsx2。(15分)
4 2．R 是集合 A 上的等价关系，|A|=n，|R|=s。对于 A 关于 R 的商集 A/R，|A/R|=r。 证明：rsn 2。（15 分）
3.格是一个偏序集,其中每对元素都有一个最大下界和最小上界。 (1)证明一个集合上的所有划分的集合与关系≤构成一个格。 (2)如果划分P1是P2的加细,则P1≤P2。(22分,每题11分)
5 3．格是一个偏序集，其中每对元素都有一个最大下界和最小上界。 （1）证明一个集合上的所有划分的集合与关系≤构成一个格。 （2）如果划分 P1 是 P2 的加细，则 P1≤P2。（22 分，每题 11 分）