2023年离散数学习题解第一部分集合论部分.pdf

《2023年离散数学习题解第一部分集合论部分.pdf》由会员分享，可在线阅读，更多相关《2023年离散数学习题解第一部分集合论部分.pdf（89页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学辅助教材概念分析结构思想与推理证明第一部分集合论刘国荣交大电信学院计算机系4离散数学习题解答习题一（第一章集合）1.列出下述集合的所有元素:1)A=x x GNAx 是偶数八 x OAn2人 p3O/-10deN)(d wlAdx p A(3keN)(p=k-d)。3.拟定下列各命题的真假性：1 )0 c 02)06 03)0 c 0 4)0G 0 5)a,b c(a,b,c,a,b,c6）a,b（a,b,c a,b,c）7）a,b c a,b,a,b,8）a,b）Ga,b,a,b,解1 ）真。由于空集是任意集合的子集；2）假。由于空集不含任何元素；3）真。由于空集是任意集合的子集；4

2、）真。由于0是集合0 的元素；5）真。由 于a.b是集合a,b,c,a,b,c）的子集；6）假。由于a,b不是集合 a,b,c,a,b,c的元素;7）真。由于a,b是集合a,b,a,b 的子集；8）假。由于 a,b不是集合 a,b,a,b的元素。4.对任意集合A,B,C,拟定下列命题的真假性：1）假如 AW B ABSC,KI AeC,2）假如 ACBABGC,则 AGC。3）假如 AuBABC C,则 ACC。解1）假。例如 A=a,B=a,b,C=a,b,从而 AdBABSC 但 A6C。2）假。例如 A=a,B=a,a,C=a,a,从而 AW B A B GC,但、ACC。3）假。例如

3、A=a,B=a,b,C=a,a,b,从而 ACBABC,但 A WC。5.对任意集合A,B,C,拟定下列命题的真假性：1)假如 ACBABu C,则 AGC。2)假如 A S B A B cC.J lI J A cC o3)假如 A=B ABC C,则 ACC。3)假如AqBABCC,贝 I jA gC。解 1)真。由于B q C o V x (xe Bn xe c),因此AWBn Aw c。2)假。例如 A=a,B=a,b,C=a,b,c)从而 A G B A B c C,但 A gC o3 )假。例如 A=a,B=a,b,C=a,a,b,从而 A=BA B C C,但 Ae C。4)假。例

4、 如 人=h,B=a,b,C=a,b,b,从而 A=B 八B W C,但 A 5 C 6.求下列集合的幕集：1 )a,b,c2)a,b,c3)(0 4)0,0)5)a,b,a,a,b,a,b,a,b 解 1)0,a,b,c,a,b,a,c,b,c,a,b,c 2),a ,b,c,a,a,b3)0,04)0,0,0,0,05)0,a,b 7.给定自然数集合N 的下列子集：A=1,2,7,8B=xx250C=Mr可以被3 整除且0WxA U B=B4)=B=A U B性)n A U B=A U(A UB)=A UB=(A UA)UB律)n A UB=(A U AZ)UB律)n A UB=XUB律)

5、n A UB=X壹律)（定理（等号=的对称（两边同时左并上A）（U 的结合（U的互换（互补（零方法三油于A cX JELBCX,所以根据定理2 的 3，）就有A UBcX；另一方面，由于B=A U B 及根据换质位律可得B 3 3 UB,因此,由互补律及再次应用定理2 的 3）可得X=BUB uA U B,即 X=A U B;所以，A UB=X(2)次证 A U B=X=A C B，=0;算 )Az U B=X=(A UB)二X（两边同时取补运=(AZ)AB=X 律)=AGB=X身律)=An B =x 律)(de Mo r gan（反（零壹(3)再证 A AB=0nA&B;方 法（零壹律）:A

6、=AnX（互补律）A n(B U B)A A B)UA A B)（分派律）=（AAB）U0（条件A AB，=0)=AnB（零壹律）cB理 2 的 3)方法二：ADB=0=B=BU0律)=BU(A n B )=(BUA)n(B U B)律)=(AUB)n(B U B)律)=(AUB)n X律)=AUB壹律)n A=B2)1 0.对于任意集合A,B,C,下列各式是否成立，为什么？I)AU B=A U C=B=C2)ACB=AnC=B=C（定（零壹（条件 A OB=0）（分派（U 的互换（互补（零（定理4 的 解 1）不一定。例如:A=a,B=a,b,C=b。显然有A U B=A U C B W C

