集合代数复习进程

1、集合代数1、集合的描述定义、集合的描述定义 所谓所谓集合集合，是指某些可辨别的不同对象的全体，是指某些可辨别的不同对象的全体，将用大写字母将用大写字母A，B，X，Y，表示之。表示之。 组成集合的对象称为集合的组成集合的对象称为集合的元素元素或成员，将用小或成员，将用小写字母写字母a，b，x，y 表示之。表示之。 a是是A的元素或的元素或a属于属于A，记作记作a A； a不是不是A的元素或的元素或a不属于不属于A，记作，记作a A，或者，或者 (a A)。2、集合的表示：、集合的表示：表示一个特定集合，基本上有表示一个特定集合，基本上有两种方法：两种方法：枚举法枚举法：列出集合的所有元素，元素之

2、间用：列出集合的所有元素，元素之间用逗号分开，再用花括号括起。如：逗号分开，再用花括号括起。如：A= a, e, i, o, u 表明集合表明集合A是由字母是由字母 a, e, i ,o和和u为元素为元素构成的。构成的。谓词法谓词法：用：用谓词公式谓词公式来确定集合。即个体域中来确定集合。即个体域中能使谓词公式为真的那些元素，确定了一个集能使谓词公式为真的那些元素，确定了一个集合。因为这些元素都具有某种特殊性质。若合。因为这些元素都具有某种特殊性质。若P(x)含有一个自由变元的含有一个自由变元的谓词公式谓词公式，则，则x|P(x)定义了集合定义了集合S，并可表为：，并可表为：S=x|P(x)

3、由此可见，由此可见，P(c)为真当且仅当为真当且仅当 c S。 从而有从而有 x S P(x)=T集合的元素是彼此不同的。集合的元素是彼此不同的。如：如：1，1，2，2，31，2，3集合的元素是无序的集合的元素是无序的。 如：1，2，33，1，2 元素和集合之间的关系是隶属关系元素和集合之间的关系是隶属关系，属于属于记作 ，不属于不属于记作 。如：Aa，b，c，d，d 这里 aA，b，cA，dA，dA，但 bA，dA。 可以用一种树形图来表示这种可以用一种树形图来表示这种隶属关系隶属关系，该图分层构，该图分层构成，成，每个层上的结点都表示一个集合，它的儿子就是每个层上的结点都表示一个集合，它的

4、儿子就是它的元素。它的元素。上例中集合上例中集合 Aa，b，c，d，d 的树形图如图所示。的树形图如图所示。图中的图中的a，b，c，d也是集合，也是集合，由于所讨论的问题与由于所讨论的问题与a，b，c，d的元素无关，所以没有列出它的元素无关，所以没有列出它们的元素。鉴于们的元素。鉴于集合的元素是集合的元素是集合集合这一规定，这一规定，隶属关系隶属关系可以可以看作是处在不同层次上的集合看作是处在不同层次上的集合之间的关系。之间的关系。可形式表为可形式表为： A=B ( x)(x Ax B)或者A=B ( x)(x Ax B)( x)(x Bx A) 顺便指出，在应用外延公理证明集合顺便指出，在应

5、用外延公理证明集合A与与B相等时，只需考察：相等时，只需考察： 对于任意元素对于任意元素x，应有：，应有：x Ax B 成立即可。这就是说，成立即可。这就是说，证明两集合相等时可按证明两集合相等时可按此法行事此法行事。子集子集是描述一个集合与另一个集合之间的关是描述一个集合与另一个集合之间的关系，其定义如下系，其定义如下: 设设A和和B是任意两个集合，如果集是任意两个集合，如果集合合A的每个元素，都是集合的每个元素，都是集合B中的一个元素，中的一个元素，则称则称A是是B的的子集子集，或称，或称A被被包含于包含于B中，或中，或者说者说 B包含包含A，并记为，并记为A B。二、集合之间的关系二、集

6、合之间的关系集合包含的符号化表示：集合包含的符号化表示：A B ( x)(x Ax B)表明：要证明表明：要证明A B，只需对任意元素，只需对任意元素x，有下式，有下式x Ax B成立即可。成立即可。如果如果A B且且B A，则称，则称A与与B相等，记作相等，记作AB。若集合若集合B不包含集合不包含集合A，记为，记为A B。 设设A和和B是两个集合，若是两个集合，若A B且且A B，则称，则称A是是B的的真子集真子集，记为，记为A B，也，也称称B真包含真包含A。该定义也可表为。该定义也可表为A B (A BA B)如果如果A不是不是B的真子集，则记作的真子集，则记作A B。 如果一个集合包含

