离散数学 3-1集合概念表示法

1、Discrete Mathematics山东科技大学山东科技大学信息科学与工程学院信息科学与工程学院集合论十九世纪下半叶，康托尔创立了著名的集合论，在集合论刚产生时，曾遭到许多人的猛烈攻击。但不久这一开创性成果就为广大数学家所接受了，并且获得广泛而高度的赞誉。数学家们发现，从自然数与康托尔集合论出发可建立起整个数学大厦。因而集合论成为现代数学的基石。集合论“一切数学成果可建立在集合论基础上”这一发现使数学家们为之陶醉。1900年，国际数学家大会上，法国著名数学家庞加莱就曾兴高采烈地宣称：“借助集合论概念，我们可以建造整个数学大厦今天，我们可以说绝对的严格性已经达到了”可是，好景不长。1903年

2、，一个震惊数学界的消息传出：集合论是有漏洞的！这就是英国数学家罗素提出的著名的罗素悖论。理发师悖论（罗素悖论）理发师悖论（罗素悖论）20世纪英国著名哲学家、数学家罗素提出一个著名的悖论“理发师难题”，其内容如下： 西班牙的塞维利亚有一个理发师，这位理发师有一条极为特殊的规定：他只给那些“不给自己刮胡子”的人刮胡子。 罗素悖论罗素悖论罗素构造了一个集合S：S由一切不是自身元素的集合所组成。罗素问：S是否属于S呢？如果S属于S，根据S的定义，S就不属于S；反之，如果S不属于S，同样根据定义，S就属于S。无论如何都是矛盾的。G.弗雷格在收到罗素介绍这一悖论的信后伤心地说：“一个科学家所遇到的最不合心

3、意的事莫过于是在他的工作即将结束时，其基础崩溃了。罗素先生的一封信正好把我置于这个境地。”可以说，这一悖论就象在平静的数学水面上投下了一块巨石，而它所引起的巨大反响则导致了第三次数学危机。危机产生后，数学家纷纷提出自己的解决方案：人们希望能够通过对康托尔的集合论进行改造，通过对集合定义加以限制来排除悖论，这就需要建立新的原则。“这些原则必须足够狭窄，以保证排除一切矛盾；另一方面又必须充分广阔，使康托尔集合论中一切有价值的内容得以保存下来。”1908年，策梅罗在这一原则基础上提出第一个公理化集合论体系，后来经其他数学家改进，称为ZF系统。这一公理化集合系统很大程度上弥补了康托尔朴素集合论的缺陷。

4、公理化集合系统的建立，成功排除了集合论中出现的悖论，从而比较圆满地解决了第三次数学危机。集合论第3章 集合和关系第4章 函数第三章第三章 集合与关系集合与关系 本章主要讲授集合论的基本知识，包括集合本章主要讲授集合论的基本知识，包括集合运算、包含排斥原理、笛卡尔积、关系及其性质、运算、包含排斥原理、笛卡尔积、关系及其性质、关系的运算、特殊关系关系的运算、特殊关系(包括等价关系、相容关包括等价关系、相容关系、序关系系、序关系)等。等。重点是集合的运算、关系及其表示、关系重点是集合的运算、关系及其表示、关系的性质、关系的闭包、等价关系、偏序关系。的性质、关系的闭包、等价关系、偏序关系。难点是关系的

5、性质、等价关系、偏序关系的证明。难点是关系的性质、等价关系、偏序关系的证明。3-1 3-1 集合的概念和表示法集合的概念和表示法 组成集合的对象称为集合的组成集合的对象称为集合的member或或（element）。）。 是是一些确定的、作为一些确定的、作为整体识别整体识别的、的、互相区别互相区别的的对象的总体对象的总体。一、集合的基本概念一、集合的基本概念 一般用大写字母表示集合，用小写字母表示一般用大写字母表示集合，用小写字母表示 A A，读作，读作“ 属于属于A”A”、“ 是是A A的元素的元素”、“A A的成员的成员”、 “ “ 在在A A之中之中”、“A A 包含包含 ”。 如果如果是