7、。2)不一定。例如:A=a,B=a,b,C=b,c。显然有An B=A n c,但 B N C。1 1.设 A,B 为集合，给出下列等式成立的充足必要条件：1)AB=B2)AB=BA3)AnB=AUB4)AB=A 解 1)A B=A C B,由假设可知 AB=B,即 A C B =B。由此可知 B=A C B=B,故此 B=B CB=0。由假设可知A=A0=A B=B=0。所以当AB=B时有A=B=00。反之，当 A=B=0时，显然AB=B 因此AB=B的充足必要条件是A=B=02)设 A B W 60,则有元素a CAB,那么,aGA,而由假设A B=B A 0所 以 aCBA,从 而 ae

8、A,矛盾。所 以 AB=，故 A=B。另一方面由B A=A B=0o可得BcA 因此当 A B=B A 时，有 A=B。反之，当 A=B 时，显然A B=BA=0因此,A B=B A 的充要条件是A=B。3）由于 AU B=A CB,从而 A=AUB=AnBqB,以及 Be A U B=AABqA 故 此:AUB=ACB,有 A=Bo5）根据定理6 的 1）有 A0=A，由已知条件AB=A,可得AB=A0。从而由对称差的消去律可得B=0o反之，若 B=0,则 AB=A（所以AB=A 的充足必要今12.对下列集合,画出其文图：1）A n B 2）A（BUC）3）A n（B,UC）解DIA n k

9、13.用公式表达出下面图中的阴;解B0=Ao“牛为B=0。A(RUCy A fW IJC歌部分(A A C RC A U R IJC U/A C R C C1 4 .试用成员表法证明1)(A B)C =A (B C)2)(A U B)A (B U C)c A B 解 1)成员表如下A B CA B(人 加 政B cA(B C)0 0 000000 0 101110 1 011110 1 110001 0 011011 0 110101 1 000101 1 10101成员表中运算结果C及 A(B C)的两列状态表白，全集中的每一个体对它俩有相同的从属关系，故(A B)C=A(B S C)1)成

10、员表如下：A BcA U B(B U C)(B U C)(A U B)n(B U C)B，A A B 0 0 00010100 010100100 101100000 1 11100001 0 01011111 0 111001111 011000011 1110000成员表中运算结果(A U B)n(B U C)及 AAB的两列状态表白，全集中的每一个体，凡是从属(A U B)n(B U C)的，都从属ACB,故(A U B )n (B U C)c A A B注咱然数集N取为 1,2,3,，n,习题二（第二章关系）1.设 A=1,2,3,B=a,b求1)AXB 2)BX A 3)BX B 4

11、)2 BX B 解1)AX B=(l,a),(1,b),(2,a),(2,a),(3,a),(3,b)2)BXA=(a,1),(a,2),(a,3),(b,l),(b,2),(b,3)3)BXB=(a,a),(a,b),(b,a),(b,b)4)2B=0,a,b,a,b2BX B0,a),(0,b),(a,a),(a,b),(b,a),(b,b),(a,b,b)2.使A=AX A成立的集合A存在吗？请阐明理由。解一般地说，使A=AX A成立的集合A不存在，除非A=0。否则 A#0,则存在元素xd AX A,故有y i,y 2 C A,使x=(yi,y2),从而 y”A X A,故此有 y”y

12、2 丫3皿，使 yi=(yi,y 2)，y2=(y34)，.。这说明A中每个元素x,其结构为元组的无穷次嵌套构成，这不也许。我们讨论的元素的结构必须是由元组的有限次嵌套构成。3 .证明 AXB=B X A oA=0V B=0V A=B 证 必要性:即证A XB=BX AnA=0VB=0VA=B若A X B=0,则A=0或者B=0若A X B W 0,则AW0且B W0,因此对任何xGA及任何yGB就有(x,y)G A X B,根据 AXB=BXA,可得(x,y)e B X A,故此:可得 xGB,y A,因此而得A=B且B=A,所以由=的反对称性A=B充足性:即证A=0V B=0 VA=BnA

