离散数学集合论部分PPT讲稿.ppt

离散数学集合论部分离散数学集合论部分第1页，共192页，编辑于2022年，星期日 对于从事计算机科学工作的人们来说，集合对于从事计算机科学工作的人们来说，集合论是必不可少的基础知识。例如程序设计语言、论是必不可少的基础知识。例如程序设计语言、数据结构、形式语言等都离不开子集、幂集、集数据结构、形式语言等都离不开子集、幂集、集合的分类等概念。集合成员表和范式在逻辑设计、合的分类等概念。集合成员表和范式在逻辑设计、定理证明中也都有重要应用。定理证明中也都有重要应用。本部分从集合的直观概念出发，介绍了集本部分从集合的直观概念出发，介绍了集合论中的一些合论中的一些基本概念基本概念和和基本理论基本理论。第2页，共192页，编辑于2022年，星期日 集合论是研究集合的一般性质的数学分集合论是研究集合的一般性质的数学分支支，它研究集合不依赖于组成它的事物的，它研究集合不依赖于组成它的事物的特性的性质。集合论总结出由各种对象构特性的性质。集合论总结出由各种对象构成的集合的共同性质，并用统一的方法来成的集合的共同性质，并用统一的方法来处理。处理。集合论的特点是研究对象的广泛性，集合论的特点是研究对象的广泛性，集合是各种不同对象的抽象，这些对象可集合是各种不同对象的抽象，这些对象可以是数或图形，也可以使任意其它事务。以是数或图形，也可以使任意其它事务。第3页，共192页，编辑于2022年，星期日1.1.二十六个英文字母可以看成是一个集合；二十六个英文字母可以看成是一个集合；2.2.所有的自然数看成是一个集合；所有的自然数看成是一个集合；3.3.重庆邮电大学计算机学院重庆邮电大学计算机学院20102010级的本科学生可以看成是一级的本科学生可以看成是一个集合；个集合；4.4.这间教室中的所有座位可以看成是一个集合。这间教室中的所有座位可以看成是一个集合。例例:集合的基本概念集合的基本概念第4页，共192页，编辑于2022年，星期日组成一个集合的那些对象或单元称为这个集组成一个集合的那些对象或单元称为这个集合的元素。合的元素。通常，用小通常，用小写的英文字母写的英文字母a,b,c,表示表示集合中的元素。元素可以是单个的数字也可集合中的元素。元素可以是单个的数字也可以是字母，还可以是集合。以是字母，还可以是集合。如：如：A=a,c,b;B=a,b,c集合的元素集合的元素第5页，共192页，编辑于2022年，星期日元素与集合的属于关系：元素与集合的属于关系：设设A是一个集合，是一个集合，a是集合是集合A中的元素，中的元素，元素与集合元素与集合的关系：的关系：属于属于；不属于不属于 若若a是集合是集合A中的元素记为中的元素记为a A，读作，读作a属于属于A；若若a不是集合不是集合A中的元素，则记为中的元素，则记为a A，读作，读作a不属于不属于A。例如：例如：A是正偶数集合，则是正偶数集合，则2 A，4 A，6 A；而；而1 A，3 A，19 A。第6页，共192页，编辑于2022年，星期日特别注意：特别注意：集合并不决定于它的元素展示方法。集合的元素被重复集合并不决定于它的元素展示方法。集合的元素被重复或重新排列，集合并不改变，即或重新排列，集合并不改变，即a,a,b,c,d,c=a,b,c,d。集合的元素可以是具体事物，可以是抽象概念，也可集合的元素可以是具体事物，可以是抽象概念，也可以是集体，如一本书，一支笔；集合以是集体，如一本书，一支笔；集合1,2,3可以是集可以是集合合B=一本书，一支笔，一本书，一支笔，1,2,3的元素。特别地，的元素。特别地，以集合为元素的集合称为集合族或集合类如以集合为元素的集合称为集合族或集合类如A=1,2,3,8,9,6。集合中元素之间可以有某种关联，也可以彼此毫无集合中元素之间可以有某种关联，也可以彼此毫无关系。关系。第7页，共192页，编辑于2022年，星期日有限集有限集A中所含元素的个数称为集合的元数。中所含元素的个数称为集合的元数。记作：记作：|A|如：如：A=1,3,2,4,5,9则则|A|=6；设设A是所有英文字母组成的集合，则是所有英文字母组成的集合，则A=26。特别，特别，|=0集合的元素数集合的元素数第8页，共192页，编辑于2022年，星期日列举法列举法(列元素法列元素法)：将集合中的元素一一列举，将集合中的元素一一列举，或列出足够多的元素以反映集合中元素的特征，或列出足够多的元素以反映集合中元素的特征，例如：例如：V=a,b,c,d,e或或B=1,2,3,4,5,6,。描述法描述法(谓词表示法谓词表示法):将集合元素的条件或性质将集合元素的条件或性质用文字或符号在花括号内竖线后面表示出来。用文字或符号在花括号内竖线后面表示出来。A=x|关于关于x的一个命题的一个命题P;如：如：B=x|0 x10;B=x|x=a2,a是自然数是自然数。集合的表示法集合的表示法第9页，共192页，编辑于2022年，星期日EAae文氏图文氏图用一个大的矩形表示全集，在矩形内画一些圆或其它用一个大的矩形表示全集，在矩形内画一些圆或其它的几何图形，来表示集合，有时也用一些点来表示集合中的几何图形，来表示集合，有时也用一些点来表示集合中的特定元素。的特定元素。例如：例如：集合集合A=a,b,c,d,e，用，用文氏图文氏图表示如下表示如下:dcb第10页，共192页，编辑于2022年，星期日几类特殊集合几类特殊集合:N=0,1,2,3,，即自然数集合。，即自然数集合。Z=,-2,-1,0,1,2,3,，即整数集合。，即整数集合。Z+=1,2,3,，即正整数集合。，即正整数集合。Q=有理数集合。有理数集合。R=实数集合。实数集合。C=复数集合。复数集合。第11页，共192页，编辑于2022年，星期日确定性；确定性；互异性；互异性；无序性；无序性；多样性；多样性；集合的特征集合的特征第12页，共192页，编辑于2022年，星期日任何一个对象，或者是这个集合的元素，或者任何一个对象，或者是这个集合的元素，或者不是，二者必居其一；不是，二者必居其一；例如：例如：A=x|x是自然数，且是自然数，且x100；B=x|x+1=3；C=x|x是大学生是大学生。确定性确定性第13页，共192页，编辑于2022年，星期日 集合中任何两个元素都是不同的，即集合中集合中任何两个元素都是不同的，即集合中不允许出现重复的元素。不允许出现重复的元素。例如：例如：集合集合A=a,b,c,c,b,dA=a,b,c,c,b,d，实际，实际 上，应该是上，应该是A=a,b,c,dA=a,b,c,d。再如再如 1,2,3,2,4=1,2,3,4 1,2,3,2,4=1,2,3,4。互异性互异性第14页，共192页，编辑于2022年，星期日 集合与其中的元素的顺序无关；集合与其中的元素的顺序无关；例如：例如：集合集合a,b,c,d,e、d,c,e,a,b、e,c,d,b,a，都是表示同一个集合。，都是表示同一个集合。集合集合4,2,1,3=1,2,3,4。无序性无序性第15页，共192页，编辑于2022年，星期日集合中的元素可以是任意的对象，集合中的元素可以是任意的对象，相互独立，相互独立，不要求一定要具备明显不要求一定要具备明显的共同特征。的共同特征。例如：例如：A=a,a,a,b,a,1；A=1,a,*,-3,a,b,x|x是汽车是汽车,地球地球注意注意:对于任何集合对于任何集合A,都有都有A A。多样性多样性第16页，共192页，编辑于2022年，星期日设设A，B是两个集合，若是两个集合，若B的元素都是的元素都是A的元素，则称的元素，则称B是是A的的子集子集，也称，也称A包含包含B，或，或B被被A包含，记以包含，记以B A，或，或A B。若若B A，且，且A B，则称，则称B是是A的的真子集真子集，也称，也称A真真包含包含B，或，或B真包含于真包含于A，记以，记以A B，或，或B A。子集：子集：第17页，共192页，编辑于2022年，星期日例例3.1设设A=a,b,c,a,a,b试试判判断断下下列列表表达达式式正正确与否。确与否。（1）a A（2）a A（3）a A（4）A（5）A（6）b A（7）b A（8）b A（9）a,b A(10)a,b A(11)c A(12)c A(13)c A(14)a,b,c A。解解：(4)4)，(7)(7)，(11)(11)，(13),(14)(13),(14)错误。错误。第18页，共192页，编辑于2022年，星期日例例3.2对于任意集合对于任意集合A,B和和C,下述论断是否正确下述论断是否正确（1）若）若A B,B C则则A C（2）若）若A B,B C则则A C（3）若）若A B,B C则则A C解解：（：（1）（2）（3）对对(3)举反例举反例A=,B=1,C=1。第19页，共192页，编辑于2022年，星期日例例3.3设设A=1,2,3,4,5,6,7,8下列选项正确的是（下列选项正确的是（3）；）；（1）1 A（2）1,2,3 A（3）4,5 A（4）A例例3.4下列各选项错误的是（下列各选项错误的是（2）；）；（1）（2）（3）（4）例例3.5在在0_之间填上正确的符号：（之间填上正确的符号：（4）（1）=（2）（3）（4）第20页，共192页，编辑于2022年，星期日 当两个集合当两个集合A A和和B B的元素完全一样，即的元素完全一样，即A A，B B实际上是实际上是同一个集合时，则称集合同一个集合时，则称集合A A，B B相等，记为相等，记为A=BA=B。符号化表示为：符号化表示为：A=BA BB A例：例：设设A=x|x是偶数，且是偶数，且0 x10，B=2,4,6,8，则则A=B。集合相等集合相等第21页，共192页，编辑于2022年，星期日注：注：说明两个集合说明两个集合A、B相等，需说明两相等，需说明两个问题：个问题：1、A是集合是集合B的子集（的子集（A B）（任意元素（任意元素aA，有，有aB）2、B是集合是集合A的子集（的子集（A B）（任意元素（任意元素aB，有，有aA）第22页，共192页，编辑于2022年，星期日集合的包含关系也可表成集合的包含关系也可表成A B(x)(x Ax B)这表明，要证明这表明，要证明A B，只需对任意元素，只需对任意元素x，有下式有下式x Ax B成立即可。成立即可。第23页，共192页，编辑于2022年，星期日空集空集不含任何元素的集合叫做空集，记作不含任何元素的集合叫做空集，记作。空集的符号化表示为：空集的符号化表示为：=x|P(x)P(x)。其中其中P(x)为任何谓词公式。为任何谓词公式。如：如：A=x|xRx2+1=0。该方程无实数解。该方程无实数解。注意：注意：由定义可知，对任何集合由定义可知，对任何集合A，有，有A。这是因为任意元。这是因为任意元素素x，公式，公式xx A总是为真。总是为真。第24页，共192页，编辑于2022年，星期日注意：注意：与与是不同的。是不同的。是以是以为元素的集合，为元素的集合，而而没有任何元素，能用没有任何元素，能用构构成集合的无限序列：成集合的无限序列：，该序列除第一项外，每项均以前一项为元素的集合。该序列除第一项外，每项均以前一项为元素的集合。第25页，共192页，编辑于2022年，星期日定理：定理：空集是一切集合的子集。空集是一切集合的子集。证明：证明：对于任何集合对于任何集合A，由子集定义有，由子集定义有,A x(xxA)右边的蕴涵式中前件为右边的蕴涵式中前件为x为假，所以整个为假，所以整个蕴涵式蕴涵式对一切对一切x为真，所以为真，所以 A为真为真推论推论：空集是唯一的。：空集是唯一的。证明证明:如不唯一如不唯一,设存在空集设存在空集1和和2,由空集是一切由空集是一切集合的子集得集合的子集得1 2和和2 1。根据集合相等的定义得，。根据集合相等的定义得，1=2第26页，共192页，编辑于2022年，星期日全集：全集：如果一个集合包含了所要讨论的每一个如果一个集合包含了所要讨论的每一个集合，则称该集合为全集，记为集合，则称该集合为全集，记为E或或U。它可形式地表为它可形式地表为E=x|P(x)P(x)。其中。其中P(x)为任何谓词公式。为任何谓词公式。第27页，共192页，编辑于2022年，星期日注意符号注意符号 和和 意义的区别：意义的区别：表示元素与集合之间的关系，而表示元素与集合之间的关系，而 则表示集则表示集合与集合之间的关系。但由于集合的抽象性，集合与集合之间的关系。但由于集合的抽象性，集合中的元素可以是集合，故可以发生如：合中的元素可以是集合，故可以发生如：A B且且A B的情形的情形例例设设A=1,2,3,1,2,3，则则1,2,3 A且且1,2,3 A。注意：注意：第28页，共192页，编辑于2022年，星期日对任意集合对任意集合A,有有A A。空集是任意集合的子集，且空集是唯一的。空集是任意集合的子集，且空集是唯一的。对于任意两个集合对于任意两个集合A、B，A=B的充的充要条件是要条件是A B且且B A。（。（这个结论非常简单，但它非常重要，很多证明都这个结论非常简单，但它非常重要，很多证明都是用这个方法或思路来证明。）是用这个方法或思路来证明。）重要结论重要结论第29页，共192页，编辑于2022年，星期日设设A是集合，是集合，A的所有子集为元素做成的集合称为的所有子集为元素做成的集合称为A的的幂集幂集,记以记以P(A)符号化表示为：符号化表示为：P(A)=x|x A。例：例：A=a,b,c，则，则P(A)=,a,b,c,a,b,a,c,b,c,a,b,c。幂集幂集第30页，共192页，编辑于2022年，星期日例例3.6设设A=a,a下列选项错误的是下列选项错误的是A.a P(A)B.a P(A)C.a P(A)D.a P(A)例例3.7幂集幂集P(P(P()为（为（C）A.,B.,C.,D.,P(A)=P(A)=,a,a,a,a 第31页，共192页，编辑于2022年，星期日例例3.8判断下面的关系是否正确判断下面的关系是否正确,并简要说明理由。并简要说明理由。a,b a,b,c,a,b,ca,ba,b,c,a,b,ca,b a,b,a,ba,ba,b,a,b第32页，共192页，编辑于2022年，星期日解答解答：对选项对选项,因为因为a,b中每个元素中每个元素(只有只有a和和b)均在集均在集合合a,b,c,a,b,c对选项对选项,因为因为a,b中每个元素中每个元素(只有只有a和和b)均均在集合在集合a,b,a,b对选项对选项,集合集合a,b,c,a,b,c中含有中含有4个个元素，分别为元素，分别为a,b,c,a,b,c没有没有a,b，所以不正确。，所以不正确。对选项对选项,集合集合a,b,a,b中含有中含有3个元素，个元素，分别为分别为a,b,a,b没有没有a,b，所以不正确。，所以不正确。第33页，共192页，编辑于2022年，星期日1.若若A为有穷集，为有穷集，|A|=n，则，则|2A|=Cn0+Cn1+Cnn=2n。2.x P(A)当且仅当当且仅当x A。3.设设 A、B是是 两两 个个 集集 合合，A B当当 且且 仅仅 当当P(A)P(B)。幂集的性质幂集的性质第34页，共192页，编辑于2022年，星期日并并A B=x|x A x B；交交A B=x|x A x B；相对补相对补A B=x|x A x B；对称差对称差A B=(A B)(B A)=(A B)(A B)；绝对补绝对补 A=E A。3.2集合的基本运算集合的基本运算第35页，共192页，编辑于2022年，星期日 A B A A B A A B A B A-B A B A A B B C A B (A B)-C集合运算对应的文氏图表示集合运算对应的文氏图表示第36页，共192页，编辑于2022年，星期日并和交运算可以推广到有穷个集合上，即并和交运算可以推广到有穷个集合上，即A1 A2 An=x|x A1 x A2 x AnA1 A2 An=x|x A1 x A2 x An某些重要结果：某些重要结果：A B AA B A B=A B=A B=A第37页，共192页，编辑于2022年，星期日集合的广义交和广义并集合的广义交和广义并 设设S为集合，为集合，S的元素的元素构成的集合称为的元素的元素构成的集合称为S的的广义并广义并，记为，记为 S，其中，其中 S=xz(z S x z；设设S非空集合，非空集合，S的元素的公共元素构成的集的元素的公共元素构成的集合称为合称为S的广义交，记为的广义交，记为 S，其中，其中 S=xz(z Sx z。第38页，共192页，编辑于2022年，星期日说明：说明：（1 1）规定）规定 =，无意义。无意义。（2 2）若）若 ，则由定义不难证明，则由定义不难证明 S=S=S=S=（3 3）并运算和广义并运算的运算符相同，但前者是二元运算，）并运算和广义并运算的运算符相同，但前者是二元运算，后者是一元运算，因此在运算过程中不会对后者是一元运算，因此在运算过程中不会对 产生误解。产生误解。第39页，共192页，编辑于2022年，星期日例：例：设集合设集合A=a,b,c,a,c,d,a,c,e，求，求 A，A，A，A，A，A。解：解：A=a,b,c,d,e；A=a,c；A=a b c d e；A=a c；A=a c；A=a b c d e。第40页，共192页，编辑于2022年，星期日优先级优先级 一般地,一元运算符(补集,幂集,广义并,广义交)优先于优先于 二元运算符(差集,并集,交集,对称差,笛卡儿积)；二元运算符优优先于先于集合关系符(,)。此外,许多集合表达式里还使用到联结词,和逻辑关系符以及括号,我们规定:(1)集合运算优先于逻辑运算；(2)括号内优先于括号外；(3)同一括号内,同一优先级按从左至右运算。第41页，共192页，编辑于2022年，星期日集合运算律集合运算律幂等律幂等律：AAA；AAA同一律同一律：AA；AE=A零零律：律：AE=E；A结合律：结合律：(AB)CA(BC)；(AB)CA(BC)交换律交换律：ABBA；ABBA分配律分配律：A（BC）（）（AB）(AC)；A(BC)=(AB)(AC)第42页，共192页，编辑于2022年，星期日排中律：排中律：矛盾律：矛盾律：吸收律吸收律：A（AB）AA(AB)A摩根律：摩根律：双重否定律双重否定律：第43页，共192页，编辑于2022年，星期日其它常用结论：其它常用结论：AB A,AB B；A AB,B AB；A-B A，A-B=AB；AB=BA BAB=AA-B=；A B=B A；(A B)C=A(B C)A=A；A A=；A B=A CB=C。第44页，共192页，编辑于2022年，星期日集合集合等式的证明，可采用命题逻辑的等值式证明，等式的证明，可采用命题逻辑的等值式证明，其基本思想是互为子集：其基本思想是互为子集：欲证欲证:A=B即证即证:即证即证:对任意的对任意的x,，当上述过程可逆时，可以合并为当上述过程可逆时，可以合并为对任意的对任意的x,集合相等的证明方法集合相等的证明方法第45页，共192页，编辑于2022年，星期日例：例：证明下列集合恒等式。证明下列集合恒等式。（1 1）AA（BCBC）（）（ABAB）(AC)(AC)（2 2）（3 3）证明：证明：(1)(1)对任意的对任意的x x第46页，共192页，编辑于2022年，星期日(2)对任意的对任意的x(3)对任意的对任意的x第47页，共192页，编辑于2022年，星期日例例3.3.2证明：（证明：（1）（2）A B=（AB）-（AB）证明证明：(1)(2)AB=（A-B）（B-A）第48页，共192页，编辑于2022年，星期日例例证明证明(AB)-C=(A-C)(B-C).证明证明:对于对于 xx(AB)-Cx(AB)x C(xAxB)x C(xAx C)(xBx C)x(A-C)x(B-C)x(A-C)(B-C)(AB)-C=(A-C)(B-C)第49页，共192页，编辑于2022年，星期日例例证明证明证明：证明：(1)必要性必要性：对任意的：对任意的X,因此，因此，。(2)充分性充分性：对任意的：对任意的x，因此因此，结论得证。，结论得证。第50页，共192页，编辑于2022年，星期日例例求在求在1和和1000之间不能被之间不能被5或或6，也不能被，也不能被8整除的数整除的数的个数解：设的个数解：设1到到1000之间的整数构成全集之间的整数构成全集E，A，B，C分别表示其中可被分别表示其中可被5，6或或8整除的数的集合。整除的数的集合。解：解：在在ABC中的数一定可被中的数一定可被5,6和和8的最小公倍的最小公倍数数 5,6,8=120整除，即整除，即ABC=1000/5,6,8=8同样可得同样可得AB=1000/5,6=33；AC=1000/5,8=25；BC=1000/6,8=41；第51页，共192页，编辑于2022年，星期日然后计算然后计算 A=1000/5=200；B=1000/6=166；C=1000/8=125从而得到从而得到 ABC=200+100+33+67=400所以，所以，不能被不能被5或或6,也不能被也不能被8整除的数有整除的数有600个。个。150100671733258第52页，共192页，编辑于2022年，星期日对上述子集计数：对上述子集计数：|S|=1000；|A|=1000/5=200；|B|=1000/6=133；|C|=1000/8=125；|A B|=1000/30=33；|B C|=1000/40=25|B C|=1000/24=41；|A B C|=1000/120=8。代入公式：代入公式：N=1000(200+133+125)+(33+25+41)8=600。这个方法叫这个方法叫容斥原理。容斥原理。第53页，共192页，编辑于2022年，星期日称为包含排斥原理，简称称为包含排斥原理，简称容斥原理容斥原理。容斥原理容斥原理定理：定理：有穷集有穷集S中不具有中不具有p1,p2,pm元素数是元素数是第54页，共192页，编辑于2022年，星期日推论推论设设A1,A2,An是是n个集合，则个集合，则第55页，共192页，编辑于2022年，星期日例例 某班有某班有2525个学生，其中个学生，其中1414人会打篮球，人会打篮球，1212人会打排人会打排球，球，6 6人会打篮球和排球，人会打篮球和排球，5 5人会打篮球和网球，还有人会打篮球和网球，还有2 2人会打这三种球。而人会打这三种球。而6 6个会打网球的人都会打另外一种个会打网球的人都会打另外一种球球(指篮球或排球指篮球或排球)，求不会打这三种球的人数。，求不会打这三种球的人数。解：解：设会打排球、网球、篮球的学生集合分设会打排球、网球、篮球的学生集合分别为别为A，B和和C，则有，则有 A=12，B=6，C=14，S=25 AC=6，BC=5，ABC=2第56页，共192页，编辑于2022年，星期日现在求现在求AB，因为会打网球的人都会打另一种球，即篮球和排，因为会打网球的人都会打另一种球，即篮球和排球，而其中会打篮球的有球，而其中会打篮球的有5人，那么另一个人肯定会打排球但不会人，那么另一个人肯定会打排球但不会打篮球，再加上会打三种球的打篮球，再加上会打三种球的2人，共有人，共有3人会打排球和网球，即人会打排球和网球，即AB=3，根据容斥定理有，根据容斥定理有 ABC=25-（12+6+14）+（3+6+5）-2=5324排球排球1212篮球篮球1414网球网球6 6155不会打三种球人数为：不会打三种球人数为：25-(12+5+3)=5第57页，共192页，编辑于2022年，星期日课堂练习：证明下列等式课堂练习：证明下列等式第58页，共192页，编辑于2022年，星期日第四章第四章二元关系和函数二元关系和函数 说起关系这个词，对我们并不陌生，世界上存在着各种各样说起关系这个词，对我们并不陌生，世界上存在着各种各样的关系，人与人之间的的关系，人与人之间的“同志同志”关系；关系；“同学同学”关系；关系；“朋友朋友”关系；关系；“师生师生”关系；关系；“上下级上下级”关系；关系；“父子父子”关系；两关系；两个数之间有个数之间有“大于大于”关系；关系；“等于等于”关系和关系和“小于小于”关系；两关系；两个变量之间有一定的个变量之间有一定的“函数函数”关系；计算机内两电路间有导线关系；计算机内两电路间有导线“连接连接”关系；程序间有关系；程序间有“调用调用”关系等等。所以对关系进行关系等等。所以对关系进行深刻的研究，对数学与计算机科学都有很大的用处。深刻的研究，对数学与计算机科学都有很大的用处。第59页，共192页，编辑于2022年，星期日集合的笛卡尔积与二元关系集合的笛卡尔积与二元关系由两个元素由两个元素x,y（允许（允许x=y）按一定顺序排列成）按一定顺序排列成的二元组叫做一个的二元组叫做一个有序对或序偶有序对或序偶，记作，记作,其中其中x是是它的它的第一元素第一元素，y是它的是它的第二元素第二元素。有序对有序对具有以下性质：具有以下性质：(1)当当xy时，时，(2)=x=wy=v例例：已知：已知=，求，求x和和y。解：由有序对相等的充要条件得解：由有序对相等的充要条件得x+3=y+7y-2=3y-x解得解得x=6,y=2。第60页，共192页，编辑于2022年，星期日一个一个有序有序n元组元组(n3)是一个有序对，其中第一个元素是一是一个有序对，其中第一个元素是一个有序个有序n-1元组，一个有序元组，一个有序n元组记作元组记作,即即=,xn例：例：空间直角坐标系中点的坐标空间直角坐标系中点的坐标,等都是有序等都是有序3元组。元组。n维空间中点的坐标或维空间中点的坐标或n维向量都是有序维向量都是有序n元组。元组。形式上也可以把形式上也可以把看成有序看成有序1元组。元组。第61页，共192页，编辑于2022年，星期日设设A，B为集合，用为集合，用A中元素为第一元素，中元素为第一元素，B中元素中元素为第二元素构成有序对。所有这样的有序对组成的集合为第二元素构成有序对。所有这样的有序对组成的集合叫做叫做A和和B的的笛卡儿积笛卡儿积，记作，记作AB。笛卡儿积的符号化表示为：笛卡儿积的符号化表示为：AB=|xAyB例例：若：若A=1,2,B=a,b,c,则则AB=,BA=,易知：若易知：若|A|=m,(即集合即集合A的元素的个数的元素的个数),|B|=n,则则|AB|=|BA|=mn第62页，共192页，编辑于2022年，星期日有序对就是有顺序的数组有序对就是有顺序的数组，如，如，x,y的的位置是确定的，不能随意放置。位置是确定的，不能随意放置。注注 意意：有有 序序 对对 ，以以 a,b为为 元元 素素 的的 集集 合合a,b=b,a；有序对；有序对(a,a)有意义，而集合有意义，而集合a,a不成立。不成立。笛笛卡卡儿儿积积是是一一种种集集合合合合成成的的方方法法，把把集集合合A，B合合成成集集合合AB，规定，规定AB x A,y B。由由于于有有序序对对中中x,y的的位位置置是是确确定定的的，因因此此AB的的记记法法也也是是确定的，不能写成确定的，不能写成BA。笛卡儿积也可以多个集合合成笛卡儿积也可以多个集合合成A1A2An。笛卡儿积的运算性质。笛卡儿积的运算性质。第63页，共192页，编辑于2022年，星期日笛卡儿积的性质：笛卡儿积的性质：1、对任意集合、对任意集合A，根据定义有，根据定义有A=A=2、一般来说，笛卡儿积不满足交换律，即、一般来说，笛卡儿积不满足交换律，即ABBA（当（当ABB、A时）时）3、笛卡儿积不满足结合律，即、笛卡儿积不满足结合律，即(AB)CA(BC)（当（当ABC时）时）4、笛卡儿积运算对并和交运算满足分配律，即、笛卡儿积运算对并和交运算满足分配律，即A(BC)=(AB)(AC)(BC)A=(BA)(CA)A(BC)=(AB)(AC)(BC)A=(BA)(CA)第64页，共192页，编辑于2022年，星期日例：例：证明证明(BC)A=(BA)(CA)对于对于(BC)Ax(BC)yAxBxCyAxBxCyAyA(xByA)(xCyA)BACA(BA)(CA)(BC)A=(BA)(CA)第65页，共192页，编辑于2022年，星期日例例：设：设A，C，B，D为任意集合，为任意集合，判断以下命题是否为真，并说明理由。判断以下命题是否为真，并说明理由。(1)AB=AC=B=C。(2)A-(BC)=(A-B)(A-C)。(3)存在集合存在集合A,使得使得A AA。解：解：(1)(1)不一定为真。反例不一定为真。反例A=,BA=,B、C C为任意不相为任意不相 等的非空集合。等的非空集合。(2)(2)不一定为真。反例不一定为真。反例A=1,B=2,C=3.A=1,B=2,C=3.(3)(3)为真。当为真。当 A=A=时成立。时成立。第66页，共192页，编辑于2022年，星期日设设A1,A2,An,是集合是集合(n2),它们的它们的n阶笛卡儿阶笛卡儿积记作积记作A1A2An，其中，其中A1A2An=|x1 A1x2 A2xn An。当当A1=A2=An=A时时,将起将起n阶笛卡儿积记作阶笛卡儿积记作An例例，A=a,b,则：则：A3=AAA=a,ba,ba,b=,。第67页，共192页，编辑于2022年，星期日例例：设集合：设集合A=a,b,B=1,2,3,C=d,求求ABC，BA。解：解：先计算先计算AB,ABC,d,BA,。第68页，共192页，编辑于2022年，星期日例：例：设集合设集合A1,2,求求AP(A)。解：解：P(A)=,1,2,1,2AP(A)1,2,1,2,1,2=,第69页，共192页，编辑于2022年，星期日如果一个集合符合以下条件之一：如果一个集合符合以下条件之一：(1)集合非空，且它的元素都是有序对集合非空，且它的元素都是有序对(2)集合是空集集合是空集则称该集合为一个则称该集合为一个二元关系二元关系，记作，记作R，简称为关系。，简称为关系。对于二元关系对于二元关系R，若，若R,可记作可记作xRy;如果如果 R,则记作则记作xRy。例例：R1=,aR1b,1R12。第70页，共192页，编辑于2022年，星期日二元关系二元关系是两种客体之间的联系，例如某学生是两种客体之间的联系，例如某学生学习语文、数学、外语，表示为：学习语文、数学、外语，表示为：A A 语文语文,数学数学,外语外语 功课的成绩分四个等级，记作功课的成绩分四个等级，记作B BAA，B B，C C，DD于是该生成绩的全部可能为于是该生成绩的全部可能为ABABABAB ,D,D,D而该生的实际成绩而该生的实际成绩 P P,DP P是是ABAB的一个子集，它表示了功课与其成绩的一种关系。的一个子集，它表示了功课与其成绩的一种关系。由由此此可可见见：两两个个集集合合之之间间的的二二元元关关系系，实实际际上上就就是是两两个个元元素素之之间的某种相关性。间的某种相关性。第71页，共192页，编辑于2022年，星期日设设A，B为集合，为集合，AB的任何子集所定义的的任何子集所定义的二元关系叫做从二元关系叫做从A到到B的的二元关系二元关系；特别当特别当A=B时则叫做时则叫做A上的上的二元关系二元关系。例：例：若若A=a,b，B=1,2,3，则，则AB=,令令R1=,R2=,R3=。因为因为R1 AB，R2 AB，R3 AB，所以，所以R1,R2和和R3均均是由是由A到到B的二元关系。的二元关系。第72页，共192页，编辑于2022年，星期日又例：若又例：若A=a,b，B=1,2,3，则，则BA=,令令R4=,R5=,因为因为R4 BA，R5 BA，所以所以R4和和R5均是由均是由B到到A的关系。的关系。又又BB=,。令令R6=，,R7=,因为因为R6 BB，R7 BB，所以所以R6和和R7均是集合均是集合B上上的关系。的关系。第73页，共192页，编辑于2022年，星期日若集合若集合|A|=n,则集合则集合A上的二元关系有多少个？上的二元关系有多少个？答：答：|A|=n，则，则|AA|=n2,AA的任一个子集就是的任一个子集就是A上的二元关系，即上的二元关系，即P(A)=2n个。个。例例A=1,2则则AA有有2n个不同的二元关系；个不同的二元关系；AA=1,21,2=,。AA的任一个子集就是的任一个子集就是AA的幂集，即的幂集，即P(A)P(A)=,第74页，共192页，编辑于2022年，星期日三类特殊的关系三类特殊的关系空关系：空关系：对于任何集合对于任何集合A，空集，空集是是AA的的子集，称作子集，称作A上的上的空关系；空关系；全关系：全关系：定义定义EA=|xAyA=AA为为全域关系；全域关系；恒等关系：恒等关系：定义定义IA=|xA为为A上上恒等关系。恒等关系。例：例：若若A=1,2,3，则，则EA=,IA=,。第75页，共192页，编辑于2022年，星期日例：例：设设A=1,2,3,4，请表示下列关系。，请表示下列关系。(1)R=|x是是y的倍数的倍数(2)R=|(x-y)2A(3)R=|x除除y是素数是素数(4)R=|xy解：解：(1)R=,；(2)R=,；(3)R=,；(4)R=,第76页，共192页，编辑于2022年，星期日关系表示法关系表示法有穷集合上的二元关系的三种表示方法：有穷集合上的二元关系的三种表示方法：n集合表示法集合表示法（前已使用）（前已使用）n关系矩阵法关系矩阵法n关系图关系图关系矩阵是表示关系的另一种有效的方法，其优点是关系矩阵是表示关系的另一种有效的方法，其优点是可以利用矩阵作为研究关系的手段，而且这样做便于计算可以利用矩阵作为研究关系的手段，而且这样做便于计算机进行处理。机进行处理。第77页，共192页，编辑于2022年，星期日设设R：AB，A和和B都是有限集，且都是有限集，且|A|=n,|B|=m,A,B中的元素已按一定的次序排列若中的元素已按一定的次序排列若A=x1,x2,xn,B=y1,y2,ym且且R A B,若若则称矩阵则称矩阵M(R)M(R)=(r rij ij)n m m 为为R的的关系矩阵关系矩阵。关系矩阵法关系矩阵法第78页，共192页，编辑于2022年，星期日 0 1 1 1MR=0 0 1 1 0 0 0 1 0 0 0 0例例A=1,2,3,4,R为为A上的小于关系，上的小于关系，则则R=,R的关系矩阵为：的关系矩阵为：1 2 3 41 2 3 41 1 2 2 3 3 4 4第79页，共192页，编辑于2022年，星期日例例:设集合设集合A2,3,4,B=8,9,12,14。R是由是由A到到B的二元关系，定义：的二元关系，定义：R=|a整除整除b写出写出R的表达式和关系矩阵。的表达式和关系矩阵。解解：R=,R的关系矩阵：的关系矩阵：第80页，共192页，编辑于2022年，星期日关系图关系图关系图是表示关系的一种直观形象的方法，设关系图是表示关系的一种直观形象的方法，设R：AB，A和和B都是有限集，都是有限集，A=x1,x2,xn,B=y1,y2,ym关系关系R的有序对的有序对可用图中从结点可用图中从结点xi到到yj的有向边表的有向边表示，这样即可将关系用图表示之。示，这样即可将关系用图表示之。例例设设R:AB，A=x1,x2,x3,x4,B=y1,y2,y3R=,，R的关系如下图所示的关系如下图所示x1x2x3x4y1y2y3第81页，共192页，编辑于2022年，星期日设设R是在是在A上的二元关系，上的二元关系，A=x1,x2,xn关系关系R的有序偶的有序偶可用图中从结点可用图中从结点xi到到xj的有向边表示，这样即可将关系的有向边表示，这样即可将关系用图表示之。用图表示之。例例：设设R:AA，A=a,b,c,dR=,R的关系如下图所示：的关系如下图所示：abcd第82页，共192页，编辑于2022年，星期日 例：例：设集合设集合A=a,b,c,d,R是是A上的关系上的关系R=,试以关系矩试以关系矩