離散數(shù)學(xué)(第三版)陳建明-劉國(guó)榮課后習(xí)題答案

離散數(shù)學(xué)輔助教材

概念分析結(jié)構(gòu)思想與推理證明

第一部分

集合論

劉國(guó)榮

交大電信學(xué)院計(jì)算機(jī)系

離散數(shù)學(xué)習(xí)題解答

習(xí)題一(第一章集合)

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

1)A={x\xEN/\x是偶數(shù)△x<\5］

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

3)C={4r是十進(jìn)制的數(shù)字}

［解］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){奇整數(shù)集合}

2){小于7的非負(fù)整數(shù)集合}

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)真。因?yàn)榭占侨我饧系淖蛹?/p>

2)假。因?yàn)榭占缓魏卧兀?/p>

3)真。因?yàn)榭占侨我饧系淖蛹?/p>

4)真。因?yàn)?是集合{0}的元素；

5)真。因?yàn)閧a,b}是集合{a,b,c,{a,b,c}}的子集;

6)假。因?yàn)閧a,b}不是集合{a,b,c,{a,b,c}}的元素；

7)真。因?yàn)閧a,b}是集合{a,b,{{a,b}}}的子集;

8)假。因?yàn)閧a,b}不是集合{a,b,{{a,b}}}的元素。

4.對(duì)任意集合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},),從而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.對(duì)任意集合A,B,C,確定下列命題的真假性：

1)如果ACBABqC,則A￡C。

2)如果A￡R/\HuC貝IJAu「c

3)如果AqBABGC,則A￡C。

3)如果AqB/\B￡C,則AqC。

［解］1)真。因?yàn)锽qC=Wx(x￡B=>x￡C),1alitA6BnA￡C。

2)假。例如A={a},B={{a),),C={{a},,{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.給定自然數(shù)集合N的下列子集：

A={1,2,7,8)

B={.標(biāo)＜50}

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

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

列出下面集合的元素：

1)AUBUCUD

2)ADBACnD

3)B\(AUC)

4)(A'DB)UD

［解］因?yàn)锽={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.設(shè)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')(交運(yùn)算的結(jié)合律)

=AA(BUC)'(deMorgan律)

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

方法二：對(duì)任一元素入e(A\B)\C,貝iJxeC,同時(shí)，AEA\B,X《A,X足B,

所以，REA,xeBUC,即工￡A\(BUC),由此可見(jiàn)(A\B)\CcA\(BUC)。

反之，對(duì)任一元素x￡A\(BUC),則x￡A,且xgBUC,也就是說(shuō)x任A,x任B,

x^Co所以(A\B)\C,由此可見(jiàn)A\(BUC)q(A\B)\Co

因此A\(B\C)o

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

=A\(BUC)(根據(jù)1))

=A\(CUB)（并運(yùn)算交換律）

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

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

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

=(A\C)\(Bncf)（根據(jù)I）

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

方法二：對(duì)任一元素工&（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)。

反之，對(duì)任(A\C)\(B\C),可知x￡A\C,x圮B\C。由x&A\C,可知x^A,

xcC。又因?yàn)閤￡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）（根據(jù)1））

=A\（CUB）（并運(yùn)算交換律）

=（A\C）\B（根據(jù)1））

方法二：對(duì)任一元素（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.設(shè)A、B是X全集的子集，證明：

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

［解］(采用循環(huán)證法)

⑴先證AqB=A'UB=X：

方法一：A'UB=A'U(AUB)（因?yàn)闂l件AqB及定理4）

二(A'UA)UB（U的結(jié)合律）

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

=XUB（互補(bǔ)律）

=X（零壹律）

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

=>B=AUB（等號(hào)二的對(duì)稱(chēng)性）

nA'UB=A'U(AUB)（兩邊同時(shí)左并上A'）

=>A/UB==(A,UA)UB（U的結(jié)合律）

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

nA'UB=XUB（互補(bǔ)律）

=A'UB=X（零壹律）

方法三：因?yàn)锳'qX且BqX,所以根據(jù)定理2的3，）就有A'UBcX；

另一方面，由于B&A'UB及根據(jù)換質(zhì)位律可得B'三NqA'UB,因止匕,

由互補(bǔ)律及再次應(yīng)用定理2的丁），可得X=BUB'qA'UB,即XqA'UB；

所以，A'UB=XO

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

A'UB=Xn(A'UB)Z=X'（兩邊同時(shí)取補(bǔ)運(yùn)算'）

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

nAGB'=X'（反身律）

=AAB'=X'（零壹律）

⑶再證AAR'=0nAuR：

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

=AA(BUB,)（互補(bǔ)律）

二(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（互補(bǔ)律）

=AUB（零壹律）

=>AcB（定理4的2））

10.對(duì)于任意集合A,B,C,下列各式是否成立，為什么？

1）AUB=AUCnB=C

2)APB=AnC=>B=C

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