13、 XB=B XA 这是显然的。4.证明(ACB)X(CnD)=(AXC)C l(B XD)证 证法一：(元素法)对任一(x,y)(A A B)X(CAD)有 xCAAB.yCCCD,于是 xd A,xeB,yeC,yDo 因而(x,y)6AXC,且(x,y)SBX D,所 以(x,y)e(AXC)Cl(BXD)。因 而(ACB)X(CAD)c(AXC)A(BXD)另一方面，对任一(x,y)e(A XC)A(BX D),于是有(x,y)CAXC且(x,y)e B X D,因而 xGA,yGC,xWB y e D,所以 xG A CByG (CCD)。所以(x,y)G(A AB)X(CO D)因而

14、(AXC)C(BXD)u(AAB)X(C C lD)。综合这两个方面有(A nB)X(CAD)=(AXC)n(BXD)o证法二：(逻辑法)对任何x,y(x,y)S(AnB)X(CAD)=xAn BAye C nD=(x A AX e B)A(y C/y e D)律）=(XG AA y eC)A(xe BAyGD)（人的结合律、互换=(x,y)eAXCA(x,y)G B X Dn(x,y)G(AX C)n(BXD)由 x,y 的任意性，可得：(AAB)X(CAD)=(AXC)A(B X D)。5.下列各式中哪些成立,哪些不成立？对成立的式子给出证明,对不成立的式子给出反例。1)(AUB)X(CU

15、D)=(AXC)U(B XD)2)(AB)X(CD)=(AXC)(BXD)3)(AB)X(CD)=(AXC)(BXD)4)(AB)XC=(AXC)(BX C)5)(AB)XC=(AX C)(B X C)解1)不成立。设人=佰用=仕,C=c,D=d,则(a,-d)G(AU B)X(CU D),但(a,-d)g(AXC)U(BX D)。所以(AUB)X(CUD)=(AX C)U(B X D)不成立。事实上有：(AXC)U(BX D)c(AUB)X(C)=(AU B)X(C U D)2)不成立。设 人=a,B=b,C=D=c,则(a,c)G(AXC)(BXD)但(a,c)g(AB)X(CD)。因而(

16、A b)X(CD)=(A XC)(BX D)不成立。事实上有：(AB)X(CD)u(AXC)(BX D)。由于 ABuA,CE,故有(AXC)(BXD)G AX C;又若(x,y)e(AB)X(CD)故此 xAB,从而 x至 B,yCD,从而丫血,故此国)e B X D综合这两方面，有(AB)X(CD)u(AXC)(B XD)o3)不成立。设人=归,B=(b,C=a,D=b,则(a,b)e(AB)X(CD),但(a,b)e(AXC)(BXD)。所以(A B)X(CD)c(AXC)(B X D)不成立。又设 A=a,B=b,C=a,D=c 则(a,c)e (AXC)(B X D),但(a,c)任

17、(AB)X(C D)。所 以(A X C)(B X D)仁。$)乂(2时)不成立。因 此(AB)X(CD)与(AXC)(B X D)无任何包含关系。总之(A B)X(C D)=(A X C)(B X D)不成立。4)成立。证明如下:对任一(x,y)G(AB)X C,有 xC A,xeB,ySC 于是(x,y)WAXC,且(x,y)e (AB)XC,且(x,y)/B X C(否则 x d B),所 以(x,y)S(A X C)(B X C),因而(AB)X CG(A X C)(BXC)O又对任一(x,y)e (A X C)(B X C),有(x,y)G AX C,且(x,y KBXC 从而 xG

18、A,yGC 及 xeB。即 xGAB,y C,故此(x,y)G(A B)X C。所 以(AX C)(BXC)c(AXB)XCo因 而(AB)XC=(A X C)(B X C)。另一种证明方法：(AXB)X C=(A CB )XC(差集的定义)=(AXC)n(B X C)(叉积对交运算的分派律)=(A X c)n(B X c y(因(B X C)=(Bz XC)n(BXC)U(B X C)但(AXC)n(BXC)=(AXC)n(B X C)U 0=(A X c)n(B,x o)=(A XC)n(B XC)(差集的定义)证法三：(逻辑法)对任何x,y(x,y)e(AXC)(BXC)n(x,y)WA

19、XCA(x,y)gBX Cn(xC A A ye C)A(xg B vygC)=(xdA人 y W C 人 x/B)v(x G A/yeC/y任 C)(A对v 的分派律)=(xGAAXBAYGC)v(xd A人 yG C/ye C)(A的结合律、互换律)=(x e AAxgB)A y GC(人及v 的零壹律、A的结合律)=x A BA y GCn(x,y)G(A B)XC由 x,y 的任意性,可得：(A B)X C=(A X C)(B X C)。5)成立。证明如下：对 任 一(x,y)e(AB)X C,故 此 x6A B,yC 于 是 xe A 且 xe B,或者 x gA 且 X e B o

20、 因此(X,y)e (A X C)(B XC)。所以(AB )X C=(A X C)(B X C)。对任一(x,y)(A X C)(B X C)。贝 I (x,y)e AX C且(x,y)任 BXC,或 者(x ,y)eA X C 且(x,y)B X C。因此 A,y C,xgB,或者 x B,yG C,x$A。所以 xWAB,或 x G B A，并且 y G C ,故此 xA B ,yGC。因 此(x,y)C(A B)X C,即(AXC)(B X C)q (A B)X C 综合两方面、就 有(A B)X C=(A X C)(B X C)另一种证明方法:(A B)X C=(A B)U (B A

21、)X C (对称差的定义)=(A B)X C)(B A)X C)(叉积对并运算的分派律)=(A X C)(B X C)U (B X C)(AXC)(根据 4)=(A X C)(B X C)(对称差的定义)6 .设人=1,2,3,B =a,求出所有由A到 B的关系。解:R 0=0,R 尸(1,a),R2=(2,a),R3=(3,a),R 4=(1 ,a ),(2 ,a),R s =(1,a ),(3,a ),R e=(2 ,a ),(3 ,a)R=(l,a),(2 ,a),(3,a)7 .设 A=1,2,3,4 ,R 1=(1,3),(2,2),(3,4),R 2 =(1,4),(2 ,3),(

22、3,4),求RUR2，R 1 C I R 2，R|R2,RI,D(R Q,D(R2)，次(R i),次(R2),D(RIU R2),汉(R,n R2)解:R|U R z=(3),(1,4),(2,2),(2,3),(3,4)R.AR2=(3,4)R)R2=(1,3),(2,2)Ri=(AXA)R=(1,1),(1,2),(1,4),(2,1),(2,3),(2,4),(3,1 ),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4)(R.)=1,2,3 ,次(R 1 )=2,3,4,(R2)=1,2,3次(R2)=3,4(R UR2)=1,2,3 ,次(R|AR2)=48.对

