离散数学习题解 29

习题七

7.1. 已知 A={?,{?}},求 A×P(A).

A×P(A)={ ???,??,??,{?}?,??,{{?}}?,??,{?,{?}}?,?{?},??,?{?},{?}?,?{?},{{?}}?, ?{?},{?,{?}}?} 7.2. 对于任意集合 A,B,C, 若 A×B?A×C,是否一定有 B?C 成立? 为什么? 不一

定, 因为有反例: A=?,B={1},C={2},B?C,A×B=?=A×C.

7.3. 设 A, B, C, D 是任意集合,

(1) 求证(A∩B)×(C∩D)=(A×C)∩(B×D).

(2) 下列等式中哪个成立? 那些不成立?对于成立的给出证明, 对于不成立的举一反例.

(A∪B)×(C∪D)=(A×C)∪(B×D) (A?B)×(C?D)=(A×C) ??(B×D)

(1) ??x,y??

?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)

??x,y?∈(A×B) ??x,y?∈(C×D) ??x,y?∈A×B∩C×D (A∩B)×(C∩D)=(A×C)∩(B×D)

(2)都不成立, 反例: A={1,2},B={2,3},C={1,2},D={2,3} (A∪B)×(C∪D)={1,2,3}×{1,2,3}?(A×C)∪(B×D) (A?B)×(C?D)={1}×{1}?(A×C) ??(B×D)

7.4. 略

7.5. 设 A, B 为任意集合, 证明

若 A×A=B×B, 则 A=B.

?x,

x∈A??x,x?∈A×A??x,x?∈B×B?x∈B A=B

7.6. 列出从集合 A={1, 2}到 B={1}的所有的二元关系.

R1=??,R2={?1,1?},R2={?2,1?},R3={?1,1?,?2,1?}.

7.7. 列出集合 A={2, 3, 4}上的恒等关系 IA, 全域关系 EA, 小于或等于关系 LA, 整除关系 DA.

IA={?2,2?,?3,3?,?4,4?} EA=A×A={?2,2?,?2,3?,?2,4?,?3,2?,?3,3?,?3,4?,?4,2?,?4,3?,?4,4?} LA={?2,2?,?2,3?,?2,4?,?3,3?,?3,4?,?4,4?} DA={?2,2?,?2,4?,?3,3?,?4,4?}

7.8. 列出集合 A={?, {?}, {?, {?}}, {?, {?}, {?, {?}}}}上的包含关系.

R?={??,??,??,{?}?,??,{?,{?}}?,??,{?,{?},{?,{?}}}?,?{?},{?}?,?{?},{?,{?}}?,?{?},{?,{?},??,{ ?}?}?,?{?,{?}}, {?,{?}}?,?{?,{?}},{?,{?},{?,{?}}}?, ?{?,{?},{?,{?}}},{?,{?},{?,{?}}}?}

7.9. 设 A={1, 2, 4, 6}, 列出下列关系 R:

(1) R={?x, y?|x, y∈A?x+y?2} (2) R={?x, y?|x, y∈A?|x?y|=1}

离散数学习题解

(3) R={?x, y?|x, y∈A?x/y∈A} (4) R={?x, y?|x, y∈A?y 为素数}

(1)R={?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?}=EA?{?1,1?} (2)R={?1,2?,?2,1?}

(3)R={?1,1?,?2,2?,?4,4?,?6,6?,?2,1?,?4,2?,?4,1?} (4)R={?1,2?,?2,2?,?4,2?,?6,2?}

30

7.10.略 7.11.Ri 是 X 上的二元关系, 对于 x∈X 定义集合

Ri(x)={y|xRiy}.

显然 Ri(x) ?X. 如果 X={?4, ?3, ?2, ?1, 0, 1, 2, 3, 4}, 且令

R1={?x, y?|x, y∈X?x

求 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)= ??

7.12.设 A={0, 1, 2, 3}, R 是 A 上的关系, 且

R={?0, 0?, ?0, 3?, ?2, 0?, ?2, 1?, ?2, 3?, ?3, 2?}

给出 R 的关系矩阵和关系图. 7.13.设

A = {?1, 2?, ?2, 4?, ?3, 3?} B = {?1, 3?, ?2, 4?, ?4, 2?}

求 A∪B, A∩B, domA, dom(A∪B), ranA, ranB, ran(A∩B), fld(A?B).

A∪B={?1,2?, ?1,3?, ?2,4?, ?3,3?, ?4,2?} A∩B={?2,4?} domA={1,2,3} dom(A∪B)={1,2,3,4} ranA={2,3,4} ranB={3,4,2} ran(A∩B)={4} fld(A?B)={1,2,3}

7.14.设

?1

R={?0,1?,?0,2?,?0,3?,?1,2?,?1,3?,?2,3?}

求 R○R,R,R?{0,1},R[{1,2}].

R○R={?0,2?, ?0,3?, ?1,3?}

R?1={?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}

7.15.设

?1

2A={??,{?,{?}}?,?{?},??}

求 A,A,A3,A?{?},A[?],A??,A?{{?}},A[{{?}}].

A?1={?{?,{?}},??,??,{?}?}, A2={?{?},{?,{?}}?}, A3=?,

