概率第三章集合論課后答案

第三章集合論

P45

1.解：

(1)集合可表示為｛尤|ax+%=O,a,beR｝

(2)集合可表示為｛1"-+-Kx2+x+1,x3—1,x3+1,x6—1｝

(3)集合可表示為｛<%V>1Y+V<0｝

(4)集合可表示為｛<x,y>\x>cos。,y>sin6,6€[0,2%]｝

(5)集合可表示為｛x|x=5〃,〃e/｝

2.解：

設戲劇、音樂、廣告分配的時間分別為x,y,z

(2)可表示為｛<x,y,z>\x+y+z=30.x>y,x,y,z=5n,neI]

(3)可表示為｛<x,y,z>|x+y+z=30,z=xvz=y,x,y,z=5〃,〃￡/｝

(4)可表示為｛<x,y,z>|x+y+z=30,y=5,x,y,z=5〃,〃c/｝

P46

3.

給出集合A、8和C的例子，使得AwB,36c而4任。。

解：

A={a}

B={{a},b}

C={{{a},b},c]

4.

(1)該命題為假命題

(2)該命題為假命題

(3)該命題為真命題

證明：任取xeA,由于AC,所以必有xeB。又也。，所以必有

即對于任意的^^人，都有xeC,所以如果A[B且8±C,則AqC。

(4)該命題為假命題

(5)該命題為假命題。

5.

解：可能。若4={1},8={1,2,{1}},則

6.

⑴{a,{a}}

解：設.={。，{。}}

則夕(4)={0,{a},{{a}},{a,{a}})

(2){{1,{2,3}}}

解：設>={{1,{2,3}}}

則p(A)={0,{{l,{2,3}}}}

⑶{<Z>,a,}

解：設4={0,。,{8}}

則2(4)={0,{0},{。},{蝕,{0同,{0,{圻},{。,g}},{0,。,仍}}}

(4)。(°)

解：設A=p(0)={0}

則p(A)={0,{0}}

⑸p(p(0))

解:設A=Q(Q(0))={0,{0}}

則夕G4)={0,{0},{{0}},{0,{0}}}

7.

解：A={0}

p(A)={0,{0}}

B=p(p(A))={0,{0},{{0}},{0,{0}}}

(1)0eB,0^B

⑵{0}eB,{0}cB

(3){{0}}eB,{{0}}cS

8.證明：

充分性："{{a},{a,b}}={{c},{c,d}},

:.{a}={c},{a,b}=[c,d}

:.a-c,b=d

充分性得證。

必要性：a=c,b=d

:.{a}={c},{a,b}={c,d]

[[a},{a,b}]={{c],{c,d}],b}={c,d}

必要性得證。

9.

(i)解：子集個數(shù)2KM

^101

(2)解：元素的奇數(shù)的子集個數(shù)為J=2i°°

2

(3)解：不會有102個元素的子集。

10.

解：把17化為二進制，是00010001,Bn={a4,a^}；

