第3单元 二元关系-2闭包`次序`等价.pptVIP

第 3 章 二 元 关 系 3.3 关系上的闭包运算 3.3.1 逆关系 定理3.3―2 设 R、R1 和 R2 都是从 A 到B 的二元关系，那么下列各式成立： 3.3.2 关系的闭包运算 定义3.3―2 设R是A上的二元关系, R的自反(对称,传递)闭包是关系R′,使 (i) R′是自反的(对称的,传递的) (ii) R′R (iii)对任何自反的(对称的,传递的)关系R″,如果 R″R,那么R″R′ R的自反,对称和传递闭包分别记为r(R),s(R)和t(R). R的自反(对称,传递)闭包是包含R并且具有自反(对称,传递)性质的最小关系. 构造 R 的自反，对称和传递闭包的方法 定理3.3―5 设 R 是集合 A 上的二元关系，那么， 定理3.3―6 设 R 是集合 A 上的二元关系，那么， 定理3.3―7 设 R 是集合 A 上的二元关系，那么 例2 例3 设 A ={ a，b，c，d }， 3.4 次序关系 定义3.4―1 如果集合 A 上的二元关系 R 是自反的， 反对称的和传递的，那么称 R 为 A 上的偏序。 D={ } M={ } 例2 (1) P={1，2，3，4}，〈P， ? 〉的哈斯图 (2) A={2，3，6，12，24，36}，〈A，整除〉的哈斯图。 由图所示的哈斯图， 写出对应的偏序关系、 关系矩阵。 定义3.4―2 设〈A， ? 〉是一偏序集合，B是A的子集 (1)元素b∈B是 B 的最大元素，如果对每一元素 x∈B，x≤b 定理3.4―1 设〈A, ? 〉是一偏序集合，且 B ? A，如果B有最大(最小)元素，那么它是唯一的。 如果 a 是一下界并且对每一 B 的下界 a′有a′? a，那么元素 a∈A 叫做 B 的最大下界。 例4 (3)考虑偏序集合〈{2,5,6,10,15,30}, 整除〉, 其哈斯图如图。 设B={2,5,6,10,15,30}, 那么 极小元素：2、5 ；没有最小元素、下界、最大下界； 30是 最大元素、极大元素、上界、最小上界。 结论： 设〈A， ? 〉为偏序集，B ? A 3.4.2 拟序集合 定义3.4―5 如果集合A上的二元关系R是传递的和反自反的, 那么R叫做A上的拟序.〈A,R〉称为拟序集合. 常借用符号＜表示拟序。 拟序是反对称的。 证明： 如果xRy和yRx, 由R的传递性得xRx, 但这与R的反自反性矛盾, 所以xRy∧yRx常假,于是 xRy∧yRx→x=y 常真, 【无义证明法】 即R是反对称的. 例5 (1) 实数集合中的＜是拟序关系 (2) 集合族中的真包含是拟序关系 拟序集合和偏序集合是紧密相关的,唯一区别是相等关系E. 定理3.4―5 在集合A上, (1) 如果R是一拟序, 那么r(R)=R∪E是偏序. (2) 如果R是一偏序, 那么R-E是一拟序. 证明：习题12。 3.4.3 线序集合 如果≤是一偏序, 若a≤b或b≤a,我们说a和b是可比较的. 偏序集合中的元素不一定都可比较, 所以叫“偏”序. 定义3.4―6 在偏序集合〈A,≤〉中. 如果每一a,b∈A, 或者a≤b,或者b≤a. 那么≤叫做A上的线序(或全序), 〈A,≤〉叫做线序集合或链. 例6 (1)P={ ,{a},{a,b},{a,b,c}},〈P,〉是线序集合,其哈斯图如图3.4―8所示 (2)〈I,≤〉是线序集合,其哈斯图(不完全)如图3.4―9所示 (4)〈{1,2,3,6},整除〉不是线序集合; 如果A是多于一个元素的集合, 那么〈ρ(A),〉不是线序集合. 3.5