[经济学]第四章关系ppt课件

1、第四章第四章 关系关系本章学习目的本章学习目的 关系是离散数学中刻画元素之间互相联络的一个重要关系是离散数学中刻画元素之间互相联络的一个重要概念。它仍然是一个集合，以具有联络的对象组合作概念。它仍然是一个集合，以具有联络的对象组合作为其成员。在计算机科学与技术领域中有着广泛的应为其成员。在计算机科学与技术领域中有着广泛的应用，关系数据库模型就是以关系及其运算作为理论根用，关系数据库模型就是以关系及其运算作为理论根底的。本章主要讨论二元关系的根本理论。通过本章底的。本章主要讨论二元关系的根本理论。通过本章学习，读者应该掌握以下内容：学习，读者应该掌握以下内容： 关系、关系的表示关系、关系的表示

2、关系的性质和运算关系的性质和运算 关系的性质和闭包关系的性质和闭包学习内容学习内容1. 1. 序偶与笛卡儿积序偶与笛卡儿积2. 2. 二元关系及其表示二元关系及其表示3. 3. 关系的运算关系的运算4. 4. 关系的性质及闭包关系的性质及闭包4.1 4.1 序偶与笛卡儿积序偶与笛卡儿积4.1.1 4.1.1 有序有序n n元组元组 4.1.2 4.1.2 笛卡儿积的概念笛卡儿积的概念 4.1.3 4.1.3 笛卡儿积的性质笛卡儿积的性质 4.1 4.1 序偶与笛卡儿积序偶与笛卡儿积4.1.1 4.1.1 有序有序n n元组元组 定义定义 由两个元素由两个元素x x和和y y按一定按一定次序排列

3、组成的二元组，称为一次序排列组成的二元组，称为一个有序对或序偶，个有序对或序偶， 记为记为xy，其中，其中x x，y y分别称为序偶的第分别称为序偶的第一、二分量或称第一、二元素。一、二分量或称第一、二元素。定理定理4.1 4.1 两序偶两序偶ab，cd是相等的，当且仅当是相等的，当且仅当a=ca=c，b=db=d；记作；记作a=d。4.1 4.1 序偶与笛卡儿积序偶与笛卡儿积4.1.1 4.1.1 有序有序n n元组元组 例例4.1.1 4.1.1 设有序对设有序对2x+y=x+2y，那么根据有序，那么根据有序对相等的充分条件有对相等的充分条件有2x+y2x+yx-2yx-2y和和6 6x+

4、2yx+2y，因此得到，因此得到x x1818，y y6 6。 4.1 4.1 序偶与笛卡儿积序偶与笛卡儿积4.1.2 4.1.2 笛卡儿积的概念笛卡儿积的概念 定义定义 给定两个集合给定两个集合A和和B，假如序偶的第一个分量是，假如序偶的第一个分量是A中中的一个元素，第二个分量是的一个元素，第二个分量是B中的一个元素，那么所有这种中的一个元素，那么所有这种序偶的集合，称为集合序偶的集合，称为集合A和和B的笛卡儿积，简称为卡氏积，的笛卡儿积，简称为卡氏积，记为记为AB，即，即AB= xAyB。 4.1 4.1 序偶与笛卡儿积序偶与笛卡儿积4.1.2 4.1.2 笛卡儿积的概念笛卡儿积的概念 例

5、例1A=a，b，B=c，d，求，求AB。2A=a，b，B=c，d，求，求BA。3A=a，b，B=1，2，C=c，求，求ABC和和ABC。4.1 4.1 序偶与笛卡儿积序偶与笛卡儿积4.1.2 笛卡儿积的概念 解解 1AB=a，bc，d=， 。2BA=c，da，b=，。3AB=a，b1，2=， 。4.1 4.1 序偶与笛卡儿积序偶与笛卡儿积4.1.2 笛卡儿积的概念 ABC=，c，c，c， ，c =，。 BC=1，2c=，。 ABC=a，a，b， b，。4.1 4.1 序偶与笛卡儿积序偶与笛卡儿积定理定理4.4 4.4 设设A, BA, B为集合为集合. . 那么有那么有 1 1 A AB=BB

