二元关系实用教案.ppt

本章(běn￿zhānɡ)说明q本章(běn zhānɡ)的主要内容q有序对与笛卡儿集q二元关系的定义和表示法q关系的运算q关系的性质q等价关系与划分q偏序关系q本章(běn zhānɡ)与后续各章的关系q本章(běn zhānɡ)是函数的基础q本章(běn zhānɡ)是图论的基础 第1页/共128页第一页，共129页本章(běn￿zhānɡ)内容7.1￿有序对与笛卡儿积7.2￿二元关系7.3￿关系的运算7.4￿关系的性质(xìngzhì)7.6￿等价关系与划分7.7￿偏序关系￿￿￿￿本章小结￿￿￿￿习题￿￿￿￿作业第2页/共128页第二页，共129页7.1￿有序对与笛卡儿积￿定义7.1￿由两个(liǎnɡ￿ɡè)元素x和y（允许x=y）按一定顺序排列成的二元组叫做一个有序对(ordered￿pair)或序偶，记作，其中x是它的第一元素，y是它的第二元素有序对具有以下性质：￿（1）当x≠y时，≠￿（2）＝的充分必要条件是x＝u且y＝v￿说明(shuōmíng)q有序对中的元素(yuán sù)是有序的q集合中的元素(yuán sù)是无序的第3页/共128页第三页，共129页。

例7.1例7.1 已知＝<5,2x+y>，求x和y 由有序对相等由有序对相等(xiāngděng)(xiāngděng)的充要条件有的充要条件有 x+2x+2＝＝5 5 2x+y 2x+y＝＝4 4 解得解得 x x＝＝3,y3,y＝＝-2-2 解答(jiědá)第4页/共128页第四页，共129页定义7.2￿设A，B为集合,用A中元素为第一(dìyī)元素，B中元素为第二元素构成有序对所有这样的有序对组成的集合叫做A和B的笛卡儿积(Cartesian￿product)，记作A×B笛卡儿积的符号化表示为A×B＝{|x∈A∧y∈B}￿￿￿笛卡儿积的定义(dìngyì)qA A表示某大学所有学生的集合，表示某大学所有学生的集合，B B表示大学开设的所有课表示大学开设的所有课程的集合，程的集合，q则则A×BA×B可以用来表示该校学生选课的所有可能可以用来表示该校学生选课的所有可能(kěnéng)(kěnéng)情况q令令A A是直角坐标系中是直角坐标系中x x轴上的点集，轴上的点集，B B是直角坐标系中是直角坐标系中y y轴轴上的点集，上的点集，q于是于是A×BA×B就和平面点集一一对应。

就和平面点集一一对应 举例第5页/共128页第五页，共129页笛卡尔积举例(jǔ￿lì)设设A={a,b}, B={0,1,2}A={a,b}, B={0,1,2}，，则则A×B={,,,,,}A×B={,,,,,}B×A={<0,a>,<0,b>,<1,a>,<1,b>,<2,a>,<2,b>} B×A={<0,a>,<0,b>,<1,a>,<1,b>,<2,a>,<2,b>} 举例(jǔlì)说明(shuōmíng)q如果|A|=m,|B|=n,则|A×B|=mn第6页/共128页第六页，共129页笛卡儿积的运算(yùn￿suàn)性质￿(1)对任意集合A，根据定义(dìngyì)有A×＝,￿×A＝(2)一般的说，笛卡儿积运算不满足交换律，即A×B≠B×A￿(当￿A≠￿∧￿B≠￿∧￿A≠B￿时)(3)笛卡儿积运算不满足结合律，即(A×B)×C≠A×(B×C)(当￿A≠￿∧￿B≠￿∧￿C≠￿时)(4)笛卡儿积运算对并和交运算满足分配律，即A×(B∪C)=(A×B)∪(A×C)(B∪C)×A=(B×A)∪(C×A)A×(B∩C)=(A×B)∩(A×C)(B∩C)×A=(B×A)∩(C×A)(5)AC￿∧￿BD￿￿A×B￿￿C×D第7页/共128页第七页，共129页。

A×(B∪C)=(A×B)∪(A×C)的的证证明明(zhèngmíng)任取￿￿∈A×(B∪C)￿x∈A￿∧￿y∈B∪C￿x∈A￿∧￿(y∈B∨y∈C)￿￿(x∈A∧y∈B)￿∨￿(x∈A∧y∈C)￿￿∈A×B￿∨￿∈A×C￿￿∈(A×B)∪(A×C)￿所以(suǒyǐ)￿A×(B∪C)=(A×B)∪(A×C)第8页/共128页第八页，共129页例7.2例7.2 设A={1,2},求P(A)×A P(A)×AP(A)×A ＝＝ { {,{1},{2},{1,2}}×{1,2},{1},{2},{1,2}}×{1,2} ＝＝{<{<,1>,<,1>,<,2>,,2>, <{1},1>,<{1},2>,<{1},1>,<{1},2>,<{2},1>,<{2},2>,<{2},1>,<{2},2>,<{1,2},1>,<{1,2},2>}<{1,2},1>,<{1,2},2>} 解答(jiědá)第11页/共128页第十一页，共129页例7.3例7.3 设A，B，C，D为任意集合，判断以下命题是否(shì fǒu)为真，并说明理由。

1) A×B＝A×C  B＝C(2) A-(B×C)＝(A-B)×(A-C)(3) A＝B∧C＝D  A×C＝B×D(4) 存在集合A，使得A = A×A(1) (1) 不一定不一定(yīdìng)(yīdìng)为真当A A＝＝，，B B＝＝{1},C{1},C＝＝{2}{2}时，时，有有 A×B A×B＝＝＝＝A×CA×C，但，但B≠CB≠C2) (2) 不一定不一定(yīdìng)(yīdìng)为真当A=B={1},CA=B={1},C＝＝{2}{2}时，有时，有 A-(B×C) A-(B×C)＝＝{1}–{<1,2>}{1}–{<1,2>}＝＝{1}{1} (A-B)×(A-C) (A-B)×(A-C)＝＝×{1}×{1}＝＝(3) (3) 为真由等量代入的原理可证由等量代入的原理可证 (4) (4) 为真当A A＝＝时，有时，有 A=A×A A=A×A 成立 解答(jiědá)第12页/共128页第十二页，共129页7.2￿二元关系(binary￿relation)定义定义7.3 7.3 如果一个集合如果一个集合(jíhé)(jíhé)满足以下条件之一：满足以下条件之一：（（1 1）集合）集合(jíhé)(jíhé)非空，且它的元素都是有序对非空，且它的元素都是有序对（（2 2）集合）集合(jíhé)(jíhé)是空集是空集 则称该集合则称该集合(jíhé)(jíhé)为一个二元关系，记作为一个二元关系，记作R R。

