离散数学第7章课件-高等教育出版社-屈婉玲-耿素云-张立昂主编.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 实例 例15 设X为集合, A＝P(X)－{?}－{X}, 且A≠?. 若|X|=n, n≥2. 问： (1) 偏序集 A, R? 是否存在最大元？ (2) 偏序集 A, R? 是否存在最小元？ (3) 偏序集 A, R? 中极大元和极小元的一般形式是什么？ 并说明理由. 解 (1) A, R? 不存在最小元和最大元, 因为n≥2. (2) A, R? 的极小元就是 X 的所有单元集, 即{x}, x∈X. (3) A, R? 的极大元恰好比 X 少一个元素, 即X?{x}, x∈X. * 第七章 习题课 主要内容 有序对与笛卡儿积的定义与性质 二元关系、从A到B的关系、A上的关系 关系的表示法：关系表达式、关系矩阵、关系图 关系的运算：定义域、值域、域、逆、合成、限制、像、幂 关系运算的性质: A上关系的自反、反自反、对称、反对称、传递的性质 A上关系的自反、对称、传递闭包 A上的等价关系、等价类、商集与A的划分 A上的偏序关系与偏序集 * 基本要求 熟练掌握关系的三种表示法 能够判定关系的性质（等价关系或偏序关系） 掌握含有关系运算的集合等式 掌握等价关系、等价类、商集、划分、哈斯图、偏序集等概念 计算A?B, dom R, ranR, fldR, R?1, R?S , Rn , r(R), s(R), t(R) 求等价类和商集A/R 给定A的划分?，求出? 所对应的等价关系 求偏序集中的极大元、极小元、最大元、最小元、上界、下界、上确界、下确界 掌握基本的证明方法 证明涉及关系运算的集合等式 证明关系的性质、证明关系是等价关系或偏序关系 * 练习1 1．设A = {1, 2, 3}, R = {x,y | x, y?A且x+2y ? 6 }， S = {1,2, 1,3,2,2}, 求: (1) R的集合表达式 (2) R?1 (3) dom R, ran R, fld R (4) R?S, R3 (5) r(R), s(R), t(R) * 解答 (1) R = {1,1, 1,2, 2,1, 2,2, 3,1} (2) R?1 = {1,1, 2,1, 1,2, 2,2, 1,3 } (3) domR = {1, 2, 3}, ranR = {1,2}, fldR = {1, 2, 3} (4) R?S = {1,2, 1,3, 2,2, 2,3, 3,2, 3,3} R3 = {1,1, 1,2, 2,1, 2,2, 3,1, 3,2} (5) r(R) = {1,1, 1,2, 2,1, 2,2, 3,1, 3,3} s(R) = {1,1,1,2,2,1, 2,2, 3,1, 1,3} t(R) = {1,1, 1,2, 2,1, 2,2, 3,1, 3,2} * 练习2 2．设A={1,2,3,4}，在A?A上定义二元关系R： x,y,u,v?R ? x+y = u+v， 求R导出的划分. A?A={1,1, 1,2, 1,3, 1,4, 2,1, 2,2, 2,3, 2,4,3,1, 3,2, 3,3, 3,4, 4,1, 4,2, 4,3, 4,4} 根据 x,y 中的 x+y = 2, 3, 4, 5, 6, 7, 8 将A划分成等价类： A/R={{1,1}, {1,2,2,1}, {1,3, 2,2, 3,1}, {1,4, 2,3, 3,2, 4,1}, {2,4, 3,3, 4,2}, {3,4, 4,3}, {4,4}} * 3．设R是Z上的模 n 等价关系, 即 x?y ? x ? y(modn), 试给出由R确定的Z的划分?. 练习3 解 设除以 n 余数为 r 的整数构成等价类 [r]，则 [r] ={ kn+r | k?Z }, r = 0, 1, …, n?1 ? = { [r] | r = 0, 1, …, n?1} * 图11 练