离散数学(第三版)陈建明-刘国荣课后习题答案

离散数学辅助教材

概念分析结构思想与推理证明

第一部分

集合论

刘国荣

交大电信学院计算机系

离散数学习题解答

习题一(第一章集合)

1.列出下述集合的全部元素：

1)A={x\xEN/\x是偶数△x<\5］

2)B={x|x£NA4+x=3}

3)C={4r是十进制的数字}

［解］1)A={2,4,6,8,10,12,14)

2)B=0

3)C={0,1,2,3,4,5,6,7,8,9}

2.用谓词法表示下列集合：

1){奇整数集合}

2){小于7的非负整数集合}

3){3,5,7,11,13,17,19,23,29)

［解］1){n|nelA(3mGl)(n=2m+l)|；

2){nlnelAn>0An<7}；

3)(plpeNAp>2Ap<3()A-1(3deN)(d/1AdwpA0keN)(p=k・d)))。

3.确定下列各命题的真假性：

1)000

2)0G0

3)0c(0}

4)0E{0}

5){a,b}c{a,b,c,{a,b,c))

6){a,b}£(a,b,c,{a,b,c})

7){a,b|c{a,b,{{a,b,}})

8){a,b}G{a,b,{{a,b,})}

［解］1)真。因为空集是任意集合的子集；

2)假。因为空集不含任何元素；

3)真。因为空集是任意集合的子集；

4)真。因为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)如果A£B/\B£C,则A0C。

2)如果A&B/\B£C,则A&C。

3)如果AuB/XBWC,则A£C。

［解］1)假。例如A={a},B=(a,b),C={{a},{b}),从而AWB/XBEC但AWC。

2)假。例如A={a},B={a,{a}},C={{a},{{a}}},从而AWBABRC,但、A

eCo

3)假。例如A={a},B={a,b),C={{a},a,b},从而ACB八B£C,但A)C。

5.对任意集合A,B,C,确定下列命题的真假性：

1)如果ACBABqC,则A£C。

2)如果A£R/\HuC贝IJAu「c

3)如果AqBABGC,则A£C。

3)如果AqB/\B£C,则AqC。

［解］1)真。因为BqC=Wx(x£B=>x£C),1alitA6BnA£C。

2)假。例如A={a},B={{a),{b}),C={{a},{b},{c}}从而ARBABqC,但

A^Co

3)假。例如A={a},B={{a,b}},C={{a,{a,b}},从而AcBABeC,但A任C。

4)假。例如A={a},B={{a,b)},C={(a,b),b},从而AqB/\B£C,但A任C。

6.求下列集合的鼎集：

1){a,b,c)

2){a,{b,c)}

3){0}

4){0,{0}}

5){{a,b),{a,a,b},{a,b,a,b)}

［解］1){0,{a},{bj,{c},{a,b},{a,c},{b,c},{a,b,c}}

2){,{a},{{b,c}),{a,{a,b})}

3){0,{0}}

4){0,{0),{{0)},{0,{0})}

5){0，{{a,b})}

7.给定自然数集合N的下列子集：

A={1,2,7,8)

B={.标＜50}

C={MY可以被3整除且()&W30}

D={4r=2K,K£IA0WKW6}

列出下面集合的元素：

1)AUBUCUD

2)ADBACnD

3)B\(AUC)

4)(A'DB)UD

［解］因为B={1,2,3,4,5,6,7},C={3,6,9,12,15,18,21,24,27,30},

D={1,2,4,8,16,32,64,),故此

1)AUBUCUD={1,2,3,4,5,6,7,8,9,12,15,16,18,21,24,27,

30,32,64)

2)AABACnD=0

3)B\(AUC)={4,5)

4)(A'AB)UD={1,2,3,4,5,6,7,8,16,32,64}

8.设A、B、C是集合，证明：

1)(A\B)=A\(B\C)

2)(A\B)\C=(A\C)\(B\C)

3)(A\B)\C=(A\C)\B

［证明］1)方法一：(A\B)\C

