离散数学-第五章 关系课件.ppt

《离散数学-第五章 关系课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5章关系Relation关系是在集合的基础上定义的一个重要的概念，与集合的概念一样，关系的概念在计算机科学中也是最基本的。它主要反映元素之间的联系和性质，在计算机科学中有重要的意义，如有限自动机和形式语言，编译程序设计，信息检索，数据结构以及算法分析和程序设计的描述中经常出现。第5章关系内容提要：1.笛卡尔积及关系的概念2.关系的性质3.关系矩阵和关系图4.复合关系与逆关系5.关系的闭包6.等价关系及证明7.分划、覆盖、等价类、商集的概念8.偏序与哈斯图9.关系在计算机科学中的应用第5章关系5.1.1笛卡

2、尔积定义5.1由n个具有给定次序的个体a1,a2,…,an组成的序列，叫做有序n元组，记作(a1,a2,…,an)。其中ai（i=1,2,…,n）叫做该有序n元组的第i个坐标。有序n元组与前面所讲的n个元素的集合这两个概念是两个不同的概念，不同在于集合中这n个元素是无序的，而在有序n元组中，必须对这n个元素指定一个次序。因此对任意给定的n个个体，他们只能组成一个n元素的集合，但却可以组成n!个不同的有序n元组。5.1关系及其表示5.1.1笛卡尔积另外，有序n元组的一种常见的特殊情形是n=2。有序n元组（a,

3、b）又被称为序偶。序偶的一个熟悉的例子是平面上点的笛卡尔坐标表示。例如，序偶（1,3），（2,4），（5,3）等均表示平面上不同的点。定义5.2设(a1,a2,…,an)和(b1,b2,…,bn)两个有序n元组，如果ai=bi(i=1,2,…,n)，则称这两个有序n元组相等，记为(a1,a2,…,an)=(b1,b2,…,bn)。5.1关系及其表示5.1.1笛卡尔积定义5.3设A1,A2,…,An是任意集合，则称集合{(a1,a2,…,an)

4、aiAi,i=1,2,…,n}为集合A1,A2,…,An的笛卡

5、尔积，记为A1A2…An。5.1关系及其表示5.1.1笛卡尔积例5.1设A={a,b}，B={1,2,3}，求AB，BA，AA，BB。解AB={(a,1),(a,2),(a,3),(b,1),(b,2),(b,3)}BA={(1,a),(1,b),(2,a),(2,b),(3,a),(3,b)}AA={(a,a),(a,b),(b,a),(b,b)}BB={(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)}5.1关系及其表示5.

6、1.1笛卡尔积例5.2设A=，B={1,2,3}，求AB，BA。解AB=B=，BA=B=5.1关系及其表示5.1.1笛卡尔积定理5.1设A,B为任意两个有限集，则

7、AB

8、=

9、A

10、•

11、B

12、推论5.1设A1,A2,…,An为任意n个有限集，则

13、A1A2…An

14、=

15、A1

16、•

17、A2

18、•…•

19、An

20、5.1关系及其表示5.1.1笛卡尔积定理5.2设A,B,C,D为任意四个非空集合，则(1)ABCD当且仅当AC,BD；(2)AB=CD当且仅当A=C,B=D。定理5.3设A,B,

21、C为任意三个集合，则(1)A(B∪C)=(AB)∪(AC)(2)(A∪B)C=(AC)∪(BC)(3)A(B∩C)=(AB)∩(AC)(4)(A∩B)C=(AC)∩(BC)(5)A(B-C)=(AB)-(AC)(6)(A-B)C=(AC)-(BC)5.1关系及其表示5.1.1笛卡尔积例5.3设A,B,C和D是任意的集合，试问下列等式是否成立？为什么？(1)(A∩B)(C∩D)=(AC)∩(BD)解成立。因为对于任意的（x,y），设(x,y)(A∩B)(C∩D)

22、xA∩ByC∩DxAxByCyD(x,y)A×C(x,y)B×D(x,y)(AC)∩(BD)5.1关系及其表示5.1.1笛卡尔积(2)(A∪B)(C∪D)=(AC)∪(BD)解不成立。举一反例如下：设A=D=，B=C={1}，则(A∪B)(C∪D)=BC={(1,1)}，(AC)∪(BD)=∪=，显然等式不成立。5.1关系及其表示5.1.2关系的基本概念定义5.4设nI+，A1,A2,…,An为任意n个集合，A1A2…An，则(1)称

23、为A1,A2,…,An间的n元关系；(2)若n=2，则称为从A1到A2的二元关系；(3)若=，则称为空关系；(4)若=A1A2…An，则称为普遍关系；(5)若A1=A2=…=An=A，则称为A上的n元关系；(6)若={(x,x)

24、xA}，则称为A上的恒等关系。若是由A到B的一个关系，且(a,b)，则a对b有关系，记作ab。5.1关系及其表示5.1.2关系的基本概念例5.4设A=