《离散数学》课件：1-2-关系(简)

《《离散数学》课件：1-2-关系(简)》由会员分享，可在线阅读，更多相关《《离散数学》课件：1-2-关系(简)（86页珍藏版）》请在文档大全上搜索。

1、第二节第二节 关关 系系(relations)的基本概念及其性质的基本概念及其性质 1.2.2等价关系等价关系 1.2.3部分序关系部分序关系1.2.1 关系的基本概念及其性质关系的基本概念及其性质定义定义1.2.1 设设A1, ,A2, , ,An是是n个集合，个集合， 集合集合A1 A2 An的一个子集的一个子集F称为称为A1, ,A2, , ,An上的一个上的一个n元关系。特别地，集合元关系。特别地，集合A B中的一中的一个子集个子集R，称为集合，称为集合A与与B上的一个二元关系上的一个二元关系( (binary relationbinary relation) )，简称为关系。，简称为

2、关系。对于对于x A，y B，若，若(x, ,y) R则称则称x，y有关系有关系R，记为，记为xRy；若；若(x, ,y) R，则称，则称x，y没有关系没有关系R，记为，记为xRy。若若B=A，则，则R称为称为A上的二元关系。上的二元关系。 关系的特点关系的特点1.A A上的任一子集都是上的任一子集都是A上的一个关系；上的一个关系；2.若若A=n，则，则A上的关系有上的关系有 个。个。3.A上的三个特殊关系，即空关系上的三个特殊关系，即空关系 ；全域关系全域关系EA=A A；相等关系相等关系IA=(x,x) x A。4. 5.有序偶有序偶(a,b)=(c,d)的充要条件是的充要条件是a=c，b

3、=d。22nRAARERA例例设设A=a,b,c,d,e,f为学生集合，为学生集合，B= , , , 为选修课程集合，为选修课程集合，C=2,3,4,5为学习成绩为学习成绩集合，学生与课程之间存在着一种关系即集合，学生与课程之间存在着一种关系即“选修关系选修关系”；学生、课程和成绩之间也；学生、课程和成绩之间也存在着一种叫做存在着一种叫做“学习成绩关系学习成绩关系”。设用。设用R表示选修关系，表示选修关系，S表示学习成绩关系，那表示学习成绩关系，那么么R为为A与与B上的二元关系，上的二元关系，S为为A，B和和C上的三元关系。上的三元关系。 R=(a, ),(a, ),(b, ),(b, ),(

4、c, ),(c, ),(e, ),(f, )表示学生表示学生a选修课程选修课程 ， ；学生；学生b选修课程选修课程 ， ；学生；学生c选修课程选修课程 ， ；学生；学生e 选修课选修课程程 ；学生；学生f选修课程选修课程 ；而学生；而学生d没有选修没有选修任何课程。任何课程。S=(a, ,5), (a, ,5), (b, , 3), (c, ,4), (f, ,2)表示学生表示学生a所选的两门课程成绩都是所选的两门课程成绩都是5分；分；学生学生b所选所选 课程的成绩是课程的成绩是3分；学生分；学生c所选所选 课程的成绩是课程的成绩是4分；学生分；学生f所选所选 课程的成绩课程的成绩是是2分。分

5、。 关系是集合，因此集合的方法对关系都关系是集合，因此集合的方法对关系都是有效的。因而有子关系，关系的并、交、是有效的。因而有子关系，关系的并、交、差、余等运算。差、余等运算。v例：例：R，S是集合是集合A上的两个关系，若上的两个关系，若R S，则称，则称R为为S的子关系；的子关系；对任意对任意x，y A，有，有 x(RS)y当且仅当当且仅当xRy或者或者xSy x(R S)y当且仅当当且仅当xRy并且并且xSy x(R-S)y当且仅当当且仅当xRy并且并且xSy x y当且仅当当且仅当xR yR定义定义1.2.2 逆关系逆关系(inverse relation)设设R是集合是集合A上的一个关

