北大离散数学chap3

集合论简介北京大学现代数学中，每个对象(如数，函数等)本质上都是集合，都可以用某种集合来定义，数学的各个分支，本质上都是在研究某一种对象集合的性质。集合论的特点是研究对象的广泛性，它也是计算机科学与工程的基础理论和表达工具，而且在程序设计，数据结构，形式语言，关系数据库，操作系统等都有重要应用。本课程在第三，四章中介绍集合论的内容。,GCantor集合论是研究集合一般性质的数学分支，它的创始人是康托尔(，1845－1918)。在第三章集合的基本概念和运算第一节集合的基本概念内容：集合，元素，子集，幂集等。重点：(1)掌握集合的概念及两种表示法，(3)掌握子集及两集合相等的概念，(4)掌握幂集的概念及求法。(2)常见的集合,,,,NZQRC和特殊集合,E，一、集合的概念。1、集合——一些确定的对象的整体。集合用大写的字母标记其中的对象称元素，用小写字母标记12{,,}nAaaa表示集合A12,,naaa含有元素注意：(1)或aAaA(2)集合中的元素均不相同{,,},{,,,},{,,}abcabbccab表示同一个集合。(3)集合的元素可以是任何类型的事物，一个集合也可以作为另一个集合的元素。例如：,{,},,{}Aabcbb2、集合的表示法。(1)列举法(将元素一一列出)例如：{2,3,4,5}A(2)描述法(用谓词概括元素的属性)例如：{|25}BxxZx一般，用描述法表示集合|()AxPx3、常见的一些集合。,,,,NZQRC4、集合间的关系。()BAxxBxA()BAxxBxA(1)BABA的子集，记为BABABABABABA为BABA的真子集，记4、集合间的关系。5、特殊的集合。空集ABABBA(2)对任意集合AAA有(3)两集合,ABAB相等，记作全集EU)(或AE(A为任一集合)例1、选择适当的谓词表示下列集合。(1)小于5的非负整数集解：{|5}xxNx(2)奇整数集合{|21}xxnnZ解：例1、选择适当的谓词表示下列集合。(3)10的整倍数集合，解：解：(4){3,5,7,11,13,17,19}{|10}xxnnZ{|220}xxx是素数例2、用列举法表示下列集合。解：解：(1)1{|25}Sxxx1{2,5}S(2)2{|}Sxx是十进制的数字2{0,1,2,9}S例2、用列举法表示下列集合。解：解：(3)3{|510}SxxZx3{6,7,8,9,10}S(4)4,|0(12)Sxyxyy40,1,0,2S例3、确定下面命题的真值：(1)真值T真值F(2)(3){}真值T(4){}真值T例3、确定下面命题的真值：真值T真值F真值T真值F(5){,},,,,,ababcabc(6){,},,,,,ababcabc(7){,},,,ababab(8){,},,,ababab例4、,,ABCABBC有可能ACAC，且为集合，若吗？吗，有可能解：两种情形都有可能。设{},{},{},{}AaBaCaa，则,ABBCAC。，有又设{},{},{}AaBaCa，则,ABBCAC。，但二、幂集。1、nnm()mn子集。元个元素的集合)的元集(例如：{,,}Aabc为3元集。0元子集：(只有一个)，1元子集：{},{},{}abc133C个)，(共2元子集：{,},{,},{,}abacbc233C个)，(共3元子集：{,,}abc331C个)。(共一般，n012nnnnnCCC个。元集共有子集解：(){,{},{},{},{,},PAabcab{,},{,},{,,}}acbcabc2、集合A的幂集，()PAA记的全体子集为元素的集合。——例5、{,,}Aabc()PA。，求若An()PA2n个元素。有个元素，则有例6、求以下集合的幂集。(1)A解：(){}PA(2){}A解：(){,}PAA(3),{}A解：(),{},{},PAA例6、求以下集合的幂集。解：解：(4)1,{2,3}A(),{1},{2,3},PAA(5){,2},{2}A(),{,2},{2},PAA第二节集合的基本运算内容：集合的运算，文氏图，运算律。重点：(1)掌握集合的运算,,,~,ABABABAAB(2)用文氏图表示集合间的相互关系和运算，(3)掌握基本运算律的内容及运用。一、集合的运算。{|}ABxxAxB{|}ABxxAxBAB，相对补集集合,ABAB，的并集交集AB，对称差AB。绝对补集~A，(当,ABAB不交)时，称以上定义加以推广，121niniAAAA12{|}nxxAxAxA121niniAAAA12{|}nxxAxAxA{|}ABxxAxB()()()()ABABBAABAB~{|}AEAxxExA(其中E为全集)，(1)AB{1}(2)BC{1,5}(3)~A{2,3,5}(4)~BA{1,2,3,5}{1,2,5}B{2,4}C，求出以下集合。，例1、设{1,2,3,4,5}E{1,4}A，，(5)AB{2,4,5}(6)~()AB{3}(7)()~ABC{1,3,5}(8)()()ABAC{1,4}{1,2,5}B{2,4}C，求出以下集合。，例1、设{1,2,3,4,5}E{1,4}A，，1、文氏图。(2)矩形内的圆表示集合，(1)用大矩形表示全集E，二、文氏图()JohnVenn。1、文氏图。(3)除特殊情形外，一般，表示两个集合的圆是相交的，(4)圆中的阴影的区域表示新组成的集合。二、文氏图()JohnVenn。2、用文氏图表示集合的有关运算。例2、用文氏图表示下列集合。(1)AB2、用文氏图表示集合的有关运算。例2、用文氏图表示下列集合。(2)~AB2、用文氏图表示集合的有关运算。例2、用文氏图表示下列集合。(3)()ABC2、用文氏图表示集合的有关运算。例2、用文氏图表示下列集合。(4)(~)ABC例3、用集合公式表示下列文氏图中的阴影部分。(1)解：ABC例3、用集合公式表示下列文氏图中的阴影部分。(2)解：()()()ABACBC三、集合运算律。1、幂等律：AAA，AAA2、结合律：()()ABCABC,()()ABCABC3、交换律：ABBA,ABBA4、分配律：()()()ABCABAC()()()ABCABAC,三、集合运算律。5、同一律：AA,AEA6、零律：AEE,A7、互否律：~AAE(排中律)，~AA(矛盾律)8、吸收律：，()AABA()AABA三、集合运算律。9、德摩根律：()()()ABCABAC~()~~BCBC()()()ABCABAC~()~~BCBC~E三、集合运算律。9、德摩根律：10、双重否定律：~(~)AA以上恒等式的证明思路：~E欲证PQxxPxQ。，，即证对任意()()xAxBC()xAxBxC()()xAxBxAxC()()xABxAC()()xABAC故()()()ABCABAC例4、证明分配律()()()ABCABAC。x证明：对任意()xABC，除基本运算外，还有以下一些常用性质(证明略)13、ABA14、~ABAB15、ABBABABAAB12、AABBAB11、ABAABB，，除基本运算外，还有以下一些常用性质(证明略)16、ABBA17、()()ABCABC18、AA19、AA20、ABACBC“”的交换律“”的结合律xAxBxAB~xAxB~xAB故~ABAB例5、证明：~ABAB(第14条)证明：对任意x，证明：()(~)ABAABA()(~)ABAA()ABEAB例6、证明()ABAAB。例7、化简()()ABCAB()ABCA所以原式化简为()ABA解：因为ABABC，所以()()ABCABAB，()AABC又因为所以()ABCAA，例7、化简()()ABCAB()ABCA解：又()ABA()~ABA(~)(~)AABA()BABA最后，原式化简为BA。例8、设为假的各有哪些？,,ABCE（1）ABABB（2）ABABA（3）ABABA的子集，以下命题中为真，均为解：为真的命题有(1)、(3)、(5)，为假的命题有(2)、(4)、(6)。例8、设为假的各有哪些？,,ABCE（4）ABABB（5）()ABABAB（6）()BAABBA的子集，以下命题中为真，均为第三章小结与例题一、集合的基本概念。1、基本概念。元素和集合的属于关系；有限集和无限集；子集和真子集；集合的相等；空集和全集；幂集。2、应用。(1)用集合的两种表示法表示集合。(2)求给定集合的幂集。二、集合的基本运算。1、基本概念。交集，并集，差集，补集，对称差集；文氏图；基本运算律。2、应用。(1)用文氏图表示集合间的相互关系和运算。(2)运用基本运算律进行证明，化简等。表示计算机科学系学生的集合，R表示二年级大学生的集合，S表示数学系学生的集合，M表示选修离散数学的学生的集合，T表示爱好文学的学生的集合，L表示爱好体育运动的学生的集合，P用集合交集，并集和包含关系表示：(1)所有计算机科学系二年级的学生都选修离散数学，解：RST例1、设F表示一年级大学生的集合，(2)数学系的学生或者爱好文学或者爱好体育运动，解：MLP表示计算机科学系学生的集合，R表示二年级大学生的集合，S表示数学系学生的集合，M表示选修离散数学的学生的集合，T表示爱好文学的学生的集合，L表示爱好体育运动的学生的集合，P用集合交集，并集和包含关系表示：例1、设F表示一年级大学生的集合，(3)数学系一年级的学生都没有选修离散数学，解：()MFT表示计算机科学系学生的集合，R表示二年级大学生的集合，S表示数学系学生的集合，M表示选修离散数学的学生的集合，T表示爱好文学的学生的集合，L表示爱好体育运动的学生的集合，P用集合交集，并集和包含关系表示：例1、设F表示一年级大学生的集合，(4)只有一、二年级的学生才爱好体育运动，解：pFS表示计算机科学系学生的集合，R表示二年级大学生的集合，S表示数学系学生的集合，M表示选修离散数学的学生的集合，T表示爱好文学的学生的集合，L表示爱好体育运动的学生的集合，P用集合交集，并集和包含关系表示：例1、设F表示一年级大学生的集合，(5)除去数学系和计算机科学系二年级的学生外都不选修离散数学。解：()TMRS表示计算机科学系学生的集合，R表示二年级大学生的集合，S表示数学系学生的集合，M表示选修离散数学的学生的集合，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)4XS2XS，但解：12,XSS或4S(4)若3XS解：3XS或5S例2、设11,2,,8,9S22,4,6,8S31,3,5,7,9S43,4,5S53,5