集合与关系.docx

1、集合与关系第三章 集合与关系3.1 第 2 题 (2)(3)(5),第 3 题 (2)(4), （广义并，广义交）第 4 题 (1)(4)(5), 第 5 题 (1)(2)(3),第 8 题 (2)(4) ，3.2 第 11题， 第 12题3.3 第 19 题, 第 20 题，第 23 题，第 26 题，第 27 题，第 31 题 (2)(5)3.4第 33题，第 37题 ,3.5第 47题，第 49题 (2)3.6第 53题，第 54题，第 57 题3-12. 设有集合 A=x| x 是小于等于 6 的质数 B= x| 4 x 12 ，x 是偶整数C= x| x =1,4,5,7,8 ,并设

2、全集为 A B C。求下列集合表达式的结果。解 : 根据题目所给的集合 , 先求得集合A=2,3,5,B=4,6,8,10,12,C=1,4,5,7,8(2)(B C) (A B)= (4,6,8,10,12 1,4,5,7,8) (2,3,5 4,6,8,10,12)=4,8-2,3,4,5,6,8,10,12=(3) (A B) (A C)=( 2,3,5 4,6,8,10,12 ) (2,3,5 1,4,5,7,8 )=2 ， 3， 4， 5， 6， 8， 10， 12-1 ， 2， 3， 4， 7， 8 =5 ， 6， 10， 12(5)A (C B)= 2,3,5 (1,4,5,7,

3、84,6,8,10,12)= 2,3,54，8= 1 ， 2， 3，5， 6， 7， 10， 123. 设 A=1,2 ， 1 ， 1 ， 0 , B=1,3 ，2,3 ， 1 ， 0 ，计算下列并集和交集。(2) A(4) B解：（ 2） A=0 ， 1， 2=(4) B= =4.求下列集合的幂集，并用下标子集表示。(1)(4)2(5)x,y,z解： (1) 设 A= ， A 的幂集为 ， （ A）的下标子集表示为 A 0 。(4) 设 A=2 ， A 是空集的幂集 ， A 的幂集 （ A ）为 ， ，（ A ）的下标子集表示为 A 0 ， A 1 。(5) 设 A=x,y,z ， A 的幂

4、集 （ A ）为 ,x,y,z,x,y,x,z,y,z,x,y,z ，（A ）的下标子集表示为 A 0,A 4 ,A 2,A 1,A 6,A 5,A 3,A 7 。5.设集合 A 有 5 个元素，根据子集的下标，写出子集的列举表示。(1)A 12(2)A 23(3)A 0解：设 A=a,b,c,d,e ，则A 12=A 01100 =b,cA 23= A 10111 =a,c,d,eA 0= A 00000 =8.设 A,B,C 都是集合，证明下列命题。(2)如果对一切集合 A 都有 A B=A , 那么必有 B=（ 3）如果 A B 那么 （ A ） A （B）(4) （ A） (B) =(

5、A B)证明：(2)反证法： 已知 B AB，A B=A B A 对一切集合 A 成立，假定 B 不等于 ，那么必有 B 的非空真子集 C, C B A , 由于 C 是集合，满足C B=C （替换已知条件中的 A ）, 由定理六可得 B C ,此与 C B 矛盾。由反证法可得 B= 。直接证法：构造式子 (AB) (AB) 由已知 A B=A 可得：=AA=而 (A B) ( A B)=（ A A） B, 由已知条件得=B所以： (A B)(AB) = （A A ） B=B =(3)任取 (A) ，得 A，由于 A B，则 A B ，由包含关系的传递性知 是 B 的子集，可得 (B) ，故

6、（ A） (B)。(4) 一方面， 由（ 3）的结果可得 ：如果 A B A 和 A B B那么有 （A B） (A) 和 （ A B） (B)（由 A B, C D 可得 AC BD）于是得 (A B) （ A ） （ B）另一方面，任取 (A) （ B） ,得 (A) 且 (B) ，即 A 且 B , 于是得 A B ， (A B) ，故得（A ） (B) (A B)综合此两方面 （ A ） (B) =(A B)3-211200 名学生中有 120 人选网络课程， 130 名选人工智能课程， 110 人选多媒体制作课程。已知同时选网络课程和人工智能课程的有 80 人，同时选媒体制作课程与网

