《离散数学教学课件 ppt 作者 郝晓燕 第3章 集合》由会员分享，可在线阅读，更多相关《离散数学教学课件 ppt 作者 郝晓燕 第3章 集合（41页珍藏版）》请在金锄头文库上搜索。
1、,第3章 集合,早在1638年，意大利天文学家伽利略发现了这样一个问题，全体自然数与全体平方数，谁多谁少？这一问题为现代数学基础集合论的诞生播下了种子。 集合论是19世纪末德国数学家乔治康托创造的。现代数学的发展告诉我们，康托的集会论是自古希腊时代以来两千多年里，人类认识史上第一次给无穷建立起抽象的形式符号系统和确定的运算。并从本质上揭示了无穷的特性，使无穷的概念发生了一次革命性的变化，并渗透到所有的数学分支，从根本上改造了数学的结构，促进了数学许多新的分支的建立和发展，成为实变函数论、代数拓扑、群论和泛函分析等理论的基础。,康托（Georg Cantor，18451918），1845年3月3
2、日生于俄国彼得堡，1856年全家迁居德国法兰克福。康托先后就学于苏黎世大学、哥廷根大学、法兰克福大学和柏林大学，主要学习哲学、数学和物理。在柏林大学，他受到著名分析学家魏尔斯特拉斯的影响，对纯粹数学产生了兴趣。22岁 时以求不定方程 的整数解的博士论文获哲学博士学位。,1 集合的概念,3-1-1 集合的定义 数学的集合是以涵盖宇宙一切事物的一般集合作为其研究对象，而数学的大多数分支所研究的对象或者可以看成某种特定结构的集合，或者可以通过集合来定义，因此集合论的基本概念几乎渗透到数学的一切领域。 集合:一些离散个体构成的,用大写字母A,B,C等表示 元素:组成集合的事物(成员),用小写字母a，b
3、，x，y，表示。,集合的元素具有如下性质:,（1）无序性：集合中元素出现的排列顺序无关 （2）相异性：集合中的元素都是不同的，凡是相同的元素，均视为同一个元素。 （3）确定性：对任何元素和集合都能确定这个元素是否为该集合的元素。集合的元素一旦给定，这一集合便完全确定了，元素a与集合A的关系只能是：元素a属于A，记作aA；或者a不属于A，记作aA，也可以记作(aA)。 （4）任意性：集合的元素也可以是集合。,3-1-2 集合的表示方法,（1）枚举法：列出集合中全部元素或部分元素的方法。 （2）描述法：通过刻画集合中元素所具备的某种特性来表示集合的方法，其一般表示方法为A=x|P(x)，通过谓词P
4、概括集合元素的性质。,3归纳法,归纳法是通过归纳定义集合，主要由三部分组成： 第一部分：基础。指出某些最基本的元素属于某集合； 第二部分：归纳。指出由基本元素造出新元素的方法； 第三部分：极小性。指出该集合的界限。,注意：第一部分和第二部分指出一个集合至少包括的元素，第三部分指出一个集合至多要包含的元素,集合A按如下方式定义： （1）0和1都是A中的元素； （2）如果a, b是A中的元素，则ab, ba也是A中的元素； （3）有限次使用(1)、(2)后所得到的字符串都是A中的元素。 试指出其定义方式。并举出集合A中的3个元素,4、递归指定集合,通过计算规则定义集合中的元素,例 设 a0 1，
5、ai+1 2ai （i0） 定义Sa0 ，a1 ，a2 ，. ak | k0， 试写出集合S中的所有元素。,5、文氏图解法,文氏图解法是一种利用平面上点的集合作成的对集合的图解。一般用平面上的圆形或方形表示一个集合。,A,A,罗素悖论,在某个城市中有一位理发师，他的广告词是这样写的：“本人的理发技艺十分高超，誉满全城。我将为本城所有不给自己刮脸的人刮脸，我也只给这些人刮脸。我对各位表示热诚欢迎！”来找他刮脸的人络绎不绝，自然都是那些不给自己刮脸的人。可是，有一天，这位理发师从镜子里看见自己的胡子长了，他本能地抓起了剃刀，你们看他能不能给他自己刮脸呢？如果他不给自己刮脸，他就属于“不给自己刮脸的
6、人”，他就要给自己刮脸，而如果他给自己刮脸呢？他又属于“给自己刮脸的人”，他就不该给自己刮脸。,思考：考虑一个特殊的集合R，R把所有不属于自身的集合组成一个整体，集合R用描述法表示R=x|xR，问R是否属于R？如果说R属于R，那么R满足R 的定义，R不属于自身，即R不属于R；如果说R不属于R，那么R不满足定义，即R应属于自身，那么R属于R。无论怎样都自相矛盾，这就是著名的罗素悖论。,解决方案,人们希望能够通过对康托尔的集合论进行改造，通过对集合定义加以限制来排除悖论，这就需要建立新的原则。“这些原则必须足够狭窄，以保证排除一切矛盾；另一方面又必须充分广阔，使康托尔集合论中一切有价值的内容得以保
7、存下来。” 1908年，策梅罗在自己这一原则基础上提出第一个公理化集合论体系，后来这一公理化集合系统很大程度上弥补了康托尔朴素集合论的缺陷。除ZF系统外，集合论的公理系统还有多种，如诺伊曼等人提出的NBG系统等。公理化集合系统的建立，成功排除了集合论中出现的悖论，从而比较圆满地解决了第三次数学危机。围绕着数学基础之争，形成了现代数学史上著名的三大数学流派，而各派的工作又都促进了数学的大发展等等。,逻辑主义数学即逻辑,逻辑主义的主要代表人物是英国著名的数学家,哲学家和逻辑学家罗素,他与怀特海于1913年完成了逻辑主义的经典代表作-数学原理.作者企图在这3卷本的数学巨著中向人们说明:全部数学可以以
8、一个逻辑公理系统严格推导出来,也就是说可以从逻辑概念出发用明显的定义得出数学概念;由逻辑命题开始用纯逻辑的演绎推得数学定理.从而,使全部数学都可以从基本的逻辑概念和逻辑规则而推导出来.这样,就可以把数学看成是逻辑学延伸或分支.,形式主义元数学,将各门数学形式化,构成形式系统,然后用一种初等方法证明各个形式系统的相容性,即无矛盾性,从而导出全部数学的无矛盾性. 哥德尔的不完备性定理说,证明一门数学的无矛盾性不可能在本门数学内做出,必须在一门较之更强的数学中才可能做出.,直觉主义,“存在即是被构造.“人们对数学的认识不依赖于逻辑和语言经验,而是“原始直觉“(即人皆有的一种能力),纯粹数学是“心智的
9、数学构造自身“,是“反身的构造“,它“开始于自然数“,而不是集合论. 这种数学构造之成为构造,与这种构造物的性质无关,与其本身是否独立于人们的知识无关,与人们所持的哲学观点也无关.构造物应该怎样就怎样,数学判断应该是永恒的真理.,3-2 集合之间的关系,3-2-1 集合之间的关系 （1）相等关系：两集合A和B相等，当且仅当它们有相同的元素。若A与B相等，记为A=B；否则，记为AB。可形式化为：A=B(x)(xAxB)。,（2）包含关系：设A和B是任意两个集合，如果集合A的每个元素，都是集合B中的一个元素，则称A是B的子集合，简称子集；或称A被包含于B中，记为AB，或称B包含A，记为BA。可形式
10、化为：AB(x)(xAxB)。 （3）真包含关系：设A，B是任意两个集合，如果AB并且AB，则称A是B的真子集，记作A B。可形式化为： ABABAB (x)(xAxB)(y)(yByA)。,定理3-2.1 设A和B是任意两个集合，A=B AB且BA。 证明：若集合A和B相等，当且仅当它们有相同的元素，因此(x)(xAxB)和(x)(xBxA)为真，即AB且BA；若AB且BA，假设AB，则设有一元素xA且xB与AB矛盾，或有一元素yB且yA与BA矛盾，因此必然有A=B。,3-2-2 特殊集合,空集:不含有任何元素的集合，记为。可形式化为：=x|P(x)P(x)，P(x)为任意谓词公式。 空集的
11、性质如下。 空集是任何集合的子集。 证明：对于任意集合A，A(x)(xxA)T(恒真命题) 空集是唯一的。 证明：假设1和2是两个空集，且12，由空集的性质可知12并且21，由定理3-2.1可知1=2与12矛盾。,（2）全集：如果一个集合包含了所要讨论的每一个集合，则称该集合为全集，记为U或E。可形式化为：E=x|P(x)P(x)，其中P(x)为任何谓词公式。 类似空集性质的证明可得到全集的性质： 任何集合是全集的子集； 全集是唯一的。 注意：在实际应用中，常常把某个适当大的集合看成全集，因此全集具有相对性。,（3）幂集：设A为任意集合，把A的所有不同子集构成的集合叫做A的幂集，记为P(A)，
12、可形式化为：P(A)=B|BA。 例3-2.1 求集合A的幂集。 A= 解：P(A)= A= 解：P(A)=， 思考：A是有限集合，则P(A)包含多少个元素？,2.集合的并 AB=xxAxB 即由属于A或者属于B的元素组成的集合,AB,A,B,E,3-3-1 集合的基本运算,1.集合的交 AB=xxAxB 即由既属于A又属于B的元素组成的集合,AB,A,B,E,AB=,A,B,3.集合的差 AB=xxAxB 即由属于A而不属于B的元素组成的集合,A,B,AB,A,B,E,4.集合的补 A=xxExA 即由属于E而不属于A的元素组成的集合,A,A,E,5.集合的对称差 AB=(AB) (BA),
13、AB,A,B,E,3-3-2 集合关系的证明方法,集合关系的基本证明方法是命题演算法 （1）证XY 任取元素x，xXxY （2）证X=Y 方法一 分别证明 XY并且YX 方法二 任取元素x，xXxY,例3-3.3 证明AB=AB 证明：任取元素x，xAB，根据定义3-3.1 xAB xAxB xAxB xAB 因此得AB=AB,分配律(证明),A(BC)=(AB)(AC) 证明: x, xA(BC) xA x(BC) (定义) xA (xB xC) (定义) (xAxB)(xAxC) (命题逻辑分配律) (xAB)(xAC) (定义) x(AB)(AC) (定义) A(BC)=(AB)(AC)
14、,零律(证明),A = 证明: x, xA xA x (定义) xA 0 (定义) 0 x (定义) A = ,排中律(证明),AA = E 证明: x, xAA xA xA (定义) xA xA (定义) xA （xA ） (定义) 1 x E (E定义) AA = E,集合运算的性质,设A，B，C为任意的集合 交换律 AB=BA AB=BA 结合律 （AB）C=A（BC） （AB）C=A（B C） 分配律 A（BC )=（AB）（AC） （BC )A =（BA）（CA ） A（BC）=（AB）（AC） （BC )A =（BA）（CA ） 吸收律 A（AB）=A A（AB）=A,双重否定律 A=A 幂等律 AA=A AA=A 同一律 AE=A A=A 囿律 （0-1律） A= AE=E 矛盾-排中律 AA= AA=E 德摩根律 （AB）=AB （AB）=AB AB=AB A B= (AB) (BA) （AB）（AB） =（AB）（AB）,吸收律(证明),A(AB)=A 证明: A(AB) = (AE)(AB) (同一律) = A(EB) (
