第三章--集合与关系课件

第二编第二编 集合论集合论 集合论是研究集合的一般性质的数学集合论是研究集合的一般性质的数学分支。分支。在现代数学中，每个对象（如数、函在现代数学中，每个对象（如数、函数等）本质上都是集合，都可以用某种集数等）本质上都是集合，都可以用某种集合来定义。数学的各个分支，本质上都是合来定义。数学的各个分支，本质上都是在研究这种或那种对象的集合的性质。集在研究这种或那种对象的集合的性质。集合论已成为全部现代数学的理论基础。合论已成为全部现代数学的理论基础。第二编第二编 集合论集合论 集合论的特点是研究对象的广泛性。集合论的特点是研究对象的广泛性。它总结出由各种对象构成的集合的共同性质，它总结出由各种对象构成的集合的共同性质，并用统一的方法来处理。因此，集合论被广并用统一的方法来处理。因此，集合论被广泛地应用于各种科学和技术领域。泛地应用于各种科学和技术领域。第二编第二编 集合论集合论 由于集合论的语言适合于描述和研究由于集合论的语言适合于描述和研究离散对象及其关系，所以也是计算机科学离散对象及其关系，所以也是计算机科学与工程的理论基础，在程序设计、关系数与工程的理论基础，在程序设计、关系数据库、排队论、开关理论，形式语言和自据库、排队论、开关理论，形式语言和自动机理论等学科领域中都有重要的应用。动机理论等学科领域中都有重要的应用。本篇主要介绍：集合、二元关系和函数，本篇主要介绍：集合、二元关系和函数，以及集合的基数问题。以及集合的基数问题。第三章第三章 集合与关系集合与关系 3.1 集合概念和表示集合概念和表示3.2 集合的运算集合的运算3.3 序偶与笛卡尔积序偶与笛卡尔积3.4 关系及其表示关系及其表示3.5 关系的性质关系的性质3.6 复合关系和逆关系复合关系和逆关系3.7 关系的闭包运算关系的闭包运算 3.8集合划分和覆盖集合划分和覆盖3.9等价关系与等价类等价关系与等价类3.10相容关系相容关系3.11序关系序关系第三章第三章 集合与关系集合与关系 教学目的及要求教学目的及要求：深深刻刻理理解解和和掌掌握握有有关关集集合合和和关关系系的的基基本本概概念念和和基基本本运运算。算。教学内容教学内容：集集合合的的概概念念与与表表示示、集集合合的的运运算算、序序偶偶与与笛笛卡卡尔尔积积、关关系系及及表表示示、关关系系的的性性质质、复复合合关关系系和和逆逆关关系系、关关系系的闭包运算、等价关系与等价类、序关系。的闭包运算、等价关系与等价类、序关系。教学重点教学重点：关系及关系的运算、等价关系、序关系。：关系及关系的运算、等价关系、序关系。教学难点教学难点：关系的闭包运算、等价关系、等价类。：关系的闭包运算、等价关系、等价类。3.1 集合的概念和表示法集合的概念和表示法1、集合与元素、集合与元素（1）集合）集合：具有某种特殊性质的客体的聚合。：具有某种特殊性质的客体的聚合。讨论：讨论：一些不同的确定的对象之全体。一些不同的确定的对象之全体。客体：是泛指一切，可以是具体的、抽象的客体：是泛指一切，可以是具体的、抽象的元素（成员）：属于任何集合的任何客体。元素（成员）：属于任何集合的任何客体。符号：符号：用大写英文字母用大写英文字母A，B.表示集合，用小表示集合，用小写英文字母写英文字母a，b.或其它符号表示元素。或其它符号表示元素。元素与集合间的关系：元素与集合间的关系：a是集合是集合S中的元素，则写中的元素，则写成成a S；b不是集不是集S合中的元素，则写成合中的元素，则写成b S。3.1 集合的概念和表示法集合的概念和表示法集合集合S的基数的基数(势势)：S中的元素个数。用中的元素个数。用|S|表示。表示。有限集合：集合的基数（元素）是有限的。有限集合：集合的基数（元素）是有限的。无限集合：集合的基数（元素）是无限的。无限集合：集合的基数（元素）是无限的。本书中常用集合符本书中常用集合符:Im(m1)有限个正数的集合有限个正数的集合1,2,3m Nm(m0)有限个自然数的集合有限个自然数的集合0,1,2m 以上是有限集合以上是有限集合,下面是无限集合：下面是无限集合：3.1 集合的概念和表示法集合的概念和表示法N 自然数集合自然数集合 0,1,2I+正整数集合正整数集合 1,2,3I 整数集合整数集合 -1,0,1,2P 素数集合素数集合 大于大于1的正整数，只能被的正整数，只能被1和自己和自己整除整除Q 有理数集合有理数集合 i/j|i、j均为整数且均为整数且j0R 实数集合实数集合 有理数、无理数有理数、无理数C 复数集合复数集合 a+bi|a、b可为实数可为实数,i=3.1 集合的概念和表示法集合的概念和表示法(2)集合的表示方法集合的表示方法:(a)枚举法枚举法(列举法列举法)把集合的元素列于花括号内。把集合的元素列于花括号内。例：例：命题的真假值组成的集合：命题的真假值组成的集合：S=T,F 自然数自然数0,1,2,3,4五个元素的集合：五个元素的集合：P=0,1,2,3,4(b)谓词公式描述法谓词公式描述法 所有集合均可用谓词公式来表示：所有集合均可用谓词公式来表示：S=x|p(x)3.1 集合的概念和表示法集合的概念和表示法 例：例：大于大于10的整数的集合：的整数的集合：S1=x|x I x10 偶整数集合：偶整数集合：S2=x|y(y I x=2y)有限个元素集合：有限个元素集合：S3=1,2,3,4,5=x|x I (1 x 5)S4=F,T=x|x=T x=F S5=1,4=x|(x-5x+4=0)(c)同一集合可以用多种不同的形式表示。同一集合可以用多种不同的形式表示。(d)集合也可作为某一集合的元素。集合也可作为某一集合的元素。例：例：S=a,1,2,p,q 3.1 集合的概念和表示法集合的概念和表示法(3)三个特殊集合三个特殊集合 全集全集:如果一个集合包含了所要讨论的每一个集如果一个集合包含了所要讨论的每一个集合，则称该集合为全集合，简称全集，用合，则称该集合为全集合，简称全集，用E表示。表示。E=x|p(x)p(x)p(x)为任何谓词公式为任何谓词公式 空集空集:不拥有任何元素的集合称为空集（或称零不拥有任何元素的集合称为空集（或称零 集），用集），用表示表示,=x|p(x)p(x)=注意注意,前者是空集，是没有元素的集合；前者是空集，是没有元素的集合；后者是以后者是以作为元素的集合。作为元素的集合。集合族集合族:集合中的元素均为集合，称这样的集集合中的元素均为集合，称这样的集合为集合族。例合为集合族。例A=a，b，c、d3.1 集合的概念和表示法集合的概念和表示法2、集合之间的关系、集合之间的关系 相等相等:给定二个集合给定二个集合A和和B，当且仅当，当且仅当A和和B具具有同样的元素（成员），则有同样的元素（成员），则A和和B相等，记作相等，记作A=B,并规定并规定：（：（A=B）x(x A x B)例：例：a,b,c=b,a,a,c,c 例：设例：设P=1,2,4，Q=1,2,4，则，则P Q3.1 集合的概念和表示法集合的概念和表示法 包含包含:设设A、B是任意二个集合，如果集合是任意二个集合，如果集合A的的每一个元素都是每一个元素都是B的一个元素，则称的一个元素，则称A是是B的的子集，或者说子集，或者说A包含于包含于B，或者说，或者说B包含包含A，记，记作作 A B，或者，或者B A。并规定：。并规定：A BB Ax(x A x B)例：例：A1=1,2,3 A2=0 A3=1,2,3,0 B=1,2,3,0 则则A1、A2、A3均为均为B的子集合，并记为的子集合，并记为 A1 B，A2 B，A3 B3.1 集合的概念和表示法集合的概念和表示法真包含真包含:设设A、B是任意二个集合，若是任意二个集合，若A B且且AB，则称，则称 A是是B的真子集，记作的真子集，记作A B（A真真包含于包含于B）,并规定：并规定：A B（A B AB）注意区分注意区分“”和和“”的关系：的关系：“”关系是指集合和该集合中元素间的关系。关系是指集合和该集合中元素间的关系。例：例：S=a,b,c 则则a S，b S，c S 而而“”关系是指二个集合之间的关系。关系是指二个集合之间的关系。例：例：S1=a,b S2=a,b,1,2 则则S1 S2 若若A不包含于不包含于B，则也可表示成，则也可表示成A B3.1 集合的概念和表示法集合的概念和表示法 定理定理 设设E是全集，是全集，A是一个集合，则一定有是一个集合，则一定有A E。证明：证明：x（x A x E）而而x E始终为始终为“T”，所以所以x A x E一定为一定为“T”故有故有 x（x A x E）为）为“T”，则有，则有A E3.1 3.1 集合的概念和表示法集合的概念和表示法 定理定理 设设A、B是任意二个集合，当且仅当是任意二个集合，当且仅当A B和和B A 才有才有A=B。证明：证明：()充分性充分性：（：（A=B）（A B B A）(A=B)x(x A x B x B x A)x(x A x B)x(x B x A)(A B)(B A)()必要性必要性：A B B AA=B (A B)(B A)x(x A x B)x(x B x A)(A=B)3.1 集合的概念和表示法集合的概念和表示法推论推论对于任一集合对于任一集合A，则有，则有A A。定理定理设设A、B、C是任意集合，如果是任意集合，如果A B和和B C，则，则A C。推论推论若若A B和和B C，则，则A C。3.1 集合的概念和表示法集合的概念和表示法 定理定理 设有空集设有空集和任一集合和任一集合A，则，则A证明：设证明：设x A，要证明，要证明A，只要证：，只要证：（x）(x x A)为为“T”中没有元素，中没有元素，x为假，（为假，（x）（）（x x A）为）为“T”定理定理 是唯一的。是唯一的。证明：设有二个空集合证明：设有二个空集合1和和2 是任何集合的子集是任何集合的子集（1 2 2 1）(1=2)3.1 集合的概念和表示法集合的概念和表示法3、幂集和索引集合、幂集和索引集合（1）幂集：）幂集：例：例：S1=a 则子集为则子集为，a S2=1，2 则子集为则子集为，1，2，1，2 S3=则子集有则子集有（而不是（而不是）由此可见由此可见,给定一个集合给定一个集合S,则则和和S一定是一定是S的子集。的子集。3.1 集合的概念和表示法集合的概念和表示法 幂集幂集:设设A是集合，是集合，A的所有子集（作为元素）的所有子集（作为元素）的集合称为的集合称为A的幂集的幂集,记作记作(A)或或2A,且有：且有：(A)(=2A)=x|x A 例：例：若若A1=，则，则(A1)=若若A2=a，则，则(A2)=，a 若若A3=1，2,则则(A3)=，1，2，1，2 3.1 集合的概念和表示法集合的概念和表示法讨论：讨论：(a)集合的元素个数称为集合的集合的元素个数称为集合的“基数基数”或叫或叫“势势”|(S)|=2|s|为幂集为幂集(S)的基数的基数(b)若若A为有限集合，则为有限集合，则(A)也为有限集合。也为有限集合。若若A为无限集合，则为无限集合，则(A)也为无限集合。也为无限集合。(c)一定有一定有A(A)，(A)，即对非空集合，即对非空集合，在幂集中至少有两个子集在幂集中至少有两个子集和和A。3.1 集合的概念和表示法集合的概念和表示法（2）索引集合）索引集合 为了在计算机上表示集合，必须给每一个集合的为了在计算机上表示集合，必须给每一个集合的元素加上标记，以用来表示元素在集合中的位置。元素加上标记，以用来表示元素在集合中的位置。例：例：S1=a，b 假设集合假设集合S1中，中，a,b的位置已经固定。的位置已经固定。则用二进制下标法来表示则用二进制下标法来表示S的所有子集：的所有子集：=B=B0000，a=Ba=B1010，b=Bb=B0101，aa，b=Bb=B1111这样这样(S1)=B(S1)=B0000，B B0101，B B1010，B B1111=B=Bi i|i|i J J 而其中而其中J=00J=00，0101，1010，1111（索引集合或指标集合（索引集合或指标集合）3.1 集合的概念和表示法集合的概念和表示法例：例：已知集合已知集合S=a1，a2，a3，a4，a5，a6，S的子集有的子集有26 个个,可以分别表示成可以分别表示成B0，B1B(26-1)则则B7=B000111=a4，a5，a6 B15=B001111=a3，a4，a5，a6 B22=B010110=a2，a4，a5等等等等3.2 集合的运算集合的运算 1.交集交集（交运算）（交运算）交集交集:二个集合二个集合A和和B的交集的交集AB是由是由A和和B所共有的所共有的全部元素构成的集合，即：全部元素构成的集合，即：AB=x|x A x B 例：例：A=a，b B=a，c AB=a 定理定理 集合的相交运算是可交换的和可结合的，即集合的相交运算是可交换的和可结合的，即对于任何集合对于任何集合A，B，C有有 AB=BA，（，（AB）C=A（BC）证明：设证明：设x是是AB中任一元素中任一元素 则则x ABx x|x A x Bx x|x B x Ax BA AB=BA 3.2 集合的运算集合的运算 定理定理 设设A是是E的任一子集，则有的任一子集，则有 （1）AA=A （2）A=（3）AE=A不相交不相交:A、B是二个集合，若是二个集合，若AB=，则称，则称A和和B 是不相交的，或者说是不相交的，或者说A和和B没有相同的元素。没有相同的元素。若若C是一个集合族是一个集合族（集合族：元素均为集合（集合族：元素均为集合 的集合）使的集合）使C的任何二个元素都不相交，则的任何二个元素都不相交，则 称称C为不相交的集合族。为不相交的集合族。例：例：A=a，b，c A为不相交的集合族为不相交的集合族 3.2 集合的运算集合的运算2.并集（并运算）并集（并运算）定义定义 A、B是任意二个集合，是任意二个集合，A和和B的并集的并集A B是是 由由A和和B的所有元素构成的集合，即：的所有元素构成的集合，即：A B=x x A x B。例：例：A=a,b,c B=1,2,3 则则 A B=a,b,c,1,2,3 定理定理 集合的并运算是可交换的和可结合的，即对集合的并运算是可交换的和可结合的，即对 任何任何A，B，C,有有 A B=B A和（和（A B）C=A（B C）3.2 集合的运算集合的运算 定理定理 集合的并和交运算，每一个对另一个都是可集合的并和交运算，每一个对另一个都是可 分配的。即：分配的。即：(1)A（BC）=（A B）（A C）(2)A（B C）=（AB）（AC）定理定理 设设A、B、C是全集是全集E的任意子集，则有：的任意子集，则有：(1)A A=A (2)A=A (3)A E=E3.2 集合的运算集合的运算3.相对补集：相对补集：定义定义 设设A和和B是二个任意集合，是二个任意集合，B对对A的相对补的相对补 集（集（A-B）是由）是由A中且不属于中且不属于B的所有元素的所有元素 组成的集合。即：组成的集合。即：A-B=xx A x B=xx A x B例：设例：设A=0，1，2 B=2，3，4 则则 A-B=0,1 B-A=3，4注意，注意，A-BB-A。3.2 集合的运算集合的运算 定理定理 设设A，B，C，D是是E的子集，则有：的子集，则有：(1)A-B A，(2)若若A B和和C D，则，则AC BD，(3)若若A B和和C D，则，则A C B D，(4)若若A A B，则，则 B A B (5)若若AB A，则，则AB B (6)若若A B，则，则A B=B (7)若若A B，则，则AB=A (8)A-=A (9)A(B-A)=(10)A(B-A)=A B3.2 集合的运算集合的运算 (11)A-（B C）=（A-B）（A-C）(12)A-（BC）=（A-B）（A-C）4、绝对补集（补运算、绝对补集（补运算）定义定义 设设E是全集，任一集合是全集，任一集合A对对E的相对补集称的相对补集称 为为A的绝对补集（或称补集）记作的绝对补集（或称补集）记作A（或（或 A）。即：）。即：A=E-A=x|x E x A=x|x A例：设例：设E=a，b，c，d A=a，b 则则 A=c，d 3.2 集合的运算集合的运算 定理定理 A是是E的任一子集，则有的任一子集，则有 (1)A A=E (2)A A=定理定理 设设A、B是是E的二个子集，当且仅当的二个子集，当且仅当 A B=E和和AB=才有才有B=A（或（或A=B）证明：证明：()充分性：充分性：B=A（A B=E）（AB=）B=A A B=A A=E AB=AA=成立成立3.2 集合的运算集合的运算()必要性：必要性：(A B=E)(AB=)B=A B=EB=(A A)B =(AB)(AB)=（AB）=（AA）（AB）=A（A B）=AE=A 3.2 集合的运算集合的运算补集的性质：补集的性质：（1）（A）=A（2）（A B）=AB（3）（AB）=A B（4）=E（5）A-B=AB 例：设例：设A=2，5，6，B=2，3，4，C=1，3，4，E=1，2，3，4，5，6则则A-B=5，6=AB =2，5，61，5，6=5，63.2 集合的运算集合的运算5、环和、环和(对称差对称差)定义定义 设设A、B是任意二集合，是任意二集合，A和和B的环和记作的环和记作 AB。即：。即：AB=(A-B)(B-A)=(AB)(BA)或者或者x(AB)x x|x A x B 例：设例：设A=2，5，6，B=2，3，4 则则 A B=3，4，5，6 3.2 集合的运算集合的运算对称差的性质：对称差的性质：(1)A B=B A (可交换可交换)(2)(A B)C=A(B C)(可结合可结合)(3)A B=(A-B)(B-A)=(AB)(BA)=(A B)(A B)(4)A A=(5)A=A(6)A B=(A(B)(B(A)=(AB)(BA)=(B-A)(A-B)=A B(7)A(B C)=(AB)(AC)(对对 可分配可分配)3.2 集合的运算集合的运算6、文氏图、文氏图(1)文氏图的画法规则：文氏图的画法规则：规定矩形表示规定矩形表示E。子集用圆画在。子集用圆画在E中。中。(2)文氏图应用：文氏图应用：（a）表示集合和运算的关系）表示集合和运算的关系 可用文氏图画出各种运算：可用文氏图画出各种运算：（b）证明集合恒等式）证明集合恒等式例：例：A（B C）=（A B）（A C）3.3 序偶与笛卡尔乘积序偶与笛卡尔乘积 1.序偶：序偶：定义定义3-4.1 由两个具有给定次序的客体所组成的序列由两个具有给定次序的客体所组成的序列称为序偶。记作称为序偶。记作x，y例：例：XY二维平面上点的坐标二维平面上点的坐标x，y就是序偶。就是序偶。说明：在序偶中二个元素要有确定的排列次序。即：说明：在序偶中二个元素要有确定的排列次序。即：若若a b时，则时，则a，b b，a 若若x，y=a，b（x=a y=b）下面定义多重序元：下面定义多重序元：三重序元三重序元=x,y,z n重序元重序元=x1，x2,x3,xn 3.3 序偶与笛卡尔乘积序偶与笛卡尔乘积2.笛卡尔乘积笛卡尔乘积定义定义3-4.2设设A，B为二个任意集合，若序偶的第一为二个任意集合，若序偶的第一个成员（左元素）是个成员（左元素）是A的一个元素，序偶的第二的一个元素，序偶的第二个成员（右元素）是个成员（右元素）是B的一个元素，则所有这样的一个元素，则所有这样的序偶的集合称为的序偶的集合称为A和和B的笛卡尔乘积（直积）。的笛卡尔乘积（直积）。记作：记作：A B=x，y|（x A）（y B）例：设例：设A=1，2 B=a，b 则则A B=,2,b B A=,A B B A 即即“”是不满足交换律。是不满足交换律。3.3 序偶与笛卡尔乘积序偶与笛卡尔乘积例：设例：设A=a，b，B=1，2，C=z 则则 (A B)C=,z =,A (B C)=a,b 1,z,2,z =a,a,b,b,（A B）C A（B C）“”不满足结合不满足结合律。律。3.3 序偶与笛卡尔乘积序偶与笛卡尔乘积定理定理3-4.1若若A，B，C是三个集合，则有：是三个集合，则有：(1)A（B C）=（A B）（A C）(2)A（B C）=（A B）（A C）(3)（A B）C=（A C）（B C）(4)（A B）C=（A C）（B C）证明：（证明：（2）设设是是A(B C)中的任一元素中的任一元素,则则 A（B C）x,y|x A y B C|x A y B y C3.3 序偶与笛卡尔乘积序偶与笛卡尔乘积|(x A y B)(x A y C)(A B)(A C)即即 A(B C)=(A B)(A C)例：设例：设A=1，B=1，2，C=2，3 则则A（B C）=1 1，2，3 =1，1，1，2，1，3 p经常不断地学习,你就什么都知道。你知道得越多,你就越有力量pStudyConstantly,AndYouWillKnowEverything.TheMoreYouKnow,TheMorePowerfulYouWillBe写在最后感谢聆听不足之处请大家批评指导Please Criticize And Guide The Shortcomings结束语讲师：XXXXXX XX年XX月XX日