离散数学 第3章

1、集合论简介 现代数学中，每个对象(如数，函数等)本质上都是集合，都可以用某种集合来定义，数学的各个分支，本质上都是在研究某一种对象集合的性质。集合论的特点是研究对象的广泛性，它也是计算机科学与工程的基础理论和表达工具，而且在程序设计，数据结构，形式语言，关系数据库，操作系统等都有重要应用。本课程在第三，四章中介绍集合论的内容。,G Cantor集合论是研究集合一般性质的数学分支，它的创始人是康托尔(，18451918)。在第三章第三章 集合的基本概念和运算集合的基本概念和运算 第一节第一节 集合的基本概念集合的基本概念 内容：内容： 集合，元素，子集，幂集等。 重点：重点： (1) 掌握集合的

2、概念及两种表示法， (3) 掌握子集及两集合相等的概念， (4) 掌握幂集的概念及求法。 (2) 常见的集合 , ,N Z Q R C和特殊集合,E，一、集合的概念。一、集合的概念。 1、集合集合一些确定的对象的整体。 集合用大写的字母标记 其中的对象称元素，用小写字母标记 12 ,nAa aa表示集合A12,na aa含有元素注意：注意： (1) 或 aAaA(2) 集合中的元素均不相同 , , , , , , , , , a b ca b b cc a b表示同一个集合。 (3) 集合的元素可以是任何类型的事物， 一个集合也可以作为另一个集合的元素。 例如： , , , , Aa b cb