=(ACIB')nc/(差集的定义)

=An(B‘nc')(交运算的结合律)

=AA(BUC)'(deMorgan律)

=A\(BUC)(差集的定义)

方法二：对任一元素入e(A\B)\C,贝iJxeC,同时，AEA\B,X《A,X足B,

所以，REA,xeBUC,即工£A\(BUC),由此可见(A\B)\CcA\(BUC)。

反之，对任一元素x£A\(BUC),则x£A,且xgBUC,也就是说x任A,x任B,

x^Co所以(A\B)\C,由此可见A\(BUC)q(A\B)\Co

因此A\(B\C)o

2)方法一：(A\B)\C

=A\(BUC)(根据1))

=A\(CUB)（并运算交换律）

=A\((CUB)AX)（0—1律）

=A\((CUB)A(CUCZ))（0—1律）

=A\(CU(Bnc/)（分配律）

=(A\C)\(Bncf)（根据I）

=(A\C)\(BCIC)（差集的定义）

方法二：对任一元素工&（A\B）\C,可知x/B,工/C,x£A\C。又由xeB,

x《B\C,xG(A\C)\(B\C)\(B\C)o所以(A\B)\Cq(A\C)\(B\C)。

反之，对任(A\C)\(B\C),可知x£A\C,x圮B\C。由x&A\C,可知x^A,

xcC。又因为x£B\C及x成C,可知"B。所以，xe(A\B)\C。因此(A\B)\Cq

(A\B)\Co

由此可得（A\B）\（B\C）c（A\B）\Co

3）方法一：（AC）\C

=A\（BUC）（根据1））

=A\（CUB）（并运算交换律）

=（A\C）\B（根据1））

方法二：对任一元素（A\B）\C,可知x£A,xeB,xeC。由为工£A,

x^C,所以，x£A\C。又由x成B,(A\C)\Bo所以，(A\B)\Cq(A\C)\B。

同理可证得(A\C)\Be(A\B)\C-

9.设A、B是X全集的子集，证明：

AqBoA'UB=X<=>APB,=0

［解］(采用循环证法)

⑴先证AqB=A'UB=X：

方法一：A'UB=A'U(AUB)（因为条件AqB及定理4）

二(A'UA)UB（U的结合律）

=(AUAZ)UB（U的交换律）

=XUB（互补律）

=X（零壹律）

方法二：AcB=>AUB=B（定理4）

=>B=AUB（等号二的对称性）

nA'UB=A'U(AUB)（两边同时左并上A'）

=>A/UB==(A,UA)UB（U的结合律）

nA'UB=(AUAZ)UB（U的交换律）

nA'UB=XUB（互补律）

=A'UB=X（零壹律）

方法三：因为A'qX且BqX,所以根据定理2的3，）就有A'UBcX；

另一方面，由于B&A'UB及根据换质位律可得B'三NqA'UB,因止匕,

由互补律及再次应用定理2的丁），可得X=BUB'qA'UB,即XqA'UB；

所以，A'UB=XO

(2)次证A'UB=XnAnB'=0；

A'UB=Xn(A'UB)Z=X'（两边同时取补运算'）

n(A‘)'OB'=XZ（deMorgan律）

nAGB'=X'（反身律）

=AAB'=X'（零壹律）

⑶再证AAR'=0nAuR：

方法一：A=AAX（零壹律）

=AA(BUB,)（互补律）

二(AGB)U(AAB')（分配律）

=(AAB)U0（条件AGB'=0）

二AAB（零壹律）

qB（定理2的3”

方法二：AGB'=0=>B=BU0（零壹律）

=BU(AAB,)（条件ACB'=0）

=(BUA)n(BUB/)（分配律）

=(AUB)A(BUB,)（U的交换律）

=(AUB)nX（互补律）

=AUB（零壹律）

=>AcB（定理4的2））

10.对于任意集合A,B,C,下列各式是否成立，为什么？

1）AUB=AUCnB=C

2)APB=AnC=>B=C

［解］1)不一定。例如:A={a},B={a,b),C={b}o显然有

AUB=AUC,ffiB^Co

2)不一定。例如:A={a［,B={a>b),C={b,c)o显然有

ACB二AAC,但BWC。

II.设A,B为集合，给出下列等式成立的充分必要条件：

1)A\B=B

2)A\B=B\A

3)AAB=AUB

4)A㊉B=A

［解］1)A\B=AAB,,由假设可知A\B二B,即AGB'=B。由此可知B=AGB'印’，

