离散数学第2章-课件.ppt

1、计算机科学与工程系计算机科学与工程系Tianjin University of Technology Department of Computer Science&Engineering(Discrete Mathematics)计算机科学与工程系计算机科学与工程系Tianjin University of Technology Department of Computer Science&Engineering(Discrete Mathematics)(D i s c r e t e Ma t h e ma t i c s)(D i s c r e t第二章第二章 集合集合SetsSets

2、 本章首先采用朴素集合论的方法，介绍有关集合的一些基本本章首先采用朴素集合论的方法，介绍有关集合的一些基本知识，内容显得较为直观，学起来易于接受。但集合及其相关的知识，内容显得较为直观，学起来易于接受。但集合及其相关的概念是本门课程后面各章内容的基础，同学们务必熟练的掌握。概念是本门课程后面各章内容的基础，同学们务必熟练的掌握。第二章第二章 集合集合 本章首先采用朴素集合论的方法，介绍有关本章首先采用朴素集合论的方法，介绍有关 第一节第一节 集合的概念和表示法一集合的概念和表示法一 集合的概念二集合的概念二 集合的表示法集合的表示法 一、集合的基本概念一、集合的基本概念1、集合的定义、集合的定

3、义具有某种共同属性的事物的全体具有某种共同属性的事物的全体 称为称为例如：例如：集合。集合。计算机网络是计算机之间以信息传输为主要计算机网络是计算机之间以信息传输为主要目的而连接起来的计算机系统的集合。目的而连接起来的计算机系统的集合。计算机内存的全体单元构成一集合。计算机内存的全体单元构成一集合。一、集合的基本概念一、集合的基本概念1、集合的定义具有某种共同属性的事物的全体、集合的定义具有某种共同属性的事物的全体一、集合的基本概念一、集合的基本概念2、集合的元素、集合的元素1、集合的元素表示的事物可以是具体的，、集合的元素表示的事物可以是具体的，注：注：也可也可以是以是抽象的。抽象的。2、集

4、合的元素是任意的，、集合的元素是任意的，但必须是确定的但必须是确定的和可和可以区分的。以区分的。集合里含有的对象或客体集合里含有的对象或客体 称为集合的称为集合的元素。元素。一、集合的基本概念一、集合的基本概念2、集合的元素、集合的元素1、集合的元素表示的事物可以、集合的元素表示的事物可以一、集合的基本概念一、集合的基本概念3、集合的分类、集合的分类1)有限集合有限集合集合的元素个数是有限的。集合的元素个数是有限的。2)无限集合无限集合集合的元素个数是无限的。集合的元素个数是无限的。一、集合的基本概念一、集合的基本概念3、集合的分类、集合的分类1)有限集合集合的元素个数有限集合集合的元素个数二

5、、集合的表示法二、集合的表示法1、符号表示法、符号表示法通常用大写字母通常用大写字母A,B,C,代表集合代表集合;用小写字母用小写字母a,b,c,代表元素。代表元素。1)如果如果a是集合是集合A的一个元素的一个元素,则记为则记为 aA,读做读做“a属于属于A”,或或“a在集合在集合A中中”。2)如果如果a不是集合不是集合A的一个元素的一个元素,则记为则记为读做读做“a不属于不属于A”,或或“a不在集合不在集合A中中”。aA,任一元素任一元素,对某一集合而言对某一集合而言,或属于该集合或属于该集合,或不属于该集合或不属于该集合,二者必居其一二者必居其一,且只居其一。且只居其一。注：注：二、集合的

6、表示法二、集合的表示法1、符号表示法通常用大写字母、符号表示法通常用大写字母A,B,C,二、集合的表示法二、集合的表示法1、符号表示法、符号表示法绝不容许界限不分明或含糊不清的情况存在。绝不容许界限不分明或含糊不清的情况存在。注：注：离散数学中，只讨论界限清楚、无二义性的描述，离散数学中，只讨论界限清楚、无二义性的描述，不清晰的对象构成的集合不清晰的对象构成的集合 属于模糊论的研究范畴。属于模糊论的研究范畴。著名理发师问题就属于模糊论的研究范畴。著名理发师问题就属于模糊论的研究范畴。二、集合的表示法二、集合的表示法1、符号表示法绝不容许界限不分明或含糊不清的、符号表示法绝不容许界限不分明或含糊

