离散数学高等教育出版社配套屈婉玲耿.ppt
《离散数学高等教育出版社配套屈婉玲耿.ppt》由会员分享,可在线阅读,更多相关《离散数学高等教育出版社配套屈婉玲耿.ppt(40页珍藏版)》请在三一文库上搜索。
1、1,主要内容 集合的基本概念 属于、包含 幂集、空集 文氏图等 集合的基本运算 并、交、补、差等 集合恒等式 集合运算的算律、恒等式的证明方法,第二部分 集合论,第六章 集合代数,2,6.1 集合的基本概念,1. 集合定义 集合没有精确的数学定义 理解:由离散个体构成的整体称为集合,称这些个体为集 合的元素 常见的数集:N, Z, Q, R, C 等分别表示自然数、整数、有 理数、实数、复数集合,2. 集合表示法 枚举法-通过列出全体元素来表示集合 谓词表示法-通过谓词概括集合元素的性质 实例: 枚举法 自然数集合 N=0,1,2,3, 谓词法 S= x | x是实数,x21=0,3,元素与集
2、合,1. 集合的元素具有的性质 无序性:元素列出的顺序无关 相异性:集合的每个元素只计 数一次 确定性:对任何元素和集合都 能确定这个元素是否 为该集合的元素 任意性:集合的元素也可以是 集合 2元素与集合的关系 隶属关系:或者 3集合的树型层次结构,d A , a A,4,集合与集合,集合与集合之间的关系:, =, , , , 定义6.1 A B x ( xA xB ) 定义6.2 A = B A B B A 定义6.3 A B A B A B A B x ( xA xB ) 思考: 和 的定义 注意 和 是不同层次的问题,5,空集、全集和幂集,1定义6.4 空集 :不含有任何元素的集合 实
3、例: x | xR x2+1=0 定理6.1 空集是任何集合的子集。 证 对于任意集合A, A x (xxA) T (恒真命题) 推论 是惟一的,3. 定义6.6 全集 E:包含了所有集合的集合 全集具有相对性:与问题有关,不存在绝对的全集,2. 定义6.5 幂集:P(A)= x | x A 实例:P()=, P()=, 计数:如果 |A|=n,则 |P(A)|=2n.,6,6.2 集合的运算,初级运算 集合的基本运算有 定义6.7 并 AB = x | xA xB 交 AB = x | xA xB 相对补 AB = x | xA xB 定义6.8 对称差 AB = (AB)(BA) 定义6.
4、9 绝对补 A = EA,7,文氏图,集合运算的表示,A,B,A,B,A,B,A,B,A,B,AB,AB,AB,AB,A,8,几点说明,并和交运算可以推广到有穷个集合上,即 A1 A2 An = x | xA1 xA2 xAn A1 A2 An = x | xA1 xA2 xAn A B AB = AB = AB = A,9,广义运算,1. 集合的广义并与广义交 定义6.10 广义并 A = x | z ( zA xz ) 广义交 A= x | z ( zA xz ) 实例 1, 1,2, 1,2,3=1,2,3 1, 1,2, 1,2,3=1 a=a, a=a a=a, a=a,10,关于广
5、义运算的说明,2. 广义运算的性质 (1) =,无意义 (2) 单元集x的广义并和广义交都等于x (3) 广义运算减少集合的层次(括弧减少一层) (4) 广义运算的计算:一般情况下可以转变成初级运算 A1, A2, , An=A1A2An A1, A2, , An=A1A2An 3. 引入广义运算的意义 可以表示无数个集合的并、交运算,例如 x | xR=R 这里的 R 代表实数集合.,11,运算的优先权规定,1 类运算:初级运算, , , , 优先顺序由括号确定 2 类运算:广义运算和运算, 运算由右向左进行 混合运算:2 类运算优先于1 类运算,例1 A=a,a,b,计算A(AA). 解:
6、 A(AA) = a,b(a,ba) = (ab)(ab)a) = (ab)(ba) = b,12,有穷集合元素的计数,1. 文氏图法 2. 包含排斥原理 定理6.2 设集合S上定义了n条性质,其中具有第 i 条性质的 元素构成子集Ai, 那么集合中不具有任何性质的元素数为,推论 S中至少具有一条性质的元素数为,13,实例,例2 求1到1000之间(包含1和1000在内)既不能被5和6整 除,也不能被8整除的数有多少个?,解 方法一:文氏图 定义以下集合: S= x | xZ 1x1000 A= x | xS x可被5整除 B= x | xS x可被6整除 C= x | xS x可被8整除 画
7、出文氏图,然后填入相应的数字,解得 N=1000(200+100+33+67) =600,14,实例,方法二 |S| = 1000 |A|=1000/5=200, |B|=1000/6=166, |C|=1000/8=125 |AB| = 1000/lcm(5,6) = 1000/33 = 33 |AC| = 1000/lcm(5,8) = 1000/40 = 25 |BC| = 1000/lcm(6,8) = 1000/24 = 41 |ABC| = 1000/lcm(5,6,8) = 1000/120 = 8 = 1000(200+166+125)+(33+25+41)8 = 600,15
8、,6.3 集合恒等式,集合算律 1只涉及一个运算的算律: 交换律、结合律、幂等律,16,集合算律,2涉及两个不同运算的算律: 分配律、吸收律,17,集合算律,3涉及补运算的算律: DM律,双重否定律,18,集合算律,4涉及全集和空集的算律: 补元律、零律、同一律、否定律,19,集合证明题,证明方法:命题演算法、等式置换法 命题演算证明法的书写规范 (以下的X和Y代表集合公式) (1) 证XY 任取x, xX xY (2) 证X=Y 方法一 分别证明 XY 和 YX 方法二 任取x,xX xY 注意:在使用方法二的格式时,必须保证每步推理都是充 分必要的,20,集合等式的证明,方法一:命题演算法
9、 例3 证明A(AB) = A (吸收律) 证 任取x, xA(AB) xAxAB xA(xAxB) xA 因此得 A(AB) = A.,例4 证明 AB = AB 证 任取x, x AB xAxB xAxB xAB 因此得 AB = AB,21,等式代入法,方法二:等式置换法 例5 假设交换律、分配律、同一律、零律已经成立,证明吸 收律. 证 A(AB) = (AE)(AB) (同一律) = A(EB) (分配律) = A(BE) (交换律) = AE (零律) = A (同一律),22,包含等价条件的证明,例6 证明AB AB=B AB=A AB= 证明思路: 确定问题中含有的命题:本题含
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 高等教育出版社 配套 屈婉玲耿
链接地址:https://www.31doc.com/p-2599833.html