离散数学关系的性质省公开课一等奖全国示范课微课金奖PPT课件.pptx

该【离散数学关系的性质省公开课一等奖全国示范课微课金奖PPT课件 】是由【liaoyumen】上传分享，文档一共【22】页，该文档可以免费在线阅读，需要了解更多关于【离散数学关系的性质省公开课一等奖全国示范课微课金奖PPT课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。 关系性质

自反性与反自反性
对称性与反对称性
传递性
关系闭包
闭包定义
闭包计算
Warshall算法
1
第1页
自反性与反自反性
设R为A上关系,  (1) 若x(x∈A→<x,x>R), 则称R在A上是自反. (2) 若x(x∈A→<x,x>R), 则称R在A上是反自反.
自反：A上全域关系EA, 恒等关系IA, 小于等于关系LA,
整除关系DA
反自反：实数集上小于关系、幂集上真包含关系.
R2自反, R3 反自反, R1既不自反也不反自反.
例1 A = {a, b, c}, R1, R2, R3 是 A上关系, 其中 R1 = {<a,a>,<b,b>} R2 = {<a,a>,<b,b>,<c,c>,<a,b>} R3 = {<a,c>}
2
第2页
对称性与反对称性
例2 设A＝{a,b,c}, R1, R2, R3和R4都是A上关系, 其中  R1＝{<a,a>,<b,b>}， R2＝{<a,a>,<a,b>,<b,a>} R3＝{<a,b>,<a,c>}， R4＝{<a,b>,<b,a>,<a,c>}
设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上反对称关系.实例 对称：A上全域关系EA, 恒等关系IA和空关系
反对称：恒等关系IA，空关系是A上反对称关系
R1 对称、反对称. R2 对称，不反对称.
R3 反对称，不对称. R4 不对称、也不反对称
3
第3页
传递性
例3 设A＝{a, b, c}, R1, R2, R3是A上关系, 其中 R1＝{<a,a>,<b,b>} R2＝{<a,b>,<b,c>} R3＝{<a,c>}
设R为A上关系, 若 xyz(x,y,z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R),则称R是A上传递关系.实例：A上全域关系 EA, 恒等关系 IA 和空关系 , 小
于等于关系, 小于关系, 整除关系, 包含关系, 真包含关系
R1 和 R3 是A上传递关系, R2不是A上传递关系.
4
第4页
关系性质充要条件
设 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
5
第5页
自反性证实
证实模式 证实 R 在 A 上自反
任取 x,
xA  ……… ………..…. …….  <x, x>R
前提 推理过程 结论
例4 证实若 IA R ，则 R 在 A 上自反.
证 任取x, xA  <x, x> IA  <x, x>R 所以 R 在 A 上是自反.
6
第6页
对称性证实
证实模式 证实 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 上是对称.
7
第7页
反对称性证实
证实模式 证实 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 上是反对称.
8
第8页
传递性证实
证实模式 证实 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 上是传递.
9
第9页
关系性质判别

自反性
反自反性
对称性
反对称性
传递性
表示式
IAR
R∩IA=
R=R1
R∩R1 IA
RRR
关系
矩阵
主对角
线元素
全是1
主对角线
元素全是
0
矩阵是对称
矩阵
若rij＝1, 且
i≠j, 则rji＝0
对M2中1所
在位置,M
中对应位置
都是1
关系图
每个顶
点都有
环
每个顶点
都没有环
假如两个顶
点之间有边,
一定是一对
方向相反
边(无单边)
假如两点之
间有边, 一定
是一条有向
边(无双向边)
假如顶点xi
到xj有边, xj
到xk有边,则
从xi到xk也
有边
10
第10页