AUB=AUC,ffiB^Co

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

ACB二AAC,但BWC。

II.設(shè)A,B為集合，給出下列等式成立的充分必要條件：

1)A\B=B

2)A\B=B\A

3)AAB=AUB

4)A十B=A

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

故此B=BGB'=0o

由假設(shè)可知A=A\0=A\B=B=0o所以當(dāng)A\B=B時(shí)有A=B=00o

反之，當(dāng)A=B=0時(shí)，顯然A\B=B。

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

2)設(shè)A\BW60,則有元素a￡A\B,那么，a￡A,而由假設(shè)A\B=B\A。所以a

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

BeAo因此當(dāng)A\B=B\A時(shí)，有人=8。

反之，當(dāng)A=B時(shí)，顯然A\B=B\A=0

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

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

UB=ACB,有A=Bo

5)根據(jù)定理6的1)有A十0=A,由已知條件A十B=A,可得A十B=A十0。

從而由對(duì)稱(chēng)差的消去律可得B=0o

反之，若B=0,則A十B=A十0=A。

所以A十B=A的充分必要條件為B=0o

12.對(duì)下列集合，畫(huà)出其文圖：

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

成員表中運(yùn)算結(jié)果十C及A十(B十C)的兩列狀態(tài)表明，全集中的每一個(gè)

體對(duì)它倆有相同的從屬關(guān)系，故

(A十B)十C=A8(B十C)

1)成員表如下：

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

000001010

001010010

010110000

011110000

100101111

101110011

110110000

111110000

成員表中運(yùn)算結(jié)果(AUB)n(BUC)'及AC1B'的兩列狀態(tài)表明，全

集中的每一個(gè)體，凡是從屬(AUB)D(BUC)'的，都從屬AAB，，故

(AUB)A(BUC)'cAAB

注：自然數(shù)集N取為{1,2,3,……，n,……}

習(xí)題二(第二章關(guān)系)

1.設(shè)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},,{a,b}}

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

({a,b},b)}

2.使AqAXA成立的集合A存在嗎？請(qǐng)闡明理由。

［解］一般地說(shuō)，使AqAXA成立的集合A不存在，除非A=0。

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

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

這說(shuō)明A中每個(gè)元素x,其結(jié)構(gòu)為元組的無(wú)窮次嵌套構(gòu)成，這不可能。我們討論

的元素的結(jié)構(gòu)必須是由元組的有限次嵌套構(gòu)成。

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

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

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

若AXB產(chǎn)0,則AK0且BH0,因此對(duì)任何x￡A及任何y?B就有(x,

y)￡AXB,根據(jù)AXB二BXA,可得(x,y)EBXA,故此可得x《B,yEA,

因此而得AcB旦BeA,所以由q的反對(duì)稱(chēng)性A=B。

充分性：即證A=0VB=0VA=B=AXB=BXA這是顯然的。

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

［證］證法一：(元素法)對(duì)任一(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)

另一方面，對(duì)任一(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

綜合這兩個(gè)方面有(AAB)X(CAD)=(AXC)A(BXD)。

證法二：(邏輯法)對(duì)任何x,y

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

=x￡AClBAY￡CCD

=>(xeAAXeB)A(ye0yeD)

z=>(xeAAyec)A(xeBAyeD)(人的結(jié)合律、交換律)

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

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

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

5.下列各式中哪些成立，哪些不成立？對(duì)成立的式子給出證明，對(duì)不成立的式子給

出反例。

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)不成立。設(shè)人=⑶,B=,C={c),D={d),則(a,-d)€(AUB)X

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

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

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

2)不成立。設(shè)人=⑻，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)

不成立。事實(shí)上有：(A\B)X(C\D)&(AXC)\(BXD)o因?yàn)锳\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)不成立。設(shè)A={a},B=,C={a),D=,則(a,b)e(A十B)X(C十D),

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

XD)不成立。又設(shè)A={a},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)無(wú)任何

包含關(guān)系?？傊?A十B)X(COD)=(AXC)十(BXD)不成立。

4)成立。證明如下：對(duì)任一(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)。

又對(duì)任一(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)(叉積對(duì)交運(yùn)算的分配律)

=(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)(差集的定義)

證法三：(邏輯法)對(duì)任何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)(八對(duì)v的分配律)

=(x￡AAX任BAy￡C)v(x￡AAy￡C/\y任C)(△的結(jié)合律、交換律)

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

=>x￡A\BAyec

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

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