二元关系也可简二元关系也可简称为关系对于二元关系称为关系对于二元关系R R，如果，如果∈R∈R，可记作，可记作xRyxRy；如；如果果 R R，则记作，则记作xRyxRy设设R1R1＝＝{<1,2>,}{<1,2>,}，，R2R2＝＝{<1,2>,a,b}{<1,2>,a,b}则则R1R1是二元关系，是二元关系，R2R2不是不是(bù shi)(bù shi)二元关系，只是一个二元关系，只是一个集合，除非将集合，除非将a a和和b b定义为有序对定义为有序对根据上面的记法可以写根据上面的记法可以写1R121R12，，aR1baR1b，，aR1caR1c等 举例(jǔlì)第13页/共128页第十三页，共129页集合A上的二元关系的数目依赖于A中的元素数如果|A|=n，那么|A×A|=n2， A×A的子集(zǐ jí)就有 个每一个子集(zǐ jí)代表一个A上的二元关系，所以A上有 个不同的二元关系例如|A|=3，则A上有 个不同的二元关系7.2￿二元关系定义定义7.4 7.4 设设A A，，B B为集合，为集合，A×BA×B的任何子集的任何子集(zǐ jí)(zǐ jí)所定义的二元关系叫所定义的二元关系叫做从做从A A到到B B的二元关系；特别当的二元关系；特别当A=BA=B时，则叫做时，则叫做A A上的二元关系。

上的二元关系 A={0,1}A={0,1}，，B={1,2,3}B={1,2,3}，那么，那么(nà me) (nà me) R1={<0,2>}R1={<0,2>}，，R2=A×BR2=A×B，，R3=R3= ，，R4={<0,1>}R4={<0,1>}等都是从等都是从A A到到B B的二元关系，而的二元关系，而R3R3和和R4R4同时也是同时也是A A上的上的二元关系二元关系 举例说明第14页/共128页第十四页，共129页常用(chánɡ￿yònɡ)的关系定义7.5￿对任意(rènyì)集合A，定义全域关系￿EA={|x∈A∧y∈A}=A×A￿恒等关系￿IA={|x∈A}空关系￿￿￿设设 A={1,2} A={1,2}，那么，那么(nà me)(nà me)EA={<1,1>,<1,2>,<2,1>,<2,2>}EA={<1,1>,<1,2>,<2,1>,<2,2>}IA={<1,1>,<2,2>} IA={<1,1>,<2,2>} 举例第15页/共128页第十五页，共129页其它常用(chánɡ￿yònɡ)的关系•小于或等于关系：LA={|x,y∈A∧x≤y}，其中￿AR。

•整除关系：DB={|x,y∈B∧x整除y}，其中￿AZ*￿Z*是非零整数集•包含(bāohán)关系：R＝{|x,y∈A∧xy}，其中￿A是集合族￿(1)(1)设设 A={1,2,3} A={1,2,3}，，B B＝＝{a,b}{a,b}则则 LA={<1,1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3>} LA={<1,1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3>} DA={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>} DA={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>} (2)(2)令令A=P(B)={A=P(B)={,{a},{b},{a,b}},{a},{b},{a,b}}，则，则A A上的包含上的包含(bāohán)(bāohán)关系是关系是 R R ＝＝{<{<, ,>,<>,<,{a}>,<,{a}>,<,{b}>,<,{b}>,<,{a,b}>,,{a,b}>, <{a},{a}>,<{a},{a,b}>,<{b},{b}>, <{a},{a}>,<{a},{a,b}>,<{b},{b}>, <{b},{a,b}>,<{a,b},{a,b}>} <{b},{a,b}>,<{a,b},{a,b}>} 举例第16页/共128页第十六页，共129页。

例7.4例7.4￿设A={1,2,3,4}，下面各式定义的R都是A上的关系(guān￿xì)，试用列元素法表示R1)￿R={￿|￿x是y的倍数}(2)￿R={￿|￿(x-y)2∈A}(3)￿R={￿|￿x/y是素数}(4)￿R={￿|￿x≠y}￿解答(jiědá)(1)(1)R={<4,4>,<4,2>,<4,1>,<3,3>,<3,1>,<2,2>,<2,1>,<1,1>} R={<4,4>,<4,2>,<4,1>,<3,3>,<3,1>,<2,2>,<2,1>,<1,1>} (2)(2)R={<2,1>,<3,2>,<4,3>,<3,1>,<4,2>,<2,4>,<1,3>,<3,4>,R={<2,1>,<3,2>,<4,3>,<3,1>,<4,2>,<2,4>,<1,3>,<3,4>,<2,3>,<1,2>}<2,3>,<1,2>}(3)(3)R={<2,1>,<3,1>,<4,2>}R={<2,1>,<3,1>,<4,2>}(4)R=E(4)R=EA A-I-IA A={<1,2>,<1,3>,<1,4>,<2,1>,<2,3>,<2,4>,<3,1>,={<1,2>,<1,3>,<1,4>,<2,1>,<2,3>,<2,4>,<3,1>, <3,2>,<3,4>,<4,1>,<4,2>,<4,3>} <3,2>,<3,4>,<4,1>,<4,2>,<4,3>} 第17页/共128页第十七页，共129页。

关系的表示(biǎoshì)方法•关系的三种表示方法：•集合(jíhé)表达式•关系矩阵•关系图•关系矩阵和关系图可以表示有穷集上的关系第18页/共128页第十八页，共129页关系(guān￿xì)矩阵和关系(guān￿xì)图的定义设设A={x1,x2,…,xn},RA={x1,x2,…,xn},R是是A A上的关系上的关系(guān xì)(guān xì)令 则则 是是R R的关系的关系(guān xì)(guān xì)矩阵，记作矩阵，记作MRMR 设设A={xA={x1 1,x,x2 2, ,…,x,xn n},R},R是是A A上的关系令图上的关系令图G=G=，，其中顶点集合其中顶点集合V=AV=A，，边集为边集为E E对于对于  x xi i,x,xj j∈V∈V，，满足满足 < ∈E >∈E  x xi iRxRxj j称图称图G G为为R R的的关系图关系图，记作，记作 G GR R第19页/共128页第十九页，共129页关系(guān￿xì)矩阵和关系(guān￿xì)图的实例设设 A={1,2,3,4} A={1,2,3,4}，，R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>}R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>}，，则则R R的关系的关系(guān xì)(guān xì)矩阵和关系矩阵和关系(guān xì)(guān xì)图分别是图分别是 第20页/共128页第二十页，共129页。

