离散数学关系ppt课件

第第2章章关关系系1第2章 关 系1考察日常生活和科学技术中的考察日常生活和科学技术中的考察日常生活和科学技术中的考察日常生活和科学技术中的“关系关系关系关系”：人与人之间有：人与人之间有：人与人之间有：人与人之间有：l父子关系父子关系父子关系父子关系l兄弟关系兄弟关系兄弟关系兄弟关系l师生关系师生关系师生关系师生关系两数之间有：两数之间有：两数之间有：两数之间有：大于关系大于关系大于关系大于关系等于关系等于关系等于关系等于关系小于关系小于关系小于关系小于关系2考察日常生活和科学技术中的“关系”：2集合之间有：集合之间有：集合之间有：集合之间有：l包含关系包含关系包含关系包含关系l相等关系相等关系相等关系相等关系元素与集合之间有：元素与集合之间有：元素与集合之间有：元素与集合之间有：l属于关系属于关系属于关系属于关系函数之间有：函数之间有：函数之间有：函数之间有：l调用关系调用关系调用关系调用关系3集合之间有：3关系关系关系关系联系联系联系联系:事物间的多值对应。事物间的多值对应。事物间的多值对应。事物间的多值对应。本章讨论的是：本章讨论的是：本章讨论的是：本章讨论的是：用集合理论刻画这些用集合理论刻画这些用集合理论刻画这些用集合理论刻画这些“联系联系联系联系”所建立的最一般的所建立的最一般的所建立的最一般的所建立的最一般的数学模型数学模型数学模型数学模型关系关系关系关系，这也是计算机科学中数据描述，这也是计算机科学中数据描述，这也是计算机科学中数据描述，这也是计算机科学中数据描述和信息处理的最常用的数学模型。和信息处理的最常用的数学模型。和信息处理的最常用的数学模型。和信息处理的最常用的数学模型。4关系联系:事物间的多值对应。42.1关系的概念关系的概念2.1.12.1.1n元关系元关系元关系元关系定义定义定义定义2-12-1设设设设A A1 1,A A2 2,A An n是集合，则称是集合，则称是集合，则称是集合，则称A A1 1 A A2 2A An n的任意一个子集的任意一个子集的任意一个子集的任意一个子集R R为为为为A A1 1,A A2 2,A An n间的间的间的间的n n元关系元关系元关系元关系。集合集合集合集合A A1,A A2,A An叫做关系的叫做关系的叫做关系的叫做关系的域域域域,n n叫做它的叫做它的叫做它的叫做它的阶阶阶阶。若若若若R R A An n,则称则称则称则称R R为为为为A A上的上的上的上的n n元关系。元关系。元关系。元关系。52.1 关系的概念定义2-1设A1,A2,An是集可以利用可以利用可以利用可以利用n n元关系表示计算机的数据库元关系表示计算机的数据库元关系表示计算机的数据库元关系表示计算机的数据库:数数数数据据据据库库库库由由由由记记记记录录录录组组组组成成成成，这这这这些些些些记记记记录录录录是是是是由由由由字字字字段段段段构构构构成成成成的的的的n n元元元元组。字段是组。字段是组。字段是组。字段是n n元组的数据项。元组的数据项。元组的数据项。元组的数据项。6可以利用n元关系表示计算机的数据库:6例例例例 设设设设R R是是是是A A N N S S D D T T 的子集，的子集，的子集，的子集，其中其中其中其中A A是所有航空是所有航空是所有航空是所有航空公司的集合，公司的集合，公司的集合，公司的集合，N N是航班号的集合，是航班号的集合，是航班号的集合，是航班号的集合，S S是出发地的集合，是出发地的集合，是出发地的集合，是出发地的集合，D D是目的地的集合，是目的地的集合，是目的地的集合，是目的地的集合，T T是起飞时间的集合。则是起飞时间的集合。则是起飞时间的集合。则是起飞时间的集合。则R R是由是由是由是由5 5元组元组元组元组(a,n,s,d,ta,n,s,d,t)组组组组成的表示成的表示成的表示成的表示飞机航班的关系飞机航班的关系飞机航班的关系飞机航班的关系。例如，设例如，设例如，设例如，设R R表示由国内航空公司表示由国内航空公司表示由国内航空公司表示由国内航空公司飞机航班构成的关飞机航班构成的关飞机航班构成的关飞机航班构成的关系，如果南方航空公司在系，如果南方航空公司在系，如果南方航空公司在系，如果南方航空公司在15:0015:00有从广州到北京的有从广州到北京的有从广州到北京的有从广州到北京的29632963航班，那么航班，那么航班，那么航班，那么(南方航空，南方航空，南方航空，南方航空，29632963，广州，北京，广州，北京，广州，北京，广州，北京，15:00)15:00)属于属于属于属于R R。7 例 设R是ANSDT 的子集，其中A是所定义定义定义定义若若若若(a,ba,b)R R,则称则称则称则称a a与与与与b b有关系有关系有关系有关系R R,记为记为记为记为aRbaRb;若若若若(a,ba,b)R R,则称则称则称则称a a与与与与b b没有关系没有关系没有关系没有关系R R,记为记为记为记为aRbaRb。设有两个集合设有两个集合设有两个集合设有两个集合A A和和和和B B，其笛卡儿积，其笛卡儿积，其笛卡儿积，其笛卡儿积A A B B的任意的任意的任意的任意一个子集一个子集一个子集一个子集R R称为称为称为称为从从从从A A到到到到B B的的的的一个一个一个一个二元关系二元关系二元关系二元关系（relation from relation from A A to to B B）。即）。即）。即）。即:R R A A B B特别地，当特别地，当特别地，当特别地，当A AB B时，时，时，时，R R称为称为称为称为A A上的上的上的上的关系关系关系关系（relation on relation on A A ）,这时这时这时这时 R R A A2 22.1.2 2.1.2 二元关系二元关系二元关系二元关系8定义 若 (a,b)R,则称a与b有关系R,直观地看，二元关系就是反映直观地看，二元关系就是反映直观地看，二元关系就是反映直观地看，二元关系就是反映“多值对应多值对应多值对应多值对应”的二的二的二的二维表，例如，维表，例如，维表，例如，维表，例如，学生选课表：学生选课表：学生选课表：学生选课表：学学学学 生生生生课课课课 程程程程张三张三张三张三离散数学离散数学离散数学离散数学李四李四李四李四微积分微积分微积分微积分张三张三张三张三高级语言高级语言高级语言高级语言.9直观地看，二元关系就是反映“多值对应”的二维表，例如，学生把学生选课表用集合来表示：把学生选课表用集合来表示：把学生选课表用集合来表示：把学生选课表用集合来表示：R R=（张三（张三（张三（张三,离散数学）离散数学）离散数学）离散数学）,（李四（李四（李四（李四,微积分）微积分）微积分）微积分）,（张三（张三（张三（张三,高级语言）高级语言）高级语言）高级语言）,序偶的集合序偶的集合序偶的集合序偶的集合R R同样也刻画了学生集合同样也刻画了学生集合同样也刻画了学生集合同样也刻画了学生集合A A=张三，张三，张三，张三，李四，李四，李四，李四，与课程集合与课程集合与课程集合与课程集合B B=离散数学，微积分，高离散数学，微积分，高离散数学，微积分，高离散数学，微积分，高级语言，级语言，级语言，级语言，之间之间之间之间“多值对应多值对应多值对应多值对应”的联系。的联系。的联系。的联系。10 把学生选课表用集合来表示：10【例例例例】设设设设A A1,2,3,4,51,2,3,4,5,B Ba a,b,cb,c,则则则则R R1 1(1,(1,a a),(1,),(1,b b),(2,),(2,b b),(3,),(3,a a)是从是从是从是从A A到到到到B B的关系的关系的关系的关系,而而而而R R2 2(a a,2),(,2),(c c,4),(,4),(c c,5),5)是从是从是从是从B B到到到到A A的关系。的关系。的关系。的关系。11【例】设A1,2,3,4,5,Ba,【定义定义定义定义】设设设设R R A A A A,1)1)当当当当R R 时时时时,称称称称R R为为为为A A上的上的上的上的空关系空关系空关系空关系;2)2)当当当当R RA A A A=A A2 2时时时时,称称称称R R为为为为集集集集合合合合A A上上上上的的的的全全全全域域域域关关关关系系系系,用用用用E EA A表示。显然表示。显然表示。显然表示。显然E EA A(x,yx,y)|)|x xA A 且且且且 y yA A 3)3)若若若若R R(x x,x x)|)|x xA A,则则则则称称称称R R是是是是A A上上上上的的的的恒恒恒恒等等等等关关关关系系系系,用用用用A A表示。表示。表示。表示。12【定义】设RAA,12【例】【例】【例】【例】设设设设A A1,2,3,4,51,2,3,4,5，R R是是是是A A上的二元关系，其上的二元关系，其上的二元关系，其上的二元关系，其定义为：当定义为：当定义为：当定义为：当a a，b b A A且且且且a a能整除能整除能整除能整除b b时，时，时，时，(a a,b b)R R（R R称为称为称为称为A A上的上的上的上的整除关系整除关系整除关系整除关系），求），求），求），求R R。13【例】设A1,2,3,4,5，R是A上的二元关【例】【例】【例】【例】设设设设A A1,2,3,4,5,61,2,3,4,5,6，R R是是是是A A上的二元关系，上的二元关系，上的二元关系，上的二元关系，其定义为：当其定义为：当其定义为：当其定义为：当a a，b b A A且且且且a a和和和和b b被被被被3 3除后余数相同时，除后余数相同时，除后余数相同时，除后余数相同时，(a a,b b)R R（R R也称为也称为也称为也称为A A上的模上的模上的模上的模3 3同余关系同余关系同余关系同余关系,记为记为记为记为 3 3），），），），求求求求R R。14【例】设A1,2,3,4,5,6，R是A上的定义定义定义定义1.121.12设设设设R R是一个二元关系，是一个二元关系，是一个二元关系，是一个二元关系，(1)(1)R R中所有序偶的第一元素构成的集合称为中所有序偶的第一元素构成的集合称为中所有序偶的第一元素构成的集合称为中所有序偶的第一元素构成的集合称为R R的的的的定义域定义域定义域定义域（domaindomain），记做），记做），记做），记做dom dom R R。(2)(2)R R中所有序偶的第二元素构成的集合称为中所有序偶的第二元素构成的集合称为中所有序偶的第二元素构成的集合称为中所有序偶的第二元素构成的集合称为R R的的的的值域值域值域值域（rangerange），记做），记做），记做），记做ran ran R R。2.1.32.1.3关系的定义域、值域关系的定义域、值域关系的定义域、值域关系的定义域、值域例如：例如：例如：例如：A A=a,b,c,da,b,c,d，B B=1,2,3=1,2,3，R R(a a,2),(,2),(b b,2),(,2),(c c,1),1)，则：则：则：则：domdomR R=a,b,ca,b,c，ranranR R=1,2=1,215定义1.12设R是一个二元关系，2.1.3 关系的定义域、值2.1.42.1.4关系表示关系表示关系表示关系表示1 1、关系图、关系图、关系图、关系图2 2、关系矩阵、关系矩阵、关系矩阵、关系矩阵162.1.4 关系表示161.1.关系图关系图关系图关系图 情形情形情形情形1 1：R R是从是从是从是从A A到到到到B B的关系的关系的关系的关系,采用如下的图示采用如下的图示采用如下的图示采用如下的图示:1 1）用用用用大大大大圆圆圆圆圈圈圈圈表表表表示示示示集集集集合合合合A A和和和和B B，里里里里面面面面的的的的小小小小圆圆圆圆圈圈圈圈（或实心圆）表示集合中的元素（或实心圆）表示集合中的元素（或实心圆）表示集合中的元素（或实心圆）表示集合中的元素;2 2）若若若若a aA A，b bB B，且且且且(a a,b b)R R，则则则则在在在在图图图图中中中中将将将将表表表表示示示示a a和和和和b b的的的的小小小小圆圆圆圆圈圈圈圈用用用用直直直直线线线线或或或或弧弧弧弧线线线线连连连连接接接接起起起起来来来来,并并并并加加加加上上上上从结点从结点从结点从结点a a到结点到结点到结点到结点b b方向的箭头。方向的箭头。方向的箭头。方向的箭头。171.关系图 17例如：例如：例如：例如：A A=a a1 1,a a2 2,a a3 3,a a4 4 B B=b b1 1,b b2 2,b b3 3,b b4 4,b b5 5 R R=(=(a a1 1,b b1 1),(),(a a2 2,b b3 3),(),(a a3 3,b b2 2),),(a a4 4,b b4 4),(),(a a4 4,b b5 5)18例如：18情形情形情形情形2 2：R R是是是是A A上的关系上的关系上的关系上的关系,其画法如下其画法如下其画法如下其画法如下:1)1)集集集集合合合合A A中中中中的的的的每每每每一一一一个个个个元元元元素素素素a a用用用用带带带带有有有有元元元元素素素素符符符符号号号号的的的的顶顶顶顶点点点点(称作顶点称作顶点称作顶点称作顶点a a)表示。表示。表示。表示。2)2)若若若若a a,b bA A,且且且且(a a,b b)R R,则则则则将将将将顶顶顶顶点点点点a a和和和和顶顶顶顶点点点点b b用用用用一一一一条条条条带带带带有有有有箭箭箭箭头头头头的的的的有有有有向向向向边边边边连连连连接接接接起起起起来来来来,其其其其方方方方向向向向由由由由顶顶顶顶点点点点a a指指指指向向向向顶点顶点顶点顶点b b。19 情形2：R是A上的关系,其画法如下:19【例】【例】【例】【例】A A=a a1 1,a a2 2,a a3 3,a a4 4,a a5 5，R R=(=(a a1 1,a a1 1),(),(a a1 1,a a2 2),(),(a a2 2,a a3 3),),(a a3 3,a a4 4),(),(a a4 4,a a1 1),(),(a a4 4,a a5 5),(),(a a5 5,a a3 3)。求求求求R R的关系图。的关系图。的关系图。的关系图。20【例】A=a1,a2,a3,a4,a5，202.2.关系矩阵关系矩阵关系矩阵关系矩阵：由表格法抽象而来：由表格法抽象而来：由表格法抽象而来：由表格法抽象而来 【定定定定义义义义】设设设设集集集集合合合合A A x x1 1,x x2 2,x xmm,B B y y1 1,y y2 2,y yn n,R R是是是是从从从从A A到到到到B B的的的的关关关关系系系系,则则则则mm n n矩矩矩矩阵阵阵阵MMR R(mmij ij)mm n n叫叫叫叫R R的的的的关系矩阵关系矩阵关系矩阵关系矩阵,其中其中其中其中:21 2.关系矩阵：由表格法抽象而来 21【例例例例】设设设设A A1,2,3,4,5,1,2,3,4,5,B B a a,b,cb,c,求求求求下下下下面面面面两两两两个关系的关系矩阵。个关系的关系矩阵。个关系的关系矩阵。个关系的关系矩阵。A A到到到到B B的关系的关系的关系的关系:R R1 1(1,(1,a a),(1,),(1,b b),(2,),(2,b b),(3,),(3,a a)B B到到到到A A的关系的关系的关系的关系:R R2 2(a a,2),(,2),(c c,4),(,4),(c c,5),5)22 【例】设A1,2,3,4,5,Ba,设设设设集集集集合合合合A A a a1 1,a a2 2,a an n,对对对对于于于于A A上上上上的的的的关关关关系系系系R R,其其其其关关关关系矩阵系矩阵系矩阵系矩阵MMR R(mmij ij)n n n n是是是是n n n n的的的的,其中其中其中其中:【例例例例】求求求求A A1,1,2,2,3,3,44上上上上的的的的 关关关关系系系系、E EA A和和和和I IA A的关系矩阵。的关系矩阵。的关系矩阵。的关系矩阵。23设集合Aa1,a2,an,对于A上的关系R2.1.52.1.5函数的关系定义函数的关系定义函数的关系定义函数的关系定义函数如何转换成关系函数如何转换成关系函数如何转换成关系函数如何转换成关系?【例【例【例【例2-152-15】A A=a a,b b,c c,B B=1,2,3,=1,2,3,f f:A A B B,f f(a a)=2,)=2,f f(b b)=3,)=3,f f(c c)=3.)=3.注意：注意：注意：注意：一般来说一般来说一般来说一般来说,A A到到到到B B的关系不是的关系不是的关系不是的关系不是A A到到到到B B的函数的函数的函数的函数.242.1.5 函数的关系定义24定义定义定义定义2-42-4A A到到到到B B的关系的关系的关系的关系f f 满足满足满足满足:(1)dom(1)domf f=A A;（像的存在性）（像的存在性）（像的存在性）（像的存在性）(2)(2)对任意对任意对任意对任意x xA A，若，若，若，若 (x x,y y1 1)f f 且且且且 (x x,y y2 2)f f,则则则则y y11=y y2 2；（像的唯一性）（像的唯一性）（像的唯一性）（像的唯一性）则称则称则称则称f f 为为为为A A到到到到B B的函数。的函数。的函数。的函数。关系如何转换成函数关系如何转换成函数关系如何转换成函数关系如何转换成函数?25定义2-4A到B的关系f 满足:关系如何转换成函数?25作业：作业：P44:1,3,7，13(1)(2)26作业：262.2 关系的运算关系的运算2.2.1.2.2.1.关系的集合运算关系的集合运算关系的集合运算关系的集合运算 设设设设注意：注意：注意：注意：272.2 关系的运算2.2.1.关系的集合运算27可以用可以用可以用可以用n n元关系上的集合运算构造新的元关系上的集合运算构造新的元关系上的集合运算构造新的元关系上的集合运算构造新的n n元关系。元关系。元关系。元关系。例例例例 设设设设A A和和和和B B分别是学校的所有学生和所有课程的分别是学校的所有学生和所有课程的分别是学校的所有学生和所有课程的分别是学校的所有学生和所有课程的集合。假设集合。假设集合。假设集合。假设:R R1 1由所有有序对由所有有序对由所有有序对由所有有序对(a,ba,b)组成，其中组成，其中组成，其中组成，其中a a是选修课程是选修课程是选修课程是选修课程b b的的的的学生学生学生学生;R R2 2由所有的有序对由所有的有序对由所有的有序对由所有的有序对(a,ba,b)构成，其中课程构成，其中课程构成，其中课程构成，其中课程b b是是是是a a的必的必的必的必修课。修课。修课。修课。问关系问关系问关系问关系R R1 1R R2 2，R R1 1 R R2 2，R R1 1R R2 2，R R2 2R R1 1，R R1 1 R R2 2是什么是什么是什么是什么?28可以用n元关系上的集合运算构造新的n元关系。28解解解解 关系关系关系关系R R1 1R R2 2由所有的有序对由所有的有序对由所有的有序对由所有的有序对(a,ba,b)组成，其中组成，其中组成，其中组成，其中a a是是是是一个学生，他或者选修了课程一个学生，他或者选修了课程一个学生，他或者选修了课程一个学生，他或者选修了课程b b，或者课程，或者课程，或者课程，或者课程b b是他的必是他的必是他的必是他的必修课。修课。修课。修课。R R1 1 R R2 2是所有有序对是所有有序对是所有有序对是所有有序对(a,ba,b)的集合，其中的集合，其中的集合，其中的集合，其中a a是一个学是一个学是一个学是一个学生，他选修了课程生，他选修了课程生，他选修了课程生，他选修了课程b b并且课程并且课程并且课程并且课程b b也是也是也是也是a a的必修课。的必修课。的必修课。的必修课。29解 29R R1 1R R2 2是所有有序对是所有有序对是所有有序对是所有有序对(a,ba,b)的集合，其中的集合，其中的集合，其中的集合，其中a a已经选修已经选修已经选修已经选修了课程了课程了课程了课程b b，但，但，但，但b b不是不是不是不是a a的必修课。的必修课。的必修课。的必修课。R R2 2R R1 1是所有有序对是所有有序对是所有有序对是所有有序对(a,ba,b)的集合，其中的集合，其中的集合，其中的集合，其中b b是是是是a a的必的必的必的必修课，但修课，但修课，但修课，但a a没有选它。没有选它。没有选它。没有选它。R R1 1 R R2 2由所有的有序对由所有的有序对由所有的有序对由所有的有序对(a,ba,b)组成，其中学生组成，其中学生组成，其中学生组成，其中学生a a已经已经已经已经选修了课程选修了课程选修了课程选修了课程b b，但课程，但课程，但课程，但课程b b不是不是不是不是a a的必修课，或者课程的必修课，或者课程的必修课，或者课程的必修课，或者课程b b是是是是a a的必修课，但是的必修课，但是的必修课，但是的必修课，但是a a没有选修它。没有选修它。没有选修它。没有选修它。30R1R2是所有有序对(a,b)的集合，其中a已经选修了课程如何用关系矩阵实现关系的集合运算如何用关系矩阵实现关系的集合运算如何用关系矩阵实现关系的集合运算如何用关系矩阵实现关系的集合运算?QuestionsQuestionsQuestions记关系记关系记关系记关系R R的关系矩阵为的关系矩阵为的关系矩阵为的关系矩阵为MMR R=(=(u uij ij)mm n n，关系，关系，关系，关系S S的关系矩的关系矩的关系矩的关系矩阵为阵为阵为阵为MMS S =(=(v vij ij)mm n n ，则，则，则，则1)1)R RS S 的关系矩阵的关系矩阵的关系矩阵的关系矩阵MM R RS S 是是是是MMR R与与与与MMS S的的的的按位或按位或按位或按位或(布尔布尔布尔布尔和和和和):):MM R RS S=MMR R+MMS S=(=(u uij ij+v vij ij)mm n n =(=(u uij ij v vij ij)mm n n 布尔和布尔和布尔和布尔和逻辑或逻辑或逻辑或逻辑或布尔和布尔和布尔和布尔和31如何用关系矩阵实现关系的集合运算?Questions记关系R2)2)R R S S 的关系矩阵的关系矩阵的关系矩阵的关系矩阵MM R R S S 是是是是MMR R与与与与MMS S的的的的按位与按位与按位与按位与(按位布按位布按位布按位布尔积尔积尔积尔积):):MM R RS S=(=(u uij ij v vij ij)mm n n =(=(u uij ij v vij ij)mm n n3)3)的关系矩阵的关系矩阵的关系矩阵的关系矩阵MM 是是是是MMR R的的的的按位按位按位按位取反取反取反取反:把每个把每个把每个把每个1 1改为改为改为改为0 0，每个，每个，每个，每个0 0改为改为改为改为1 14)4)利用利用利用利用A AB B A A,可计算可计算可计算可计算MMR R-S S 及及及及MMR R S S布尔积布尔积布尔积布尔积逻辑与逻辑与逻辑与逻辑与322)RS 的关系矩阵M RS 是MR与MS的按位与(按2.2.22.2.2关系的逆运算关系的逆运算关系的逆运算关系的逆运算定义定义定义定义2-52-5设设设设R R是是是是A A到到到到B B的二元关系，如果把的二元关系，如果把的二元关系，如果把的二元关系，如果把R R中的中的中的中的每一个有序对中的元素顺序互换，所每一个有序对中的元素顺序互换，所每一个有序对中的元素顺序互换，所每一个有序对中的元素顺序互换，所得到的得到的得到的得到的B B到到到到A A的二元关系称为的二元关系称为的二元关系称为的二元关系称为R R的的的的逆关逆关逆关逆关系系系系，记作，记作，记作，记作R R-1-1。例例例例:R R表示表示表示表示“课程课程课程课程-学生学生学生学生”关系关系关系关系，则，则，则，则R R-1-1是是是是“学生学生学生学生-课程课程课程课程”关系。关系。关系。关系。332.2.2 关系的逆运算定义2-5设R是A到B的二元关系，如【例】【例】【例】【例】A A=a a,b b,c c，B B=x x,y y,z z，R R是是是是A A到到到到B B的二元关系，的二元关系，的二元关系，的二元关系，且有：且有：且有：且有：R R=(=(a a,x x),(),(b b,y y),(),(c c,y y)，则则则则R R-1-1是是是是B B到到到到A A的二元关系，且有：的二元关系，且有：的二元关系，且有：的二元关系，且有：R R-1-1=(=(x x,a a),(),(y y,b b),(),(y y,c c)【例】【例】【例】【例】A A=1,2,3=1,2,3，R R是是是是A A上的二元关系，且有：上的二元关系，且有：上的二元关系，且有：上的二元关系，且有：R R=(1,2),(2,3),(3,1)=(1,2),(2,3),(3,1)则其逆关系为：则其逆关系为：则其逆关系为：则其逆关系为：R R-1-1=(2,1),(3,2),(1,3)=(2,1),(3,2),(1,3)34【例】A=a,b,c，B=x,y,z，R是A逆逆逆逆关关关关系系系系R R-1-1的的的的关关关关系系系系矩矩矩矩阵阵阵阵与与与与关关关关系系系系R R的的的的关关关关系系系系矩矩矩矩阵阵阵阵有何联系？有何联系？有何联系？有何联系？QuestionsQuestionsQuestions如果二元关系如果二元关系如果二元关系如果二元关系R R的关系矩阵为的关系矩阵为的关系矩阵为的关系矩阵为MMR R，则，则，则，则MMR R的转置的转置的转置的转置矩阵矩阵矩阵矩阵MMR RT T就是逆关系就是逆关系就是逆关系就是逆关系R R-1-1的关系矩阵。的关系矩阵。的关系矩阵。的关系矩阵。35逆关系R-1的关系矩阵与关系R的关系矩阵有何联系？Quest【定理【定理【定理【定理2-22-2】【定理【定理【定理【定理2-32-3】(1)(1)(2)(2)(3)(3)R R是是是是A A上的关系上的关系上的关系上的关系,则则则则36 36定义定义定义定义2-62-6R R是集合是集合是集合是集合A A到到到到B B的二元关系，的二元关系，的二元关系，的二元关系，S S是集合是集合是集合是集合B B到到到到C C的二元关系，的二元关系，的二元关系，的二元关系，R R和和和和S S的的的的复合复合复合复合R R S S 定义为定义为定义为定义为R R S S=(x x,z z)|y y B B使得使得使得使得(x x,y y)R R且且且且(y y,z z)S S 它是它是它是它是A A到到到到C C的二元关系。的二元关系。的二元关系。的二元关系。2.2.32.2.3关系的复合运算关系的复合运算关系的复合运算关系的复合运算1.1.关系关系关系关系R R和和和和S S的复合的复合的复合的复合37定义2-6R是集合A到B的二元关系，S是集合B到C的二元关系例例例例:R R表示表示表示表示“教师教师教师教师-课程课程课程课程”关系，关系，关系，关系，S S表示表示表示表示“课程课程课程课程-学生学生学生学生”关系，关系，关系，关系，则则则则R R S S 是是是是“教师教师教师教师-学生学生学生学生”关系。关系。关系。关系。例例例例:R R表示表示表示表示“父子父子父子父子”关系，关系，关系，关系，则则则则R R R R 是是是是“祖孙祖孙祖孙祖孙”关系。关系。关系。关系。38例:38例例例例:R R表示表示表示表示“教师教师教师教师-课程课程课程课程”关系，关系，关系，关系，S S表示表示表示表示“课程课程课程课程-学生学生学生学生”关系，关系，关系，关系，T T表示表示表示表示“学生学生学生学生-家长家长家长家长”关系，关系，关系，关系，则则则则(R R S S)T T 是是是是“教师教师教师教师-学生家长学生家长学生家长学生家长”关系。关系。关系。关系。例例例例:R R表示表示表示表示“父子父子父子父子”关系，关系，关系，关系，则则则则(R R R R)R R是什么关系是什么关系是什么关系是什么关系?39例:39 例例例例:设设设设A A1,2,3,41,2,3,4,B B2,3,42,3,4,C C1,2,1,2,3 3,R R(a a,b b)|()|(a a,b b)A A B B 且且且且(a ab b4)4)S S(b b,c c)|()|(a a,b b)B B C C 且且且且 (|(|b bc c|1)1)求求求求R R S S。解解解解:R R(1,3),(2,2)(1,3),(2,2)S S(2,1),(3,2),(4,3),(2,3)(2,1),(3,2),(4,3),(2,3)R R S S(1,2),(2,1),(2,3)(1,2),(2,1),(2,3)复合关系复合关系复合关系复合关系R R S S的图示如图所示。的图示如图所示。的图示如图所示。的图示如图所示。40 例:设A1,2,3,4,B2,复合关系复合关系复合关系复合关系 R S 41复合关系 R S 412.2.复合关系的矩阵表示复合关系的矩阵表示复合关系的矩阵表示复合关系的矩阵表示设设设设A A=a a1 1,a a2 2,a amm，B B=b b1 1,b b2 2,b bn n，C C=c c1 1,c c2 2,c cs s，R R是是是是A A到到到到B B的二元关系，的二元关系，的二元关系，的二元关系，R R的关系矩阵为：的关系矩阵为：的关系矩阵为：的关系矩阵为：其中：其中：1(1(a ai i,b bj j)R R0(0(a ai i,b bj j)R R42 2.复合关系的矩阵表示其中：1 (ai,bjS S是是是是B B到到到到C C的二元关系，的二元关系，的二元关系，的二元关系，S S的关系矩阵：的关系矩阵：的关系矩阵：的关系矩阵：其中：其中：1(1(b bi i,c cj j)S S0(0(b bi i,c cj j)S S43S是B到C的二元关系，S的关系矩阵：其中：1 (bi,c令：令：令：令：则有：则有：则有：则有：当当当当u u1111v v1111=1=1或或或或 u u1212v v2121=1=1或或或或或或或或 u u1n1nv vn1n1=1=1时时时时 w w1111=1=1；当当当当u u1111v v1111=0=0且且且且 u u1212v v2121=0=0且且且且且且且且 u u1n1nv vn1n1=0=0时时时时 w w1111=0=0；一般地有：一般地有：一般地有：一般地有：当当当当u ui i1 1v v1 1j j=1=1或或或或 u ui i2 2v v2 2j j=1=1或或或或或或或或 u uin in v vnjnj=1=1时时时时 w wij ij=1=1；当当当当u ui i1 1v v1 1j j=0=0且且且且 u ui i2 2v v2 2j j=0=0且且且且且且且且 u uin in v vnjnj=0=0时时时时 w wij ij=0=0；44令：则有：44引入引入引入引入布尔加法布尔加法布尔加法布尔加法(逻辑或逻辑或逻辑或逻辑或)（即（即（即（即0+0=00+0=0，1+0=0+1=11+0=0+1=1，1+1=11+1=1），则：），则：），则：），则：w w1111=1=1当且仅当当且仅当当且仅当当且仅当 u u1111v v1111+u u1212v v2121+u u1n1nv vn1n1=1=1；一般地一般地一般地一般地w wij ij=1=1当且仅当当且仅当当且仅当当且仅当 u ui i1 1v v1 1j j+u ui i2 2v v2 2j j+u uin in v vnjnj=1=1；这说明：这说明：这说明：这说明：复合关系复合关系复合关系复合关系R R S S 的关系矩阵的关系矩阵的关系矩阵的关系矩阵MMR R S S=MMR R MMS S 其中其中其中其中 是是是是矩阵的布尔乘法矩阵的布尔乘法矩阵的布尔乘法矩阵的布尔乘法（矩阵的逻辑乘法矩阵的逻辑乘法矩阵的逻辑乘法矩阵的逻辑乘法）。）。）。）。45 引入布尔加法(逻辑或)（即0+0=0，1+0=0+【例】【例】【例】【例】A A=1,2,3=1,2,3，B B=a a,b b,c c,d d，C C=x x,y y,z z，R R是是是是A A到到到到B B的二元关系，的二元关系，的二元关系，的二元关系，R R=(1,=(1,a a),(1,),(1,b b),(2,),(2,b b),(3,),(3,c c)，S S是是是是B B到到到到C C的二元关系，的二元关系，的二元关系，的二元关系，S S=(=(a a,x x),(),(b b,x x),(),(b b,y y),(),(b b,z z)。则有：则有：则有：则有：46 【例】A=1,2,3，B=a,b,c,【例】【例】【例】【例】A A=1,2,3,4=1,2,3,4，R R和和和和S S都是都是都是都是A A上的二元关系上的二元关系上的二元关系上的二元关系R R=(1,1),(1,2),(1,3),(2,3),(2,4),(4,3),(4,4)=(1,1),(1,2),(1,3),(2,3),(2,4),(4,3),(4,4)S S=(1,2),(1,3),(2,3),(2,4),(3,1),(4,3)=(1,2),(1,3),(2,3),(2,4),(3,1),(4,3)则有：则有：则有：则有：47 【例】A=1,2,3,4，R和S都是A上的二定理定理定理定理2-42-4设设设设R R是是是是A A到到到到B B的二元关系，的二元关系，的二元关系，的二元关系，S S是是是是B B到到到到C C的二的二的二的二元关系，元关系，元关系，元关系，T T是是是是C C到到到到D D的二元关系，则：的二元关系，则：的二元关系，则：的二元关系，则：(R R S S)T T=R R (S S T T)二元关系与其关系矩阵是一一对应的，复合关二元关系与其关系矩阵是一一对应的，复合关二元关系与其关系矩阵是一一对应的，复合关二元关系与其关系矩阵是一一对应的，复合关系系系系R R S S的关系矩阵等于的关系矩阵等于的关系矩阵等于的关系矩阵等于R R的关系矩阵与的关系矩阵与的关系矩阵与的关系矩阵与S S的关系矩阵的关系矩阵的关系矩阵的关系矩阵的乘积，而矩阵的乘法运算满足结合律，所以的乘积，而矩阵的乘法运算满足结合律，所以的乘积，而矩阵的乘法运算满足结合律，所以的乘积，而矩阵的乘法运算满足结合律，所以关系关系关系关系的复合也满足结合律的复合也满足结合律的复合也满足结合律的复合也满足结合律，即：，即：，即：，即：48定理2-4设R是A到B的二元关系，S是B到C的二元关系，T定理定理定理定理2-72-7设设R AB，则：，则：(1)IAR=R(2)RIB=R定理定理定理定理2-62-6设设设设R R是是是是A A到到到到B B的二元关系，的二元关系，的二元关系，的二元关系，S S是是是是B B到到到到C C的二的二的二的二元关系，则元关系，则元关系，则元关系，则(R R S S)-1-1=S S-1-1 R R-1-1。49定理2-7设 R AB，则：定理2-6设R是A到B的二定义定义定义定义2-72-7设设设设R R是是是是A A上的关系，上的关系，上的关系，上的关系，n n为自然数，则为自然数，则为自然数，则为自然数，则R R 的的的的n n 次幂定义为：次幂定义为：次幂定义为：次幂定义为：(1)(1)R R0 0=(=(x,xx,x)|)|x x A A=I IA A(2)(2)R Rn+1n+1=R Rn nR R由于二元关系的复合满足结合律，所以二元关由于二元关系的复合满足结合律，所以二元关由于二元关系的复合满足结合律，所以二元关由于二元关系的复合满足结合律，所以二元关系的幂运算是有意义的。系的幂运算是有意义的。系的幂运算是有意义的。系的幂运算是有意义的。3.3.关系的幂运算关系的幂运算关系的幂运算关系的幂运算50定义2-7设R是A上的关系，n为自然数，则R 的n 次幂定义【例】例】例】例】设设设设R R是世界上所有人的集合上的关系，如是世界上所有人的集合上的关系，如是世界上所有人的集合上的关系，如是世界上所有人的集合上的关系，如果果果果a a认识认识认识认识b b，那么，那么，那么，那么R R包含包含包含包含(a,ba,b)。问。问。问。问R Rn n是由怎样的序偶是由怎样的序偶是由怎样的序偶是由怎样的序偶构成的构成的构成的构成的?其中其中其中其中n n是大于等于是大于等于是大于等于是大于等于2 2的正整数。的正整数。的正整数。的正整数。解解解解如果存在人如果存在人如果存在人如果存在人c c，使得，使得，使得，使得(a,ca,c)R R且且且且(c,bc,b)R R，即存在，即存在，即存在，即存在人人人人c c使得使得使得使得a a认识认识认识认识c c，c c认识认识认识认识b b，那么关系，那么关系，那么关系，那么关系R R2 2包括包括包括包括(a,ba,b)。类似地，如果存在人类似地，如果存在人类似地，如果存在人类似地，如果存在人x x1 1，x x2 2，x xn n-1-1使得使得使得使得a a认识认识认识认识x x1 1，x x1 1认识认识认识认识x x2 2，x xn n-1-1认识认识认识认识b b，那么，那么，那么，那么R Rn n包含对包含对包含对包含对(a,ba,b)。51【例】设R是世界上所有人的集合上的关系，如果a认识b，那【例】【例】【例】【例】设设设设R R是广州市所有地铁站的集合上的关系。是广州市所有地铁站的集合上的关系。是广州市所有地铁站的集合上的关系。是广州市所有地铁站的集合上的关系。如果可以从站如果可以从站如果可以从站如果可以从站a a不换车就旅行到站不换车就旅行到站不换车就旅行到站不换车就旅行到站b b，那么，那么，那么，那么R R包含对包含对包含对包含对(a,ba,b)。当。当。当。当n n是正整数时，是正整数时，是正整数时，是正整数时，R Rn n是由怎样的序偶构成的是由怎样的序偶构成的是由怎样的序偶构成的是由怎样的序偶构成的?解解解解 如果经过至多如果经过至多如果经过至多如果经过至多n-1n-1次换车就可以从站次换车就可以从站次换车就可以从站次换车就可以从站a a旅行到站旅行到站旅行到站旅行到站b b，关系，关系，关系，关系R Rn n就包含就包含就包含就包含(a,ba,b)。52【例】设R是广州市所有地铁站的集合上的关系。如果可以从站a定理定理定理定理2-82-8设设设设R R是是是是A A上的关系，上的关系，上的关系，上的关系，m,nm,n N N，则，则，则，则(1)(1)R RmmR Rn n=R Rm+nm+n(2)(2)(R Rmm)n n=R Rmnmn(3)(3)(R Rmm)-1-1=(=(R R-1-1)mm53定理2-8设R是A上的关系，m,n N，则53作业：作业：P51:1,3,11 54作业：54定义定义定义定义2-2-9,109,10设设设设R R是是是是A A上的关系上的关系上的关系上的关系,(1)(1)若对于若对于若对于若对于所有的所有的所有的所有的x xA A,都有都有都有都有(x,xx,x)R R,则称则称则称则称R R是是是是自反的自反的自反的自反的(reflexivereflexive)。(2)(2)若对于若对于若对于若对于所有的所有的所有的所有的x xA A,都有都有都有都有(x,xx,x)R R,则则则则称称称称R R是是是是反自反的反自反的反自反的反自反的(irreflexiveirreflexive)。2.3 关系的性质关系的性质 55定义2-9,10设R是A上的关系,2.3 关系的性质【例例例例】设设设设A A1,2,3,1,2,3,R R11,R R22,R R3 3 是是是是A A上的关系，其中上的关系，其中上的关系，其中上的关系，其中 R R1 1(1,1),(2,2)(1,1),(2,2)R R2 2(1,1),(2,2),(3,3),(1,2)(1,1),(2,2),(3,3),(1,2)R R3 3(1,3)(1,3)说明它们是否为说明它们是否为说明它们是否为说明它们是否为A A上的自反关系或反自反关系。上的自反关系或反自反关系。上的自反关系或反自反关系。上的自反关系或反自反关系。【例例例例】全域关系全域关系全域关系全域关系E EA A ,恒等关系恒等关系恒等关系恒等关系A A是是是是A A上的自反关系上的自反关系上的自反关系上的自反关系;小于等于关系小于等于关系小于等于关系小于等于关系 A A ,整除关系整除关系整除关系整除关系D DA A是是是是A A上的自反关系上的自反关系上的自反关系上的自反关系;小于关系小于关系小于关系小于关系 A A是反自反关系。是反自反关系。是反自反关系。是反自反关系。56【例】设A1,2,3,R1,R2,R3 分析上述关系的关系图和关系矩阵，可得出结论分析上述关系的关系图和关系矩阵，可得出结论分析上述关系的关系图和关系矩阵，可得出结论分析上述关系的关系图和关系矩阵，可得出结论:若若若若关关关关系系系系R R是是是是自自自自反反反反的的的的,当当当当且且且且仅仅仅仅当当当当其其其其关关关关系系系系图图图图中中中中每每每每个个个个结结结结点点点点都都都都有有有有自自自自回回回回路路路路(环环环环),),其其其其关关关关系系系系矩矩矩矩阵阵阵阵中中中中,主主主主对对对对角角角角线线线线上上上上的的的的元元元元素素素素均为均为均为均为;若若若若关关关关系系系系R R是是是是反反反反自自自自反反反反的的的的,当当当当且且且且仅仅仅仅当当当当其其其其关关关关系系系系图图图图中中中中每每每每个个个个结结结结点点点点都都都都没没没没有有有有自自自自回回回回路路路路(环环环环),),其其其其关关关关系系系系矩矩矩矩阵阵阵阵中中中中,主主主主对对对对角角角角线线线线上上上上的的的的元素全为元素全为元素全为元素全为。注注注注意意意意,一一一一个个个个关关关关系系系系不不不不是是是是自自自自反反反反的的的的,不不不不一一一一定定定定就就就就是是是是反反反反自自自自反的。反的。反的。反的。57分析上述关系的关系图和关系矩阵，可得出结论:57定理定理定理定理2-2-9,109,10设设设设 R R A A A A，则：，则：，则：，则：(1)R R自反自反自反自反 I IA A R R.(2)R R反自反反自反反自反反自反 I IA A R R=.58定理2-9,10设 R AA，则：58定义定义定义定义2-112-11定义定义定义定义2-122-12设设设设R R是是是是A A上的关系，上的关系，上的关系，上的关系，(1)(1)若对于任意的若对于任意的若对于任意的若对于任意的x x,y yA A,每当每当每当每当(x,yx,y)R R 时就有时就有时就有时就有 (y,xy,x)R R,则称则称则称则称R R 是是是是对称的对称的对称的对称的(symmetricsymmetric)。(2)(2)若若若若(x,yx,y)R R 且且且且x x y y时时时时,必有必有必有必有(y,xy,x)R R,则称则称则称则称R R是是是是反对称的反对称的反对称的反对称的(antisymmetricantisymmetric)。59定义2-11设R是A上的关系，59 【例例例例】设设设设A A1,2,3,1,2,3,R R11,R R22,R R3 3,R R4 4是是是是A A上上上上的的的的关关关关系系系系，其中其中其中其中 R R1 1(1,1),(2,2)(1,1),(2,2)R R2 2(1,1),(1,2),(2,1)(1,1),(1,2),(2,1)R R3 3(1,2),(1,3)(1,2),(1,3)R R4 4(1,2),(2,1),(1,3)(1,2),(2,1),(1,3)说明它们是否为说明它们是否为说明它们是否为说明它们是否为A A上的对称关系或反对称关系。上的对称关系或反对称关系。上的对称关系或反对称关系。上的对称关系或反对称关系。60 【例】设A1,2,3,R1,R2,【例例例例】全域关系全域关系全域关系全域关系E EA A ,恒等关系恒等关系恒等关系恒等关系A A是是是是A A上的上的上的上的对称对称对称对称关系关系关系关系;小于等于关系小于等于关系小于等于关系小于等于关系 A A ,整除关系整除关系整除关系整除关系D DA A是是是是A A上的上的上的上的反对称反对称反对称反对称关系。关系。关系。关系。61【例】全域关系EA,恒等关系A是A上的对称关系;61分析这些关系的关系矩阵和关系图，可得出结论分析这些关系的关系矩阵和关系图，可得出结论分析这些关系的关系矩阵和关系图，可得出结论分析这些关系的关系矩阵和关系图，可得出结论:若关系若关系若关系若关系R R是对称的是对称的是对称的是对称的,当且仅当其关系图中当且仅当其关系图中当且仅当其关系图中当且仅当其关系图中,若有顶若有顶若有顶若有顶点点点点a a到顶点到顶点到顶点到顶点b b的边的边的边的边,则一定有顶点则一定有顶点则一定有顶点则一定有顶点b b到顶点到顶点到顶点到顶点a a的边的边的边的边,其关系矩阵是一个其关系矩阵是一个其关系矩阵是一个其关系矩阵是一个对称矩阵对称矩阵对称矩阵对称矩阵。若关系若关系若关系若关系R R是反对称的是反对称的是反对称的是反对称的,当且仅当其关系图中当且仅当其关系图中当且仅当其关系图中当且仅当其关系图中,若有若有若有若有顶点顶点顶点顶点a a到顶点到顶点到顶点到顶点b b的边的边的边的边,则一定没有顶点则一定没有顶点则一定没有顶点则一定没有顶点b b到顶点到顶点到顶点到顶点a a的的的的边边边边,其关系矩阵关于主对角线对称的元素不同时其关系矩阵关于主对角线对称的元素不同时其关系矩阵关于主对角线对称的元素不同时其关系矩阵关于主对角线对称的元素不同时为为为为,即当即当即当即当r rij ij=(i i j j)时时时时,必有必有必有必有r rji ji=。62分析这些关系的关系矩阵和关系图，可得出结论:62定理定理定理定理2-2-11,1211,12设设设设 R R A A A A，则：，则：，则：，则：(1)R R对称对称对称对称 R R=R R-1-1.(2)R R反对称反对称反对称反对称 R R R R-1-1 I IA A.63定理2-11,12设 R AA，则：63定义定义定义定义2-132-13设设设设R R是是是是A A上的关系上的关系上的关系上的关系,若对任意若对任意若对任意若对任意x x,y y,z zA A,每每每每当当当当(x,yx,y)R R且且且且(y,zy,z)R R时，就有时，就有时，就有时，就有(x,zx,z)R R,则称则称则称则称R R是是是是传递的传递的传递的传递的(transitivetransitive)。关系图上传递的特征：关系图上传递的特征：关系图上传递的特征：关系图上传递的特征：如果顶点如果顶点如果顶点如果顶点x x到到到到y y有边，有边，有边，有边，y y到到到到z z有边，则有边，则有边，则有边，则x x到到到到z z也有边。也有边。也有边。也有边。64定义2-13设R是A上的关系,若对任意x,y,zA,【例例例例】设设设设A A1,2,3,1,2,3,R R11,R R22 是是是是A A上的关系，其中上的关系，其中上的关系，其中上的关系，其中 R R1 1(