离散数学关系课件.ppt

《离散数学关系课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第二章关系1在现实生活中,集合与集合之间还存在着某种联系，如同学关系、朋友关系等。这些关系正是各门学科所要研究的主要内容。离散数学从集合出发，主要研究集合之间的关系。本章内容主要研究二元关系。2本章主要内容：关系的基本概念关系的表示方法关系的运算关系的性质关系的闭包等价关系与划分偏序关系32.1关系的基本概念为了讨论关系，首先引入有序对和笛卡儿积两个概念。由两个元素a,b组成的集合{a,b}中，a和b是没有次序的。有时需要考虑有次序的两个元素，所以需要由两个元素组成新的东西，并且两个元素是有次序的。定义2.1两个元素a,b有次序地放在一起，称为一个有序对或序偶，记为(a,b)。在有序对(a

2、,b)中，a称为第一元素，b称为第二元素。且(a1,b1)=(a2,b2)当且仅当a1=a2且b1=b2。4定义2.2设A,B是两个集合，集合{(x,y)

3、x∈A且y∈B}称为A和B的笛卡儿积，也称卡氏积，记为A×B。用属于关系来表示就是：(x,y)∈A×B当且仅当x∈A且y∈B和(x,y)∉A×B当且仅当x∉A或y∉B。其中A称为第一集合，B称为第二集合。5例2.1设A={1,2,3},B={a,b}，求A×B。由笛卡儿积的定义可知有A×=×A=。又由有序对的性质可知，一般没有A×B≠B×A。A×B也是一个集合，所以可以和另一集合C作笛卡儿积(A×B)×C，类似地有A×(B×C)。

4、但是，一般没有(A×B)×C=A×(B×C)，且A×B中的元素既不是A中的元素，也不是B中的元素。6定理2.1如果B1A1，B2A2，则B1×B2A1×A2。7证明对(x,y)∈B1×B2，有x∈B1且y∈B2，又因为B1A1，B2A2，则x∈A1且y∈A2，所以(x,y)∈A1×A2，即B1×B2A1×A2。8定理2.2A,B,C是任意集合，则：(1)A×(B∪C)=(A×B)∪(A×C)，(B∪C)×A=(B×A)∪(C×A)。(2)A×(B∩C)=(A×B)∩(A×C)，(B∩C)×A=(B×A)∩(C×A)。(3)A×(B-C)=(A×B)-(A×C)，(B-C)×A

5、=(B×A)-(C×A)。9证明(1)对(x,y)∈A×(B∪C)，有x∈A且y∈B∪C，因此x∈A且(y∈B或y∈C)，当y∈B时，由x∈A和y∈B得(x,y)∈A×B，当y∈C时，由x∈A和y∈C得(x,y)∈A×C，所以(x,y)∈(A×B)∪(A×C)，即A×(B∪C)⊆(A×B)∪(A×C)。因为A⊆A，B⊆B∪C和C⊆B∪C得A×B⊆A×(B∪C)和A×C⊆A×(B∪C)，因此(A×B)∪(A×C)⊆A×(B∪C)。因此A×(B∪C)=(A×B)∪(A×C)成立。同理可证(B∪C)×A=(B×A)∪(C×A)。10(2)对(x,y)∈(A×B)∩(A×C)，有(x,y)∈A

6、×B且(x,y)∈A×C，所以（x∈A且y∈B）且（x∈A且y∈C）。由y∈B且y∈C得y∈B∩C，由x∈A且y∈B∩C得(x,y)∈A×(B∩C)。因此(A×B)∩(A×C)A×(B∩C)。因为A⊆A，B∩C⊆B和B∩C⊆C，所以有A×(B∩C)⊆A×B和A×(B∩C)⊆A×C成立，因此A×(B∩C)⊆(A×B)∩(A×C)。因此A×(B∩C)=(A×B)∩(A×C)。同理可证(B∩C)×A=(B×A)∩(C×A)。11(3)对(x,y)∈A×(B-C)，有x∈A且y∈B-C，所以x∈A且y∈B且yC。由x∈A且y∈B得(x,y)∈A×B，由yC得(x,y)A×C，所以(x,y

7、)∈(A×B)-(A×C)。因此A×(B-C)⊆(A×B)-(A×C)。对(x,y)∈(A×B)-(A×C)，有(x,y)∈A×B且(x,y)A×C，由(x,y)∈A×B得x∈A且y∈B，由x∈A和(x,y)A×C得yC，所以x∈A且y∈B且yC。由y∈B且yC得y∈B-C，所以(x,y)∈A×(B-C)。因此(A×B)-(A×C)⊆A×(B-C)。因此A×(B-C)=(A×B)-(A×C)。同理可证(B-C)×A=(B×A)-(C×A)。12定义2.3任给n≥2，n个元素a1，…,an有次序地放在一起，称为一个n元有序组，记为(a1，…，an)。为了体现n元有序组的次序，规定

8、(a1，…，an)=(b1,，…，bn)当且仅当任给1≤i≤n，都有ai=bi。n元有序组可以组成集合，特别地有n个集合的卡氏积。13定义2.4任给n≥2，A1，…，An是n个集合，集合{(x1,⋯,xn)

9、任给1≤i≤n，都有xi∈Ai}称为A1，…，An的卡氏积，记为A1×…×An。任给1≤i≤n，Ai称为这个卡氏积的第i个集合。14定义2.5如果一个集合满足以下条件之一：（1）集合非空，且它的元素都是有序对；（2）