Ch08二元关系

1、离散数学离散数学智能科学系智能科学系冯寅冯寅EmailEmail：FengYFengY2022-5-16智能科学系智能科学系95-2第第8 8章二元关系章二元关系8.1.18.1.1 序偶与序偶与笛卡尔乘积笛卡尔乘积 定义定义8.18.1由两个元素由两个元素x,yx,y按照一定的次序组成的二元按照一定的次序组成的二元组称为组称为有序偶对有序偶对，简称，简称序偶序偶, ,记作记作,其中，称其中，称x x为为的第一元素，的第一元素，y y为为的第二元素。的第二元素。例例8.18.1平面上点的坐标平面上点的坐标，x,yRx,yR；中国地处亚洲中国地处亚洲 ， , , 等都是等都是序偶序偶。 这这条单

2、地址指令条单地址指令也是也是序偶。序偶。性质性质8.18.1（1 1） x,y（当当xyxy时时) ) （2 2） x,y当且仅当当且仅当x xu,yu,yv v。8.18.1二元关系及其表示法二元关系及其表示法2022-5-16智能科学系智能科学系95-3n n重有序组重有序组定义定义8.28.2由由n n个元素个元素a a1 1,a,a2 2,a,a3 3, ,a,an n按照一定的次按照一定的次序组成的序组成的n n元组称为元组称为n n重有序组重有序组，记作，记作a 即：即：a a,a,an n 。例例8.28.2a a年年b b月月c c日日d d时时e e分分f f秒可用下述六重有

3、序组秒可用下述六重有序组来描述：来描述：。性质性质8.28.2a b 当且当且仅当仅当a ai ib bi i（i i1,2,3,1,2,3,n,n）。2022-5-16智能科学系智能科学系95-4定义定义8.38.3设设A,BA,B是两个集合，称集合是两个集合，称集合A AB B|(xA)(yB)|(xA)(yB)为为集合集合A A与与B B的的笛卡笛卡儿儿积积。特别，记特别，记A AA A为为A A2 2。笛卡儿积笛卡儿积BA1 12 23 34 4a ab bc cd dD DC CA AB B|(xA)(yB)|(xA)(yB)C CD D|(xC)(yD)|(xC)(yD),2022

4、-5-16智能科学系智能科学系95-5设设A A1,2,B1,2,Ba,ba,b例例8 8.3.3则则A AB B,；B BA A,。由于由于1,a,，知：知：A ABBBBA A但但| |A AB|B|B|BA|A|A|A|B|B|。因此，一般情况下，对任何两个集合因此，一般情况下，对任何两个集合A A、B B，当当ABAB时，有：时，有：A ABBBBA A。2022-5-16智能科学系智能科学系95-6定义定义8.48.4设设A A1 1,A,A2 2, ,A,An n是是n n个集合，称集合个集合，称集合A A1 1A A2 2A An na|(a|(ai iAAi i)i1,2,)i

5、1,2,n,n为为集合集合A A1 1,A,A2 2,A,A3 3, ,A,An n的的笛卡儿积笛卡儿积。推广推广当当A A1 1A A2 2A An nA A时，记时，记A A1 1A A2 2A An n为为A An n。当当A A1 1,A,A2 2, ,A,An n都是有限集时，都是有限集时，|A|A1 1A A2 2A An n| |A|A1 1| |A|A2 2| |A|An n| |。2022-5-16智能科学系智能科学系95-7例例8.48.4 假设我们在上假设我们在上“离散数学离散数学”课时，教室里共有课时，教室里共有n n8.1.28.1.2关系的引入关系的引入s1s2sm

6、c1c2c3cn0s3把椅子，听课的学生共有把椅子，听课的学生共有m m个（个（mnmn），每个学生坐一把），每个学生坐一把椅子。此时，学生与椅子之间有一定的从属关系。椅子。此时，学生与椅子之间有一定的从属关系。设分别用两个集合设分别用两个集合A A，B B来表示教室里所有椅子的集合来表示教室里所有椅子的集合和学生的集合，即和学生的集合，即A=cA=c1 1,c,c2 2,c,c3 3, ,c,cn n ，B=sB=s1 1,s,s2 2,s,s3 3, , ,s sm m 。此时，若将它们用坐标描述出来即为下图。此时，若将它们用坐标描述出来即为下图。若若s si i坐坐c cj j，则可在坐

7、标的交叉部分标，则可在坐标的交叉部分标上红点，由于只能是学生坐椅子，而非椅上红点，由于只能是学生坐椅子，而非椅子坐学生，因此，学生子坐学生，因此，学生s si i与椅子与椅子c cj j有一定有一定的顺序，此时无法用单纯的集合的顺序，此时无法用单纯的集合ssi i,c,cj j 来来表示两者的关系，而必须用一种有序的形表示两者的关系，而必须用一种有序的形式表示。另外，图中的所有红点的集合实式表示。另外，图中的所有红点的集合实际上正好反应了际上正好反应了m m个学生坐个学生坐n n把椅子的全部把椅子的全部就座情况。就座情况。2022-5-16智能科学系智能科学系95-8定义定义8.58.5设设A

