《離散的數(shù)學(xué)結(jié)構(gòu)》課后習(xí)題答案

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

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

第一部分

集合論

劉國榮

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

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

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

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

1)A={xlxGN△尤是偶數(shù)人x<15}

2)B={xLxeNA4+x=3}

3)C={xLr是十進(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(3meI)(n=2m+l)}；

2){n|nGlAn>0An<7}；

3){plpeNAp>2Ap<30A-1(3deN)(d*1Ad^pA(3keN)(p=k-d))}o

3.確定下列各命題的真假性：

1)0c0

2)0￡0

3)0c{0}

4)0e{0}

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

6){a,b}G(a,b,c,{a>b>c})

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

8){a,b}e{a,b,{{a,b,}}}

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

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

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

4)真。因為0是集合{0}的元素；

5)真。因為{a,b}是集合{a,b,c,{a,b,c}}的子集；

6)假。因為{a,b}不是集合{a,b,c,{a,b,c}}的元素；

2

7）真。因為{a,b}是集合{a,b,{{a,b}}}的子集；

8）假。因為{a,暇不是集合{a,b,{{a,b}}}的元素。

4.對任意集合A,B,C,確定下列命題的真假性：

1）如果AWBABGC,貝IJAGC。

2）如果A6BABGC,貝IJA6C。

3）如果AuBABdC,則AWC。

［解］1）假。例如A={a},B={a,b},C={{a},},從而AWBABWC但AWC。

2）假。例如A={a},B={a,{a}},C={{a},{{a}}},從而AGBABGC,但、A

GCo

3）假。例如A={a},B={a,b},C={{a},a,b},從而ACBAB^C,但AdC。

5.對任意集合A,B,C,確定下列命題的真假性：

I）如果AGBABqC,貝IjAGC。

2）如果AeBABqC，貝ijAuC。

3）如果AaBABGC,則AGC。

3）如果AuBABCC,貝IJA?。

［解J1）真。因為BuCoVx（xGBnxdC）,因此AGBnAGC。

2）假。例如A={a},B={{a},},C={{a},,{c}}從而ABBAB=C,但

AeC。

3）假。例如A={a},B={{a,b}},C={{a,{a,b}},從而A=BABGC,但A史C。

4）假。例如A={a},B={{a,b}},C={{a,b},b},AWAGBABGC,但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},,{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的下列子集：

3

A={1,2,7,8}

B={xLr2<50}

C={x\x可以被3整除且0WxW30}

D={%lx=2K,KGI/\0WKW6}

列出下面集合的元素：

1)AUBUCUD

2)AABncnD

3)B\(AUC)

4)(A*AB)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)AABncnD=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