故此B=BGB'=0o

由假设可知A=A\0=A\B=B=0o所以当A\B=B时有A=B=00o

反之，当A=B=0时，显然A\B=B。

因此A\B=B的充分必要条件是A=B=0o

2)设A\BW60,则有元素a£A\B,那么，a£A,而由假设A\B=B\A。所以a

eR\A,从而a/A,矛盾"所以A\R二,故Au—另一方面由R\A二A\R=00可得

BeAo因此当A\B=B\A时，有人=8。

反之，当A=B时，显然A\B=B\A=0

因此，A\B=B\A的充要条件是A=B。

3)由于AUB=AHB,从而AqAUB=AGBqB,以及BqAUB:AGBqA故此A

UB=ACB,有A=Bo

5)根据定理6的1)有A㊉0=A,由已知条件A㊉B=A,可得A㊉B=A㊉0。

从而由对称差的消去律可得B=0o

反之，若B=0,则A㊉B=A㊉0=A。

所以A㊉B=A的充分必要条件为B=0o

12.对下列集合，画出其文图：

1)A'AB'

2)A\(BUC)'

3)AH(B'UC)

［解］

A'AB'尺(BUC)'AARUC)

13.用公式表示出下面图中的阴影部分

［解1

(AUBUC)U(AABnC)'

14.试用成员表法证明

1)(Ae)B)㊉C=A(B㊉C)

2)(AUB)n(BLC)qAB'

[W]1)成员表如下

ABCAeB(A㊉B)㊉CB㊉CA㊉(B㊉C)

0000000

0010111

0101111

0111000

1001101

1011010

1100010

1110101

成员表中运算结果㊉C及A㊉(B㊉C)的两列状态表明，全集中的每一个

体对它俩有相同的从属关系，故

(A㊉B)㊉C=A8(B㊉C)

1)成员表如下：

ABcAUB(BUC)(BUC)'(AUB)n(BUQ,B，AAB'

000001010

001010010

010110000

011110000

100101111

101110011

110110000

111110000

成员表中运算结果(AUB)n(BUC)'及AC1B'的两列状态表明，全

集中的每一个体，凡是从属(AUB)D(BUC)'的，都从属AAB，，故

(AUB)A(BUC)'cAAB

注：自然数集N取为{1,2,3,……，n,……}

习题二(第二章关系)

1.设A={1,2,3,},B={a,b}求

1)AXB2)BXA3)BXB4)2BXB

［解］1)AXB={(1,a),(1,b),(2,a),(2,a),(3,a),(3,b))

2)BXA={(a,1),(a,2),(a,3),(b,1),(b,2),(b,3)}

3)BXB={(a»a),(a,b),(b,a)(b.b)}

4)2B={0,{a},{b},{a,b}}

2BXB{(0,{a}),(0,b),({a},a),({a},b),((b),a),({b},b),

({a,b},b)}

2.使AqAXA成立的集合A存在吗？请阐明理由。

［解］一般地说，使AqAXA成立的集合A不存在，除非A=0。

否则AW0.则存在元素丫&AXA,故有yi，yaWA.使r=(yi，y?)，从