把31化為二進制，是00011111,用1={々4，%,々6

{。2M6，%}，編碼為01000110，為B：o

{q,%},編碼為10000001,為429

P53

1.解：4={0,l,2,3,4}8={2,4,6}

AU8={0,123,4,6}

API8={2,4}

2.解：A={h,o,k]B={b,I,a,c,k}

A\jB={b,l,a,c,k,o]

AC\B={b,k}

3.解:A={1,2,7,8}B={12,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)AU(BU(CUO))={0,123,4,5,6,7,8,9,12,15,16,18,21,24,27,30,32,64}

(2)An(5n(cnr>))=0

Auc={0,123,6,7,8,9,12,15,18,21,24,27,30)

⑶B-(AUC)={4,5}

={345,6}

(4)~

(An6)U。={12,3,4,5,6,8,16,32,64)

P53

4.證明：充分性：由于(An8)uc=Ari(Buc>=(AnB)u(An。

所以c=anc,即

充分性得證。

必要性：由于

所以C=AflC

所以(AnB)UC=(AC|B)U(AnC)

必要性得證。

5.

(1)(A-B)-C=A-(BC)

證明:

(A-B)-C

=(A-B)-C

=(A~B)~C

=A(~B~C)

=A~(BC)

=A-(BC)

上面是一種簡單的方法，還可以利用文字敘述，任取x屬于(A-B)-C,。。。。。證明。

還有一種方法，就是利用第五章的特征函數(shù)證明，下面給出過程

W(A-B)-C

=(〃AA*〃8)一(心一

=(〃A-〃A*〃B)(1-*〃C)

▼A-(BC)

="A，A*(/B+〃C，B*/C)

=〃A(1-(〃B+〃C-〃8*〃C))

所以，W(A-B)-C=WATBC)

從而可得，(A—8)—C=A—(5C)o

(2)(A-B)-C=(A-C)-B

證明：

(A-B)-C

=(A-B)-C

=A~B~C

=A~C~B

=(A—C)~B

(3)(A-B)-C=(A-C)-(B-C)

證明:

(A-C)-(B-C)

=(A~C)-(B~C)

=(A~C)~(B~C)

=(A~C)(~BC)

=(A~C~B)(A~CC)

=A~B~C

=(A-B)~C

因止匕，(A-B)-C=(A-C)-(B-C)

6.解：0A{0}=0

{0}A{0}={0}

{0,{0}}-0={0,{0})

{0,{0}}-{0}={{0}}

7.

(1)證明：

①證明AqBA。

充分性：若AqB,則若xeA,那么必有xeB。因此，若x史8,則必有

即若xc~B,則有xc~A,即~81~4

必要性：若~81~人，則若xe~B,則有xe~A,即若x走8,則必有xeA。那么，

若xeA,那么必有xeB,即AqB；

由以上兩點可知：AcBo~Ba~A。

②證明：AqBoAuB=B

充分性：若xeAUB,那么有xwA或xeB。

若xeA,則由A[B可知，必有xeB,所以若XGAUB,必有xeB,即

若xeB,那么必有xeAUB，即6工AUB,所以AUB=B,充分性得證;

必要性：因為AuB=B,所以，對于任意的xwAUB，必有xeB,所以AqB,必

要性得證；

由以上兩點可知：Aq8oAuB=B

③證明：Ac5<=>AnB=A

充分性：若xeAflB,那么必有尤eA,即

若xwA,那么由AqB可知，必有無€8,所以xeAflB，即4口4口5,

所以，AnB=A；

必要性：因為AnB=A,所以對于任意的xeA,必有xeAp|6,xeB,所以Aq3；

由以上兩點可知，A三8=AnB=A。

由以上三點可知，A屋Bo~Bu~A=AuB=B=AnB=A。

(2)

①證明:Af]B=0oAc~B

充分性：因為Afi3=0,所以對于任意的x,若xwA,則必有x紀B,即xc~B,

所以Ac~B；

必要性：因為Au~B,所以對于任意的》,若xeA,則必有xc~B,即x史8,所以

AD3=0；

由以上兩點可知：APl5=0<=>Ac~B

②證明：AA5=0<=>Bc~A

充分性：因為4口8=0,所以對于任意的x,若xeB,則必有x史A,即xc~A,

所以Bc~A；

必要性：因為BU~A,所以對于任意的x,若無則必有xc~A,即xeA,所以

AC\B=0；

由以上兩點可知：AnB=0oBG~A.

由上可知：Ap|B=0<=>Ac~B<=>Bc~A

(3)

①證明：AUB=EQ~AUB

充分性：因為AuB=E,所以若x史A,則必有xeB,即若xe~A,則必有九eB,

所以~AuB；

必要性：因為Au~A=E,又~AUB,必有AuB=E；

由以上兩點可知：AuB=E=~AuB

②證明：AUB=E=~BGA

充分性：因為AuB=E,所以若則必有尤eA,即若xe~B,則必有xeA,

所以~BcA；

必要性：因為Bu~B=E,又~BuA,必有AuB=E；

由以上兩點可知：AuB=E=~BuA.

由上可知：AuB=E=~AuB=~BUA.。

(4)證明：A=B<=>A0B=4)

充分性：由于A=B,所以Ac~B=?,Bn~A=。

所以A◎B=(An~B)u(Bn~A)=。

必要性：因為A合B=(Ac~B)u(Bn~A)=。

所以An~B=?且Bc~A=?

因為Ac~B=0，所以AGB

又Bc~A=?,所以BuA

所以A=B。

由上可知：A=B=A?B=0。

8.

(1)解：不一定。

若此時有AUB=AUC=A,但BwC。

⑵解：不一定。

若=此時有AnB=AnC=A，但BHC。

(3)解：一定有。

9.

(1)(A-5)(A—C)=A

解：由于(A—8)(4-。)=人，因此必有4-8=4且4—。=4。也就是4B=0

并且AC=0o

(2)(A—B)(A-C)=0

解：由于(A—8)(A—。=0,因此必有A—6=0且A—C=0。也就是并且

AcCo

(3)(A-3)(A-C)=0

解：

(A-B)(A-C)

=(A~B)(A~C)

=A~B~C

=A~(BC)

因此，(A—3)(A-C)=0意味著C)

(4)(A-5)?(A-C)=0

解：

(A—B)十(A-C)

=(A~8)十(A~C)

=(A~B~(A~C))(A~C~(A~B))

={A-B(~AC))(A~C(~AB))

=(A~BC)(AB~C)

=A(B十C)

兩種可能，第一種8十C=0,即B=C：

第二種，A^BC或者4口~(3C)

因此，此題答案為3=C或者A=3C或者?(BC)o

c

11.

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

證明:

(A8)十(AC)

=(AB~(AC))(AC-(AB))

=(AB(~A~C))(AC(~A~B))

=(AB-A)(AB~C)(AC~A)(AC~B)

=(AB~C)(AC~B)

=A((B~C)(C~6))

=A(B十C)

因此，A(8十C)=(AB)十(A0。

(2)A(3十C)=(A8)十(AC)

注意:這個題目本身不正確，舉例如下：全集為{1,2,3},A=⑴,B={2},C={3}

則A(B?C)={1,2,3}1(A5)十(AC)={2,3},不相等。

P57

1.解：設A,B,C分別表示參加足球隊、籃球隊和棒球隊的隊員的集合

MnBnq=3

|AUBUC|=|A|+|B|+|C|-|AnB|-|AnC|-|BnC|+|AnBnC|=>

|AnB|+|AnC|+|BnCb|A|+|B|+|C|+|AAenC|-|AUSUC|

=38+15+20+3-58=18

即同時參加兩個對的隊員共有18個。

2.解：設A,B,C分別表示讀甲種、乙種、丙種雜志的學生的集合。

(1)wriBnq=io%網(wǎng)=60%網(wǎng)=50%冏=50%

|AAJ3|=30%怛Ciq=30%|AACj=30%

|AnBn-c|+iAncn-BI+IBncn-Ai=|AnB|+|Bnc|+|Anc|-3|AnBnc|

=30%+30%+30%-3*10%

=60%

所以確定讀兩種雜志的學生的百分比為60%?

(2)

l~An~Bn~c|=ioo%-(Ancn~Bi+iBncn-Ai+iAnBn-ci+|AnBnc|)

=100%-(60%+10%)

=30%

所以不讀任何雜志的學生的百分比為30%。

3.

解：設A,B,C分別表示騎木馬、坐滑行軌道和乘宇宙飛船的兒童集合。

由公園的總收入知，|A|+|B|+|C|=70/0.5=140

|ABC|=20

IAB-C\+\A?BC\+\-ABC\+\ABC|=55

|AB\+\AC\+\BC\

=3|ABC\+\AB~C\+\A~BC\+\~ABC\

因此，=55+2|ABC\

=55+40

=95

沒有坐過任何一種的兒童總數(shù)為

|~A~B~C|

=75-|ABC\

=75-(|AI+I^I+ICI-IAB\-\AC\-\BC\+\ABC|)

=75-(140-95+20)

=10

答：一共io個兒童沒有坐過其中任何一種游樂設備。

4.解：用A,B分別表示在第一次考試和第二次考試中得A的學生的集合。

(1)網(wǎng)=26|B|=21

又卜AD?@+|AU3|=50,則

|~/in-=50-1AUB|=50-dA|+|B|-|AAB|)

=50-(26+21-1AD3|)=17

n|AnB|=14

所以有14個學生兩次考試都取得Ao

(2)網(wǎng)=4()冏=4()卜小~曰=4

又卜/lf|~@+|AUB|=50,則

|AU8|=46=|A|+|8|-lAflBI

n|Ap|8|=34

所以有34個學生在兩次考試中都取得A。

|/l|=|AA-B|+|AAfi|

n|柏~8|=|川-lAflBI

=40-34

=6

所以有6個學生僅在第一次考試中取得Ao

|B|=|BA-A|+|AAB|

n|fiA-AH5|-|AAB|

=40-34

=6

所以有6個學生僅在第二次考試中取得A。

5.

解：設A,B,C分別是學習數(shù)學、物理、生物的大一學生集合。

由題意可知，

|A|=67,|5|=47,|C|=95,

|A8|=28,|AC\=26,C\=27,

|~A~B~C|=50

|~A~B~C|

=200-|ABC\

=200-(|A|+|B|+|C|-|AB\-\AC\-\BC\+\ABC|)

=200-(67+47+95-26-27-28+1ABC|)

=50

解方程，得

IABCi=22

因此，一共有22人三門功課都學?

P59

i.

(1)Ax{l}x5

解：AX{1}X5={<0,1,1>,<0,1,2>,<1,1,1>,<1,1,2>}

(2)A2X5

解

A2xB={<0,0,1>,<0,1,1>,<1,0,1>,<1,1,1>,<0,0,2>,<0,1,2>,<1,0,2>,<1,1,2>}

(3)(BxA)2

解：j?xA={<1,0>,<1,1>,<2,0>,<2,1>}

(fixA)2={?1,0>,<1,0?,?l,0>,<l,l?,?l,0>,<2,0?,?1,0>,<2,1?,

?1,1>,<1,0?,?1,1>,<1,1?,?1,1>,<2,0?,?1,1>,<2,1?,

?2,0>,<1,0?,?2,0>,<l,l?,?2,0>,<2,0?,?2,0>,<2,1?,

?2,1>,<1,0?,?2,1>,<1,1?,?2,1>,<2,0?,?2,1>,<2,1?}

P60

2.

解：XxY表示在在笛卡爾坐標系中，一34》〈2且一2《丁40的矩形區(qū)域內(nèi)的點集。

12.第60頁第3題

(1)(AB)x(CD)=(AxC)(BxD)

證明：任取<%,y>e(AB)x(C。)，有

<%,y〉c(A5)x(CD)

<=>jce(A5)A_ye(CD)

<^>(xeA/\yeC)/\(xe.B/\yED)

=<x,y>&AxCA<x,yBXD

=<x,y>e(AxC)(BxD)

由<x,y〉取值的任意性知，(AB)x(CD)=(AxQ(BxDf.

(2)當且僅當才，才有(AB)C=A(BC)

證明：當C=A時，AC=A,于是(AB)C=(AC)(BC)=A(BC)。

當(AB)C=A(BC)時，

任取可知xe(AB)C,由(AB)C=A(B。知XGA(BC),

于是得到xeA。所以，C=A。

3.

(1)證明：

任取<x,y>

<x,y>w(AnB)x(cnO)=(x€AnB)A(ywCn。)

=>(xeA/\xeB)A(yeCAyeD)

=(xw/IAJeC)A(xeBAy&D)

=>(<x,y>EAXC)A(<x,y>eBxD)

=><x,y>e(AxC)Pl(Bx￡))

所以(AnB)x(cno)q(Axc)n(Bx。)

<蒼y>e(AxC)n(Bx￡))=(<>e/IQC)A(<>eBQD)

=>(xeAAyeC)/\(xeBAyeD)

任取=(XEAAxeB)A(yeCAyeD)

=>(%GAriB)A(yGCriD)

=><x,y>G(AAB)x(CAD)

所以(4xC)「(5x￡>)q(A「5)x(C「D)

故(Ar)3)x(criD)=(AxC)ri(BxO)

(2)證明：

充分性：由于（AnB）uc=Ari（5Uc）=（AriB）u（Aric）

所以C=AC|C，即CqA

充分性得證。

必要性：由于CqA

所以C=ADC

所以(An3)uc=(An3)u(Anc)

必要性得證。

4.證明：

必要性：若A=0,AxB=BxA=0；

同理，若8=0,AxB=5xA=0；

若A=B,則顯然有AxB=3xA；

必要性得證。

充分性性：由于Ax8=BxA

所以對于任意的<x,y>eAxB,必有<x,y>eBxA

<x,yAxBx&A/\y&B<x,y>^BxA<^x^B/\y&A

即若xeA則必有xeB；若yeB,則必有yeA,所以當A#0,8時,

A=B；

充分性得證。

5,

(1)(AB)x(CD)=(AxQ(BxD)

解：任取<%,y>c(AB)x(C。)，有

<x,y>e(AJ5)x(CD)

o%c(AB)/\ye(CD)

<=>(xeAvxeB)A(yeCvyeD)

=(%cA/\(yeCvyeD))v(JCG5A(_yeCvyeD))

<=>(xeAAyeC)v(xeA/\yeD)v(xeBAyeC)v(xeB/\yeD)

<=><x,y>e(AxC)(AxD)(BxC)(BxD)

選擇A=⑴,B=⑵，C={a},D=

則(A5)x(。D)={<l,a>,<l,b>,<2,a>,<2,b>}

(AxC)(BxD)={<\,a>,<2,b>]

因此該等式不成立。

(2)(A-B)x(C-D)=(AxQ-(BxD)

解：任取<%,y>c(A—B)x(C—D),有

<x,>G(A-B)x(C-D)

u><%,y〉e(A~B)義(C?D)

0%c(A?8)Aye(C~D)

=(%eA/\%￡3)/\(yGC/\yw￡>)

o(xeA/\yeC)/\(%e3/\ywZ))

o(%eA/\yeC)/\(%￡B/\y￡。)

=(%GAA)GC)A—I(%cBvycD)

選擇A={1,2},B=⑴,C={a,b},D={a}

(A-B)x(C-D)={<2,b>j

(AxC)-(BxD)={<l,b>,<2,a>,<2,b>}

因此，該等式不成立。

(3)(A十B)x(C十O)=(AxC)十(Bx￡>)

解：設八={1,2},B=⑵，C={3,4},D={4}

則(A十3)x(。十。)={<1,3>}

(AxC)十(8x￡))={<1,3>,<1,4>,<2,3>}

因此，該等式不成立。

(4)(A-B)xC=(AxC)-(BxC)

解：取<x,y>G(A-8)XC,有

<x,y>e(A-B)xC

0<%,y〉e(4~B)xC

oxe(A-B)AyeC

(xeA/\yeC)A(x^Bvy^C)

o(xeA/\yeC)八-n(xeB△yeC)

=(<%,y>cAxC)△(<%,y〉￡8xC)

=<x,y>e(AxC-BxC)

因此，該等式成立。

(5)(A十3)xC=(AxC)十(BxC)

解：任取取<%,y>c(AxC)十(3xC),有

<%,y>c(AxC)十(8xC)

o((%eAAyeC)八一)(%eB八yeC))V((XGBA^GC)A-)(XeAAyeC))