8、 A1 1,A,A2 2, ,A,An n为为n n个非空集合，称个非空集合，称8.1.38.1.3关系的定义关系的定义A A1 1A A2 2A An n的任意子集的任意子集R R为以为以A A1 1A A2 2A An n为基的为基的n n元关系元关系。特别：特别：当当R R时，则称时，则称R R为为空关系空关系；当当R RA A1 1A A2 2A An n时，则称时，则称R R为为全关系全关系。由于由于A A1 1A A2 2A An n的任何子集都是一个的任何子集都是一个n n元元关系，按照子集的定义，关系，按照子集的定义，A A1 1A A2 2A An n共有共有2 2|A|A1

9、 1A A2 2A An n| |个不同的子集。因此，个不同的子集。因此，以以A A1 1A A2 2A An n为基的为基的不不同关系共有同关系共有2 2|A|A1 1A A2 2A An n| |个。个。2022-5-16智能科学系智能科学系95-9例例3.1.53.1.5在下列数据库中，常将用表格的方式表示出来的文件看在下列数据库中，常将用表格的方式表示出来的文件看作是关系作是关系R R，如下表是一个学生学籍管理的一个数据库：，如下表是一个学生学籍管理的一个数据库：则此时有关系则此时有关系R R A A1 1A A2 2A A6 6，其中，其中A1A194081-1,94081-1,94

10、081-2,94081-2,94081-3,94081-3, ，A2A21,2,3,1,2,3, ，A3A3 王雷王雷, ,李华李华, ,张江张江, ,赵小容赵小容, ,陈涛陈涛, ,黄静黄静, , ，A4A4 男，女男，女,A5A517,18,19,20,2117,18,19,20,21，A6A6 四川四川, ,北京北京, ,江苏江苏, ,云南云南, ,广东广东, ,山东山东, , 。系别与班级系别与班级 学号学号姓名姓名性别性别 年龄年龄 籍贯籍贯94081-11王王 雷雷男男18 四川四川94081-13李李 华华男男19 江苏江苏94081-22张张 江江男男17 北京北京94082-

11、14赵小容赵小容女女18 云南云南94082-22陈陈 涛涛男男19 广东广东94082-31黄黄 静静女女19 山东山东2022-5-16智能科学系智能科学系95-10定义定义8.68.6设设A A，B B为两个集合，为两个集合，A AB B的任何一个子的任何一个子集集R R所定义的二元关系称为所定义的二元关系称为从从A A到到B B的的二元关系二元关系，简称，简称关关系系。如。如R R是从是从A A到到A A的二元关系，则称的二元关系，则称R R为为A A上的上的二元关系二元关系。8.1.48.1.4二元关系二元关系由于任何由于任何A AB B的子集都是一个二元关系，按照子集的的子集都是一

12、个二元关系，按照子集的定义，知定义，知A AB B共有共有2 2|A|B|A|B|个不同的子集。因此，从个不同的子集。因此，从A A到到B B不不同的关系共有同的关系共有2 2|A|B|A|B|个。个。设有一序偶：设有一序偶：RR，常把这一事实记为常把这一事实记为xRyxRy，读作读作“x x对对y y有关系有关系R R”。如如 x,y R R，则记为则记为xRyxRy，读作读作“x x对对y y没有关系没有关系R R”。2022-5-16智能科学系智能科学系95-11域域满足：满足：C Cx|x| RR，D Dy|y| RR。称称C C为为R R的的定义域定义域，记为记为C CdomRdom

13、R；称称D D为为R R的的值域值域，记记D DranRranR；称称fldRfldRdomRranRdomRranR为为R R的的域域。称称A A为为R R的的前域前域，称，称B B为为R R的的后后域域，C C A A，D D B B2022-5-16智能科学系智能科学系95-12设设R R1 1|(x,y|(x,y I)(xy)I)(xy)；R R2 2|(x,y|(x,y I)(xI)(x2 2+y+y2 21)1)；R R3 3|(x,y|(x,y I)(yI)(y2x)2x)；R R4 4|(x,y|(x,y I)(|x|I)(|x|y|y|3)3)。都是定义在整数集都是定义在整数

14、集I I上的关系，求它们的定义域上的关系，求它们的定义域和值域。和值域。例例.6.6解解domRdomR1 1I,ranRI,ranR1 1I I；domRdomR2 20,1,-1,ranR0,1,-1,ranR2 20,1,-10,1,-1；domRdomR3 3I,ranRI,ranR3 3E E；domRdomR4 43,-3,ranR3,-3,ranR1 13,-33,-3。2022-5-16智能科学系智能科学系95-138.1.58.1.5关系的表示法关系的表示法1.1.集合表示法集合表示法由于关系也是一种特殊的集合，所以集合的由于关系也是一种特殊的集合，所以集合的两种基本的表示法

15、也可以用到关系的表示中。即两种基本的表示法也可以用到关系的表示中。即可用枚举法和叙述法来表示关系。可用枚举法和叙述法来表示关系。例例3.1.73.1.7 设设A A2,B2,B3,3,关系关系R R 如定义集合如定义集合N N上的上的“小于等于小于等于”关系：关系：R R|(x,y|(x,y N)(xy)N)(xy) 。2022-5-16智能科学系智能科学系95-142.2.关系图法关系图法设设A Aaa1 1,a,a2 2,a,a3 3,.,a,.,an n,B,Bbb1 1,b,b2 2,b,b3 3,.,b,.,bm m ，R R是是 设设a a1 1,a,a2 2,a,a3 3,.,a

