《离散数学第13讲》由会员分享，可在线阅读，更多相关《离散数学第13讲（27页珍藏版）》请在金锄头文库上搜索。
1、第二部分 集合论对于从事计算机科学工作的人们来说，集合论是必不可少的基础知识。例如有限状态机、形 式语言等都离不开子集、幂集、集合的分类等概 念。集合成员表和范式在逻辑设计、定理证明中 也都有重要应用。本部分从集合的直观概念出发，介绍了集合论中的一些基本概念和基本理论，其中包括集合 、关系、函数等。离散数学 第13讲 本讲基本知识点： 1、集合的基本概念 2、集合的运算 3、集合基本恒等式2第六章 集合代数6.1 集合的基本概念直观定义： 一些事物汇集到一起组成的一个整体称为集合，而这些事物就是这个集合的元素或成员。 集合通常用大写字母来标记，如N、Z、Q、R、C。集合表示方法：列元素法 A=
2、1,2,3,4,5谓词表示法 B=x | xN 1x5 3第六章 集合代数集合的特征互异性 1,2,3,2,4= 1,2,3,4无序性 4,2,1,3 = 1,2,3,4元素和集合之间的关系属于（）或 不属于（ ）如：对于A= 1,2,3,4，1 A, 2,3 A, 3 A.可以用树形图表示这种关系。考虑：4, 4, 4 呢 ?4第六章 集合代数如：A1 2,3 42 3 44本书规定：对于任何集合A，都有A A。5第六章 集合代数定义6.1设A，B为集合，如果B中的每个元素都是A中的元素，则称B是A的子集合，简称子集。也称B被A包含，或B包含于A，或A包含B，记作B A。如果B不被A包含，则
3、记作B A。包含的符号化表示为： B A x(xB xA)例如：N Z Q R C, 而C R.显然：对于任何集合A，都有A A。6第六章 集合代数定义6.2设A，B为集合，如果A B且B A，则称A与B相等，记作A=B。如果A与B不相等，则记作 AB。相等的符号化表示为： A=B A B B A7第六章 集合代数定义6.3设A，B为集合，如果B A且BA，则称B是A的真子集,也称B被A真包含，或B真包含于A，或A真包含B，记作BA。如果B不被A真包含，则记作 A B。真子集的符号化表示为：BA A B B A例如：N Z Q R C, 而C C.显然：对于任何集合A，都有A A。8第六章 集
4、合代数定义6.4 不含任何元素的集合叫做空集，记作 。 空集的符号化表示为： x|xx 如：C=x|x Z+ x xA2 和 xA2= x A1 (2) 利用已知的恒等式代入。总体上还是采用命题逻辑中的等值式，在叙述上 采用半形式化的方法，其中表示当且仅当， 意即“等价”。18第六章 集合代数例6.6 证明A-(BC)=(A-B)(A-C). 证明： 对于xx A-(BC) x A x (BC) x A (xB xC) x A (xB xC) x A (x B x C) x A x B x C (x A x B) (x A x C) x A- B x A- C x ( A- B) (A- C)
5、 A-(BC)=(A-B)(A-C)19第六章 集合代数 例6.8 利用代入已知恒等式证明 A(AB)=A. 证明: A(AB)= (AE)(AB) = A(E B)= AE= A A(AB)=AP101列出了关于集合运算性质的一些重要结 果，请注意掌握。20第六章 集合代数集合论中证明题的解题思路： 1、证明类似 “A B”结论的思路 在A中任意取一元素x，证明x在B中存在。 2、证明“A=B”的思路： 方法1：证明“A B”并且“BA” 方法2：等值值演算21第六章 集合代数典型例题：证明AB P(A)P(B) 证证明：(1)必要性(“x A =x P(A) x P(B) =x P(B)
6、x B xB (2)充分性(“=”) 任意xP(A)=X A= X B = xP(B)22集合代数小结 一、基本知识点：1、基本概念：集合，元素，集合的元数； 集合的表示方法：列举法和描述法； 特殊集合：全集合E，空集合， 集合的关系：包含，子集，集合相等，幂集 2、集合的运算性质 集合的运算有并、交、补、差、对称差。由这些运算 ，派生出11条运算律(即运算的性质)，即交换律、 结合律、分配律、幂等律、同一律、零律、互补律 、吸收律、摩根律和双补律等。23集合代数小结 二、考查要点： 1、概念：在集合概念部分要特别注意：元素与子集 ，子集与幂集，与()，空集与所有集 合等的关系。 2、幂幂集的
7、性质质： （1）若A为为有穷穷集，|A|=n，则则|2A | = Cn0 + Cn1 + + Cnn =2n（2）x(A) xA（3）AB (A)(B)24集合代数小结 3、 进行集合的运算；集合运算式的化简；集合恒等 式的推理证明。 4、集合恒等式的证明方法通常有二： 其一，要证明AB，先证明AB，再证明AB。即证 x A = xB 和 xB= x A其二，通过运算律进行等式推导。25集合代数小结 三、典型例题： 指出下列命题的真值。 1、如果A B，B C，则A C。（） 2、如果A B，B C，则A C。（） 3、设A，B为集合，若B ，则A-B A。( ) 4、 2A2B=2AB 。（） 5、 A B= A C ，则B=C。（） 6、 A B= A C ，则B=C。（）26集合代数小结 解：（1）假，如取A=a,B=a,b,C=a,b,c(2) 假，如取A=a,B=a,b,C=a,b,c3）假，例如当B=A 时， A-B = A （4）真，因为x 2A2B x A x Bx A B x 2AB （5）假，如当ABC时，亦有A B= A C 。 （6）真，等式两边同时左加A：A A B= A A C B= C B=C27