o((%eAAycC)A(xeBvy￡C))v((xEB/\y&C)A(xAvyC))

o(xeA/\yeC/\%￡3)v(%￡A/\xeB/\yeC)

0((%eA/\%￡B)v(%￡A/\%eB))△yeC

o%e((A?B)(~AB))A_yGC

xEA?B/\yEC

o<%,y〉w(A十8)xC

因此，該等式成立。

第四章二元關系

P63

1.給出下列關系R的所有序偶。

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

7?={<x,y>|x,yGAAB}

解：AC13={0,2}

R={<0,0>,<0,2>,<2,0>,<2,2>}

(2)A={1,2,3,4,5},3={1,2,3}

H=|<x,y>|xeA/\yeB/\x=y2}

解：7?={<1,1>,<4,2>}

2.設為和R2都是從A={1,2,3,4}到8={2,3,4}的二元關系，并且

R,={<1,2>,<2,4>,<3,3>}

R2={<1,3>,<2,4>,<4,2>}

求KU%、胭）、D限）、R⑻、幽）、。（凡UR?）、砧0因）。

解：/?(U7?2={<1,2>,<2,4>,<3,3>,<1,3>,<4,2>}

與0%={<2,4>}

￡>(/?,)={1,2,3)

。(&)={1,2,4}

H(Rj={2,3,4}

雙&)={2,3,4}

咽U&)={1,2,3,4}