16、,.,an n和和b b1 1,b,b2 2,b,b3 3,.,b,.,bm m分别为图中的节点，分别为图中的节点，用用“。”表示表示； 如如 R,R,则从则从a ai i到到b bj j可用一有向边可用一有向边a ai ib bj j相连。相连。a 为对应图中的有向边。为对应图中的有向边。从从A A到到B B的一个二元关系，则对应于关系的一个二元关系，则对应于关系R R之关系图有如下之关系图有如下规定：规定：如如R R是定义在是定义在A Aa 上的关系，则对上的关系，则对应于关系应于关系R R有如下规定：有如下规定： 设设a a1 1,a,a2 2,.,a,.,an n为图中节点，用为图中节

17、点，用“。”表表示。示。 如如 R,R,则从则从a ai i到到a aj j可用一有向边可用一有向边a ai ib bj j相连。相连。a 为对应图中的有向边；为对应图中的有向边； 如如a R,R,则从则从a ai i到到a ai i用一带箭头的小圆环表示用一带箭头的小圆环表示a ai i 2022-5-16智能科学系智能科学系95-15设设A AP 是六个程序，考虑它之间的是六个程序，考虑它之间的一种调用关系一种调用关系R R，如，如P Pi i可调用可调用P Pj j, ,则有则有P R,R,现假现假设设R RP,P则此关系则此关系R R的关系图如下：的关系图如下：例例8.88.82022

18、-5-16智能科学系智能科学系95-162 2）设设A Aaa1 1,a,a2 2,a,a3 3, ,a,a6 6是六个人，是六个人，B B11，2 2，3 3是是三套房间，考虑三套房间，考虑A A到到B B之间的一种住宿关系之间的一种住宿关系R R，如，如a ai i住房住房间间j,j,则有则有a,j R,R,现假设：现假设：R Ra,2则此关系则此关系R R的关系图如下：的关系图如下：例例3.1.7(3.1.7(续续) )2022-5-16智能科学系智能科学系95-17设设A Aaa1 1,a,a2 2,a,a3 3,.,a,.,an n ，B Bbb1 1,b,b2 2,b,b3 3,.