6、=BA A A= A= B=B=A=BA=B 2 2 B B C C A AB B A AC C 3 3 A A A AB B A AC C B B C C 4 4A ABCBC= =A AB BA AC C 5 5A ABCBC= =A AB BA AC C 6 6A AB-CB-C= =A AB B- -A AC C4.1 4.1 序偶与笛卡儿积序偶与笛卡儿积4.2 二元关系及其表示二元关系及其表示4.2.1 4.2.1 二元关系的概念二元关系的概念 4.2.2 4.2.2 二元关系的表示二元关系的表示 1 1关系矩阵表示法关系矩阵表示法 2 2关系图表示法关系图表示法 4.2 二元关系及

7、其表示二元关系及其表示4.2.1 4.2.1 二元关系的概念二元关系的概念 定义定义 设设R是二元关系，由是二元关系，由 R的所有的所有x组成的集合称组成的集合称为为R的定义域，记作的定义域，记作dom R dom R ，即，即dom R dom R =xx? y yy y B Bxy R R 。 由由 R的所有的所有y组成的集合称为组成的集合称为R的值域，记的值域，记作作ran R ,而而fld R是它们的并集，即是它们的并集，即fld Rdom Rran R定义定义 设设A，B是两个集合，是两个集合，R是笛卡儿积是笛卡儿积AB的任一子集，的任一子集，那么称那么称R为从为从A到到B的一个二元

8、关系，简称关系。特别当的一个二元关系，简称关系。特别当A= =B时，时，那么称那么称R为为A上的二元关系或上的二元关系或A上的关系。上的关系。 4.2 二元关系及其表示二元关系及其表示4.2 二元关系及其表示二元关系及其表示4.2 二元关系及其表示二元关系及其表示4.2 二元关系及其表示二元关系及其表示4.2.2 4.2.2 二元关系的表示二元关系的表示 1 1关系矩阵表示法关系矩阵表示法 设给定集合设给定集合A=aA=a1 1，a a2 2，a an n ，集合，集合B=bB=b1 1，b b2 2，b bm m ，R R为为从从A A到到B B的一个二元关系，构造一个的一个二元关系，构造一

9、个n nm m矩阵。用集合矩阵。用集合A A的元素标的元素标注矩阵的行，用集合注矩阵的行，用集合B B的元素标注矩阵的列，对于的元素标注矩阵的列，对于aAaA和和bBbB，假设假设aRbR，那么在行，那么在行a a和列和列b b穿插处标穿插处标1 1，否那么标，否那么标0 0。这样得到的矩阵称为这样得到的矩阵称为R的关系矩阵。的关系矩阵。4.2 二元关系及其表示二元关系及其表示4.2.2 4.2.2 二元关系的表示二元关系的表示 解解 R R的关系矩阵为：的关系矩阵为：4.2 二元关系及其表示二元关系及其表示4.2 二元关系及其表示二元关系及其表示解解 R R的关系矩阵为：的关系矩阵为：4.2

10、 二元关系及其表示二元关系及其表示4.2.2 4.2.2 二元关系的表示二元关系的表示 2 2关系图表示法关系图表示法 有限集的二元关系可以用有向图来表示，设集合有限集的二元关系可以用有向图来表示，设集合A=a1，a2，an，集合，集合B=b1，b2，bm，R为从为从A到到B的一个二元关系，首的一个二元关系，首先用小圆圈画出先用小圆圈画出n个结点分别表示个结点分别表示a1，a2，an，然后另外作出，然后另外作出m个结点分别表示个结点分别表示b1，b2，bm，假如，假如aA、bB且且 R，那么自结点那么自结点a到结点到结点b作出一条有向弧，其箭头指向作出一条有向弧，其箭头指向b。假如。假如 R，

11、那么结点，那么结点a和结点和结点b之间没有线段联结。用这种方法得到的之间没有线段联结。用这种方法得到的图称为图称为R的关系图。的关系图。 4.2 二元关系及其表示二元关系及其表示解解 A A上的关系图如下图。上的关系图如下图。4.2.2 4.2.2 二元关系的表示二元关系的表示- - 关系图表示法关系图表示法 例例4 44 4 分别作出例分别作出例4 42 2与例与例4 43 3中关系的关系图中关系的关系图4.2 二元关系及其表示二元关系及其表示例43中关系的关系图4.3 关系的运算关系的运算4.3.1 4.3.1 关系的交、并、差、补运算关系的交、并、差、补运算 4.3.2 4.3.2 关系