/?(/?,A7?2)={4,4}

3.用L表示“小于或等于”，D表示“整除”，這里X?！繁硎尽皒整除y”。L和D都定義

于集合{1,2,3,4,5,6}上。試把L和D表示成集合，并求出Lf]。。

解：

<1,1><1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<2,2>,<2,3>,<2,4>,<2,5>,<2,6>,

L=<<3,3>,

<3,4>,<3,5>,<3,6>,<4,4>,<4,5>,<4,6>,<5,5>,<5,6>,<6,6>

[<1,1>,<1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<2,2>,<2,4>,<2,6>,<3,3>,<3,6>,

D—<

<4,4>,<5,5>,<6,6>

<1,1>,<1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<2,2>,<2,4>,<2,6>,<3,3>,<3,6>,<4,4>,

LC)D-<

<5,5>,<6,6>

4.如果關系R和S都是自反的。證明：RUS,RAS也是自反的。

證明：設R是集合A上的二元關系，S是集合B上的二元關系。

因為R和S都是自反的，

所以對于VxeA,都有＜x,x〉eR,

對于VxeB,都有＜x,x〉eS。

(1)設xwAUB,那么尤eA或xeB。

若xeA,有<x,x>cR,那么必有<x,x>e/?US。

若xeB,有<x,x>eS,那么必有<x,x>cRUS。