23、任意集合A 及上的关系R i和 R 2,证明1)沈(RiU R2)=(Rl)U次(R2)2)队(R,HR,)U次(R/C 次的)证1)一方面，由于R&R,UR 2,R2=R|UR2,根据定理 1,有次(RI)=*(RIUR2)，次(R2)G次(RiURz)故贝(R1)U次(Rz)Ji(R|U R：，)另一方面，若 x d 次(Ri U R z )那么存在着y W A,使(y,x)G(R UR2)因 此(y,x)R i，或者(y,x)e R z,从而x e 汉(Ri)或 者 x e 次(R?)于是x e次(Ri)U 次(R，)，所 以 次(Ri UR?)U 次(Ri)U灭(R 2)1 1.设A=

24、1,2,3,4,定义A 上的下列关系R产(1,1),(1,2),(3,3),(3,4),R2=(1,2),(2,1)R3=(1 ,1),(1 ,2),(2,2),(2,1),(3,3),(3,4),(4,3),(4,4)R4=(1,2),(2,4),(3,3),(4,1)R5=(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)R6=A X A,R7=0请给出上述每一个关系的关系图与关系矩陈，并指出它具有的性质。解J：1 0 0 22)0 1 0 01 0 0 0R一0 0 0 00 0 0 0R2是反自反的，对称的。3)1 1 0 01 1 0 0R i=0 0 1 10

25、0 1 1R3是自反的，对称的，传递的，因此是等价关系。循环的综合这两方面，就 有(R 1U R 2)=次(R I)U次(R 2)2)由于RIARZURI,R)n R2CR2,根据定理1 ,有/30%)口火(R)女(R i C R?)U R 2,所 以,火(R m R 2)a H(R C&(R 2)反方向的包含不成立，反全由第7题可得，那里次(R i AR z)=4 ,我(R i)C/(RZ)=2,3 ,4)n 3,4 =3,4 因此女(R|)n$/(R 2)中(R)A R2)9.设A 有 n个元素的有限集合，请指出A 上有多少个二元关系?并阐明理由。解 A 上有2 n 2 个元关系。由于叉积