7.3￿关系(guān￿xì)的运算定义7.6￿设R是二元关系1)R中所有有序对的第一元素构成的集合称为(chēnɡ￿wéi)R的定义域(domain)，记为dom￿R形式化表示为：dom￿R￿＝￿{x￿|￿y(∈R￿)}(2)R中所有有序对的第二元素构成的集合称为(chēnɡ￿wéi)R的值域(range)￿，记作ran￿R形式化表示为ran￿R＝{y￿|￿￿￿x(∈R)}(3)R的定义域和值域的并集称为(chēnɡ￿wéi)R的域(field)，记作fld￿R形式化表示为fld￿R＝dom￿R￿∪￿ran￿R￿￿￿例7.5 求R={<1,2>,<1,3>,<2,4>,<4,3>}的定义域、值域和域 解答(jiědá)dom R＝{1,2,4} ran R＝{2,3,4} fld R＝{1,2,3,4} 第21页/共128页第二十一页，共129页关系(guān￿xì)的逆和右复合运算定义7.7￿设R为二元关系(guān￿xì)，R的逆关系(guān￿xì)，简称R的逆(inverse)，记作R-1,其中R-1＝{|∈R}定义7.8￿设F,G为二元关系(guān￿xì)，G对F的右复合(composite)记作FG，其中FG＝{￿|￿t(∈F∧∈G)}例7.6￿设F＝{<3,3>,<6,2>},G={<2,3>}，则F-1￿＝{<3,3>,<2,6>}FG＝{<6,3>}GF＝{<2,3>}说明(shuōmíng)q可以把二元关系看作一种作用，∈R可以解释为x通过R的作用变到y。

qFG表示两个作用的连续发生第22页/共128页第二十二页，共129页关系(guān￿xì)的限制和像定义7.9￿设R为二元关系，A是集合(jíhé)(1)￿R在A上的限制(restriction)记作R↑A，其中R↑A={|xRy∧x∈A}￿(2)￿A在R下的像(image)记作R[A]，其中R[A]=ran(R↑A)￿说明(shuōmíng)qR在A上的限制R↑A是R的子关系qA在R下的像R[A]是ran R的子集第23页/共128页第二十三页，共129页例7.7设设R R＝＝{<1,2>{<1,2>，，<1,3><1,3>，，<2,2><2,2>，，<2,4><2,4>，，<3,2>}<3,2>}R↑{1}＝{<1,2>，<1,3>}R↑ ＝R↑{2,3}＝{<2,2>，<2,4>}，<3,2>}R[{1}]＝{2,3}R[] ＝R[{3}]＝{2}第24页/共128页第二十四页，共129页关系与集合(jíhé)的说明•关系是集合，集合运算对于关系也是适用的￿•规定：•关系运算中逆运算优先于其它(qítā)运算•所有的关系运算都优先于集合运算，•优先权的运算以括号决定运算顺序。

￿•例如：•ran￿F-1•FG∪FH•ran￿(F↑A)第25页/共128页第二十五页，共129页例题(lìtí)•设A表示是学校的所有学生(xué￿sheng)的集合，B表示学校的所有课程的集合，并设R1由所有有序对组成，其中a是选修课程b的学生(xué￿sheng)R2由所有的有序对构成，其中课程b是a的必修课则关系R1∪R2、R1∩R2、R1⊕R2、R1－R2、R2－R1的含义为•R1∪R2：a是一个学生(xué￿sheng)，他或者选修了课程b，或者课程b是他的必修课•R1∩R2：a是一个学生(xué￿sheng)，他选修了课程b并且课程b也是a的必修课￿•R1⊕R2：学生(xué￿sheng)a已经选修了课程b，但课程b不是a的必修课，或者课程b是a的必修课，但是a没有选修它•R1－R2：学生(xué￿sheng)a已经选修了课程b，但课程b不是a的必修课￿•R2－R1：课程b是学生(xué￿sheng)a的必修课，但是a没有选修它￿￿￿￿第26页/共128页第二十六页，共129页定理(dìnglǐ)7.1定理(dìnglǐ)7.1￿设F是任意的关系，则￿(1)(F-1)-1＝F￿(2)dom￿F-1＝ran￿F，ran￿F-1＝dom￿F￿(1)(1)任取任取，由逆的定义，由逆的定义(dìngyì)(dìngyì)有有 ∈(F-1)-1 ∈(F-1)-1 ∈F-1 ∈F-1 ∈F ∈F (2)(2)任取任取x x x x∈∈dom dom F F-1-1  y y(∈F>∈F-1-1) )  y y(<(∈F) ,x>∈F)  x∈ran F x∈ran F 所以有所以有 dom Fdom F-1-1＝＝ran Fran F证明第27页/共128页第二十七页，共129页。

关系(guān￿xì)的幂运算定义(dìngyì)7.10￿设R为A上的关系，n为自然数，则R的n次幂定义(dìngyì)为：（1）￿R0＝{|x∈A}＝IA（2）￿Rn+1＝Rn￿￿R说明(shuōmíng)q对于A上的任何关系R1和R2都有R10＝R20＝IA 即：A上任何关系的0次幂都相等，都等于A上的恒等关系IAq对于A上的任何关系R都有R1＝R，因为R1＝R0  R＝IA  R＝R第36页/共128页第三十六页，共129页Rn的计算的计算(jì suàn)•给定A上的关系R和自然数n，怎样计算Rn呢？•若n是0或1，结果是很简单的下面考虑n≥2的情况•如果R是用集合表达式给出的，可以通过n-1次右复合计算得到Rn•如果R是用关系矩阵M给出的，则Rn的关系矩阵是Mn，即n个矩阵M之积与普通矩阵乘法(chéngfǎ)不同的是，其中的相加是逻辑加，即•1+1＝1，1+0＝0+1＝1，0+0＝0•如果R是用关系图G给出的，可以直接由图G得到Rn的关系图G'G'的顶点集与G相同考察G的每个顶点xi，如果在G中从xi出发经过n步长的路径到达顶点xj，则在G'中加一条从xi到xj的边。

当把所有这样的便都找到以后，就得到图G'￿第37页/共128页第三十七页，共129页例7.8例7.8￿设A＝{a,b,c,d}，R＝{,,,}，求R的各次幂，分别(fēnbié)用矩阵和关系图表示￿解答(jiědá)第38页/共128页第三十八页，共129页例7.8因此M4＝M2，即R4＝R2因此可以得到R2＝R4＝R6＝…R3＝R5＝R7＝…￿用关系图的方法(fāngfǎ)得到R0,￿R1,￿R2,￿R3,…的关系图如下图所示第39页/共128页第三十九页，共129页幂运算(yùn￿suàn)的性质定理(dìnglǐ)7.6￿设A为n元集，R是A上的关系，则存在自然数s和t,使得Rs=RtR为A上的关系(guān xì)，对任何自然数k，Rk都是A×A的子集证明又知|A×A|=n2，|P(A×A)|= ，即A×A的不同子集仅 个当列出R的各次幂R0，R1，R2，…， ，…时，必存在自然数s和t使得Rs=Rt说明q该定理说明有穷集上只有有穷多个不同的二元关系当t足够大时，Rt必与某个Rs(s