因此，當xwAUB時，必有<X,X>G/?US,

所以RUS也是自反的。

(2)設XGACIB,那么XGA且xeB

因此<x,x〉eR且<x,x〉eS,即<x,x〉e/?DS。

所以APIS也是自反的。

5.如果關系R和S都是自反的、對稱的、可傳遞的，證明：ACIS也是自反的、對稱的和

可傳遞的。

證明：設R是集合A上的二元關系，S是集合B上的二元關系。

①自反性的證明如題4。

②對于任意的eADB,若<x,y>eRp|S,

那么<x,y〉eR且<x,y〉eS

因為R和S都是對稱的，所以<y,x〉eH且<y,x〉eS,

所以<y,x〉e/?ASo

即對于任意的MyeAAB,若<x,y>eRnS,則必有V>e/?PlS,

所以APIS是對稱的。

③對于任意x,y,zeACIB,若<x,y>eRDS且<y,z>cRDS,

那么有<x,y>eR,<y,z>w—且<x,y>eS,<y,z>eS?

因為R和S都是可傳遞的，

所以有<x,z>eR且<x,z〉eS,即<x,z〉eRnS。

即對于任意x,y,zeAQB,若<x,y〉eRnS且<y,z>e/?DS,都有

<x,z>e/?nso

所以/?ns是可傳遞的。