而yi，yz^AXA,故此有yi,y2,y3，y4，使y尸(yi»ya)»ya=(y3，yQ,...。

这说明A中每个元素x,其结构为元组的无穷次嵌套构成，这不可能。我们讨论

的元素的结构必须是由元组的有限次嵌套构成。

3.证明AXBnBXAoA=0VB=0VA=B

［证］必要性：即证AXB=BXA=A=0VB=0VA=B

若AXB=0,贝JA=0或者B=0

若AXB产0,则AK0且BH0,因此对任何x£A及任何y©B就有(x,

y)£AXB,根据AXB二BXA,可得(x,y)EBXA,故此可得x《B,yEA,

因此而得AcB旦BeA,所以由q的反对称性A=B。

充分性：即证A=0VB=0VA=B=AXB=BXA这是显然的。

4.证明(AGB)X(CAD)=(AXC)A(BXD)

［证］证法一：(元素法)对任一(x,y)E(APB)X(CAD)有x^AAB,y

eCAD,于是x£A,xEB,yEC,y£D。因而(x,y)eAXC,且(x,y)

eBXD,所以(x,y)£(AXC)n(BXD)。因而(AGB)X(CAD)c

(AXC)n(BXD)

另一方面，对任一(X,y)e(AXC)n(BXD),于是有(x,y)EAX

C且(x,y)EBXD,因而x£A,y£C,xeByEDo所以xSAAB,ye(C

AD)o所以(x,y)e(APB)X(CCD)。因而(AXC)A(BXD)c(A

AB)X(CnD)o

综合这两个方面有(AAB)X(CAD)=(AXC)A(BXD)。

证法二：(逻辑法)对任何x,y

(x,y)e(AAB)X(CnD)

=x£AClBAY£CCD

=>(xeAAXeB)A(ye0yeD)

z=>(xeAAyec)A(xeBAyeD)(人的结合律、交换律)

n(x,y)£AXCA(x,y)£BXD

n(x,y)£(AXC)A(BXD)

由x,y的任意性，可得：(AAB)X(CCD)=(AXC)n(BXD)。

5.下列各式中哪些成立，哪些不成立？对成立的式子给出证明，对不成立的式子给

出反例。

1)(AUB)X(CLD)=(AXC)U(BXD)

2)(A\R)X(CD)=(AXC)\(RXD)

3)(A㊉B)X(C©D)=(AXC)㊉(BXD)

4)(A\B)XC=(AXC)\(BXC)

5)(A㊉B)XC=(AXC)㊉(BXC)

［解］1)不成立。设人=⑶,B={b},C={c),D={d),则(a,-d)€(AUB)X

(CUD),但(a,・d)任(AXC)U：BXD)。所以(AUB)X(CU

D)=(AXC)U(BXD)不成立。事实上有：(AXC)U(BXD)c

(AUB)X(C)c(AUB)X(CUD)o

2)不成立。设人=⑻，B={b),C=D={c),则(a,c)e(AXC)\(BXD)但

(a,c)《(A\B)X(C\D)o因而(A\b)X(C\D)=(AXC)\(BXD)

不成立。事实上有：(A\B)X(C\D)&(AXC)\(BXD)o因为A\BqA,

C\Dc,故有(AXC)\(BXD)GAXC；又若(x,y)G(A\B)X(C\D)

故此x£A\B,从而x《B,y£C\D,从而y任D,故此(x,y)任BXD综合这

两方面，有(A\B)X(C\D)q(AXC)\(BXD)。

3)不成立。设A={a},B={b},C={a),D={b},则(a,b)e(A㊉B)X(C㊉D),

但(a,b)任(AXC)㊉(BXD)。所以(A㊉B)X(C㊉D)q(AXC)㊉(B

XD)不成立。又设A={a},B={b},C={a},D={c)则(a,c)e(AXC)㊉

(BXD),但(a,c)生(A㊉B)X(C㊉D)。所以(AXC)㊉(BXD)q(A㊉B)

X(C㊉D)不成立。因此(A㊉B)X(C㊉D)与(AXC)㊉(BXD)无任何

包含关系。总之(A㊉B)X(COD)=(AXC)㊉(BXD)不成立。

4)成立。证明如下：对任一(x,y)W(A\B)XC.有x£A,x《B,y£C于是(x,

y)0AXC,且(x,y)e(A\B)XC,且(x,y)任BXC(否则x£B),所以

(x,y)e(AXC)\(BXC)o因而

(A\B)XCq(AXC)\(BXC)。

又对任一(x,y)£(AXC)\(BXC),有(x,y)eAXC,且(x,y)

任BXC从而x£A,y@C及x任B。即x£A\B,y£C,故止匕(x,y)e(A\B)

XCo所以(AXC)\(BXC)q(AXB)XC。

因而(A\B)XC=(AXC)\(BXC)o

另一种证明方法：

(AXB)XC

=(AABr)XC(差集的定义)

