离散数学课后答案详细(4)

如图所示。

25-(5+4+2+3)-5-1=25-14-5-1=5 不会打球的人共5人

21.设集合A＝{{1，2}，{2，3}，{1，3},{?}},计算下列表达式： （1）?A （2）?A （3）??A （4）??A 解:

（1）?A={1，2}?{2，3}?{1，3}?{?}={1，2，3,?}

（2）?A={1，2}?{2，3}?{1，3}?{?}=?

（3）??A=1?2?3??=?

22.(2)、(3)、(4)、(8)、(10)为真，其余为假。

24.(1)为真，其余为假，因为

(P-Q) = P ? (P-Q)∩Q = P∩Q ? = P∩Q (2)(3)(4)的反例：P ={1} ，Q ={2}

26.(A–B)∪(B–A) = (A∩ =(A∪B)∩( =(A∪B)∩E∩

B)∪(B∩

A)∩(

A) B∪

A)

（4）??A=?

B∪B)∩(A∪

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

C =A∩(B∩

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

B)∪(A∩

C∩C)

27.(1)(A-B)-C = A∩ (2)(A-C)-(B-C)A∩ =A∩ =A∩

C∩(∩

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

C =A∩

(3)(A–B-C=A∩28.(1)A∩(B∪

C∩B=(A–C)–B

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

=A∩B=B∩A (2)

((

A∪

B)∩

A) =

(

A∪

B)∪

A

=(A∩B)∪A = A

29.由第26题有(A-B)∪(B-A)=(A∪B)–(A∩B)，故(A-B)∪(B-A)A∪B。假若x?A∩B，那么x?A∪B，因此x(A∪B)-(A∩B),与(A-B)∪(B-A) = (A∪B)-(A∩B) = A∪B矛盾.

30.AB?x(x?A→x?B)?x(xB→xA) ?x(x?B→x? AB ? 而

A)?

B

A A∪B A∪B=E反之，

A∪AA∪B ? E

A∪BE，因此AB ? A∪B = E ? A∩(

A∪B)= A ? A∩B = A ? AB

综合上述，AB?A∪B = E

AB ? A-B = ? A-BB

反之A-BB ? (A-B)∪BB ? A∪BB ? A∪B = B ? AB 综合上述AB?A-BB

31.任取x ,x?A ? {x} A=>{x}?P(A)=>{x}?P(B)=>{x}B ? x?B

32.先证CA∧CB ? CA∩B,任取x,x?C ? x?C∧x?C ? x?A∧x?B ? x?A∪B,从而得到CA∪B.再证CA∩B ? CA∧CB，这可以由CA∩BA,CA∩BB得到。 33.PQ ? P-Q= ? P-Q

P，反之，P-QP ?

P∩(P-Q)P∩

P ? P-Q= ? PQ

34.令X=，则有∪Y =，即Y = . 35.AB ? A∪

AB∪

A ? EB∪

A因为E为全集,B∪

AE综合上述B∪

A=E.

36.由A∩CB∩C,A-CB-C，利用A∪CB∪D有： (A∩C)∪(A-C) (B∩C)∪(B-C) ? (A∩C)∪(A∩ ? (A∩(C∪37.恒等变形法

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

39.任取x，有x?P(A) ? x A ? x B ? x?P(B)，因此P(A)P(B). 40.(1)任取x有

x?P(A)∩P(B)?x?P(A)∧x?P(B)?xA∧xB ?xA∩B?x?P(A∩B) (2)任取x有

x?P(A)∪P(B)?x?P(A)∨x?P(B)?xA∧xB ? xA∪B?x?P(A∪B)

注意与(1)的推理不同，上面的推理中有一步是“ ? ”符号，而不是“?”符号。 (3)反例如下：A = {1}，B = {2}，则 P(A)∪P(B)= {,{1},{2}} P(A∪B)={,{1},{2},{1,2}}

返回

C)(B∩C)∪(B∩

C)

C)(B∩(C∪C) ? A∩EB∩E ? AB

第七章 二元关系

本章自测答案

1.已知A={?,{?}},求A×P(A)。A×P(A)={ ?{?},{?,{?}}?} 3.(1) 任取< x,y >,有

?(A ∩ B)×(C ∩ D) <=>x?A ∩ B ∧ y ?C ∩ D

?,??,??,{?}?,??,{{?}}?,??,{?,{?}}?,?{?},??,?{?},{?}?,?{?},{{?}}?, ?

?x ?A∧x ? B∧y ?C∧y ? D ?(x ?A∧y ?C )∧(x?B∧y?D) ??A×C∧< x,y >?B×D ??(A×C)∩(B×D)

(2)都为假,反例如下:

A ={1}, B ={1,2}, C ={2}, D ={3} 4.(1)为假,反例如下:A ={1}, B =,C = {2}; (2)为真,证明如下:任取有

?A×(B∩C)×(C∩D)?x?A∩B∧y?B∧y?C ?(x?A∧y?B)∧(x?A∧y?C)

??A×B∧?A×C??(A×B)∩(A×C) (3)为真,令A = 即可; (4)为假,反例如下: A = 7.

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

={<2 . 3>,<2,4>,<3,2>,<3,4>,<4,2>,<4,3>} ∪

LA={<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>} DA={<2,2>,<2,4>,<3,3>,<4,4>}

.8。 列出集合A = {?，{?} {?，{?}}，{?，{?} {?，{?}}} 上的包含关系。??R?={??,??,??,{?}?,??,{?,{?}}?,??,{?,{?},{?,{?}}}?,?{?},{?}?,?{?},{?,{?}}?,?{?},{?,{?},??,{ ?}?}?,?{?,{?}}, {?,{?}}?,?{?,{?}},{?,{?},{?,{?}}}?, ?{?,{?},{?,{?}}},{?,{?},{?,{?}}}?}

9.(1){<1,2>,<1,4>,<1,6>,<2,1>,<2,2>,<2,4> <2,6>,<4,1>,<4,2>,<4,4>, <4,6> <6,1>, <6,2>,<6,4> <6,6>} (2){<1,2>,<2,1>};

(3){<1,1>,<2,1>,<4,1>,<6,1>,<2,2>,<4,2>,<4,4>,<6,6>} (4){<1,2>,<2,2>,<4,2>,<6,2>}

.11.R i是X上的二元关系、 对于x?X定义集合

R 我 (x) = {y|xR 我 y}。显然Ri(x) ?X。如果X = {? 4，? 3，? 2，? 1，0、 1、 2、 3、 4}，且令 R1 = {〈x，y〉|x，y?X∧x < y}R2 = {〈x，y〉|x，y?X∧y?1 < x < y + 2} R3 = {〈x、 y〉|x、 y?X∧x2≤y} 求R1 (0) R1 (1) R2 (0)，R2 (? 1)，R3 (3)。R1 (0) = {1,2,3,4}R1 (1) = {2,3,4}R2 (0) = {? 1，0}R2 (? 1) = {? 2，? 1}R3 (3) = ? 12.（略）

13.A∩B = {<1,2>,<2,4>,<3,3>,<1,3>,<4,2>}, A ∩ B ={<2,4>} domA = {1,2,3},domB = {1,2,4},dom(A ∪ B) = {1,2,3,4}

ranA = {2,3,4},ranB = {2,3,4},ran(A ∪ B) = {4},fld(A - B) = {1,2,3}

14.RR = {<0,2>,<0,3>,<1,3>}

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

15.设 ????A = {〈?，{?，{?}} 〉、 〈 {?} ?〉} 求A?1、 A2、 A3 {?}、 [?]，A?，{{?}}、 [{{?}}]。??A?1 ={?{?,{?}},??,??,{?}?}, ??A2 ={?{?},{?,{?}}?}, ??A3 =?, ??A{?}={??,{?,{?}}?}, ??A[?]={?,{?}}, 33 ??A?=?, ??A{{?}}={?{?},??}, ??A[{{?}}]=?

16．设A={a,b,c,d}，R1，

R2为A上的关系，其中

R1=?a,a,a,b,b,d?

R2??a,d,b,c,b,d,c,b求R1?R2,R2?R1,R1,R2。 解: R1?R2={,,} R2?R1={}

23?

R1=R1?R1={,,}

2

R2=R2?R2={,,}

2

R2=R2?R2={,,}

3

2

18.(1)F(G∪H) = FG∪FH 任取 ,有

?F (G∪H)?t(?F∧?G∪H) ?t(?F∧(?G∨?H))

?t((?F∧?G)∨(?F∧?H)) ?t(?F∧?G)∨t(?F∧?H)) ??FG∨?FH??FG∪FH (2)和(4)类似可证 19.(2)任取y,有

y?R[T∪W]?x(x?T∪W∧?R) ?x((x?T∨x?W)∧?R

?x((x?A∧?R)∨(x?W∧?R)) ?x(x?T∧?R)∨x(x?W∧?R) ?y?R[T]∨y?R[W]?y?R[T]∩R[W] (3)任取,有

?F(A∩B)?x?A∩B?F ?x?A∧x?B∧?F

?(x?A∧?F)(x?B∧?F) ??FA∧?FB ??FA∩F B 20.(1)任取,有 ?(

∪

) <=>?∨

?

∪

?? ?? ??

∨?∪

(2)和(1)类似可证.

21.只有对称性,因为1+1≠10,<1,1>R,R不是自反的,又由于<5,5>?R,因此R不是反自反的,根据xRy?x+y = 10=>yRx ,可知R是对称的,又由于<1,9>,<9,1>都是属于R,因此R不是反对称的, <1,9>,<9,1>都属于R,如果R是传递的,必有<1,1>属于R.但这是不成立的,因此R也不是传递的. 22.(1)关系图如图7.15所示; (P148) (2)具有反自反性、反对称性、传递性.

26.(1)R={<3,3>,<3,1>,<3,5>}, = {<3,3>,<3,1>,<3,5>}

(2)r(R)={<1,1>,<1,5>,<2,2>,<2,5>,<3,3>,<3,1>,<4,4>,<4,5>,<5,5>,<6,6>} s(R)={<1,5>,<5,1>,<2,5>,<5,2>,<3,3>,<3,1>,<1,3>,<4,5>,<5,4>} T(R)={<1,5>,<2,5>,<3,3>,<3,1>,<3,5>,<4,5>} 31.(1)R = {<2,3>,<3,2>,<2,4>,<4,2>,<3,4>,<4,3>}∪32.(1)不是等价关系，因为<1,1> R，R不是自反的；

(2)不是等价关系，因为R不是传递的，1R3，3R2但是没有1R2； (3)不是等价关系，因为<2,2> R，R不是自反的； (4)不是等价关系，因为R不是传递的。 (5)是等价关系。

33．关系图如图7.17说示 (P151) [a] = [b] ={a,b},[c] = [d] = {c,d}

；(2)R； (3)R.

36．设A={1，2，3，4}，在A?A上定义二元关系R，

?,A?A ，〈u,v> R ?u + y = x + v. (1) 证明R 是A?A上的等价关系. (2)确定由R 引起的对A?A的划分. （1）证明：∵R ?u+y=x-y

∴R?u-v=x-y

???A?A

∵u-v=u-v ∴R ∴R是自反的

任意的,?A×A 如果R ，那么u-v=x-y ∴x-y=u-v ∴R ∴R是对称的

任意的,,?A×A 若R,R 则u-v=x-y,x-y=a-b