离散数学W15L2C4-4.5等价关系与偏序关系

关系性质判别

自反

定义

反自反

对称

反对称

传递

?x?y?z(x,y,z∈A∧∈R∧∈R→∈R)R?R?R对M2中1所在位置,

M中相应位置都是1如果顶点xi 连通到xk , 则从xi到xk 有边

?x(x∈A→?R)?R)

?x?y(x,y∈A∧?x?y(x,y∈A

∈R→∈R∧>∈R)∈R→x=

y)R=R?1

R∩R?1?IA

条件关系矩阵

IA?R主对角线元素全是1每个顶点都有环

R∩IA=?

主对角线元矩阵是对称矩阵若rij＝1, 且素全是0i≠j, 则rji＝0

关系

图

每个顶点都如果两个顶点之如果两点之间没有环间有边, 是一对有边, 是一条

方向相反的边(有向边(无双向无单边)边)

1

例：给定集合X={a,b,c}，R和S是X中的关系，给

R?{?a,b?,?a,c?,?c,b?}定

S?{?a,b?,?b,c?,?c,a?}试求出t(R),t(S)，并画出关系图

解：t(R)?R1R2R3????Rt(S)?Sa1S2S3????Sa1S2S3 {?a,b?,?b,c?,?c,a?,?a,c?,?b,a?,?c,b?,?a,a?,?b,b?,?c,c?}abcbcbcR,t(R)

S

t(S)

A上模3关系的关系图

实例设A={1,2,…,8}, 如下定义A上的关系R：

R = { | x,y∈A∧x≡y(mod 3) }

其中x≡y(mod 3) 叫做x 与y模3相等, 即x 除以3的余数与y 除以3的余数相等.

3

4.5 等价关系与偏序关系

?

等价关系的定义与实例?等价类及其性质?商集与集合的划分

?等价关系与划分的一一对应?偏序关系

?

偏序集与哈斯图

?

偏序集中的特定元素

4

等价关系的定义

定义设R 为非空集合上的关系. 如果R 是自反的、对称的和传递的, 则称R 为A 上的等价关系. 设R 是一个等价关系, 若∈R, 称x 等价于y, 记做x～y.

5