离散数学教程——集合的基本概念

1、集合的基本概念,1.1 集合的表示 1.2 集合的子集 1.3 笛卡尔积 1.4 集合的运算 1.5 罗素悖论,离散数学教程,引言：什么是集合？,一些自行车 在计算机系车棚内的自行车,一些自行车 不是集合，无法确定范围和性质 在计算机系车棚内的自行车 是集合，可以确定范围和性质,1.1 集合的表示,集合的定义 集合：具有共同性质的一些东西汇集成一个整体。例：复旦大学教师 元素：构成一个集合中的那些对象。 aA a是A的元素，a属于A aA a不是A的元素，a不属于A 例：吴永辉复旦大学教师，沈恩绍 复旦大学教师 常用大写字母表示集合，小写字母或数字表示元素,1.1 集合的表示,二 集合的表示 列出集合中的元素：A=1,3,5,7,9 描述集合中元素具有的共同性质 x | p(x) ： 通过某规则的计算来定义集合中的元素,1.1 集合的表示,三 术语 空集：不含任何元素的集合，记为 有/无限集：集合中有有限个元素/否则 有限集A的元素个数称为集合A的基数，记为|A|。 集合中元素之间的次序是无关紧要的。 多重集：集合中元素可以重复出现 集合族：以集合为元素组成的集合 与是不同的： 表示以

2、为元素的集合。,例：设A, B, C是任意3个集合，如果AB, B C, 则AC可能吗？ AC常真吗？举例说明。 /*集合论题集，经典习题，集合基础*/,1.2 集合的子集,一 文氏图：用平面上封闭曲线包围点集的图形来表示集合 图1.1, 图1. 2,二 定义1.1（子集） 集合A, B，A的每一元素都是B的元素，则A是B的子集。AB或BA。 特别：AA。 此外，若存在元素aA, 但aB, 则A不是B的子集.,三 定义1.2（集合相等与不相等）：集合A和B的元素全相同，则称A和B相等，A=B；否则称A和B不相等，AB。,定理1.1 A=BAB并且BA。,1.2 集合的子集证明的方法,定理1.1： A=BAB并且BA。 “当且仅当”：证明由两部分组成： 1）由条件证明结论 A=B AB并且BA 2）由结论证明条件 AB并且BA A=B,证明： A=B AB并且BA。因为A=B，由定义A中的每个元素是在B中，所以AB，同理B中的每个元素是在A中，所以BA。 AB并且BA A=B。反证，如果AB，则A中至少有一个元素不在B中，与AB矛盾；或者B中至少有一个元素不在A中，与BA矛盾。所以AB不

3、可能成立。所以A=B。,四 定义1.3（真子集）：AB并且AB，则AB。 （和不同：元素 集合；集合集合）,例：设A, B, C是集合，判断下列命题真假，如果为真，给出证明；如果为假，给出反例： 1) AB, BC AC; 2) AB, BC AC; 3) AB, BC AC; 4) AB, BC AC; 5) aA, AB aB. /*集合论题集，经典习题，集合基础*/,五 定义1.4（全集）：在取定一个集合U以后，对于U的任何子集而言，称U为全集。,定理1.2： （1）A (2) AA (3) AU,1.2 集合的子集证明的方法,证明：（1）A (2) AA (3) AU （1）反证法：假设结论不成立，导出矛盾结果。 不是A的子集，导致矛盾 （2，3）基本法：由子集定义 x左x右，则左右,证明：（1）A 假设不是A的子集，则至少有一个元素x，使得x且xA。又因为是空集，它没有元素，所以对任何x，必有x，导致矛盾。因此是集合A的子集。,反证法的证明步骤,（1）假设命题的结论不成立； （2）进行一系列的推理； （3）推理过程中出现下列情况中的一种： 1）与已知条件矛盾； 2）与公理矛盾

4、； 3）与已知定理矛盾； （4）由于上述矛盾的出现，可以断言，原来的假定“结论不成立”是错误的 （5）肯定原来命题是正确的。,反证法的思想 / 思维过程,“结论不成立”与“结论成立”必有一个正确。 “结论不成立”会导致出现错误，推理过程、已知条件、公理和已知定理没有错误，惟一有错误的是一开始接假定的“结论不成立”，所以“结论不可能不成立”，即“结论成立”。,1.2 集合的子集,六 定义1.5（幂集）： A的所有子集组成的集合称为A的幂集。记为P(A)。 例 1.1（已知A，求幂集） 定理 1.3 | P(A) |=2|A| 证明方法：组合的方法,求幂集 代数法,P13 习题1.13 设A=a, a，问： (1) aP(A)? aP(A)? (2) aP(A)? aP(A)? (3) 又设A=a, b，重复(1)、(2)。 解: (1, 2)首先求P(A)，代数法： 代入：设x=a ，则A=a, x； P(A)=, a, x, a, x； 回代： P(A)=, a, a, a, a,P(A)=, a, a, a, a a P(A) a P(A) aP(A) aP(A) 同理，用代入法，设