7、络课的有90 人，同时选人工智能和多媒体制作的人有 70 人，同时选三门课的学生有 60 人。是否能算出一门课都没有选的人数？解 : 根据包含排斥原理 ,设选网络课程的同学组成 A 集合， |A|=120设选人工智能课程的同学组成 B 集合， |B|=130设选多媒体制作课程的同学组成 C 集合， |C|=110设没选任何课程的同学组成 D 集合， |D| = y| A B|=80| CB| =70| A C| =90|A B C|=60如果 200 人中有 y 个人没选课200=120+130+110-80-70-90+60+yy=2012证明：任意 n 个连续的整数中，必存在一个整数能被

8、n 整除。证明：反证法：设 a 1 , a 2 , ,a n 是任意 n 个连续的整数，每个数被 n 整除的余数只能是0， 1，2， ， n-1 中之一。如果这 n 个数中不存在任何数被 n 整除，那么余数的选择范围就在 1，2， ， n-1 之中。根据鸽巢原理则必有两个数被 n 除时余数相同，不妨设为 a i , a j , 1 i a n ,此与 a j an 矛盾，所以必存在一个整数能被 n 整除。3-319.设 A=0,1,求 AA,A3。A A=， ， ， ,A 3 =，20.设有 A=0 ， 1，2 ，构造一个所有两位三进制码的集合。解：根据A A= ， ， ， ， ， ， ， 构

9、造所有两位三进制码的集合为 00 ， 01 ，02 ， 10,11,12,20,21,2223. 设集合 A=0,1, ，9, A 上的二元关系 R= x，y | x,y A, x=y+2n, n I 写出关系 R 的关系集合，关系矩阵，画出 R 的关系图关系矩阵 M R=关系图 GR24.设A= a， b ，R= x，y |x，y(A)，xy 写出关系R 的关系集合，关系矩阵，画出 R 的关系图。25.设 A=1 ， 2， ， 26 ，B= a，h， j， p， t ，R=x，y|xA， yB，x 是y 在字母表中的次序写出关系R 的关系集合，关系矩阵，画出R 的关系图。求出dom(R)，

10、ran(R)， fld(R)。解： R=, ， ， ， dom(R)=1,8,10,16,20 ， ran (R)=B ， fld (R)=1,8,10,16,20,a,h,j,p,t 。矩阵是 26行5列阵图是从 A 到 B 的对射图。略26.解 :集合 A=0,1, ，6, A 上的二元关系 R= x，y | x,y写出关系 R 的关系集合，关系矩阵，画出 R 的关系图。根据 R 的入集条件，写出关系 R 如下：R=, ， ， ， ， A, x是 y的质因子27.对习题 23，24， 25，26 所述的关系 R 讨论其关系性质。解： 23 题 是等价关系， R 具有自反性，对称性，传递性。

11、24 题诗篇序关系， R 具有自反性，反对称性，传递性。25 题的 R 关系是 A 到 B 的关系，且 A 与 B 不相等，所以不能讨论 R 的关系性质。26 题从关系集合可以看出， R 不是自反的，不是反自反的，不是对称的，是反对称的，是传递的，不是反传递的。31.设 A 是给定的集合， R 是 A 上的二元关系，证明以下命题。(2)如果 R 既是对称的又是反对称的，那么R 是恒等关系 I A 的子集。(5)如果 R 满足对传递性，那么R 1 是传递的。证明：（2）已知 R 既是对称的又是反对称的，那么由对称性知对 任取 a,bR 必有 b,aR, 由反对称性知 a=b ,即任取 a,bR

12、必得 a=b,所以 RIA。（ 5）已知 R 具有传递性，即对任意取的a,bR， b,cR,有a,cR。 根据逆关系的定义，可以得到对任意取的 a,bR-1 ， b,cR-1 ,有 b,aR， c,bR,由 R 是传递的可得任取c,aR ,于是得到a,cR-1可见 R-1具有传递性。3-433.设A=1,2,3 ,B=a,b,c,d，C= 4,5,6 ,对下列关系， 求复合关系R?S 的关系集合与关系矩阵。(1)R=(2)R=1,b1,a, 2,d , 2,d, 3,c , 3,c,;2,b S=;a,4S= b,5 , d,4, a,4 , c,6, d,6 , b,5(3)R=,;S=,解

