第三章集合与关系-最终版

1、河南工业大学离散数学课程组河南工业大学离散数学课程组第1页集合与关系的结构图集合与关系的结构图枚举法枚举法有向图有向图矩阵矩阵等价关系等价关系有向图有向图等价类等价类商集商集划分划分偏序关系偏序关系相容类相容类最大相最大相容类容类完全覆盖完全覆盖简化图简化图全序全序哈斯图哈斯图计算方法计算方法运算性质运算性质二元关系二元关系概念及表示方法概念及表示方法性质性质自反自反对称对称传递传递反对称反对称反自反反自反相容关系相容关系运算运算复合复合求逆求逆闭包闭包重要重要元素元素河南工业大学离散数学课程组河南工业大学离散数学课程组2第第3 3章章 集合与关系集合与关系离 散 数 学河南工业大学河南工业大

2、学信息科学与工程学院信息科学与工程学院河南工业大学离散数学课程组河南工业大学离散数学课程组第3页第二篇第二篇 集合论集合论n 集合论是现代数学的集合论是现代数学的基础基础，几乎与，几乎与现代数学的各个分支都有着密切联系，现代数学的各个分支都有着密切联系，并且渗透到所有科技领域，是不可缺并且渗透到所有科技领域，是不可缺少的数学工具和表达语言。少的数学工具和表达语言。n 集合论的起源可以追溯到集合论的起源可以追溯到16世纪末世纪末期，为了追寻微积分的坚实基础，开期，为了追寻微积分的坚实基础，开始时，人们仅进行了有关数集的研究。始时，人们仅进行了有关数集的研究。18761883年，年，康托尔康托尔(

3、Georg Cantor)发表了一系列有关集合论研究的文章，发表了一系列有关集合论研究的文章，奠定了集合论的深厚基础。集合论在奠定了集合论的深厚基础。集合论在程序语言、数据结构、编译原理、数程序语言、数据结构、编译原理、数据库与知识库、形式语言和人工智能据库与知识库、形式语言和人工智能等领域都得到了广泛的应用，并且还等领域都得到了广泛的应用，并且还得到了发展。得到了发展。康托尔康托尔河南工业大学离散数学课程组河南工业大学离散数学课程组第4页第四章内容（自学）第四章内容（自学）第三章内容（重点）第三章内容（重点）第二篇第二篇 集合论集合论主要包括如下内容：主要包括如下内容：n集合论初步集合论初步

4、n二元关系二元关系n函数函数n实数集合与集合的基数实数集合与集合的基数河南工业大学离散数学课程组河南工业大学离散数学课程组第5页第三章第三章 集合与关系集合与关系n本章的主要内容本章的主要内容n3-1 集合的概念和表示法集合的概念和表示法n3-2 集合的运算集合的运算n3-3 包含排斥原理包含排斥原理*n3-4 序偶和笛卡尔积序偶和笛卡尔积n3-5 关系和表示关系和表示n3-6 关系的性质关系的性质（重点）（重点）n3-7 复合关系和逆关系复合关系和逆关系n3-8 关系的闭包关系的闭包（重点）（重点）n3-9 集合的划分和覆盖集合的划分和覆盖n3-10 等价关系与等价类等价关系与等价类（重点）

5、（重点）n3-11 相容关系相容关系n3-12 序关系序关系河南工业大学离散数学课程组河南工业大学离散数学课程组第6页1-2节的内容提要节的内容提要集合间的关系集合间的关系3特殊集合特殊集合4集合的概念集合的概念1集合的概念集合的概念1集合的表示方法集合的表示方法2集合的表示方法集合的表示方法2无限集合无限集合5集合的运算集合的运算5河南工业大学离散数学课程组河南工业大学离散数学课程组第7页1-2节学习要求节学习要求重点掌握重点掌握一般掌握一般掌握11 1 集合的概念集合的概念及集合间关系及集合间关系2 2 集合的表示集合的表示3 3 集合运算及集合运算及定律定律4 4 幂集幂集P(A)P(A

6、) 21 1 集合的归纳集合的归纳法表示法表示2 2 集合的对称集合的对称差运算差运算 河南工业大学离散数学课程组河南工业大学离散数学课程组第8页3-1 集合集合n一、集合的概念一、集合的概念n集合集合（SET）：）：n即是由一些即是由一些确定确定的的彼此不同彼此不同的客体（事物）汇集的客体（事物）汇集到一起组成一个整体，称为集合。到一起组成一个整体，称为集合。n讨论：讨论：n客体：泛指一切，可以是具体的、抽象的。客体：泛指一切，可以是具体的、抽象的。n元素元素(element，成员，成员)：n 即组成集合的客体，称之为元素。即组成集合的客体，称之为元素。n二、集合的记法二、集合的记法n通常用

7、带通常用带(不带不带)标号的大写字母标号的大写字母A、B、C、.、A1、 B1 、C1 、.、X、Y、Z、.表示表示集合集合；n通常用带（不带）标号的小写字母通常用带（不带）标号的小写字母a、b、c、.、a1、 b1 、c1 、.、x、y、z、.表示表示元素元素。河南工业大学离散数学课程组河南工业大学离散数学课程组第9页固定的符号固定的符号0, 1, 2, 自然数集合自然数集合N, -2, -1, 0, 1, 2, 整数集合整数集合 Ip/q,p,q是整数，且是整数，且q0 有理数集合有理数集合 Q 实数集合实数集合 R复数集合复数集合 C河南工业大学离散数学课程组河南工业大学离散数学课程组第

