离散数学关系的性质

1第一页，共二十七页，编辑于2023年，星期日自反反自反对称反对称传递定义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有边

第二页，共二十七页，编辑于2023年，星期日自反性与反自反性例：自反关系：A上的全域关系EA,恒等关系IA

小于等于关系LA,整除关系DA反自反关系：实数集上的小于关系幂集上的真包含关系

第三页，共二十七页，编辑于2023年，星期日实例例1A={1,2,3},R1,R2,R3是A上的关系,其中

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

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

R3＝{<1,3>}R2自反,R3反自反,R1既不是自反也不是反自反的第四页，共二十七页，编辑于2023年，星期日对称性与反对称性实例：对称关系：A上的全域关系EA,恒等关系IA和空关系反对称关系：恒等关系IA，空关系是A上的反对称关系.

第五页，共二十七页，编辑于2023年，星期日实例例2设A＝{1,2,3},R1,R2,R3和R4都是A上的关系,

其中

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

不对称、也不反对称.第六页，共二十七页，编辑于2023年，星期日传递性实例：

A上的全域关系EA,恒等关系IA和空关系小于等于关系,小于关系，整除关系，包含关系，真包含关系

第七页，共二十七页，编辑于2023年，星期日实例例3设A＝{1,2,3},R1,R2,R3是A上的关系,其中

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

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

R3＝{<1,3>}

R1和R3是A上的传递关系R2不是A上的传递关系第八页，共二十七页，编辑于2023年，星期日关系性质的充要条件设R为A上的关系,则

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

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

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

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

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

第九页，共二十七页，编辑于2023年，星期日实例例.判断下图中关系的性质,并说明理由.(2)反自反，不是自反的；反对称，不是对称的；是传递的.(1)不自反也不反自反；对称,不反对称；不传递.(3)自反，不反自反；反对称，不是对称；不传递.第十页，共二十七页，编辑于2023年，星期日自反性证明证明模式证明R在A上自反任取x,xA

……………..….…….<x,x>R

前提推理过程结论例4证明若IAR，则

R在A上自反.证任取x,

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

因此R在A上是自反的.第十一页，共二十七页，编辑于2023年，星期日对称性证明证明模式证明R在A上对称任取<x,y><x,y>R

……………..….…….<y,x>R

前提推理过程结论例5证明若R=R1,则R在A上对称.证任取<x,y>

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

1

<y,x>R

因此R在A上是对称的.

第十二页，共二十七页，编辑于2023年，星期日反对称性证明证明模式证明R在A上反对称任取<x,y><x,y>R<y,x>R

………..……….

x=y

前提推理过程结论例6证明若R∩R1IA,

则R在A上反对称.证任取<x,y>

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

1

<x,y>R∩R

1

<x,y>IA

x=y

因此R在A上是反对称的.第十三页，共二十七页，编辑于2023年，星期日传递性证明证明模式证明R在A上传递任取<x,y>，<y,z><x,y>R<y,z>R

…..……….<x,z>R

前提推理过程结论例7证明若RRR

,

则R在A上传递.证任取<x,y>，<y,z><x,y>R<y,z>R

<x,z>RR

<x,z>R

因此R在A上是传递的.第十四页，共二十七页，编辑于2023年，星期日运算与性质的关系自反性反自反性对称性反对称性传递性R11

√√√√√R1∩R2

√√√√√R1∪R2

√√√××R1R2

×√√√×R1∘R2

√××××第十五页，共二十七页，编辑于2023年，星期日4.4关系的闭包闭包定义闭包的构造方法集合表示矩阵表示图表示闭包的性质第十六页，共二十七页，编辑于2023年，星期日闭包定义定义设R是非空集合A上的关系,R的自反（对称或传递）闭包是A上的关系R,使得R满足以下条件：

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

（2）RR

（3）对A上任何包含R的自反（对称或传递）关系R

有RR.

一般将R的自反闭包记作r(R),对称闭包记作s(R),

传递闭包记作t(R).

第十七页，共二十七页，编辑于2023年，星期日闭包的构造方法定理1设R为A上的关系,则有

(1)r(R)=R∪R0

(2)s(R)=R∪R1

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

说明：对于有穷集合A(|A|=n)上的关系,(3)中的并是有限的.

若R是自反的，则r(R)=R;若R是对称的，则

s(R)=R;若R是传递的，则t(R)=R.第十八页，共二十七页，编辑于2023年，星期日（3）t(R)＝R∪R2∪R3∪…

先证R∪R2∪…t(R)成立，为此只需证明对任意的正整数n有Rn

t(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)是传递的）这就证明了Rn+1

t(R)。由归纳法命题得证。第十九页，共二十七页，编辑于2023年，星期日再证t(R)R∪R2∪…成立，为此只须证明R∪R2∪…是传递的。任取<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>∈Rt

Rs)

ts(<x,z>∈Rt+s)

<x,z>∈R∪R2∪…从而证明了R∪R2∪…是传递的。第二十页，共二十七页，编辑于2023年，星期日推论

设R为有穷集A上的关系，则存在正整数r使得t(R)=R∪R2∪…∪Rr第二十一页，共二十七页，编辑于2023年，星期日闭包的构造方法（续）设关系R,r(R),s(R),t(R)的关系矩阵分别为M,Mr,Ms和Mt,则

Mr=M+EMs=M+M’

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

(1)考察G的每个顶点,如果没有环就加上一个环，最终得到Gr.(2)考察G的每条边,如果有一条xi到xj的单向边,i≠j,则在G

中加一条xj到xi的反方向边，最终得到Gs.(3)考察G的每个顶点xi,找从xi出发的每一条长度不超过n的路径，如果从xi到路径中任何结点xj没有边，就加上这条边.当检查完所有的顶点后就得到图Gt.第二十三页，共二十七页，编辑于2023年，星期日实例例1设A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>},R和r(R),s(R),t(R)的关系图如下图所示.Rr(R)s(R)t(R)第二十四页，共二十七页，编辑于2023年，星期日R={<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(