7、不清的二、集合的表示法二、集合的表示法2、描述集合中元素的方法、描述集合中元素的方法 1)列举法列举法 a、全部列举法：、全部列举法：以任意顺序写出集合的所有元素以任意顺序写出集合的所有元素,隔开，隔开，元素间用逗号元素间用逗号并将其放在花括号内并将其放在花括号内。例如例如“所有小于所有小于5的正整数的正整数”，这个集合的元素为这个集合的元素为1,2,3,4,再没有别的元素了。再没有别的元素了。如果把这个集合命名为如果把这个集合命名为A,A=1,2,3,4就可记为就可记为二、集合的表示法二、集合的表示法2、描述集合中元素的方法以任意顺序写出集合的、描述集合中元素的方法以任意顺序写出集合的大家有

8、疑问的，可以询问和交流可以互相讨论下，但要小声点大家有疑问的，可以询问和交流可以互相讨论下，但要小声点二、集合的表示法二、集合的表示法2、描述集合中元素的方法、描述集合中元素的方法 1)列举法列举法 b、部分列举法：、部分列举法：列举集合的部分元素，列举集合的部分元素，素素其他元素可从列举的元其他元素可从列举的元用省略号代替。用省略号代替。例如例如A表示表示“全体小写英文字母全体小写英文字母”的集合，的集合，A=a,b,y,z则则归纳出来归纳出来，列举法仅适用于描述元素个数有限的集合列举法仅适用于描述元素个数有限的集合注：注：或或元素具有明显排列规律的集合。元素具有明显排列规律的集合。二、集合

9、的表示法二、集合的表示法2、描述集合中元素的方法列举集合的部分元素，、描述集合中元素的方法列举集合的部分元素，二、集合的表示法二、集合的表示法2、描述集合中元素的方法、描述集合中元素的方法 2)描述法描述法 把集合元素的共同属性描述出来。把集合元素的共同属性描述出来。集合中元素的属性。集合中元素的属性。P(x)表示任何谓词，表示任何谓词，则则A=x|P(x)即用谓词概括即用谓词概括表示所有使谓词表示所有使谓词P(x)成立的元素成立的元素x所组成的集合。所组成的集合。例：例：x|x2-3x+2=0、x|x=2n-1nN如果如果P(a)为真，为真，则则aA，否则否则 aA,(谓词表示法谓词表示法)

10、集合的元集合的元素素集合的元素集合的元素必须满足的必须满足的条件条件二、集合的表示法二、集合的表示法2、描述集合中元素的方法把集合元素的共同属性、描述集合中元素的方法把集合元素的共同属性二、集合的表示法二、集合的表示法1、有些集合可以用两种方法表示，、有些集合可以用两种方法表示，注：注：但是有些但是有些集合不可以用列元素法表示，集合不可以用列元素法表示，如实数集合。如实数集合。2、集合的元素是彼此不同的，、集合的元素是彼此不同的，如果同一个元如果同一个元素在集合中多次出现素在集合中多次出现 应该认为是一个元素。应该认为是一个元素。如如:3,4,4,4,5、3,4,5、5,4,3 是同一个集合。

11、是同一个集合。3、集合的元素是无序的。、集合的元素是无序的。4、集合的元素可以是一个集合，、集合的元素可以是一个集合，但不允许以但不允许以集合自身为其元素。集合自身为其元素。如如:S=a,b,S=a,b,S,aS，bS,二、集合的表示法二、集合的表示法1、有些集合可以用两种方法表示，注：但是有些、有些集合可以用两种方法表示，注：但是有些A，三、元素和集合之间的关系三、元素和集合之间的关系元素和集合之间的关系元素和集合之间的关系,是隶属关系，是隶属关系，即属于即属于或不属于，或不属于，属于记作属于记作，不属于记作不属于记作。例如：例如：A=1，1，2，3，311，23A，A，3A，23 A，A。