第40页/共128页第四十页，共129页定理(dìnglǐ)7.8的说明•有穷集A上的关系R的幂序列R0，R1，…是一个周期性变化的序列就象正弦函数(hánshù)一样，利用它的周期性可以将R的高次幂化简为R的低次幂•例7.9￿设A={a,b,d,e,f}，R={,,,,}求出最小的自然数m和n，使得m

即满足题目要求第45页/共128页第四十五页，共129页7.4￿关系(guān￿xì)的性质•自反性•反自反性•对称性•反对称性•传递性第46页/共128页第四十六页，共129页自反性和反自反性定义(dìngyì)7.11￿设R为A上的关系，(1)若x(x∈A→∈R)，则称R在A上是自反(reflexivity)的2)若x(x∈A→R)，则称R在A上是反自反(irreflexivity)的例如￿全域关系EA，恒等关系IA，小于等于关系LA，整除关系DA都是为A上的自反关系包含关系R是给定集合族A上的自反关系小于关系和真包含关系都是给定集合或集合族上的反自反关系第47页/共128页第四十七页，共129页例7.10例7.10 设A={1,2,3}，R1，R2，R3是A上的关系，其中R1＝{<1,1>,<2,2>}R2＝{<1,1>,<2,2>,<3,3>,<1,2>}R3＝{<1,3>}说明R1，R2和R3是否为A上的自反(zì fǎn)关系和反自反(zì fǎn)关系解答 R1既不是自反(zì fǎn)的也不是反自反(zì fǎn)的，R2是自反(zì fǎn)的，R3是反自反(zì fǎn)的。

第48页/共128页第四十八页，共129页对称性和反对称性定义7.12￿设R为A上的关系，（1）若xy(x,y∈A∧∈R→∈R)，则称R为A上对称(symmetry)的关系2）若xy(x,y∈A∧∈R∧∈R→x=y)，则称R为A上的反对称(antisymmetry)关系￿例如(lìrú)￿A上的全域关系EA，恒等关系IA和空关系都是A上的对称关系恒等关系IA和空关系也是A上的反对称关系但全域关系EA一般不是A上的反对称关系，除非A为单元集或空集第49页/共128页第四十九页，共129页例7.11例7.11￿设A＝{1,2,3}，R1，R2，R3和R4都是A上的关系，其中(qízhōng)R1＝{<1,1>,<2,2>}R2＝{<1,1>,<1,2>,<2,1>}R3＝{<1,2>,<1,3>}R4＝{<1,2>,<2,1>,<1,3>}说明R1，R2，R3和R4是否为A上对称和反对称的关系解答￿R1既是对称也是反对称的R2是对称的但不是反对称的R3是反对称的但不是对称的R4既不是对称的也不是反对称的第50页/共128页第五十页，共129页。

传递性定义(dìngyì)7.13￿设R为A上的关系，若xyz(x,y,z∈A∧∈R∧∈R→∈R)则称R是A上的传递(transitivity)关系例如￿A上的全域关系EA,恒等关系IA和空关系都是A上的传递关系小于等于关系，整除关系和包含关系也是相应集合上的传递关系小于关系和真包含关系仍旧是相应集合上的传递关系￿第51页/共128页第五十一页，共129页例7.12例7.12￿设A＝{1,2,3}，R1，R2，R3是A上的关系(guān￿xì)，其中R1＝{<1,1>,<2,2>}R2＝{<1,2>,<2,3>}R3＝{<1,3>}说明R1，R2和R3是否为A上的传递关系(guān￿xì)解答￿R1和R3是A上的传递关系(guān￿xì)，R2不是A上的传递关系(guān￿xì)￿第52页/共128页第五十二页，共129页关系(guān￿xì)性质的等价描述￿定理7.9￿设R为A上的关系，则（1）R在A上自反当且仅当￿IA￿￿R（2）R在A上反自反当且仅当￿R∩IA＝（3）R在A上对称(duìchèn)当且仅当￿R＝R-1（4）R在A上反对称(duìchèn)当且仅当￿R∩R-1￿￿IA（5）R在A上传递当且仅当￿RRR￿说明(shuōmíng)q利用该定理可以从关系的集合表达式来判断或证明关系的性质。

分析关系性质的证明方法关系性质的证明方法第53页/共128页第五十三页，共129页定理(dìnglǐ)7.9￿(1)的证明（1）￿R在A上自反(zì￿fǎn)当且仅当￿IA￿￿R必要性￿￿任取，有￿￿￿￿∈IA￿￿￿￿x,y∈A￿∧￿x＝y￿￿￿∈R￿￿所以￿IA￿￿R充分性 任取x，有 x∈A  ∈IA  ∈R 所以(suǒyǐ) R在A上是自反的第54页/共128页第五十四页，共129页定理(dìnglǐ)7.9￿(2)的证明（2）R在A上反自反当且仅当￿R∩IA＝充分性 任取x，有 x∈A  ∈IA  R (R∩IA= ) 所以(suǒyǐ) R在A上是反自反的用反证法 假设(jiǎshè)R∩IA≠， 必存在∈R∩IA 由于IA是A上恒等关系， 可知 x∈A且∈R 这与R在A上是反自反的相矛盾第55页/共128页第五十五页，共129页定理(dìnglǐ)7.9￿(3)的证明（3）￿R在A上对称(duìchèn)当且仅当￿R＝R-1必要性。

任取，有￿￿￿∈R￿￿∈R(因为R在A上对称(duìchèn))￿∈R-1￿所以￿R＝R-1充分性 任取， 由 R＝R-1 得 ∈R  ∈R-1  ∈R 所以(suǒyǐ) R在A上是对称的第56页/共128页第五十六页，共129页定理(dìnglǐ)7.9￿(4)的证明（4）￿R在A上反对(fǎnduì)称当且仅当￿R∩R-1￿￿IA必要性￿￿任取，有￿￿￿∈R∩R-1￿∈R￿∧￿∈R-1￿∈R￿∧￿∈R￿x＝y￿(R是反对(fǎnduì)称的)￿∈IA所以￿R∩R-1￿IA充分性任取, ∈R ∧ ∈R ∈R ∧ ∈R-1 ∈R∩R-1 ∈IA (R∩R-1 IA) x＝y所以(suǒyǐ) R在A上是反对称的第57页/共128页第五十七页，共129页定理(dìnglǐ)7.9￿(5)的证明（5）￿R在A上传递(chuándì)当且仅当￿RRR必要性。