7、了所要讨论的如果一个集合包含了所要讨论的每一个集合，则称该集合为每一个集合，则称该集合为全集全集，记为，记为 E。它可形式地表为它可形式地表为E = x|P(x)P(x)其中：其中：P(x)为任何谓词公式。为任何谓词公式。 显然，显然，全集全集E即是第二章中的即是第二章中的全总个体域全总个体域。于是，每个元素于是，每个元素 x 都属于全集都属于全集 E，即命题，即命题( x)(x E)为真。为真。由定义易知，对任意集合由定义易知，对任意集合A，都有，都有A E。在实际应用中，常常把某个适当大的集合看在实际应用中，常常把某个适当大的集合看成全集成全集 E。全集是有相对性的。全集是有相对性的。 不

8、含任何元素的集合，称为不含任何元素的集合，称为，记作记作，它可形式地表为：，它可形式地表为：= x|P(x)P(x) 其中：其中：P(x)为任何谓词公式。为任何谓词公式。由定义可知，对任何集合由定义可知，对任何集合A，有，有A。这是。这是因为任意元素因为任意元素x，公式，公式xx A总是为真。总是为真。(2) ， ， ， ，该序列除第一项外，每项均以前面各项为元素的该序列除第一项外，每项均以前面各项为元素的集合。它即是集合。它即是在在1924年使用空集年使用空集给出给出自自然数然数的集合表示：的集合表示：0:=，1:= ，2:= , ， 空集是一切集合的子集。空集是一切集合的子集。 空集是唯一

9、的。空集是唯一的。 () 对任一集合对任一集合A，有，有A A。() 若若A B且且B C，则，则A C。三、集合的基数三、集合的基数 表示集合中元素多少或度量集合大小的数，称作表示集合中元素多少或度量集合大小的数，称作集合的集合的或势。一个集合或势。一个集合A的基数，记为的基数，记为|A|。 如果一个集合恰有如果一个集合恰有m个不同的元素，且个不同的元素，且m是某个是某个非负整数，称该集合是非负整数，称该集合是有限的有限的或或有穷的有穷的，否则称这，否则称这个集合为个集合为无限的无限的或或无穷的无穷的。 例如：例如： Nm=0,1,2,m-1为含为含m个元素的有穷集。个元素的有穷集。N =

10、0, 1, 2, 3, ，即自然数集合。，即自然数集合。Z = , -2, -1, 0, 1, 2, 3, ，即整数集合。，即整数集合。Z+ = 1, 2, 3, ，即正整数集合。，即正整数集合。Q = 有理数集合。有理数集合。R = 实数集合。实数集合。C = 复数集合。复数集合。四、集合的幂集四、集合的幂集 一个集合的幂集是指以该集合所有子集为元素的一个集合的幂集是指以该集合所有子集为元素的集合，即是由这些子集所组成的集合族。集合，即是由这些子集所组成的集合族。 设设A为一集合，为一集合，A的的是一集合族，记是一集合族，记为为 (A)， (A) = B|B A 由定义可知，由定义可知， (

11、A)，A (A)。任给一个任给一个n元集，怎样求出它的全部子集？元集，怎样求出它的全部子集？ (A)有有2n个元素。个元素。五、文氏图五、文氏图 文氏文氏(Venn)图是一种利用平面上的点构图是一种利用平面上的点构成的图形来形象展示集合的一种方法。成的图形来形象展示集合的一种方法。 全集全集E用一个矩形的内部表示，其他集用一个矩形的内部表示，其他集合用矩形内的园面或一封闭曲线圈成的面积合用矩形内的园面或一封闭曲线圈成的面积来表示。来表示。如果如果A B，则表示，则表示A的圆面一般将完全落在表示的圆面一般将完全落在表示B的圆面的圆面内，如图中内，如图中(a)。如果如果A与与B没有公共元素没有公共

12、元素，那么表示，那么表示A的圆面将同表示的圆面将同表示B的的圆面分开，如图中圆面分开，如图中(b)。当当A和和B是两个是两个任意的集合任意的集合时，可能会是：有些元素在时，可能会是：有些元素在A中但不在中但不在B中，有些元素在中，有些元素在B中却不在中却不在A中，有些元素同中，有些元素同时在时在A和和B中，有些元素则既不在中，有些元素则既不在A中也不在中也不在B中，因此用中，因此用图中图中(c)表示任意两个集合表示任意两个集合A和和B。集合运算是指用已知的集合去生成集合运算是指用已知的集合去生成新新的集合。的集合。假设所有集合都是假设所有集合都是全集全集E的子集，即这些集的子集，即这些集合是利

