离散数学习题解
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
离散数学习题解
7.41.略 7.42.略 7.43.略 7.44.略 7.45.略 7.46.略 7.47.略 7.48.略 7.49.略 7.50.略
33
离散数学习题解 34
习题八
8.1. 1 设 f: ???, 且
?1 ?f (x) ???? ??x 2 ??若x为奇数 若x为偶数
求 f(0), f({0}), f(1), f({1}), f({0, 2, 4, 6, …}), f({4, 6, 8}), f({1, 3, 5, 7})
f(0) = 0,
f({0}) = {f(0)} = {0},
f(1) = 1, f({1}) = {f(1)} = {1},
f({0, 2, 4, 6, …}) = {f(0), f(2), f(4), f(6), …} = {0, 1, 2, 3, …} = ?, f({4, 6, 8}) = {f(4), f(6), f(8)} = {2, 3, 4}, f({1, 3, 5, 7}) = {1, 1, 1, 1} = {1}. 8.2. 2.设 A={1, 2}, B={a, b, c}, 求 BA.
BA={f1, f2, f3, f4, f5, f6, f7, f8, f9}
f1 = {?1, a?, ?2, a?}, f2 = {?1, a?, ?2, b?}, f3 = {?1, a?, ?2, c?}, f4 = {?1, b?, ?2, a?}, f5 = {?1, b?, ?2, b?}, f6 = {?1, b?, ?2, c?}, f7 = {?1, c?, ?2, a?}, f8 = {?1, c?, ?2, b?}, f9 = {?1, c?, ?2, c?}.
8.3. 3.给定函数 f 和集合 A, B 如下: (1) f: R?R, f(x)=x, A={8}, B={4} (2) f: R?R+, f(x)=2x, A={1}, B={1, 2}
(3) f: N?N?N, f(x)= ?x, x+1}, A={5}, B={?2, 3?} (4) f: N?N, f(x)=2x+1, A={2, 3}, B={1, 3} (5) f: Z?N, f(x)=|x|, A={?1, 2}, B={1}
(6) f: S?S, S=[0, 1], f(x)=x/2+1/4, A=(0, 1), B=[1/4, 1/2] (7) f: S?R, S=[0, +∞), f(x)=1/(x+1), A={0, 1/2}, B={1/2} (8) f: S?R+, S=(0, 1), f(x)=1/x, A=S, B={2, 3}. 对以上每一组 f 和 A, B, 分别回答以下问题: (a) f 是不是满射, 单射和双射的?如果 f 是双射的, 求 f 的反函数. (b)
-1
求 A 在 f 下的像 f(A)和 B 在 f 下的完全原像 f(B).
8.4. 4.判断下列函数中那些是满射的? 哪些是单射的? 哪些是双射的? (1) f: ???, f(x) = x2 + 2
(2) f: ???, f(x) = (x)mod 3, x 除以 3 的余数.
?1 (3) f: ???, f (x) ????
?0
?0 ?1
若x为奇数 若x为偶数
若x为奇数 若x为偶数
(4) f: ??{0, 1}, f (x) ????
(5) f: ??{0}?R, f(x)=log10x (6) f: R?R, f(x)=x2?2x?15
离散数学习题解
(1)单射, ∵ f(x) = x2 + 2 在?上是单调的. 不是满射, ∵ ?x??, f(x) = x2 + 2 ??0.
35
(3)不是单射的, ∵ f(0) = f(2) = 0. 不是满射的, ∵ ?x??,
?0 f (x) ?
???1
若x为奇
??2.
数 若x为偶数
(5)是单射的, ∵ f(x)=log10x 在?上是单调的. 不是满射的, ∵ ?x??, f(x)=log10x ??2.
8.5. 设 X = {a, b, c, d}, Y = {1, 2, 3}, f = {?a, 1?, ?b, 2?, ?c, 3?}, 判断以下命题的真假 (1)f 是从 X 到 Y 的二元关系, 但不是从 X 到 Y 的函数; (2) f 是从 X 到 Y 的函数, 但不是从满射, 也不是单射 (3) f 是从 X 到 Y 的满射, 但不是从单射; (4) f 是从 X 到 Y 的双射. 8.6. 对于给定的 A, B 和 f, 判断 f 是否为从 A 到 B 的函数 f : A ??B. 如果是, 说明 f 是否为单射, 满射, 双射的. 2 (1)A = ?, B = ?, f (x) = x+ 1. (2)A = ?, B = _, f (x) = 1 ??x. (3) A = ???, B = _, f (?x, y?) = x ??(y+1).. (4)A = {1, 2, 3}, B = {p, q, r}, f = {?1, q?, ?2, q?, ?3, q?}. (5)A = B = ?, f (x) = 2x. (6) A = B = \\?\\, f (?x, y?) = ?y + 1, x + 1?. (7) A = ???, B = ?, f (?x, y?) = x2 + 2y2. (8) A = B = \\, f (x) = 1 x ??1 . (9) A = ???, B = ?, f (?x, y, z?) = x + y ??z. 8.7. 7.设 A = {a, b, c, d}, B = {0, 1, 2} (1)给出一个函数 f : A ??B, 使得 f 不是单射的也不是满射的; (2)给出一个函数 f : A ??B, 使得 f 不是单射的但是满射的; (3)能够给出一个函数 f : A ??B, 使得 f 是单射但不是满射的吗? (4)设|A| = m, |B| = n, 分别说明存在单射, 满射, 双射函数 f : A ??B 的条件.
(1)答案不唯一. f = {?a, 0?, ?b, 0?, ?c, 0?, ?d, 0?}. (2)答案不唯一. f = {?a, 0?, ?b, 1?, ?c, 2?, ?d, 2?}. (3)不能. 事实上 A 到 B 不存在单射, ∵|A| = 4 > |B| = 3. (4)存在单射的条件是 m ??n, 存在满射的条件是 m ??n, 存在双射的条件是 m = n.
8.8. 给出自然数集?上的函数 f, 使
得 (1)f 是单射的, 但不是满射的; (2)f 是满射的, 但不是单射的. 8.9. 9.设 A 是 n 元集(n ??1), 则从 A 到 A 的函数中有多少个双射函数? 有多少个单射函数. 从 A 到 A 的函数中双射函数和单射函数都有 n!个. 注: 事实上, 从 A 到 A 的函数中满射函数也有 n!个.
8.10.10. 设 f : ??? ???, f (?x, y?) = x + y +
1 (1)说明 f 是否为单射, 满射, 双射的; (2)令 A = {?x, y?|x, y??且 f (?x, y?) = 3}, 求 A; (3)令 B = { f (?x, y?)|x, y?{1, 2, 3}且 x = y}, 求 B.
(1)f 不是单射的, ∵ f (?0, 1?) = f (?0, 1?) = 2. f 不是满射的, ∵ ??x??, f (?x, y?) > 0. 从而 f 不是双射的. (2)要使 f (?x, y?) = x + y + 1 = 3, 可取?x, y??= ?1, 1?, ?0, 2?, ?2, 0?. 故 A = {?1, 1?, ?0, 2?, ?2, 0?}. (3) B = { f (?1, 1?), f (?2, 2?), f (?3, 3?)} = {3, 5, 7}.
8.11.确定 f 是否为从 X 到 Y 的函数, 并对 f : X ??Y 指出哪些是单射, 哪些是满射, 那些是双射的.
2 (1)X = Y = \\, \\为实数集, f (x) = x– x;
(2) X = Y = \\, f (x) =??x;