任取，有￿￿￿∈RR￿t(∈R∧∈R)￿￿∈R(因为R在A上是传递(chuándì)的)所以￿RRR任取,∈R，则￿￿￿∈R∧∈R￿∈RR￿∈R￿(因为RRR)所以￿R在A上是传递(chuándì)的第58页/共128页第五十八页，共129页例7.13例7.13￿设A是集合，R1和R2是A上的关系，证明(zhèngmíng)：(1)若R1，R2是自反的和对称的，则R1∪R2也是自反的和对称的2)若R1和R2是传递的，则R1∩R2也是传递的第59页/共128页第五十九页，共129页例7.13￿(1)的证明(zhèngmíng)(1)若R1，R2是自反(zì￿fǎn)的和对称的，则R1∪R2也是自反(zì￿fǎn)的和对称的证明(zhèngmíng)由于由于R R1 1和和R R2 2是是A A上的自反关系，故有上的自反关系，故有I IA A   R R1 1 和和 I IA A   R R2 2从而得到从而得到 I IA A   R R1 1∪R∪R2 2。

根据定理根据定理7.97.9可知可知 R R1 1∪R∪R2 2在在A A上是自反的上是自反的再由再由R R1 1和和R R2 2的对称性有的对称性有R R1 1＝＝R R1 1-1 -1 和和 R R2 2＝＝R R2 2-1-1根据练习七第根据练习七第1818题的结果有题的结果有( (R R1 1∪R∪R2 2) )-1-1＝＝R R1 1-1-1∪R∪R2 2-1-1＝＝R R1 1∪R∪R2 2从而证明了从而证明了R R1 1∪R∪R2 2也是也是A A上对称的关系上对称的关系第60页/共128页第六十页，共129页例7.13￿(2)的证明(zhèngmíng)(2)若R1和R2是传递(chuándì)的，则R1∩R2也是传递(chuándì)的证明(zhèngmíng)由由R R1 1和和R R2 2的传递性有的传递性有R R1 1   R R1 1   R R1 1 和和 R R2 2   R R2 2   R R2 2再使用定理再使用定理7.47.4得得 ( (R R1 1∩R∩R2 2) ) (R(R1 1∩R∩R2 2) )   R R1 1   R R1 1∩R∩R1 1   R R2 2∩R∩R2 2   R R1 1∩R∩R2 2   R R2 2  (R(R1 1∩R∩R2 2)∩R)∩R1 1   R R2 2∩R∩R2 2   R R1 1 ( (将前面的包含式代入将前面的包含式代入) )   R R1 1∩R∩R2 2从而证明了从而证明了R R1 1∩R∩R2 2也是也是A A上的传递关系。

上的传递关系 第61页/共128页第六十一页，共129页关系(guān￿xì)性质的特点自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性集合表达式集合表达式I IA A   R RR∩IR∩IA A＝＝R R＝＝R R-1-1R∩RR∩R-1 -1   I IA AR R R R R R关系矩阵关系矩阵主对角线主对角线元素全是元素全是1 1主对角线元主对角线元素全是素全是0 0 矩阵是对称矩阵是对称矩阵矩阵 若若r rijij＝＝1 1，，且且i≠ji≠j，，则则r rjiji＝＝0 0 对对M M2 2中中1 1所在所在位置，位置，M M中中相应的位置相应的位置都是都是1 1 关系图关系图每个顶点每个顶点都有环都有环每个顶点都每个顶点都没有环没有环 如果两个顶如果两个顶点之间有边，点之间有边，一定是一对一定是一对方向相反的方向相反的边边( (无单边无单边) ) 如果两点之如果两点之间有边，一间有边，一定是一条有定是一条有向边向边( (无双无双向边向边) ) 如果顶点如果顶点x xi i到到x xj j有边，有边，x xj j到到x xk k有边，有边，则从则从x xi i到到x xk k也有边也有边 第62页/共128页第六十二页，共129页。

例7.14例7.14￿判断下图中关系的性质(xìngzhì)，并说明理由￿（1）对称的，不是自反的，不是反自反的，不是反对(fǎnduì)称的，不是传递的2）是反自反的，不是自反的，是反对(fǎnduì)称的，不是对称的，是传递的3）是自反的，不是反自反的，是反对(fǎnduì)称的，不是对称的，不是传递的第63页/共128页第六十三页，共129页关系(guān￿xì)的性质和运算之间的关系(guān￿xì)自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性R R1 1-1-1√√√√√√√√√√R R1 1∩R∩R2 2√√√√√√√√√√R R1 1∪R∪R2 2√√√√√√××××R R1 1－－R R2 2××√√√√√√××R R1 1   R R2 2√√××××××××第64页/共128页第六十四页，共129页7.6￿等价关系与划分(huà￿fēn)定义7.15￿设R为非空集合上的关系如果(rúguǒ)R是自反的、对称的和传递的，则称R为A上的等价关系(equivalent￿relation)设R是一个等价关系，若∈R，称x等价于y，记做x～y。

￿举例￿(1)平面上三角形集合中，三角形的相似关系2)人群中的同性关系第87页/共128页第八十七页，共129页例7.16例7.16￿设A＝{1,2,…,8}，如下定义(dìngyì)A上的关系R：R＝{|x，y∈A∧x≡y(mod￿3)}其中x≡y(mod￿3)叫做x与y模3相等，即x除以3的余数与y除以3的余数相等不难验证R为A上的等价关系，因为x∈A，有x≡x(mod￿3)x,y∈A，若x≡y(mod￿3)，则有y≡x(mod￿3)x,y,z∈A，若x≡y(mod￿3)，y≡z(mod￿3)，则有x≡z(mod￿3)第88页/共128页第八十八页，共129页等价(děngjià)类定义7.16￿设R为非空集合A上的等价(děngjià)关系，x∈A，令[x]R={y|y∈A∧xRy}称[x]R为x关于R的等价(děngjià)类，简称为x的等价(děngjià)类，简记为[x]或￿x￿qx x的等价的等价(děngjià)(děngjià)类是类是A A中所有与中所有与x x等价等价(děngjià)(děngjià)的元素构成的元素构成的集合。

的集合 q例例7.167.16中的等价中的等价(děngjià)(děngjià)类是：类是：q[1][1]＝＝[4][4]＝＝[7][7]＝＝{1,4,7}{1,4,7}q[2][2]＝＝[5][5]＝＝[8][8]＝＝{2,5,8}{2,5,8}q[3][3]＝＝[6][6]＝＝{3,6} {3,6} 第89页/共128页第八十九页，共129页整数(zhěngshù)集合Z上的模n等价关系设x是任意整数，n为给定的正整数，则存在唯一的整数q和r，使得x＝qn+r其中0≤r≤n-1，称r为x除以n的余数例如n＝3，那么－8除以3的余数为1，因为￿-8＝-3×3+1对于任意的整数x和y，定义模n相等关系～x～y￿￿x≡y(mod￿n)不难验证它是整数集合Z上的等价关系将Z中的所有整数根据它们除以n的余数分类(fēn￿lèi)如下：余数为0的数，其形式为nz，z∈Z余数为1的数，其形式为nz+1，z∈Z…￿余数是n-1的数，其形式为nz+n-1，z∈Z以上构成了n个等价类，使用等价类的符号可记为[i]＝{nz+i|z∈Z}，i=0，1，…，n-1第90页/共128页第九十页，共129页。