=(AXC)A(B'XC)(叉积对交运算的分配律)

=(AXC)n(BXC)'

(因(BXC)'=(B’XC))n(BXC*)U(B'XC')

但(AXC)n(BXC)'=((AXC)n(B'XO)UO

=(AXC)n(B'XC))

=(AXC)n(B'XC)(差集的定义)

证法三：(逻辑法)对任何x,y

(x,y)E(AXC)\(BXC)

=>(x,y)GAXCA(x,y)eBXC

n(x£AAy£C)A(xgBvy/C)

=>(x£AAy£CAX^B)V(X6AAy£C/\y史C)(八对v的分配律)

=(x£AAX任BAy£C)v(x£AAy£C/\y任C)(△的结合律、交换律)

=>(xEAAXB)AyeC(八及v的零壹律、人的结合律)

=>x£A\BAyec

=>(x,y)£(A\B)XC

由x,y的任意性，可得：(A\B)XC=(AXC)\(BXC)。

5)成立。证明如下：对任一(x,y)W(A㊉B)XC,故此x《A㊉B,y£C于

是x£A且x史B,或者x^A且x£B。因此(x,y)£(AXC)㊉(BXC)。

所以(A㊉B)XCc(AXC)㊉(BXC)o

对任一(x,y)e(AXC)㊉(BXC)。则(x,y)WAXC且(x,y)

dBXC,或者(x,y)史AXC且(x,y)BXC。因此x£A,yC,x任B,或者x

£B,yec,x纪A。所以x£A\B,或x£B\A,并且yWC,故此x£A㊉B,ye

Co因此(x,y)e(A㊉B)XC,即(AXC)㊉(BXC)c(A㊉B)XC。

综合两方面、就有(A㊉B)XC=(AXC)㊉(BXC)

另一种证明方法：(A㊉B)XC

=((A\B)U(B\A))XC(对称差的定义)

=(((A\B)XC)((B\A)XC)(叉积对并运算的分配律)

=((AXC)\(BXC)U(BXC)\(AXC))(根据4))

=(AXC)㊉(BXC)(对称差的定义)

6.设A=［1,2,3},B={a),求出所有由A到B的关系。

FI

［解］:R(0,R={(1,a)},R2={(2,a)),R3={(3,a)},

R4={(1,a),(2,a)},Rs=((1,a),(3,a)),R6={(2,a),(3,a)),

R7={(1,a),(2,a),(3,a)}

7.设A={l,2,3,4}.R1={(I,3),(2.2),(3.4)},R2={(1,4),(2・3),

II

(3,4)),求：RUR2,R1GR2，R\R2，R/，D(Ri),D(R2),次(R)

次(R2),D(R1UR2),求(R|AR2)

［解］:R1UR2={(1,3),(1,4),(2,2),(2,3),(3,4)}

RIAR2={(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)}

(Ri)={1,2,3),(RI)={2,3,4),

(R2)={L2,3},次(R2)={3,4)

(R1UR2)={1,2,3},cR(RiPR：)={4}

8.对任意集合A及上的关系Ri和R2,证明

T)次(R|UR2)=次(RI)U/(R2)

I

2)次(RAR2)之双(Ri)G次(R2)

［证］1)一方面，由于RIGRIUR?,R2^RIUR2,根据定理1,有次(Ri)三火(Ri

UR2),次(R2)之衣(R|UR2)故

次(RI)U/(R2)G次(RiUR2)

I

另一方面，若x£次(RUR2)那么存在着y£A,使(y,x)e(R)U

R2)因此(y，x)GRi,或者(y,x)£R2,从而x匕火(Ri)或者x£/(R2)

O

于是x£<^(R］)U次(R2),所以次(R|UR2)匚次(Ri)U次(R2)

11.设A={1,2,3,4),定义A上的下列关系

Ri={(1,1),(1,2),(3,3),(3,4)},R2={(1,2),(2,1)}

R3={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=AXA,R?=0

请给出上述每一个关系的关系图与关系矩陈，并指出它具有的性质。

［解］:

10-------->02

1100

000

011

-1nn4

0000

X.

Ri是反对称的，传递的。

2)

0100

000

000

0000

R2是反自反的，对称的。

3)

1100、

100

011

0011

R3是自反的，对称的，传递的，因此是等价关系。循环的综合这两方面，就有

(RIUR2)二次(RI)(R2)o

2)由于R1GR2QR1，RIAR2CR2,根据定理1,有次(RiGR?)(Ri),次

(R1AR2)=Rz，所以次(R)nR2)口次(Ri)(R2)反方向的包含不