19、,b,.,bm m ，R R是从是从A A到到B B的一个二元关系，的一个二元关系， 称称矩阵矩阵M MR R(r(rijij) )n nm m为关系为关系R R的的关系矩阵关系矩阵或或邻接矩阵邻接矩阵，其中：，其中：)m,.,3 , 2 , 1j ;n,.,3 , 2 , 1i (Rb,a, 0Rb,a , 1rjijiij 3.3.关系矩阵关系矩阵显然，显然，关系矩阵是布尔矩阵关系矩阵是布尔矩阵。注意注意 在写关系矩阵时，首先应对集合在写关系矩阵时，首先应对集合A A和和B B中的元中的元素进行素进行排序排序，不同的排序会得到不同的关系矩阵。当集，不同的排序会得到不同的关系矩阵。当集合以枚

20、举法表示时，如果没有对集合的元素排序，则默合以枚举法表示时，如果没有对集合的元素排序，则默认枚举的次序为元素的排序。认枚举的次序为元素的排序。 2022-5-16智能科学系智能科学系95-18设设A A22，3 3，4 4，B B11，2 2，4 4。考虑。考虑从从A A到到B B的的“大于等于大于等于”关系关系R R和和“小于等于小于等于”关关系系S S：R R,，S S,。写出写出R R，S S的关系矩阵。的关系矩阵。 111011011MR 100100110MS例例8.98.9解：解：根据定义，由于根据定义，由于A AB B是相对于是相对于R R的全集，所以的全集，所以A AB-R,B

21、-R,且且R RA AB,B,RR。2022-5-16智能科学系智能科学系95-19设设R R，S S都是集合都是集合A A到到B B的两个关系，则：的两个关系，则：RSRS|(xRy)(xSy)|(xRy)(xSy)RSRS|(xRy)(xSy)|(xRy)(xSy)R - SR - S | ( x R y ) ( x S y ) | ( x R y ) ( x S y ) |(x|(xy)y)R 8.28.2关系的运算关系的运算8.2.18.2.1关系的交、并、补、差运算关系的交、并、补、差运算RRRR2022-5-16智能科学系智能科学系95-20设设A Aa,b,c,Ba,b,c,B1

22、,21,2，R R,，S S,，则：则： RSRSRSRSR-SR-S例例8.8.1 10 0,，；,；,A AB-RB-R。R2022-5-16智能科学系智能科学系95-21关系关系的的复合运算复合运算设设 R R 是 一 个 从 集 合是 一 个 从 集 合 A A 到 集 合到 集 合 B B 的 二 元 关的 二 元 关系，系，S S是从集合是从集合B B到集合到集合C C的二元关系的二元关系( (也可也可简单地描述为简单地描述为R R：ABAB，S S：BC)BC)，则，则R R与与S S的的复合关系复合关系（合成关系合成关系）R R S S是从是从A A到到C C的关系，的关系，并

23、并且：且：R R S S|(xA)(zC)|(xA)(zC)( ( y)y)(yB)(xRy)(ySz)(yB)(xRy)(ySz)运算运算“ ”称为称为复合运算复合运算。注意，在复合关系中，注意，在复合关系中，R R的后域的后域B B一定是一定是S S的的前域前域B B，否则，否则R R和和S S是不可复合的。复合的结果是不可复合的。复合的结果R R S S的前域就是的前域就是R R的前域的前域A A，后域就是，后域就是S S的后域的后域C C。如果。如果对任意的对任意的xAxA和和zCzC，不存在，不存在yByB，使得，使得xRyxRy和和ySzySz同时成立，则同时成立，则R R S S

24、为空，否则为非空。并且，为空，否则为非空。并且， R=RR=R = = 。 2022-5-16智能科学系智能科学系95-22例例8.118.11某人某人a a与与c c有外祖父的关系，则一定存在一个有外祖父的关系，则一定存在一个b b，使使得得a a与与b b有父女关系而有父女关系而b b与与c c有母子关系。有母子关系。某人某人a a与与b b有有“兄妹兄妹”关系，关系，b b和和c c有有“母子母子”关系，则关系，则a a与与c c有有“舅甥舅甥”关系。关系。例例8.128.12设设R R,S S,，分别是定义为从分别是定义为从ABAB和从和从BCBC的关系，的关系，其中其中A AB BC

25、 C1,2,3,41,2,3,4。 用集合方法求用集合方法求R R S S，S S R R，R R R R，S S S S。则：则：R R S S,；S S R R,；R R R R,；S S S S,。例例8.118.112022-5-16智能科学系智能科学系95-23 R R S S R R。S SA AB BC CA AC C1 1。1 1。1 11 1。1 12 2。2 2。2 22 2。2 23 3。3 3。3 33 3。3 34 4。4 4。4 44 4。4 4用 关 系 图 求用 关 系 图 求R R S S。例例8.128.12用关系矩阵求用关系矩阵求R R S S。 0000

26、100000100010M MR R S S M MR R M MS S 00000010010001000010000101000000 2022-5-16智能科学系智能科学系95-240 否则否则记为记为 AB2022-5-16智能科学系智能科学系95-25设设I I是整数集合，是整数集合，R R，S S是是I I到到I I的两个关系：的两个关系：R R|xI|xI；S S|xI|xI。则：则： R R S SS S R RR R R RS S S S(R(R R)R) R R(R(R S)S) R R例例8 8.13.13|xI|xI|xI|xI|xI|xI|xI|xI|xI|xI|xI

27、|xI2022-5-16智能科学系智能科学系95-26定义定义8.88.8设设R R是一个从集合是一个从集合A A到集合到集合B B的二元的二元关系，则从关系，则从B B到到A A的关系的关系R R-1-1| RR称为称为R R的的逆关系逆关系, ,运算运算“-1-1”称为称为逆运算逆运算。8.2.38.2.3关系的关系的逆逆运算运算注意：关系是一种集合，逆关系也是一种集注意：关系是一种集合，逆关系也是一种集合，因此，如果合，因此，如果R R是一个关系，则是一个关系，则R R-1-1和都是关和都是关系，但系，但R R-1-1和是完全不同的两种关系，千万不要和是完全不同的两种关系，千万不要混淆。

28、混淆。RR2022-5-16智能科学系智能科学系95-27设设A Aa,b,c,d,Ba,b,c,d,B1,2,3,R1,2,3,R是从是从A A到到B B的一个关系，的一个关系，R R,，则：则：R R-1-1例例8.148.14 如用关系图表示逆关系，则仅将关系图中的有如用关系图表示逆关系，则仅将关系图中的有向边的方向改变成相反方向。向边的方向改变成相反方向。 如用关系矩阵表示逆关系，则如用关系矩阵表示逆关系，则M MR R-1-1M MR RT T。R,。2022-5-16智能科学系智能科学系95-28关系图和关系矩阵如下：关系图和关系矩阵如下：例例8.14(8.14(续续) )-110

29、0011100000111000110101010100010101RRRMMM，2022-5-16智能科学系智能科学系95-29定理定理8.18.1设设R,S,TR,S,T分别是从集合分别是从集合A A到集合到集合B B，集合，集合B B到到集合集合C C，集合，集合C C到集合到集合D D的二元关系，则：的二元关系，则：1)1)(R(R S)S) T TR R (S(S T)T)2)2)(R(R S)S)-1-1S S-1-1 R R-1-18.2.48.2.4关系运算的性质关系运算的性质证明证明1)1)设设(R(R S)S) T T，cC,cC,使得：使得：RR S S，TT。则由复合运

30、算知则由复合运算知, ,至少存在至少存在RR (S(S T),T),又对于又对于RR S S，则至少存一个，则至少存一个bBbB，使得，使得RR，SS。因此因此, ,由由S,T,S,T,有有SS T T，又由，又由RR和和SS T T，知：，知：所以所以(R(R S)S) T T R R (S(S T)T)。同理可证：同理可证：R R (S(S T)T) (R(R S)S) T T。由集合性质知：由集合性质知：(R(R S)S) T TR R (S(S T)T)。2022-5-16智能科学系智能科学系95-302)2). .任取任取(R(R S)S)-1-1，则，则RR S S由由“ ”的定义

