离散数学-关系的性质讲课讲稿

4.3关系(guānxì)的性质自反性反自反性对称性反对称性传递性第一页，共27页。1自反反自反对称反对称传递定义x∈A,有<x,x>R),x∈A,有<x,x>R,若

<x,y>∈R有<y,x>∈R),若<x,y>∈R且x

y,则<y,x>R若<x,y>∈R<y,z>∈R，则<x,z>∈R),表达式IARR∩IA=R=R1

R∩R1

IA

RRR关系矩阵主对角线元素全是1主对角线元素全是0矩阵是对称矩阵若rij＝1,且i≠j,则rji＝0对M2中1所在位置,M中相应位置都是1关系图每个顶点都有环每个顶点都没有环如果两个顶点之间有边,是一对方向相反的边(无单边)如果两点之间有边,是一条有向边(无双向边)如果顶点xi连通到xk,则从xi到xk有边

第二页，共27页。2自反性与反自反性例：自反关系(guānxì)：A上的全域关系(guānxì)EA,恒等关系(guānxì)IA小于等于关系(guānxì)LA,整除关系(guānxì)DA反自反关系(guānxì)：实数集上的小于关系(guānxì)幂集上的真包含关系(guānxì)

第三页，共27页。3实例(shílì)例1A={1,2,3},R1,R2,R3是A上的关系(guānxì),其中

R1＝{<1,1>,<2,2>}

R2＝{<1,1>,<2,2>,<3,3>,<1,2>}

R3＝{<1,3>}R2自反(zìfǎn),R3反自反(zìfǎn),R1既不是自反(zìfǎn)也不是反自反(zìfǎn)的第四页，共27页。4对称性与反对称性实例：对称关系(guānxì)：A上的全域关系(guānxì)EA,恒等关系(guānxì)IA和空关系(guānxì)反对称关系(guānxì)：恒等关系(guānxì)IA，空关系(guānxì)是A上的反对称关系(guānxì).

第五页，共27页。5实例(shílì)例2设A＝{1,2,3},R1,R2,R3和R4都是A上的关系(guānxì),其中

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对称(duìchèn)、反对称(duìchèn).R2对称(duìchèn)，不反对称(duìchèn).R3反对称(duìchèn)，不对称(duìchèn).R4不对称(duìchèn)、也不反对称(duìchèn).第六页，共27页。6传递性实例：A上的全域关系(guānxì)EA,恒等关系(guānxì)IA和空关系(guānxì)小于等于关系(guānxì),小于关系(guānxì)，整除关系(guānxì)，包含关系(guānxì)，真包含关系(guānxì)

第七页，共27页。7实例(shílì)例3设A＝{1,2,3},R1,R2,R3是A上的关系(guānxì),其中

R1＝{<1,1>,<2,2>}

R2＝{<1,2>,<2,3>}

R3＝{<1,3>}

R1和R3是A上的传递(chuándì)关系R2不是A上的传递(chuándì)关系第八页，共27页。8关系(guānxì)性质的充要条件设R为A上的关系(guānxì),则

(1)R在A上自反当且仅当IAR

(2)R在A上反自反当且仅当R∩IA=

(3)R在A上对称当且仅当R=R1

(4)R在A上反对称当且仅当R∩R1IA

(5)R在A上传递当且仅当RRR

第九页，共27页。9实例(shílì)例.判断(pànduàn)下图中关系的性质,并说明理由.(2)反自反，不是自反的；反对(fǎnduì)称，不是对称的；是传递的.(1)不自反也不反自反；对称,不反对称；不传递.(3)自反，不反自反；反对称，不是对称；不传递.第十页，共27页。10自反性证明(zhèngmíng)证明模式证明R在A上自反任取x,xA……………..….…….<x,x>R前提推理过程(guòchéng)结论例4证明(zhèngmíng)若IAR，则R在A上自反.证任取x,

xA<x,x>IA<x,x>R

因此R在A上是自反的.第十一页，共27页。11对称性证明(zhèngmíng)证明模式证明R在A上对称任取<x,y><x,y>R……………..….…….<y,x>R前提推理(tuīlǐ)过程结论例5证明(zhèngmíng)若R=R1,则R在A上对称.证任取<x,y>

<x,y>R<y,x>R1<y,x>R

因此R在A上是对称的.

第十二页，共27页。12反对称性证明(zhèngmíng)证明模式证明R在A上反对称任取<x,y><x,y>R<y,x>R………..……….x=y前提推理(tuīlǐ)过程结论例6证明若R∩R1IA,则R在A上反对(fǎnduì)称.证任取<x,y>

<x,y>R<y,x>R<x,y>R<x,y>R1<x,y>R∩R1<x,y>IAx=y

