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

1

1

1

22003

1

2“

”

3

(

beta“+”

4(“ ”02CS≈

chouxiaoyatedyakaru

2

(beta4++)3

WORKEDOUTANDTEXIFIED

BY

4

(E-mail:xiaoxinpan@http://www.77cn.com.cn)

HONOREDREVIEWER

(chouxiaoya@http://www.77cn.com.cn)

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∈A∈A∨A∨x∨x∈x∈B∈B)))B))))(¬¬xx∈∈AA∨∨xx∈∈AA∨)∧x(∈¬xB))

∈B∨x∈A))∧

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

B A∈A)(3)A⊕B=A

B=

Proof:

B=

A⊕B=A⊕

=A

A⊕B=A

B= ⊕B

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

10

()(()()

()

)

(

)

(()

()()

(

)

()((()

)()

)

(

)

(B= )(1.7(4))

(1.7(4))(1.7(5))(

1.7(2))(A⊕B=A)(

1.7(5))

)

Q.E.D.(4)Proof:

A∩B=A∪B

A=B

A=B

A∩B=A∩A

=A=A∪A=A∪B

A∩B=A∪B

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

=A∪(B∪B)=(A∪B)∪B=(A∩B)∪B=BQ.E.D.

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

(

(A∩B((((

(A∩B(

)

=A∪B)))))

=A∪B))

22.(1)

Lemma1.5

Lemma1.6

(2)A={a},C={b},B=D={a,b}A B∧C DA∪B C∪DA=C={a,b},B={a,b,c},D={a,b,d}A B∧C DA∩B C∩D

23.Proof:

x∈B∧x∈/Cx∈/B∧x∈Cx∈B∧x∈/C

x∈Ax∈/A⊕Bx∈A⊕CA⊕B=A⊕Cx∈/Ax∈A⊕Bx∈/A⊕CA⊕B=A⊕Cx∈/B∧x∈C

A⊕B=A⊕C B=C

Q.E.D.

24.(A B) C=(A C) B(A C) (B C)

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

(A B) C=

(A B) C=(A C) B

11

Proof:

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

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

Q.E.D.

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

Proof:

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

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

Q.E.D.

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

Proof:

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

=(A∩～B∩～C)∪

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

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

Q.E.D.25.(1)A;

(2)A B;(3)B A.26.(1)Proof:

A C∧B C

x∈A∪B x∈A∨x∈B

(x∈A∨x∈B)∧

12

x

(()()()

(

(()

((

(()()

()()()

((

(

)

)

)

)))

)

))

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

A∪B Cx

x∈A= x∈A∨x∈B

= x∈C(((((

&

))))

)

&

A CB C

Q.E.D.

(2)Proof:

C A∧C B

x

x∈C (x∈C)∧(x∈C)

(= (x∈A)∧(x∈B)( x∈A∩B

C A∩B

(x

x∈C= x∈A∩B

(Q.E.D.

x∈A∧x∈B

(

27.Proof:

A

A( ∈PA

( ( { } { } PA∧ PA{ ,∈PPA∧ ∈PPA( { ,{ }}{ }} ((

{ ,∈{ }}PPPPPA∈A

PPPA

{ ,{ }}A

PPPA

A

PA

Q.E.D.

28.

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

(1) (2)A B ～B ～A

Proof:

A B x(x∈A→x∈B)

(

13

)&

)

)

&

)

)

1).1)&)1.1)

))

)

x(¬(x∈B)→¬(x∈A)) x(x∈/B→x∈/A) x(x∈～B→x∈～A)((∈/())

)

Q.E.D.

～B ～A(1) (3)

A B ～A∪B=E

Proof:

A B x(x∈A→x∈B)

x(¬(x x∈A)∨(x∈B))x(x∈/A∨x∈B)Q.E.D.

～x((x∈～A∨x∈B)Ax∈～∪BA=∪E

B) 1

(1) (4)

A B A B ～A

Proof:

A B ～A x(x∈A B→x∈～A)

x((x∈A x(¬(x∈A∧∧xx∈/∈/BB)→)x∈～A) x((¬x∈A∨¬x∈/B∨)∨xx∈～∈～AA)) x x((x((¬((¬x¬x∈A∨¬x∈/B)∨x∈/A)x∈∈AA∨∨¬¬x∈xB∈B)∨¬x∈A) x(¬x∈A∨¬x∈A)∨∨x¬x∈∈BA)) x(¬x∈A∨x∈B)Q.E.D.

Ax (xB

∈A→x∈B)(1) (5)

A B A B B

Proof:

A B B x(x∈A B→x∈B)

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

(

(((((((∈/)

((((

(

(((

)

(

(((∈/((

))))

)

)

)

)))

))

)))

)

)

)

)

)

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

)

)

)

)

)

Q.E.D.29.Proof:

x

x∈(∩A)∩(∩B) x z∈(z(∩∈AA)∧→xx∈∈(∩z)B∧)