6、是A A的元素，的元素， A A读作读作“属于属于A ”A ”。空集和只含有有限多个元素的集合称为空集和只含有有限多个元素的集合称为（finite sets），否则称为），否则称为（infinite sets）。）。有限集合中元素的个数称为集合的有限集合中元素的个数称为集合的（cardinality）。集合）。集合A的基数表示为的基数表示为 A 。集合的分类集合的分类二、集合的三种表示方式二、集合的三种表示方式：列举法列举法 将集合的元素列举出来。将集合的元素列举出来。 （2）描述法）描述法 利用一项规则（一个谓词公式），描述集合利用一项规则（一个谓词公式），描述集合中的元素的共同性质，以便决

7、定某一物体是否中的元素的共同性质，以便决定某一物体是否属于该集合。属于该集合。 （3）归纳法）归纳法用递归方法定义集合。用递归方法定义集合。 1、列举法：将集合的元素列举出来、列举法：将集合的元素列举出来例：例：A=a，b，c，d，A1=1，3，5，7，9，使用列举法，须列出足够多的元素以反映集合中使用列举法，须列出足够多的元素以反映集合中成员的特征。成员的特征。如：如：B=2，4，8，若若x=2n，则，则 B=2，4，8，16，32，若若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，x R，

8、D=(x，y)|x2+y2 1，x，y R F=x|x是中国的一个省是中国的一个省说明：说明：1、描述法中、描述法中C=x|1 x 5，x R与与C=y|1 y 5，x R表示同一个集合。表示同一个集合。2、集合中元素是无序的。、集合中元素是无序的。a，b，c，b，c，a，c，a，b表示同一个集合。表示同一个集合。3、集合中的元素可能也是集合，例：、集合中的元素可能也是集合，例：A=1，2，1，1，2，3，1 A，1 A。三、集合的关系三、集合的关系1.相等关系相等关系相等相等(外延性公理外延性公理)：两个集合是相等的，当且仅当：两个集合是相等的，当且仅当它们有相同的成员。它们有相同的成员。

9、两个集合两个集合A和和B相等，记作相等，记作A=B，两个集合不，两个集合不相等，记作相等，记作A B。0，1=x|x(x2-2x+1)=0，x I0，1 1，2对任意谓词公式对任意谓词公式P(x)，均存在集合，均存在集合S，使得，使得 S = x P(x) 两个集合两个集合 A和和 B相等相等它们具有相同它们具有相同的元素。即对任意集合的元素。即对任意集合A、B, A=B x(x Ax B) 对任意个体域，任一谓词公式都确定一个以该对任意个体域，任一谓词公式都确定一个以该域中的对象为元素的集合。即对给定个体域域中的对象为元素的集合。即对给定个体域U，对，对任意谓词公式任意谓词公式P(x)，存在

10、集合，存在集合S，使得，使得 Sx x UP(x)如果如果A的每一个的每一个元素都是元素都是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。A B或或B A ，也可能两者均不成立，不，也可能两者均不成立，不是两者必居其一。是两者必居其一。 例：例：A=1，

11、2，3，B=1，2，C=1，3， D=3，F=1，4，则则B A， C A， D C， F A ()()()()ABx xAxBx xBxA n元集、元集、m元子集元子集n含有n个元素的集合称为n元集。n它的含有m个元素的子集称为它的m元子集。四、特殊的集合四、特殊的集合1、空集、空集定义定义3-1.3：不含任何元素的集合称为空集，记作：不含任何元素的集合称为空集，记作。=x|p(x)p(x)例如：例如：X=x|x2+1=0，xR是空集。是空集。注意：注意： ， 定理定理3-1.2：对于任意一个集合A，A。证明：反证法，假设存在一个集合A，使得A为假。则存在x且xA，这与空集的定义矛盾，所以A

