离散数学(14)-课件·PPT.ppt

第三章二元关系 等价关系和划分
等价关系
二元关系的另一重要类型是等价关系,其定义如下:
―1如果集合A上的二元关系R是自反的, 对称的和传递的,那么称R是等价关系。
1
设R是A上的等价关系,a,b,c是A的任意元素。
如果aRb(即<a,b>∈R),通常我们记作a~b,
读做“a等价于b”,如日常中的“相等”“相同”。
(1)因为具有R自反性,所以A上每一元素和自己等价。反映到R的有向图上,每一结点都有一自回路。
2
(2)因为R具有对称性,所以如果a等价于b,则b也等价于a, 反映到R的有向图上,如果有从a到b的弧,那么也有从b到a的弧。
(2)因为具有R传递性,所以如果a等价于b,b等价于c则a也等价于c, 反映到有向图上,如果有从a到c有一条路径(长度为2),则从a到c有一条弧(长度为1) 。
3
例1 (a) 同学集合A={a,b,c,d,e,f,g},A中的关系R是“住在同一房间”。这是等价关系,因为(i)任一个人和自己同住一间,具有自反性。(ii)若甲和乙同住一间,则乙和甲也同住一间,具有对称性。(iii)若甲和乙同住一间,乙和丙同住一间,则甲和丙也同住一间,具有传递性,现假设a和b同住一间, d, e, f同住一间,c住一间,则:
4
R={<a,a>,<a,b>,<b,a>,<b,b>,<c,c>,<d,d>,<e,e>, <f,f>, <d,e>,<e,d>,<e,f>,<f,e>,<d,f>,<f,d>}
其有向图如下图所示
5
(b)数中的相等关系,集合中的相等关系(IA), 命题演算中的关系,相同关系等都是等价关系。
(c)空集合中的二元关系R是等价关系,因为
(i)  x(x∈→xRx)
(ii)  x  y[x∈∧y∈∧xRy→yRx]
(iii)  x  y  z[x∈∧y∈∧z∈
∧xRy∧yRz→xRz]
都无意义地真,所以是R是等价关系。
6
集合A上的全域关系R=A × A是等价关系。
模数等价是整数域或其子集上的等价关系,并且是等价关系中极为重要的一类。
―2设k是一正整数而a,b∈ m, a-b=m·k,那么a和b是模k等价,写成
a≡b(modk)
整数k叫做等价的模数
7
―1 模k等价是任何集合A I上的等价关系
证:如果A=,例1(c)≠,则
(i), a-a= 0·k,得出 a≡a(modk)
(ii)≡b(modk)时,存在某m∈I,
8
使a - b=m·k,于是b - a= (-m)·k,因此
b≡a(modk)
(iii)≡b(modk)和b≡c(modk),
那么存在m1,m2∈I,使a - b=m1k和
b - c=m2·k,将两等式两边相加,得
a - c=(m1+m2)·k,所以 a≡c(modk)
9
将模k等价 a≡b(modk) 改写成a-b=m·k
例如: 6-3 = 1 · 3; 9-3 = 2 · 3;…..模3等价
及{<6,3>,<9,3>, <9,9>, <6,6>, <3,3>, <3,6>, <3,9> …}·3
我们更多时候用表达式, 它说明模k等价可以将一个整数与k相除表示成一个整数m与余数和的形式. 再利用余数相同来分类.
10