8、10页三、集合与元素的关系三、集合与元素的关系n客体客体a与集合与集合A之间的关系只能是之间的关系只能是属于属于和和不属于不属于之一。之一。na是集合是集合A的元素或的元素或a属于属于集合集合A，记为记为a A，称称a是是A的的成员，成员，A包含包含a，a在在A中。中。na不是集合不是集合A的元素或的元素或a不属于不属于集合集合A，记为记为a A，或者，或者 (a A)，称称a不是不是A的成员，的成员，A不包含不包含a，a不在不在A中。中。例如，例如，对元素对元素2和自然数集合和自然数集合N，就有，就有2属于属于N，即，即 2 N， 对元素对元素-2和自然数集合和自然数集合N，就有，就有-2不

9、属于不属于N，即，即 -2 N。n有限集：有限集：组成集合的元素个数是有限的。组成集合的元素个数是有限的。n|A|：有限集合：有限集合A中元素的个数。中元素的个数。n无限集：无限集：组成集合的元素个数是无限的。组成集合的元素个数是无限的。河南工业大学离散数学课程组河南工业大学离散数学课程组第11页四、集合的表示方法四、集合的表示方法n 集合是由它包含的元素完全确定的，为了表集合是由它包含的元素完全确定的，为了表示一个集合，通常有：示一个集合，通常有： 枚举法（列举法）枚举法（列举法） 谓词表示法（隐式法、叙述法）谓词表示法（隐式法、叙述法）文氏文氏(Venn)图图-辅助的集合的表示方法辅助的集

10、合的表示方法河南工业大学离散数学课程组河南工业大学离散数学课程组第12页1、枚举法（显式表示法）、枚举法（显式表示法）n就是把集合的元素（全部或部分）写在花括号的里面，就是把集合的元素（全部或部分）写在花括号的里面，每个元素仅写一次，不考虑顺序，并用每个元素仅写一次，不考虑顺序，并用”,”分开分开。例例 （1）命题的真假值组成的集合：）命题的真假值组成的集合：S=T,F （2）Aa，e，i，o，u河南工业大学离散数学课程组河南工业大学离散数学课程组第13页在使用中，分两种情况：在使用中，分两种情况：（1）当集合中元素个数有限且较少时，将元素全部写出。当集合中元素个数有限且较少时，将元素全部写出

11、。 例例1：设集合：设集合A是由绝对值不超过是由绝对值不超过3的整数组成。的整数组成。 A=-3, -2, -1, 0, 1, 2, 3（2）当集合当集合A元素的个数元素的个数无限无限或或有限但个数较多有限但个数较多时，不时，不能或不需要一一列举出来，只要写出少数元素，以显能或不需要一一列举出来，只要写出少数元素，以显示出它的规律。（示出它的规律。（当规律不明确，不能用此方法当规律不明确，不能用此方法）。）。 例例2：设集合：设集合B是由自然数的平方构成的集合。是由自然数的平方构成的集合。 B = 0, 1, 4, 9, 16, , n2, 适用场景：适用场景：u一个集合仅含有限个元素。一个集

12、合仅含有限个元素。u一个集合的元素之间有明显关系一个集合的元素之间有明显关系 。河南工业大学离散数学课程组河南工业大学离散数学课程组第14页2、谓词表示法（隐式法、叙述法）、谓词表示法（隐式法、叙述法）n用用谓词谓词描述集合中描述集合中元素的属性元素的属性，称为谓词表示法（叙述法、，称为谓词表示法（叙述法、隐式法）隐式法）n一般表示方法：一般表示方法：Ax|P(x)n若个体域内，客体若个体域内，客体a使得使得P(a)为真，则为真，则aA，否则，否则a A。n例如：例如：n大于大于10的整数的集合：的整数的集合： S=x| xIx10)n命题的真假值组成的集合：命题的真假值组成的集合：S=F,T

13、=x|x=Fx=Tn适用场景：适用场景：n一个集合含有很多或无穷多个元素；一个集合含有很多或无穷多个元素；n一个集合的元素之间有容易刻画的共同特征。一个集合的元素之间有容易刻画的共同特征。n其其突出优点突出优点是原则上不要求列出集合中全部元素，而只要是原则上不要求列出集合中全部元素，而只要给出该集合中元素的特性。给出该集合中元素的特性。P(x)是谓词公式是谓词公式，x具有的性质具有的性质P代表元素代表元素河南工业大学离散数学课程组河南工业大学离散数学课程组第15页A3、文氏、文氏(Venn)图图-辅助的集合的表示方法辅助的集合的表示方法n文氏文氏(Venn)图是一种利用平面上的点构成的图图是一

14、种利用平面上的点构成的图形来形象展示集合的一种方法，用一个矩形的形来形象展示集合的一种方法，用一个矩形的内部表示全集，其他集合用矩形内的园面或一内部表示全集，其他集合用矩形内的园面或一封闭曲线圈成的面积来表示。封闭曲线圈成的面积来表示。U河南工业大学离散数学课程组河南工业大学离散数学课程组第16页说明：说明：n 集合中的元素都是不同的，凡是相同集合中的元素都是不同的，凡是相同的元素，均视为同一个元素；的元素，均视为同一个元素；n1,1,2=1,2n 一旦给定了集合一旦给定了集合A，对于任意客体，对于任意客体a，可以准确地判定可以准确地判定a是否在是否在A中。中。n 集合中的元素是没有顺序的。集