6.給定集合S={1,2,3,4}和S中的關系R,證明R是不可傳遞的。求出一個關系R=R,

而N是可傳遞的，能否再求出另外一個關系&衛(wèi)R且凡是可傳遞的。

解：此題不正確，關系R沒有給出

7.給定集合5={1,2,…J0}和S中的關系R,R={<x,y>|x+y=10},關系R有哪幾

種性質(zhì)。

解：R是不自反的，對稱的，不可傳遞的。

不自反性：

當x=5時，<尤,x>eR；當x是集合S中的其他數(shù)時，<x,x>史R

因此，R不是自反的，也是反自反的。

對稱性：

對于任意的x,yeS,若有<x,y>eR,

那么x+y=10,則必有y+x=10

即<y,x>eRo

即對于任意的x,yeS,若有<x,y〉eH,則必有<y,x〉eH。

所以R是對稱的。

不可傳遞性：舉反例即可。

由此可知，<4,6>eR且<6,4>eR,但是<4,4>eR。

所以R是不可傳遞的。

8.給出滿足下列要求的二元關系的實例。

(1)既是自反的又是反自反的。

(2)既不是自反的又不是反自反的。

(3)既是對稱的又是反對稱的。

(4)既不是對稱的又不是反對稱的。

解：(1)空集上的二元關系。

(2)A={1,2},R={。。}，R是集合A上的二元關系。

(3)空集上的二元關系。

(4)A={1,2,3},R={<1,1>,<1,2>,<2,1>,<1,3>},R是集合A上的二元關系。

P69

1.給定集合X={0,1,2,3},R是X中的關系，并可表示成

R={<0,0>,<0,3>,<2,0>,<2,1>,<2,3>,<3,2>}

試畫出R的關系圖，并寫出對應的關系矩陣。

0123

0F1001

解:%=10000

21101

310010

關系圖如下:

2.設集合X={1,2,3},則集合X中有多少個二元關系。

解：有2寸=512個二元關系。

3.設X是具有n個元素的有窮集合，證明:X中有個二元關系。

證明：集合X中的每個二元關系都是XxX的子集，X有〃個元素，XxX有1個元素,

夕(XxX)有2"'個元素，每一個元素都是XxX的一個子集，也是一種二元關系，因而,

在X中有2/個不同的二元關系。

4.給定集合*={1,2,3}。圖4-6給出了X中的關系R的12個關系圖。對于每個關系圖，

寫出相應的關系矩陣，并證明被表達的關系是否是自反的或反自反的；是否是對稱的或反對

稱的；是否是可傳遞的。

(a)自反的、不對稱的、不可傳遞的；

其對應的關系矩陣為：

110

MR=\11

101

(b)不自反的、反對稱的、不可傳遞的；

其對應的關系矩陣為：

110

MK=001

100

(c)自反的、對稱的、可傳遞的；

其對應的關系矩陣為：

111

MR=\11

111

(d)自反的、不對稱的、不可傳遞的；

其對應的關系矩陣為：

110

MR=011

111

(e)不自反的、不對稱的、不可傳遞的；

其對應的關系矩陣為：

010

MR=111

110

(f)不自反的、對稱的、不可傳遞的；

其對應的關系矩陣為：

111

MR=\00

100

(g)自反的、反對稱的、可傳遞的；

其對應的關系矩陣為：

101

MR=111

001

(h)自反的、不對稱的、不可傳遞的;

其對應的關系矩陣為:

110

/=111

001

(i)不自反的、對稱的、可傳遞的；此題圖有錯誤

其對應的關系矩陣為：

011

妁=111

111

(J)自反的、反對稱的、不可傳遞的；

其對應的關系矩陣為：

101

%=110

011