成立，反全由第7题可得，那里区(R|DR2)={4},(Ri)na(R2)={2,

3,4)0{3,4}={3,4}因此

队（Ri）次（R2）$（RIAR2）

9.设A有n个元素的有限集合，请指出A上有多少个二元关系？并阐明理由。

［解］A上有2n2个元关系。因为叉积AXA有n2个元素，因而AXA有2n2个子

集，而每个子集都是A上的一个二元关系。

10.定义在整数集合I上的相等关系、关系、“V”关系，全域关系，空关系，

是否具有表中所指的性质，请用Y（有）或N（元）将结果填在表中。

性质自反的反自反的对称的反对称的传递的

关系、\

相等关系YNYYY

〈关系YNNYY

〈关系NYNYY

全域关系YNYNY

空关系NYYYY

4)

0100

0001

R4=

0010

1000

R4是反对称的，循环的。

0111

0011

R5=

0001

1000

R5是反自反的，反对称的，传递的。

1o。21111

1111

R6=

1111

3。----4_1111

R6是自反的，对称的，传递的，循环的。从而是等价关系。

7)

1oO20000

R7是反三反的对称

0000

R7=的，传递的，循环

0000

的，反传递的，反

3。。40000

12.设A是A上的关系，证明

1）R是自反的当且反当IA^R

2）R是反自反的当且仅当IACR=0

3）R是对称的当且反当R二R

4）R是反对称的当且仅当RARML

5）R是传递的当且仅当RoRGR

［证］1）必要性

若R是自反的，则对任何x£A,都有（x,x）WR,但是IA={（x,x）|x

£A},所以IAUR。

充分性

若LUA则由L={（x,x）IxeA）,可知对任何x£A,都有（x,x）£R,

所以R是自反的。

2）必要性

若R是反自反的，则对任何x£A,都是（x,x）/R,从而（x,x）ER',

由IA={（x,x）|x£A}可知IAMR'。于是IACRUR'CR=0,另外OGIA^R，

所以IAGR=0。

充分性

若IACR=0，则R是反自反的。否则，不是反自反的，那么应存在某一xo

QA,使得（xo，xo）£R。但是（xo，xo）金L，从而（xo，x（））0。这不可能，

矛盾。

3）必要性，

若R是对称的，则对任何（x,y）&R,就有（y,x）WR。于是根据逆

关系的定义，可得（X,y）£R,于是RUR;对任何（x,y）£R,由逆关

系的定义，可得（y,x）ERo再次利用R的对称性有（y,x）£R,于是Ri

R；综合两方面，有R二R。

充分性

若R=R,则对任何（x,y）WR,由R=R可得（x,y）WR。从而由

逆关系的定义，可知（y,x）WR这说明R是对称的。

4）必要性

若R是反对称的，则对任何（x,y）eR,即有（x,y）£R及（x,y）

eR,从逆关系的定义，就有（x,y）eR及（y,x）eR,因此，利用R的

反对称性，可得x=y。于是就有（x,y）=（x,x）eiA,所以RAR

充分性

若RGRCJA,则对任何（x,y）eR及（y,x）eR,从逆R关系的定

义，可得（x,y）&R及（x,y）eR,也即（K,y）&RAR,利用RClR=IA

可得（x,y）eiA,于是x=y。所以R是反对称的。

5）必要性

若R是传递的，则对任何（x,y）RoR,由复合关系的定义可知，存在着

yWA,使（x,y）ER且（y,y）eR,从而利用R的传递性，可知（x,y）£

Ro所以

RORCRC

充分性

RoRo从而利用RoRGR可得（x,y）£R。所以R是传递的。

证法二：

l）n）:对任何x,

x£A

=＞（X,X）0IA（IA是幺关系，因此是自反关系）

=＞（x,x）ER（R是自反关系）

所以L.R;

＜=）:对任何x£A,

x&A

=＞（X,X）WIA（IA是幺关系，因此是自反关系）

n（x,x）£R（因IACR）

所以，R是自反关系；

2）n）首先0UACR；

其次，对任何x,y£A,若

(x,y)eiAnR

=>(x,y)eiAA(x,y)€R

^x=yA(x,y)eR(IA是幺关系，因此是自反关系)

=>(x,x)£R

则与R是反自反关系，(x,x)eR矛盾。故IACR=0；

因此，由包含关系q的反对称性，可得IAnR=0；

<=):对任何x《A,若