3、 b2、集合的表示法。 (1) 列举法(将元素一一列出) 例如： 2,3,4,5A (2) 描述法(用谓词概括元素的属性) 例如： |25Bx xZx一般，用描述法表示集合 |( )Ax P x3、常见的一些集合。 , ,N Z Q R C4、集合间的关系。 ()BAx xBxA ()BAx xBxA (1)BABA的子集，记为BABABABABABA为BABA的真子集，记 4、集合间的关系。 5、特殊的集合。 空集空集 ABABBA(2) 对任意集合AAA有(3) 两集合,A BAB相等，记作全集全集EU)(或AE( A为任一集合)例例1、选择适当的谓词表示下列集合。 (1) 小于5的非负整

4、数集 解：解： |5x xNx(2) 奇整数集合 |21x xnnZ 解：解： 例例1、选择适当的谓词表示下列集合。 (3) 10的整倍数集合， 解：解： 解：解： (4)3,5,7,11,13,17,19 |10 x xnnZ |220 x xx是素数例例2、用列举法表示下列集合。 解：解： 解：解： (1)1 |25Sx xx12,5S (2)2 |Sx x是十进制的数字20,1,2,9S 例例2、用列举法表示下列集合。 解：解： 解：解： (3)3 |510Sx xZx36,7,8,9,10S (4)4,|0(12)Sx yxyy 40,1 , 0,2S 例例3、确定下面命题的真值： (

5、1) 真值 T真值 F(2) (3) 真值 T(4) 真值 T例例3、确定下面命题的真值： 真值 T真值 F真值 T真值 F(5) , , , , ,a ba b ca b c(6) , , , , ,a ba b ca b c(7) , , ,a ba ba b(8) , , ,a ba ba b例例4、, ,A B CABBC有可能ACAC，且为集合，若吗？吗，有可能解：解：两种情形都有可能。 设 , , , AaBaCaa，则,AB BCAC。，有又设 , , AaBaCa，则,AB BCAC。，但二、幂集。二、幂集。 1、nnm()mn子集。 元个元素的集合)的元集(例如： , , A

6、a b c为3元集。0元子集：(只有一个)，1元子集： , , abc133C 个)，(共2元子集： , , , , , a ba cb c233C 个)，(共3元子集： , , a b c331C 个)。(共一般，n012nnnnnCCC个。元集共有子集解：解： ( ) , , , , , ,P Aabca b , , , , , , a cb ca b c2、集合A的幂集，()P AA记的全体子集为元素的集合。例例5、 , , Aa b c( )P A。，求若An( )P A2n个元素。有个元素，则有例例6、求以下集合的幂集。 (1) A解：解： ( ) P A(2) A解：解： ( )

7、, P AA(3) , A 解：解： ( ), , ,P AA 例例6、求以下集合的幂集。 解：解： 解：解： (4) 1,2,3A ( ),1, 2,3 ,P AA(5) ,2,2A ( ), ,2 , 2 ,P AA第二节第二节 集合的基本运算集合的基本运算 内容：内容： 集合的运算，文氏图，运算律。 重点：重点： (1) 掌握集合的运算 ,AB AB ABA AB(2) 用文氏图表示集合间的相互关系和运算， (3) 掌握基本运算律的内容及运用。 一、集合的运算。一、集合的运算。 |ABx xAxB |ABx xAxBAB，相对补集集合,A BAB，的并集交集AB，对称差AB。绝对补集 A

8、， (当,A BAB不交)时，称以上定义加以推广， 121niniAAAA12 |nx xAxAxA121niniAAAA12 |nx xAxAxA |ABx xAxB()()()()ABABBAABAB |AEAx xExA(其中E为全集)， (1) AB1(2) BC1,5(3) A2,3,5(4) BA1,2,3,51,2,5B 2,4C ，求出以下集合。 ，例例1、设1,2,3,4,5E 1,4A ，(5) AB2,4,5(6) ()AB3(7) ()ABC1,3,5(8) ()()ABAC1,41,2,5B 2,4C ，求出以下集合。 ，例例1、设1,2,3,4,5E 1,4A ，1

9、、文氏图。 (2) 矩形内的圆表示集合， (1) 用大矩形表示全集E，二、文氏图二、文氏图()JohnVenn。1、文氏图。 (3) 除特殊情形外，一般，表示两个集合 的圆是相交的，(4) 圆中的阴影的区域表示新组成的集合。 二、文氏图二、文氏图()JohnVenn。2、用文氏图表示集合的有关运算。 例例2、用文氏图表示下列集合。 (1) AB2、用文氏图表示集合的有关运算。 例例2、用文氏图表示下列集合。 (2) AB2、用文氏图表示集合的有关运算。 例例2、用文氏图表示下列集合。 (3) ()ABC2、用文氏图表示集合的有关运算。 例例2、用文氏图表示下列集合。 (4) ()ABC例例3、

10、用集合公式表示下列文氏图中的阴影部分。 (1) 解：解： ABC例例3、用集合公式表示下列文氏图中的阴影部分。 (2) 解：解： ()()()ABACBC三、集合运算律。三、集合运算律。 1、幂等律：幂等律： AAA，AAA2、结合律：结合律： ()()ABCABC,()()ABCABC3、交换律：交换律： ABBA,ABBA4、分配律：分配律： ()()()ABCABAC()()()ABCABAC,三、集合运算律。三、集合运算律。 5、同一律：同一律： AA,AEA6、零律：零律： AEE,A7、互否律：互否律： AAE(排中律)， AA(矛盾律) 8、吸收律：吸收律： ，()AABA()A

11、ABA三、集合运算律。三、集合运算律。 9、德德 摩根律：摩根律： ()()()ABCABAC ()BCBC()()()ABCABAC ()BCBC E三、集合运算律。三、集合运算律。 9、德德 摩根律：摩根律： 10、双重否定律：双重否定律： ()AA以上恒等式的证明思路： E欲证PQxxPxQ。，即证对任意()()xAxBC()xAxBxC()()xAxBxAxC()()xABxAC()()xABAC故 ()()()ABCABAC例例4、证明分配律()()()ABCABAC 。x证明：证明： 对任意()xABC，除基本运算外，还有以下一些常用性质 (证明略) 13、 ABA14、 ABAB

12、15、 ABBABABAAB12、AABBAB11、ABAABB，除基本运算外，还有以下一些常用性质 (证明略) 16、 ABBA17、()()ABCABC18、 AA19、 AA20、 ABACBC“ ”的交换律“ ”的结合律xAxBxABxAxBxAB故 ABAB例例5、证明：ABAB(第14条)证明：证明： 对任意x，证明：证明： ()()ABAABA()()ABAA()ABEAB例例6、证明()ABAAB。例例7、化简 ()()ABCAB()ABCA所以原式化简为 ()ABA解：解：因为ABABC，所以()()ABCABAB，()AABC又因为所以()ABCAA，例例7、化简 ()()

13、ABCAB()ABCA解：解：又 ()ABA()ABA()()AABA()BABA最后，原式化简为BA。例例8、设为假的各有哪些？, ,A B CE（1）ABABB（2）ABABA（3）ABA BA的子集，以下命题中为真，均为解：解：为真的命题有(1)、(3)、(5)，为假的命题有(2)、(4)、(6)。 例例8、设为假的各有哪些？, ,A B CE（4） ABABB（5）()ABABAB（6）()BAA BBA的子集，以下命题中为真，均为第三章第三章 小结与例题小结与例题 一、集合的基本概念。一、集合的基本概念。 1、基本概念。 元素和集合的属于关系；有限集和无限集；子集和真子集；集合的相等

14、；空集和全集；幂集。2、应用。 (1) 用集合的两种表示法表示集合。 (2) 求给定集合的幂集。 二、集合的基本运算。二、集合的基本运算。 1、基本概念。 交集，并集，差集，补集，对称差集；文氏图；基本运算律。 2、应用。 (1) 用文氏图表示集合间的相互关系和运算。 (2) 运用基本运算律进行证明，化简等。 表示计算机科学系学生的集合， R表示二年级大学生的集合， S表示数学系学生的集合， M表示选修离散数学的学生的集合， T表示爱好文学的学生的集合， L表示爱好体育运动的学生的集合， P用集合交集，并集和包含关系表示： (1) 所有计算机科学系二年级的学生都选修离散数学， 解：解： RST

15、例例1、设F表示一年级大学生的集合， (2) 数学系的学生或者爱好文学或者爱好体育运动， 解：解： MLP表示计算机科学系学生的集合， R表示二年级大学生的集合， S表示数学系学生的集合， M表示选修离散数学的学生的集合， T表示爱好文学的学生的集合， L表示爱好体育运动的学生的集合， P用集合交集，并集和包含关系表示： 例例1、设F表示一年级大学生的集合， (3) 数学系一年级的学生都没有选修离散数学， 解：解： ()MFT表示计算机科学系学生的集合， R表示二年级大学生的集合， S表示数学系学生的集合， M表示选修离散数学的学生的集合， T表示爱好文学的学生的集合， L表示爱好体育运动的学

16、生的集合， P用集合交集，并集和包含关系表示： 例例1、设F表示一年级大学生的集合， (4) 只有一、二年级的学生才爱好体育运动， 解：解： pFS表示计算机科学系学生的集合， R表示二年级大学生的集合， S表示数学系学生的集合， M表示选修离散数学的学生的集合， T表示爱好文学的学生的集合， L表示爱好体育运动的学生的集合， P用集合交集，并集和包含关系表示： 例例1、设F表示一年级大学生的集合， (5) 除去数学系和计算机科学系二年级的学生外都不选修离散数学。 解：解： ()TMRS表示计算机科学系学生的集合， R表示二年级大学生的集合， S表示数学系学生的集合， M表示选修离散数学的学生

17、的集合， T表示爱好文学的学生的集合， L表示爱好体育运动的学生的集合， P用集合交集，并集和包含关系表示： 例例1、设F表示一年级大学生的集合， (1) 5XS解：解： 2XS解：解： 5XS例例2、设11,2,8,9S 22,4,6,8S 31,3,5,7,9S 43,4,5S 53,5S ，确定在以下条件下X15,SS集合相等？ 中哪个可能与，(2)4XS2XS，但解：解： 12,XS S或4S(4) 若3XS解：解： 3XS或5S例例2、设11,2,8,9S 22,4,6,8S 31,3,5,7,9S 43,4,5S 53,5S ，确定在以下条件下X15,SS集合相等？ 中哪个可能与，

18、(3)1XS3XS且解：解： X与其中任何集合都不相等 例例2、设11,2,8,9S 22,4,6,8S 31,3,5,7,9S 43,4,5S 53,5S ，确定在以下条件下X15,SS集合相等？ 中哪个可能与，(5) 若3XS1XS且例例3、简要说明： 举出它们的元素和子集。 的区别，与子集有解：解：是无任何元素的集合，是以集合为元素的集合， 元素为 ,。，子集有例例4、设 3,4A ，4,3B1,2C，27120Dx xx,3,4E4,4,3F 4, ,3,3G，问上述集合中有哪些是相等的。 解：解： ADFBCEG(1) ABBCAC解：解：结论不一定成立。 例例5、设, ,A B C

19、是集合，证明或反驳下列断言。 若 Aa Ba Ca则有ABBCAC，但若 Aa Ba Cc则有ABBCAC，。(2) ABBCAC解：解：结论不一定成立。 例例5、设, ,A B C是集合，证明或反驳下列断言。 若 Aa Ca则有ABBCAC Bb ，但若 Aa则有ABBCAC Bb Cc，。aAABaB(3) 解：解：结论成立。 由ABxA xB因aAaB。有知： 故。例例5、设, ,A B C是集合，证明或反驳下列断言。(1) ( )( )ABP AP B( )xP A ，有 xA证明：证明：设 AB例例6、设,A B为任意集合，证明： 又ABxB( )xP B，即有，故所以( )( )P

20、 AP B。( )( )P AP BAB例例6、设 为任意集合，证明： ,A B(2) 证明：证明：设 ( )( )P AP BxA ，有 ( )xP A又( )( )P AP B ( )xP B，故即xB，所以AB。例例7、求下列集合的基数和每个集合的幂集。 (1) 1, 2,3解：解：基数2， 幂集为： , 1 ,2,3, 1, 2,3(2) , , a b解：解：基数3， 幂集为： ,aba , ,ba ba b8 ;Bx x(1) 2，4，6，8 解：BC例8、设, ,A B C D EZ12 ;Ax x(2 )() ;Cx xkkZ (3 )();Dx xkkZ (21)();Ex xkkZ试用, ,A B C D E其中：表示下述集合。(2) 3，6，9 解：AD例8、设, ,A B C D EZ12 ;Ax x(2 )() ;Cx xkkZ (3 )();Dx xkkZ (21)();Ex xkkZ试用, ,A B C D E其中：表示下述集合。(3) 10 解：()ABE例8、设, ,A B C D EZ12 ;Ax