离散数学及应用 课件 4.3 关系的性质

DiscreteMathematics鄢小虎

离散数学课程回顾关系的表达：有序对集合、关系矩阵、关系图基本运算定义域、值域、域逆、合成、限制、像高级运算幂运算

对应矩阵中，矩阵具有哪些性质？对称性？34.3关系的性质自反性反自反性对称性反对称性传递性4自反性与反自反性定义设R为A上的关系,

(1)若

x(x∈A→<x,x>

R),则称R在A上是自反的.

(2)若

x(x∈A→<x,x>

R),则称R在A上是反自反的.

实例：同姓关系、父子关系？5自反性特点关系图中，每个结点都有环6自反性特点关系矩阵中，主对角线都为17课堂提问下列关系是否为自反关系？恒等关系IA

？小于等于关系LA？(小于关系？)整除关系DA？8反自反性特点关系图中，每个结点都无环9反自反性特点关系矩阵中，主对角线都为010课堂提问下列关系是否为反自反关系？实数集上的小于关系？11实例例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>}R1既不是自反也不是反自反的R2自反,R3反自反总结：可以既不是自反也不是反自反的但不能同时为自反和反自反12自反和反自反

自反反自反表达式IA

RR∩IA=

关系矩阵主对角线元素全是1主对角线元素全是0关系图每个顶点都有环每个顶点都没有环13编程练习判断关系R是否为自反关系和反自反关系。提示：自反：IA

R；反自反：R∩IA=

实例：A={1,2,3}，R＝{<1,1>,<2,2>,<3,3>,<1,2>}输入：集合A和关系R；输出：是和否通过对集合A进行循环，从而构造IA14编程练习已知关系R由关系矩阵M给出，要求判断由M表示的这个关系是否为自反关系和反自反关系。

提示：主对角线元素全是1（0）实例：15对称性与反对称性定义

设R为A上的关系,

(1)若

x

y(x,y∈A∧<x,y>∈R→<y,x>∈R),则称R为A上对称的关系.

(2)若

x

y(x,y∈A∧<x,y>∈R∧<y,x>∈R→x=y),则称R为A上的反对称关系.判断：同姓关系、朋友关系？16对称性特点若有边，则成对出现；没有边也是可以的17对称性特点18反对称性特点若有边，则只有一条边；没有边也是可以的19反对称性特点20课堂提问下列关系是否为对称和反对称关系？恒等关系IA？空关系？父子关系？

21实例例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

不对称、也不反对称.总结：可以同时为(不为)对称和反对称22总结：对称和反对称

对称反对称表达式R=R

1

R∩R

1

IA

关系矩阵矩阵是对称矩阵若rij＝1,且i≠j,则rji＝0关系图如果两个顶点之间有边,是一对方向相反的边(无单边)如果两点之间有边,是一条有向边(无双向边)23编程练习判断关系R是否为对称关系和反对称关系。提示：对称：R=R

1

；反对称：R∩R

1

IA

实例：A={1,2,3}，R＝{<1,1>,<1,2>,<2,1>}24扩展：编程练习已知关系R由关系矩阵M给出，要求判断由M表示的这个关系是否为对称关系和反对称关系。

提示：对称：矩阵是对称矩阵；

反对称：若rij＝1,且i≠j,则rji＝0实例：25传递性定义

设R为A上的关系,若

x

y

z(x,y,z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R),

则称R是A上的传递关系.

实例：恒等关系IA和空关系

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

同姓关系、父子关系、朋友关系？26传递关系

传递表达式R∘R

R关系矩阵对M2中1所在位置,M中相应位置都是1关系图如果顶点xi到xj有边，

xj

到xk有边，则从xi到xk

有边

如何存在两步可以到的边，一定存在一步可以到的边；没有两步可以到的边也ok27实例例3设A＝{1,2,3},R1,R2,R3是A上的关系,其中

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

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

R3＝{<1,3>}

R1是A上的传递关系R2不是A上的传递关系R3是A上的传递关系28编程练习判断关系R是否为传递关系。提示：R∘R

R实例：A={1,2,3}，R＝{<1,1>,<2,2>,<3,3>,<1,2>}29扩展：编程练习已知关系R由关系矩阵M给出，要求判断由M表示的这个关系是否为传递关系。提示：对M2(逻辑加)中1所在位置,M中相应位置都是1实例：30关系性质的充要条件设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

31自反性证明证明模式证明R在A上自反任取x,x

A

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

<x,x>

R

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

R，则

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

x

A

<x,x>

IA

<x,x>

R

因此R在A上是自反的.32对称性证明证明模式证明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

<x,y>

R

因此R在A上是对称的.

33反对称性证明证明模式证明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上是反对称的.34传递性证明证明模式证明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上是传递的.35运算与性质的关系(了解)自反性反自反性对称性反对称性传递性R1

1

√√√√√R1∩R2

√√√√√R1∪R2

√√√××R1

R2

×√√√×R1∘R2

√××××36课前复习

传递表达式R∘R

R关系矩阵对M2中1所在位置,M中相应位置都是1关系图如果顶点xi到xj有边，

xj

到xk有边，则从xi到xk

有边

对称反对称表达式R=R

1

R∩R

1

IA

关系矩阵矩阵是对称矩阵若rij＝1,且i≠j,则rji＝0关系图如果两个顶点之间有边,是一对方向相反的边(无单边)如果两点之间有边,是一条有向边(无双向边)空集包含于任何集合37实例例8判断下图中关系的性质,并说明理由.(b)反自反，不是自反的；反对称，不是对称的；是传递的.(a)不自反也不反自反；对称,不反对称；不传递.(c)自反