z(= zz(((zz∈∈AA→→xx∈∈zz)

)∧(zz∈∈BB→→xx∈∈z))z)= z((z∈A→x∈z)∨(z∈B→x∈z))

z((¬(z∈A)∨(x∈z))∨(¬(z∈B)∨(x∈ zz((((¬¬((zz∈∈AA))∨∨¬¬((zz∈∈B))∨(x∈z)∨(x∈zz))))) z(¬(z∈A∧z∈B)∨B))∨(x∈z)) zz((zz∈∈AA∧∩zB∈→Bx→∈xz)∈x∈z)z)Q.E.D.

x∈∩(A∩B)30.(1)Proof:

x

x∈P(A)∩P(B) x∈P(A)∧x∈P(B)

x A∧x BQ.E.D.

xx ∈PA(∩AB∩B)

(2)

Lemma1.7

A,B,C

C A C A∪B

15

((((((((((((

(((26

(

))

)))

)

)

))

))

)

)

(2))

)

)

C B C A∪B

Proof:

C A C A∧A A∪B

= C A∪B

C B C A∪B

Q.E.D.

(Lemma1.4)(

)

Lemma1.8A,B,CC A∨C B C A∪BProof:

C A∨B (C A∨C B)∧(C A→C A∪B)

∧(C B→C A∪B)= (C A∪B)∨(C A∪B) C A∪B

Q.E.D.

(Lemma1.7)

)(

(

)

Proof:

x

x∈P(A)∪P(B) x∈P(A)∨x∈P(B)

x A∨x B= x A∪B x∈P(A∪B)

Q.E.D.

()()(Lemma1.8)()

31.193

32.10

55

|A∩B|+|A∩C|+|B∩C|

|A∩B|+|A∩C|+|B∩C| 2|A∩B∩C|

33.

k→∞

Ak=[0,1]

34.

k→∞

Bk=

16

35.

k→∞

Ak={0}

36.

Proof:

2

Lemma1.9FG

n(n∈N+∧ k(k∈N+∧k≥n→(F(k)∧G(k)))) n1(n1∈N+∧ k(k∈N+∧k≥n1→F(k)))

∧ n2(n2∈N+∧ k(k∈N+∧k≥n2→G(k)))

x(A(x)∧B(x))= xA(x)∧ xB(x)

”

n=max(n1,n2)

k(k∈N+∧k≥n→(k≥n1∧k≥n2))

“

Q.E.D.

(1)

lim

k→∞Bk lim

k→∞k→∞

Ak∪limAk∨x∈lim

2

n2,n1<n2

)

(

(

n1>n2,n1=

outline)

17

n0(n0∈N+∧ k(¬(k∈N+∧k≥n0)∨(x∈Ak∨x∈Bk))) n0(n0∈N+∧ k(k∈N+∧k≥n0→(x∈Ak∨x∈Bk))) n0(n0∈N+∧ k(k∈N+∧k≥n0→x∈Ak∪Bk))(((

)

))

x∈lim

(Akk) lim

k→∞

∪Bklim→∞

Bk

lim

klim→∞

Ak∪lim

k→∞(Ak

(1)x

∪Bk)

Ak

n0(x)

k≥n0(x)

x∈Akk

x∈/(Ak∪Bk)

k

(Akk→∞

∪Bk) lim

klim→∞

Bk

lim

klim→∞

Ak∪lim

Akk→∞

∪

klim→∞

Ak∪

klim→∞

Ak∪lim

klim→∞

Ak∪

x∈lim

k→∞(Ak∪Bk)x∈Bkx∈

k→∞

limAk∪

k→∞

lim(Ak∪Bk)

k→∞

limBk

x∈

limk→∞Ak∧x∈/

limAk∪lim(Ak∪Bk)

limk→∞(Ak∪

limk→∞Ak∪

Bk)

k→∞

k→∞

limAk∪

k→∞

x

x∈ x∈

k→∞

limBk

k→∞

limBk

((

))

)

n(n∈N+→( k(k∈N+∧k≥n∧x∈Ak)))∨

n(n∈N+→( k(k∈N+∧k≥n∧x∈Bk)))= n(n∈N+→( k(k∈N+∧k≥n∧x∈Ak)∨

k(k∈N+∧k≥n∧x∈Bk)))

n(n∈N+→ k((k∈N+∧k≥n∧x∈Ak)∨

(k∈N+∧k≥n∧x∈Bk)))

n(n∈N+→ k(k∈N+∧k≥n∧(x∈Ak∨x∈Bk))) n(n∈N+→ k(k∈N+∧k≥n∧x∈Ak∪Bk)) x∈

((((

))

)

k→∞

lim(Ak Bk)

((

n(n∈N+→ k(k∈N+∧k≥n∧x∈(Ak Bk))) n(n∈N+→ k(k∈N+∧k≥n∧x∈Ak∧x∈/Bk)) n(n∈N+→ k(k∈N+∧k≥n∧x∈Ak∧

19

))

本文来源：https://www.bwwdw.com/article/4vei.html