12、可以用一种树形图表示可以用一种树形图表示集合与元素的隶属关系。集合与元素的隶属关系。A11,233123321，2，A，三、元素和集合之间的关系元素和集合之间的关系，三、元素和集合之间的关系元素和集合之间的关系,是隶属关是隶属关AB()四、集合间的包含关系四、集合间的包含关系1、子集、子集如果集合如果集合A中每个元素中每个元素 都是集合都是集合B中的元素，中的元素，则称则称A是是B的的或或A包含于包含于B，子集，子集，或者或者B包含包含A，记作记作AB如果如果A不是不是B的子集，的子集，或或 BA。AB (x)x Ax B则在则在A中至少有一个元素中至少有一个元素不属于不属于B时，时，称称B不

13、包含不包含A，记作记作或或 BA。注：注：1)AA，2)AB，BC，则则AC。A B ()B()四、集合间的包含关系四、集合间的包含关系2、集合相等、集合相等1)定义定义两个集合相等两个集合相等当且仅当当且仅当 它们有相同的元素。它们有相同的元素。若若A和和B相等，相等，记作记作 A=B(x)x Ax (外延性原理外延性原理)A=B。两个集合不相等，两个集合不相等，记作记作A B。B()四、集合间的包含关系四、集合间的包含关系2、集合相等、集合相等2)判断判断A与与B互为互为子集。子集。定理定理 若若A和和B相等相等 当且仅当当且仅当 AB 且且 BA。即即四、集合间的包含关系四、集合间的包含

14、关系2、集合相等、集合相等A 与与B 互为子集。定理互为子集。定理 若若A()()四、集合间的包含关系四、集合间的包含关系3、真子集、真子集如果集合如果集合A中每个元素中每个元素 都属于集合都属于集合B，但但B中中不属于不属于A，则称则称A是是B的的记作记作A B 或或 BA。AB(x)x Ax B至少有一个元素至少有一个元素真子集。真子集。(x)x Bx ABA B例例 A=a，bB=a，b不是不是的的 子集。子集。（真）（真）A()(四、集合间的包含关系四、集合间的包含关系3、真子集、真子集可以用文氏图了表示集合间的包含关系。可以用文氏图了表示集合间的包含关系。文氏文氏(Venn)图是一种

15、利用平面上的点构成的图是一种利用平面上的点构成的图形来形象展示集合的一种方法。图形来形象展示集合的一种方法。集合用矩形、园面集合用矩形、园面如果如果AB，或一封闭曲线来表示。或一封闭曲线来表示。则表示则表示A的圆面的圆面一般完全落在一般完全落在表示表示B的圆面内。的圆面内。ABBAAB四、集合间的包含关系四、集合间的包含关系3、真子集可以用文氏图了表示集合间的包含、真子集可以用文氏图了表示集合间的包含四、集合间的包含关系四、集合间的包含关系4、隶属和包含关系的区别、隶属和包含关系的区别例例 A=a，a，B=aBA，B A，B是是A的元素，的元素，B的元素的元素a 是是A的元素，的元素，B是是A

16、的子集。的子集。隶属是隶属是 元素元素 和和 集合集合 的关系，的关系，包含是包含是 集合集合 和和 集合集合 的关系，的关系，某些集合可以同时成立这两种关系。某些集合可以同时成立这两种关系。是个体与整体的关系，是个体与整体的关系，是部分与整体的关系。是部分与整体的关系。四、集合间的包含关系四、集合间的包含关系4、隶属和包含关系的区别例、隶属和包含关系的区别例 A=a五、特殊集合五、特殊集合1、空集、空集 定义定义不含任何元素的集合不含任何元素的集合空集，空集，称为称为记作记作。例例 两条平行线交点的集合两条平行线交点的集合 为为。例例 x|x 0 x 0 x R=。注：注：1)与与 的区别。