26、A XA 有 n 2 个元素，因而A XA 有 2 n 2个子集，而每个子集都是A 上的一个二元关系。1 0.定义在整数集合I 上的相等关系、“W”关系、关系，全域关系，空关系，是否具有表中所指的性质，请用Y(有)或N(元)将结果填在表中。生质关 系 自反的反自反的对称的反对称的传递的相等关系YNYYYW关系YNNYY 关系NYNYY全域关系YNYNY空关系NYYYY4)R 4是反对称的彳盾环的。/?4=01000001001010000 1 1 11 0 0 0R 5 是反自反的，反对称的，传递的。1 0 0 23 41 1 1 11 1 1 1R 6是自反的，对称的，传递的，循环的。从而是

27、等价关系。7)1 o。20 0 0 0-0 0 0 0R7是反自反的对称Rl=0 0 0 03 o o 40 0 0 0的，传递的，循环1 2.设A 是A 上的关系，证明1)R是自反的当且反当IA=R2)R 是反自反的当且仅当I AAR=03 )R是对称的当且反当R=R4 )R是反对称的当且仅当R C R =IA5 )R是传递的当且仅当R o R U R 证 1 )必要性若 R是自反的，则对任何x GA,都有(x,x)G R,但是h=(x,x)|x G A,所以LGR。充足性若 L、=A 则 由 IA=(x,x )|x d A,可知对任何x e A,都 有(x,x)e R,所以 R是自反的。2

28、)必要性若 R是反自反的，则对任何x G A,都是(x,x)C R,从而(x,x )WR,由 IA=(x,x)|x W A 可知 L、U R。于是 IACR=R C R=0,此外O CIACR，所以 L、C R=0。充足性若 IACR=0,则 R是反自反的 否则，不是反自反的，那么应存在某一 x o C A,使得(X o,X o)s R o但是(X o，X o)WIA,从 而(X o，X O)0 o 这不也许，矛盾。3）必要性，若 R 是对称的，则对任何（x,y）右七就有（丫米）G R 于是根据逆关系的定义，可得（x,y）W R，于是R R；对任何（x,y）e R,由逆关系的定义，可得（y,x

29、）C R 再次运用R 的对称性有（y,x）e R,于是R=R;综合两方面，有 R=R。充足性若 R=R,则对任何（x,y）G R,由 R=R 可 得（x,y）6 R。从而由逆关系的定义，可 知（y,x）WR这说明R 是对称的。4）必要性若 R 是反对称的，则对任何（x,y）G R,即 有（x,y）GR及（x,y）ER,从逆关系的定义，就有（x,y）WR及（y,X）G R,因此，运用R 的反对称性，可得x=y。于是就有（x,y）=（x,X）IA,所以 R。R=IA。充足性若 RAR=IA,则对任何（x,y）C R 及（y,x）GR,从逆R 关系的定义，可得（x,y）GR 及（x,y）6 R ,也

30、 即（x,y）C R A R,运用 R C R=IA 可 得（x,y）GIA,于是x=y。所以R 是反对称的。5）必要性若 R 是传递的，则对任何（x,y）R。R,由复合关系的定义可知,存在着y eA,使（x,y）C R 且（y,y）C R,从而运用R 的传递性，可 知（x,y）G R。所以R o RCRO充足性R 0Ro从而运用R。R=R 可 得（x,y）G R 所以R 是传递的。证法二：l）n）:对任何x,xSAn（x,x）eiA（IA是幺关系，因此是自反关系）=（X,X）WR（R 是自反关系）所 以IAQR:)一方面 0 a I 八 cR ；另一方面,对任何x,y A,若(x ,y)e

31、iAn R=(x,y)e iAA(x,y)R R=x=y A(x,y)e R (IA是幺关系，因此是自反关系)=(x,x )R则与R是反自反关系，(x ,x )KR矛盾。故 I ,c R q 0 ；因此，由包含关系1的反对称性，可 得 k nR=0;u)：对任何x w A,若(x,x)R=(X ,x)e I AA(X ,X )eR (IA是幺关系,因此是自反关系)=(x,x)IACRn(x ,x )0(因 IAn R=0)则与空集不含任何元素，(x,x)0 矛盾。故对任何x G A,(x,x)g R ;所以,R是反自反关系；3)=)对任何 x,y d A(x,y)e R (y ,x)G R (

32、R是对称关系)o(x,y)G R所以，R=R;(x,y )e R(R=R)n(y,x)G R所以,R是对称的；4)=)对任何 x ,y e A(x,y)G R c Rn(x ,y)eRA(X，Y)G R=(x,y)G R A(y,x)G R=x=y (R 是反对称关系)n(x,y)s I A(IA 是自反关系）所以,RCRUI(x,y )e R(R=R)n(y,x)G R所以,R是对称的；1 3.设 A、B 为有穷集合,R,SCA XB,MR=(XI j)mx ,Ms=(y i j)mx n1)为了 RQS,必须且只须V H j (x i j W y i j)2)设MR US=(Z y)m X

