等价关系与 及序关系 北京大学计算机系离散数学讲义(ppt版).pptVIP

《集合论与图论》第8讲 偏序集A,?, A,?, A,| ??A?R ? = { x,y | x,y?A ? x?y }, ? = { x,y | x,y?A ? x?y }, ??A?Z+={ x | x?Z ? x0 } | = { x,y | x,y?A ? x|y } 偏序集A,? A?P(A), ? = { x,y | x,y?A ? x?y } 设A={a,b}, A1={?,{a},{b}}, A2={{a},{a,b}}, A3=P(A)={?,{a},{b},{a,b}},则 ?1 = IA1 ? { ?,{a},?,{b} } ?2 = IA2 ? { {a},{a,b} } ?3 = IA3 ? { ?,{a},?,{b}, ?,{a,b}, {a},{a,b}, {b},{a,b} } 偏序集?,?加细 A??, ?是由A的一些划分组成的集合 ?加细 = { x,y | x,y?? ? x是y的加细 } 设A={a,b,c}, A1={{a,b,c}},A2={{a},{b,c}}, A3={{b},{a,c}},A4={{c},{a,b}},A5={{a},{b},{c}} 取?1={A1,A2},?2={A2,A3},?3={A1,A2,A3,A4,A5} ?1 = I?1 ? { A2,A1 }, ?2 = I?2, ?3 = I?3 ? { A2,A1,A3,A1, A4,A1, A5,A1,A5,A2,A5,A3,A5,A4}. # 哈斯图(Hasse diagram) 设A,?是偏序集, x,y?A 可比(comparable): x与y可比 ? x?y ? y?x 覆盖(cover): y覆盖x ? x?y ? ??z( z?A ? x?z?y ) 哈斯图: 当且仅当y覆盖x时,在x与y之间画无向边, 并且x画在y下方 例16(1)(2) 例16: 画出下列偏序关系的哈斯图. (1) A,|, A={1,2,3,4,5,6,9,10,15} (2) A,?, A={a,b,c}, A?P(A), A={?,{a},{b},{c},{a,b},{b,c},{a,c}} 解: 1 2 4 3 6 9 15 5 10 ? {a} {b} {c} {a,b} {a,c} {b,c} 例16(3) 例16: 画出下列偏序关系的哈斯图. (3) ?,?加细, ?={A1,A2,A3,A4,A5,A6}, A={a,b,c,d} A1 = { {a}, {b}, {c}, {d} }, A2 = { {a,b}, {c,d} }, A3 = { {a,c}, {b,d} }, A4 = { {a}, {b,c,d} }, A5 = { {a}, {b}, {c,d} }, A6 = { {a,b,c,d} } 解: A1 A2 A5 A3 A4 A6 # 偏序关系中的特殊元素 最大元, 最小元 极大元, 极小元 上界, 下界 最小上界(上确界), 最大下界(下确界) 最大元, 最小元 设A,?为偏序集, B?A, y?B 最大元(maximum/greatest element): y是B的最大元 ? ?x( x?B ? x?y ) 最小元(minimum/least element): y是B的最小元 ? ?x( x?B ? y?x ) 最大元, 最小元举例(例16(1)) 例16(1): A,|, A={1,2,3,4,5,6,9,10,15} B1={1,2,3}, B2={3,5,15}, B3=A. B1的最大元是{}, B1的最小元是{1} B2的最大元是{15}, B2的最小元是{} B3的最大元是{}, B3的最小元是{1} 1 2 4 3 6 9 15 5 10 1 2 4 3 6 9 15 5 10 极大元,极小元 设A,?为偏序集, B?A, y?B 极大元(maximal element): y是B的极大元 ? ?x( x?B ? y?x ? x=y ) 极小元(minimal element): y是B的极小元 ? ?x( x?B ? x?y ? x=y ) 极大元,极小元举例(例16(1)) 例16(1): A,|, A={1,2,3,4,5,6,9,10,15} B1={1,2,3}, B2={3,5,15}, B3=A. B1的极大元是{2,3}, B1的极小元是{1} B2的极大元是{15}, B2的极小元是{3,5} B3的极大元是{4,6,