17、的区别。是集合，没有元素是集合，没有元素有有1个元素的集合个元素的集合2)，五、特殊集合五、特殊集合1、空集不含任何元素的集合空集，称为记作、空集不含任何元素的集合空集，称为记作。例。例 五、特殊集合五、特殊集合1、空集、空集 定理定理空集空集是任一集合是任一集合A的子集，的子集，即即 A。下列命题是否为真。下列命题是否为真。1);2);3);4)。五、特殊集合五、特殊集合1、空集空集、空集空集是任一集合是任一集合A 的子集，即的子集，即 A。下。下五、特殊集合五、特殊集合1、空集、空集 推理推理空集空集是唯一的。是唯一的。设设1，2是两个空集是两个空集,则则1 2，且且2 1，得得1=2，所

18、以空集是唯一的。所以空集是唯一的。证明：证明：证明唯一性证明唯一性一般采用反一般采用反证法证法(绝对唯一绝对唯一)证毕。证毕。五、特殊集合五、特殊集合1、空集空集、空集空集是唯一的。设是唯一的。设1，2 是两个空集是两个空集,五、特殊集合五、特殊集合1、空集、空集 2)证明一个集合是空集，或证明集合的唯一性，证明一个集合是空集，或证明集合的唯一性，常采用反证方法，常采用反证方法，即假设该集合不是空集，即假设该集合不是空集，或不唯一，或不唯一，导致与已知条件的矛盾或导致唯一。导致与已知条件的矛盾或导致唯一。注：注：1)任何非空集合任何非空集合A，至少有至少有 子集：子集：两个两个、和和A。只有只

19、有 子集子集一个一个。五、特殊集合五、特殊集合1、空集、空集 2)证明一个集合是空集，或证明集合的证明一个集合是空集，或证明集合的五、特殊集合五、特殊集合2、全集、全集 定义定义在一定范围内，如果在一定范围内，如果所有所有集合都是某一集集合都是某一集合的子集，合的子集，则称此集合为则称此集合为全集全集,记作记作 U。注：注：1)全集是相对的，不同的问题有不同的全集，全集是相对的，不同的问题有不同的全集，即使是同一个问题也可以取不同的全集。即使是同一个问题也可以取不同的全集。2)一般地说，全集取得小一些，问题的描述和一般地说，全集取得小一些，问题的描述和 处理会简单些。处理会简单些。3)全集全集

20、U 用一个矩形的内部表示，用一个矩形的内部表示，U五、特殊集合五、特殊集合2、全集在一定范围内，如果所有集合都是某一集合的、全集在一定范围内，如果所有集合都是某一集合的五、特殊集合五、特殊集合3、幂集、幂集 定义定义由集合由集合A的的所有子集所有子集为元素所组成的集合为元素所组成的集合称为称为A的的幂集幂集,记作记作注：注：1)幂集的元素都是幂集的元素都是集合。集合。或或P(A)或或2 A。2)任一集合的幂集任一集合的幂集 都非空。都非空。3)在在 A 的所有子集中，的所有子集中，A 和和又叫平凡子集。又叫平凡子集。(A)五、特殊集合五、特殊集合3、幂集由集合、幂集由集合A 的所有子集为元素所

21、组成的集合称为的所有子集为元素所组成的集合称为 、a 五、特殊集合五、特殊集合3、幂集、幂集例例 的的幂集：幂集：)(=A=a的的幂集：幂集：=、a A=a，b的的幂集：幂集：)A(=ba、b有有 个元素个元素1有有 个元素个元素2有有 个元素个元素4202122(A)、a 五、特殊集合五、特殊集合3、幂集、幂集 一般地，一般地，集合集合A=a1、a2、an，则则)A(有有 个元素。个元素。2n它的它的m(0 m n)元子集有元子集有 个，个，mnC不同的子集共有不同的子集共有0nC1nC 2nC+nnC=(1+1)n=2n个。个。五、特殊集合五、特殊集合3、幂集集合、幂集集合A=a 1、a

22、2、a n ，则，则A=x|，理发师问题理发师问题 在一个很僻静的孤岛上，住着一些人家，岛上只在一个很僻静的孤岛上，住着一些人家，岛上只有一位理发师，该理发师专给那些并且只给那些自己有一位理发师，该理发师专给那些并且只给那些自己不刮脸的人刮脸。那么，谁给这位理发师刮脸？不刮脸的人刮脸。那么，谁给这位理发师刮脸？解：解：设设不给自己刮脸的人不给自己刮脸的人x 是是b是这位理发师。是这位理发师。1)若若bA，则则b是不给自己刮脸的人，是不给自己刮脸的人，而由题意，而由题意，b只给集合只给集合A中的人刮脸。中的人刮脸。b 要给要给b 刮脸，刮脸，即即b A。A=x|2)若若b A，理发师问题理发师问

