4二元关系和函数探究.ppt

* liu qun, northeastern Univ. * 2.3.11相容关系 例2中的元素用 表示，则有图1 （图1） （图2） 相容关系的图形特征为自身都有回路，两点关系对称， 所以相容关系的图形可简化成图2， 例2中的关系矩阵为 相容关系的矩阵特征是对角线为1的对称矩阵， 所以可简化成下三角矩阵（注意少一阶） * liu qun, northeastern Univ. * 2.3.11相容关系 相容类 例 上例中有相容类有{x1,x2},{x1,x4}{x2,x4}{x1,x2,x4}等 前三个都可加上一个元素扩充为另一个相容类， 而最后一个却不行，即最后一个为最大相容类 相容类的图形是关系r图形的子图 * liu qun, northeastern Univ. * 2.3.11相容关系 最大相容类 设r是集合A上的相容关系，不能真包含在任何其他相容类中的相容类，称作最大相容类，记作 从关系图中看，最大相容类的图形是关系r图形中的完备图部分 （即每个顶点之间都有关系，包括孤立点） a d b c e 例 如关系图如右 则最大相容类为{a,b,c}{c,d}{e} 例如前例中的{x1,x2,x4}， {x2,x3,x5}，{x2,x4,x5} * liu qun, northeastern Univ. * 2.3.11相容关系 a b c d 例 同室四人每个人都有一些爱好如下： A爱好游泳(a),跳舞(b),下棋(C) B爱好跳舞(b),游泳(a) C爱好跳舞(b) 打球(d) D爱好下棋(c) 游泳(a) 有相同爱好者必能谈得来， 试给出那些人在一起时谈得来的关系 解： 上的相容关系如上图， 找出极大相容性分块 表示 A,B,C爱好跳舞，谈得来； A,B,D爱好游泳，谈得来 * liu qun, northeastern Univ. * 2.3.11相容关系 完全覆盖 在集合A上给定相容关系r，其最大相容类的集合， 称作集合A的完全覆盖，记作 一个集合的覆盖不是唯一的，但完全覆盖却是唯一的 * liu qun, northeastern Univ. * 2.3.11相容关系 定理 设r是有限集A上的相容关系，C是一个相容类， 那么必存在一个最大相容类 使得 即由一个相容类，一定可以扩展成一个最大相容类 设C是一个相容类， （1）做C∪aj,其中aj∈C，且为与C中每个元素都相容的 最小足标的元素，得相容类C1 （2）再对C1做上一步骤，如此进行下去，直至没有元 素aj存在为止， 最后得到的即为包含C的最大相容类 扩展的方式是： * liu qun, northeastern Univ. * 2.3.11相容关系 人有了知识，就会具备各种分析能力， 明辨是非的能力。 所以我们要勤恳读书，广泛阅读， 古人说“书中自有黄金屋。 ”通过阅读科技书籍，我们能丰富知识， 培养逻辑思维能力； 通过阅读文学作品，我们能提高文学鉴赏水平， 培养文学情趣； 通过阅读报刊，我们能增长见识，扩大自己的知识面。 有许多书籍还能培养我们的道德情操， 给我们巨大的精神力量， 鼓舞我们前进。 * * liu qun, northeastern Univ. * 全序集 设 为一个偏序集，若A是一个链，则称 是全序集或线序集。在这种情况下，二元关系 称为全序关系或线序关系。 例如上例中B1={3，6，12，24}构成的集合 集合A本身由链构成，形如线型， 例 自然数N构成的集合 4.5等价关系和偏序关系——偏序关系 * liu qun, northeastern Univ. * 极大元 设 是一个偏序集合，且B是A的子集， 对于B中一个元素b，如果B中没有任何元素x， 满足b≠x，且b x，则称b为B的极大元。 极小元 设 是一个偏序集合，且B是A的子集， 对于B中一个元素b，如果B中没有任何元素x， 满足b≠x，且x b，则称b为B的极小元。 例P99/4.16 极大元和极小元不是唯一的 极大元之间没有关系，极小元既是 极大元在哈斯图的顶部，极小元相反 4.5等价关系和偏序关系——偏序关系 * liu qun, northeastern Univ. * 最大元 设 是一个偏序集合，且B是A的子集， 对于B中某个元素b，如果对B中每个元素x， 都有x b，则称b为 的最大元。 最小元 设 是一个