31、知：则至少存一个的定义知：则至少存一个bB,bB,使得：使得：RR，SS，即：即：RR-1-1,S,S-1-1。由由SS-1-1和和RR-1-1, ,有：有：SS-1-1 R R-1-1，所以，所以，(R(R S)S)-1-1 S S-1-1 R R-1-1。反之，任取反之，任取SS-1-1 R R-1-1，由，由“ ”的定义知：则至的定义知：则至少存一个少存一个bB,bB,使得：使得：SS-1-1和和RR-1-1，所以：所以：RR，SS。由由“ ”知：知：RR S S。即有：。即有：(R(R S)S)-1-1。所以，所以，S S-1-1 R R-1-1 (R(R S)S)-1-1。由集合的定

32、义知：由集合的定义知：(R(R S)S)-1-1S S-1-1 R R-1-1。定理定理8.1(8.1(续续) )2022-5-16智能科学系智能科学系95-31定义定义8.98.9设设R R是集合是集合A A上的二元关系，则可上的二元关系，则可定义定义R R的的n n次幂次幂R Rn n, ,该该R Rn n也是也是A A上的二元关系，定义上的二元关系，定义如下：如下：1.R1.R0 0I IA A|aA|aA；2.R2.R1 1；3.3.R Rn+1n+1R Rn n R RR R R Rn n。关系的关系的幂幂显然，显然，R Rm m R Rn nR Rm+nm+n,(R,(Rm m)

33、)n nR Rmnmn。2022-5-16智能科学系智能科学系95-32例例8.158.15设设A Aa,b,c,d,e,f,a,b,c,d,e,f,定义在定义在A A上的关系上的关系R R,，S S,求求R Rn n和和S Sn n。解解R R1 1R R，R R2 2R R R R,，R R3 3R R R R R RR R2 2 R R,，R R4 4R R3 3 R R,，R R5 5R R4 4 R R,，R R6 6R R5 5 R R,R R5 5，R R7 7R R6 6 R RR R5 5，R Rn nR R5 5(n(n5)5)。2022-5-16智能科学系智能科学系95-

34、33S S1 1S,S,例例8.15(8.15(续续) )S S2 2S S S S,，S S3 3S S S S S SS S2 2 S S,，S S4 4S S3 3 S S,，S S5 5S S4 4 S S，S S6 6S S5 5 S S，S S7 7，S Sn n(n(n5)5)。2022-5-16智能科学系智能科学系95-34证明证明显然，显然， 。下面证：下面证：设设A A是有限集合，且是有限集合，且| |A|A|n n，R R是是A A上的二元关上的二元关系，则：系，则：RRin1ii1i RRin1ii1i RRi1iin1i RRRi1niin1ii1i Rin1i 定理

35、定理8.28.2由于，由于， 为此，只要证明对任意的为此，只要证明对任意的k kn n，有有R Rk k 即可。即可。对任意对任意 Ra,bRk k，则由，则由“ ”的定义知，存在的定义知，存在a a1 1,a,a2 2, ,，a ak-k-1 1AA（为了统一，并假设（为了统一，并假设a a0 0a,a,a ak kb)b)，使得：，使得：aRR，aRR，aRR，,a,RR。2022-5-16智能科学系智能科学系95-35由于由于| |A|A|n n，所以所以由鸽笼原理知：由鸽笼原理知： k+1k+1个元素中至少有个元素中至少有两个两个以上以上元素相同元素相同，不不妨妨假设假设a ai ia

36、 aj j(i(ij)j)，则可在，则可在aRR，aRR，aRR，,a,RR中删去中删去 RR，aRR，,a,RR后仍有后仍有 RR，aRR，aRR，,a,RR，aRR，,a,RR由关系的复合运算得，由关系的复合运算得，=a=RRkk，其中，其中k kk-(j-i)k-(j-i)，此时：，此时：定理定理8.28.2( (续续1)1)2022-5-16智能科学系智能科学系95-36若若knkn，则：，则： ；Rin1i Rin1i Rin1i RRin1ii1i RRin1ii1i 定理定理8.28.2( (续续2)2)若若kkn n，则重复上述做法，最终总能找到则重复上述做法，最终总能找到kn

37、kn，使得：使得： a,baRRkk，所以，所以， 。即有：即有： ，由此有：由此有：R Rk k 。由由k k的任的任意性知：意性知： ，2022-5-16智能科学系智能科学系95-37设设R R是从集合是从集合A A到集合到集合B B的关系，的关系，S S1 1,S,S2 2是从集合是从集合B B到集到集合合C C的关系，的关系，T T是从集合是从集合C C到集合到集合D D的关系，则：的关系，则：R R (S(S1 1SS2 2) )(R(R S S1 1)(R)(R S S2 2) )R R (S(S1 1SS2 2) ) (R(R S S1 1)(R)(R S S2 2) )(S(S

38、1 1SS2 2) ) T T(S(S1 1 T)(ST)(S2 2 T)T)1)1) (S(S1 1SS2 2) ) T T (S(S1 1 T)(ST)(S2 2 T)T)定理定理8.38.3证明证明4)4)对任意对任意(S(S1 1SS2 2) ) T T，则由复合运算知，则由复合运算知，至少存在至少存在cC,cC,使得：使得：(S(S1 1SS2 2) )，TT。即：。即：SS1 1, ,且且SS2 2。因此，由因此，由SS1 1, ,且且TT，则有：，则有：(S(S1 1 T),T),由由SS2 2, ,且且TT，则有：，则有：(S(S2 2 T)T)。所以，所以，(S(S1 1 T

39、)(ST)(S2 2 T)T)。即，即，( (S S1 1SS2 2) ) T T (S(S1 1 T)(ST)(S2 2 T)T)。2022-5-16智能科学系智能科学系95-38设设A Aa,Ba,Bbb1 1,b,b2 2,C,Cc,c,关系关系S S1 1，S S2 2，T T定定义如下：义如下：S S1 1a,b,S S2 2a,b,T Tb,c。例例8.168.16 则由于：则由于：S S1 1SS2 2,所以：所以：(S(S1 1SS2 2) ) T T T T,但：但：S S1 1 T T，S S2 2 T T，所以：所以：( (S S1 1 T)(ST)(S2 2 T)T)，