因此R在A上是反对(fǎnduì)称的.第十三页，共27页。13传递性证明(zhèngmíng)证明模式证明R在A上传递任取<x,y>，<y,z><x,y>R<y,z>R…..……….<x,z>R前提推理(tuīlǐ)过程结论例7证明若RRR,则R在A上传递(chuándì).证任取<x,y>，<y,z><x,y>R<y,z>R<x,z>RR<x,z>R

因此R在A上是传递(chuándì)的.第十四页，共27页。14运算(yùnsuàn)与性质的关系自反性反自反性对称性反对称性传递性R11

√√√√√R1∩R2

√√√√√R1∪R2

√√√××R1R2

×√√√×R1∘R2

√××××第十五页，共27页。154.4关系(guānxì)的闭包闭包定义闭包的构造方法集合表示(biǎoshì)矩阵表示(biǎoshì)图表示(biǎoshì)闭包的性质第十六页，共27页。16闭包定义(dìngyì)定义设R是非空集合A上的关系,R的自反（对称或传递）闭包是A上的关系R,使得R满足(mǎnzú)以下条件：

（1）R是自反的（对称的或传递的）

（2）RR

（3）对A上任何包含R的自反（对称或传递）关系R有RR.一般将R的自反闭包记作r(R),对称闭包记作s(R),传递闭包记作t(R).第十七页，共27页。17闭包的构造方法定理1设R为A上的关系,则有

(1)r(R)=R∪R0

(2)s(R)=R∪R1

(3)t(R)=R∪R2∪R3∪…

说明：对于有穷集合(jíhé)A(|A|=n)上的关系,(3)中的并是有限的.若R是自反的，则r(R)=R;若R是对称的，则s(R)=R;若R是传递的，则t(R)=R.第十八页，共27页。18（3）t(R)＝R∪R2∪R3∪…

先证R∪R2∪…t(R)成立，为此只需证明(zhèngmíng)对任意的正整数n有Rnt(R)即可。用归纳法。n＝1时，有R1＝Rt(R)。假设Rnt(R)成立，那么对任意的<x,y>有 <x,y>∈Rn+1＝RnR t(<x,t>∈Rn∧<t,y>∈R) t(<x,t>∈t(R)∧<t,y>∈t(R)) <x,y>∈t(R)（因为t(R)是传递的）这就证明(zhèngmíng)了Rn+1t(R)。由归纳法命题得证。第十九页，共27页。19再证t(R)R∪R2∪…成立，为此只须证明R∪R2∪…是传递(chuándì)的。任取<x,y>,<y,z>，则 <y,z>∈R∪R2∪…∧<x,y>∈R∪R2∪… t(<y,z>∈Rt)∧s(<x,y>∈Rs) ts(<y,z>∈Rt∧<x,y>∈Rs) ts(<x,z>∈RtRs) ts(<x,z>∈Rt+s) <x,z>∈R∪R2∪…从而证明了R∪R2∪…是传递(chuándì)的。第二十页，共27页。20推论(tuīlùn)设R为有穷集A上的关系，则存在正整数r使得t(R)=R∪R2∪…∪Rr第二十一页，共27页。21闭包的构造方法（续）设关系R,r(R),s(R),t(R)的关系矩阵分别为M,Mr,Ms和Mt,则

Mr=M+EMs=M+M’Mt=M+M2+M3+…E是和M同阶的单位矩阵,M’是M的转置矩阵.注意在上述等式中矩阵的元素相加时使用(shǐyòng)逻辑加.第二十二页，共27页。22闭包的构造方法（续）设关系R,r(R),r(R),s(R),t(R)的关系图分别记为G,Gr,Gs,Gt,则Gr,Gs,Gt的顶点集与G的顶点集相等.除了G的边以外,以下述方法添加新边：

(1)考察G的每个顶点,如果没有环就加上一个环，最终(zuìzhōnɡ)得到Gr.(2)考察G的每条边,如果有一条xi到xj的单向边,i≠j,则在G中加一条xj到xi的反方向边，最终(zuìzhōnɡ)得到Gs.(3)考察G的每个顶点xi,找从xi出发的每一条长度不超过n的路径，如果从xi到路径中任何结点xj没有边，就加上这条边.当检查完所有的顶点后就得到图Gt.第二十三页，共27页。23实例(shílì)例1设A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>},R和r(R),s(R),t(R)的关系(guānxì)图如下图所示.Rr(R)s(R)t(R)第二十四页，共27页。24R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>},r(R)=R∪R0={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>}∪{<a,a>,<b,b>,<c,c>,<d,d>}

={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>,<a,a>,<b,b>,<c,c>,<d,d>}s(R)=R∪R1