13、用子集公理得到的。下面依次介绍常合是利用子集公理得到的。下面依次介绍常见的集合运算。见的集合运算。 设设A和和B是任意两个集合，是任意两个集合， A和和B的的并并是集合，记为：是集合，记为：AB，AB = x | x A x B A和和B的的交交是集合，记为：是集合，记为：AB，AB = x | x A x B A和和B的的差差，或，或B关于关于A的的是集合，记为：是集合，记为：A B，A B = x | x A x B 一、并、交和差运算一、并、交和差运算 若若A和和B是集合，且是集合，且AB=，则，则称称A和和B是是不相交不相交的。的。 如果如果C是个是个集合族集合族，且，且C中任意两个不

14、同元素中任意两个不同元素都都不相交不相交，则称，则称C中的集合是互不相交的，或中的集合是互不相交的，或称称C是是两两不相交的集合族两两不相交的集合族。 任给集合任给集合A，B和和C，则：，则： AB=BA AB= BA (AB)C=A(BC) (AB)C=A(BC)该定理表明，集合该定理表明，集合并并和和交交运算满足运算满足交换律交换律和和结结合律。合律。 任给集合任给集合A、B和和C，则，则 A(BC)=(AB)(AC) A(BC)=(AB)(AC)该定理表明，集合运算该定理表明，集合运算并对交并对交、交对并交对并都是都是可分配可分配的。的。 任给集合任给集合A，B，C和和D，则，则 若若A

15、 B，则，则AB=B，AB=A 若若A B和和C D， 则则AC BD，AC BD AE=E，AE=A 任给集合任给集合A，B和和C，则，则 A (BC)=(A B)(A C) A (BC)=(A B)(A C) 集合集合A的补是集合，记为的补是集合，记为 A， A=E A=x|x Ex A=x|x A 任给集合任给集合A，则，则 A A=E， A A=。 任给集合任给集合A和和B，则，则B= A iff AB=E 且且 AB=该定理表明了若该定理表明了若A的补是的补是B，则，则B的补是的补是A，即即A和和B互补。补的唯一性。互补。补的唯一性。 E=， =E 任给集合任给集合A，则，则A=A。

16、该定理表明了，该定理表明了，A的补的补是的补的补是A。 任给集合任给集合A和和B，则，则 (AB)= A B， (AB)= A B。 任给集合任给集合A和和B，A和和B的的对称差对称差是是集合，记为集合，记为A B， A B =(A B)(B A)=x|(x Ax B)(x Bx A) 任给集合任给集合A和和B，则，则A B=(AB)( A B)=(AB) (AB) A B=A B A B=B A A A= A=A集合之间的关系和运算可以用文氏图集合之间的关系和运算可以用文氏图给予形象的描述给予形象的描述 二、集合代数与对偶原理二、集合代数与对偶原理 这里将形式地讨论由集合、集合变元、集合运算

17、这里将形式地讨论由集合、集合变元、集合运算和圆括号所构成的和圆括号所构成的以及集合代数中的以及集合代数中的。 与命题逻辑相似，对于给定集合实行集合运算，与命题逻辑相似，对于给定集合实行集合运算，可以生成可以生成的集合。同用大写英文字母表示确定集合的集合。同用大写英文字母表示确定集合一样，也用大写字母表示不确定的集合，前者称为一样，也用大写字母表示不确定的集合，前者称为集集合常元合常元，后者称为，后者称为集合变元集合变元。集合变元用以集合常元。集合变元用以集合常元代替后，才表示确定的集合。下面将给出集合的合式代替后，才表示确定的集合。下面将给出集合的合式公式定义。公式定义。 可按下列规则生成可按

18、下列规则生成： 单个集合变元是集合合式公式。单个集合变元是集合合式公式。 若若A是集合合式公式，则是集合合式公式，则A也是集合合式公式。也是集合合式公式。 若若A和和B是集合合式公式，则是集合合式公式，则(AB)，(AB)，(A B)和和(A B)也都是集合合式公式。也都是集合合式公式。 只有有限次使用、和构成的符号串才是集只有有限次使用、和构成的符号串才是集合合式公式。合合式公式。 简称集合合式公式为简称集合合式公式为。 用任意集合常元取代两个集合公式用任意集合常元取代两个集合公式中的各个集合变元，若所得集合是相等的，则中的各个集合变元，若所得集合是相等的，则称该两个集合公式是称该两个集合公