A?{?}={??,{?,{?}}?}, A[?]={?,{?}},

离散数学习题解

A??=?,

A?{{?}}={?{?},??}, A[{{?}}]=??

31

7.16.设 A={a,b,c,d}, R1,R2 为 A 上的关系, 其中

R1={?a,a?,?a,b?,?b,d?} R2={?a,d?2 ,?b,c?,?b,d?,?c,b?} 3

求 R1○R2, R2○R1,R1 ,R2 .

R1○R2={?a,a?,?a,c?,?a,d?}, R2○R1={?c,d?}, 2R 1 ={?a,a?,?a,b?,?a,d?}, 3R 2 ={?b,c?,?b,d?,?c,b?}

7.17.设 A={a,b,c}, 试给出 A 上两个不同的关系 R1 和 R2,使得 R1 =R1, R2 =R2.

R1={?a,a?,?b,b?}, R2={?b,c?,?c,b?}

7.18.证明定理 7.4 的(1), (2), (4).

2

3

(1) F○ (G∪H)=F○G∪F○H

任取?x,y?,

?x,y?∈F○ (G∪H)

??t(?x,t?∈F??t,y?∈G∪H)

??t(?x,t?∈F??(?t,y?∈G??t,y?∈H))

??t((?x,t?∈F??t,y?∈G) ??(?x,t?∈F??t,y?∈H)) ??t(?x,t?∈F??t,y?∈G) ??t(?x,t?∈F??t,y?∈H)) ??x,y?∈F○G??x,y?∈F○H ??x,y?∈F○G∩F○H 所以有 F○ (G∩H)??F○G∩F○H.

(2) (G∪H) ○F=G○F∪H○F 任取?x,y?,

?x,y?∈(G∪H) ○F

??t(?x,t?∈(G∪H) ??t,y?∈F)

??t((?x,t?∈G??t,y?∈H) ??t,y?∈F))

??t((?x,t?∈G??t,y?∈F) ??(?x,t?∈H??t,y?∈F)) ??t(?x,t?∈G??t,y?∈F) ??t(?x,t?∈H??t,y?∈F)) ??x,y?∈G○F??x,y?∈H○F ??x,y?∈G○F∪H○F

(4) (G∩H) ○F?G○F∩H○F 任取?x,y?,

?x,y?∈(G∩H) ○F

??t(?x,t?∈(G∩H) ??t,y?∈F)

??t((?x,t?∈G??t,y?∈H) ??t,y?∈F))

??t((?x,t?∈G??t,y?∈F) ??(?x,t?∈H??t,y?∈F)) ??t(?x,t?∈G??t,y?∈F) ??t(?x,t?∈H??t,y?∈F)) ??x,y?∈G○F??x,y?∈H○F ??x,y?∈G○F∪H○F

7.19.证明定理 7.5 的(2), (3).

(2) F[A∪B]=F[A]∪F[B]

任取 y,

离散数学习题解

y∈F[A∪B]

??x(?x,y?∈F?x∈A∪B) ??x(?x,y?∈F??(x∈A?x∈B))

??x((?x,y?∈F?x∈A) ??(?x,y?∈F?x∈B)) ??x(?x,y?∈F?x∈A) ??x(?x,y?∈F?x∈B) ?y∈F[A] ?y∈F[B] ?y∈F[A]∪F[B] 所以有 F[A∩B]=F[A]∪F[B].

(3) F? (A∩B) ?F?A∩F?B

任取?x,y??

?x,y?∈F? (A∩B) ??x,y?∈F?x∈(A∩B) ??x,y?∈F??(x∈A?x∈B)

??(?x,y?∈F?x∈A) ??(?x,y?∈F?x∈B) ??x,y?∈F?A??x,y?∈F?B

??x,y?∈F?A∩F?B 所以有 F? (A∪B) ?F?A∩F?B.

32

7.20.设 R1 和 R2 为 A 上的关系, 证明:

(1)(R1∪R2) ?1=R1 ∪R2

(2)(R1∩R2) ?1=R1 ∩R2

?1 ?1 ?1

?1 ?1

(1)(R1∪R2) ?1=R1 ∪R2

任取?x,y??

?x,y?∈(R1∪R2) ?1 ??y,x?∈(R1∪R2) ??y,x?∈R1??(y,x)∈R2) ?1

?1

??x,y?∈R1 ?1 ??x,?y1 ?∈R2 ??x,y?∈R1 ??R1 2 ?1

?1

所以(R1∪R2) =R1 ∪R2

(2)(R1∩R2) ?1=R1 ∩R2

?1

?1

?1

任取?x,y??

?x,y?∈(R1∩R2) ?1 ??y,x?∈(R1∩R2) ??y,x?∈R1??(y,x)∈R2) ?1

?1

??x,y?∈R1 ?1 ??x,?y1 ?∈R2 ??x,y?∈R1 ?R2

所以(R1∪R2) ?1=R1 ∩R2

7.21.略 7.22.略 7.23.略 7.24.略 7.25.略 7.26.略 7.27.略 7.28.略 7.29.略 7.30.略 7.31.略 7.32.略 7.33.略 7.34.略 7.35.略 7.36.略 7.37.略 7.38.略 7.39.略 7.40.略

?1 ?1