离散数学基础(洪帆)第二讲_关系.ppt

4.关系的性质在关系矩阵和关系图中的特点 性质 表示 自反性 反自反性 对称性 反对称性 可传递性 集合表达 形式 关系矩阵 主对角线元素全为1 主对角线元素全为0 对称 矩阵 对i≠j的情况,若rij=1,则rji=0 对 中1所在的位置, 中相应位置都是1 . 关系图 每个顶点都有环 每个顶点 都没有环 任何两个不同顶点之间 无单向边 任何两个 不同顶点 之间 无双向边 如果顶点xi到xj, xj到xk有边, 则xi到xk有边。 二、二元关系的闭包 设 是集合A上的关系, 我们希望 具有某些有用的性质, 比如说自反性。如果不具有自反性, 我们通过在其中添加一部分序偶来改造, 得到新的关系 , 使得其具有自反性。但又不希望它与 相差太多, 换句话说, 添加的序偶要尽可能的少。满足这些要求的就称为 的自反闭包。除自反闭包外还有对称闭包和传递闭包等。 1.定义 设 是集合A上的关系, 的自反闭包 (对称闭包或传递闭包)是A上关系 它满足下列条件: (1) 是自反的(对称的或可传递的); (2) ; (3) 对A上任何包含 的自反(对称或 可传递)关系 , 有 。 注: 将自反闭包记为 , 对称闭包记为 将传递闭包记为 。 定理 设 是集合A上的关系：则 (1) ; (2) ; (3) 。 推论: 设 是有限集合A上的关系, 若#(A)=n, 则 。 2. 求闭包的方法 注：由 的关系图构造 的关系图的方法： 对于 的图中的每个结点 ai ,找出从 ai 经有限长的路能够到达（有路）的结点， 这些结点在 的图中，边必须由 ai 指向它们。 3.定理 设 是集合A上的关系, 则： (1) 是自反的当且仅当 ; (2) 是对称的当且仅当 ; (3) 是传递的当且仅当 ; 4.定理 设 是集合A上的关系: (1)若 是自反的, 则 也是自反的。 (2)若 是对称的, 则 也是对称的。 (3)若 是传递的, 则 也是传递的。 5.定理 设 是A上的关系, 且 , 则有 , , 。 由等价关系的对称性也称b等价于a。 一、 等价关系的定义 2.6 等价关系 定义 设 是集合A上的一个关系, 若它是自反的, 对称的且可传递的, 则称 为A上的一个等价关系。 设 是集合A上的一个等价关系, 若a b成立, 注： 则说a等价于b, 例1 在中国人组成的集合上定义的“同姓”关系, 它具备自反、对称、传递的性质, 因此是一个等价关系。 例2 平面上直线集合上的“平行”关系是等价关系, 而其上的“垂直”关系不是等价关系, 因为它既不是自反的，也不是传递的。 例3 平面上三角形的“全等、相似”关系是等价关系。 例4 “朋友”关系不是等价关系，因为它不是传递的。 例5 集合的“包含”关系不是等价关系， 因为它不是对称的。 例6 设A={1,2,…,8}, 如下定义A上的关系 R: R ={(a,b)|a,b∈A, a≡b(mod3)}. 其中a≡b(mod3)叫做a与b模3相等, 即a与b除以3的余数相等(即3整除|a-b|). 判定R是否为A上的一个等价关系？ 解: