《第五章 关 系习题》由会员分享，可在线阅读，更多相关《第五章 关 系习题（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
