【集合论】偏序关系 相关题目解析 ( 偏序关系 中的特殊元素 | 绘制哈斯图 | 链 | 反链 )

文章目录

• • • • 偏序关系中的特殊元素问题
      • 偏序关系证明 哈斯图 链 反链

偏序关系中的特殊元素问题

题目 : 偏序关系 特殊元素 ;

• 条件 : 下图是 某一 偏序集

的哈斯图 , 其中

• 问题

:

是什么链 ;

• 问题

:

是什么链 ;

• 问题

:

是什么链 ;

• 问题

:

是什么链 ;

• 问题

:

是什么链 ;

• 问题

:

是什么链 ;

• 问题

:

的上界, 下界, 上确界 , 下确界 ;

• 问题

:

的上界, 下界, 上确界 , 下确界 ;

解答 :

① 问题

:

是一条 长为 4 的 链 ; 这四个元素互相之间是可比的 ; 并且也是覆盖的 ,

覆盖

,

覆盖

,

覆盖

;

② 问题

:

是一条 长为 3 的链 ;

之间都是可比的 , 但没有覆盖关系 , 即他们之间都有其它元素相隔 , 这也是链 ; 集合中有

个元素 , 且这些元素可比 , 那么这个集合就是一个长为

的链 , 中间可以隔着其它元素 ;

③ 问题

:

是一条 长为 2 的链 ;

之间隔着 4 个元素 , 但这个集合中元素是可比的 , 也是链, 长度为集合的元素个数 ;

④ 问题

:

是一条 长为 3 的 反链 ; 集合中的元素 , 都不可比 , 那这个集合就是反链 ; 如果一部分可比 , 另一部分不可比 , 那这个集合什么都不是 , 既不是链 , 也不是反链 ;

⑤ 问题

:

是一条 长为 1 的 链 , 同时也是一条长为 1 的反链 ; 如果集合中只有一个元素 , 那么该集合 既是 链 , 又是 反链 , 长度为

;

⑥ 问题

:

既不是链 , 也不是反链 ;

是可比的,

是可比的 ,

是可比的 ,

是可比的 ,

不可比 ,

不可比 , 因此其 既不是链 , 也不是反链 ;

⑦ 问题

:

上界问题 :

• 1> 上界集合 :

上界集合为

;

• 2> 上确界 ( 最小上界 ) :

的上确界 是

, 即 上界集合的 最小元 ;

注意 : 上界 是一个元素 , 一个集合的上界 可能有很多个, 上界集合 是 上界元素 的集合 ; 上界集合中的最小元 是 上确界 或 最小上界 ; 集合不一定有上界 ( 有可能上面有两个极大元, 互不可比 ) , 有上界 不一定有 上确界 ;

下界问题 :

• 1> 下界集合 :

下界集合为

;

• 2> 下确界 ( 最大下界 ) :

的下确界 是

, 即 下界集合的 最大元 ;

注意 : 下界 是一个元素 , 一个集合的下界 可能有很多个, 下界集合 是 下界元素 的集合 ; 下界集合中的最大元 是 下确界 或 最大下界 ; 集合不一定有下界 ( 有可能下面有两个极小元, 互不可比 ) , 有下界 不一定有 下确界 ( 最大下界 ) ;

求 一个 集合 的 下界和上界 , 注意从集合的 最小元 ( 下界 ) 和 最大元 ( 上界 ) 开始算 , 不要忽略这两个元素 ;

⑧ 问题

:

是反链 , 其没有 上界 和 下界 , 自然 也 不存在 上确界 和 下确界 ; 反链 是 没有 上界 和 下界的 , 元素之间都不可比 ;

偏序关系证明 哈斯图 链 反链

题目 :

• 条件 : 集合

是

的所有因子组成的集合 , "

" 是

上的整除关系 ;

• 问题 1 : 证明该 关系 是 偏序关系 ;
• 问题 2 : 画出关系的哈斯图
• 问题 3 : 确定

中的最长链 ; 写出所有最长链 ;

• 问题4 :

中的元素至少可以划分成多少个互不相交的反链 , 并写出这些反链 ;

解答 :

问题 1 : 偏序关系证明 :

① 写出

的因子集合 : 先列出其素因子 , 然后使用素因子组合即可 ; ( 注意

整除

,

是较小的数 , 是除数 ,

是较大的数 , 是被除数 ,

是整除关系的表示 )

② 证明偏序关系 需要证明其 三个性质 自反 反对称 传递 ;

• 1.证明自反性 :

,

本身 肯定能整除 它自己 ,

与

是可比的 , 因此

是自反的 ;

• 2.证明反对称性 :

能整除

, 并且

不等于

,

肯定不能整除

, 举例

能整除

,

不能整除

;

• 3.证明传递性 :

能整除

,

能整除

, 那么

能整除

成立 , 举例

能整除

,

能整除

, 那么

能整除

;

问题 2 : 画哈斯图 : 先画出

, 从底下向上画, 画完后 逐个检查 是否有遗漏 ;

问题 3 : 确定最长链 并 找出最长链 :

① 逐个寻找 , 最长链为 6 , 从底部到上面 从左到右 逐个分支进行遍历 写出 长度为 6 的链 ; 从底部

开始写 , 最左侧的链 为 :

这个最左侧链从顶部向下走 , 从

开始有个分支 , 写下这个链

继续往下走 ,

的位置有个分支 , 其下对应着

个分支 分别是 :

继续往下走 ,

的位置有分支 , 对应

给出参考答案 , 不在详细列出 :

1→2→4→8→24→120

1→2→4→8→40→120

1→2→4→12→24→120

1→2→4→12→60→120

1→2→6→12→60→120

1→2→6→30→60→120

1→3→6→12→24→120

1→3→6→12→60→120

1→3→6→30→60→120

1→3→15→30→60→120

1→5→10→20→40→120

1→5→10→30→60→120

1→5→15→30→60→120

问题 4 : 集合

至少划分成 多少 互不相交的反链 , 完整写出这些反链 :

分析 : 将集合

划分成最多的反链个数 是

个 , 即每个元素都划分成一个单独的反链 ;

现在需要将其尽可能多的将上述集合进行合并 , 每个集合必须是反链 :

结果 : 至少能划分成 6 个互不相交的反链 ;

技巧 : 哈斯图 横向 没有关联的一条线 可以组成一条反链 ;