5、x=b ，则A=a, x； 回代： P(A)=, a, b , a, b，则a P(A)，a P(A)， aP(A)，aP(A),1.3 笛卡尔积,一 定义1.6（有序对） 两个对象按一定次序组成一对，称为有序对(a, b)。 （a, b)=(c, d) a=c和b=d。,二 定义1.7（有序n元组） n个对象的序列a1, a2, ,an组成一组称为有序n元组，记为(a1, a2, ,an)，其中ai称为第i个分量。 两个有序n元组相等每个对应分量相等。,1.3 笛卡尔积,三定义1.8（直积） 两个集合A和B，定义A和B的笛卡尔积为AB=(a, b) | aA, bB，又称AB为A和B的直积。,1.3 笛卡尔积,四 定义1.9（笛卡尔积） n个集合A1, A2, , An , A1 A2An=(a1, a2, ,an) | aiAi, i=1, n。 若对所有i，Ai=A, 则A1 A2An记为An。,1.4 集合的运算,一 定义1.10 (并，交，差，补，对称差) (1) AB=x | xA或xB (2) AB=x | xA且xB (3) A-B=x | xA且xB (4) =U-A

6、 (5) AB=(A-B)(B-A),例 集合运算：A=1,2,3,4,5, B=1,2,4,6, C=7,8, U=1,2,3,4,5,6, 7,8,9,10 AB=1,2,3,4,5,6, AB=1,2,4, AC=, A-B=3,5, A-C=A,1.4 集合的运算,证明两个集合相等，可用如下办法： 基本法 集合相等的充要条件是两个集合互为子集；即，左式右式，右式左式。所以证明：x左式x右式；x右式x左式。 经典实例：例1.4，例1.5，例1.6证明 理论基础：定理1.1和定义1.1, 1.2 公式法 由集合运算的基本性质，通过推演，进行证明。 经典实例：例1.7，例1.8 证明 理论基础：定理1.4和定义1.10,基本法,例1.4 A(BC)=(AB)(AC) 证明： 1）A(BC)(AB)(AC) 任一xA(BC)x(AB)(AC) 2）(AB)(AC)A(BC) 任一x(AB)(AC)xA(BC),基本法,例1.5 若AB, 则(AB)=A, AB=B. 证明： 1）证(AB)=A思想： (AB)A； A(AB) 2）证AB=B思想： ABB; BAB,例1.6证明:,1.

7、4 集合的运算,三 定理1.4 (集合运算的基本性质) (1) 幂等律 AA=A AA=A (2) 交换律 AB=BA AB=BA (3) 结合律 A(BC)=(AB)C A(BC)=(AB)C (4) 分配律 A(BC)=(AB)(AC) A(BC)=(AB)(AC),1.4 集合的运算,(5) 恒等律 AU=U AU=A A=A A= (6) 取补律,1.4 集合的运算,(7) 双重补,1.4 集合的运算,(8) 狄摩根律,证明类似于例1.4，例1.5，例1.6证明,判断题，为真给出证明，为假给出反例： 若AB=AC，则B=C。 /*北京大学1994考研*/,解：错误。 如果A为空集，则有AB=AC，即使BC，原式成立。,公式法,原则： 1）根据集合运算的定义，将集合运算表达式中-和转换为和； 2）将补运算作用到单一集合上； 3）左式右式；右式左式；左式中间式，右式中间式； 4）根据定义1.10和定理1.4转换,例：(AB)-C=(A-C)(B-C),例1.7 证明(AB)-(AC)=A(B-C) 证明思想：将集合运算表达式中-转换,例1.8 证明AB=(AB)-(AB) 证明思想

8、：将集合运算表达式中-和转换,P()= . /*北京理工大学1999考研*/,判断题，为真给出证明，为假给出反例： （1）x-x （2）(AB)C= (AC)(BC) /*(1)北京大学1994考研, (2)上海交通大学2001考研*/,解：错误。 x-x=x 显然，x不成立。,幂集证明基本法、幂集的定义,证明：P(A)P(B)P(AB)，并说明等号成立的条件。 /*上海交通大学1999考研*/,判断下式是否成立，如果成立，则证明；否则举出反例。 P(A)P(B)=P(AB) /*上海交通大学2001考研*/,1.4 集合的运算,四 定义1.11 (多个集合的并和交) 设集合A1, , An，定义： A1An= x | 至少有某个i，1in，xAi ，称为A1, , An的并； A1An= x | xAi，对一切i=1,n成立，称为A1, , An的交。,1.4 集合的运算,五、多个集合的运算，除对并（交）的结合律、交换律成立以外，还有 (1) 分配律 B(A1A2An)=(BA1) (BA2) (BAn) B(A1 A2 An)= (BA1) (BA2)(BAn) (2) 狄摩根律,1.4 集合的运算,六、广义并、广义交 1. 定义（广义并） 设为一个集合族，称由中全体元素的元素组成的集合成为的广义并集，记作 ，称为广义并运算符，读作“大并”。 =x|z (z 并且xz) 例：=a, b, c, d, d, e, f =a, b, c, d, e, f.,1.4 集合的运算,2. 定义（广义交） 设为一个非空集合族，称由中全体元素的公共元素组成的集合成为的广义交集，记作 ，称为广义交运算符，读作“大交”。 =x|z (如果z，则xz) 例：设=1, 2, 3, 1, a, b, 1, 6, 7 =1,3. 在广义并与广义交的运算中，集合族中的元素仍看成集合族。 例，给出下列集合族： 1=a, b, c, d, 2=a, b, 3=a,

《离散数学教程——集合的基本概念》由会员suns****4568分享，可在线阅读，更多相关《离散数学教程——集合的基本概念》请在金锄头文库上搜索。