离散期末复习资料(2)

(2) 等价类是什么？

解 (1) 任取正整数x，x / x = 1 = 20，所以xRx，R是自反的。 若xRy，则有整数m使得x / y = 2m，y / x = 2?m，? m也是整数，所以yRx，R是对称的。 若xRy且yRz，则有整数m, n使得x / y = 2m，y / z = 2n， x / z = (x / y)?( y / z) = 2m ? 2n = 2m+n m + n也是整数，所以xRz，R是传递的。R是等价关系。 (2) 对于每个正奇数k，{ x | ?m (m?N ? x = k ? 2m)}是等价类。

[1]R = {1, 2, 4, 8, 16,?} [3]R = {3, 6, 12, 24, 48,?}

?

第七章 考点：

1、给定一个函数，判断函数究竟是单射，满射，双射？ 例题：1. f : N → N , f (x) = 2x ，是单射，不是满射，因

为奇数不在值域中。

2. f : N → N , f (x) = x + 1，是单射，不是满射， 因为0 不在值域中。

3. f : I → I , f (x) = x + 1，是双射。

4. f : N → N × N ，f (x) = < x, x > ，是单射，不是 满射，因为< 0, 1 > 不在值域中。

5. f : R → I， f (x) = ?x? ，不是单射，因为 f (1) = f (1.5)；是满射。

6. f : I → I , f (x) = | x | ，不是满射，因为负整数 不在值域中；不是单射，因为f (1) = f (?1) 。

7. f : R→ R , f (x) = 2x + 3， f 是双射。

8．f : R→ R , f (x) = x2 ，不是单射也不是满射，更不是双射。 2、函数的运算（非常重要，尤其是后面这道题） 定义7.7 设f : X → X，f n 定义如下： 1. f 0(x) = x 2. f n+1(x) = f ( f n(x))

定理7.1 若f : X → Y 且g : Y → Z ，则函数的复合g ° f 是

一个从X到Z的函数，即g ° f : X → Z ，且对所有的

x∈X，( g ° f )(x) = g (f (x))。

例7.15设f : R→ R 定义为f (x) = x + 2 ， 设g : R→ R 定义为g (x) = x ? 2 ， 设h : R→ R 定义为h (x) = 3x ， 则g ° f (x) = x + 2 ? 2 = x f ° g (x) = x ? 2 + 2 = x f ° f (x) = x + 2 + 2 = x + 4 g ° g (x) = x ? 2 ? 2 = x ? 4 f ° h (x) = 3x + 2

h ° g (x) = 3(x ? 2) = 3x ? 6 h ° f (x) = 3(x + 2) = 3x + 6

f °h ° g (x) = 3(x ? 2) + 2 = 3x ? 4 重要题目：课本140页第6题

第八章 考点：（第八章不考） 1、证明两个集合等势？

概念：两个集合A和B是等势的，当且仅当A和B的元素是一一对应的，记作A~B、 方法一：集合是有穷的，当且仅当它与某个自然数等势。（每个自然数是比它小的所有自然数的集合）

方法二：构造函数，将集合一一对一映射到集合二上，使两集合元素一一对应。 例一：设N=｛0，1，2??｝，E=｛0，2，4??｝，求证 N~E 提示：建立函数关系f:N→E由f（n）=2n给定，这里n∈N

函数f是双射函数，在N和E之间建立起一一对应，因此，N~E 例二：自然数集合N与有理数集合Q等势 见课本146页例8.6

例三：开区间（0，1）与实数集合R等势，证明：

提示：构造函数f（x）=tgπ（2x-1）/2, f把（0，1）一对一并且连续的映射到R上。 注意：：两集合的一一对应的关系不是唯一的。

方法三：自然数集合的基数以及有理数、整数、奇数、偶数集的基数都是阿列夫零 实数集的基数是C=2^阿列弗0 自然数集合的幂集的基数和实数集基数相等

注意：不存在最大的集合。。