12、的复合运算关系的复合运算 4.3.3 4.3.3 关系的逆运算关系的逆运算 4.3 关系的运算关系的运算例例4.5 4.5 设设X=1, 2, 3, 4, X=1, 2, 3, 4, 那么那么X X上的小于关系，上的小于关系， 恒等关系恒等关系, , 大于关系分别为大于关系分别为 = = 1 2，13，14，23，24，34Ix=1Ix=1，22，33，4 4 = = 1，31 41，32 , ,42，4 3 分别求分别求小于关系与恒等关系的并小于关系与恒等关系的并, , 大于关系与大于关大于关系与大于关系的并系的并, , 大于关系的补大于关系的补. .4.3 关系的运算关系的运算解解 小于关

13、系与恒等关系的并即为小于关系与恒等关系的并即为小于等于关系小于等于关系 = Ix = = Ix = ，, ，小于关系与大于关系的并即为不等关系小于关系与大于关系的并即为不等关系 = = ，, ， 另外大于关系的补即为小于等于关系另外大于关系的补即为小于等于关系4.3 关系的运算关系的运算4.3.2 关系的逆运算 定义定义 设设R R是从集合是从集合A A到集合到集合B B的二元关系，假如将的二元关系，假如将R R中中每个序偶的第一元素和第二元素的顺序互换，所得到每个序偶的第一元素和第二元素的顺序互换，所得到的集合称为的集合称为R R的逆关系，记为的逆关系，记为R R-1-1，即，即R R-1-

14、1=y=x xRyR日常生活中，日常生活中， 互为逆关系的例子：互为逆关系的例子：父子关系与子父关系父子关系与子父关系师生关系与生师关系师生关系与生师关系数学上大于关系与小于关系。数学上大于关系与小于关系。4.3 关系的运算关系的运算例例4.6 设设 A=1， 2， 3， 4， B=, R=，求求R的逆关系的逆关系R-1-1解解 R-1-1=，4.3 关系的运算关系的运算定理定理4.6 4.6 设设R R1， R R2， R R3都是从都是从X X到到Y Y的二元关系，那么：的二元关系，那么： 1 1 R R1 1 R R2 2 R R1 1-1-1 R R2 2-1-12 2R R1 1RR

15、2 2-1-1=R=R1 1-1-1SS2 2-1-13 3R R1 1RR2 2-1-1=R=R1 1-1-1RR2 2-1-14 4RR-1-1= = R R-1-1这里这里R = XR = X Y-RY-R4.3 关系的运算关系的运算4.3.2 4.3.2 关系的复合运算关系的复合运算 定义定义 设设R是从集合是从集合X到集合到集合Y上的二元关系，上的二元关系，S是从集合是从集合Y到集合到集合Z上的二元关系，那么上的二元关系，那么R S称为称为R和和S的复合关系，表示为的复合关系，表示为R S= xXzZ yyYRS从从R，S得到得到R S的运算称为关系的复合运算也称为合成运的运算称为关

16、系的复合运算也称为合成运算。算。 4.3 关系的运算关系的运算4.3.2 4.3.2 关系的复合运算关系的复合运算 例例4.7 设设 X=1，2，3，4, 5，R1=，, ，R2=， ，求求R1 R2 ， 解解 ： R1 R2 =，。如下图：如下图：12345XXX4.3 关系的运算关系的运算例例4.8 设设X=1，2，3，4, 5。R1=，R2=，求，求R1 R2, R2 R1, R1 R1, R2 R2, R1 R2 R2, R1 R2 R2 解：解： R1 R2= ， R2 R1= ， R1 R1 =， R2 R2 =，R1 R2 R2 = R1 R2 R2 = 4.3 关系的运算关系的

17、运算4.3.3 4.3.3 关系的复合运算关系的复合运算 定理定理4.7 设设R是从是从X到到Y的关系，的关系，Q是从是从Y到到Z的关系，的关系，S是从是从Z到到W 的关系，那么有的关系，那么有R Q S = R Q S.定理定理4.8 设设R是是X到到Y的关系，那么的关系，那么 Ix R=R Iy=R 4.3 关系的运算关系的运算定理定理4.9 设设R1, R2是是X到到Y的关系的关系.设设R3, R4是是Y到到Z的关系的关系.那么有那么有 1 R1 R2 R1 R3 R2 R3 R3 R4 R1 R3 R1 R4 2R1R2 R3=R1 R3R2 R3 R1 R3R4 = R1 R3 R1