19、式是相等相等的，简称等式。的，简称等式。因为集合公式相等，不依赖于取代集合变元的因为集合公式相等，不依赖于取代集合变元的集合，故常称这些等式为集合，故常称这些等式为，或，或。它们刻划了集合运算的某些性质，。它们刻划了集合运算的某些性质，这些性质描述一个代数，称为这些性质描述一个代数，称为。下。下面列出常用面列出常用：（1）等幂律等幂律 AA=A AA=A（2）结合律结合律 (AB)C=A(BC) (AB)C=A(BC)（3）交换律交换律 AB=BA AB=BA（4）分配律分配律 A(BC)=(AB)(AC) A(BC)=(AB)(AC)（5）同一律同一律 A=A AE=A（6）零律零律AE=E

20、 A=（7）补余律补余律 AA=E AA=（8）吸收律吸收律 A(AB)=A A(AB)=A（9）德德摩根律摩根律 (AB)= AB (AB)= AB（10）双重否定律双重否定律 A=A一、有限集基数的有关结果一、有限集基数的有关结果设设A A、B B为任意有限集合，则有为任意有限集合，则有|AB| |A|+|B|-|AB| |AB| |A|+|B|-|AB| |AB|min(|A|,|B|)|AB|min(|A|,|B|)|A|A B|=|A|+|B|-2|AB|B|=|A|+|B|-2|AB|A-B|A|-|B| |A-B|A|-|B| (|A-B|+|B|=|AB|A|) (|A-B|+

21、|B|=|AB|A|) 任给集合任给集合A和和B，则，则 | |AB| = |A| |B| |AB|当当AB= ，则有，则有 |AB|=|A|+|B|。当当AB，则，则 |A| = |A(B B)| = |A B|+|AB| |B| = |B A|+|BA| |A|+|B| = |A B|+| AB|+|AB|+|AB| = |AB|+|AB| |AB| = |A|+|B|-|AB| 例：例：设某班有设某班有60名同学，其中班足球队员有名同学，其中班足球队员有28名，篮球队员有名，篮球队员有15名。若有名。若有25名同学没有名同学没有参加这二个队，问同时参加这二个队的队员参加这二个队，问同时参

22、加这二个队的队员有多少名？有多少名？解：解：设设A A为足球队员集合，为足球队员集合，B B为篮球队员集合，为篮球队员集合，则则 |AB|=60-25=35|AB|=60-25=35， |AB|=|A|+|B|-|AB|=28+15-35=8 |AB|=|A|+|B|-|AB|=28+15-35=8二、包含二、包含n n个集合的包含排斥原理个集合的包含排斥原理|A|A1 1AA2 2AAn n|=|= i=1n A Ai i - - 1ijn1ijn A Ai iAAj j + + 1ijkn1ijkn A Ai iAAj jAAk k + + (-1) (-1)n-1n-1 A A1 1AA

23、2 2AAn n 特别地，特别地，n=3n=3， |A|A1 1AA2 2AA3 3|=|A|=|A1 1|+|A|+|A2 2|+|A|+|A3 3|-|A|-|A1 1AA2 2|-|-|A|A1 1AA3 3|-|A|-|A2 2AA3 3|+|A|+|A1 1AA2 2AA3 3| |证明：证明：当当n=2时，结论成立。时，结论成立。设设n-1n-1时，结论成立，则时，结论成立，则|A|A1 1AA2 2AAn n| |=|=|i=1i=1n-1n-1A Ai i|+|A|+|An n|-|(|-|(i=1i=1n-1n-1A Ai i)A)An n| |= = i=1i=1n n A

24、 Ai i - - 1ijn-11ijn-1A Ai iAAj j+(-1)+(-1)n-2n-2|i=1i=1n-1n-1A Ai i|-|- I=1I=1n-1n-1A Ai iAAn n- - 1ijn-11ijn-1A Ai iAAj jAAn n+ + (-1) (-1)n-2n-2|i=1i=1n-1n-1A Ai iAAn n|= = i=1i=1n n A Ai i - - 1ijn1ijnA Ai iAAj j+(-1)+(-1)n-1n-1|i=1i=1n nA Ai i| |例：例：试决定在试决定在1到到100之间能被之间能被2，3，5中某一数整除的中某一数整除的数的个数

