《《数学集合论》ppt课件》由会员分享，可在线阅读，更多相关《《数学集合论》ppt课件（142页珍藏版）》请在金锄头文库上搜索。
1、集合论(Set Theory)是现代数学的基础它的起源可追溯到16世纪末，但集合论实际发展是由 19世纪 70年代德国数学家康托尔(G . Cantor) 在无穷序列和分析的有关课题的理论研究中创立的. 集合论在计算机科学、人工智能领域、逻辑学及语言学等方面都有着重要的应用对于从事计算机科学的工作者来说，集合论是不可缺少的理论知识，熟悉和掌握它是十分必要的,第3章 集合、关系与映射,3.1 集合的基本概念,一、集合的概念 把具有相同性质的所有对象汇集在一起就称为一个集合. 把组成集合的对象称为元素。,例如： 方程x210的实数解集合； 26个英文字母的集合； 坐标平面上所有点的集合；,二、集合
2、的表示,一般用带下角标或不带下角标的大写字母表示集合，如 A, B, P1, P2, Q1, Q2等; 一般用带标号或不带标号的小写字母表示集合，如 a, b, c, a1, a2,等;,3.1 集合的基本概念,三、说明集合的方法,（1）列举法：如A=1,2,3,4，B0,2,4,6,8,10,（2）描述法：如A=x|P(x),P(x)是元素x所具有的性质。 例：A=x|x2-5x+6=0,（3）特定的字符集：在集合中常约定： N表示自然数集合；I(或Z)表示整数集合； Q表示有理数集合；R表示实数集合； E表示偶数集合； O表示奇数集合； P表示素数集合； F表示分数集合； C表示复数集合；
3、 R表示正实数集合； R*表示非零实数，即R*=x|xRx0;,（4）图示法：用封闭曲线表示集合，封闭曲线内的点 表示集合中的元素,3.1 集合的基本概念,注意： 集合的元素是确定的，即对集合A，任一元素a或属于此集合(aA)或不属于此集合(aA) ，两者必居其一。 集合中的每个元素均不相同。 即集合 1,2,2,3,4,4 = 1,2,3,4 (3) 集合中的元素是无序的。 例：4,3=3,4,3.1 集合的基本概念,包含关系： 若集合B中的每个元素都是A中的元素，称B包含于A或A包含B，称集合B是集合A的一个子集记为 BA : (x)(xBxA) 如果B不被A包含，则记作B A。 例如：N
4、ZQRC，但Z N。,3.1 集合的基本概念,四、集合间的关系：相等关系和包含关系,结论：对任何集合A都有A A,A。,例如： Aa，a和a的关系为 a A ，又有 aA,若B是A的子集且在A中存在不属于B的元素，则称 集合B是集合A的一个真子集，记为 BA : BA(x)(xAxB ，称A真包含于B。,3.1 集合的基本概念,例如：N Z Q R C,相等关系： 若集合A的任一元素都是集合B中的元素并且集合B 中的元素也是集合A中元素，则称这两个集合相等， 记为AB :(x)(aA aB) 或 AB : (AB)(BA) 否则称这两个集合不相等，记为A B,3.1 集合的基本概念,五、子集具
5、有的性质： AA 自反性 ABBAAB 反对称性 ABBCA C 传递性 证明: 这里仅给出的证明, 余下类似可证 ABBA (x)(xAxB)(x)(xBxA) (x)(xAxB)(xBxA) (x)(xAxB) AB,3.1 集合的基本概念,不包含任何元素的集合称为空集。记为 例如：A=x|x2-1, xR 对任何集合A， A 全集U：所有集合都是U的子集。,3.1 集合的基本概念,六、集合的运算,交运算： AB := x|xAxB ,3.1 集合的基本概念,并运算： AB: x|xAxB ,3.1 集合的基本概念,两个集合的并和交运算可以推广成n个集合的并和交： A1A2Anx|xA1x
6、A2xAn A1A2Anx|xA1xA2xAn,六、集合的运算,3.1 集合的基本概念,并和交运算还可以推广到无穷多个集合的情况： ,A1A2 ,A1A2,差运算： BA : x|xBxA,3.1 集合的基本概念,全集U：所有集合都是U的子集。 补集：全集U与集合A的差集称为A的补集， 记为 UA=x|x A,A,U,3.1 集合的基本概念,对称差运算： AB:= x|x(AB)x(BA) ,AB,3.1 集合的基本概念,显然： AA AB BA ABA AU,图形表示集合间的关系文氏图(Venn Digram表示),U,A, B,3.1 集合的基本概念,AB,交换律 ABBA ； ABBA
7、结合律 A(BC)=(AB)C A(BC)=(AB)C 分配律 A(BC)=(AB) (AC) A(BC)=(AB)(AC) 4. 吸收律 A(AB)=A ； A(AB)=A De Mergam律 幂等律 AAA ; AAA 补余律 零律 A AUU 壹律 AUA AA 互补律 重非律,集合运算的算律：设A,B,C是任意三个集合。,定理：设A, B, C, D是任意三个集合。 （1） 若A B，则ABA ；ABB； (BA)AB （2） AB A, B; A, B AB （3） 若A B且C D；则AC BD ； AC BD （4） 若AB ；则称A，B不相交；若还有ABU， 则称A，B为互补
8、。 （5）若A B，则,（6） A(BC)(AB)(AC) ； A(B C) (AB) (AC) (7) A (BC)(A B) (A C) 但 A (BC) (AB) (AC),幂集：由集合A的所有子集组成的集合称为A的幂集。 记为P(A)或2A 即P(A):B|BA,例如：Aa P(A)=,a A=a,b P(A)=,a,b,a,b A=,a P(A)=,a,a,设Aa1,a2,an,则A的子集B的二进制编码为： 若aiB，则ai记为1，否则记为0，i1,2,n. 按此规定得到的一个二进制数称为集合B的编码。,设|A|=n,则P(A)= 2n,集合的应用求若干有限集合并的元素个数。,定理：
9、设A1，A2是两个有限集合， 记|A1|, |A2|为它们所含的元素个数， 则|A1A2|= |A1|+|A2| A1A2|,例1：假设某班有50名学生，其中英语成绩为优的25名，数学成绩为优的20名，又有15名学生数学和英语成绩均为优。问这两门课都不是优的学生有几名？,解：英语成绩为优的学生组成的集合是A；|A|=25 数学成绩为优的学生组成的集合是B；|B|=20 因此这两门可成绩均为优的学生组成的集合是AB； | AB |=15 所以 | AB |=|A| +|B| AB |=25201530， 这说明两门课中至少有一门课为优的学生是30名， 所以这两门课都不是优的学生有503020名,
10、例2：求出在1和90之间(包括90)能被2，3，5 任一 数整除的整数个数。,解：设A1，A2，A3分别为表示1和90之间能被2，3，5 任一数整除的整数集合。,所以 在1和90之间(包括90)能被2，3，5 任一数整除 的整数个数为66。,3.2 关 系,定义1（笛卡尔积或直乘积） 设A，B是任意两个集合， AB|xA, yB 称为集合A和B的笛卡尔积或直乘积。 称为有序对或序偶对，x称为序偶对的第一 个元素，y称为序偶对的第二个元素。 = iff a=x且b=y,例：A=a,b，B=1,2,3，C=x 则 AB, BA, , , , ,结论：设 |A|=n, |B|=m, 则 | AB |
11、=nm,3.2 关 系,(AB)C,x,x,x, ,x,x,x,结论： (AB)C A(BC),A(BC), ,笛卡儿积运算的性质: 1. 若A，B中有一个空集,则它们的笛卡儿积是空集, 即 AA A 2. 当AB且A,B都不是空集时,有 ABBA。 所以,笛卡儿积运算不满足交换律。 3. 当A,B,C都不是空集时,有 (AB)CA(BC). 所以,笛卡儿积运算不满足结合律。,定理1(笛卡儿积运算对或运算满足分配律,即) 设A, B, C是任意三个集合；则 A(BC) = (AB)(AC) /对具有左分配律 A(BC) = (AB)(AC) /对具有左分配律 (AB)C= (AB)(AC) /
12、对具有右分配律 (AB)C= (AB)(AC) /对具有右分配律,3.2 关 系,证明： A(BC)=(AB)(AC) /对具有左分配律 令x, y为分别属于集合A和集合BC的任意元素, 则 A(BC) xAy(BC) xA(yByC) (xAyB)(xAyC) AB AC (AB)(AC) 所以： A(BC)=(AB)(AC),3.2 关 系,定理2：设A, B, C，D是任意四个集合；则 若AB且CD，则ACBD,规定： AAA A,记为AnAn-1A 例：A1,2 A3=A2A= 1,22 1,2 = ,1, ,2, ,1,2, ,1, ,2, ,1, ,2,3.2 关 系,定义2（二元
13、关系） 设A, B是任意两个集合，则AB的任一子集称为从A到B的 二元关系(简称关系)，记为R，显然R AB， 若R，则称x和y有关系R，记为xRy; 否则R，则称x, y没有关系，记为xRy 若AB，则称关系R是集合A上的一个二元关系，即RA2； R| xA, 称R为A上的恒等关系，记为IA； 若R，则称R为空关系，记为A； 若RAAA2，则称R为全域关系，记为UA； 设|A|=n, 则A2的序偶对一共有n2个，A上的二元关系一共有,3.2 关 系,例1：A=a,b, B=1,2,3 则R1,是一个从A到B的(二元)关系。 同理 R2, 也是一个从A到B的(二元)关系。,例2：A=a, b,
14、 c, 则 IA,是一个A上的恒等关系。 UA ,是一个A上的全域关系。,3.2 关 系,定理：若R1和R2是A上的关系，则 R1R2， R1R2， R1R2也是A上的关系。,3.2 关 系,证明：因为R1和R2是A上的关系，则R1 A2， R2 A2 所以R1R2 A2； R1R2 A2； R1R2 A2； 故 ，R1R2， R1R2， R1R2， 也是A上的关系。,定义3 设R是从集合A到B的一个关系，称 domRx|(y)(R) 为R的定义域。 romRy|(x)(R) 为R的值域。,3.2 关 系,例：R,的 domR=a,b romR=1,2,3,关系的表示,矩阵法,图形法,3.2 关 系,矩阵法： 设两个有限集合 A=x1, x2, ,
