离散数学习题解 36
(3) X = Y = \\, f (x) = + 1 x ; x ??1 x ??1 (4)X = Y = ?={x| x ???, x > 0}, f (x) = x + 1; 8.12.设 f: S?T, 证明 (1)f (A∩B) ??f (A) ∩ f (B), 其中 A, B ??S. (2)举出反例说明等式 f (A∩B) = f (A) ∩ f (B)不是永远为真的. (3)说明对于什么函数, 上述等式为真. 8.13.设 A 为非空集合, R 为 A 上的等价关系, g: A ??A / R 为自然映射. (1)设 R 为整数集合上的模 n 相等关系, 求 g(2). (2)说明 g 的性质(单射, 满射, 双射). (3)说明在什么条件下, g 为双射函数. 8.14.设 S 为集合, A, B 是 S 的子集, ?T 表示 T 的特征函数, 且?A = {?a, 1?, ?b, 1?, ?c, 0?, ?d, 0?}, ?B = {?a, 0?, ?b, 1?, ?c, 0?, ?d, 1?}, 求?A B. 8.15.15.设 A={1, 2, 3, 4}, A1={1, 2}, A2={1}, A3=?, 求 A1, A2, A3 和 A 的特征函数?A1, ?A2, ?A3 和?A. ∩?x (5)X = Y = ?, f (x) = ???x ?1 .
8.16.16.设 A={a, b, c}. R 为 A 上的等价关系, 且
R={?a, b?, ?b, a?}∪IA
求自然映射 g: A?A/R.
8.17.17．设 f, g, h∈RR, 且 f(x)=x+3, g(x)=2x+1, h(x)=
1 2 求 f○g, g○f, f○f, g○g, h○f, g○h, f○h, g○h○f.
8.18.18．设 f, g, h∈?, 且有
?
?0
f(n)=n+1, g(n)=2n, h(x) ????
?1
求 f○f, g○f, f○g, h○g, g○h, h○g○f
若x为偶数 若x为奇数
8.19.设 f : \\ ??\\, f (x) = x2 ??2, g : \\ ??\\, g(x) = x + 4, h : \\ ??\\, h(x) = x ??1. (1)求 g○f, f○g; (2)问 g○f 和 f○g 是否为单射, 满射, 双射的? (3)f, g, h 中哪些函数有反函数? 如果有, 求出这些反函数. 8.20.20.设 f, g 是从?到?的函数, 且 ?x ?1 ?f (x) ????0 ?x, ??(1)求 f○g x ??0,1, 2, 3 x ??4 x ??5 ? x g(x) ? ??2 ????3 ?? x为偶数 x为奇数 (2)说明 f○g 是否为单射, 满射, 双射的. 离散数学习题解 37
(1)这里的复合运算是右复合: f○g(x) = g(f (x)). 当 x = 1, 3, 4 以及大于 5 的偶数时, f (x)是偶数; 当 x = 0, 2 以及 大于 5 的奇数时, f (x)是奇数, 所以
??x ?1
???2 ,???0, g(x) ????
?3, ??x
??2, ?
并且 f○g: ? ???.
x ??1, 3
?1,
?2, ???0, x ??4
????
x ??0, 2或 ??5的奇
?3,
数 ? x x为大于 的偶数
5 ? ,
??2
x ??1 x ??3
x ??4
x ??0, 2或 ??5的奇数 x为大于5的偶数
(2)f 不是单射的, ∵ f(0) = f(2) = 3. f 是满射的, ∵ ran f ={0, 1, 2, 3}∪{x/2|x 为大于 5 的偶数} = {0, 1, 2, 3}∪{3, 4, 5, …, n, …} = ?.
8.21.21.设 f : ? ?????, f (x) = ?x, x + 1?. (1)说
明 f 是否为单射和满射, 为什么
(2)f 的反函数是否存在, 如果存在, 求出 f 的反函数; (3)求 ran f.
(1)f 是单射的, ∵?x1, x2??, 若 x1 ??x2, 则 f(x1) = ?x1, x1 + 1????f(x2) = ?x2, x2 + 1?. F 不是满射的, 因为若?0, 0????ran f, 则?x??, 使得 f (x) = ?x, x + 1??= ?0, 0?, 而这是不可能的.
(2)因为 f = {?x, ?x, x + 1??| x??}是单射, 它的逆关系 f ?1= {??x, x + 1?, x?| x??}是函数, 是从 ran f 到 dom f = ? 的双射函数. 但 f ?1 不是??? ???的函数, 因为 dom f ?1 = ran f ? ???. (3) ran f={?n, n + 1??n??}.
8.22.设 f: ? ???, f (x) = (x)mod n. 在?上定义等价关系 R, ?x, y??,
?x, y??R ??f(x) = f (y). (1)计算 f (?). (2)确定商集? / R.
8.23.设 f1, f2, f3, f4 为实数集\\到\\的函数, 且
f1(x) = ??
f2(x) = x, f3(x) = ??
???1, x ??0
,
??1, x ??0
??1, x为整数 ???1, 否则
,
f4(x) = 1.
在\\上定义二元关系 Ei, ?x, y?\\, ?x, y??Ei ?f (x) = f (y), 则 Ei 是\\上的等价关系, 称 为 fi 导出的等价关系, 求商集\\/Ei, i = 1, 2, 3, 4.
8.24.24.对于以下集合 A 和 B, 构造从 A 到 B 的双射函数 f: A?B.
(1)A={1, 2, 3}, B={a, b, c} (2)A=(0, 1), B=(0, 2) (3) A={x|x???x<0}, B=? (4) A=R, B=R+
8.25.25.设 f: \\?\\?\\?\\, f(?x, y?)=??(x+y)/2, (x-y)/2?, 证明 f 是双射的.
8.26.设 f: A ??B, g: B ??C, 且 f○g: A ??C 是双射. 证明: (1)f : A ??B 是单射的. (2)g: B ??C 是满射的.
8.27.按照阶从低到高的次序排列下列函数, 如果 f (n)与 g(n)的阶相等, 则表示为 f (n) = ?(g(n)).
33 3
x, ??n, log n, n, nlog n, 2n+ n, 2n, (log n)2, lg n, n+ log n. 8.28.证明
(log n)log n = nloglog n .
4log n = n2; 2log n = n; 2 = n1 / log n;
离散数学习题解 38
2 2log n ??n 2 log n
离散数学习题解 39
习题九
9.1. 1.设 A={a,b,c}, B=2A, 由定义证明 P(A)≈2A.
9.2. 2.设[1, 2]和[0, 1]是实数区间, 由定义证明[1, 2]≈[0, 1]. 9.3. 3.设 A={2x|x∈?}, 证明 A≈?. 9.4. 4.证明定理 9.1. 9.5. 5.证明定理 9.3 的(1), (3). 9.6. 设 A, B, C, D 是集合, 且 A≈C, B≈D, 证明 A×B≈C×D. 9.7. 找出三个不同的?的真子集, 使得他们都与?等势.
9.8. 找出三个不同的?的真子集 A, B, C, 使得 A?·?, B?·?, C?·?. 9.9. 根据自然数的集合定义计算: (1)3∪6, 2∩5 (2)4?3, 3?1 (3)∪4, ∩1 (4)1×4, 22. 9.10.略 9.11.设 A, B 为可数集, 证明
(1)A∪B 是可数集. (2)A×B 是可数集.
离散数学习题解 40
习题十
10.1.列出以下运算的运算表:
1 x 的倒数, 即○x= 1 . (1) A={1,2, }, ?x∈A, ○x 是 2 x
?x,y∈A 有 (2) A={1,2,3,4},x○y=max(x,y),max(x,y)是 x 和 y 之中较大的数.
x ○x 1 1 1 (1) 2 2
1 2 2
10.2.略 10.3.略
10.4.判断下列集合对所给的二元运算是否封闭: (1) 整数集合?和普通的减法运算 (2) 非零整数集合?*和普通的除法运算
1 1 2 3 4 (2) 2 2 2 3 4 3 3 3 3 4 4 4 4 4 4
(3) 全体 n×n 实矩阵集合 Mn(\\)和矩阵加法及乘法运算, 其中 n≥2
(4) 全体 n×n 实可逆矩阵集合关于矩阵加法和乘法运算, 其中 n≥2 (5) 正实数集合\\+和○运算, 其中○运算定义为:
?a,b∈\\+,a○b=ab?a?b
(6) n∈?+,n?={nz|z∈?}.n?关于普通的加法和乘法运算.
(7) A={a1,a2,...,an},n≥2. ○运算定义如下: ?ai,aj∈A,ai○aj=ai.
(8) S={2x?1|x∈?+}关于普通的加法和乘法运算.
(9) S={0,1},S 关于普通的加法和乘法运算.
(10)S={x|x=2n,n∈?+}, S 关于普通的加法和乘法运算.
(1)封闭
(2)不封闭 (3)加法与乘法都封闭 (4)乘法封闭,加法不封闭 (5)不封闭 (6)加法与乘法都封闭 (7)封闭