离散数学习题解 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