第五章关系习题

第五章关系5.1有序组与集合的笛卡尔积内容提要定义5.1设a，b为任意对象，称集合｛｛a｝，｛a,b｝｝为二元有序组，或序偶（orderedpairs），简记为a，b。称a为a，b的第一分量，称b为第二分量。注意，第一、二分量未必不同。定理5.1对任意序偶a，b,c,d,a，b=c,d当且仅当a＝c且b=d。定义5.2递归定义n元序组a1，…ana1，a2=｛｛a1｝，｛a1,a2｝｝a1，…an=a1，…an-1,an本质上,n元序组依然是序偶。ai称为n元序组的第i分量。定理5.2对任意对象a1，…，an，b1，…，bn，a1，…，an=b1，…，bn当且仅当a1=b1，…，an=bn定义5.3对任意集合A1，A2,…，An，（1）A1A2，称为集合A1,A2的笛卡尔积(Cartesianproduct)，定义为A1A2=｛xuv(x=u,v∧uA1∧vA2)｝=｛u,vuA1∧vA2｝（2）递归地定义A1A2…AnA1A2…An=(A1A2…An-1)An当A1=A2=…=An=A时，A1A2…An简记为An定理5.3对任意集合A1，A2,…，An，A1A2…An=｛a1,…,ana1A1∧…∧anAn｝关于笛卡儿积有以下性质。定理5.4设A,B,C为任意集合，*表示，或–运算，那么A(B*C)＝(AB)*(AC)(B*C)A＝(BA)*(CA)定理5.5对任意有限集合A1，…，An，有:A1…An＝A1…An(为数乘运算)定理5.6对任意非空集合A，B，（l）（2）习题解答练习5.1l、证明定理5.3。证当n=2时，根据定义，A1A2={a1,a2|a1A1a2A2}，原命题成立；当n=k时，设A1A2…Ak={a1,a2,…,ak|a1A1a2A2…akAk}成立，则n=k+1时，A1A2…AkAk+1={u,ak+1|u(A1A2…Ak)ak+1Ak+1}，根据归纳假设有：A1A2…AkAk+1={a1,a2,…,ak,ak+1|a1A1a2A2…akAkak+1Ak+1}。归纳完成，命题得证。2、完成定理5.4的全部证明。证（1）A(BC)=(AB)(AC)对任意x，y，x，yA(BC)xAy(BC)xA(yByC)(xAyB)(xAyC)x，yABx，yACx，y(AB)(AC)因此A(BC)=(AB)(AC)证（2）(BC)A=(BA)(CA)对任意x，y，x，y(BC)Ax(BC)yA(xBxC)yA(xByA)(xCyA)x，yBAxCAx，y(BA)(CA)因此(BC)A=(BA)(CA)。证（3）(BC)A=(BA)(CA)对任意x，y，x，y(BC)Ax(BC)yA(xBxC)yA(xByA)(xCyA)x，yBAxCAx，y(BA)(CA)因此(BC)A=(BA)(CA)。证（4）(B-C)A=(BA)-(CA)对任意x，y，x，y(B-C)Ax(B-C)yA(xBxC)yA(xByA)xCx，yBAxCA因此(B-C)A=(BA)-(CA)。3、设A={1,2,3},R为实数集，请在笛卡儿平面上表示出AR和RA。123xy123xyARRA4、-（3）(A–B)(C–D)＝(AC)–(BD)（4）(AB)(CD)=(AC)(BD)解（1）成立。因为对于任意x,yx,y(A–B)Cx(A–B)yCxAxByC(xAyC)xBx,yACx,yBCx,y(AC)–(BD)因此(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)={1,2}{1,1,1,2,2,1，2,2}={1,2}（3）不成立。例如，令A={1，2}，B={1}，C={1}，D=，则(A–B)(C–D)＝{2,1}，而(AC)–(BD)={1,1,2,1}（4）不成立。例如，令A={1}，B={2}，C={3}，D={4}，则(AB)(CD)={1,3,1,4,2,3,2,4}(AC)(BD)={1,3,2,4}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,yx,yABxAyBxCyDx,yCD因此，若AC，BD，那么ABCD证（2）由于C,有yC；对于任意xA，x,yAC。因为ACBC，故x,yBC，进而xB，yC。于是AB得证。证（3）对于任意x,yx,y((A–C)B)(A(B–D))x,y(A–C)B)x,y(A(B–D))(x(A–C)yB)(xAy(B–D))(xAxCyB)(xAyByD)(xAyB)(xCyD)(xAyB)┐(xCyD)x,yAB┐x,yCDx,y(AB)–(CD)因此(AB)–(CD)＝((A–C)B)(A(B–D))。6、利用正规公理证明：没有非空集合A，使得AAA。证设xA，由于AAA，那么xAA，令x=u,v={{u},{u,v}},而uA，vA，从而u{u}x。对u作同上的讨论，有u1A,使得u1{u1}u{u}x。如此等等，可得到无穷降链…u2{u2}u1{u1}u{u}x与正规公理矛盾，因此，没有非空集合A，使得AAA。5.2关系内容提要5.2.1关系的基本概念定义5.4R称为集合A1，A2，…，An-1到An上的n元关系（n-aryrelations）,如果R是A1A2…An-1的一个子集。当A1＝A2＝…＝An-1＝An时，也称R为A上n元关系。当n=2时，称R为A1到A2的二元关系。n元关系也可视为A1A2…An-1到An的二元关系。定义5.5设R为A到B的二元关系。（1）用xRy表示x,yR，意为x，y有R关系（为可读性好，我们将分别场合使用这两种表达方式中的某一种）。xR¯y表示x,yR。（2）称Dom（R）为关系R的定义域（domain），Dom（R）=｛x|xA∧y(x,yR)｝（3）称Ran（R）为关系R的值域（range），Ran（R）＝｛y|yB∧x(x,yR)｝（4）称A为R的前域，B为R的陪域。几个特殊的二元关系：AB,称为A到B的空关系。ABAB，称AB为A到B的全关系。EA=｛x,x|xA｝,称为A上相等关系。5.2.2关系的基本运算定义5.6称关系R和S相等，如果R与S有相同的前城和陪域，并且xy(xRyxSy)定理5.7设R是A到B的关系，R的逆关系或逆（converse）是B到A的关系，记为R~，规定为R~=｛y,xxRy｝很显然，对任意xA,yB，xRyyR~x若MR为R的关系矩阵，那么MR~＝MR’（M’表示矩阵M的转置矩阵）定理5.8设R和S都是A到B的二元关系，为,,–运算，那么（1）R~~=R（2）R¯~=R~¯（3）(RS)~=R~S~（4）RS当且仅当R~S~定义5.8设R为A到B的二元关系，S为B到C的二元关系，那么RS为A到C的二元关系，称为关系R与S的合成（compositions），定义为RS=｛x,zxA∧zC∧y(yB∧xRy∧yRz)｝或简单地RS=｛x,zy(xRy∧yRz)｝这里称为合成运算。RR也记为R2。定理5.9设EA,EB为集合A，B上的相等关系，RAB，那么（1）EAR=REB=R（2）R=R=定理5.10设R,S,T均为A上二元关系，那么（1）R(ST)=(RS)(RT)（2）(ST)R=(SR)(TR)（3）R(ST)(RS)(RT)（4）(ST)R(SR)(TR)（5）R(ST)=(RS)T（6）(RS)~=S~R~定理5.11设R为A上二元关系，m，n为自然数，那么（l）Rm◦Rn＝Rm+n（2）(Rm)n＝Rmn定理5.12设集合A的基数为n,R是A上二元关系，那么存在自然数i,j使得0≤ij≤，Ri＝Rj。定理5.13设A=｛a1,…,am｝，B=｛b1,…,bm｝，C=｛c1,…,cp｝,RAB，SBC，MR=[rij]mn为R的关系矩阵，MS＝[sij]np为S的关系矩阵。那么，合成关系R◦S的关系矩阵MRS＝[tij]为一mn矩阵，其各分量tij可如下求取这里，∨为真值析取运算。5.2.3关系的基本特性定义5.9设R是A上的二元关系。（1）称R是自反的（reflexive），如果对任意xA，均有xRx。即,R自反当且仅当x(xA→xRx)（2）称R是反自反的（irreflexive）,如果对任意xA，xRx均不成立．即,R反自反当且仅当x(xA→┐xRx)（3）称R是对称的（Symmetic），如果对任意x,yA，xRy蕴涵yRx。即，R对称当且仅当xy(x,yA∧xRy→yRx)（4）称R是反对称的（antisymmetric）,如果对任意x,yA，xRy且yRx蕴涵x＝y。即,R反对称当且仅当xy(x,yA∧xRy∧yRx→x=y)（5）称R是传递的（transitive），如果对任意x,y,zA，xRy且yRz蕴涵xRz。即,R传递当且仅当xyz(x,y,zA∧xRy∧yRz→xRz)定理5.14设R为A上二元关系。（1）R自反当且仅当EAR。（2）R反自反当且仅当EAR（3）R对称当且仅当RR~。（4）R反对称当且仅当RR~EA。（5）R传递当且仅当R2R。定理5.15设R1，R2均为A上二元关系。（1）五大特性对交运算均封闭。即若R1，R2有五大特性之一，则R1R2仍有此性质。（2）自反、反自反、对称性对并运算封闭。（3）反自反、对称、反对称性对差运算封闭。（4）对称性对补运算封闭。（5）五大特性对求逆运算均封闭。（6）自反性对合成运算封闭，其他四大特性对合成运算均不封闭。5.2.4关系特性闭包定义5.10设R是集合A上二元关系，称R'为R的自反闭包（对称闭包，传递闭包），如果R'满足：（1）R'是自反（对称的，传递的）。（2）RR'。（3）对任意A上关系R''，若R''满足（1）和（2），则R'R''定理5.16设R是集合A上的二元关系，那么（1）r(R)=EAR（2）s(R)=RR~（3）t(R)=定理5.17设R是集合A上任一关系，那么（1）R自反当且仅当R=r(R)。（2）R对称当且仅当R=s(R)。（3）R传递当且仅当R=t(R)。定理5.18设R是集合A上任一二元关系，那么（1）如果R是自反的，那么s(R)和t(R)都是自反的