1、集合论,一、本部分的主要内容集合代数-集合的概念和基本运算关系-二元关系的表示、运算、性质、特殊的关系函数-函数定义、性质、运算二、本部分的基本要求掌握集合及其相关的基本概念熟练掌握集合以及关系、函数的基本运算了解和使用基本的证明方法,集合论,德国著名数学家康托（GEORGE CANTOR，18451918)在总结前人的基础上，创立了集合论。集合论为整个经典数学的各分支提供了共同的理论基础。 朴素集合论由于在定义集合的方法上缺乏限制，会导致悖论,集合论,另一个德国数学家蔡梅罗（ERNST ZERMELO）于1908年建立了集合论的公理系统，由这个公理系统，他推出了很多数学上的重要结果。他的公理
2、使数学哲学中产生的一些矛盾基本上得到统一，在此基础上形成了公理化集合论和抽象集合论,集合论,集合论在计算机科学中也具有十分广泛的应用，计算机科学领域中的大多数基本概念和理论几乎均采用集合论的有关术语来描述和论证,集合论,集合论在计算机科学中也具有十分广泛的应用，计算机科学领域中的大多数基本概念和理论几乎均采用集合论的有关术语来描述和论证,denotes +1denotes -1,How would you classify this dataset?,集合论,集合论在计算机科学中也具有十分广泛的应用，计算机科学领域中的大多数基本概念和理论几乎均采用集合论的有关术语来描述和论证,denotes
3、+1denotes -1,How would you classify this dataset?,wT x + b=0,wTx + b0,y,f(x,w,b) = sign(wTx + b),f,x,第六章 集合代数,主要内容集合的基本概念-属于、包含、幂集、空集等集合的基本运算-并、交、补、差等集合恒等式-集合运算的算律、恒等式的证明方法 与后面各章的关系是集合论后面各章的基础,第一节： 集合的基本概念,6.1 集合的基本概念,集合是能作为整体论述的事物的集体，又称为类、族、搜集组成集合的每个事物叫做这个集合的元素或成员。用符号表示某个元素属于某个集合，表示不属于任意元素，对于某一集合而言
4、 ，或属于该集合，或者不属于，二者必居其一，不可兼得。这也符合命题演算中，命题要么是真，要么是假的二值逻辑,通常有三种方法表示集合：1) 列举法2) 描述法 用谓词描述出集合元素的公共特征来表示这个集合。例如：A=a|aR 0a a4 S=a|P(a) 表示a属于S当且仅当 P(a)为真3) 归纳定义法,6.1 集合的基本概念,有限集合的元素的个数称为该集合的基数或势记为|A|。 例：A=0,1 |A|=2；|A|=1外延公理：两个集合A和B相等，即A=B，当且仅当他们有相同的成员（也就是，A的每一元素是B的一个元素而B的每一个元素也是A的一个元素）。用逻辑符号表达是： A=B x(xA xB
5、),6.1 集合的基本概念,讨论集合:集合中元素的次序是无关紧要的集合中的元素的重复出现无足轻重集合的表示不是唯一的，一个集合可以用多种方法表示例如： a,b,c=c,b,a=a,c,b=a,a,b,c,c 讨论: P=a,b,c 与 Q=a,b,c， PQ 设A=x | x*(x-1)=0与 B=0, 1， A = B,6.1 集合的基本概念,集合间的包含关系定义：设A和B是集合，如果A的每一个元素是B的一个元素，那么A是B的子集合，记为A B，读做“ B包含A”或“A包含于B中”。 A B x(xA xB)注意：可能AB或BA，也可能两者均不成立，不是两者必居其一。 定义：设A和B是集合,
6、 如果AB和BA则称A和B相等，记做A=B。定义：如果A B，且AB，那么称A是B的真子集，记作A B，读作“B真包含A” A B (A B) (AB),6.1 集合的基本概念,本章中讨论的集合和元素都是限于某一论述域的。我们记该论述域为E，又称为全集合。定义：没有任何元素的集合称为空集，记为 前者是空集，是没有元素的集合；后者是以作为元素的集合定理：对任意集合A有： A 提示： A x(x xA)推论：空集是唯一的 提示： 1 2 2 1 定理：对任意集合A，有A E,6.1 集合的基本概念,例：确定下列命题是否为真（1） （2） （3） （4） 含有n个元素的集合简称n元集，它的含有m个（
7、mn）元素的子集称为它的m元子集。,6.1 集合的基本概念,例：A=a,b,c,求A的全部子集解：将A的子集从小到大分类：0元子集：只有一个空集。1元子集：有3个a,b,c。2元子集：有3个a,b,a,c,b,c。3元子集：有1个A本身。A共有8个子集，分别为,a,b,c, a,b,a,c, b,c,a,b,c 。所以一般n个元素的集合有2n个不同的子集合,6.1 集合的基本概念,幂集合定义：由集合A的所有子集（包括空集及A本身）所组成的集合叫做A的幂集，记以 P(A),即 P(A) =B|BA一个给定集合的幂集是唯一的例:(a)如果A=, 那么 P(A) = （b）如果A=a,b, 那么 P
8、(A) = ,a,b,a,b,6.1 集合的基本概念,设A为一个有限集，A的基数为|A|，则P(A)的基数|P(A)|=2|A|例：A=，那么 P(A) = , ,6.1 集合的基本概念,第二节：集合的运算与集合恒等式,定义：设A和B是集合A和B的并记为AB，是集合 AB=x|xA xBA和B的交记为AB，是集合 AB=x|xAxB A和B的差，或B关于A的相对补，记为AB,是集合 AB =x|xAx B,6.2 集合的运算,6.2 集合的运算,例：设A= a,b,c， B =b,c,d，求AB， AB ， AB 。解 AB=a,b,cb,c,d = a,b,c,d AB=a,b,cb,c,d
9、 = b,c AB =a,b,cb,c,d = a定义 设 A 与 B 是两个集合。若有AB =，那么称 A 和 B 是不相交的。如果C是一个集合的族，使C的任意两个不同元素（集合）都不相交，那么C是（两两）不相交集合的族。,定义：设A，B是两集合，集合(A-B)(B-A)称为集合A，B的对称差，记作AB。即 AB=x(xAxB)(xBxA)用图表示如下： A B 将AB中同时属于A，B的元素去掉定理 AB =（AB）-（AB）,6.2 集合的运算,定义. 设E是论述域而A是E的子集。A的（绝对）补，记为A，是集合 AEAx|xEx A=x A例：若 E= 1，2，3，4 和 A= 1，2 ，
10、 则 A = 3，4 若 E = N 且 A= x | x 0， 则 A= 0,6.2 集合的运算,例：A=xx-2,xR, E=xx2,xR 求：A，AA。解：A=xx2x-2 =x-2x2，xR AA= AA=(A-A)(A-A)= =,6.2 集合的运算,并和交运算的扩展设C是某论述域子集的集合，(a)C的成员的并，记为C，是由下式指定的集合 C=x | S(S C x S)(b)如果C，C的成员的交，记为C，是下式指定的集合 C=x | S(S C x S)定义说明：如果x C ，那么x至少是一个子集SC 的元素。如果x C ，那么x是每一个子集SC 的元素,注意： 对C的定义来说，C
11、必须非空，否则，由于C=，那么蕴含式 对于每一S将是无意义的真。 对每一x是真。因此所定义的集合就是E，是不正确的。,6.2 集合的运算,例：设论述域是实数R(a)如果C=1,2,4,3,4,5,4,6,那么 C=1,2,3,4,5,6， C=4,(b)我们用0, a)表示集合x|0xa如果Sa=0,a),aR+,C=Sa | aR+,那么 C=0,)， C=0,6.2 集合的运算,6.2 集合的运算,运算的优先权规定：一类运算：广义运算、幂集、绝对补运算，运算由右向左进行二类运算：并、交、相对补、对称差运算，优先顺序由括号决定一类运算优先于二类运算例 A=a,a,b，则 A(AA) = a,
12、b(a,ba) = (ab)(ab)a) = (ab)(ba) = b,6.3 集合恒等式,设 A,B,C,D是论述域E的任何子集，于是有:幂等律 AA = A AA = A 结合律 (A B) CA ( B C) (A B) CA (B C)交换律 ABBA ABBA分配律 A(BC)= (AB) (AC) A(BC)= (AB) (AC),同一律 A = A AE= A 零律 AE = E A= 排中律 AAE矛盾律 AA吸收律 A(AB)= A A(AB)= A德摩根定律 A- (BC)=(A-B) (A-C) A- (BC)=(A-B) (A-C) (BC)= BC (BC)=BC E
13、 E双重否定律 (A)=A,6.3 集合恒等式,A B A A B B A AB B AB A-B A A-B=ABAB=B A B A B =A A-B= AB = BA(AB)C=A(BC)A=A AA=AB=ACB=C,6.3 集合恒等式,例： 证明ABA B证：对任意的x，x(AB) xA x B xA x B x A B 所以ABA B,6.3 集合恒等式,例： 如果A B和C D，那么(AC) (BD)证明：设x是属于(AC)的任意元素， 那么xA xC，现分情况证明：如果xA，因为A B，所以xB 所以x BD；如果xC，因为C D，所以xD 所以x BD因此，如果x AC，那么
14、x BD所以有 (AC) (BD),6.3 集合恒等式,证明： AB=B A B A B =A A-B= 证明:先证AB=B A B。对任意x，xA xA x B xABxB所以A B 再证A B A B =A ，显然A B A ， 对任意x，xA xA x A xA x B xA B 所以A B =A,6.3 集合恒等式,再证：A B =A A-B= AB A B (A B ) B A (BB)= 再证： A-B= AB=B因为(A-B)B=AB,而A-B= AB=B,6.3 集合恒等式,6.3 集合恒等式,证明： AB = AC AB = AC B = C,解题思路分析命题：含有3个命题：
15、 AB = AC , AB = AC, B = C 证明要求 前提：命题和 结论：命题 证明方法： 恒等式代入 反证法 利用已知等式通过运算得到新的等式,6.3 集合恒等式,方法一：恒等式代入 B = B(BA) = B(AB) = B(AC) = (BA)(BC) = (AC)(BC) = (AB)C = (AC)C = C,方法二：反证法假设 B C，则存在 x (xB且xC), 或存在 x (xC且xB) 不妨设为前者. 若x属于A，则x属于AB 但x不属于AC，与已知矛盾；若x不属于A，则x属于AB但x不属于AC，也与已知矛盾,6.3 集合恒等式,方法三：利用已知等式通过运算得到新的等
16、式由已知等式和可以得到 (AB) (AB) = (AC) (AC)即 AB = AC 从而有 A(AB) =A(AC) 根据结合律得 (AA)B = (AA) C 由于AA = , 化简上式得B = C.,6.3 集合恒等式,设A, B为集合，试确定下列各式成立的充分必要条件：(1) AB=B(2) AB=BA(3) AB=AB(4) AB=A,6.3 集合恒等式,解题思路: 求解集合等式成立的充分必要条件可能用到集合的算律、不同集合之间的包含关系、以及文氏图等. 具体求解过程说明如下： (1) 化简给定的集合等式 (2) 求解方法如下：利用已知的算律或者充分必要条件进行判断先求必要条件，然后
17、验证充分性利用文氏图的直观性找出相关的条件，再利用集合论的证明方法加以验证,6.3 集合恒等式,(1) AB=B AB=B A=B=. 求解过程如下： 由AB=B得 (AB)B = BB 化简得B=. 再将这个结果代入原来的等式得A= . 从而得到必要条件A=B=.再验证充分性. 如果A=B=成立，则AB=B也成立.,(2) AB=BA AB=BA A=B. 求解过程如下：充分性是显然的，下面验证必要性. 由AB=BA得 (AB)A=(BA)A从而有A=AB, 即BA. 同理可证AB.,6.3 集合恒等式,(3) AB=AB AB=AB A=B. 求解过程如下：充分性是显然的，下面验证必要性. 由AB=AB得 A(AB) = A(AB)化简得A =AB，从而有BA. 类似可以证明AB.,(4) AB=A AB=A B=. 求解过程如下：充分性是显然的，下面验证必要性. 由AB = A得 A(AB) = AA根据结合律有 (AA)B = AA即 B = , 就是B = .,作业,812143046（1），（2），（6）,