等价(děngjià)类的性质定理7.14￿设R是非空集合A上的等价关系，则（1）x∈A，[x]是A的非空子集（2）x,y∈A，如果xRy，则[x]＝[y]（3）x,y∈A，如果R，则[x]与[y]不交（4）∪{[x]|x∈A}＝A证明（1）￿由等价类的定义可知(kě￿zhī)，￿x∈A有[x]A又由于等价关系的自反性有x∈[x]，即[x]非空￿第91页/共128页第九十一页，共129页定理(dìnglǐ)7.14（2）x,y∈A，如果(rúguǒ)xRy，则[x]=[y]任取z，则有￿￿￿z∈[x]￿￿∈R￿￿∈R(因为R是对称的)￿∈R￿∧￿∈R￿∈R(因为R是传递的)￿∈R￿￿(因为R是对称的)￿￿z∈[y]所以￿[x][y]同理可证￿[y][x]因此，[x]=[y]第92页/共128页第九十二页，共129页定理(dìnglǐ)7.14（3）x,y∈A，如果R，则[x]与[y]不交假设￿[x]∩[y]≠￿，则存在￿z∈[x]∩[y]，从而有￿z∈[x]∧z∈[y]，即∈R∧∈R成立。

根据R的对称性和传递性，必有∈R，与R矛盾，即假设错误(cuòwù)，原命题成立￿第93页/共128页第九十三页，共129页定理(dìnglǐ)7.14（4）∪{[x]|x∈A}＝A￿先证￿∪{[x]|x∈A}A任取y，y∈∪{[x]|x∈A}￿￿x(x∈A∧y∈[x])￿￿y∈A￿(因为[x]A)从而(cóng￿ér)有∪{[x]|x∈A}￿A再证￿A∪{[x]|x∈A}任取y，y∈A￿￿y∈[y]∧y∈A￿￿￿￿￿y∈∪{[x]|x∈A}从而(cóng￿ér)有A{[x]|x∈A}成立综上所述得￿∪{[x]|x∈A}＝A第94页/共128页第九十四页，共129页商集定义7.17￿设R为非空集合A上的等价关系，以R的所有等价类作为(zuòwéi)元素的集合称为A关于R的商集(quotient￿set)，记做A/R，即A/R={[x]R|x∈A}例7.16中的商集为{{1,4,7},{2,5,8},{3,6}}整数集合Z上模n等价关系的商集是{{nz+i|z∈Z}|i=0,1,…,n-1}第95页/共128页第九十五页，共129页。

划分(huà￿fēn)定义7.18￿设A为非空集合，若A的子集族π(πP(A)，是A的子集构成的集合)￿满足下面的条件：（1）π（2）xy(x,y∈π∧x≠y→x∩y＝)（3）∪π=A则称π是A的一个划分(huà￿fēn)(partitions)，称π中的元素为A的划分(huà￿fēn)块说明(shuōmíng)q设集合π是A的非空子集的集合，若这些非空子集两两不相交，且它们的并等于A，则称π是集合A的划分第96页/共128页第九十六页，共129页例7.17例7.17￿设A＝{a,b,c,d}，给定π1,π2,π3,π4,π5,π6,如下(rúxià)：π1={{a,b,c},{d}}π2={{a,b},{c},{d}}π3={{a},{a,b,c,d}}π4={{a,b},{c}}π5={,{a,b},{c,d}}π6={{a,{a}},{b,c,d}}判断哪一个是A的划分π1和π2是A的划分，其它都不是A的划分因为π3中的子集{a}和{a,b,c,d}有交，∪π4≠A，π5中含有空集，而π6根本不是A的子集族第97页/共128页第九十七页，共129页。

商集与划分(huà￿fēn)•商集就是A的一个划分，并且(bìngqiě)不同的商集将对应于不同的划分•反之，任给A的一个划分π，如下定义A上的关系R：•R={|x,y∈A∧x与y在π的同一划分块中}•则不难证明R为A上的等价关系，且该等价关系所确定的商集就是π•由此可见，A上的等价关系与A的划分是一一对应的￿第98页/共128页第九十八页，共129页例7.18例7.18￿给出A＝{1,2,3}上所有(suǒyǒu)的等价关系这些划分与这些划分与A A上的等价关系之间的一一对应上的等价关系之间的一一对应(duìyìng)(duìyìng)是：是：π1π1对应对应(duìyìng)(duìyìng)于全域关系于全域关系EAEA，，π5π5的对应的对应(duìyìng)(duìyìng)于恒等关系于恒等关系IAIA，，π2π2，，π3π3和和π4π4分别对应分别对应(duìyìng)(duìyìng)于等价关系于等价关系R2R2，，R3R3和和R4R4 其中其中 R2={<2,3>,<3,2>}∪IAR2={<2,3>,<3,2>}∪IAR3={<1,3>,<3,1>}∪IAR3={<1,3>,<3,1>}∪IAR4={<1,2>,<2,1>}∪IAR4={<1,2>,<2,1>}∪IA第99页/共128页第九十九页，共129页。

例题(lìtí)例题￿问集合A＝{a,b,c,d}上有多少个不同的等价关系？解答￿只要求出A上的全部划分，即为等价关系划分为一个(yī￿ɡè)块的情况：1种，即{a,b,c,d}划分为两个块的情况：7种，即{{a,b},{c,d}}，{{a,c},{b,d}}，{{a,d},{b,c}}{{a},{b,c,d}}，{{b},{a,c,d}}，{{c},{a,b,d}}，{{d},{a,b,c}}划分为三个块的情况：6种，即{{a,b},{c},{d}}，{{a,c},{b},{d}}，{{a,d},{b},{c}},{{a},{b},{c,d}}，{{a},{c},{b,d}}，{{a},{d},{b,c}}划分为四个块的情况：1种，即{a},{b},{c},{d}}因此，共有15种不同的等价关系第100页/共128页第一百页，共129页7.7￿偏序(partial￿order)关系(guān￿xì)定义7.19￿设R为非空集合A上的关系如果R是自反(zì￿fǎn)的、反对称的和传递的，则称R为A上的偏序关系，记作≤设≤为偏序关系，如果∈≤，则记作x≤y，读作“x小于或等于y”。

