《离散数学集合概念表示法.ppt》由会员分享，可在线阅读，更多相关《离散数学集合概念表示法.ppt（56页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、离散数学集合概念表示法现在学习的是第1页，共56页集合论十九世纪下半叶，康托尔创立了著名的集合论，在集合论刚产生时，曾遭到许多人的猛烈攻击。但不久这一开创性成果就为广大数学家所接受了，并且获得广泛而高度的赞誉。数学家们发现，从自然数与康托尔集合论出发可建立起整个数学大厦。因而集合论成为现代数学的基石。现在学习的是第2页，共56页集合论“一切数学成果可建立在集合论基础上”这一发现使数学家们为之陶醉。1900年，国际数学家大会上，法国著名数学家庞加莱就曾兴高采烈地宣称：“借助集合论概念，我们可以建造整个数学大厦今天，我们可以说绝对的严格性已经达到了”可是，好景不长。1903年，一个震惊数学界的消息
2、传出：集合论是有漏洞的！这就是英国数学家罗素提出的著名的罗素悖论。现在学习的是第3页，共56页理发师悖论（罗素悖论）理发师悖论（罗素悖论）20世纪英国著名哲学家、数学家罗素提出一个著名的悖论“理发师难题”，其内容如下：西班牙的塞维利亚有一个理发师，这位理发师有一条极为特殊的规定：他只给那些“不给自己刮胡子”的人刮胡子。现在学习的是第4页，共56页罗素悖论罗素悖论罗素构造了一个集合S：S由一切不是自身元素的集合所组成。罗素问：S是否属于S呢？如果S属于S，根据S的定义，S就不属于S；反之，如果S不属于S，同样根据定义，S就属于S。无论如何都是矛盾的。G.弗雷格在收到罗素介绍这一悖论的信后伤心地说
3、：“一个科学家所遇到的最不合心意的事莫过于是在他的工作即将结束时，其基础崩溃了。罗素先生的一封信正好把我置于这个境地。”可以说，这一悖论就象在平静的数学水面上投下了一块巨石，而它所引起的巨大反响则导致了第三次数学危机。现在学习的是第5页，共56页危机产生后，数学家纷纷提出自己的解决方案：人们希望能够通过对康托尔的集合论进行改造，通过对集合定义加以限制来排除悖论，这就需要建立新的原则。“这些原则必须足够狭窄，以保证排除一切矛盾；另一方面又必须充分广阔，使康托尔集合论中一切有价值的内容得以保存下来。”1908年，策梅罗在这一原则基础上提出第一个公理化集合论体系，后来经其他数学家改进，称为ZF系统。
4、这一公理化集合系统很大程度上弥补了康托尔朴素集合论的缺陷。公理化集合系统的建立，成功排除了集合论中出现的悖论，从而比较圆满地解决了第三次数学危机。现在学习的是第6页，共56页集合论第3章 集合和关系第4章 函数现在学习的是第7页，共56页第三章第三章 集合与关系集合与关系 本章主要讲授集合论的基本知识，包括集合运算、本章主要讲授集合论的基本知识，包括集合运算、包含排斥原理、笛卡尔积、关系及其性质、关系的包含排斥原理、笛卡尔积、关系及其性质、关系的运算、特殊关系运算、特殊关系(包括等价关系、相容关系、序关系包括等价关系、相容关系、序关系)等。等。重点是集合的运算、关系及其表示、关系的性重点是集合
5、的运算、关系及其表示、关系的性质、关系的闭包、等价关系、偏序关系。质、关系的闭包、等价关系、偏序关系。难点是关系的性质、等价关系、偏序关系的证明。难点是关系的性质、等价关系、偏序关系的证明。现在学习的是第8页，共56页3-1 3-1 集合的概念和表示法集合的概念和表示法现在学习的是第9页，共56页 组成集合的对象称为集合的组成集合的对象称为集合的成员成员成员成员（member）或或元素元素元素元素（element）。）。集合集合是一些确定的、作为是一些确定的、作为整体识别整体识别的、的、互相区别互相区别的的对象对象的总体的总体。一、集合的基本概念一、集合的基本概念 一般用大写字母表示集合，用小
6、写字母表示一般用大写字母表示集合，用小写字母表示元素。元素。元素。元素。例如例如例如例如A A A A表示一个集合，表示一个集合，表示一个集合，表示一个集合，a a a a表示元素，如果表示元素，如果表示元素，如果表示元素，如果a a a a是是是是A A A A的元素，记为：的元素，记为：a a a a A A，读作，读作“a a a a属于属于A”A”、“a a a a是是A A的元素的元素”、“a a a a是是A A的成员的成员”、“a a在在A A之中之中”、“A A 包含包含a a a a”。如果如果a a a a不不不不是是A A的元素，的元素，记为：记为：记为：记为：a a a
7、 a A A ，读作读作“a a a a不不不不属于属于A”A”。现在学习的是第10页，共56页空集和只含有有限多个元素的集合称为空集和只含有有限多个元素的集合称为有限集有限集有限集有限集（finite sets），否则称为），否则称为无限集无限集无限集无限集（infinite sets）。）。有限集合中元素的个数称为集合的有限集合中元素的个数称为集合的基数基数基数基数（cardinality）。）。集合集合A的基数表示为的基数表示为 A。集合的分类集合的分类现在学习的是第11页，共56页二、集合的三种表示方式二、集合的三种表示方式：（l l）列举法列举法 将集合的元素列举出来。将集合的元素列
8、举出来。（2）描述法）描述法 利用一项规则（一个谓词公式），描述集合中的利用一项规则（一个谓词公式），描述集合中的元素的共同性质，以便决定某一物体是否属于该集元素的共同性质，以便决定某一物体是否属于该集合。合。（3）归纳法）归纳法用递归方法定义集合。用递归方法定义集合。现在学习的是第12页，共56页1、列举法：将集合的元素列举出来、列举法：将集合的元素列举出来例：例：A=a，b，c，d，A1=1，3，5，7，9，使用列举法，须列出足够多的元素以反映集合中成使用列举法，须列出足够多的元素以反映集合中成员的特征。如：员的特征。如：B=2，4，8，若若x=2n，则，则 B=2，4，8，16，32，若
9、若x=2+n(n-1)，则，则 B=2，4，8，14，22，2、描述法：、描述法：A=x|P(x)或或A=x：P(x)例：例：C=x|1 x 5，xR，D=(x，y)|x2+y2 1，x，yR F=x|x是中国的一个省是中国的一个省现在学习的是第13页，共56页说明：说明：1、描述法中、描述法中C=x|1 x 5，xR与与C=y|1 y 5，xR表示同一个集合。表示同一个集合。2、集合中元素是无序的。、集合中元素是无序的。a，b，c，b，c，a，c，a，b表示同一个集合。表示同一个集合。3、集合中的元素可能也是集合，例：、集合中的元素可能也是集合，例：A=1，2，1，1，2，3，1A，1A。现
10、在学习的是第14页，共56页三、集合的关系三、集合的关系1.相等关系相等关系相等相等(外延性公理外延性公理)：两个集合是相等的，当且仅当它：两个集合是相等的，当且仅当它们有相同的成员。们有相同的成员。两个集合两个集合A和和B相等，记作相等，记作A=B，两个集合不相等，两个集合不相等，记作记作A B。0，1=x|x(x2-2x+1)=0，x I0，1 1，2现在学习的是第15页，共56页2.2.包含关系（子集）包含关系（子集）包含关系（子集）包含关系（子集）定义定义定义定义3-1.1 设设设设A A、B B是任意两个集合，是任意两个集合，是任意两个集合，是任意两个集合，如果如果A的每一个元素的每
11、一个元素都是都是B的元素，则称的元素，则称集合集合A是是集合集合B的的子集合子集合（或（或子集子集子集子集，subsets），或称），或称A包含在包含在B内，内，记为记为A B；或称或称B包含包含A，记为记为记为记为B A。即即 A B x(x Ax B)设设A，B，C为任意集合，根据定义，显然有：为任意集合，根据定义，显然有：包含关系具有自反性包含关系具有自反性：A A 包含关系具有传递性：若包含关系具有传递性：若A B且且B C，则，则A C。现在学习的是第17页，共56页 注：可能注：可能注：可能注：可能A B或或B A，也可能两者均不成立，不是两，也可能两者均不成立，不是两者必居其一。
12、者必居其一。例：例：A=1，2，3，B=1，2，C=1，3，D=3，F=1，4，则则B A，C A，D C，F A 现在学习的是第18页，共56页现在学习的是第19页，共56页现在学习的是第20页，共56页四、特殊的集合四、特殊的集合1、空集、空集定义定义3-1.3：不含任何元素的集合称为空集，记作：不含任何元素的集合称为空集，记作。=x|p(x)p(x)例如：例如：X=x|x2+1=0，x R是空集。是空集。注意：注意：，定理定理3-1.2：对于任意一个集合A，A。证明：反证法，假设存在一个集合A，使得A为假。则存在x且xA，这与空集的定义矛盾，所以A，空集是任意集合的子集。推论：空集是唯一
13、的。推论：空集是唯一的。证明：设1，2是两个空集，则12，21，得1=2，所以空集是唯一的。现在学习的是第22页，共56页2、全集、全集定义定义3-1.4：在一定范围内，如果所有集合均是某一集合的子集，则称该集合为全集。记作E。E=x|p(x)p(x)3、幂集、幂集定义定义3-1.5：给定集合A，由A的所有子集为元素组成的集合称为A的幂集，记作(A)或2A。(A)=u|uA例：设A=1，2，3，写出A的幂集(A)。解：(A)=，1，2，3，1，2，1，3，2，3，1，2，3现在学习的是第23页，共56页 一般地如果|A|=n，则：A的0元子集有Cn0=1个，即空集，1元子集有Cn1个，2元子集
14、有Cn2个，n-1元子集有Cnn-1个，n元子集有Cnn个。所以A的子集个数为：Cn0+Cn1+Cn2+Cnn=2n。有：定理定理3-1.3：如果有限集A有n个元素，其幂集(A)有2n个元素。现在学习的是第24页，共56页例：A=a,，判断下列结论是否正确。（1）A，（2）A，（3）A（4）A，（5）aA，（6）aA，（7）aA，（8）aA，结论（1）、（2）、（3）、（5）、（8）正确。现在学习的是第25页，共56页3-2 3-2 集合的运算及其性质集合的运算及其性质现在学习的是第27页，共56页一、集合的运算一、集合的运算1、交、交定义定义3-2.1：设任意两个集合A和B，由A和B的所有共
15、同元素组成的集合，称为A和B的交集，记为AB。AB=x|x Ax B文氏图现在学习的是第28页，共56页例1：A=0，2，4，6，8，10，12，B=1，2，3，4，5，6，AB=2，4，6例2：设A是平面上所有矩形的集合，B是平面上所有菱形的集合，AB是所有正方形的集合。例3：设A是所有能被K整除的整数的集合，B是所有能被L整除的整数的集合，AB是所有能被K与L最小公倍数整除的整数的集合。举例举例现在学习的是第29页，共56页性质：性质：a)AA=Ab)A=c)AE=Ad)AB=BAe)(AB)C=A(BC)f)ABA，ABB现在学习的是第30页，共56页例题4：设AB，求证ACBC。证明：
16、对任一个x AC，则x A且x C，因为有AB，若x A，则x B，所以x B且x C，故x BC。因此ACBC。举例举例现在学习的是第32页，共56页现在学习的是第33页，共56页2、并集、并集定义定义3-2.2：设任意两个集合A和B，所有属于A或属于B的元素组成的集合，称为A和B的并集，记作AB。AB=x|x Ax B文氏图现在学习的是第34页，共56页例1：A=1，2，3，4，B=2，4，5，AB=1，2，3，4，5例2：设A是奇数集合，B是偶数集合，AB是整数集合，AB=。举例举例现在学习的是第35页，共56页性质：性质：a)AA=Ab)AE=Ec)A=Ad)AB=BAe)(AB)C=
17、A(BC)f)AAB，BAB现在学习的是第36页，共56页例题3：设AB，CD，求证ACBD。证明：对任一x AC，则x A或x C，（1）若x A，则x B，故x B D；（2）若x C，则x D，故x BD。因此ACBD。举例举例现在学习的是第37页，共56页定理定理3-2.1 设设A，B，C为三个集合，则下列分配律成立。为三个集合，则下列分配律成立。a)A(B C)=(A B)(A C)b)A(B C)=(A B)(A C)证明：证明：a)设设S=A(B C)，T=(A B)(A C)，若，若x S，则，则x A且且x B C，即，即x A且且 x B或或 x A且且 x C，x A B
18、或或x A C即即x T，所以，所以S T。反之，若反之，若x T，则，则x A B或或x A C，x A且且 x B或或 x A且且 x C，即，即x A且且x B C，于是，于是x S，所以，所以T S。因此，因此，S=T。b)证明完全与证明完全与a)类似。类似。现在学习的是第38页，共56页定理定理3-2.2 设设A，B为任意两个集合，则下为任意两个集合，则下列吸收律成立。列吸收律成立。a)A(A B)=Ab)A(A B)=A证明：证明：a)A(A B)=(A E)(A B)=A(E B)=A E=Ab)A(A B)=(A A)(A B)=A(A B)=A现在学习的是第39页，共56页定
19、理定理3-2.3 A B，当且仅当，当且仅当A B=B或或A B=A。证明：若证明：若A B，对任意，对任意x A必有必有x B，（1）对任意）对任意x A B，则，则x A或或x B，即，即x B，所以，所以A B B。（2）又）又B A B，因此得到，因此得到A B=B。反之，若反之，若A B=B，因为，因为A A B，所以，所以A B。同理可证得同理可证得A B=A现在学习的是第40页，共56页3、差集、补集、差集、补集定义定义3-2.3：设A、B是任意两个集合，所有属于A而不属于B的元素组成的集合称为B对A的补集，或相对补，(或A和B差集)记作A-B。A-B=x|xAxB文氏图现在学习
20、的是第41页，共56页定义定义3-2.4：设E为全集，任一集合A关于E的补，称为A的绝对补，记作A。A=E-A=x|xExA文氏图现在学习的是第42页，共56页性质性质：a)(A)=Ab)E=c)=Ed)AA=Ee)AA=现在学习的是第43页，共56页定理3-2.4 设A，B为任意两个集合，则下列关系式成立。a)(AB)=ABb)(AB)=AB定理3-2.5 设A，B为任意两个集合，则下列关系式成立。a)A-B=ABb)A-B=A-(AB)定理3-2.6 设A，B，C为三个集合，则A(B-C)=(AB)-(AC)定理3-2.7 设A，B为任意两个集合，若AB，则a)BAb)(B-A)A=B现在
21、学习的是第44页，共56页4、对称差定义定义3-2.5：设A、B是任意两个集合，集合A和B的对称差，其元素或属于A，或属于B，但不能既属于A又属于B，记作AB。AB=(A-B)(B-A)文氏图现在学习的是第45页，共56页性质：a)AB=BAb)A=Ac)AA=d)AB=(AB)(AB)e)(AB)C=A(BC)现在学习的是第46页，共56页3-3 3-3 包含排斥原理包含排斥原理 (容斥原理容斥原理)现在学习的是第47页，共56页包含排斥原理包含排斥原理1、定理、定理3-3.1：设A1，A2为有限集合，其元素个数分别为|A1|，|A2|，则|A1A2|=|A1|+|A2|-|A1A2|，此定
22、理被称作包含排斥原理。证明：a)当A1A2=，则|A1A2|=|A1|+|A2|b)若A1A2，则|A1|=|A1A2|+|A1A2|，|A2|=|A1A2|+|A1A2|所以|A1|+|A2|=|A1A2|+|A1A2|+|A1A2|+|A1A2|=|A1A2|+|A1A2|+2|A1A2|而|A1A2|+|A1A2|+|A1A2|=|A1A2|故|A1A2|=|A1|+|A2|-|A1A2|现在学习的是第48页，共56页解：设解：设A为从为从1到到500的整数中，能被的整数中，能被3除尽的数的集合。除尽的数的集合。B为从为从1到到500的整数中，能被的整数中，能被5除尽的数的集合。除尽的数
23、的集合。则则 A=500/3=166（x表示不超过表示不超过x的最大整数）的最大整数）B=500/5=100 A B=500/（3*5）=33由包含排斥原理：由包含排斥原理：A B=A+B-A B=166+100-33=233即从即从1到到500的整数中，能被的整数中，能被3或或5除尽的数有除尽的数有233个。个。例例1 1：求从：求从1 1到到500500的整数中，能被的整数中，能被3 3或或5 5除尽的数的个数。除尽的数的个数。现在学习的是第49页，共56页解：设职员和学生的集合分别是解：设职员和学生的集合分别是A和和B。由已知条件。由已知条件 A=10，B=12，A B=5，有，有 A
24、B=A+B-A B=10+12-5=17，则，则(A B)=E-A B=20-17=3。有有3名青年既不是职员又不是学生。名青年既不是职员又不是学生。例例2：在：在20名青年中有名青年中有10名是公司职员，名是公司职员，12名是学生，其中名是学生，其中5名既是职员又是学生，问有几名既不是职员，又不是学生。名既是职员又是学生，问有几名既不是职员，又不是学生。现在学习的是第50页，共56页例题例题3 3 假设在假设在1010名青年中有名青年中有5 5名是工人，名是工人，7 7名是学生，名是学生，其中兼具工人和学生双重身份的青年有其中兼具工人和学生双重身份的青年有3 3名，问有几名，问有几名既不是工
25、人又不是学生。名既不是工人又不是学生。解：设工人的集合为解：设工人的集合为W W，学生的集合为，学生的集合为S S。则根据题设有。则根据题设有|E|=10|E|=10，W W=5=5，S S=7=7，W W S S=3=3，则则 W W S S=W W+S S-W W S S=5+7-3=9=5+7-3=9，则则(A(A B)B)=E E-A A B B=10-9=1=10-9=1。有有1 1名既不是工人又不是学生。名既不是工人又不是学生。现在学习的是第51页，共56页2、三个集合的包含排斥原理：、三个集合的包含排斥原理：对于三个集合A1，A2和A3，其元素个数分别为|A1|，|A2|，|A3
26、|，则|A1A2A3|=|A1|+|A2|+|A3|-|A1A2|-|A1A3|-|A2A3|+|A1A2A3|现在学习的是第52页，共56页例题例题4 在某工厂装配在某工厂装配30辆汽车，可供选择的设备是收音机、空辆汽车，可供选择的设备是收音机、空气调节器和对讲机。已知其中有气调节器和对讲机。已知其中有15辆汽车有收音机，辆汽车有收音机，8辆有空气辆有空气调节器，调节器，6辆有对讲机，而且其中有辆有对讲机，而且其中有3辆汽车这三样设备都有。辆汽车这三样设备都有。我们希望至少有多少辆汽车没有任何设备。我们希望至少有多少辆汽车没有任何设备。解：设解：设A1，A2和和A3分别表示配有收音机、空气调
27、节器和对讲机的汽车集合。因此分别表示配有收音机、空气调节器和对讲机的汽车集合。因此|A1|=15，|A2|=8，|A3|=6，|A1 A2 A3|=3，故，故|A1 A2 A3|=|A1|+|A2|+|A3|-|A1 A2|-|A1 A3|-|A2 A3|+|A1 A2 A3|=15+8+6-|A1 A2|-|A1 A3|-|A2 A3|+3=32-|A1 A2|-|A1 A3|-|A2 A3|因为因为|A1 A2|A1 A2 A3|，|A1 A3|A1 A2 A3|，|A2 A3|A1 A2 A3|所以所以|A1 A2 A3|32-3-3-3=23即至多有即至多有23辆汽车有一个或几个选择的设备，因此至少有辆汽车有一个或几个选择的设备，因此至少有7辆汽车不提供任何可辆汽车不提供任何可选择的设备。选择的设备。现在学习的是第53页，共56页3、n个集合的包含排斥原理个集合的包含排斥原理定理定理3-3.2 设A1，A2，An为有限集合，其元素个数分别为|A1|，|A2|，|An|，则现在学习的是第56页，共56页