离散数学关系的性质

离散数学关系的性质演示文稿1第1页，共25页。2（优选）离散数学关系的性质第2页，共25页。自反性与反自反性例：自反关系：A上的全域关系EA,恒等关系IA

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

第3页，共25页。实例例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既不是自反也不是反自反的第4页，共25页。对称性与反对称性实例：对称关系：A上的全域关系EA,恒等关系IA和空关系

反对称关系：恒等关系IA，空关系是A上的反对称关系.

第5页，共25页。实例例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

不对称、也不反对称.第6页，共25页。传递性实例：

A上的全域关系EA,恒等关系IA和空关系

小于等于关系,小于关系，整除关系，包含关系，真包含关系

第7页，共25页。实例例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上的传递关系第8页，共25页。关系性质的充要条件设R为A上的关系,则

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

R

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

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

1

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

1

IA

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

R

R

第9页，共25页。实例例.判断下图中关系的性质,并说明理由.(2)反自反，不是自反的；反对称，不是对称的；是传递的.(1)不自反也不反自反；对称,不反对称；不传递.(3)自反，不反自反；反对称，不是对称；不传递.第10页，共25页。自反性证明证明模式证明R在A上自反任取x,x

A

……………..….…….

<x,x>

R

前提推理过程结论例4证明若IA

R，则

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

x

A

<x,x>

IA

<x,x>

R

因此R在A上是自反的.第11页，共25页。对称性证明证明模式证明R在A上对称任取<x,y><x,y>

R

……………..….…….

<y,x>

R

前提推理过程结论例5证明若R=R

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

<x,y>

R

<y,x>

R

1

<y,x>

R

因此R在A上是对称的.

第12页，共25页。反对称性证明证明模式证明R在A上反对称任取<x,y><x,y>

R

<y,x>

R

………..……….

x=y

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

1

IA,

则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上是反对称的.第13页，共25页。传递性证明证明模式证明R在A上传递任取<x,y>，<y,z><x,y>

R

<y,z>

R

…..……….

<x,z>

R

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

R

R

,

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

R

<y,z>

R

<x,z>

R

R

<x,z>

R

因此R在A上是传递的.第14页，共25页。运算与性质的关系自反性反自反性对称性反对称性传递性R1

1

√√√√√R1∩R2

√√√√√R1∪R2

√√√××R1

R2

×√√√×R1∘R2

√××××第15页，共25页。4.4关系的闭包闭包定义闭包的构造方法集合表示矩阵表示图表示闭包的性质第16页，共25页。闭包定义定义设R是非空集合A上的关系,R的自反（对称或传递）闭包是A上的关系R

,使得R

满足以下条件：

（1）R

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

（2）R

R

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

有R

R

.

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

传递闭包记作t(R).

第17页，共25页。闭包的构造方法定理1设R为A上的关系,则有

(1)r(R)=R∪R0

(2)s(R)=R∪R

1

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

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

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

s(R)=R;若R是传递的，则t(R)=R.第18页，共25页。（3）t(R)＝R∪R2∪R3∪…

先证R∪R2∪…

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

t(R)即可。用归纳法。n＝1时，有R1＝R

t(R)。假设Rn

t(R)成立，那么对任意的<x,y>有

<x,y>∈Rn+1＝Rn

R

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)。由归纳法命题得证。第19页，共25页。再证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)

t

s(<y,z>∈Rt∧<x,y>∈Rs)

t

s(<x,z>∈Rt

Rs)

t

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

<x,z>∈R∪R2∪…从而证明了R∪R2∪…是传递的。第20页，共25页。推论

设R为有穷集A上的关系，则存在正整数r使得t(R)=R∪R2∪…∪Rr第21页，共25页。闭包的构造方法（续）设关系R,r(R),s(R),t(R)的关系矩阵分别为M,Mr,Ms和Mt,则

Mr=M+EMs=M+M’

Mt=M+M2+M3+…E是和M同阶的单位矩阵,M’是M的转置矩阵.注意在上述等式中矩阵的元素相加时使用逻辑加.第22页，共25页。闭包的构造方法（续）设关系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