注意￿这里的“小于或等于”不是指数的大小，而是在偏序关系中的顺序性x“小于或等于”y的含义是：依照这个序，x排在y的前边或者x就是y根据不同偏序的定义，对序有着不同的解释偏序关系举例集合A上的恒等关系IA小于或等于关系整除关系包含关系￿￿第101页/共128页第一百零一页，共129页可比定义7.20￿设R为非空集合( jíhé)A上的偏序关系，定义(1)￿x,y∈A，x＜y￿￿x≤y∧x≠y(2)￿x,y∈A，x与y可比￿￿x≤y∨y≤x其中x＜y读作x“小于”y这里所说的“小于”是指在偏序中x排在y的前边在具有偏序关系的集合( jíhé)A中任取两个元素x和y，可能有下述几种情况发生：x＜y(或y＜x)，x＝y，x与y不是可比的例如A＝{1，2，3}，≤是A上的整除关系，则有1＜2，1＜3，1=1，2=2，3=3，2和3不可比第102页/共128页第一百零二页，共129页全序关系(guān￿xì)定义7.21￿设R为非空集合( jíhé)A上的偏序关系，如果x,y∈A，x与y都是可比的，则称R为A上的全序关系(或线序关系)例如数集上的小于或等于关系是全序关系，因为任何两个数总是可比大小的。

整除关系一般来说不是全序关系，如集合( jíhé){1,2,3}上的整除关系就不是全序关系，因为2和3不可比￿第103页/共128页第一百零三页，共129页偏序集定义(dìngyì)7.22￿集合A和A上的偏序关系≤一起叫做偏序集，记作例如￿整数集合Z和数的小于或等于关系≤构成偏序集集合A的幂集P(A)和包含关系R构成偏序集第104页/共128页第一百零四页，共129页覆盖(fùgài)(cover)定义7.23￿设为偏序集￿x,y∈A，如果￿x＜y￿且不存在￿z∈A使得(shǐ￿de)x＜z＜y，则称y覆盖x例如￿{1,2,4,6}集合上的整除关系，有2覆盖1，4和6都覆盖2但4不覆盖1，因为有1＜2＜46也不覆盖4，因为4＜6不成立第105页/共128页第一百零五页，共129页哈斯图(Hasse diagram)•利用偏序关系的自反性、反对称性和传递性所得到的偏序集合图，称为哈斯图•画偏序集的哈斯图的方法•(1)用小圆圈代表元素•(2)x,y∈A，若x＜y，则将x画在y的下方(xià￿fānɡ)•(3)对于A中的两个不同元素x和y，如果y覆盖x，就用一条线段连接x和y。

第106页/共128页第一百零六页，共129页例7.19例7.19￿画出偏序集<{1,2,3,4,5,6,7,8,9}，R整除(zhěngchú)>和的哈斯图￿第107页/共128页第一百零七页，共129页例7.20例7.20￿已知偏序集的哈斯图如右图所示，试求出集合( jíhé)A和关系R的表达式￿解答(jiědá)A={a,b,c,d,e,f,g,h}R={ ,,,,,,,,}∪IA 第108页/共128页第一百零八页，共129页偏序集中(jízhōng)的特殊元素定义(dìngyì)7.24￿设为偏序集，BA，y∈B（1）若x(x∈B→y≤x)成立，则称y为B的最小元（2）若x(x∈B→x≤y)成立，则称y为B的最大元（3）若x(x∈B∧x≤y→x＝y)成立，则称y为B的极小元（4）若x(x∈B∧y≤x→x＝y)成立，则称y为B的极大元363242126B B最大元最大元最小元最小元极大元极大元极小元极小元{2,3,6,12,{2,3,6,12,24,36}24,36}{6,12}{6,12}{2,3,6}{2,3,6}{6}{6}无无 无无 24,26 2,312 12 6 6 12 6 6 6 无无 6 2,3 6 6 6 6 6 6第109页/共128页第一百零九页，共129页。

特殊(tèshū)元素的性质•最小元是B中最小的元素，它与B中其它元素都可比•极小元不一定与B中元素可比，只要没有比它小的元素，它就是极小元•对于有穷集B，极小元一定存在，但最小元不一定存在最小元如果(rúguǒ)存在，一定是唯一的•极小元可能有多个，但不同的极小元之间是不可比的（无关系）•如果(rúguǒ)B中只有一个极小元，则它一定是B的最小元•哈斯图中，集合B的极小元是B中各元素中的最底层第110页/共128页第一百一十页，共129页例7.21例7.21￿设偏序集如右图所示，求A的极小( jí￿xiǎo)元、最小元、极大元、最大元￿解答(jiědá)极小元：a,b,c,g极大元：a,f,h没有最小元与最大元说明(shuōmíng)哈斯图中的孤立顶点既是极小元也是极大元 第111页/共128页第一百一十一页，共129页例7.22例7.22￿设X为集合，A＝P(X)－{}－{X}，且A≠若|X|＝n，问：（1）偏序集是否存在最大元？（2）偏序集是否存在最小元？（3）偏序集中极大元和极小元的一般形式是什么？并说明理由解答￿不存在最小元和最大元，因为n≥2。

考察幂集P(X)的哈斯图，最底层的顶点是空集，记作第0层由底向上，第1层是单元集，第2层是二元子集，…由|X|=n，则第n－1层是X的n－1元子集，第n层，也就是最高层只有一个顶点X偏序集与相比，恰好缺少第0层与第n层(因为X是n元集)因此(yīncǐ)的极小元就是X的所有单元集，即{x}，x∈X；而极大元恰好少一个元素，即X-{x}，x∈X￿第112页/共128页第一百一十二页，共129页上界、下界(xià￿jiè)定义(dìngyì)7.25￿设为偏序集，BA，y∈A1）若￿x(x∈B→x≤y)成立，则称y为B的上界2）若￿x(x∈B→y≤x)成立，则称y为B的下界3）令C＝{y|y为B的上界}，则称C的最小元为B的最小上界或上确界4）令D＝{y|y为B的下界}，则称D的最大元为B的最大下界或下确界￿第113页/共128页第一百一十三页，共129页上界(shàngjiè)与下界举例363242126B B上界上界下界下界上确界上确界下确界下确界{2,3,6,12{2,3,6,12,24,36},24,36}{6,12}{6,12}{2,3,6}{2,3,6}{6}{6} 无无 无无 无无 无无12,24,36 2,3,612,24,36 2,3,6 12 6 12 66,12,24,36 6,12,24,36 无无 6 6 无无6,12,24,366,12,24,36 2,3,6 6 6 2,3,6 6 6q考虑(kǎolǜ)右图中的偏序集。