23、题 在一个很僻静的孤岛上，住着一些人家，岛上只在一个很僻静的孤岛上，住着一些人家，岛上只有一位理发师，该理发师专给那些并且只给那些自己有一位理发师，该理发师专给那些并且只给那些自己不刮脸的人刮脸。那么，谁给这位理发师刮脸？不刮脸的人刮脸。那么，谁给这位理发师刮脸？解：解：则则b是要给自己刮脸的人，是要给自己刮脸的人，而由题意，而由题意，理发师只给自己不刮脸的人刮脸。理发师只给自己不刮脸的人刮脸。b 是不给自己是不给自己 刮脸的人，刮脸的人，即即bA。无论无论1)和和2)，都有都有 bA 及及b A 同时成立。同时成立。这种情况称为罗索悖论，这种情况称为罗索悖论，是模糊论的范畴。是模糊论的范畴。

24、返回返回2)若若b A，理发师问题，理发师问题 在一个很僻静在一个很僻静 第二节第二节 集合的运算一集合的运算一 集合的交二集合的交二 集合的并集合的并 三三 集合的补四集合的补四一、集合的交一、集合的交1、定义、定义2、文氏图、文氏图任意两个集合任意两个集合A和和B，由由A和和B的的所有共同元素所有共同元素组成的集合，组成的集合，称为称为A和和B的的交集交集，记为记为 AB。AB=x|xA xB即即(Intersection)ABAB一、集合的交一、集合的交1、定义任意两个集合、定义任意两个集合A 和和B，由，由A 和和B 的所有共同元的所有共同元一、集合的交一、集合的交如果两个集合没有任何

25、共同的元素，如果两个集合没有任何共同的元素，(Intersection)例如，例如，A=a,b,c,e,f，B=b,e,f,r,s，C=a,t,u,v,则则 AB=b,e,f AC=a BC=则称它们是则称它们是不相交不相交 集合。集合。EAB一、集合的交如果两个集合没有任何共同的元素，一、集合的交如果两个集合没有任何共同的元素，(I n t e r s e一、集合的交一、集合的交三个或更多的集合的交集运算：三个或更多的集合的交集运算：n21AAA(Intersection)ABC=x|xA xB xC kn1kA一、集合的交三个或更多的集合的交集运算：一、集合的交三个或更多的集合的交集运算：

26、(I n t e r s e c t一、集合的交一、集合的交3、性质、性质AA1)幂等律幂等律(Intersection)=AA2)零律零律=AE3)同一律同一律=AAB4)交换律交换律=BAA(BC)5)结合律结合律=(AB)C一、集合的交一、集合的交3、性质、性质A A 1)幂等律幂等律(I n t e r s e c t i o()B一、集合的交一、集合的交3、性质、性质(Intersection)若若AB，6)则则AC BC。反之反之 不然。不然。证：证：AB (x)x Ax 分析：分析：若若xAC，即即xAxC,AB xAxB则则xBxC,xBC。反之，反之，取取C=，A=a，B=b

27、，则则AC=BC=但但AB证毕证毕()B 一、集一、集一、集合的交一、集合的交3、性质、性质(Intersection)AB7)A,AB B（集合越交（集合越交越小）越小）注：注：集合运算的规律和命题演算的某些规律是一致集合运算的规律和命题演算的某些规律是一致的，所以命题演算的方法是证明集合恒等式的的，所以命题演算的方法是证明集合恒等式的基本方法。基本方法。一、集合的交一、集合的交3、性质、性质(I n t e r s e c t i o n)A B 7)A二、集合的并二、集合的并1、定义、定义2、文氏图、文氏图任意两个集合任意两个集合A和和B，由属于由属于A 或属于或属于B组成的集合，组成的