(k)自反的、反對稱的、可傳遞的；

其對應的關系矩陣為：

100

“?=110

101

(1)不自反的、反對稱的、可傳遞的。

其對應的關系矩陣為：

001

%=111

001

5.給定集合X={0,1,2,3},舄和可是X中的關系,分別為

R1={<i，/>l/=i+lv/=〃2}

R2={<i,j>\i=j+2}

求出下列合成關系。

(1)R］。R2

(2)R2OR1

(3)R、。艮。&

(4)R：

(5)R；

解：&={<0,1>,<1,2>,<2,3>,<0,0>,<2,1>},

鳥={<2,0>,<3,1>}

(1)4/?,={<1,O>,<2,1>}

(2)R24={<2,0>,<2,l>,<3,2>}

(3)4Ry/?,={<1,0>,<1,1>,<2,2>}

(4)&={<0,0>,<0,1>,<0,2>,<0,3>,<1,2>,<2,1>,<2,3>}

(5)R；=0

.設為和是集合中的二元關系。試證或反證下列命題：

6R2x

(1)如果為和&是自反的，則名。此也是自反的。

(2)如果用和與是反自反的，則與。此也是反自反的。

(3)如果N和凡是對稱的，則鳥。凡也是對稱的。

(4)如果K和凡是反對稱的，則/。夫2也是反對稱的。

(5)如果鳥和凡是可傳遞的，則K。&也是可傳遞的。

解：(1)證明：任?。X,由于用和&是自反的，因此,<尤,%>6火2,

可得<%,%>6勺&,由x取值的任意性可知，/?,&是自反的。

⑵設X={1,2,3}，4={<1,3>},鳥={<3,1>},則凡此={<1,1>},不是反

自反的。

(3)設X={1,2,3}，N={<1,2>,<2,1>},凡={<3,2>,<2,3>},則

顯g={<1,3>},不是對稱的。

(4)設X={1,2,3},/^={<1,2>,<3,1>},7?2={<1,1>,<2,3>},則

R]&={<1,3>,<3,1>},不是反對稱的。

(5)設X={1,2,3,4,={<1,2>,<2,3>,<1,3>,<5,4>},/?,={<2,3>,

<3,5>,<2,5>,<4,4>},則44={<1,3>,<1,5>,<2,5>,<5,4>},不可傳遞。

7.設凡，和R.3是集合X中的二元關系。試證明：若與之尺2,則有

(1)oR2R,

(2)&R\=R3R,

證明：

(1)任取<%,z>c勺％,則一定存在某一個yeX,使得

<y,z>c叫，由4=鳥知，

(3j)(<>GNA<y,z>cR)

=>(3_y)(<x,y>GA,A<y,z>wR3)

=<X,Z>G凡R3

根據(jù)<%,z〉取值的任意性，問題得證，&/?3口&

(2)任取&,則一定存在某一個ycX,使得<%,

<y,z>^Rl,由4口鳥知,

(力)(<%,y>w居人<Kz><與)

二>(3j)(<x,y>&R3A<y，z>wR?)

OCX.ZAWR,R2

根據(jù)<%,Z>取值的任意性，問題得證，鳥4口鳥與。

8.試證明定理4.4.1的(2),(3),(4)。

(2)見書本67頁

(3)當且僅當存在某一個yeF,使得<x,y>e&UR3且<y，z>eK,，才有

<X9Z>G(凡1)凡)。&,而

(3>'X<x,y>e&U4△<y,z>e&)

<

。(3_yX(x,y>ER2\/<x,y>e&)A<y,z>e/?4)

=(3yX(<x,y>e/?2△<Xz>e&)v(<x,y>e&A<y,z>e/?4))

o(3yX<%y>e&△<y,z>e&)v(3yX<x,y>e&△<y,z>e&)

<=><X,Z>G1?2o/?4V<X,Z>G7?3oz?4

o<X,z>e(7?2OR4)U(&oR4)

(4)當且僅當存在某一個yeY,使得<x,y>e&D&且<y,z〉e4,才有

<x,z>G(7?2m?3)o7?4,而

(3>'X<x,y>eR2PI/?3A<y,z>e/?4)

o(3JX(<>e/?2A<X,jy>e7?3)A<y,z>e7?4)

o(3yX(<x,y>eR2A<y,z>e/?4)A(<x,y>eR3A<y,z>&&))

=>(3yX<x,y>e/?,A<y,z>e/?4)A(3J\<x,y>&&人<y,z>eR4)

=<龍,z>e火2。R4A<龍，z>eR3。H4

o<x,z>e(R2°&)C|(4°&)

P75

1.設乂={0,1,2,3},K和&是X中的關系，

"={<，,/>|/=i+lv/=〃2}

叫={C=j+2}

試求出關系矩陣：M&；MR。；MR/MR?；MR「MR1；

MROMR?。%；%。

解：R]={<0,0>,<0,1>,<1,2>,<2,3>,<2,1>}

&={<2,0>,<3,1>}

由此可得：&。&={<1，0>，<2,1>}

R,。&={<2,0>,<2,1>,<3,2>}

&。R?。&={<1,0>,<1,1>,<2,2>}

R：={<0,0>,<0,1>,<0,2>,<0,3>,<1,2>,<2,1>,<2,3>}

所以:

11000000

00100000

MR、MR2

01011000

00000100

00000000

10000000

MROMRr=MRUMR、=11

R\2010000

00000010

00001111

11000010

M肝一

一00100101

00000000

2.此題有錯誤

3.試證明定理4.4.6的(3)、(4)、(5)、(7)和(8)式。

>e

<>￡R]n&}=<〉￡<<y，x與nR2