12、，空集是任意集合的子集。推论：空集是唯一的。推论：空集是唯一的。证明：设1，2是两个空集，则12，21，得1=2，所以空集是唯一的。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 一般地如果|A|=n，则：A的0元子集有Cn0=1个，即空集，1元子集有Cn1个，2元子集有Cn2个，n-

13、1元子集有Cnn-1个，n元子集有Cnn个。所以A的子集个数为：Cn0+Cn1+Cn2+Cnn=2n。有：定理定理3-1.3：如果有限集A有n个元素，其幂集(A)有2n个元素。例：A=a, ，判断下列结论是否正确。（1） A，（2） A，（3）A（4）A，（5）aA， （6） aA，（7）aA， （8）aA，结论（1）、（2）、（3）、（5）、（8）正确。上次课n集合的概念n集合的表示n集合的关系n特殊的集合：空集、全集、幂集3-2 3-2 集合的运算及其性质集合的运算及其性质一、集合的运算一、集合的运算1、交、交定义定义3-2.1：设任意两个集合A和B，由A和B的所有共同元素组成的集合，称为

14、A和B的交集，记为AB。 AB=x|x Ax B文氏图例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最小公倍数整除的整数的集合。举例举例性质：性质：a)AA=Ab)A=c)AE=Ad)AB=BAe)(AB)C=A(BC)f)ABA，ABB例题4：设AB，求证ACBC。证明：对任一个x AC，则x A且x C， 因为有AB，若x A，则x B， 所以x B且x C，故x BC。 因此

15、ACBC。举例举例2、并集、并集定义定义3-2.2：设任意两个集合A和B，所有属于A或属于B的元素组成的集合，称为A和B的并集，记作AB。 AB=x|x Ax B文氏图例1：A=1，2，3，4，B=2，4，5，AB=1，2，3，4，5例2：设A是奇数集合，B是偶数集合，AB是整数集合，AB=。举例举例性质：性质：a)AA=Ab)AE=Ec)A=Ad)AB=BAe)(AB)C=A(BC)f)AAB，BAB例题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。举例举例定理定理3-

16、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或或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)类

17、似。类似。定理定理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定理定理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

18、B=B，因为，因为A A B ，所以，所以A B 。同理可证得同理可证得A B=A3、差集、补集、差集、补集定义定义3-2.3：设A、B是任意两个集合，所有属于A而不属于B的元素组成的集合称为B对A的补集，或相对补，(或A和B差集)记作A-B。 A-B=x|xAxB文氏图定义定义3-2.4：设E为全集，任一集合A关于E的补，称为A的绝对补，记作A。 A=E-A=x|xExA文氏图性质性质：a)(A)=Ab)E=c)=Ed)AA=Ee)AA=定理3-2.4 设A，B为任意两个集合，则下列关系式成立。a)(AB)=ABb)(AB)=AB定理3-2.5 设A，B为任意两个集合，则下列关系式成立。a)

19、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=B4、对称差定义定义3-2.5：设A、B是任意两个集合，集合A和B的对称差，其元素或属于A，或属于B，但不能既属于A又属于B，记作AB。 AB=(A-B)(B-A)文氏图性质：a)AB=BAb)A=Ac)AA=d)AB=(AB)(AB)e)(AB)C=A(BC)3-3 3-3 包含排斥原理包含排斥原理 ( (容斥原理容斥原理) )包含排斥原理包含排斥原理1、定理、定理3-3.1：设A1，A2为有限集合，其元素个

20、数分别为|A1|，|A2|，则|A1A2|=|A1|+|A2|-|A1A2|，此定理被称作包含排斥原理。证明：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| 解：设解：设A为从为从1到到500的整数中，能被的整数中，能被3除尽的数的集合。除尽的数的集合。 B为从为从1到到