28、集合，称为称为A和和B的的并集并集，记为记为 AB。AB=x|xA xB即即(Union)的元素的元素AB二、集合的并二、集合的并1、定义任意两个集合、定义任意两个集合A 和和B，由属于，由属于A 或属于或属于B 组成组成二、集合的并二、集合的并三个或更多的集合的并集运算：三个或更多的集合的并集运算：(Union)EABABC=x|xA C xB xCn21AAA n1kkAABC 二、集合的并三个或更多的集合的并集运算：二、集合的并三个或更多的集合的并集运算：(U n i o n)E A B二、集合的并二、集合的并3、性质、性质AA1)幂等律幂等律(Union)=AAU2)零律零律=UA3)

29、同一律同一律=AAB4)交换律交换律=BAA(BC)5)结合律结合律=(AB)C二、集合的并二、集合的并3、性质、性质A A 1)幂等律幂等律(U n i o n)=A A U二、集合的并二、集合的并3、性质、性质，(Union)若若AB，6)则则AC BD。反之反之 不然。不然。若若xAC，即即xAxC,CD，1)若若xA，则则xB，xBD，2)若若xC，则则xD，xBD，始终有始终有xBD。反之，反之，取取C=D=E，A=a，B=b，则则ACE=BD=E但但AB证：证：证毕。证毕。二、集合的并二、集合的并3、性质、性质(U n i o n)若若A B，6)则则A C B二、集合的并二、集合

30、的并3、性质、性质(Union)AB，7)A（集合越并（集合越并越大）越大）ABB 二、集合的并二、集合的并3、性质、性质(U n i o n)A B，7)A （集合越（集合越xB()xBxA()()二、集合的并二、集合的并4、和和的关系的关系(Union)定理定理对任意集合对任意集合A、B和和C有有:1)A(BC)=(AB)(AC);2)A(BC)=(AB)(AC)。即即对对可以分配可以分配,对对可以分配。可以分配。1)A(BC)=x|xA xC=x|xAxC=(AB)(AC)=x|xAxBxAxC x|分配律分配律分配律分配律证：证：x B()xB()xA二、集合的并二、集合的并4、和和的

31、关系的关系(Union)定理定理对任意集合对任意集合A、B有有:1)A(AB)=A2)A(AB)=A证一：证一：1)A(AB)=x|xA=x|xA=A吸收律吸收律吸收律吸收律命题逻命题逻辑中的辑中的吸收律吸收律x B()二、集合的并二、集合的并4、和和的关系的关系吸收律吸收律(Union)定理定理对任意集合对任意集合A、B有有:ABAB=B 或或 AB=A。当且仅当当且仅当AB，BB，AB BB=B由性质由性质7)BABAB=B反之，反之，由性质由性质7)AAB,AB=BAB证：证：证毕。证毕。二、集合的并二、集合的并4、和和的关系吸收律的关系吸收律(U n i o n)定理对任意集定理对任意

32、集三、集合的补三、集合的补1、定义、定义2、文氏图、文氏图任意两个集合任意两个集合A和和B，由属于由属于A 但不属于但不属于B组成的集合，组成的集合，称为称为B 对于对于A的的补集补集记为记为 AB。AB=x|xA xB即即(Relative Complement)所有元素所有元素或或相对相对的的补补 或或A和和B的差。的差。=x|xA(xB)BABA三、集合的补三、集合的补1、定义任意两个集合、定义任意两个集合A 和和B，由属于，由属于A 但不属于但不属于B 组组三、集合的补三、集合的补3、绝对补集、绝对补集全集全集U 和集合和集合A的差集的差集称为称为A的的绝对补绝对补记为记为U AA=即

