第三章集合备课讲稿.doc

第三章集合备课讲稿 第三章集合3.1集合论基础3.2集合运算及其性质3.3集合的笛卡儿积与无序积退出3.1集合论基础1.集合与元素所谓集合，是指某些可辨别的不同对象的全体，将用大写字母A，B，X，Y，表示之。 组成集合的对象称为集合的元素或成员，将用小写字母a，b，x，y表示之。 a是A的元素或a属于A，记作a?A；a不属于A或a不是A的元素，记作a?A，或者?(a?A)。 集合的元素一旦给定，这一集合便完全确立。 这一事实被形式地叙述为外延公理。 外延公理两集合A和B相等，当且仅当它们有相同的元素。 若若A与B相等，记为A=B；否则，记为A?B。 外延公理可形式表为A=B?(?x)(x?A?x?B)或者A=B?(?x)(x?A?x?B)?(?x)(x?B?x?B)顺便指出，在应用外延公理证明集合A与B相等时，只需考察对于任意元素x，应有下式x?B?x?B成立即可。 这就是说，证明两集合相等时可按此法行事。 二是谓词法，用谓词公式来确定集合。 即个体域中能使谓词公式为真的那些元素，确定了一个集合，因为这些元素都具有某种特殊性质。 若P(x)含有一个自由变元的谓词公式，则x|P(x)定义了集合S，并可表为S=x|P(x)由此可见，P(c)为真当且仅当c?S。 从而有x?S?x?P(x)例如， (1)可表为A=x|x是英文字母表中元音字母在用性质来描述集合时，可表述为概括原理或子集合公理。 子集公理对于任给集合A和性质P，存在集合B，使得得B中元素恰为A中满足P的那些元素。 子集公理可形式地表为(?B)(?x)(x?B?x?A?(x)其中?(x)为不含B自由出现。 子集公理的提出，避免了悖论，使集合论得以存在和发展。 应该指出的是集合并不决定于它的元素展示方法。 集合的元素被重复或重新排列，集合并不改变，即a,a,e,i,o,u=a,u,e,o,i。 但有时对重复出现的元素都认为是集合的元素，这种集合称为多重集。 即a,a,e,i,o,u,u?a,e,i,o,u。 本书中集合在不特别指明时，都指前者，即中的集合。 集合的元素可以是具体事物，可以是抽象概念，也可以是集体，不是集合的元素称为本元。 如，一本书，一支笔，集合1,2,3可以组成集合B=一本书，一支笔，1,2,3。 特别地，以集合为元素的集合称为集合族或集合类如如A=1,2,3,8,9,6。 集合中元素之间可以有某种关联，也可以彼此毫无关系。 2.子集、全集与空集子集是描述一个集合与另一个集合之间的关系，其定义如下。 定义3.1.1设A和B是任意两个集合，如果集合A的每个元素，都是集合B中的一个元素，则称A是B的子集，或称A被包含于B中中，或者说B包含A，并记为A?B。 本定义也可表成A?B?(?x)(x?A?x?B)这表明，要证明A?B，只需对任意元素x，有下式x?A?x?B成立即可。 此外，若集合B不包含集合A，记为A?B。 /定义3.1.2设A和B是两个集合，若A?B且且A?B，则称A是B的真子集，记为A?B，也称B真包含A。 该定义也可表为A?B?(A?B?A?B)定义3.1.3如果一个集合包含了所要讨论的每一个集合，则称该集合为全集，记为U或E。 它可形式地表为U=x|P(x)?P(x)其中P(x)为任何谓词公式。 显然，全集U即是第二章中的全总论域。 于是，每个元素x都属于全集U，即命题(?x)(x?U)为真。 由定义易知，对任意集合A，都有A?U。 在实际应用中，常常把某个适当大的集合看成全集U。 定义3.1.4没有任何元素的集合，称为空集，记为?，它可形式地表为?=x|P(x)?P(x)其中P(x)为任何谓词公式。 由定义可知，对任何集合A，有?A。 这是因为任意元素x，公式x?x?A总是为真。 注意，?与?是不同的。 ?是以?为元素的集合，而?没有任何元素，能用?构成集合的无限序列 (1)?，?，?，该序列除第一项外，每项均以前一项为元素的集合。 (2)?，?，?，?，该序列除第一项外，每项均以前面各项为元素的集合。 它即是冯诺依曼在1924年使用空集?给出自然数的集合表示0:=?，1:=?，2:=?,?，定理3.1.1空集是唯一的定理3.1.2()对任一集合A，有A?A。 ()若A?B且B?C，则A?C。 3集合的基数表示集合中元素多少或度量集合大小的数，称作集合的基数或势。 一个集合A的基数，记为|A|。 如果一个集合恰有m个不同的元素，且且m是是某个非负整数，称该集合是有限的或有穷的，否则称这个集合为无限的或无穷的。 例如，在本书中常用有穷集有N m=0,1,2,m-1本书中常见的无穷集合有N=0,1,2,3,，即自然数集合。 Z=,-2,-1,0,1,2,3,，即整数集合。 Z+=1,2,3,，即正整数集合。 Q=有理数集合。 R=实数集合。 C=复数集合。 4集合的幂集一个集合的幂集是指该集合所有子集的集合，即是由这些子集所组成的集合族。 定义3.1.5设A为一集合，A的幂集是一集合族，记为P(A)，P(A)=B|B?A由定义可知，?P(A)，A?P(A)。 5文氏图氏文氏(Venn)图是一种利用平面上的点构成的图形来形象展示集合的一种方法。 全集U用一个矩形的内部表示，其他集合用矩形内的园面或一封闭曲线圈成的面积来表示。 如果A?B，则表示A的圆面一般将完全落在表示B的圆面内，如图1中(a)。 如果A与B没有公共元素，那么表示A的圆面将同表示B的圆面分开，如图3-1中(b)。 当A和B是两个任意的集合时，可能会是有些元素在A中但不在B中，有些元素在B中却不在A中，有些元素同时在A和和B中，有些元素则既不在A中也不在B中，因此用图1中(c)表示任意两个集合A和B。 图图3-1最后给出集合的形式定义结束本节。 定义3.1.6A为集合=(?x)(x?A?A=?)。 这里等号“=”表示定义为的意义，是表示“定义为”还是表示“一般相等”的意义，由上下文来区分。 3.2集合运算及其性质集合运算是指用已知的集合去生成新的集合。 假设所有集合都是全集U的子集，即这些集合是利用子集公理得到的。 下面依次介绍常见的集合运算。 1并、交和差运算定义3.2.1设A和B是任意两个集合，A和B的并是集合，记为AB，AB=x|x?A?x?BA和B的交是集合，记为AB，AB=x|x?A?x?BA和B的差，或B关于A的相对补是集合，记为A-B，A-B=x|x?A?x?B定义3.2.2若A和B是集合，且且AB=?，则称称A和B是不相交的。 如果C是个集合族，且且C中任意两个不同元素都不相交，则称C中集合是两个不相交的，或称称C是两两不相交的集合族。 定理3.2.1任给集合A，B和C，则AB=BAAB=BA(AB)C=A(BC)(AB)C=A(BC)该定理表明，集合并和交运算满足交换律和结合律。 定理3.2.2任给集合A、B和C，则A(BC)=(AB)(AC)A(BC)=(AB)(AC)该定理表明，集合运算并对交、交对并都是可分配的。 定理3.2.3任给集合A，B，C和D，则若A?B，则则AB=B，AB=A若A?B和C?D，则则AC?BD，AC?BD推论3.2.3AU=U，AU=A定理3.2.4任给集合A，B和C，则A-(BC)=(A-B)(A-C)A-(BC)=(A-B)(A-C)定义3.2.3设A是含有元素为集合的集合，或者集合族。 A的并是集合，记为A，A=x|(?B)(B?A?x?B)=BA的交是集合，记为A，A=x|(?B)(B?A?x?B)=B B?A B?A定义3.2.4集合A的补是集合，记为A，A=U-A=x|x?U?x?A=x|x?A定理3.2.5任给集合A，则则AA=U，AA=?。 定理3.2.6任给集合A和B，则则B=Aiff AB=U且AB=?该定理表明了若若A的补是B，则则B的补是A，即即A和B互补。 补的唯一性。 推论3.2.5U=?，?=U定理3.2.7任给集合A，则则A”=A。 该定理表明了，A的补的补是A。 定理3.2.8任给集合A和B，则则(AB)=AB，(AB)=AB。 定义3.2.5任给集合A和B，A和B的对称差是集合，记为A?B，A?B=(A-B)(B-A)=x|(x?A?x?B)?(x?B?x?A)定理3.2.9任给集合A和B，则则A?B=(AB)(AB)=(AB)-(AB)推论3.2.9A?B=A?BA?B=B?AA?A=?2集合代数与对偶原理本小节将形式地讨论由集合、集合变元、集合运算和圆括号所构成的集合代数以及集合代数中的对偶原理。 与命题逻辑相似，对于给定集合实行集合运算，可以生成新的集合。 同用大写英文字母表示确定集合一样，也用大写字母表示不确定的集合，前者称为集合常元，后者称为集合变元。 集合变元用以集合常元代替后，才表示确定的集合。 下面将给出集合的合式公式定义。 定义3.2.6可按下列规则生成集合合式公式单个集合变元是集合合式公式。 若A是集合合式公式，则A也是集合合式公式。 若A和B是集合合式公式，则(AB)，(AB)，(A-B)和(A?B)也都是集合合式公式。 只有有限次使用、和构成的符号串才是集合合式公式。 为方便计，简称集合合式公式为公式。 定义3.2.7用任意集合常元取代两个集合公式中的各个集合变元，若所得集合是相等的，则称该二集合公式是相等的，简称等式。 因为集合公式相等，不依赖于取代集合变元的集合，故常称这些等式为集合恒等式，或集合定律。 它们刻划了集合运算的某些性质，这些性质描述一个代数，称为集合代数。 下面列出常用集合定律（ （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 AU=A（ （6）零律AU=U A?=?（ （7）补律AA=U AA=?（ （8）吸收律A(AB)=A A(AB)=A（ （9）德德摩根律(AB)=AB(AB)=AB（ （10）对合律(A)=A下面介绍集合代数中的对偶原理，它与命题逻辑中对偶原理也很相似。 对偶原理设E是集合代数中等式，将E中中的，U和?的每一个出现分别代以，?和U后得到一等式E*，称称E*为为E的对偶式。 显然，E也是E*的对偶式，即E与E*互为对偶。 如果E是一集合恒等式，则E*也是一集合恒等式。 可见，上述的集合定律中，凡成对的定律都是为对偶的。 3.3集合的笛卡尔积与无序积笛卡尔积与无序积在后面讨论关系和图论时，都有重要应用。 首先引入有序对和无序对的概念。 定义3.3.1两个元素a,b组成二元组，若它们有次序之别，称为二元有序组，或有序对，记为，称称a为第一分量，b为第一分量；若它们无次序区分，称为二元无序组，或无序对,记为(a,b)。 若若a?b时时，?。 但但(a,b)=(b,a)。 定义3.3.2给定两个有序对和。 当且仅当x=u和y=v时，有序对和相相等，亦即=iff(x=u)?(y=v)可将有序对推广到n元有序组，它的第一分量是(n-1)元有序组，并记为，或记为。 类似地定义两个n元有序组相等=iff(x1=y1)?(x2=y2)?(x n-1=y n-1)?(x n=y n)下面将使用有序对和无序对分别定义笛卡儿积和无序积。 定义3.3.3给定集合A和B，若有序对的第一分量是A的元素，第二分量是B的元素，所有这些有序对的集合，称为A和B的笛卡尔积，记为为A?B，A?B=|x?A?y?B定义3.3.4给定集合A和B，若无序对是由A中元素和B中元素组成，所有这些无序