21、500的整数中，能被的整数中，能被5除尽的数的集合。除尽的数的集合。则则 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除尽的数的个数。除尽的数的个数。解：设职员和学生的集合分别是解：设职员和学生的集合分别是A和和B。由已知条件

22、。由已知条件 A =10， B =12， A B =5，有，有 A B = A + B - A B =10+12-5=17，则，则(A B) = E - A B =20-17=3。有有3名青年既不是职员又不是学生。名青年既不是职员又不是学生。 例例2：在：在20名青年中有名青年中有10名是公司职员，名是公司职员，12名是学生，名是学生，其中其中5名既是职员又是学生，问有几名既不是职员，名既是职员又是学生，问有几名既不是职员，又不是学生。又不是学生。例题例题3 3 假设在假设在1010名青年中有名青年中有5 5名是工人，名是工人，7 7名是学名是学生，其中兼具工人和学生双重身份的青年有生，其中兼

23、具工人和学生双重身份的青年有3 3名，名，问有几名既不是工人又不是学生。问有几名既不是工人又不是学生。解：设工人的集合为解：设工人的集合为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名既不是工人又不是学生。名既不是工人又不是学生。 2、三个集合的包含排斥原理：、三个

24、集合的包含排斥原理：对于三个集合A1，A2和A3，其元素个数分别为|A1|，|A2|，|A3|，则|A1A2A3|=|A1|+|A2|+|A3|-|A1A2|-|A1A3|-|A2A3|+|A1A2A3|例题例题4 在某工厂装配在某工厂装配30辆汽车，可供选择的设备是收音机、辆汽车，可供选择的设备是收音机、空气调节器和对讲机。已知其中有空气调节器和对讲机。已知其中有15辆汽车有收音机，辆汽车有收音机，8辆辆有空气调节器，有空气调节器，6辆有对讲机，而且其中有辆有对讲机，而且其中有3辆汽车这三样辆汽车这三样设备都有。我们希望至少有多少辆汽车没有任何设备。设备都有。我们希望至少有多少辆汽车没有任何

25、设备。解：设解：设A1，A2和和A3分别表示配有收音机、空气调节器和对讲机的汽车分别表示配有收音机、空气调节器和对讲机的汽车集合。因此集合。因此|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

26、 A2 A3| 32-3-3-3=23即至多有即至多有23辆汽车有一个或几个选择的设备，因此至少有辆汽车有一个或几个选择的设备，因此至少有7辆汽车不提辆汽车不提供任何可选择的设备。供任何可选择的设备。 练习：练习： 某年级有某年级有59名学生，期末考高等数学、线性代数名学生，期末考高等数学、线性代数和英语三门课。已知高等数学、线性代数和英语和英语三门课。已知高等数学、线性代数和英语各门课的及格人数分别为各门课的及格人数分别为47人、人、49人和人和50人。人。其中高等数学、英语都及格的有其中高等数学、英语都及格的有43人，线性代数人，线性代数和英语都及格的有和英语都及格的有42人，三门课都及格

27、的有人，三门课都及格的有40人，人，三门课都不及格的有三门课都不及格的有1人。问高等数学和线性代人。问高等数学和线性代数都及格的有多少人？只有一门课及格的有多少数都及格的有多少人？只有一门课及格的有多少人？人？ 解 设全集U为该年级全体学生的集合。 A为高等数学及格的学生的集合。 B为线性代数及格的学生的集合。 C为英语及格的学生的集合。3、n个集合的包含排斥原理个集合的包含排斥原理定理定理3-3.2 设A1，A2，An为有限集合，其元素个数分别为|A1|，|A2|，|An|，则解：设解：设1 1到到250250间分别能被间分别能被2 2，3 3，5 5，7 7整除的整数集合为整除的整数集合为A A1 1，A A2 2，A A3 3，A A4 4。设。设 x x 表示不大于表示不大于x x最大整数，最大整数， A A1 1 =