15、合中的元素是没有顺序的。n 2,1=1,2集合的三大特征集合的三大特征1、互异性互异性2、确定性确定性3、无序性无序性集合中的元素可以是集合。集合中的元素可以是集合。如如 S=a,1,2,p,q河南工业大学离散数学课程组河南工业大学离散数学课程组第17页同一个集合可以用不同的表示方法：同一个集合可以用不同的表示方法：例例n方程方程x2-1=0的所有实数解的集合的所有实数解的集合A；n谓词法：谓词法：nA=x|x Rx2-1=0或或nA=x|x是实数且是实数且x2-1=0n枚举法：枚举法：nA=1，-1河南工业大学离散数学课程组河南工业大学离散数学课程组第18页五、集合与集合的关系五、集合与集合

16、的关系n（一）包含关系（一）包含关系n（二）相等关系（二）相等关系n（三）真包含关系（三）真包含关系河南工业大学离散数学课程组河南工业大学离散数学课程组第19页“包含关系包含关系” 的谓词表示：的谓词表示： A B B A ( x)(xAxB)（一）包含关系（一）包含关系n 例：设例：设A = ADA, BASIC, PASCAL ， B = BASIC, PASCAL, ADA,C,JAVA定义：定义： A包含在包含在B内，内，A包含于包含于B，B包含包含A 设设A，B是任意两个集合，是任意两个集合，n若若A的每个元素都是的每个元素都是B的元素，的元素，则称则称A是是B的子集的子集(Subs

17、et)，也称，也称A包含在包含在B内，内，B包含包含A， n记作记作B A 或或A B，n若若A不被不被B所包含，则记作所包含，则记作A B 。显然，显然，对任意集合对任意集合A，都有都有A A。 AB河南工业大学离散数学课程组河南工业大学离散数学课程组第20页（二）相等关系（二）相等关系n定义定义nAB当且仅当当且仅当A与与B具有相同的元素，否则，具有相同的元素，否则，A B。集合集合A, B中的中的元素完全相同元素完全相同，称这样的，称这样的两个两个集合集合相等相等。 n1,2,4=1,4,2 1,2,4n定理定理3-1.1 n 设设A和和B是任意两个集合，是任意两个集合，A=BA B且且

18、B A 。 n集合相等的谓词表示：集合相等的谓词表示：nA=B( x)(xAxB) 河南工业大学离散数学课程组河南工业大学离散数学课程组第21页定理定理3-1.1 A=B A B且且 B A。n证明证明：n(1)证：证：若若A B且且 B A，则，则A=B。(反证法反证法)n 已知已知A B且且 B A，假设，假设AB，n 则则至少有一个元素至少有一个元素x，使得使得xA而而x B；或者；或者xB而而x A。n 如果如果xA而而x B，则与，则与A B矛盾。矛盾。n 如果如果xB而而x A，则与，则与 B A矛盾。矛盾。n 所以所以A=B。n(2)证：证：若若A=B ，则，则A B且且 B A

19、 。n若若A=B，则两个集合有相同的元素，则两个集合有相同的元素，n即即( x)(xAxB) 为真，且为真，且( x)(xBxA) 为真，即为真，即必有必有A B且且 B A。n所以，所以， A=B A B且且 B A。该定理是证明两个集合相等的基本思路和依据。该定理是证明两个集合相等的基本思路和依据。河南工业大学离散数学课程组河南工业大学离散数学课程组第22页集合相等的谓词定义集合相等的谓词定义 A=BnA B B An( x)(xAxB) ( x)(xBxA)n( x)(xAxB) (xBxA)n( x)(xAxB) A=B( x)(xAxB)河南工业大学离散数学课程组河南工业大学离散数学

20、课程组第23页（三）真包含关系（三）真包含关系定义定义1.2.2 ：A真包含于真包含于Bn设设A,B是任意两个集合，是任意两个集合，集合集合A中的每一个元素都中的每一个元素都属于属于B，但集合，但集合B中至少有一个元素不属于中至少有一个元素不属于A。 则称则称A是是B的的真子集真子集(Proper Subset)，记作，记作A B，n如果如果A不是不是B的真子集，则记作的真子集，则记作A B。“真包含关系真包含关系”的谓词表示：的谓词表示：nA BA B ABnA B ( x)(xAxB) ( x)(x B x A)对任意对任意x，如，如x A，则则x B，并且存在，并且存在x B，但是但是x

