文章目录
偏序关系中的特殊元素问题偏序关系证明 哈斯图 链 反链偏序关系中的特殊元素问题
题目 :偏序关系 特殊元素 ;
条件 :下图是 某一 偏序集 <A,⪯><A, \preceq><A,⪯> 的哈斯图 , 其中 A={a,b,⋯ ,k}A=\{a,b,\cdots,k\}A={a,b,⋯,k}问题 111 :B1={a,c,d,e}B_1 = \{a,c,d,e\}B1={a,c,d,e} 是什么链 ;问题 222 :B2={a,e,h}B_2 = \{a,e,h\}B2={a,e,h} 是什么链 ;问题 333 :B3={b,g}B_3 = \{b,g\}B3={b,g} 是什么链 ;问题 444 :B4={g,h,k}B_4 = \{g,h,k\}B4={g,h,k} 是什么链 ;问题 555 :B5={a}B_5 = \{a\}B5={a} 是什么链 ;问题 666 :B6={a,b,g,h}B_6 = \{a, b, g, h\}B6={a,b,g,h} 是什么链 ;问题 777 :B1B_1B1 的上界, 下界, 上确界 , 下确界 ;问题 888 :B4B_4B4 的上界, 下界, 上确界 , 下确界 ;
解答 :
① 问题 111 : B1={a,c,d,e}B_1 = \{a,c,d,e\}B1={a,c,d,e} 是一条 长为 4 的 链 ;
这四个元素互相之间是可比的;并且也是覆盖的 , eee 覆盖 ddd , ddd 覆盖 ccc , ccc 覆盖 aaa;
② 问题 222 : B2={a,e,h}B_2 = \{a,e,h\}B2={a,e,h} 是一条 长为 3 的链 ;
a,e,ha,e,ha,e,h 之间都是可比的 , 但没有覆盖关系 , 即他们之间都有其它元素相隔 , 这也是链 ;
集合中有 nnn 个元素 , 且这些元素可比 , 那么这个集合就是一个长为 nnn 的链 , 中间可以隔着其它元素 ;
③ 问题 333 : B3={b,g}B_3 = \{b,g\}B3={b,g} 是一条 长为 2 的链 ;
b,gb,gb,g 之间隔着 4 个元素 , 但这个集合中元素是可比的 , 也是链, 长度为集合的元素个数 ;
④ 问题 444 : B4={g,h,k}B_4 = \{g,h,k\}B4={g,h,k} 是一条 长为 3 的 反链 ;
集合中的元素 , 都不可比 , 那这个集合就是反链;
如果一部分可比 , 另一部分不可比 , 那这个集合什么都不是 , 既不是链 , 也不是反链 ;
⑤ 问题 555 : B5={a}B_5 = \{a\}B5={a} 是一条 长为 1 的 链 , 同时也是一条长为 1 的反链 ;
如果集合中只有一个元素 , 那么该集合 既是 链 , 又是 反链 , 长度为 111 ;
⑥ 问题 666 : B6={a,b,g,h}B_6 = \{a, b, g, h\}B6={a,b,g,h} 既不是链 , 也不是反链 ;
g,ag,ag,a 是可比的, h,ah,ah,a 是可比的 , g,bg,bg,b 是可比的 , h,bh,bh,b 是可比的 , g,hg,hg,h 不可比 , a,ba,ba,b 不可比 , 因此其 既不是链 , 也不是反链 ;
⑦ 问题 777 :
上界问题 :
1> 上界集合 :B1={a,c,d,e}B_1 = \{a,c,d,e\}B1={a,c,d,e} 上界集合为 {e,f,g,h}\{e, f,g,h\}{e,f,g,h};2> 上确界 ( 最小上界 ) :B1B_1B1 的上确界 是 eee , 即 上界集合的 最小元;
注意 :
上界 是一个元素 , 一个集合的上界 可能有很多个, 上界集合 是 上界元素 的集合 ;
上界集合中的最小元 是 上确界 或 最小上界 ;
集合不一定有上界 ( 有可能上面有两个极大元, 互不可比 ) , 有上界 不一定有 上确界 ;
下界问题 :
1> 下界集合 :B1={a,c,d,e}B_1 = \{a,c,d,e\}B1={a,c,d,e} 下界集合为 {a}\{a\}{a};2> 下确界 ( 最大下界 ) :B1B_1B1 的下确界 是 aaa , 即 下界集合的 最大元;
注意 :
下界 是一个元素 , 一个集合的下界 可能有很多个, 下界集合 是 下界元素 的集合 ;
下界集合中的最大元 是 下确界 或 最大下界 ;
集合不一定有下界 ( 有可能下面有两个极小元, 互不可比 ) , 有下界 不一定有 下确界 ( 最大下界 ) ;
求 一个 集合 的 下界和上界 , 注意从集合的 最小元 ( 下界 ) 和 最大元 ( 上界 ) 开始算 , 不要忽略这两个元素 ;
⑧ 问题 888 :B4={g,h,k}B_4 = \{g,h,k\}B4={g,h,k} 是反链 , 其没有 上界 和 下界 , 自然 也 不存在 上确界 和 下确界 ;
反链 是 没有 上界 和 下界的 , 元素之间都不可比 ;
偏序关系证明 哈斯图 链 反链
题目 :
条件 :集合 AAA 是 10120 的所有因子组成的集合 , " ∣|∣ " 是 AAA 上的整除关系 ;问题 1 :证明该 关系 是 偏序关系 ;问题 2 :画出关系的哈斯图问题 3 :确定 AAA 中的最长链 ; 写出所有最长链 ;问题4 :AAA 中的元素至少可以划分成多少个互不相交的反链 , 并写出这些反链 ;
解答 :
问题 1 : 偏序关系证明 :
① 写出 10120 的因子集合 : 先列出其素因子 , 然后使用素因子组合即可 ;
( 注意 xxx 整除 yyy , xxx 是较小的数 , 是除数 , yyy 是较大的数 , 是被除数 , 除数∣被除数除数 | 被除数除数∣被除数 是整除关系的表示 )
A={1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120}A=\{1, 2,3,4,5,6,8,10,12,15,20,24,30, 40,60,120\}A={1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120}
② 证明偏序关系 需要证明其 三个性质 自反 反对称 传递 ;
1.证明自反性 :∀x∈A\forall x \in A∀x∈A , xxx 本身 肯定能整除 它自己 , xxx 与 xxx 是可比的 , 因此 xxx 是自反的;2.证明反对称性 :xxx 能整除 yyy , 并且 xxx 不等于 yyy , yyy 肯定不能整除 xxx , 举例 111 能整除 222 , 222 不能整除 111 ;3.证明传递性 :xxx 能整除 yyy , yyy 能整除 zzz , 那么 xxx 能整除 zzz 成立 , 举例 111 能整除 222 , 222 能整除 444 , 那么 111 能整除 444 ;
问题 2 : 画哈斯图 :先画出 111 , 从底下向上画, 画完后 逐个检查 是否有遗漏 ;
问题 3 : 确定最长链 并 找出最长链 :
① 逐个寻找 , 最长链为 6 , 从底部到上面 从左到右 逐个分支进行遍历 写出 长度为 6 的链 ;
从底部 111 开始写 , 最左侧的链 为 :
{1,2,4,8,24,120}\{1,2,4,8,24,120\}{1,2,4,8,24,120}
这个最左侧链从顶部向下走 , 从 888 开始有个分支 , 写下这个链
{1,2,4,8,40,120}\{1,2,4,8,40,120\}{1,2,4,8,40,120}
继续往下走 , 444 的位置有个分支 , 其下对应着 333 个分支 分别是 :
{1,2,4,12,24,120}\{1,2,4,12,24,120\}{1,2,4,12,24,120}
{1,2,4,12,60,120}\{1,2,4,12,60,120\}{1,2,4,12,60,120}
{1,2,4,20,60,120}\{1,2,4,20,60,120\}{1,2,4,20,60,120}
继续往下走 , 222 的位置有分支 , 对应
给出参考答案 , 不在详细列出 :
1→2→4→8→24→1201→2→4→8→40→1201→2→4→12→24→1201→2→4→12→60→1201→2→6→12→60→1201→2→6→30→60→1201→3→6→12→24→1201→3→6→12→60→1201→3→6→30→60→1201→3→15→30→60→1201→5→10→20→40→1201→5→10→30→60→1201→5→15→30→60→120
问题 4 : 集合 AAA 至少划分成 多少 互不相交的反链 , 完整写出这些反链 :
分析 : 将集合 AAA 划分成最多的反链个数 是 161616 个 , 即每个元素都划分成一个单独的反链 ;
{{1},{2},{3},{4},{5},{6},{8},{10},{12},{15},{20},{24},{30},{40},{60},{120}}\{\{1\}, \{2\}, \{3\}, \{4\}, \{5\}, \{6\}, \{8\}, \{10\}, \{12\}, \{15\}, \{20\}, \{24\}, \{30\}, \{ 40\}, \{60\}, \{120\}\}{{1},{2},{3},{4},{5},{6},{8},{10},{12},{15},{20},{24},{30},{40},{60},{120}}
现在需要将其尽可能多的将上述集合进行合并 , 每个集合必须是反链 :
{{1},{120},{2,3,5},{4,6,15,10},{8,12,30,20},,{24,60,40}}\{ \{ 1 \}, \{ 120 \}, \{2,3,5\} , \{ 4,6,15,10 \} , \{ 8, 12 , 30, 20 \} , , \{ 24, 60 , 40 \} \}{{1},{120},{2,3,5},{4,6,15,10},{8,12,30,20},,{24,60,40}}
结果 : 至少能划分成 6 个互不相交的反链 ;
技巧 : 哈斯图 横向 没有关联的一条线 可以组成一条反链 ;