令B＝{b，c，d}，则B的下界和最大下界都不存在，上界有d和f，最小上界为d第114页/共128页第一百一十四页，共129页上界(shàngjiè)与下界的性质•B的最小元一定是B的下界(xià￿jiè)，同时也是B的最大下界(xià￿jiè)•B的最大元一定是B的上界，同时也是B的最小上界•B的下界(xià￿jiè)不一定是B的最小元，因为它可能不是B中的元素•B的上界也不一定是B的最大元•B的上界、下界(xià￿jiè)、最小上界、最大下界(xià￿jiè)都可能不存在如果存在，最小上界与最大下界(xià￿jiè)是唯一的第115页/共128页第一百一十五页，共129页本章主要(zhǔyào)内容•有序对与卡氏积￿•二元关系（包括空关系，恒等关系，全域关系等）及其表示(biǎoshì)（关系矩阵，关系图）•关系的五种性质（自反性，反自反性，对称性，反对称性，传递性）•二元关系的幂运算￿•关系的三种闭包（自反闭包，对称闭包，传递闭包）￿•等价关系和划分（包括等价类，商集，划分块等）￿•偏序关系（包括哈斯图，最大元，最小元，极大元，极小元，上界，下界，最小上界，最大下界等）￿￿￿第116页/共128页第一百一十六页，共129页。

本章(běn￿zhānɡ)学习要求•掌握：有序对及卡氏积的概念及卡氏积的性质￿•掌握：二元关系，A到B的二元关系，A上的二元关系，关系的定义域和值域，关系的逆，关系的合成，关系在集合上的限制，集合在关系下的象等概念，掌握关系的定义域、值域、逆、合成、限制、象等的主要性质￿￿•掌握：关系矩阵与关系图的概念及求法￿•掌握：集合A上的二元关系的主要性质（自反性，反自反性，对称性，反对称性，传递性）的定义及判别法，对某些关系证明(zhèngmíng)它们有或没有中的性质￿第117页/共128页第一百一十七页，共129页本章(běn￿zhānɡ)学习要求•掌握：A上二元关系的n次幂的定义及主要性质(xìngzhì)￿•掌握A上二元关系的自反闭包、对称闭包、传递闭包的定义及求法￿•掌握：等价关系、等价类、商集、划分、等概念，以及等价关系与划分之间的对应￿•掌握：偏序关系、偏序集、哈斯图、最大元、最小元、极大元、极小元、上界、下界、上确界、下确界等概念￿第118页/共128页第一百一十八页，共129页关系(guān￿xì)性质的证明•通常的证明方法(fāngfǎ)是利用定义证明•R在A上自反•任取x，有x∈A￿￿…………………………………￿∈R•R在A上对称•任取，有∈R￿￿……………………………￿∈R•R在A上反对称•任取，有∈R￿∧￿∈R￿￿……………￿￿x＝y•R在A上传递•任取，，有∈R￿∧￿∈R￿￿……………￿￿∈R第119页/共128页第一百一十九页，共129页。

有关关系(guān￿xì)性质的练习题•在正整数集合上定义关系R：•∈R，如果x和y的最大公因子是1•判断R是否满足关系的五条性质(xìngzhì)？•设A={a,b,c}，试给出A的一个二元关系R，使其同时不满足五个性质(xìngzhì)•N元素集合上有多少个自反的关系？第120页/共128页第一百二十页，共129页例题(lìtí)例题￿在正整数集合上定义(dìngyì)关系R：∈R，如果x和y的最大公因子是1判断R是否满足关系的五条性质？￿分析按增序系统地列出所有的序对，然后观察x＋y最大公因子是否在R中<1,1>21是<1,2>31是<2,1>31是<1,3>41是<2,2>42否<3,1>41是……………第121页/共128页第一百二十一页，共129页例题(lìtí)解答￿自反￿￿否<2,2>R反自反￿￿否<1,1>∈R对称￿￿￿￿是∈R→∈R反对(fǎnduì)称￿￿否<1,2>∈R∧<2,1>∈R￿但￿1≠2传递￿￿￿￿否<2,1>∈R∧<1,2>∈R￿但￿<2,2>R扩展￿￿(1)从列出的若干序偶来考察是否属于关系。

2)按一定规则列出序偶3)一个范例即可证明不满足某种性质4)证明某种性质成立，必须取出关系中的每个元素第122页/共128页第一百二十二页，共129页例题(lìtí)例题￿设A={a,b,c}，试给出A的一个二元关系R，使其同时不满足五个性质￿分析因为关系的各种性质的存在，都要求满足一定的条件，要做的就是创造(chuàngzào)或破坏这些条件从A×A出发，通过删除某些序偶，使其不满足那些性质解答令R＝{,,,,}R不满足自反性∈R不满足反自反性∈R￿∧￿R不满足对称性∈R∧∈R∧b≠c不满足反对称性∈R∧∈R∧R不满足传递性￿第123页/共128页第一百二十三页，共129页习题(xítí)设R＝{|x,y∈N￿且￿x+3y＝12}(1)求R的集合( jíhé)表达式(2)求￿dom￿R，ran￿R(3)求RR(4)求R↑{2,3,4,6}(5)求R[{3}](6)R3解答(jiědá)：{<0,4>,<3,3>,<6,2>,<9,1>,<12,0>}{0,3,6,9,12}，{0,1,2,3,4}{<3,3>,<12,4>}{<3,3>,<6,2>}{3}{<3,3>}第124页/共128页第一百二十四页，共129页。

习题(xítí)•设R是复数集合C上的关系，且满足xRyx-y＝a+bi，a和b为给定的非负整数，试确定R的性质并证明(zhèngmíng)之•解答•（1）当a＝b＝0时，满足自反性、对称性、反对称性和传递性，不满足反自反性•（2）当a、b不全为0时，只满足反自反性、反对称性第125页/共128页第一百二十五页，共129页习题(xítí)例题￿设I为整数集，R＝{|x≡y(mod￿k)}，证明R是等价关系证明￿设任意a,b,c∈I(1)因为a－a＝0，所以(suǒyǐ)∈R2)若a≡b(mod￿k)，a－b＝kt(t为整数)，则b－a＝-kt，所以(suǒyǐ)b≡a(mod￿k)3)若a≡b(mod￿k)，b≡c(mod￿k)，则a－b＝kt，b－c＝ks(t和s为整数)，a－c＝a－b＋b－c＝kt＋ks＝k(t＋s)，所以(suǒyǐ)a≡c(mod￿k)因此，R是等价关系第126页/共128页第一百二十六页，共129页作业(zuòyè)习题(xítí)七：6、13、22、46(1)第127页/共128页第一百二十七页，共129页谢谢大家(dàjiā)观赏！第128页/共128页第一百二十八页，共129页。

内容(nèiróng)总结本章说明4)笛卡儿积运算对并和交运算满足分配律，即关系运算中逆运算优先于其它运算优先权的运算以括号决定运算顺序该定理说明有穷集上只有(zhǐyǒu)有穷多个不同的二元关系如果两个顶点之间有边，一定是一对方向相反的边(无单边)证明左边包含右边，即t(R)包含每个Rn1)考察G的每个顶点，如果没有环就加上一个环k)的边，就加上这条边整数集合Z和数的小于或等于关系≤构成偏序集谢谢大家观赏第一百二十九页，共129页。