离散数学教程(耿素云屈婉玲北京大学出版社)的全部习题解答

1

1

1

22003

1

2“

”

3

(

beta“+”

4(“ ”02CS≈

chouxiaoyatedyakaru

2

(beta4++)3

WORKEDOUTANDTEXIFIED

BY

4

(E-mail:xiaoxinpan@)

HONOREDREVIEWER

(chouxiaoya@)

September1,2004

Thanksatrillion!!!Bow......

)

email

=

“ ”

“

10)

yitianxing

xuening

......

(

”

2002

6

)

“+”

BBS

Contents

1

2

3

7

2

3

2252

66

Chapter1

1.

(1){2};

(2){1,4,9,16,25,36,49,64,81,100,121,144,169,196};(3){1,8,27,64};(4){0,1,2,...};(5){2,3};

(6){a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z}.2.

(1){(x,y)|x,y∈R∧x2+y2<1};(2){θ|θ=π/4+kπ∧k∈Z};(3){x|x∈N∧x<8};

(4){(x,y,z)|x,y,z∈N∧x2+y2=z2(5){x|x∈R∧x2+5x+6=0}.};3.

(1),(4),(5),(6),(8),(9)

4.(1)Proof:

A∈B∧B C

= AA∈∈BB∧∧ (Ax(∈x∈BB→→Ax∈∈CC))= A∈CQ.E.D.

(2)

A={a},B={{a}},C={{a},{b}}

A C

(3)

A={a},B={a,b},C={{a,b},{b,c}}

3

((x/A))(

)

A∈B∧B C

A B∧B∈

C

A∈/C

(4)C

A={a},B={a,b},C={{a,b},{b,c}}

A B∧B∈

A C

5.

A={a},B={{a}},C={{{a}}}

A∈B∧B∈C

A∈/C

6.

(1)0123

{a},{b},{c}

{a,b},{a,c},{b,c}{a,b,c}

{ ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}

{1},{{2,3}}{{1},{2,3}}

{ ,{1},{{2,3}},{{1},{2,3}}}

{ },{{ }}{ ,{ }}

{ ,{ },{{ }},{ ,{ }}}

{{1,2}}{ ,{{1,2}}}

{{ ,1}},{1}{{ ,1},1}

{ ,{{ ,1}},{1},{{ ,1},1}}

(2)012

(3)012

(4)01

(5)012

7.

8.

(1){4};(2){1,3,5};(3){2,3,4,5};(4){2,3,4,5};(5){ ,{4}};(6){{1},{1,4}}.

4

9.

(1){ 7, 6, 5, 4, 3, 2, 1,0,1,2,3,4,5,6,7,8,9,12,15,16,18,21,24,27,30,32,64};(2) ;

(3){ 7, 6, 5, 4, 3, 2, 1,4,5};

(4){ 7, 6, 5, 4, 3, 2, 1,0,3,4,5,6,9,12,15,18,21,24,27,30}.10.

P(A)={ ,{a}}

PP(A)={ ,{ },{{a}},{ ,{a}}}

(1),(2),(4),(5)

11.Proof:

A B=A

A∩B=(A B)∩B

=(A∩～B)∩B=A∩(～B∩B)=A∩ =

A∩B=

A=A∩E

=A∩(B∪～B)

=(A∩B)∪(A∩～B)= ∪(A∩～B)=A∩～B=A B

A B=A A∩B=

Q.E.D.12.

Lemma1.1A

B

A B=A A∩B=

Proof:

11Q.E.D.

Lemma1.2

A

B

A B= A B

Proof:

A B= ¬ x(x∈(A B))

5

(

)

(A B=A)()()()()

()()(

)(A∩B= )()

(

)

x¬(x∈(A B)) x¬(x∈A∧x∈/B) x¬(x∈A∧¬x∈B) x(¬x∈A∨x∈B) x(x∈A→x∈B)(((∈/(()

)

)

)

)

Q.E.D.

A B(

(1)(A B)∪(A C)=AA∩B∩C= Proof:

(A B)∪(A C)=A A (B∩C)=A

A∩(B∩Q.E.D.

A∩B∩CC=)=

(2)(A B)∪(A C)= A (B∩C)

Proof:

(A B)∪(A C)= A (B∩C)=

Q.E.D.

A (B∩C)

(3)(A B)∩(A C)= A (B∪C)Proof:

(A B)∩(A C)= A (B∪C)=

Q.E.D.

A (B∪C)

(4)(A B)∩(A C)=AA∩(B∪C)= Proof:

(A B)∩(A C)=A A (B∪C)=A

Q.E.D.

A∩(B∪C)=

13.(1)

Lemma1.3A

B

A∩B A

A∩B B

Proof:

6

)

