南京大学：《离散数学 Discrete Mathmatics》课程教学资源（课件讲稿，2018）关系——第13章 关系的闭包、等价关系

关系的闭包、等价关系 离散数学一集合论 南京大学计算机科学与技术系

关系的闭包、等价关系 离散数学－集合论 南京大学计算机科学与技术系

殿原 回顾 ●关系：笛卡尔积的子集 ·函数的定义 关系的运算 ● 子集的像 。 集合运算；复合运算；逆 。单射与满射 ·0-1矩阵运算 ·反函数 关系的性质 ·自反，反自反，对称，反对 ●函数的复合 称，传递 ·函数加法与乘法 。图特征；矩阵特征

回顾  关系：笛卡尔积的子集  关系的运算  集合运算；复合运算；逆  0-1矩阵运算  关系的性质  自反，反自反，对称，反对 称，传递  图特征；矩阵特征  函数的定义  子集的像  单射与满射  反函数  函数的复合  函数加法与乘法

款售角 提要 ●闭包的定义 ·闭包的计算公式 ●传递闭包的Warshall算法 ·等价关系 ●等价类 ·划分

提要  闭包的定义  闭包的计算公式  传递闭包的Warshall算法  等价关系  等价类  划分

殿原 “闭包” 青色框满足： 一个对象 橘黄色圈满足： 1.是正方形的（性质） 1.是圆的（性质） 2.包含所给对象 2.包含所给对象 3.如果有个红色正方形 3.如果有个绿色圆也能 也能包含该对象，就 包含该对象，就一定 一定也能包含这个青 也能包含这个橘黄圈 色框

“闭包” 一个对象 橘黄色圈满足： １．是圆的（性质） ２．包含所给对象 ３．如果有个绿色圆也能 包含该对象，就一定 也能包含这个橘黄圈 青色框满足： １．是正方形的（性质） ２．包含所给对象 ３．如果有个红色正方形 也能包含该对象，就 一定也能包含这个青 色框

关系的闭包：一般概念 ●设R是集合A上的关系，P是给定的某种性质（如： 自反、对称、传递)，满足下列所有条件的关系R, 称为R的关于P的闭包： RCR ●R满足性质P ●如果存在集合A上的关系R',R'满足性质P并包含R,则 RCR' ·自反闭包(R)、对称闭包s(R)、传递闭包R)

关系的闭包：一般概念  设R是集合A上的关系，P是给定的某种性质（如： 自反、对称、传递），满足下列所有条件的关系R1 称为R的关于P的闭包:  RR1  R1 满足性质P  如果存在集合A上的关系R’，R’ 满足性质P 并包含R，则 R1R’  自反闭包r(R)、对称闭包s(R)、传递闭包t(R)