集合函数数列与求和.ppt

离散数学第2章集合 函数 数列与求和 2 2 1集合 定义1 集合是一组无序的对象定义2 集合中的对象也称为该集合的元素 或成员 如果一个集合的元素的数目是有限的并且不是很多 便可以通过列举出它的所有元素来描述它 A 1 2 3 4 一个集合由它的元素所决定而与其元素顺序无关 A 1 3 4 2 集合中的某些元素可以重复列举多次 但集合中只包含一个这样的元素 A 1 2 2 3 4 如果集合是一个包含了很多元素的有限集或是无限集 可以通过列举集合中每个元素必须满足的性质来描述 B x x是正偶数 3 定义3 两个集合相等当且仅当它们有相同的元素 X与Y相等 记做X Y 用符号表示 X Y当且仅当 例 A x x2 x 6 0 B 2 3 A B 4 子集 定义4 集合A是集合B的子集当且仅当A的每个元素也是B的元素 AB 任何集合X是其自身的子集 因为X中的每一个元素在X中 例 C 1 3 A 1 2 3 4 则C是A的一个子集 A是B的子集 当且仅当 x x A x B 为真 定义5 如果X是一个有限集合 令 X 是集合X的基数 即集合X中元素的个数如果x在X中 记做x X 如果x不在X中 记做x X 没有元素的集合称为空集 或零集 用符号 表示 2 1 2幂集 如X是Y的子集但X不等于Y 则X是Y的一个真子集空集是任何集合的子集定义7 集合X的所有子集的集合 称为X的幂集 用P X 表示 7 例 如A a b c P A 的成员 a b c a b a c b c a b c A 3 P A 23 8 8 定理 如 X n 则 P X 2n 9 2 1 3笛卡儿积 一个由两个元素组成的有序对 或序偶 写为 a b a b c d 当且仅当a c b d 定义8 有序n元组 a1 a2 an 是以a1为第一个元素 a2为第二个元素 an为第n个元素的有序组定义9 X Y集合 X Y称为X和Y的笛卡儿积 是所有有序对 x y 的集合 其中x X y Y 即X Y x y x X y Y 10 例 X 1 2 3 Y a b X Y 1 a 1 b 2 a 2 b 3 a 3 b Y X a 1 a 2 a 3 b 1 b 2 b 3 X X 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3 Y Y a a a b b a b b 11 X Y 1 a 1 b 2 a 2 b 3 a 3 b 12 例 四种餐前开胃菜 r 排骨 n 烤干酪辣味玉米片 s 虾 f 炸干酪 三种主菜 c 鸡肉 b 牛肉 t 鲑鱼 若令A r n s f E c b t 则笛卡儿积A E包含了12种可能的由一种开胃菜和一种主菜组成的正餐 13 n元组 一个n元组记为 a1 a2 an 这同样也是考虑顺序的 如 a1 a2 an b1 b2 bn 当且仅当a1 b1 a2 b2 an bn集合X1 X2 Xn的笛卡儿积定义为所有n元组 x1 x2 xn 构成的集合 其中xi Xi i 1 n 并记为X1 X2 Xn 14 X Y Z X 1 2 Y a b Z c d X Y Z X Y Z 1 a c 1 a d 1 b c 1 b d 2 a c 2 a d 2 b c 2 b d 2 1 4使用带量词的集合符号 x S P x x x S P x 例 语句 x R x2 0 任意实数的平方是非负的 x Z x2 1 有某个整数 其平方等于1 15 2 1 5量词的真值集合 集合理论 谓词逻辑谓词P的论域是D 定义P的真值集合 D中元素x使得P x 为真的元素组成的集合 记为 x D P x 例 论域是整数集合 P x x 1 Q x x2 2R x x x 问谓词P x Q x R x 的真值集合分别是什么 解 P的真值 x Z x 1 1 1 Q的真值 x Z x2 2 R的真值 x Z x x N 非负整数集合 16 17 2 2集合运算 并集X Y x x X y Y 交集X Y x x X y Y 差集X Y x x X x Y 不相交X Y S两两不相交的 18 例 A 1 3 5 B 4 5 6 A B 1 3 4 5 6 A B 5 A B 1 3 B A 4 6 19 例 集合 1 4 5 和 2 6 是不相交的S 1 4 5 2 6 3 7 8 是两两不相交的 20 全集 补 U 全集X 子集集合U X称为X的补 表示为X 21 例 A 1 3 5 如U 1 2 3 4 5 则A 2 4 如给定U 1 3 5 7 9 则A 7 9 22 Venn图 关于集合的形象化表示 1 2 4 3 A B 1 2 4 3 A B 2 2 2集合恒等式 U全集 X Y Z U结合律 A B C A B C A B C A B C 交换律A B B AA B B A 分配律A B C A B A C A B C A B A C 同一律A A A U A互补律A U A 幂等律A A A A A A上下界律A U U A 吸收律A A B A A A B A 对合律A A零一律 U U 德 摩根律 A B A B A B A B 24 Sand S S为集族 集合的集合 S x 对于某些X S x X S x 对于所有X S x X S A1 A2 An S Ai S Ai 任意集族S的并集是由所有至少属于S的一个集合X的元素构成的集合 任意集族S的交集是由所有属于S的每个集合X的元素x构成的集合 例S1 a b c z S2 1 2 3 4 5 6 7 8 9 0 S3 S4 S5 A B C Z S S1 S2 S3 S4 S5 S 任何属于S中的一个集合Si的元素构成的集合 25 26 例 Ai i i 1 i 2 S A1 A2 S Ai 1 2 S Ai n n 1 n 2 27 划分 一个由集合X的非空子集的整体组成的S 如X的每个元素都只属于S的某一个元素 S就称为X的一个划分 例 集合X 1 2 3 4 5 6 7 8 S 1 4 5 2 6 3 7 8 S是X的一个划分 28 问题求解要点 本节复习1 给出集合的定义 2 集合怎样用符号表示 3 如果X是有限集 X 表示什么 4 如何表示x是集合X的元素 5 如何表示x不是集合X的元素 6 如何表示空集 7 设X和Y是集合 给出X Y的定义 8 设X和Y是集合 给出XY的定义 9 给出X是Y的真子集的定义 10 什么是集合X的幂集 怎样表示 29 11 如果X有n个元素 X的幂集有多少个元素 12 给出X与Y的并的定义 怎样表示X与Y的并集 13 如果是一个集族 的并集的定义是什么 怎样表示的并集 14 给出X与Y的交的定义 怎样表示X与Y的交集 15 如果是一个集族 的交集的定义是什么 怎样表示的交集 16 给出X与Y是不相交的集合的定义 17 什么是两两不相交的集族 18 给出集合X与Y的差集的定义 怎样表示差集 19 什么是全集 20 什么是集合X的余集 如何表示 2 3函数 距离 速度 时间如果以每小时55英里的速度行进t个小时 则D 55t 其中t 时间 D 行进的距离函数将集合X中的每一个元素指派为集合Y中惟一的一个元素 集合X和集合Y可能相同也可能不同 上式定义的函数将每一个非负实数t指派为55t 例如 将t 1指派为55 将t 3 45指派为189 75 等等 可以将这种指派表示为有序对 1 55 3 45 189 75 形式化地说 函数是一种特殊的由有序对组成的集合 定义1 定义 令A和B为非空集合 从A到B的函数f是对元素的一种指派 对A的每个元素恰好指派B的一个元素 f a b表示f指派给A中的元素a的唯一B中的元素是bf A B 表示f是从A到B的函数f是从A到B的函数 集合A称为f的定义域 集合 b a b f B的一个子集 称为f的值域 例 集合f 1 a 2 b 3 a 是从X 1 2 3 到Y a b c 的函数 例 集合 1 a 2 a 3 b 不是从X 1 2 3 4 到Y a b c 的函数因为X中的元素4没有被指派为Y中的元素 例 集合 1 a 2 b 3 c 1 b 不是从X 1 2 3 到Y a b c 的函数因为1没有被指派为Y中惟一的元素 例 xn axn 1 c modm 例 m 11 a 7 c 5 s 3x1 ax0 c modm 7 3 5 mod11 4x2 ax1 c modm 7 4 5 mod11 0类似地 可以算出x3 5 x4 7 x5 10 x6 9 x7 2 x8 8 x9 6 x10 3 定义3 1 17 x 小于等于x的最大整数 x 大于等于x的最小整数 8 3 8 8 3 9 2 3 2一对一函数和映上函数 单射 满射函数 映上函数 一对一的 定义5 单射 一对一 从X到Y的函数f称为是一对一的 如果对每个y Y 至多有一个x X使得f x y 例2 2 22从X 1 2 3 到Y a b c d 的函数f 1 b 3 a 2 c 是一对一的 例 函数f 1 a 2 b 3 a 不是一对一的 因为f 1 a f 3 设X是有社会保障号的人的集合 对每个人x X 指定他或她与其社会保障号SS x 相对应 这样就得到了一个一对一的函数 因为需要给不同的人指定不同的社会保障号 由于这个对应是一对一的 因此可以把社会保障号用做身份证明 从X到Y的函数f是一对一的 等价于 对所有的x1 x2 X 若f x1 f x2 则x1 x2 用符号表示为 x1 x2 f x1 f x2 x1 x2 例 证明从正整数集合到正整数集合的函数f n 2n 1是一对一的 张明 必须证明对所有正整数n1和n2 如果f n1 f n2 则n1 n2 先假定f n1 f n2 依据f的定义 将这个等式变形为2n1 1 2n2 1将两边同时减1 然后同除以2 可得n1 n2所以 f是一对一的 例 如果存在x1和x2使得f x1 f x2 且x1 x2 那么一个函数不是一对一的证明从正整数集合到整数集合的函数f n 2n n2不是一对一的 必须找到正整数n1和n2 且n1 n2 使得f n1 f n2 f 2 f 4 定义7 映上函数 满射函数 如果从X到Y的函数f的值域是Y 则称函数f为对Y映上的 例2 2 29从X 1 2 3 到Y a b c 的函数f 1 a 2 c 3 b 是一对一的 并且是对Y映上的 例2 函数f 1 b 3 a 2 c 不是对Y a b c d 映上的 而是对 a b c 映上的 例 例 证明从正整数集合X到正整数集合Y的函数f n 2n 1不是对Y映上的 必须找到一个元素m Y 使得对所有的n X f n m 因为对所有的整数n f n 是奇数 所以可以选择一个正偶数y 例如选择y 2 有y Y且对于所有的n X f n y 定义8 如果一个函数既是一对一的又是映上的 则称这个函数为双射 例2 2 29从X 1 2 3 到Y a b c 的函数f 1 a 2 c 3 b 是一对一的 并且是对Y映上的 2 3 3反函数 设f是从X到Y的一对一的 映上的函数 可以证明 y x x y f 也是一个从Y到X的一对一的 映上的函数 将这个新函数记做f 1 称为f的反 逆 函数 inverse 例 函数f 1 a 2 c 3 b 的逆函数 f 1 a 1 c 2 b 3 例 函数f x 2x是从R到R 上的一对一函数 其中R表示实数集 R 表示正实数集 f 1 y x log2y 定义10复合函数 令g为从X到Y的函数 f为从Y到Z的函数 f与g的复合函数记为f g f g x f g x 是从X到Z的函数 例 给定从X 1 2 3 到Y a b c 的函数g 1 a 2 b 3 c 和从Y到Z x y z 的函数f a y b x c z 从X到Z的复合函数为f g 1 y 2 y 3 z 例3 1 41 例 如果f x log3x且g x x4 则f g x log3 x4 g f x log3x 4