21、 A。河南工业大学离散数学课程组河南工业大学离散数学课程组第24页自学自学 真包含关系的谓词定义：真包含关系的谓词定义： A BA B ABn( x)(xAxB) ( x)(xAxB)n( x)(xAxB) ( ( x)(xAxB) ( x)(xBxA)n( x)(xAxB) ( x)(xAxB) ( x)(xAxB) ( x)(xBxA)n( x)(xAxB) ( x)(xB x A)n集合集合A中的每一个元素都属于中的每一个元素都属于B，但集合，但集合B中至少中至少有一个元素不属于有一个元素不属于A。河南工业大学离散数学课程组河南工业大学离散数学课程组第25页六、几个特殊集合六、几个特殊集

22、合n1、全集、全集n2、空集、空集n3、幂集、幂集河南工业大学离散数学课程组河南工业大学离散数学课程组第26页1、全集、全集n定义定义 在一个在一个相对固定的范围相对固定的范围内，内，包含此范围内所包含此范围内所有客体的集合有客体的集合，称为，称为全集全集或或论集论集(Universal Set)，用用U或或E表示。表示。 n E=x| P(x) P(x) 其中：其中：P(x)为任何谓词。为任何谓词。n用文氏图描述如下用文氏图描述如下:U六、几个特殊集合六、几个特殊集合一般地，根据讨论问题的范围，选一般地，根据讨论问题的范围，选择对问题讨论方便的集合作为全集。择对问题讨论方便的集合作为全集。在

23、实际应用中，常常把某个适当大在实际应用中，常常把某个适当大的集合看成全集。的集合看成全集。河南工业大学离散数学课程组河南工业大学离散数学课程组第27页2、空集、空集n定义定义：n不含任何元素的集合叫做不含任何元素的集合叫做空集空集(Empty Set)，记作，记作。 n空集可以符号化为空集可以符号化为n =x| P(x) P(x)= 其中：其中：P(x)为任何谓词。为任何谓词。 设设A = x|(xR) (x20)，试列举，试列举A中的所有元素。中的所有元素。解：解： A = 。与与: 是不含任何元素的集合，是不含任何元素的集合，是含一个元素是含一个元素的集合。的集合。 = ， |=0 ，|=

24、1， 定理定理3-1.23-1.2（1 1）空集是一切集合的子集；）空集是一切集合的子集；（2 2）空集是绝对唯一的。）空集是绝对唯一的。河南工业大学离散数学课程组河南工业大学离散数学课程组第28页反证法反证法n（1）空集是一切集合的子集；）空集是一切集合的子集； An证明：证明：n因为因为( x)(xxA)为永真式，所以为永真式，所以 A。n（2）空集是绝对唯一的。）空集是绝对唯一的。n分析：分析： 对对“唯唯一性一性”的证明通常采用的证明通常采用反证法反证法。n即假设即假设“不不唯唯一一”，得出矛盾，从而说明结论正确。，得出矛盾，从而说明结论正确。n证明：（反证法）证明：（反证法）n假设空

25、集不唯一，即存在假设空集不唯一，即存在1和和2两个空集，且两个空集，且12，n因为是因为是1空集，则由性质空集，则由性质1得得 1 2 。n因为是因为是2空集，则由性质空集，则由性质1得得 2 1 。n所以所以1=2 。n与假设矛盾，所以空集是唯一的。与假设矛盾，所以空集是唯一的。 定理定理3-1.2 的证明的证明 河南工业大学离散数学课程组河南工业大学离散数学课程组第29页3、幂集、幂集引例：求集合的子集及子集的个数引例：求集合的子集及子集的个数例例 A 子集子集 子集个数子集个数n 1na ,a 2na,b ,a,b,a,b 4na,b,c ,a,b,c,a,b, a,c, b,c, a,

26、b,c 8n一般来说，对于一般来说，对于n个元素的集合个元素的集合A，它的不同的子集，它的不同的子集总数有：总数有：n(1+1)n2nn所以，所以，n元集共有元集共有2n个子集。个子集。Cn2Cn0Cn1Cnn河南工业大学离散数学课程组河南工业大学离散数学课程组第30页一般来说，对于一般来说，对于n个元素的集合个元素的集合A，它的不同的子，它的不同的子集总数有集总数有 Cn2Cn0Cn1CnnCn2Cn0Cn1Cnnxn-1yxn-2y2xnynCn2Cn0Cn1Cnn而而(x+y)n=令令x=y=1时得时得 2n=所以不同子集总数有所以不同子集总数有 2n河南工业大学离散数学课程组河南工业大

27、学离散数学课程组第31页幂集幂集定义：幂集定义：幂集(power set)n给定集合给定集合A，由，由A的的所有子集为元素所有子集为元素组成的集组成的集合称为合称为A的的幂集幂集(power set)，记为，记为(A) 。幂集的幂集的符号化表示为符号化表示为 n(A)x| x A例如：计算下列幂集例如：计算下列幂集:(1)()；(2) (a) ; (3)()。n解解 ：(1) () = ；n (2) (a)=,an (3)() = , ；n定理定理3-1.3 n若有限集合有若有限集合有n个元素，则其幂集个元素，则其幂集(A)共有共有2n个元个元素。素。|A|=n,| (A)|= 2n河南工业大

28、学离散数学课程组河南工业大学离散数学课程组第32页n子集子集Bijk编码编码 a,b,c n ijk是二进制数，是二进制数， Bi j k A, ni=1，aBijk；i=0，a Bijk； nj=1 ，bBijk；j=0，b Bijk ；nk=1，cBijk；k=0，c Bijk 。 n例：例：a,b,c 则则nB000 B001 B010 B011 B100 B101 B110 B111n c b b,c a a,c a,b a,b,cn B0 B1 B2 B3 B4 B5 B6 B7n故：故： (A)= ,c,b,b,c ,a, a,c ,a,b, a,b,cn例：例：a,b,c,dn

29、B0 = B00 =， B1 = B01 =b,c,d，B2 = B10= a， B3 = B11 =a,b,c,dn 故：故：(A)= , b,c,d, a,a,b,c,d利用子集利用子集Ba1a2a3an的下标编码求集合的下标编码求集合A的幂集，的幂集，a1a2a3an为二进制编码，为二进制编码，n为集合为集合A的元素个数。的元素个数。河南工业大学离散数学课程组河南工业大学离散数学课程组第33页n设设A=， B=(A)n(A)= ,n在求在求(A)时，时，实际上是将实际上是将,中的元素分别看中的元素分别看成成=a ,=b, 于是于是,=a,bnB= (A)= (a,b) =B0, B1,B

30、2 ,B3 n =B00, B01,B10 ,B11n=, b, a, a,bn然后再将然后再将a,b代回即可代回即可nB=(A)= (,)=, ,n以后熟悉后就可以直接写出。以后熟悉后就可以直接写出。练习练习 P86 (7)河南工业大学离散数学课程组河南工业大学离散数学课程组第34页3-2 集合的运算集合的运算一、定义一、定义 设设A、B是两个集合，是两个集合，n =x|xAxB xAB xAxBn =x|x A x B xAB xAxBn =x|xAx B xA-B xAx Bn =x|xEx A= x|x A n xA x A (xA) =x|(x A) (x B) (x B) (x A

31、)A B=(A-B)(B-A) A B=(AB)-(AB) EA B差集差集EA B交集交集补集补集EAA A并集并集EA B(1)并集并集 AB (2)交集交集 AB (3)差集差集 A-B (4)补集补集 A(5)对称差集对称差集A B河南工业大学离散数学课程组河南工业大学离散数学课程组第35页例：例：A=4,1,2,3,B=3,1,2,3,4,1,2,1n则：则：A B=4,1,2,3=AnAB=4,1,2,3,1,2,3,1=BnA-B=nB-A=1,2,3,1河南工业大学离散数学课程组河南工业大学离散数学课程组第36页二、集合的运算律二、集合的运算律等幂律等幂律: AA=A；AA=A

32、； 交换律交换律: AB=BA;AB=BA结合律结合律: A(BC)=(AB)C； A(BC)=(AB)C；恒等律恒等律: A=A； AE=A； 零律零律: AE=E； A=；分配律分配律: A(BC)=(AB)(AC) A(BC)=(AB)(AC)吸收律吸收律: A(AB)=A;A(AB)=A； 集合的运算律是指集合的交、并、补、差等运集合的运算律是指集合的交、并、补、差等运算的主要性质，也称为集合的基本定律。算的主要性质，也称为集合的基本定律。河南工业大学离散数学课程组河南工业大学离散数学课程组第37页定理定理n否定律：否定律： A=A ；n德摩根定律：德摩根定律： (AB)=AB n (

33、AB)=AB n矛盾律：矛盾律： A A；n排中律：排中律： A A E。n其他：其他：n A - A = ；n A - B = A - (AB)；n A - B =A B;n (A - B) - C = A - (BC)；n A(B-A) = AB；EA B河南工业大学离散数学课程组河南工业大学离散数学课程组第38页三、证明集合相等的四种方法三、证明集合相等的四种方法n方法一：方法一：命题演算法（逻辑等价式和推理规则）命题演算法（逻辑等价式和推理规则）n方法二：方法二：等式代入法等式代入法(假设交换律、分配律、同一假设交换律、分配律、同一律、零律已经成立律、零律已经成立)n方法三：方法三：证

34、明出：证明出：A B 且且 B A，则，则A=B。n方法四：方法四：反证法反证法河南工业大学离散数学课程组河南工业大学离散数学课程组第39页三、证明集合相等的四种方法三、证明集合相等的四种方法方法一：方法一：命题演算法（逻辑等价式和推理规则）命题演算法（逻辑等价式和推理规则）n例：证明例：证明A(AB)=A （吸收律）（吸收律）n证证 任取任取x, x (A (A B) n x Ax (A B)n x A (x Ax B) n x A n因此得因此得A (A B) = A。方法二：方法二：等式代入法等式代入法(假设交换律、分配律、同一律、假设交换律、分配律、同一律、零律已经成立零律已经成立)n

35、例例 证明吸收律证明吸收律 A (A B) = (A E) (A B) n= A (E B) = A E = A河南工业大学离散数学课程组河南工业大学离散数学课程组第40页集合等式的证明集合等式的证明n方法三：方法三：证明出：证明出：A B 且且 B A，则，则A=Bn依据：依据：n定理定理3-1.1 A=B，当且仅当当且仅当 A B且且 B A。n例如：例如： （P91定理定理3-2.5的证明方法）的证明方法）n方法四：方法四：反证法反证法n 假设不等，推出矛盾。假设不等，推出矛盾。河南工业大学离散数学课程组河南工业大学离散数学课程组第41页分析：分析： ( x)(xAB xA) ( x)(

36、xAxB)证明：证明：AB=A，n ( x)(xAB xA)n( x)(xAB xA)(xA xAB)n( x)(x ABxA)(x AxAB)n( x)( (xAxB)xA)n (x A(xAxB)n( x)(x Ax B)xA)n (x A(xAxB)n( x)(T(T ( x A xB)n( x)( x A xB)n( x)(xAxB)n A B证明证明P90定理定理3-2.3： AB=A A B河南工业大学离散数学课程组河南工业大学离散数学课程组第42页四、证明四、证明A B的四种方法：的四种方法：n方法一：方法一：A和和B是用枚举方式定义的：是用枚举方式定义的：n依次检查依次检查A的

37、每个元素是否在的每个元素是否在B中出现。中出现。n方法二：方法二：通过集合运算判断通过集合运算判断A B：n即即AB = B, AB = A, A B = 三个等式中有一个三个等式中有一个为真，则为真，则A B。n方法三：方法三：通过文氏图判断集合的包含（注意这里是通过文氏图判断集合的包含（注意这里是判断，而不是证明）判断，而不是证明）n方法四：方法四：A和和B是谓词定义的，且是谓词定义的，且A和和B中元素的性中元素的性 质分别为质分别为P和和Q：（即：（即：A=x|P(x) B=x|Q(x)n利用利用 的定义证明（按定义证明法）。的定义证明（按定义证明法）。河南工业大学离散数学课程组河南工业

38、大学离散数学课程组第43页按定义证明按定义证明的方法的方法n若定义中有若定义中有“若若则则”来描述的，则来描述的，则在证明时在证明时应采用离散数学应采用离散数学中特有的中特有的按定义证明方法按定义证明方法n即证明时，首先叙述即证明时，首先叙述定义定义的前半部分的前半部分“若若”，将这部分的内容，将这部分的内容称为称为“附加的已知条件附加的已知条件”，此时利用该，此时利用该“附加的已知条件附加的已知条件”和和题目本身所给的题目本身所给的已知条件已知条件证明出定义的后半部分证明出定义的后半部分“则则”，这部，这部分的内容称为分的内容称为定义中的结论定义中的结论。n这种证明问题的方法在于：这种证明问

39、题的方法在于：证明时不能单纯利用证明时不能单纯利用题目题目所给的所给的已知条件已知条件，而应同时利用，而应同时利用定义中的定义中的“已知已知”，推出的并非整，推出的并非整个定义，而是个定义，而是定义中的结论定义中的结论。n这与一般的证明思路：这与一般的证明思路：已知已知中间结果中间结果结论结论是完全不同的。是完全不同的。本章的证明大部分都采用本章的证明大部分都采用按定义证明方法按定义证明方法。利用利用 的定义证明：的定义证明： A B定义：定义： A B( x)(xAxB)证明：证明：假设假设( x)(xA)，利用题目中的，利用题目中的已知条件和已有的定理和已知条件和已有的定理和公理去推出即公

40、理去推出即( x)(x B) ，从而证明，从而证明A B。注意：若已知注意：若已知A B，则可以设则可以设( x)(xA) ( x)(x B) 河南工业大学离散数学课程组河南工业大学离散数学课程组第44页六、证明集合不等的方法六、证明集合不等的方法证证 A B： n方法一：方法一：举例举例 或或 画文氏图示意。画文氏图示意。n方法二：方法二：转化为证明转化为证明 逻辑判断式不等价。逻辑判断式不等价。pAB ( x)(x A且且x B) ( x)(x B且且x A)n方法三：方法三：反证法，假设反证法，假设A=B，推出矛盾。，推出矛盾。五、判断客体五、判断客体a是否是集合是否是集合A元素的基本方

41、法：元素的基本方法：n把把a作为一个整体，检查它在作为一个整体，检查它在A中是否出现。中是否出现。河南工业大学离散数学课程组河南工业大学离散数学课程组第45页七、证明集合七、证明集合A是空集的方法是空集的方法 方法一：方法一：其逻辑判断条件是永假。其逻辑判断条件是永假。 =x| P(x) P(x)方法二：方法二：用反证法：设用反证法：设 a A，引出矛盾的结果。引出矛盾的结果。河南工业大学离散数学课程组河南工业大学离散数学课程组第46页n自学自学n求证求证(A-B)-C=(A-C)-(B-C)证明：证明： 任取任取x， x(A-C)-(B-C)n x(A-C)x (B-C)n (xAx C)

42、(xBx C) n (xAx C) (x BxC)n (xAx Cx B)(xAx C xC)n xAx Cx Bn xAx Bx Cn (xAx B)x Cn xA-Bx Cn x(A-B)-Cn所以所以 (A-B)-C=(A-C)-(B-C)河南工业大学离散数学课程组河南工业大学离散数学课程组第47页n自学自学nA-(BC)=(A-B)(A-C)nA-(BC)=(A-B)(A-C)证明：任取证明：任取xA-(BC) nxAx (BC)nxA (xBxC) nxA(x Bx C)n(xAx B)(xAx C )nxA-BxA-Cnx(A-B)(A-C) n所以所以 A-(BC)=(A-B)(

43、A-C)nA(B-C)=(AB)-(AC)n但但对对- 是不可分配的，是不可分配的，n如如A(A-B)=A， 而而(AA)-(AB)=注意注意:这不是这不是分配律分配律河南工业大学离散数学课程组河南工业大学离散数学课程组第48页自学自学n证明：证明：A B B An证明证明： A B ( x)(xAxB)n ( x)(x Bx A)x(xBxA) n B An A B B An证明：德摩根定律证明：德摩根定律n(1)(AB)=AB n(2)(AB)=AB n证明证明: (1)：任取：任取x (AB)n x (AB) x AB (xAxB)n (x A)(x B)(xA)(xB)n x (AB)

44、 n(AB)=AB 河南工业大学离散数学课程组河南工业大学离散数学课程组第49页自学自学nA=B 当且仅当当且仅当AB=E且且 AB=证明：证明： (AB=E)(AB=)n( x)(xABxE) (PT=P)n ( x)(xABx) (PF= P)n( x)(xABT) x(xABF)n( x)(xAB (xAB)n( x)(xAxB) (xAxB)n( x)(xAxB)(x Ax B)n( x)(x AxB)(xBx A)n( x)(xAxB)(xBxA)n( x)(xAxB)nA=B河南工业大学离散数学课程组河南工业大学离散数学课程组第50页设设A是有穷集合，是有穷集合， 其元素个数为其元

45、素个数为|A|。n这节主要解决这节主要解决集合的计数问题集合的计数问题。例如有。例如有AB两个商店，两个商店，A店经营店经营1000种商品，种商品，B店经营店经营1200种商品，其中有种商品，其中有100种商品两个商店都经营，问两个商店共经营多少种商品两个商店都经营，问两个商店共经营多少种商品？种商品？n显然显然 |AB|=|A|+|B|-|AB|n如果有如果有ABC三个有限集合，则三个有限集合，则n|ABC|n=|AB|+|C|-|(AB)C|n=|A|+|B|-|AB|+|C|-|(AC)(BC)|n=|A|+|B|-|AB|+|C|-(|AC|+|BC|-|ABC|)n=|A|+|B|+

46、|C|-|AB|-|AC|-|BC|+|ABC| ABABAB*3-3. 包含排斥原理包含排斥原理ABCU河南工业大学离散数学课程组河南工业大学离散数学课程组第51页n一般地一般地，有，有n个有限集合个有限集合A1, A2,. An,则则niinnkjikjinjijiniiniiAAAAAAAA111111) 1(.*3-3. 包含排斥原理包含排斥原理河南工业大学离散数学课程组河南工业大学离散数学课程组第52页n令令U为全集，为全集，E、F、J分别为会英语、法语和日语人分别为会英语、法语和日语人的集合。的集合。n|U|=170 |E|=120 |F|=80 |J|=60 n|EF|=50 |

47、EJ|=25 |FJ|=30 |EFJ|=10n|EFJ|=|E|+|F|+|J|-|EF|-|EJ|-|FJ|+|EFJ|n= 120806050253010n165n|U-(EFJ)|=170-165=5 n即有即有5人不会这三种语言。人不会这三种语言。例例3-3.1某个研究所有某个研究所有170名职工，其中名职工，其中120人会英语，人会英语，80人会法语，人会法语，60人会日语，人会日语，50人会英语和法语，人会英语和法语，25人人会英语和日语，会英语和日语，30人会法语和日语，人会法语和日语，10人会英语、日人会英语、日语和法语。问有多少人不会这三种语言？语和法语。问有多少人不会这三

48、种语言？EFJ10U河南工业大学离散数学课程组河南工业大学离散数学课程组第53页n1.掌握集合的定义、谓词定义、证明方法。掌握集合的定义、谓词定义、证明方法。n2.掌握三个特殊集合，会求集合的幂集。掌握三个特殊集合，会求集合的幂集。n3.掌握集合的五种运算定义、计算方法、性质。掌握集合的五种运算定义、计算方法、性质。n*4.会用包含排斥原理解决集合计数问题会用包含排斥原理解决集合计数问题. n 作业：作业： 第第94页页d) b) 3.13.3小结小结河南工业大学离散数学课程组河南工业大学离散数学课程组第54页3.4 序偶与集合的笛卡尔积序偶与集合的笛卡尔积要求：要求：n1、理解概念；、理解概

49、念；n2、掌握序偶和笛卡尔积的定义和性质。、掌握序偶和笛卡尔积的定义和性质。河南工业大学离散数学课程组河南工业大学离散数学课程组第55页一、序偶与有序一、序偶与有序n元组元组n两个具有固定次序的客体两个具有固定次序的客体x、y组成序偶，也称为有组成序偶，也称为有序二元组，记作序二元组，记作；n称称x、y分别为序偶分别为序偶的第一，第二元素。的第一，第二元素。p固定次序固定次序是指调换第一和第二元素位置后，含义不同。是指调换第一和第二元素位置后，含义不同。n注意，注意， 第一、第一、 二元素二元素未必不同未必不同。1.定义定义：说明说明河南工业大学离散数学课程组河南工业大学离散数学课程组第56页

50、序偶的性质序偶的性质（1）当）当xy时，时，。 x,y=y,x（2）序偶二个元素可以重复，即）序偶二个元素可以重复，即也是序偶。也是序偶。 无无x,x（3）序偶中两个元素可以来自不同的集合。）序偶中两个元素可以来自不同的集合。：x A, yB x,y A（4）序偶与集合的统一：）序偶与集合的统一： = x,x,y（5）序偶相等的定义：）序偶相等的定义： ( x,y = u,v )(x=u)(y=v)由由序偶序偶相等的定义有相等的定义有 x+252x+y4 解得解得 x3,y-2。 解答解答例例 已知已知，求，求x和和y。 河南工业大学离散数学课程组河南工业大学离散数学课程组第57页序偶的推广：

51、序偶的推广： 有序有序N元组元组n 定义定义 由由N个元素个元素x1,x2,xn-1,xn按照一定的次序组成的按照一定的次序组成的N元元 组称为组称为有序有序N元组元组，记为，记为。 xi叫做该叫做该 n元组的第元组的第i个分量个分量i=1,n。n有序有序N元组与序偶的关系：元组与序偶的关系： =x1,x2,xn-1 ,xn n三元组三元组 x1, x2, x3 =x1, x2 , x3 n四元组四元组n x1, x2, x3, x4 =x1, x2, x3 , x4 = , x3, x4 n注意：注意：x1, x2 , x3 x1, x2, x3nx1, x2, x3 , x4 x1, x2

52、, x3, x4nx1, x2, x3, x4 , x5 x1, x2, x3, x4, x5例如：例如：a年年b月月c日日d时时e分分f秒，可用六元组表示秒，可用六元组表示河南工业大学离散数学课程组河南工业大学离散数学课程组第58页n定义：定义：两个两个n元组相等元组相等n设设 x1,x2,xn 与与 y1,y2,y n 是两个是两个n元组，如元组，如果果xi=yi，i=1,n，则称这两个，则称这两个n元组相等，记元组相等，记为为 x1,x2,xn = y1,y2,yn 。n用逻辑的方法表示为用逻辑的方法表示为 n ( x1,x2,xn = y1,y2,y n )n(x1= y1)(x2=

53、y2)(xn= yn)。 n 河南工业大学离散数学课程组河南工业大学离散数学课程组第59页二、集合的笛卡尔积二、集合的笛卡尔积引例引例 “斗兽棋斗兽棋”虎虎象象狮狮豹豹狼狼鼠鼠猫猫狗狗虎虎象象狮狮豹豹狼狼鼠鼠猫猫狗狗每个棋子可以看成一个序偶每个棋子可以看成一个序偶: , , , ,可看成是由可看成是由两种颜色的集合两种颜色的集合A和和8种动物的集合种动物的集合B做运算得做运算得到的到的。 A=红红,蓝蓝 B=象象,狮狮,虎虎,豹豹,狼狼,狗狗,猫猫,鼠鼠斗兽棋可记成集合：斗兽棋可记成集合：斗兽棋可记成集合：斗兽棋可记成集合：河南工业大学离散数学课程组河南工业大学离散数学课程组第60页补充的补充

54、的定义定义: A和和B的的笛卡尔积笛卡尔积或或直积直积n设设A、B是集合，由是集合，由A的元素为第一元素，的元素为第一元素，B的元素的元素为第二元素组成的为第二元素组成的所有所有序偶的集合序偶的集合，称为，称为A和和B的的笛卡尔积笛卡尔积或或直积直积，记作记作AB，即即n A B=|x Ay Bn A B x A y Bn A B x A y Bq例如：例如：qA表示某大学所有学生的集合，表示某大学所有学生的集合，B表示大学开设的表示大学开设的所有课程的集合。所有课程的集合。q则则AB可以用来表示该校学生选课的所有可能情可以用来表示该校学生选课的所有可能情况。况。1、集合的笛卡尔积的定义、集合

55、的笛卡尔积的定义河南工业大学离散数学课程组河南工业大学离散数学课程组第61页nA B=,nB A=,nA A=, ,n可见可见 ABBAn集合的笛卡尔积运算不满足交换律。集合的笛卡尔积运算不满足交换律。例：例： A=0,1，B=a,b，C=zn (A B) C=, z =,n A (B C)=0,1 , =0,0,1,1, (A B) C=,z| A B z C A (B C)=x,|x A B C,n可见可见 (A B) C A (B C)。n集合的笛卡尔积运算集合的笛卡尔积运算也不满足结合律。也不满足结合律。例：例： 设设A=0,1,2，B=a,b，求，求A B ， B A， A A 。|

56、A B |=6= |B A | |A A |=9河南工业大学离散数学课程组河南工业大学离散数学课程组第62页n1) 如果如果A、B都是有限集，且都是有限集，且|A|=m, |B|=n， 则则 |A B |=mn. n证明：由笛卡尔积的定义及排列组合中的乘法原证明：由笛卡尔积的定义及排列组合中的乘法原理，直接推得此定理。理，直接推得此定理。n 2) A = B= n 3) 对对和和满足分配律。满足分配律。 设设A,B,C是任意集合，则是任意集合，则n A (BC)= (A B)(A C)；n A (BC)= (A B)(A C)；n (AB) C= (A C)(B C)；n (AB) C= (A

57、 C)(B C)n4) 若若C,则则 A B(A C B C) (C A C B)。n5) 设设A,B,C,D为为非空集合非空集合，则，则 A B C DA CB D。（两个笛卡尔积具有。（两个笛卡尔积具有包含关系，则相应的分量也具有包含关系）包含关系，则相应的分量也具有包含关系）2、集合的笛卡尔积的性质、集合的笛卡尔积的性质河南工业大学离散数学课程组河南工业大学离散数学课程组第63页2、集合的笛卡尔积的性质、集合的笛卡尔积的性质（续）（续）求证：求证：A (BC)= (A B)(A C)n分析：分析： A (BC) ? (A B)(A C) n证明：证明：n任取任取 A (BC) nx A