33、即(Relative Complement)或或A的余集的余集或或A的补集。的补集。=x|xU xA A 或或A 或或A。U AxAxA(Absolute Complement).三、集合的补三、集合的补3、绝对补集全集、绝对补集全集U 和集合和集合A 的差集称为的差集称为A 的绝对补的绝对补三、集合的补三、集合的补4、性质、性质(Relative Complement)(A)1)双重否定律双重否定律=AU2)=3)=UAA4)排中律排中律=UAA5)矛盾律矛盾律=三、集合的补三、集合的补4、性质、性质(R e l a t i v e C o mp l e me n t三、集合的补三、集合的补

34、4、性质、性质(Relative Complement)(1)(AB)6)德摩根律德摩根律=AB(2)(AB)=AB(AB)=x|xU(xAB)=x|xU(xA=x|xU(xA)(xB)=x|(xU(xA)(xB)(xU=ABxB)证证:(1)三、集合的补三、集合的补4、性质、性质(R e l a t i v e C o mp l e me n t A()B()三、集合的补三、集合的补5、定理、定理：(Relative Complement)2)利用利用(3)的结论。的结论。A-(AB)=A(A B)=A A(3)(3)的结论的结论德摩根律德摩根律=A A B()=A-B1)A-B=AB2)A

35、-B=A-(AB)分配律分配律 A ()B (三、集合的补三、集合的补5、定理、定理(Relative Complement)4)A(B-C)=(AB)-(AC)三、集合的补三、集合的补5、定理、定理(R e l a t i v e C o mp l e me n t三、集合的补三、集合的补5、定理、定理(Relative Complement)4)a)AB B A b)AB (B-A)A=B证：证：a)若若xA则必有则必有xB，因此因此 xB，必有必有xA，即即 xB xA B A AB由上述证明可知：由上述证明可知：(A)B A(B)A=BAB B A 三、集合的补三、集合的补5、定理、定