33、n,那么 Z i=x：j V y i j,I=l,2.,m,j=l,2,.n.3)设 MR C S=(ti j)m Xn,那么 ti j=xy i ji=l,2,.m;j=1 ,2,.,n.证由于A、B是有穷集合，不妨设A=a i，a2.,am,B =b i,b2.,b n 1)必要性若RU S,则对任何i 1,2,，m,对任何j G 1 ,2,n),若(ai,b j)E R,则R的关系矩阵M R =(X i j)mX n中第I行第j列元素X j j=l,根 据R U S,可得，b j)es,从而得S的关系矩阵Ms=(y i j)mx n中第I行第j列元素y u=l,由于 是1W1故此X i

34、j W y i j；若(ai,b j)V R,则R的关系矩阵MR=(X i j)m*n中第i行第j列元素X i j=0，因此由S的关系矩阵MS=(y i j)mx n中第j列元素y i j O,可得x ijW y i j。总之，有(V i)(V j)(x i j W y i j)。2)充足性若M)(V j)(x r 则对任何(a Vi)GR,就 有R的关系矩 阵MR=(X ij)mx n中第i行第j列元素X i j =1,由于X iW y i j,所 以 泞 1，故此这说明S的关系矩阵Ms=(y i j)mx n中第i行第j列元素y i j为1，因此必有(ai,b j)e s,所以 RG S。

35、2 )对 任 何i d 1,2,m ,对 任 何j C l,2,n若Z i j=l,则(ai,b j )e R U S,故此(a i，b j)e R 或者(a i,b j)C S ,于是 x i j =1 或者 y.=1。从而b j)q S,于是 x .=0 且 y i j=O。从而 X i j V y u =0。因而 Z i 产x.V y u=0;综合上述两种情况，就有Z j i=X i j V y g,i =1,2,m,j =1,2,n .3)对任何 i d 1,2,m,对任何 j e 1,2,n 若 t.=1 ,则(a”b j)eR C S,故此出,b j)GS且(a G S,于 是x“

36、=l,且y尸1从 而X i j A y =L因而ti j=X i j A y t=1;若 ti j=0 ,则(a i,b j)C R D S ,故此(a b)S ,于是 x i j=0 或者 y：j=O,从而 Xi j A y i j=0。因而/=x“Ay；j=0。综合上述两种情况，就有 t i i=x i j A y n ,i=l,2,.,m,j=1,2,.,n。1 4.设 人=1,2,3,4),RI,R2为 A 上的关系,R1=(1,1),(1,2),(2,4)&=(1,4),(2,3),(2,4),(3,2),1。2 c120o3。3o3o无论从复合关系图还是从复合关系矩阵4 oRi4

37、cR240(00r1 1 0r-000 o-2）河&叫=二 MR2 MRi00011 10 0O()0 0 10 0 0 0=00000 00 1000 00 0 0 0000 0R2 RI1。1 01。2 o2 o一3。3。无论从复合关系图还是从复合关系矩阵4 o4 o0 0 1 11 1 0 10 0 0 00 0 0 00 0 0 10 0 0 03 MRR?oRRl =MrRt o MRO2K|0 0 0 00 0 0 00 0 0 00 0 0 0_0 0 0 00 0 0 01 0 1 01 02 0 2 0一3。3。无论从复合关系图还是从复合关系矩阵4 o 4 o-1 1 0 o

38、-“1 0 1一1 1 0 o-0 0 0 10 0 0 10 0 0 1M 用,=M RR。M RR M RR=0O0 0 0 00 0 0 00 0 0 00 0 0 00 0 0 00 0 0 04)0 0 0 00 0000000001 o o2。3。4 o ORI R1无论从复合关系图还是从复合关系矩阵0 火 箱 徂*c P.c R；（1 1、（1 6R11 5 ）设 Ri，R2R3是 A上的二元关系，假如R1QR2，证明1)R 1。R 3 Q R 2。R 32)R3O R,C R3O R2 证明1）对 任 何（x,y）R R 3,由复合关系之定义,必存在z A,使得（x,z）且(z

39、,y)eR3,运用Rl=R2可知(x,z)且(z,y)WR3,再次运用复合关系之定义，有(x,y)GR2o R3 所以 RIOR3=R2。R3。2)对 任 何(x,y)CR3。R i,由复合关系之定义，必 有z C A,使得(X,Z)R3且(z,y)CR”再由复合关系之定义，有(x,y)GR3oR2 o所以RsoRiURs。R2016.设A是有限个元素的集合，在A上拟定两个不同的关系R.和R2,使得 R；=RI,R；=R2“由于，令R|=0,则R|。儿=0,故此R：=R 1=0。令 R 2=A X A,则/=R2OR2=AX A=R2,故需证明 R2 R2 OR2=/?O 为此,对任何X,y