5)成立。證明如下：對(duì)任一(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

對(duì)任一(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紀(jì)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(對(duì)稱(chēng)差的定義)

=(((A\B)XC)((B\A)XC)(叉積對(duì)并運(yùn)算的分配律)

=((AXC)\(BXC)U(BXC)\(AXC))(根據(jù)4))

=(AXC)十(BXC)(對(duì)稱(chēng)差的定義)

6.設(shè)A=［1,2,3},B={a),求出所有由A到B的關(guān)系。

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.設(shè)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.對(duì)任意集合A及上的關(guān)系Ri和R2,證明

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

I

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

［證］1)一方面，由于RIGRIUR?,R2^RIUR2,根據(jù)定理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.設(shè)A={1,2,3,4),定義A上的下列關(guān)系

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

請(qǐng)給出上述每一個(gè)關(guān)系的關(guān)系圖與關(guān)系矩陳，并指出它具有的性質(zhì)。

［解］:

10-------->02

1100

000

011

-1nn4

0000

X.

Ri是反對(duì)稱(chēng)的，傳遞的。

2)

0100

000

000

0000

R2是反自反的，對(duì)稱(chēng)的。

3)

1100、

100

011

0011

R3是自反的，對(duì)稱(chēng)的，傳遞的，因此是等價(jià)關(guān)系。循環(huán)的綜合這兩方面，就有

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

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

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

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

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

隊(duì)（Ri）次（R2）$（RIAR2）

9.設(shè)A有n個(gè)元素的有限集合，請(qǐng)指出A上有多少個(gè)二元關(guān)系？并闡明理由。

［解］A上有2n2個(gè)元關(guān)系。因?yàn)椴娣eAXA有n2個(gè)元素，因而AXA有2n2個(gè)子

集，而每個(gè)子集都是A上的一個(gè)二元關(guān)系。

10.定義在整數(shù)集合I上的相等關(guān)系、關(guān)系、“V”關(guān)系，全域關(guān)系，空關(guān)系，

是否具有表中所指的性質(zhì)，請(qǐng)用Y（有）或N（元）將結(jié)果填在表中。

性質(zhì)自反的反自反的對(duì)稱(chēng)的反對(duì)稱(chēng)的傳遞的

關(guān)系、\

相等關(guān)系YNYYY

〈關(guān)系YNNYY

〈關(guān)系NYNYY

全域關(guān)系YNYNY

空關(guān)系NYYYY

4)

0100

0001

R4=

0010

1000

R4是反對(duì)稱(chēng)的，循環(huán)的。

0111

0011

R5=

0001

1000

R5是反自反的，反對(duì)稱(chēng)的，傳遞的。

1o。21111

1111

R6=

1111

3。----4_1111

R6是自反的，對(duì)稱(chēng)的，傳遞的，循環(huán)的。從而是等價(jià)關(guān)系。

7)

1oO20000

R7是反三反的對(duì)稱(chēng)

0000

R7=的，傳遞的，循環(huán)

0000

的，反傳遞的，反

3。。40000

12.設(shè)A是A上的關(guān)系，證明

1）R是自反的當(dāng)且反當(dāng)IA^R

2）R是反自反的當(dāng)且僅當(dāng)IACR=0

3）R是對(duì)稱(chēng)的當(dāng)且反當(dāng)R二R

4）R是反對(duì)稱(chēng)的當(dāng)且僅當(dāng)RARML

5）R是傳遞的當(dāng)且僅當(dāng)RoRGR

［證］1）必要性

若R是自反的，則對(duì)任何x￡A,都有（x,x）WR,但是IA={（x,x）|x

￡A},所以IAUR。

充分性