=<y,x>e/?,A<y.x>eR?

(3)證明：??

=<>￡/?]△<>eR2

o<x,y>eR}AR2

所以我1『”=篇「用。

<x,y>eXxY=<y,x>eXxY

(4)證明:

xeY/\yeX

o<x,y>&YxX

所以xqy=Yxx。

(5)證明：

(7)證明：見書上P74頁

<x,y>GR2<=><>GR2

(8)證明:0meRUN

=<x,y>GR、—>R]

所以&=&—K

同理與=尺2一/

得證。

4.試證明：如果關系R是自反的，則A也是自反的；如果R是可傳遞的、非自反的、對稱

的或反對稱的，則巨亦然。

證明：設R是A上的二元關系，

(1)若R是自反的，則〃uR,由于，的轉置仍是〃，因此，〃u去，故A是自反

的；

(2)若R是反自反的，則，R=0。把，和R都取轉置，由于，的轉置仍是，，因

此，IAr>R=0,故京是反自反的；

(3)若R是對稱的,任取<y,x>e且，則<%y>eR,由R的對稱性可知，<>wR,

于是<x,y>cR。由x,y取值的任意性知，A是對稱的；

(4)若R是反對稱的，任取<y,x>e天，則<%,y>wR,由R的反對稱性可知，

<y,X>^R,于是<x,y>e且。由x,y取值的任意性知，A是反對稱的；

(5)若R是可傳遞得，任取<>eH,<y,z>eR,則<、％王氏，<z,y>wR,

由R的可傳遞性，可知<z,%>eH,于是<x,z>e無。故片是可傳遞的。

5.如果R是反對稱的關系，則在RCI天的關系矩陣中有多少個非零值？

解：R的關系矩陣上，主對角線有多少個非零值，RD友的關系矩陣中就有多少非零記入值。

P79

1.設X是一個集合，N和尺2是X中的二元關系，并設與3H2,試證明:

⑵s（K）2s'（/?2）

（3）r（Rj3伏）

2.在圖4-11中給出的三個關系圖，試求出每一個的自反的、對稱的閉包，并畫出閉包的關

系圖。

a）解：由關系圖可知，

R=0

則：r（R）={<a,a>,<b,b>}

s（R）=0

t（R）=0

b）解：由關系圖可知，

7?={<a,a>,<a,b>]

則：r（7?）={<a,a>,<h,b>,<a,h>}

s（R）={<〃,〃>,<a,/?>,</?,?>}

Z（7?）={<a,a>,<a.b>}

c）解：由關系圖可知，

R={<a,b>,<b,c>,<c.a>}

則：r（/?）={<a,a>,<b,b>,<c,c>,<a,b>,<b,c>,<c.a>}

s（R）={<a.b>,<b,a>,<b,c>,<c,b>,<c,a>,<a,c>}

t（玲=卜a,b>,<b,c>,<c,a>,<a,c>,<b,a>,<c,b>,<a,a>.<b,b>,<c,c>}

3.飛和&是集合X中的關系。試證明：

（1）廠（鳥u&b

（2）s（KU〃）=s（K）Us（中）

（3）RUR2）=《K）U依）

4.設集合X={aS,c,d,e,/,g,/z},R是X中的二元關系，圖4-12給出了R的關系圖。

試畫出可傳遞閉包《R）的關系圖，并求出tsr（R）o

解：由關系圖可知，

R={<a,b>,<b,c>,<c,a>,<d,e>,<e,f>,<f,g>,<g,h>,<h,d>}

則：

<a,b