25、。数的个数。解：解：A1表示表示1到到100之间能被之间能被2整除的整数集，整除的整数集， A2表示表示1到到100之间能被之间能被3整除的整数集，整除的整数集， A3表示表示1到到100之间能被之间能被5整除的整数集，整除的整数集， 则则 |A1|=int(100/2)=50，|A2|=int(100/3)=33， |A3|=int(100/5)=20， |A1A2|=int(100/(2*3)=16， |A1A3|=int(100/(2*5)=10， |A2A3|=int(100/(3*5)=6 |A1A2A3|=int(100/(2*3*5)=3所以所以|A1A2A3|=|A1|+|A2

26、|+|A3|-|A1A2|-|A1A3|- |A2A3|+|A1A2A3|=50+33+20-16-10-6+3=74 笛卡尔积与无序积在后面讨论关系和图论时，都笛卡尔积与无序积在后面讨论关系和图论时，都有重要应用。有重要应用。 首先引入首先引入有序对有序对和和无序对无序对的概念。的概念。 由两个具有固定次序的元素由两个具有固定次序的元素a, b组成的组成的叫叫序偶序偶，并记作，并记作，其中：称，其中：称a为第一元为第一元素，素，b为第二元素。若它们无次序区分，称为二元无为第二元素。若它们无次序区分，称为二元无序组或序组或无序对无序对，记为，记为(a, b)。注：注：若若a b时，时， 。但。

27、但(a, b) = (b, a)。 两个序偶相等两个序偶相等 iff 例：例： 已知已知，求：求：x和和y。解：解：由有序对相等的充要条件有由有序对相等的充要条件有 x+252x+y4 解得解得 x3, y-2。 序偶的概念可进一步推广：三元组、四元组、序偶的概念可进一步推广：三元组、四元组、n元组：元组：1、三元组三元组是一个序偶，其第一元素是是一个序偶，其第一元素是序偶序偶，记作：，记作：注：注： 据定义：据定义： = , z , z x, 2、n元组元组：一个有序：一个有序n元组元组(n3)是一个有序对，其中第一元是一个有序对，其中第一元素是一个有序素是一个有序n-1元组元组，记作，记作

28、 即即 =,xn注：注： ,xn x1, = iff (x1=y1)(x2=y2)(xn-1=yn-1)(xn=yn) 设设A、B是任意两个集合，则由第是任意两个集合，则由第一元素属于一元素属于A，第二元素属于，第二元素属于B的所有序偶构的所有序偶构成的集合，叫做集合成的集合，叫做集合A和和B的笛卡尔积，记为的笛卡尔积，记为AB，即，即AB=|x Ay B1、假设、假设A表示某大学所有学生的集合，表示某大学所有学生的集合，B表示大学开设表示大学开设的所有课程的集合，的所有课程的集合，则则AB可用来表示该校学生选课的所有可能情况。可用来表示该校学生选课的所有可能情况。2、令、令A是直角坐标系中是

29、直角坐标系中x轴上的点集，轴上的点集，B是直角坐标系是直角坐标系中中y轴上的点集，轴上的点集，则则AB就与平面点集一一对应。就与平面点集一一对应。 3、设设A=a,b, B=0,1,2，则，则AB=,BA=, 若若|A|=n，|B|=m，则，则 |AB|=n m。笛卡尔积运算的性质：笛卡尔积运算的性质： B = A = 当当A B且且A、B均不空时，有均不空时，有AB BA (AB)C A(BC) 笛卡尔积对笛卡尔积对、满足分配律满足分配律 A CB D AB CD 任给集合任给集合A，B和和C，则，则 A(BC)=(AB)(AC) A(BC)=(AB)(AC) (AB)C=(AC)(BC)

30、(AB)C=(AC)(BC) A(BC)=(AB)(AC)的证明的证明任取任取 A(BC) xA yBC xA (yByC) (xAyB) (xAyC) AB AC (AB)(AC) A(BC)=(AB)(AC) 若若C ，则，则A B (AC BC) (CA CB)设设A、B、C、D为四个为四个非空非空集合，集合，则则AB CD 的充要条件为的充要条件为A C，B D。 该性质的该性质的不成立，可分以下情况讨论。不成立，可分以下情况讨论。（1）当）当A=B=时，显然有时，显然有A C 和和 B D 成立。成立。（2）当）当A且且B时，也有时，也有A C和和B D成立。成立。任取任取xA，由于，由于B，必存在，必存在yB，因此有，因此有 xAyB AB CD xCyD xC从而证明了从而证明了 A C。同理可证同理可证 B D。该性质的该性质的不成立，可分