离散数学第6章 集合代数ppt课件.ppt

《离散数学第6章 集合代数ppt课件.ppt》由会员分享，可在线阅读，更多相关《离散数学第6章 集合代数ppt课件.ppt（39页珍藏版）》请在三一办公上搜索。

1、1,主要内容集合的基本概念 属于、包含 幂集、空集 文氏图等集合的基本运算 并、交、补、差等集合恒等式 集合运算的算律、恒等式的证明方法,第二部分 集合论,第六章 集合代数,2,6.1 集合的基本概念,1.集合定义 集合没有精确的数学定义 理解：由离散个体构成的整体称为集合，称这些个体为集 合的元素 常见的数集：N,Z,Q,R,C 等分别表示自然数、整数、有 理数、实数、复数集合,2.集合表示法 枚举法-通过列出全体元素来表示集合 谓词表示法-通过谓词概括集合元素的性质 实例：枚举法 自然数集合 N=0,1,2,3,谓词法 S=x|x是实数，x21=0,3,元素与集合,1.集合的元素具有的性质

2、 无序性：元素列出的顺序无关 相异性：集合的每个元素只计 数一次 确定性：对任何元素和集合都 能确定这个元素是否 为该集合的元素 任意性：集合的元素也可以是 集合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 空集：不含有任何元素的集合 实例：x|xR x2+1=0 定理6.1 空集是任何集合的子集。证 对于任意集合A

3、，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.9 绝对补 A=EA,7,文氏图,集合运算的表示,A,B,A,B,A,B,A,B,A,B,AB,AB,AB,AB,A,8,几点说明,并和交运算可以推广到

4、有穷个集合上，即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,关于广义运算的说明,2.广义运算的性质(1)=，无意义(2)单元集x的广义并和广义交都等于x(3)广义运算减少集合的层次（括弧减少一层）(4)广义运算的计算：一般情况下可以转变成初级运算 A1,A2,An=A1A2An A1,A2,An

5、=A1A2An 3.引入广义运算的意义 可以表示无数个集合的并、交运算，例如 x|xR=R 这里的 R 代表实数集合.,11,运算的优先权规定,1 类运算：初级运算,，优先顺序由括号确定2 类运算：广义运算和运算，运算由右向左进行混合运算：2 类运算优先于1 类运算,例1 A=a,a,b，计算A(AA).解：A(AA)=a,b(a,ba)=(ab)(ab)a)=(ab)(ba)=b,12,有穷集合元素的计数,1.文氏图法2.包含排斥原理定理6.2 设集合S上定义了n条性质，其中具有第 i 条性质的元素构成子集Ai,那么集合中不具有任何性质的元素数为,推论 S中至少具有一条性质的元素数为,13,

6、实例,例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整除 画出文氏图，然后填入相应的数字，解得 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/l

7、cm(6,8)=1000/24=41|ABC|=1000/lcm(5,6,8)=1000/120=8=1000(200+166+125)+(33+25+41)8=600,15,6.3 集合恒等式,集合算律1只涉及一个运算的算律：交换律、结合律、幂等律,16,集合算律,2涉及两个不同运算的算律：分配律、吸收律,17,集合算律,3涉及补运算的算律：DM律，双重否定律,18,集合算律,4涉及全集和空集的算律：补元律、零律、同一律、否定律,19,集合证明题,证明方法：命题演算法、等式置换法命题演算证明法的书写规范(以下的X和Y代表集合公式)(1)证XY 任取x，xX xY(2)证X=Y 方法一 分别证

8、明 XY 和 YX 方法二 任取x，xX xY注意：在使用方法二的格式时，必须保证每步推理都是充分必要的,20,集合等式的证明,方法一：命题演算法例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

9、 证明AB AB=B AB=A AB=证明思路：确定问题中含有的命题：本题含有命题,确定命题间的关系（哪些命题是已知条件、哪些命题是要证明的结论）：本题中每个命题都可以作为已知条件，每个命题都是要证明的结论确定证明顺序：，按照顺序依次完成每个证明（证明集合相等或者包含）,23,证明,证明AB AB=B AB=A AB=证 显然BAB，下面证明AB=B.任取x，xAB xAxB xBxB xB 因此有ABB.综合上述得证.A=A(AB)A=AB(由知AB=B，将AB用B代入),24,假设AB,即xAB，那么知道xA且xB.而 xB xAB 从而与AB=A矛盾.假设AB不成立，那么 x(xAxB)