18、 R4 3R1 R2 R3 R1 R3 R2 R3 R1 R3 R4 R1 R3 R1 R44R1R2-1 R2 -1 R1 -14.3 关系的运算关系的运算4.3.2 4.3.2 关系的复合运算关系的复合运算 定理定理4.10 设设X, Y, Z均是非空有限集均是非空有限集, R是从是从X到到Y的关系，的关系，Q是从是从Y到到Z的关系，的关系，R, Q的关系矩阵分别为的关系矩阵分别为MR，MQ，那么有，那么有MR Q=MR MQ。4.3 关系的运算关系的运算4.3.2 4.3.2 关系的复合运算关系的复合运算 例例4.9 4.9 给定集合给定集合X=1X=1，2 2，3 3，4 4，55，在

19、集合，在集合X X上有两个关系，上有两个关系，R R1=1=2，23，3, 4, ，R R2=1=3，24，35，通过关系矩阵求，通过关系矩阵求R1 R2 。解解 00000000000000010000010000000000000100000100000100000001000001000001000001021RRMR1 R2 = ，4.3 关系的运算关系的运算4.3.2 4.3.2 关系的复合运算关系的复合运算 000000001000010000000100000000000000100000010000100000000010000011000000100RSM4.4 关系的性质和

20、闭包关系的性质和闭包4.4.1 自反性和反自反性4.4.2 对称性和反对称性 4.4.3 传递性 4.4.4 关系性质的断定 1自反性的断定方法 2反自反性的断定方法 3对称性的断定方法 4反对称性的断定方法 5传递性的断定方法 4.4 关系的性质关系的性质4.4.1 关系的根本性质1. 自反性定义定义 设R是集合A上的二元关系，假如对于每个xA，都有R，那么称二元关系R是自反的。R在A上是自反的 xxAR定义定义 设R是集合A上的二元关系，假如对于每个xA，都有 R，那么称二元关系R是反自反的。R在A上是反自反的 xxA R4.4 关系的性质关系的性质2 对称性定义定义 设R是集合A上的二元

21、关系，假如对于每个x，yA， 当R，就有R，那么称二元关系R是对称的。R在A上是对称的x yxAyARR 定义定义 设R是集合A上的二元关系，假如对于每个x，yA，当R和R时，必有x=y，那么称二元关系R是反对称的。 4.4 关系的性质关系的性质3 传递性 定义定义 设R是集合A上的二元关系，假如对于任意x，y，zA，当R，R，就有R，那么称二元关系R在A上是传递的。R在A上是传递的x y zxAyAzARRR4.4 关系的性质关系的性质4.4 关系的性质关系的性质4.4 关系的性质关系的性质4.4 关系的性质关系的性质4.4 关系的性质关系的性质4.4.4 关系性质的断定 定理定理4.11

22、设R是X上的二元关系, 1 R在X上是自反的当且仅当 Ix R。 2 R在X上是对称的当且仅当R=R1。 3 R在X上是传递的当且仅当R R R。 4 R在X上是反自反的当且仅当IXR=。 5 R在X上是反对称的当且仅当RR1Ix。4.4 关系的性质关系的性质4.4 关系的性质关系的性质4.4 关系的性质关系的性质4.4.4 关系性质的断定 1自反性的断定方法例例4.4.34.4.3 设集合A=a，b，c，d，A上的二元关系R=，讨论R的性质，写出R的关系矩阵，画出R的关系图。 R的关系矩阵为： 1000110101100011RM4.4 关系的性质关系的性质1自反性的断定方法解 由于，R，即

23、IA R，所以R是自反的。 1000110101100011RMR的关系矩阵为 4.4 关系的性质关系的性质1自反性的断定方法R的关系图为： 。abdc4.4 关系的性质关系的性质4.4.4 关系性质的断定 2反自反性的断定方法 定理定理4.4.2 设R是A上的二元关系，那么R在A上是反自反的当且仅当IAR=。例4.4.4 设集合A=a，b，c，d，A上的二元关系R=，讨论R的性质，写出R的关系矩阵，画出R的关系图。解 由于，R，即IAR=，所以R是反自反的。 4.4 关系的性质关系的性质4.4.4 关系性质的断定 2反自反性的断定方法R的关系矩阵为： 0100100101010110RM4.