40、A,(x,y)e A X A=R2,一定存在着z A(至少有z=x或z=y存在)，使(x,z)AXA=R2 且(z,y)A X A =R2，故 此(x,y)Rz。Rz=R；,所以Q R2。R?=R；。于是 R；=R?=A X A o2)由于A是有限个元素的集合，是不心设A=ai，a2，.an)令 R尸(a.,aj)|ai e A A a j A/|W iW n/|W j W n-|R 2=(a n,a n)U R J则R1R2,即R I与R I是不同的关系。我们来证明R；=R 1 ,R；=R2，(a)先征R；=R若(a,a j)E R),则 由R I的定义必然IWiWn,1 WiW n1,并且

41、一定存在着1W k Wnl(至少有k=j存在)，使,ak)R i且(a a)R i,从而(小网)e R】o R|=R：。故此 R IG R；。若(a,a j)R；=RIORH 则存在着 k,1 W kW n-1 ,使(出血)R i且(ak,aj)G R i,于是由R I的定义，必有lW jW n-1,从而根据R i的定义，#(ai,aj)G Rio 故此R：=R综合两个方面，可得R：二R。(b)次证 R o =R2若(&,a Q WRz,则由 R?的定义，要么 1 WiWn,1 WjW n 1,要么 I=n,j=n若1W i W n,1 WjWn 1，则一定存在着1 WkWn-l(至少有k=j

42、存在)，使(a ak)Rz 且(ak,aj)R2,从 而(a i,aj)R 2 0 Rz=R；;若1二口，j=n,则(ai,aj)=(an,an)R2，那 么(a-a n)GR2,所 以(a i,ap=a,an)ER20R2=R；因此 R2二R；o若(ai,a j)W R；=R2 0 R2,则存在着 k,使出,a R2 且(a%a i)Rz,于是由R2的定义，有k=n或 者1 W k Wn1。若k=n,则由佃斑)Rz必 有I=n，所以无论IW jW n T 还是j=n,由R2的定 义,有(a i,aj)=(an,aj)eR2;若lW kW nl,则 由(a-a k)R?必 有ljW n1故此(

43、ai,aj)R?总之证得R；=R 2,综合两方面，我们证明了 R；=R2。17.设R是 集 合A上的反对称关系,|A|二h,指 了 在R A R的关系矩阵中有多少个非零值？解由第1 2 题的4 )R 是反对称关系当且反当R A R U IA，及|A|=n 可知，在 R C R的关系矩阵中非零值最多不超过n个。18.设Ri 和 R z 是集合A上的关系，判断下列命题的真假性,并阐明理由。1)假如Ri 和 R2都是自反的，那么Ri。R?是自反的。2)假如Ri 和 R 2都是反自反的，那未Ri o Rz 是反自反的。3)假如Ri 和 R2 都是对称的，那末R i o R z 是对称的。4)假如Ri