40、(S(S1 1 T)(ST)(S2 2 T)T)(S(S1 1SS2 2) ) T T，即：即：( (S S1 1 T)(ST)(S2 2 T)(ST)(S1 1SS2 2) ) T T。2022-5-16智能科学系智能科学系95-39说明说明如果说明某事实一定成立，则一定加以证明。如果说明某事实一定成立，则一定加以证明。 如要说明某一事实不一定成立，则可举一反如要说明某一事实不一定成立，则可举一反例加以说明。例加以说明。 如要说明某事实一定不成立，则也一定加以如要说明某事实一定不成立，则也一定加以证明。证明。2022-5-16智能科学系智能科学系95-40设设R R，S S是从集合是从集合A

41、 A到集合到集合B B的二元关系，则有：的二元关系，则有：1)1) ；( (双重否定律双重否定律) )R定理定理8.48.4SRRS RR1 ( (R R-1-1) )-1-1R R；(RS)(RS)-1-1R R-1-1SS-1-1；( (分配性分配性) )(RS)(RS)-1-1R R-1-1SS-1-1；(R-S)(R-S)-1-1R R-1-1-S-S-1-1；( () )-1-1 ；( (可换性可换性) )-1-1；(A(AB)B)-1-1(B(BA)A)；S S R R S S-1-1 R R-1-1；( (单调性单调性) ) ；domRdomR-1-1ranR,ranRranR,

42、ranR-1-1domRdomR。2022-5-16智能科学系智能科学系95-418.38.3关系的性质关系的性质8.3.18.3.1自反性与反自反性自反性与反自反性 定义定义8.108.10设设R R是集合是集合A A上的二元关系，上的二元关系，对任意的对任意的xA,xA,都满足都满足 Rx,xR，则称则称R R是是自反的自反的，或或称称R R具有具有自反性自反性，即，即R R在在A A上是自反的上是自反的( ( x)(xA)(R)=1x)(xA)(R)=1对任意的对任意的xA,xA,都满足都满足 x,x R R，则称则称R R是是反自反的反自反的，或称或称R R具有具有反自反性反自反性，即

43、，即R R在在A A上是反自反的上是反自反的( ( x)(xA)(x)(xA)(R)=1R)=1 2022-5-16智能科学系智能科学系95-42设设A=a,b,c,dA=a,b,c,d， 例例8 8. .1717 R=,R=,。1001010100100001RM因为因为A A中每个元素中每个元素x x，都有，都有RR，所以，所以R R是是自反的。自反的。R R的关系图的关系图R R的关系矩阵的关系矩阵2022-5-16智能科学系智能科学系95-43S=,S=,。例例8 8. .17(17(续续1 1) ) 0101001110000010SMS S的关系图的关系图S S的关系矩阵的关系矩阵

44、因为因为A A中每个元素中每个元素x x，都有，都有S S，所以，所以S S是是反自反的。反自反的。2022-5-16智能科学系智能科学系95-44T=,T=,。例例8 8. .17(17(续续2 2) ) 1110000110100010TM因为因为A A中有元素中有元素b b，使，使T T，所以，所以T T不是自不是自反的；因为反的；因为A A中有元素中有元素a a，使，使TT，所以，所以T T不是反自反的。不是反自反的。T T的关系图的关系图T T的关系矩阵的关系矩阵2022-5-16智能科学系智能科学系95-45任何不是自反的关系未必一定是反自反的关任何不是自反的关系未必一定是反自反的

45、关系，反之亦然。即存在既不是自反的也不是系，反之亦然。即存在既不是自反的也不是反自反的关系。反自反的关系。表现在关系图上：表现在关系图上：关系关系R R是自反的，当且仅当是自反的，当且仅当其关系图中每个结点都有环；关系其关系图中每个结点都有环；关系R R是反自反是反自反的，当且仅当其关系图中每个结点都无环。的，当且仅当其关系图中每个结点都无环。表现在关系矩阵上：表现在关系矩阵上：关系关系R R是自反的，当且仅是自反的，当且仅当其关系矩阵的主对角线上全为当其关系矩阵的主对角线上全为1 1；关系；关系R R是是反自反的当且仅当其关系矩阵的主对角线上反自反的当且仅当其关系矩阵的主对角线上全为全为0