=(AAB')ncz（差集的定義）

=AA(B'ncz)（交運算的結(jié)合律）

=AA(BUC)'（deMorgan律）

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

方法二：對任一元素xd(A\B)\C,則xeC,同時，xGA\B,xGA,

所以，xCA,xgBUC,B|1X￡A\(BUC),由此可見(A\B)\C［A\(BUC)。

反之，對任一元素xGA\(BUC),貝IJxGA,且元史BUC,也就是說xeA,xwB,

xeC。所以xG(A\B)\C,由此可見A\(BUC)c(A\B)\C。

因此;A\(B\C)?

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

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

4

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

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

=A\((CUB)n(CUC;))（0—1律）

=A\(CU(BCC')（分配律）

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

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

方法二：對任一元素xG（A\B）\C,可知xGA,xeB,xeC,xGA\C。又山xeB,

xeB\C,xG(A\C)\(B\C)\(B\C)?所以(A\B)\Ca(A\C)\(B\C),

反之，對任xW(A\C)\(B\C),可知xGA\C,xeB\C。由xGA\C,可知x^A,

x￡C。又因為xeB\C及xeC,可知xtB。所以，xG(A\B)\C。因此(A\B)\Cc

(A\B)\Co

由此可得(A\B)\(B\C)c(A\B)\Co

3)方法一：(A\C)\C

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

=A\(CUB)(并運算交換律)

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

方法二：對任一元素xW（A\B）\C,可知xCA,xeB,xgCo由為xCA,

x^C,所以，xGA\C。又由x任B,xd(A\C)\B。所以，(A\B)\Cc(A\C)\B。

同理可證得(A\C)\Bc(A\B)\C?

9.設(shè)A、B是X全集的子集，證明：

A=B=A'UB=XoACB'=0

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

⑴先證AqBnA'UB=X；

方法一：A'UB=A，U(AUB)（因為條件A=B及定理4）

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

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

=XUB（互補律）

=X（零壹律）

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

nB=AUB（等號=的對稱性）

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

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

5

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

nA'UB=XUB（互補律）

nA'UB=X（零壹律）

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

另?方面，由于BqA'UB及根據(jù)換質(zhì)位律可得B'qA'qA'UB,因此,

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

所以，A'UB=X0

(2)次證A'UB=X=AnB'=0；

A'UB=X=>(A,UB)'=X'（兩邊同時取補運算'）

=(A')'OB'=X'(deMorgan律)

nAAB'=X'（反身律）

=ACB'=X'（零壹律）

(3)再證ACB'=0=>AcB；

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

=AC(BUB')（互補律）

=(AnB)u(AnB/)（分配律）

=(AAB)U0(條件ACB'=0)

=AAB（零壹律）

cB（定理2的3））

方法二：ACB，=0=B=BU0（零壹律）

=BU(ACB')(條件APIB'=0)

=(BUA)A(BUB,)（分配律）

=(AUB)A(BUB，)（U的交換律）

=(AUB)AX（互補律）

=AUB（零壹律）

=>AcB（定理4的2））

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

1）AUB=AUC=B=C

2）AC!B=AnCnB=C

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

AUB=AUC,但BWC。

2）不一定。例如:A={a},B={a,b},C={b,c）,顯然有

6

AClB=AnC,但BWC。

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

1)A\B=B

2)A\B=B\A

3)AAB=AUB

4)A十B=A

［解］1)A\B=AnB',由假設(shè)可知A\B=B,即APB'=B。由此可知B=ACB'cBz,

故此B=BCB'=0。

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

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

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

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

eB\A,從而aeA,矛盾。所以A\B=,故AqB。另一方面由B\A=A\B=0?？傻?/p>

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

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

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

3)由于AUB=ACB,從而AaAUB=ACBuB,以及B^AUB=ACBqA故此A

UB=AAB,WA=B,

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

從而由對稱差的消去律可得B=0o

反之，若B=0,貝I」A十B=A十0=A。

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

12.對下列集合，畫出其文圖：

1)A'CIB'

2)A\(BUC)'

3)ACl(B'UC)

［解］

ACB'A(BUC)'An(B(UC)

7

13.用公式表示出下面圖中的陰影部分

闡

(AUBUC)U(AnBnO,

14.試用成員表法證明

1)(A十B)十C=A(B?C)

2)(AUB)n(BUC)GAB

［解］1）成員表如下

ABCA十B(A十B)十CB十CA十(B十C)

0000000

0010111

0101111

0111000

1001101

1011010

1100010

1110101

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

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

（A十B）十C=A十（B十C）

1）成員表如下：

ABCAUB(BUC)(BUC)'(AUB)n(BUC)/B，AAB,

000001010

001010010

010110000

011110000

100101111

101110011

110110000

111110000

8

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

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

(AUB)n(BUC)'cAOB

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

9

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

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

（{a,b},b）}

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

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

否則A六0,則存在元素xCAXA,故有yi，yz^A,使》=（y「y2）.從

而yi，y2eAXA,故此有y”y2,y3,y4,使y〕=（y］,y2）（y?=（丫3，yQ，...。

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

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

3.證明AXB=BXAoA=0VB=0VA=B

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

若AXB=0,則A=0或者B=0

若AXB#0,則A#0且BW0,因此對任何xGA及任何yGB就有(x,

y)GAXB,根據(jù)AXB=BXA,可得(x,y)GBXA,故此可得x￡B,yGA,

因此而得A±B且BqA,所以由1的反對稱性A=B。

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

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