(x,x)£R

n(x,x)eIAA(X,X)£R(IA是幺关系，因此是自反关系)

=(X,X)6IACR

=>(x,x)e0(因IAnR=0)

则与空集不含任何元素，(x,x)任0矛盾。

故对任何x£A,(x,x)夕R:

所以，R是反自反关系；

3)=>)对任何x,y£A

(x,y)WR

o(y,x)£R(R是对称关系)

o(x,y)eR

所以，R=R；

<=):对任何x,yeA

(x,y)£R

n(x,y)@R(R=R)

n(y,x)£R

所以，R是对称的；

4)n)对任何x,yeA

(x,y)eRnR

n(x,y)£RA(x,y)£R

=>(x,y)eRA(y,x)eR

=>x=y(R是反对称关系)

=>(x,y)eiA(IA是自反关系)

所以，RnRCIA；

<=):对任何x,y£A

(x,y)£R

=>(x,y)eR(R=R)

=(y,x)£R

所以，R是对称的;

13.设A、B为有穷集合，R,SUAXB,MR=（xy）mxn,Ms=（yij）mxn

1）为了RGS,必须且只须VHj（Xij<

2）设MRus二（Zij）mXn,那么Zg=XijVyij,1=1,2....,m,j=l,2,....n.

3）设MR”=（tij）n】Xn,那么用二x『yij

i=l,2,....m；j=l,2,....,n.

［证］由于A、B是有穷集合，不妨设

A={aua2....,am}，B={bi，b2,....，bn}

1）必要性

若RMS,则对任何i£{l,2,……，m},对任何j£{l,2,……n）,若（出,

bj）£R,则R的关系矩阵MR=（Xij）mxn中第1行第j列元素Xij=l,根据RGS,

可得（％bj）£S,从而得S的关系矩阵Ms=（yij）mxn中第I行第j列元素yij=l，

由于是I故此XijWyij：若（％,bj）/R,则R的关系矩阵MR=（xq）mxn中

第i行第j列元素X产0,因此由S的关系矩阵MS=（yij）mxn中第j列元素均20,

可得XijWyij。总之，有（Vj）（Vj）（Xij^yij）o

2）充分性

若（V。（Vj）（xijWyij）,则对任何（a,bj）eR,就有R的关系

矩阵MR=（xpmxn中第i行第j列元素xij=l,由于XijWyu，所以yij21,故

此yij'l这说明S的关系矩阵Ms=（yij）中第i行第j列元素yij为1，因此必

有

（a,bj）es,所以RGS。

2）对任何i£{l,2,……，m},对任何j£{l,2,……，n}若Zij=l,贝J（ai,

bj）ERUS,故此（*,bj）£R或者（a”bj）ES,于是Xij=l或者yrl。从而

bj）空S,于是Xij=0且yij=O。从而XijVyij=0。因而Zg=Xij丫丫产0；

综合上述两种情况,就有Zji=XijVyij,i=l,2,....,m,j=l,2,....n,o

3）对任何i£{l,2,……m},对任何j£{l,2,……,n}。若看=1,则（为，

bj）ERAS,故此（出，bj）£S且（%,bj）WS,于是Xij=l,且丫产1从而XijA

yij=1o因而tij=Xij/\yij=l；若tij=O,则（编,bj）年ROS,故此（a,,bj）qS,于

是Xij=O或者yij=O,从而xq八yij=O0因而局=乂0丫产0。

综合上述两种情况，就有tij=Xij八丫中i=L2,...,m,j=1,2,....,n。

14.设A={1,2,3,4},Ri，R2为A上的关系,Rl={(I,1),(1,2),(2,4)),

R2={(1,4),(2,3),(2,4),(3,2)},求R0R2,R2ORI，RioR2。R】R；

-110o-0001

00010011

［解1MR、='MR=

000020100

00000000

1)

-

110o--o001--o011

000100110000

—

MR„=Mf_>oM0

/<2000001000000

000000000000

1O1o1O

2。2o