10、xAB AB与条件矛盾.,证明,25,第六章 习题课,主要内容集合的两种表示法集合与元素之间的隶属关系、集合之间的包含关系的区别与联系特殊集合：空集、全集、幂集文氏图及有穷集合的计数集合的,等运算以及广义,运算集合运算的算律及其应用,26,基本要求,熟练掌握集合的两种表示法能够判别元素是否属于给定的集合能够判别两个集合之间是否存在包含、相等、真包含等关系熟练掌握集合的基本运算（普通运算和广义运算）掌握证明集合等式或者包含关系的基本方法,27,练习1,1判断下列命题是否为真(1)(2)(3)(4)(5)a,b a,b,c,a,b,c(6)a,b a,b,c,a,b(7)a,b a,b,a,b(8

11、)a,b a,b,a,b,解(1)、(3)、(4)、(5)、(6)、(7)为真，其余为假.,28,方法分析,(1)判断元素a与集合A的隶属关系是否成立基本方法：把 a 作为整体检查它在A中是否出现，注意这里的 a 可 能是集合表达式.(2)判断AB的四种方法若A,B是用枚举方式定义的，依次检查A的每个元素是否在B中出现.若A,B是谓词法定义的，且A,B中元素性质分别为P和Q,那么“若P则Q”意味 AB，“P当且仅当Q”意味=通过集合运算判断AB，即AB=B,AB=A,AB=三个等式中有一个为真.通过文氏图判断集合的包含（注意这里是判断，而不是证明,29,练习2,2设 S1=1,2,8,9，S2

12、=2,4,6,8 S3=1,3,5,7,9 S4=3,4,5 S5=3,5 确定在以下条件下X是否与S1,S5中某个集合相等？如果是，又与哪个集合相等？（1）若 XS5=（2）若 XS4但 XS2=（3）若 XS1且 X S3（4）若 XS3=（5）若 XS3 且 X S1,30,解答,解(1)和S5不交的子集不含有3和5，因此 X=S2.(2)S4的子集只能是S4和S5.由于与S2不交，不能含有偶数，因此 X=S5.(3)S1,S2,S3,S4和S5都是S1的子集，不包含在S3的子集含有 偶数，因此 X=S1,S2或S4.(4)XS3=意味着 X是S3的子集，因此 X=S3或 S5.(5)由

13、于S3是S1的子集，因此这样的X不存在.,31,练习3,3.判断以下命题的真假，并说明理由.（1）AB=A B=（2）A(BC)=(AB)(AC)（3）AA=A（4）如果AB=B，则A=E.（5）A=xx，则 xA且x A.,32,解题思路,先将等式化简或恒等变形.查找集合运算的相关的算律，如果与算律相符，结果为真.注意以下两个重要的充要条件 AB=A AB=AB=AB AB=B AB=A 如果与条件相符，则命题为真.如果不符合算律，也不符合上述条件，可以用文氏图表示集合，看看命题是否成立.如果成立，再给出证明.试着举出反例，证明命题为假.,33,解答,解(1)B=是AB=A的充分条件，但不是

14、必要条件.当B不空但 是与A不交时也有AB=A.(2)这是DM律，命题为真.(3)不符合算律，反例如下：A=1，AA=，但是A.(4)命题不为真.AB=B的充分必要条件是 BA，不是A=E.(5)命题为真，因为 x 既是 A 的元素，也是 A 的子集,34,练习4,4证明 AB=AC AB=AC B=C,解题思路分析命题：含有3个命题：AB=AC,AB=AC,B=C 证明要求 前提：命题和 结论：命题 证明方法：恒等式代入 反证法 利用已知等式通过运算得到新的等式,35,解答,方法一：恒等变形法 B=B(BA)=B(AB)=B(AC)=(BA)(BC)=(AC)(BC)=(AB)C=(AC)C

15、=C,方法二：反证法.假设 B C，则存在 x(xB且xC),或存在 x(xC且xB).不妨设为前者.若x属于A，则x属于AB 但x不属于AC，与已知矛盾；若x不属于A，则x属于AB但x不属于AC，也与已知矛盾.,36,解答,方法三：利用已知等式通过运算得到新的等式.由已知等式和可以得到(AB)(AB)=(AC)(AC)即 AB=AC 从而有 A(AB)=A(AC)根据结合律得(AA)B=(AA)C 由于AA=,化简上式得B=C.,37,练习5,5设A,B为集合，试确定下列各式成立的充分必要条件：(1)AB=B(2)AB=BA(3)AB=AB(4)AB=A,38,分析,解题思路:求解集合等式成立的充分必要条件可能用到集合的算律、不同集合之间的包含关系、以及文氏图等.具体求解过程说明如下：(1)化简给定的集合等式(2)求解方法如下：利用已知的算律或者充分必要条件进行判断先求必要条件，然后验证充分性利用文氏图的直观性找出相关的条件，再利用集合论的证明方法加以验证,39,