［證］證法一：(元素法)對任一(x,y)e(AAB)X(CAD)有x^ACB,y

GCCD,于是xdA,xGB,yGC,yGD。因而(x,y)GAXC,且(x,y)

SBXD,所以(x,y)e(AXC)A(BXD)。因而(AC1B)X(CCD)c

(AXC)A(BXD)

另一方面，對任一(x,y)e(AXC)n(BXD),于是有(x,y)RAX

C且(x,y)GBXD,因而xGA,yGC,xGByGD。所以xGAAB,ye(C

AD)。所以(x,y)e(AAB)X(CAD)。因而(AXC)n(BXD)c(A

AB)X(CAD)o

10

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

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

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

=x￡AGBAY￡CCD

=>(x￡AAXeB)A(yGCAyGD)

^(xGAAYeC)A(xeBAYCD)(人的結(jié)合律、交換律)

=>(x,y)WAXCA(x,y)WBXD

=(x,y)e(AXC)C(BXD)

由x,y的任意性，可得：(ACB)X(CnD)=(AXC)C(BXD)。

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

出反例。

I)(AUB)X(CUD)=(AXC)U(BXD)

2)(A\B)X(C\D)=(AXC)\(BXD)

3)(A?B)X((^D)=(AXC)?(BXD)

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

5)WB)XC=(AXC)?(BXC)

［解］1)不成立?設(shè)人=履},B=,C={c},D=6116111,則(a,-d)e(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),

2)不成立。設(shè)人=e},B=,C=D={c},則(a,c)G(AXC)\(BXD)但

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

不成立。事實上有：(A\B)X(C\D)c(AXC)\(BXD)?因為A\BqA,

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

故此xGA\B,從而xeB,yeC\D,從而yeD,故此(x,y)eBXD綜合這

兩方面，有(A\B)X(C\D)a(AXC)\(BXD)。

3)不成立。設(shè)人=h},B=,C={a},D=,則(a,b)e(A十B)X(C十D),

但(a,b)￡(AXC)?(BXD)。所以(A十B)X(C十D)c(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)c(A十B)

X(C十D)不成立。因此(A十B)X(C十D)與(AXC)十(BXD)無任何

包含關(guān)系。總之(A十B)X(C十D)=(AXC)?(BXD)不成立。

11

4)成立。證明如下：對任一(x,y)G(A\B)XC,有x《A,xs2B,yGC于是(x,

y)GAXC,且(x,y)e(A\B)XC,月一(x,y)任BXC(否則xGB),所以

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

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

又對任一(x,y)e(AXC)\(BXC),有(x,y)《AXC,且(x,y)

gBXC從而xdA,yGC及xeB。即xdA\B,y￡C,故此(x,y)G(A\B)

XCo所以(AXC)\(BXC)c(AXB)XC?

因而(AXB)XC=(AXC)\(BXC)。

另一種證明方法：

(AXB)XC

=(ACB')XC(差集的定義)

=(AXC)n(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)G(AXC)\(BXC)

n(x,y)WAXCA(x,y)至BXC

=>(xGAAyGC)A(xgBvygC)

n(xeAAYeCAXeB)v(xeA^yGCAy任C)(A對v的分配律)

=>(xeAAXBAyGC)V(XGAAyGCAygC)(人的結(jié)合律、交換律)

=(xGAAX￡B)AyCC(A及v的零壹律、人的結(jié)合律)

=>x6A\BAyGC

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

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

5)成立。證明如下：對任一(x,y)e(A?B)XC,故此xGA十B,yGC于

是x6A且xeB,或者x(2A且xCB。因此(x,y)e(AXC)十(BXC)。

所以(A十B)XCc(AXC)?(BXC)。

對任一(x,y)e(AXC)十(BXC)。貝U(x,y)GAXC且(x,y)

eBXC,或者(x,y)eAXC且(x,y)BXC。因此xGA,yC,x任B,或者x

12

￡B,yCC,xgA?所以xGA\B,或x6B\A,并且ydC,故此x6A?B,y6

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))(根據(jù)4))

=(AXC)?(BXC)(對稱差的定義)

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

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

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

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