()(Lemma()

1.1)()(Lemma1.2)

()(Lemma1.2)

()(Lemma1.1)

x

x∈A∩B x∈A∧x∈B

= x∈AA∩B AA∩B B

Q.E.D.

((

)

)

Lemma1.4Proof:

A

B

A A∪B

B A∪B

x

x∈A= x∈A∨x∈B

x∈A∪BA A∪B

Q.E.D.

B A∪B

((

)

)

Proof:

(A B) C=(A∩～B)∩～C

A∩～B

(A∩～B)∪(A∩C)=A∩(～B∪C)=A∩～(B∩～C)=A (B C)

Q.E.D.(2)Proof:

()(Lemma1.3)(Lemma1.4)()()()

A∩C=

(1)

A∩C=

(A B) C=(A∩～B)∩～C()

=(A∩～C)∩～B(=(A C)∩～B()=A∩～B(Lemma1.1)=(A∩～B)∪ ()=(A∩～B)∪(A∩C)(A∩C= )

)=A∩(～B∪C)(

=A∩～(B∩～C)()=A (B C)()

xx∈A∧x∈CxB

x∈/(A B) Cx∈A (B C)(A B) C=A (B C)

)

7

Q.E.D.

14.Proof:

B=E∩B

=(A∪～A)∩B

=(A∩B)∪(～A∩B)=(A∩C)∪(～A∩C)=(A∪～A)∩C=E∩C=CQ.E.D.

15.A=B=D=G

C=F=H

16.

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

(3){ ,{ }};

17.

(1){ ,{{ }},{{{ }}},{{ },{{ }}}};(2){ ,{ },{{ }},{ ,{ }}};(3){{ },{{ }}};18.

(1){ ,1,2,3};(2) ;(3) ;(4) .19.

(1)A∪B;(2)A;(3)B.20.

Lemma1.5A,B,C,D

A B∧C D A∪C B∪D

Proof:

8

()()()()

()()(

)

x

x∈A∪C x∈A∨x∈C

(x∈A∨x∈C)∧

(x∈A→x∈B∧x∈C→x∈D)= x∈B∨x∈D((()

)

&

)Q.E.D.

x∈B∪D

(

Lemma1.6A,B,C,D

A B∧C D A∩C B∩D

Proof:

x

x∈A∩C x∈A∧x∈C

(= x∈B∧x∈C(= x∈B∧x∈D(Q.E.D.

x∈B∩D

(

Proof:

A=A∩E

(=A∩(C∪～C)

(=(A∩C)∪(A∩～C)( =(BB∩∩(CC)∪∪～(BC∩)～C)((=B∩E(=B(

Q.E.D.

21.(1)A∩B=AA BProof:

A∩B=A

xx(((xx∈∈AA∩∧Bx x∈A)

( ( ( x x(((x((((¬x¬(xx∈∈∈AAA∧∨∧x∈∈BB)) →xx∈∈AA)

)∧(x∈A→(x∈A∧x∈B)))¬xx∈∈BB)∨∨xx∈∈AA))∧∧((¬¬xx∈∈AA∨∨((xx∈A∧x∈B)))( x((¬x∈A∨x∈A∨¬x∈B)∧(¬x∈A∨(x∈∈AA∧∧xx∈∈BB))))))

((

9

)

)

&)&

)

)

)))

&Lemma1.5))))

)

))

)

)

)

x((((¬¬xx∈∈AA∨∨xx∈∈AA∨)∧¬x(¬∈xB∈)∧

A∨x∈B)))

x((1∨¬x∈B)∧(1∧(¬x∈ x x(1x((¬∧(1∧(¬x∈A∨x∈B)))A∨x∈B)))xx∈∈A∨x∈B)Q.E.D.

A BA→x∈B)(2)A∪B=AB AProof:

A∪B=A

x(x∈A∪B x∈A)

xx(((((xx∈∈AA∨∨xx∈∈BB)) →x∈A)

x x((x(((¬(((¬(xx∈∈AA∨∧x¬x∈∈BB)∨x)∨x∈x∈A∈A)A)∧∧()∧(x¬∈(xA¬x∈∈A→A∨(x∨x∈x …… 此处隐藏：3326字，全部文档内容请下载后查看。喜欢就下载吧 ……