6、系。上的一个关系。令令R-1 =(y, x) x A, y A, 并且有并且有xRy，则称关系，则称关系R-1为关系为关系R的逆。的逆。例如，小于关系的逆关系是大于关系，大于关例如，小于关系的逆关系是大于关系，大于关系的逆关系是小于关系，相等关系的逆关系仍系的逆关系是小于关系，相等关系的逆关系仍是相等关系。是相等关系。 例：例：R=(a,b),(b,c),(a,c),(b,d),则则R-1 = (b,a),(c,b),(c,a),(d,b)定义定义1.2.3 自反自反关系关系(reflexive)v集合集合A 上的关系上的关系R称为是自反的称为是自反的(反身的反身的)，如果对如果对每一个每一个

7、x A，都有，都有xRx。 v例：例：A=a, b, c, A 上的关系上的关系R1=(a,b),(b,b),(b,c) R2=(a,a),(a,b),(b,b),(b,c),(c,c)vR是自反的是自反的当且仅当当且仅当IA R，R是自反的是自反的当且仅当当且仅当R-1是自反的是自反的 。定义定义1.2.4 反自反反自反关系关系(irreflexive)v集合集合A上的关系上的关系R称为反自反的，如果对称为反自反的，如果对任意的任意的x A，xRx均不成立。或者说对任均不成立。或者说对任意的意的x A，都有，都有xRx。v例：例：A=a, b, c, A上的关系上的关系R1=(a,b),(b

8、,b),(b,c) R2=(a,b),(b,c),(a,c)v显然，显然，R是反自反的当且仅当是反自反的当且仅当 IAR= 。 讨论：讨论：是否存在既具有自反性，又具有反自反是否存在既具有自反性，又具有反自反性的关系？性的关系？是否存在既不具有自反性，又不具有反是否存在既不具有自反性，又不具有反自反性的关系？自反性的关系？空关系空关系 、全域关系、全域关系EA、相等关系、相等关系IA是否是否具有自反性，或反自反性？具有自反性，或反自反性？定义定义1.2.4 对称对称关系关系(symmetric)v集合集合A上的关系上的关系R称为对称的，如果称为对称的，如果xRy，则则yRx。其中。其中x A，

9、y A。 v例：例：A=a, b, c, A上的关系上的关系R1=(a,a),(a,b),(b,a),(b,c) R2=(a,a),(b,b),(c,b),(b,c),(a,c),(c,a)vR是对称的是对称的当且仅当当且仅当R-1=R 。定义定义1.2.4反对称反对称关系关系(antisymmetric)v集合集合A上的关系上的关系R称为是反对称的，如果称为是反对称的，如果xRy，yRx，则必有，则必有x=y ；或者说，如果；或者说，如果xRy且且x y ，则必有则必有yRx。v例：例：A=a, b, c, A上的关系上的关系R1=(a,a),(a,b),(b,c) R2=(a,a),(b,

10、b),(c,b),(b,c),(c,a)vR是反对称的是反对称的当且仅当当且仅当RR-1 IA 。讨论：讨论：是否存在既具有是否存在既具有对称对称性，又具有性，又具有反对称反对称性的关系？性的关系？是否存在既不具有是否存在既不具有对称对称性，又不具有反性，又不具有反对称对称性的关系？性的关系？空关系空关系 、全域关系、全域关系EA、相等关系、相等关系IA是否是否具有具有对称对称性，或反性，或反对称对称性？性？定义定义1.2.4 传递传递关系关系(transitive)v集合集合A上的关系上的关系R称为是传递的，如果称为是传递的，如果xRy，yRz，则，则xRz。 其中其中x A，y A，z A

11、。 v例：例：A=a, b, c, A上的关系上的关系R1=(a,a),(a,b),(b,c),(a,c) ， R2=(a,b),(a,c), R3=(a,a),(c,b),(b,c),(c,a)数的相等关系、大于关系、小于关系都数的相等关系、大于关系、小于关系都具有传递性。具有传递性。定义定义1.2.4 关系的乘积关系的乘积(composite)v设设R，S是集合是集合A上的两个关系，令上的两个关系，令RS=(x, y)x A, y A且存在一个且存在一个z A使得使得xRz，zSy。称关系。称关系RS为关系为关系R和和S的乘积的乘积或合成或合成(composite) 。 v例：兄弟关系和父