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

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

))