《第五章 关 系习题》由会员分享,可在线阅读,更多相关《第五章 关 系习题(28页珍藏版)》请在金锄头文库上搜索。
1、第五章 关 系5.1 有序组与集合的笛卡尔积内容提要定义 5.1 设 a,b 为任意对象,称集合a , a , b 为二元有序组,或序偶(ordered pairs) ,简记为。称 a 为的第一分量,称 b 为第二分量。注意,第一、二分量未必不同。定理 5.1 对任意序偶 , , = 当且仅当 ac 且 b = d 。定义 5.2 递归定义 n 元序组 =a 1 , a 1 , a2 = , an本质上, n 元序组依然是序偶。a i 称为 n 元序组的第 i 分量。定理 5.2 对任意对象 a1,a n,b 1,b n,= 当且仅当a1 = b1 ,a n= bn定义 5.3 对任意集合 A
2、1,A 2 , ,A n,(1) A1 A2,称为集合 A1 , A2 的笛卡尔积(Cartesian product) ,定义为A1 A2=x u v(x = u A1vA2)= u A 1vA2(2)递归地定义 A1 A2 AnA1 A2 An= (A1 A2 An-1 ) An当 A1 = A2 = =An =A 时,A 1 A2 An 简记为 An定理 5. 3 对任意集合 A1,A 2 , ,A n,A1 A2 An= a1 A1an An关于笛卡儿积有以下性质。定理 5.4 设 A, B, C 为任意集合, *表示 , 或 运算,那么A(B * C)(A B)*(A C)(B *
3、C) A( B A)*(C A)定理 5.5 对任意有限集合 A1,A n,有:A1 AnA 1 An ( 为数乘运算 )定理 5.6 对任意非空集合 A,B ,(l)(2)习题解答练习 5.1l、证明定理 5.3 。证 当 n = 2 时,根据定义,A 1A2= | a1 A1 a2 A2,原命题成立;当 n = k 时,设 A1A2 Ak = | a1 A1 a2 A2 ak Ak成立,则 n = k+1 时,A 1A2 Ak Ak+1 = | u (A1A2 Ak) ak+1 Ak+1,根据归纳假设有:A1A2 Ak Ak+1 = | a1 A1 a2 A2 ak Ak ak+1 Ak+
4、1。归纳完成,命题得证。2、完成定理 5.4 的全部证明。证 (1)A (B C) = (A B) (A C)对任意 x,y, A (B C) x A y (B C) x A ( y B y C) (x A y B) (x A y C) A B A C(A B) (A C)因此 A (B C) = (A B) (A C)证(2)(B C) A = (B A) (C A)对任意 x,y, (B C) A x (B C) y A (x B x C) y A (x B y A) (x C y A) B A x C A (B A) (C A)因此(B C) A = (B A) (C A)。证(3)(B
5、 C) A = (B A) (C A)对任意 x,y, (B C) A x (B C) y A (x B x C) y A (x B y A) (x C y A) B A x C A (B A) (C A)因此(B C) A = (B A) (C A)。证(4)(B - C) A = (B A) - (C A)对任意 x,y, (B - C) A x (B - C) y A (x B x C) y A (x B y A) x C B A x C A因此(B - C) A = (B A) - (C A)。3、设 A=1,2,3, R 为实数集,请在笛卡儿平面上表示出 AR 和 RA 。1 2 3
6、 xy123xyAR RA4、-(3)(A B) (C D)(A C) (B D)(4)(A B) (C D) = (A C) (B D)解 (1)成立。因为对于任意(A B) C x (A B) y C x A xB y C (x A y C) xB A C B C (AC) (BD)因此 (A B) C = (A C) ( B C)。(2)不成立。例如,令 A=1,B=2,C=1,2 ,D=1,2 ,则(A B) (C D) = (C D) = ,而(A B) (C D) = ,, = (3)不成立。例如,令 A=1,2,B=1,C=1 ,D = ,则(A B) (C D) ,而(A C)
7、 (B D) = ,(4)不成立。例如,令 A=1,B=2,C=3 ,D=4 ,则(A B) (C D) = ,(A C) (B D) = ,5、设 A , B , C , D 为任意集合,求证:(1)若 A C,B D,那么 A B C D(2)若 C , A C B C,则 A B(3)(A B) (C D)(A C) B) (A (B D)证 (1)对于任意 x,y A B x A y B xC y D C D因此,若 A C,B D,那么 A B C D证(2)由于 C ,有 y C;对于任意 x A, A C。因为 A C B C,故 B C,进而 x B,y C 。于是 A B 得
8、证。证(3)对于任意 x,y(A C) B) (A (B D) (A C) B) (A (B D) (x(A C) yB) (xA y (B D) (xA xC yB) (xA y B yD) (xA yB) (xC yD) (xA yB) (xC yD) A B C D (A B) (C D)因此(A B) (C D)(A C) B) (A (B D)。6、利用正规公理证明:没有非空集合 A,使得 A AA 。证 设 xA,由于 A AA,那么 xAA,令 x=u,u,v, 而 uA,vA,从而 uux。对 u 作同上的讨论,有 u1A,使得u1u1uux。如此等等,可得到无穷降链u2u2u
9、1u1uux与正规公理矛盾,因此,没有非空集合 A,使得 A AA 。5.2 关系内容提要5.2.1 关系的基本概念定义 5.4 R 称为集合 A1,A 2,A n-1 到 An 上的 n 元关系(n-ary relations),如果 R是 A1 A2 An-1 的一个子集。当 A1A 2A n-1 An 时,也称 R 为 A 上 n 元关系。当 n = 2 时,称 R 为 A1 到 A2 的二元关系。n 元关系也可视为 A1 A2 An-1 到 An 的二元关系。定义 5.5 设 R 为 A 到 B 的二元关系。(1)用 xRy 表示 R,意为 x,y 有 R 关系(为可读性好,我们将分别
10、场合使用这两种表达方式中的某一种) 。x Ry 表示R 。(2)称 Dom(R)为关系 R 的定义域(domain ) ,Dom(R)= x|xA y(R) (3)称 Ran(R)为关系 R 的值域(range) ,Ran(R) y| y Bx(R)(4)称 A 为 R 的前域,B 为 R 的陪域。几个特殊的二元关系: AB, 称 为 A 到 B 的空关系。AB AB ,称 AB 为 A 到 B 的全关系。 EA=|xA,称为 A 上 相等关系。5.2.2 关系的基本运算定义 5.6 称关系 R 和 S 相等,如果 R 与 S 有相同的前城和陪域,并且xy(xRyxSy)定理 5.7 设 R
11、是 A 到 B 的关系, R 的逆关系或逆(converse)是 B 到 A 的关系,记为R,规定为R= xRy很显然,对任意 xA , yB,xRy yRx若 MR 为 R 的关系矩阵,那么MRM R(M表示矩阵 M 的转置矩阵) 定理 5.8 设 R 和 S 都是 A 到 B 的二元关系,为 , , 运算,那么(1) R= R (2) R= R (3)(RS)= RS(4)R S 当且仅当 R S 定义 5.8 设 R 为 A 到 B 的二元关系,S 为 B 到 C 的二元关系,那么 RS 为 A 到 C的二元关系,称为关系 R 与 S 的合成(compositions) ,定义为RS=
12、xAzCy(yBxRyyRz)或简单地RS= y(xRyyRz)这里称为 合成运算 。RR 也记为 R2。定理 5.9 设 EA ,EB 为集合 A,B 上的相等关系,R A B,那么(1) EAR = REB = R(2) R = R = 定理 5.10 设 R , S , T 均为 A 上二元关系,那么(1) R ( S T) = (R S) (RT)(2) (S T)R = (SR) ( TR)(3) R(S T) (RS) (RT)(4) (S T)R (SR) ( TR)(5) R ( S T) = (R S)T(6) (RS ) =S R定理 5.11 设 R 为 A 上二元关系,m ,n 为自然数,那么(l) Rm RnR m+n(2)(R m)nR mn定理 5.12 设集合 A 的基数为 n , R 是 A 上二元关系,那么存在自然数 i,j