2.1相关定义
• 定义9：函数复合，不同函数对原像的多重 映射。
2.2练习
•determin whether each of these functions is a bijection from R to R a)f(x)=-3x+4 b)f(x)=-3x^2+7 c)f(x)=(x+1)/(x+2) d)f(x)=x^5+1
• 定义6：对于共域(codomain)中的每一个元 素，都能在定义域(domain)找到它的原像， 这样的函数 被称为满射
• 定义7：如果函数既是单射也是满射，那么 他被称为双射(或一一映射)
• 定义8：一一映射f的反函数就是以共域中的 元素为原像，映射到f的定义域中的唯一元 素的函数，记做： f 1 （用y表示x，然后 变量替换即可）
• 定义6：有序n元组就是由n个有序元素组成 的结构（排列与组合）
• 定义7：集合A与集合B的笛卡尔积记为 AxB(结果是一个集合，集合元素是一个二 元组，不满足交换律)
1.2集合的相关操作
• 并集 • 交集 • 差集：A-B，在A中并且不在B中的元素 • 德摩根律： ------------- --- ---
集合与映射
1.1相关定义
• 定义1：一组无序，不重复的元素的集合 • 定义2：如果集合包含元素完全相同，那么
集合相等；反之也成立 • 定义3：如果集合A的任意一个元素都是集
合B的元素，那么A是B的子集 • 定义4：集合有n个不同的元素（n>=0），
集合被称为有限集且集合的基数为n
1.1相关定义
• 定义5：集合S的幂集(power set)，就是集 合所有子集的集合，用P(S)表示
2.2练习
•Let f be a function from the set A to the set B. Let S and T be subsets of A. Show that a) f (S ∪ T ) = f (S) ∪ f (T ). b) f (S ∩ T ) ⊆ f (S) ∩ f (T).
2.2练习
• Find f ◦ g and g ◦ f , where f (x) = x^2 + 1 and g(x) = x + 2, are functions from R to R.
• Find f + g and fg for the functions f and g given in the question above
3.1关系
•A与B的二元关系就是AxB中的元素组成的集 合（本质上是一个二元组的集合） •集合A上的关系就是从集合A到集合A的二元 关系 •关系的四个性质：自反性，对称性，反对称 性，传递性 •区分对称性和反对称性 对称性： ab((a,b) R (b, a) R) 反对称性：ab(((a,b) R) ((b, a) R) a b)
A B A B
• 吸收律：并（大）交（小） • 交换律or结合律：同号结合律，异号分配律
多个集合的交集表示：
n
A1
A2
...
An
1
An
n
A1
A2
...
An
1
An
2.1相关定义
•定义1：如果A,B是非空集合，f通过一定的规 则将A中的元素映射到B中的一个元素上，f就 称为从集合A到集合B上的函数(映射，转换)， 记为： f:A->B（注：A中的元素要全部参与） 定义2（接1）：我们称A为函数f的定义域， B为函数f的共域(并不是值域);原像与像 定义3：(f1 + f2)(x) = f1(x) + f2(x)
(f1*f2)(x) = f1(x) * f2(x) (向量运算)
2.1相关定义
•定义4：当且仅当f(a)=f(b)蕴藏a=b(a, b在函 数f的定义域中)时，函数f是单射 •定义5：函数的递增和严格递增，递减和严 格递减 命题逻辑的表示形式：
xy(x y f (x) f ( y))
2.1相关定义
3.2关系的表示
• 维护一个矩阵来表示集合与集合之间的二 元关系
• 假设|A|=n，那么集合A上的关系可以用一 个n*n的方阵来表示
• 用有向图来表示关系（因为元组中的元素 是有序的）
• 边由前一个顶点元素指向后一个顶点元素
3.3关系矩阵的一些结论
•对称位置上的元素都为1，关系具有对称性 •有且只有对角线上的元素为1，关系具有对 称性和反对称性 •对角线上的元素全为1，关系具有自反性 •不存在同时为1的并且处于对称位置的元素， 关系具有反自反性