36、理(R e l a t i v e C o mp l e me n t四、集合的对称差四、集合的对称差1、定义、定义(Symmetric Difference)设设A、B 是两个集合，是两个集合，其元素其元素但但集合集合 A 和和 B 的对称差的对称差(环和）是环和）是集合，集合，记作记作A B,或属于或属于 A，或属于或属于B,不能既属于不能既属于A 又属于又属于 B，即：即：A B=(A-B)(B-A)例如例如 A=a,b,c,B=b,d,则则A B=a,c,d=x|(xA xB)(xB xA)四、集合的对称差四、集合的对称差1、定义、定义(S y mme t r i c D i f f

37、e r e四、集合的对称差四、集合的对称差2、文氏图文氏图(Symmetric Difference)BA()()ABx xABxBAABBAABBA四、集合的对称差四、集合的对称差2、文氏图文氏图(S y mme t r i c D i f f e四、集合的对称差四、集合的对称差3、性质性质(Symmetric Difference)1)交换律交换律2)同一律同一律3)零律零律A B=4)A B=B AA=AA A=B)(A(AB)四、集合的对称差四、集合的对称差3、性质性质(S y mme t r i c D i f f e r四、集合的对称差四、集合的对称差3、性质性质(Symmetri

38、c Difference)(A B)C=A(B C)5)结合律结合律6,7,()(C)(C)ABABCABAB四、集合的对称差四、集合的对称差3、性质性质(S y mme t r i c D i f f e r定义 2.2-6A、B两集合的环积记为A B，是集合。定义定义 2.2-6 A、B 两集合的环积记为两集合的环积记为A B，是集，是集离散数学第离散数学第2 章章-课件课件定理 2.2-12 (1)=A B，(2)A B=B A，(3)A A=U。AB定理定理 2.2-1 2 (1)定理定理2.2-13定理 2.2-14 定理定理2.2-1 3 定理定理 2.2-1 4 例例1 已知已知

39、A BA C，是否必须，是否必须BC？解：解：是。是。A B=A C，A(A B)=A(A C)(A A)B=(A A)C B=CB=C。例例1 已知已知A B A C，是否必须，是否必须B C？解：是。？解：是。例例2 已知已知AB=AC，是否必须，是否必须B=C？解：解：否。否。例：例：设设A=1、2，B=1，C=2例例3 已知已知AB=AC，是否必须，是否必须B=C？解：解：例：例：设设A=1，B=1、2，C=1、3否。否。例例2 已知已知A B=A C，是否必须，是否必须B=C？解：否。？解：否。2-5 2-5 集合的笛卡尔积集合的笛卡尔积 2-5 集合的笛卡尔积集合的笛卡尔积 1、序

40、偶、序偶(有序有序2元组元组)：两个具有固定次序的客体组成一个序偶(有序2元组)，记作，其中x是它的第一元素，y是它的第二元素。一、有序一、有序n元组元组1、序偶、序偶(有序有序2 元组元组)：两个具有固定次序的客体组成一个序偶：两个具有固定次序的客体组成一个序偶(例：平面直角坐标系中的一个点的坐标就构成为一个有序序偶，我们可用表示。注：序偶是讲究次序的。例和表示平面上两个不同的点，这与集合不同，1，3和3，1是两个相等的集合。2、定义：、定义：两个序偶相等，=，当且仅当x=u且y=v。一、有序一、有序n元组元组例：平面直角坐标系中的一个点的坐标就构成为一个有序序偶，我们例：平面直角坐标系中的

41、一个点的坐标就构成为一个有序序偶，我们3、有序元组：、有序元组：是一个序偶，其第一元素本身也是一个序偶，表示为，z或。4、有序、有序n元组：元组：有序n元组也是一个序偶，其第一元素是一个n-1元组。，xn，通常简记为：，其中xi称作它的第i坐标，i=1，2，n。=的充要条件是xi=yi，i=1，2，n。序偶其元素可以分别属于不同的集合，因此任给两个集合A和B，我们可以定义一种序偶的集合。3、有序元组：是一个序偶，其第一元素本身也是一个序偶，表示、有序元组：是一个序偶，其第一元素本身也是一个序偶，表示1、定义：、定义：设A和B是任意两个集合，由A中元素作第一元素，B中元素作第二元素构成序偶，所有

42、这样序偶的集合称集合A和B的笛卡尔积或直积。记作AB。即AB=|xAyB二、笛卡尔积二、笛卡尔积1、定义：设、定义：设A 和和B 是任意两个集合，由是任意两个集合，由A 中元素作第一元素，中元素作第一元素，B 中中离散数学第离散数学第2 章章-课件课件离散数学第离散数学第2 章章-课件课件2、n个集合的笛卡尔积：集合个集合的笛卡尔积：集合A1，A2，An，则，则特别地，约定：若A=或B=，则A B=，B A=2、n 个集合的笛卡尔积：集合个集合的笛卡尔积：集合A 1，A 2，A n，则约定：若，则约定：若练习：若A=，B=1，2，3，求AB，BA，AA，BB以及(AB)(BA)。解：AB=，B

43、A=，AA=，BB=，(AB)(BA)=若A、B均是有限集，|A|=m，|B|=n，则|AB|=mn。练习：若练习：若A=，B=1，2，3 ，求，求A B，B三、笛卡尔积的性质三、笛卡尔积的性质1、对于任意集合A，A=，A=。2、笛卡尔积运算不满足交换律，当A，B，AB时ABBA。3、笛卡尔积运算不满足结合律，即当A，B，C均非空时(AB)CA(BC)。三、笛卡尔积的性质三、笛卡尔积的性质4、定理、定理2-5.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

44、)C=(A C)(B C)由以上两条有：由以上两条有：A(B C)(A B)(A C)证明两个集合相等，可以证明它们互相包含。则aA，bBC，即aA，bB，且bc，证明：(2)A(BC)，即AB且AC，有(AB)(AC)，得A(BC)(AB)(AC)(AB)(AC)，则AB且AC，则aA，bB，且aA，bC，则bBC。所以A(BC)，所以(A B)(A C)A(B C)4、定理、定理2-5.1：对任意三个集合：对任意三个集合A、B、C，有由以上两条有，有由以上两条有定理2.5-2 如果所有Ai(i=1,2,n)都是有限集合，则|A1A2An|=|A1|A2|An|定理定理2.5-2 如果所有如果所有A i(i=1,2,n)都是有都是有