44、和 R?都是反对称的，那末Ri o R?是反对称的。5)假如Ri 和 R z 都是传递的，那末R,o R2是传递的。解 1)真。由于R,和 Rz 和 R2都是自反的，因而对任何，都有(x,x)WR(x,x)G R2。因此，对任何xGA,都有(x,x)G R.OR2所以RWR 2 是自反的。2)假。令 卜=a,b ,R 产 (a,b),R2=b,a 。那么 R,o R,=(a,a),它就不是A上的反自反关系。3)假。令 A=a,b ,c,R i=(a,b),(b,a)氐=(b ,c),(c,b)那末 Ri Rz=(a ,c),就不是A的对称关系。4)假。令 A=a,b,c,d ,R i=(a ,

45、c),(b,c)R?=(c,b),(d,a)易证R”R2都是反对称关系。但是R|o R z=(a,b),(b,a)就不是A上的反对称关系。5)假。令 A=a,b,c,Ri=(a ,c),(b,a),(b,c),R：=(c,b ),(a ,c),(a,b),易 证 Ri 和 R?都是传递关系，但 R-R2=(a,b),(b,b),(b,c)就不是A上的传递关系。19.设 A=1,2,3,4,5 ,R S AX A,5)用作图方法矩阵运算的方法求r (F 解 1)作图法：R 的关系图.。白/,系图S(R)的关系图R=(1,2),(2,3),(2,5),(3,4),(4,3),(5,b)G A X

46、A Aa+5=b+2=(a,b)I (a,b)e A X A A b =a+3=(1,4),(2,5,(3,6),(4,7),(5,8),(6,9)3)答 R=A X A 不对。由于R 是 A X A 上的关系，所 以 R U(A XA)X(AXA)=(A x A)2。2 3.设 A 是一个非空集合，R U A X A。假如R 在 A 上是对称的，传递的，下面的推导说明R 在 A 上是自反的：对任意的a,b G A,由于R 是对称的，有：aRbnbRa于是aR b n a RbAbRa,又运用R 是传递的，得:a Rb A b R a n a R a从而说明R 是自反的。上述推导对的吗？请阐明

47、理由。答 上述推导不正解。推殖民地的谬论误在于假设A的每个元素都由R 关联 着 A 的某一别的元素。假如这不是真的，那么对称性的条件的假设就始终是假的，因此结论当然是假的。因而在一个空集上的空关系都是平凡的对称和可传递，但不是自反的。此外关系 (a,a),(b,b),(a ,b),(b,a)是自反的和传递的，但在集合 a,b,c 上不是自反的。2 4 .设R 是集合A上的等价关系，证明R 也是集合A上的等价关系。证明证法一：(a)R是自反的对任意的a G A,由于R 是自反的，所以(a,a)e R,再由逆关系的定义有(a,a)e R(b)R 是对称的对任何(a,b )e R 由逆关系的定义，有

48、(b,a)e R,由 R 的对称性，可得(a,b )W R,再由逆关系的定义，就 有(b,a)e R。(c)R 是传递的对任何(a,b)e R 及(b,c)e R.由逆关系的定义，有(b,a)e R 及(c,b)W R,根据R 的传递性，可 得(c,a)e R,再次由逆关系的定义，就 有(a ,c)GR 综合(a)(b)(c)可知R是等价关系。证法二：(a)R是自反的：对任何a ,a e A=(a,a)e R(R 都是自反的)n(a,a)e R所以,R是自反的；(b)R是对称的：对任何 a,b A ,(a,b)e R=(b ,a)e R=(a,b )G R(R是对称的)=(b,a)e R所以,

49、R是对称的；(c)R是传递的：对任何a,b,c e A,(a,b)e R A(b ,c)e R=(b ,a)e RA(c,b)e R=(c,b )e RA(b,a)e R（人的互换律）=（c,a ）GR（R是传递的）n（a,c）e R （R 是对称的）所以，R是对称的；综 合（a）、（b）、（c ）,可知R是A上的等价关系。25.设Ri和R?都是集合A上的等价关系1 ）证明R|A R z也是A上的等价关系；2）用例于证明Ri U R 2不一定是A上的等价关系（要尽也许小地选取集合A）。证1 ）证法一：（a）R SR 2是自反的对任何a e A,由于R|,R2都是A上的自反关系，所 以（a,a）

50、C R|（a,a ）eR2,因此（a,a）e R,n R2（b）R|C R?是对称的对任何的（a ,b）G R|A R2,就 有（a,b）R 且（a,b）G R 由 R I,R2 都是A上的对称关系，所 以（a ,b ）&且（b,a）G R2,所以（b,a）G Ri A R.,（c）R|C R?是传递的对任何的(a,b)G R E R 2 及(b,c)W R 1 C R 2,就有(a,b)w Ri,(a,b)eR z 及(b,c)Ri,(b,c)e R2,于 是(a,b)e Ri 且(b ,c)e R 及(a ,b)eR2 且(b,c)G R 2 由于Ri,R2 都是A上的传递关系，所以(a,