24、4 关系的性质关系的性质2反自反性的断定方法R的关系图为： 4.4 关系的性质关系的性质4.4.4 关系性质的断定 3对称性的断定方法定理定理4.4.3 4.4.3 设R是A上的二元关系，那么R在A上是对称的当且仅当R=R1。 例4.4.54.4.5设集合A=a，b，c，d，A上的二元关系R=，讨论R的性质，写出R的关系矩阵，画出R的关系图。解 因为R，所以R不是自反的。由于R，即IAR，所以R不是反自反的。R1=，R=R1，由上面的定理可知，关系R是对称的。4.4 关系的性质关系的性质3对称性的断定方法R的关系矩阵为： 1100101101010110RM4.4 关系的性质关系的性质3对称性

25、的断定方法R的关系图为： 4.4 关系的性质关系的性质4.4.4 关系性质的断定 4反对称性的断定方法 定理定理4.4.4 4.4.4 设R是A上的二元关系，那么R在A上是反对称的当且仅当RR1IA。例4.4.6 4.4.6 设集合A=a，b，c，d，A上的二元关系R=，讨论R的性质，写出R的关系矩阵，画出R的关系图。4.4 关系的性质关系的性质例4.4.6 4.4.6 设集合A=a，b，c，d，A上的二元关系R=，讨论R的性质，写出R的关系矩阵，画出R的关系图。解 因为R，所以R不是自反的。由于R，即IA R，所以R不是反自反的。因为R1=，RR1，所以关系R不是对称的。RR1=IA，由上面

26、的定理可知，R是反对称的。4反对称性的断定方法4.4 关系的性质关系的性质 4反对称性的断定方法R的关系矩阵为：1001100001010100RM4.4 关系的性质关系的性质4反对称性的断定方法 R的关系图如图4.8所示：。abdc4.4 关系的性质关系的性质4.4.4 关系性质的断定5传递性的断定方法 定理定理4.4.5 4.4.5 设R是A上的二元关系，那么R在A上是传递的当且仅当 R R R。定理定理4.4.6 4.4.6 设集合A=a1，a2，an，R是A上的二元关系，R的关系矩阵为MR，令M=MR MR，那么R在A上是传递的当且仅当矩阵M的第i行，第j列元素为1时，MR的第i行，第

27、j列元素必为1。4.4 关系的性质关系的性质4.4.4 关系性质的断定5传递性的断定方法 例例4.4.7 设A=1，2，3，4，5，6，R=，判断R是否具有传递性。解 R的关系矩阵为：001110001000000000001000001100101110RM4.4 关系的性质关系的性质5传递性的断定方法 例例4.4.7 设A=1，2，3，4，5，6，R=，判断R是否具有传递性。令M=MR MR，那么M为： 001100000000000000000000001000001110M比较MR和M，可知二元关系R是传递的。 4.4 关系的性质关系的性质5传递性的断定方法 另一种判断关系是否具有传递

28、性的方法。设集合A=a1，a2，an，R是A上的二元关系，R的关系矩阵为MR。设MR中第i行第j列元素aij=1，考察MR中第j行所有元素：aj1，aj2，ajn；假如其中有ajk=1，这说明关系R中存在着R和R，所以假如R，即aik=0，说明R不具有传递性。假如aik=1，那么继续考察第j行中的其它非零元素，用一样的方法分析。因此当aij=1时，应将第i行元素与第j行所有元素逐个比较；假如存在着第j行某个元素为1，而第i行的对应元素为0，那么R不具有传递性。否那么应继续考察MR中的其它非零元素，用同样的方法进展，直到考察完MR中所有非零元素。 4.4 关系的性质关系的性质5传递性的断定方法 例例4.4.8 设A=1，2，3，4，5，R=，判断R是否具有传递性。解 R的关系矩阵为： 1111100111001000001000110RM4.4 关系的性质关系的性质5传递性的断定方法 考察MR中的非零元素：对于a12=1，将第2行元素逻辑加到第1行上，运算后的矩阵没有改变。对于a13=1，将第3行元素逻辑加到第1行上，运算后的矩阵没有改变。对于a22=1，将第2行元素逻辑加到第2行上，运算后的矩阵没有改变。对于其它非零元素，经同样的操作后，MR没有变化，所以R是A上的传递关系 1111