58、y (BC) nx A (y By C) n(x A y B)(x A y C)n A B A C n (A B)(A C) n所以所以A (BC)= (A B)(A C)n其余可以类似证明其余可以类似证明。 A (BC) A (BC) (A B)(A C) (A B)(A C)A=a, B=1,2, C=2,3A (BC)= a 1,2,3=,A B= a 1,2=,A C= a 2,3=,(A B)(A C)=,A (BC)= (A B)(A C) 河南工业大学离散数学课程组河南工业大学离散数学课程组第64页即即 A B(A C B C) 类似可以证明类似可以证明 A B (C A C B

59、)。4) 若若C,则则 A B(A C B C) (C A C B).n证明证明: 证证A B(A C B C) n证：证：A B A C B C n设设A B,n任取任取 A Cn x A y C n (由由A B) nx B y Cn B Cn即即 B Cn 所以所以, A C B C。2、集合的笛卡尔积的性质、集合的笛卡尔积的性质（续）（续）证：证：(A C B C) A B 若若C, 任取任取y C, 任取任取x An x A y Cn A C n(由由A C B C)n B Cnx B y Cnx Bn 所以所以, A B。 A B x A y B A B ( x)(xA xB)河南

60、工业大学离散数学课程组河南工业大学离散数学课程组第65页 5) 设设A,B,C,D为为非空集合非空集合，则，则A B C DA CB D。n证明证明: 证：由证：由A B C D A CB D。n任取任取x A，任取，任取y B，n x A y Bn ABn(由由A B C D ) CDx C y D n即即 x C y D n 所以所以, A CB D.证：由证：由A C B D A B C D。n任取任取 AB n AB x A y Bn(由由A C，B D) x C y D CD n即即 CD n所以所以, A B C D 因此，因此，A B C DA CB D。2、集合的笛卡尔积的性质