解：可用如下方法产生一个等价关系：R-Read.PPT

第三章 作业 P130 (1) P130 (2) P134（2） P134（3） P145（1） P145（4） P145（6） * * 解: 整数4可划分为 4, 1+3, 1+1+2, 2+2, 1+1+1+1 1+C+C+1/2C+1=15 (种) 四个元素的集合共有多少个不同的划分? 证明: （1）自反性：设对任意a?A, 则必存在Ai ,使a?Ai , 因为a与a 可看作在同一块中，故有 a,a ?R。 （2）对称性：设对任意a,b?A, 若有 a,b ?R, 则a, b 必在同一块，故b,a 亦在同一块, b, a ?R。 设{A1 , A2 , …… Ak}是集合A的一个划分, 我们定义A上的一个二元关系R, 使a,b ? R当且仅当a和b在这个划分的同一块中, 证明R是自反、对称和传递的。 （3）传递性：设a,b,c?A, 若有 a,b ?R,且 b, c ?R, 则必?i ,使得a?Ai , b?Ai ;且必?j ,使得b?Aj , c?Aj ; 这样i = j 。因为若i ? j ，则b?Ai?Aj ,故Ai?Aj ??，这与Ai , Aj是A的划分块矛盾, 因此a,b,c 属于同一分块,则 a,c ?R ，即R有是传递的。 试问由四个元素组成的有限集上所有的等价关系的个数为多少? 解: 因为等价关系与划分是一一对应的，因此由上节P130(1)四个元素的集合共有15个不同的划分，可知等价关系的个数也为15个。 给定集合S={1,2,3,4,5}, 找出 S上的等价关系R, 此关系R能够产生划分{{1,2},{3},{4,5}}并划出关系图。 解：可用如下方法 产生一个等价关系： R = {1,2}?{1,2}?{3}?{3}?{4,5}? {4,5}; = { 1,2 , 2,1 , 4,5 , 5,4 } ? IA 1 2 4 5 3 设集合为{3,5,15},{1,2,3,6,12},{3,9,27,54},偏序关系为整除, 划出这些集合的偏序关系图, 并指出哪些是全序关系。 解： 3 5 15 1 2 6 3 12 3 9 54 27 全序关系 找出在集合{0,1,2,3}上包含序偶0,3和2,1 的线序关系。 解： R = { 0,2 , 0,1 , 0,3 , 2,1 , 2,3 , 1,3 } ? IA 0 2 3 1 设集合P ={x1, x2 , x3 , x4 , x5}上的四个偏序关系图如图。找出P的最大元素、最小元素、极大元素、极小元素。找出子集{ x2 , x3 , x4 }、{x3 , x4 , x5}、{x1, x2 , x3}的上界、下界、上确界、下确界。 解： x1 x2 x3 x4 x5 子集{ x2 , x3 , x4 } 上(确)界：x1 下(确)界：x4 子集{x3 , x4 , x5} 上界：x1 , x3 上确界：x3 下(确)界：无 子集{x1, x2 , x3} 上(确)界：x1 下(确)界：x4 极大元素：x1 最大元素：x1 极小元素：x4 , x5 最小元素：无 * *