若LUA則由L={（x,x）IxeA）,可知對(duì)任何x￡A,都有（x,x）￡R,

所以R是自反的。

2）必要性

若R是反自反的，則對(duì)任何x￡A,都是（x,x）/R,從而（x,x）ER',

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

所以IAGR=0。

充分性

若IACR=0，則R是反自反的。否則，不是反自反的，那么應(yīng)存在某一xo

QA,使得（xo，xo）￡R。但是（xo，xo）金L，從而（xo，x（））0。這不可能，

矛盾。

3）必要性，

若R是對(duì)稱(chēng)的，則對(duì)任何（x,y）&R,就有（y,x）WR。于是根據(jù)逆

關(guān)系的定義，可得（X,y）￡R,于是RUR;對(duì)任何（x,y）￡R,由逆關(guān)

系的定義，可得（y,x）ERo再次利用R的對(duì)稱(chēng)性有（y,x）￡R,于是Ri

R；綜合兩方面，有R二R。

充分性

若R=R,則對(duì)任何（x,y）WR,由R=R可得（x,y）WR。從而由

逆關(guān)系的定義，可知（y,x）WR這說(shuō)明R是對(duì)稱(chēng)的。

4）必要性

若R是反對(duì)稱(chēng)的，則對(duì)任何（x,y）eR,即有（x,y）￡R及（x,y）

eR,從逆關(guān)系的定義，就有（x,y）eR及（y,x）eR,因此，利用R的

反對(duì)稱(chēng)性，可得x=y。于是就有（x,y）=（x,x）eiA,所以RAR

充分性

若RGRCJA,則對(duì)任何（x,y）eR及（y,x）eR,從逆R關(guān)系的定

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

可得（x,y）eiA,于是x=y。所以R是反對(duì)稱(chēng)的。

5）必要性

若R是傳遞的，則對(duì)任何（x,y）RoR,由復(fù)合關(guān)系的定義可知，存在著

yWA,使（x,y）ER且（y,y）eR,從而利用R的傳遞性，可知（x,y）￡

Ro所以

RORCRC

充分性

RoRo從而利用RoRGR可得（x,y）￡R。所以R是傳遞的。

證法二：

l）n）:對(duì)任何x,

x￡A

=＞（X,X）0IA（IA是幺關(guān)系，因此是自反關(guān)系）

=＞（x,x）ER（R是自反關(guān)系）

所以L.R;

＜=）:對(duì)任何x￡A,

x&A

=＞（X,X）WIA（IA是幺關(guān)系，因此是自反關(guān)系）

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

所以，R是自反關(guān)系；

2）n）首先0UACR；

其次，對(duì)任何x,y￡A,若

(x,y)eiAnR

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

^x=yA(x,y)eR(IA是幺關(guān)系，因此是自反關(guān)系)

=>(x,x)￡R

則與R是反自反關(guān)系，(x,x)eR矛盾。故IACR=0；

因此，由包含關(guān)系q的反對(duì)稱(chēng)性，可得IAnR=0；

<=):對(duì)任何x《A,若

(x,x)￡R

n(x,x)eIAA(X,X)￡R(IA是幺關(guān)系，因此是自反關(guān)系)

=(X,X)6IACR

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

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

故對(duì)任何x￡A,(x,x)夕R:

所以，R是反自反關(guān)系；

3)=>)對(duì)任何x,y￡A

(x,y)WR

o(y,x)￡R(R是對(duì)稱(chēng)關(guān)系)

o(x,y)eR

所以，R=R；

<=):對(duì)任何x,yeA

(x,y)￡R

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

n(y,x)￡R

所以，R是對(duì)稱(chēng)的；

4)n)對(duì)任何x,yeA

(x,y)eRnR

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

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

=>x=y(R是反對(duì)稱(chēng)關(guān)系)

=>(x,y)eiA(IA是自反關(guān)系)

所以，RnRCIA；

<=):對(duì)任何x,y￡A

(x,y)￡R

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

=(y,x)￡R

所以，R是對(duì)稱(chēng)的;

13.設(shè)A、B為有窮集合，R,SUAXB,MR=（xy）mxn,Ms=（yij）mxn

1）為了RGS,必須且只須VHj（Xij<

2）設(shè)MRus二（Zij）mXn,那么Zg=XijVyij,1=1,2....,m,j=l,2,....n.

3）設(shè)MR”=（tij）n】Xn,那么用二x『yij

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

［證］由于A、B是有窮集合，不妨設(shè)

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

1）必要性

若RMS,則對(duì)任何i￡{l,2,……，m},對(duì)任何j￡{l,2,……n）,若（出,

bj）￡R,則R的關(guān)系矩陣MR=（Xij）mxn中第1行第j列元素Xij=l,根據(jù)RGS,

可得（％bj）￡S,從而得S的關(guān)系矩陣Ms=（yij）mxn中第I行第j列元素yij=l，

由于是I故此XijWyij：若（％,bj）/R,則R的關(guān)系矩陣MR=（xq）mxn中

第i行第j列元素X產(chǎn)0,因此由S的關(guān)系矩陣MS=（yij）mxn中第j列元素均20,

可得XijWyij?？傊校╒j）（Vj）（Xij^yij）o

2）充分性

若（V。（Vj）（xijWyij）,則對(duì)任何（a,bj）eR,就有R的關(guān)系

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

此yij'l這說(shuō)明S的關(guān)系矩陣Ms=（yij）中第i行第j列元素yij為1，因此必

有

（a,bj）es,所以RGS。

2）對(duì)任何i￡{l,2,……，m},對(duì)任何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丫丫產(chǎn)0；

綜合上述兩種情況,就有Zji=XijVyij,i=l,2,....,m,j=l,2,....n,o

3）對(duì)任何i￡{l,2,……m},對(duì)任何j￡{l,2,……,n}。若看=1,則（為，

bj）ERAS,故此（出，bj）￡S且（%,bj）WS,于是Xij=l,且丫產(chǎn)1從而XijA

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

是Xij=O或者yij=O,從而xq八yij=O0因而局=乂0丫產(chǎn)0。

綜合上述兩種情況，就有tij=Xij八丫中i=L2,...,m,j=1,2,....,n。

14.設(shè)A={1,2,3,4},Ri，R2為A上的關(guān)系,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