7.設(shè)人={1,2,3,4},Rl={(1,3),(2,2),(3,4)},R2={(1,4),(2,3),

(3,4)},求：R|UR2,RAR?,RI'R2,Rj,D(R,),D(R2),(R(),

31(R2),D(RUR2),31(RCR2)

l解］:R,UR2={(1,3),(1,4),(2,2),(2,3),(3,4)}

RlnR2={(3,4)}

RI\R2={(1,3),(2,2)}

RJ=(AXA)\R={(1,1),(1,2),(1,4),(2,1),(2,3),(2,4),(3,

1),(3,2),(3,3),(4,I),(4,2),(4,3),(4,4)}

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

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

(R,UR2)={1,2,3},衣(RCR2)={4}

8.對任意集合A及上的關(guān)系R1和R2,證明

1)求(R,UR2)頡(RI)U次(R2)

2)次(R,AR2)U次(RDCl滅(R2)

［證］1)一方面，由于RmR|UR2,R2￡R)UR2,根據(jù)定理1,有次(％)=次(%

UR2),<7?(R2)=洸(R,UR,)故

次(RI)U次(R2)=次(R,UR2)

另一方面，若xG次(R)UR2)那么存在著yGA,使(y,x)G(R,U

R2)因此(y,X)eR),或者(y,x)GR2,從而xe次(R)或者xe況(R2)

于是xG次(R1)U次(R2),所以次(R,UR2)￡次(R1)U<7?(R2)O

13

11.設(shè)人={1,2,3,4},定義A上的下列關(guān)系

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

氐={(12),(2,4),(3,3),(4,1)}

R5={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}

R6=AXA,R7=0

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

［解］:

)

10-------->02

1100

0000

/?i=<*

0011

Q八)八4000oj

R是反對稱的，傳遞的。

2)

0100

1000

R\=>

0000

0000

R2是反自反的，對稱的。

3)

1100,

1100

Ri=>

0011

0011

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

(RIUR2)=次(RI)U次(R2)。

2)由于R1CIR2QR1，R|CR2=R2，根據(jù)定理1,有次(R,nR2)U次(RJ次

(R|CR2)UR2，所以漢(R,nR2)U次(RDC次(R2)反方向的包含不

成立，反全由第7題可得，那里次(RQR2)={4},h(％)。次(R2)={2,

3,4}C{3,4}={3,4}因此

次（Ri）n生女（R2）土（RiCR?）

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

［解］A上有2必個元關(guān)系。因為叉積AXA有n2個元素，因而AXA有2n2個子

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

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

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

性質(zhì)自反的反自反的對稱的反對稱的傳遞的

關(guān)系^\

相等關(guān)系YNYYY

W關(guān)系YNNYY

〈關(guān)系NYNYY

全域關(guān)系YNYNY

空關(guān)系NYYYY

4)

0100

R4是反對稱的，循環(huán)的。

5）

1。------＞。2'0111

0011

R5=

0001

3。------＞。41000

R5是反自反的，反對稱的,傳遞的。

6）

1oO2

1111

R6—

1111

3o______41111

15

R6是自反的，對稱的，傳遞的，循環(huán)的。從而是等價關(guān)系。

7)

1002'0000'

R7是反自反的對稱

0000

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

0000

的，反傳遞的，反

3°°40000

J1V4也，小1

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

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

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

3）R是對稱的當(dāng)且反當(dāng)R=R

4）R是反對稱的當(dāng)且僅當(dāng)RCR=IA

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

［證］1）必要性