13、：(1)R?S=,(2)R?S=,(3)R?S=,37.设 A 是给定的集合， R， S， T 是 A 上的二元关系，举出反例说明以下事实。(1)如果 R?S IA , 那么，未必有 S= R-1。(2)如果 R,S 都是对称的，那么R?S 未必是对称的。(3)如果 R,S 都是反对称的，那么R?S 未必是反对称的。(4)如果 R,S 都是传递的，那么R?S 未必是传递的。(5)如果 R?S= R 那么 S 未必是恒等关系。(6)如果 R? R= R ，那么 R 未必是自反的。解：设 A=a,b,c(1)R=; S= , R ?S=R?S IA 但 S R-1(2)R= ; S= , R,S

14、都对称，R?S=,R?S 不是对称的。(3)R= ; S=, R,S 都反对称，R?S =, , R ?S 不是反对称的。(4) R= ; S=, ,R,S 都传递，R?S=, R ?S 不传递(5)R= ; S=,R?S= R, 但 S 不是恒等关系。(6)R= ， R? R= R,但 S 不是自反的。3-547.举出反例说明下列事实。(1)如果 R,S 是集合 A 上的等价关系，那么R?S 未必是等价关系。(2)如果 R，S 是集合 A 上的等价关系，那么R S 未必是等价关系。(3)如果 R,S 是集合 A 上的相容关系，那么R?S 未必是相容关系。(4)如果 R，S 是集合 A 上的相

15、容关系，那么R- S 未必是相容关系。解 : 设集合 A=1,2,3(1)R= ， ， ， ， ， ； S= ， ， ， ，R?S= ， ， , ，不对称，不是等价关系。(2) R= ， ， ， ， ；S= ， ， ， ， R S= ， ， ， ， ， ， 不传递，不是等价关系。(3)R= ， ， ， ， ； S= ， ， ， ， R?S= ， ， , 不对称，不是相容关系。(4)R= ， ， ， ， ； S= ， ， ， ， R-S= ， 不自反 ，不是相容关系。49.设有集合 A=1,2,3,4 , 对以下完全覆盖给出其对应的相容关系图。(2)B= 1,2,4,3,2,4 解：根据三结点的

16、完全多边形图可以划出对应相容关系的简图：3-653.设有一个偏序集合的 HASS 图如下图所示 ,对给出的子集填写表格。集合最大元最小元极大元极小元上界上确界下界下确界e,d无无e,de,dh,ffbbd,f,hhdhdhhb,c,dde,f,ga,b,c无无无无f,ga,b,cea,b,chf,hhfb无b无54.根据下列偏序关系图，画出其 HASS 图。解：根据（ a） ,(b), (c) ,(d) 图中的盖住关系。分别划出对应的 HASSE 图如下：57.设 A=0,1, 8 ， D=x a|x,yA ， yx a， xy(mod a) ，a 是 9 的整因子 ，其中 x a 是模 a

17、同余的等价类。画出D，的 HASS 图。解：先把关系 D 中的元素搞清楚，再根据包含关系划出HASSE 图。9 的因子有 1， 3，9， D 集合中有三个等价类和一个空集。D= x 1， x 3， x 9 , ，其中 是空集。x 1= Ax 3= 3 ，6 x 9= 0 根据包含关系，科的hasse图如下：58.证明：良序关系一定是全序关系。证：设 A ， 为任意给定的良序集，任取x,y A ，x y， x,y是A 的子集。由良序集的定义，知必有 x y 或 yx 之一成立，故良序关系一定是全序关系。59.证明：设有良序集A ，对任意的S A, S 是非空子集，则S ， 仍是良序集合。证：取 S 的任意子集 C，C S， C S A 。 由 A 的任一子集总是存在最小元素，所以 C 作为 A 和 S 的任意子集也存在最小元，根据良序集的定义知 S ， 仍是良序集合。