46、0。 结论结论2022-5-16智能科学系智能科学系95-468.3.28.3.2对称性与反对称性对称性与反对称性定义定义8.118.11 设设R R是集合是集合A A上的二元关系，上的二元关系，对任意的对任意的x,yAx,yA，如果，如果RR，那么，那么RR，则，则称关系称关系R R是是对称的对称的，或称，或称R R具有具有对称性对称性，即，即R R在在A A上是对称的上是对称的 ( ( x)(x)( y)(xA)y)(xA)(yA)(R)(R)=1(yA)(R)(R)=1对任意的对任意的x,yx,y A A，如果，如果RR且且RR，那么，那么x=yx=y，则称关系，则称关系R R是是反对称

47、的反对称的，或称，或称R R具有具有反对称性反对称性，即即R R在在A A上是反对称的上是反对称的 ( ( x)(x)( y)(xA)y)(xA)(yA)(R)(R)(x=y)=1(yA)(R)(R)(x=y)=12022-5-16智能科学系智能科学系95-47设设A=a,b,c,dA=a,b,c,d， 例例8 8. .1818 R R1 1=,=,1101000100RM R R2 2=, =, 2101000000RMR R1 1的关系图的关系图R R1 1的关系矩阵的关系矩阵是对称的是对称的是反对称的是反对称的R R2 2的关系图的关系图R R2 2的关系矩阵的关系矩阵2022-5-16

48、智能科学系智能科学系95-48R R3 3=,=,例例8 8. .18(18(续续1 1) )3111000100RM R R4 4=,=,4100000001RM 既不是对称既不是对称的，也不是反对称的的，也不是反对称的R R3 3的关系图的关系图R R3 3的关系矩阵的关系矩阵既是对称的，也是反对称的既是对称的，也是反对称的R R3 3的关系图的关系图R R3 3的关系矩阵的关系矩阵2022-5-16智能科学系智能科学系95-49任何不是对称的关系未必一定是反对称的关系，反任何不是对称的关系未必一定是反对称的关系，反之亦然。即存在既不是对称的也不是反对称的关系，之亦然。即存在既不是对称的也

49、不是反对称的关系，也存在既是对称的也是反对称的关系。也存在既是对称的也是反对称的关系。表现在关系图上：表现在关系图上：关系关系R R是对称的当且仅当其关系图是对称的当且仅当其关系图中，任何一对结点之间，要么有方向相反的两条边，中，任何一对结点之间，要么有方向相反的两条边，要么无任何边；关系要么无任何边；关系R R是反对称的当且仅当其关系图是反对称的当且仅当其关系图中，任何一对结点之间，至多有一条边。中，任何一对结点之间，至多有一条边。表现在关系矩阵上：表现在关系矩阵上：关系关系R R是对称的当且仅当其关系是对称的当且仅当其关系矩阵为对称矩阵，即矩阵为对称矩阵，即r rijij=r=rjiji，

50、i,j=1,2, i,j=1,2, ,n,n；关系；关系R R是反对称的当且仅当其关系矩阵为反对称矩阵，即是反对称的当且仅当其关系矩阵为反对称矩阵，即r rijijr rjiji=0=0，i,j=1,2,i,j=1,2,n,n，ijij。 结论结论2022-5-16智能科学系智能科学系95-508.3.38.3.3传递性传递性定义定义8.128.12 设设R R是集合是集合A A上的二元关系，对任上的二元关系，对任意的意的x,y,zAx,y,zA，如果，如果RR且且RR，那么，那么RR，则称关系，则称关系R R是是传递的传递的，或称，或称R R具有具有传递传递性性，即，即R R在在A A上是传

51、递的上是传递的( ( x)(x)( y)(y)( z)(xA)(yA)(zA)z)(xA)(yA)(zA)(R)(R)(R)=1(R)(R)(R)=1 2022-5-16智能科学系智能科学系95-51设设A=a,b,c,dA=a,b,c,d， 例例8 8. .1 1 R R1 1=,=, R R2 2=11110001000000000RM20100000000000000RM是传递的是传递的R R1 1的关系图的关系图R R1 1的关系矩阵的关系矩阵是传递的是传递的R R2 2的关系图的关系图R R2 2的关系矩阵的关系矩阵2022-5-16智能科学系智能科学系95-52R R3 3=,=,

52、例例8 8. .19(19(续续1 1) ) R R4 4=,=,31100001000000000RM40110001000010000RM不是传递的不是传递的R R3 3的关系图的关系图R R3 3的关系矩阵的关系矩阵不是传递的不是传递的R R3 3的关系图的关系图R R3 3的关系矩阵的关系矩阵2022-5-16智能科学系智能科学系95-53表现在关系图上：表现在关系图上：关系关系R R是传递的当且仅当其是传递的当且仅当其关系图中，任何三个结点关系图中，任何三个结点x,y,zx,y,z（可以相同）（可以相同）之间，若从之间，若从x x到到y y有一条边存在，从有一条边存在，从y y到到z

53、 z有一有一条边存在，则从条边存在，则从x x到到z z一定有一条边存在。一定有一条边存在。表现在关系矩阵上：表现在关系矩阵上：关系关系R R是传递的当且仅当是传递的当且仅当其关系矩阵中，对任意其关系矩阵中，对任意i,j,k1,2,3,i,j,k1,2,3,n,n，若若r rijij=1=1且且r rjkjk=1=1，必有，必有r rikik=1=1。结论结论2022-5-16智能科学系智能科学系95-54在整数集在整数集I I上定义的上定义的“小于等于小于等于”关系是自反的、反对关系是自反的、反对称的、传递的关系；称的、传递的关系；“小于小于”关系是反自反的、反对称关系是反自反的、反对称的、

