第工科离散数学课件 四章 4_5_等价关系 - 知识回顾-闭包、等价.pptx

知识回顾4.4 关系的闭包-知识回顾1. 闭包[自反闭包] 设R是X上的二元关系，扩充R得到关系S 满足：(1) S是自反的； ——闭(2) R?S； ——包(3) 对X上的所有自反且有R?T的关系T，有S?T 。——S是既闭又包的最小关系则S是R的自反闭包，记作r(R) 。[对称闭包] 将自反闭包中的自反性换成对称性，记作s(R)。[传递闭包] 将自反闭包中的自反性换成传递性，记作t(R)。 2. 闭包计算4.4 关系的闭包-闭包计算3. 等价关系设R是X上的二元关系，则 (1) r(R) = R?IX (2) s(R) = R?R-1 (3) t(R) = R+ = ?i=1Ri = ?i=1Ri+?m如果R具有自反性、对称性和传递性。若x, y?R，称x与y等价，x ~ y。如果R具有自反性和对称性称为相容关系。具有自反性、对称性的关系可以简化关系图和关系矩阵的存储。 4. 等价类4.5 等价关系-等价类设R是集合A上的等价关系，对?a ? A，所有与a等价的元素组成的集合叫做由a生成的R等价类： [a]R = {x?a ? A∧a, x?R} = {x?a ? A∧x, a?R} [a] = {x | x~a} ——核心内容如果b? [a]R ，称b为等价类的代表元。(1)[a]R ? ? ——等价类非空(2) a, b?R?[a]R = [b]R?[a]R ∩[b]R ? ? ——等价类不相交1) ? (2)。对?x?[a]R ，有x, a?R，由a, b?R 和传递性，有 x?[b]R ，知 [a]R ? [b]R 。(2) ? (3)。因[a]R = [b]R ，有[a]R ∩[b]R = [a]R ?（因为a?[a]R ） ? 。 (3) ? (1) 。因 [a]R ∩[b]R ? ? ，? t ?[a]R ∩[b]R，有t ?[a]R ∧ t ?[b]R ? a, t? R ∧ t, b? R。 因为R是传递的，故 a, b?R。