若R是自反的，則對任何xGA,都有（x,x）GR,但是1八={（x,x）lx

SA）,所以IA=R。

充分性

若IA=A則由IA={（X,x）IxSA},可知對任何xGA,都有（x,x）ER,

所以R是自反的。

2）必要性

若R是反自反的，則對任何xGA,都是（x,x）走R,從而（x,x）€RZ,

由IA={（X，x）IxeA）可知IA=R'。于是IACRUR'CR=0，另外0=IACR，

所以IACR=。。

充分性

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

WA,使得（xo，x0）CR。但是（x（）,x0）eiA,從而（xo，x0）0?這不可能，

矛盾。

3）必要性,

若R是對稱的，則對任何（x,y）GR,就有（y,x）GR。于是根據(jù)逆

關(guān)系的定義，可得（x,y）eR,于是R=R;對任何（x,y）eR,由逆關(guān)

系的定義，可得（y,x）eRo再次利用R的對稱性有（y,x）￡R,于是Ru

16

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

充分性

若R=R,則對任何（x,y）WR,由R=R可得（x,y）6R?從而由

逆關(guān)系的定義，可知（y,x）GR這說明R是對稱的。

4）必要性

若R是反對稱的，則對任何（x,y）eR,即有（x,y）GR及（x,y）

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

反對稱性，可得x=y。于是就有（x,y）=（x,x）GIA,所以RCRUIA。

充分性

若RCR￡IA,則對任何（X,y）SR及（y,x）ER,從逆R關(guān)系的定

義，可得（x,y）SR及（x,y）eR,也即（x,y）GRPR,利用RDR=IA

可得（x,y）GIA，于是x=y。所以R是反對稱的。

5）必要性

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

yGA,使（x,y）eR且（y,y）GR,從而利用R的傳遞性，可知（x,y）G

Ro所以

RORCRO

充分性

RoR。從而利用RoRUR可得（x,y）eR?所以R是傳遞的。

證法二：

1)=>):對任何X,

xGA

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

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

所以IAUR；

<=)：對任何XGA,

xCA

=(x,x)e1A（1A是幺關(guān)系，因此是自反關(guān)系）

=>(x,x)eR（因IA￡R）

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

2)n)首先0cIAnR:

其次，對任何x,ydA,若

17

(x,y)GIAnR

=>(x,y)eiAA(x,y)GR

nx=yA(x,y)6R(&是幺關(guān)系，因此是自反關(guān)系)

=(x,x)GR

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

因此，由包含關(guān)系U的反對稱性，可得IACR=0；

<=):對'任何x6A,若

(x,x)GR

^(x,x)6IAA(x,x)eR(IA是幺關(guān)系，因此是自反關(guān)系)

=(x,x)eLCR

n(x,x)￡0(因IAnR=0)

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

故對任何x€A,(x,x)任R；

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

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

(x,y)ER

o(y,x)eR(R是對稱關(guān)系)

o(x,y)eR

所以，R=R：

u):對任何x,yGA

(x,y)GR

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

=(y,x)6R

所以，R是對稱的；

4)=>)對任何x,yGA

(x,y)GRnR

n(x,y)CRA(x,y)eR

=>(x,y)GRA(y,x)CR

=>x=y(R是反對稱關(guān)系)

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

所以，RARCIA;

<=):對任何x,yCA

18

(x,y)￡R

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

n(y,x)GR

所以，R是對稱的;

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

1)為了R=S,必須且只須1%(xuWyij)

2)設(shè)MRUS=(Zy)mXn,那么Zgux^Vyg,1=1,2.......，m,j=l,2,........n.

3)設(shè)MR”=(4)mXn,那么tij=x『yij

i=l,2,?????,m；j—1f2,??????,n.

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

A={a］,32?????,,,B={b”b?,.........,bn}

1)必要性

若RUS,則對任何iG{l,2,……，m},對任何jd{l,2,……n},若(宙,

bj)GR,則R的關(guān)系矩陣MR=(Xij)mxn中第I行第j列元素X,j=l,根據(jù)R=S,

可得(aPbj)es,從而得S的關(guān)系矩陣Ms=(ypmxn中第I行第j列元素yij=l,

由于是1W1故此XjjWyij；若(a,bj)eR,則R的關(guān)系矩陣MR=(Xij)mXn中

第i行第j列元素Xij=O,因此由S的關(guān)系矩陣MS=(y.)mxn中第j列元素

可得xgWyij?？傊?有(VJ(Vj)(XjjWyij)。

2)充分性

若(Vi)(Vj)(XjjWyij),則對任何(a>bj)SR,就有R的關(guān)系

矩陣MR=(Xij)mxn中