54、传递的关系；的、传递的关系；“等于等于”关系是自反的、反对称的、关系是自反的、反对称的、对称的、传递的关系。对称的、传递的关系。例例8 8.20.20例例8.218.21设设A A1,2,3,41,2,3,4，R R,，是是A A上的关系上的关系。幂集上的幂集上的“包含包含”关系关系是自反的、反对称的、传递关系关系是自反的、反对称的、传递的关系；的关系；“真包含真包含”关系是反自反的、反对称的、传递关系是反自反的、反对称的、传递的关系；的关系；“相等相等”关系是自反的、反对称的、对称的、关系是自反的、反对称的、对称的、传递的关系。传递的关系。则则R R即不是自反的，又非反自反的；即不是对称的，

55、也非即不是自反的，又非反自反的；即不是对称的，也非反对称的；也不是传递的。即不具备关系的任何性质。反对称的；也不是传递的。即不具备关系的任何性质。2022-5-16智能科学系智能科学系95-55设设A A是任意的集合，是任意的集合，A A上的全关系上的全关系A AA A是自反的、对称的、传递的是自反的、对称的、传递的关系；关系；A A上的空关系上的空关系是反自反的、反对称的、对称是反自反的、反对称的、对称的、传递的关系；的、传递的关系；1)1) A A上的恒等关系上的恒等关系I IA A是自反的、对称的、反对称是自反的、对称的、反对称的、传递的关系。的、传递的关系。例例8.228.22例例8.

56、238.23 朋友关系是自反的、对称的、而非传递的关系；朋友关系是自反的、对称的、而非传递的关系；1)1) 父子关系是反自反的、反对称的、而非传递的父子关系是反自反的、反对称的、而非传递的关系关系. .2022-5-16智能科学系智能科学系95-56设设A A1,2,3,1,2,3,试判断如下图所示试判断如下图所示A A上关系的上关系的性质：性质：例例8.248.242022-5-16智能科学系智能科学系95-57解解：从关系图易判断上述关系之性质如下：从关系图易判断上述关系之性质如下：图图a)a)的关系是自反的、对称的、反对称的、传递的关系；的关系是自反的、对称的、反对称的、传递的关系；图图

57、b)b)的关系是具备反自反的、对称的、反对称的、传递的的关系是具备反自反的、对称的、反对称的、传递的关系；关系；图图c)c)的关系是具备对称的、反对称的、传递的关系；的关系是具备对称的、反对称的、传递的关系；图图d)d)的关系是不具备任何的性质关系；的关系是不具备任何的性质关系；图图e)e)的关系是具备自反的、对称的、传递的关系；的关系是具备自反的、对称的、传递的关系；图图f)f)的关系是具备反自反的、反对称的、传递的关系；的关系是具备反自反的、反对称的、传递的关系；图图g)g)的关系是具备反自反的、反对称的关系；的关系是具备反自反的、反对称的关系；1)1)图图h)h)的关系是具备反自反的、反

58、对称的、传递的关系。的关系是具备反自反的、反对称的、传递的关系。例例8.24(8.24(续续1)1)2022-5-16智能科学系智能科学系95-58图a之例例8.24(8.24(续续2)2)100010001RM000000000RM图b之100000000RM110001110RM1 1 11 1 11 1 1RM011001000RM010001100RM011000000RM图c之图d之图e之图f之图g之图h之2022-5-16智能科学系智能科学系95-59设设R R,是定义在是定义在A Aa,ba,b上的二元关上的二元关系，系，S S,是定义在是定义在B Ba,b,ca,b,c上的二元

59、关上的二元关系系, ,试判断试判断R R，S S具备何种性质。具备何种性质。例例8.258.25解：解：1.1.由于由于R R,是定义在是定义在A Aa,ba,b上的关上的关系，所以，对任意的系，所以，对任意的xA,xA,都满足都满足 Rx,xR，则则R R是自反是自反的关系；另外，的关系；另外，R R也是对称的、反对称的和传递的也是对称的、反对称的和传递的. .2.2.S S,虽然与虽然与R R完全相等完全相等( (从集合的观点从集合的观点) )，但它却是定义在但它却是定义在B Ba,b,ca,b,c上的二元关系。由于上的二元关系。由于cBcB，但但 c,c S,S,所以，所以，S S不是不

60、是B B上的自反关系；另外，上的自反关系；另外，S S也是对也是对称的、反对称的和传递的。称的、反对称的和传递的。注意：注意：一个关系具备何种性质与他的基集密切相关，对一个关系具备何种性质与他的基集密切相关，对同一个关系如果定义在不同的基集上，可能产生不同的同一个关系如果定义在不同的基集上，可能产生不同的特性。所以，我们绝对不能脱离基集来谈论关系的性质。特性。所以，我们绝对不能脱离基集来谈论关系的性质。 2022-5-16智能科学系智能科学系95-60关系性质的逻辑表示关系性质的逻辑表示设设R R是集合是集合A A上的二元关系，上的二元关系，1)1) R R是自反的是自反的)Rx, x()Ax