离散数学 课件 3.11 偏序关系

CHAPTER03集合与关系3.11偏序关系偏序关系：核心概念与分析工具偏序关系的概念定义、范例与充要条件证明元素间的“可比”与“不可比”盖住关系与覆盖的定义哈斯图(HasseDiagram)图的简化规则与直观意义基于盖住关系的标准绘制法链、反链与全序关系的判定偏序集中的特殊元素最大/最小元vs极大/极小元上界、下界、上确界与下确界良序关系及其性质3.11.1偏序关系的概念定义3.41：偏序关系的定义设R为定义在集合A上的一个关系，若R满足自反性、反对称性和传递性，则称R是A上的一个偏序关系(OrderingRelation)，通常记作符号“≼”。序偶<A,≼>称作偏序集(poset)。自反性Reflexivity关系中的每一个元素，都必须与自身保持该关系。即对于任意a∈A，均有a≼a成立。反对称性Antisymmetry两个不同的元素不能相互“序”关系。若a≼b且b≼a，当且仅当这两个元素相等时成立，即a=b。传递性Transitivity序关系具有“接力”的特征。若a≼b且b≼c，则可以直接推导出a≼c成立。偏序关系的典型范例范例1：实数集上的“小于等于”关系在实数集R上，“小于等于”关系“≤”是一种最直观的偏序关系。它满足：•自反性：对任意实数x，总有x≤x。•反对称性：若x≤y且y≤x，则必有x=y。•传递性：若x≤y且y≤z，则必有x≤z。💡注意：偏序关系的通用符号“≼”正源于此。它代表元素间存在一种“先后”或“优劣”的排序逻辑，并不局限于数值的大小比较。范例2：正整数集上的整除关系在正整数集合N⁺上，“整除”关系“|”（a|b表示a整除b）也是一个经典的偏序关系：•自反性：任意正整数n都能整除自身(n|n)。•反对称性：若a|b且b|a，则必有a=b。•传递性：若a|b且b|c，则必有a|c。📌应用：数论中的许多问题都基于这种偏序关系展开。例如，我们可以在这个集合上找到两个数的“最小公倍数”（上确界）和“最大公约数”（下确界）。例题3.48：证明整除关系是偏序关系题目：设集合A为非零整数集合，证明A上的整除关系R={<x,y>|(x,y∈A)，x能整除y}是偏序关系。💡思路：偏序关系需满足三大性质—自反性、反对称性、传递性。我们逐一验证。01自反性(Reflexivity)根据整数的性质，任意非零整数x都能整除它本身，即x|x。结论：R满足自反性。02反对称性(Antisymmetry)若x|y且y|x，则存在整数p,q使y=px,x=qy。代入得x=pqx，即pq=1。在整数范围内，唯一解为p=q=1，故x=y。结论：R满足反对称性。03传递性(Transitivity)若x|y且y|z，则存在整数p,q使y=qx,z=py。代入得z=p(qx)=(pq)x。由于pq为整数，所以x|z。结论：R满足传递性。由上述推导可知，集合A上的整除关系R同时满足自反性、反对称性与传递性。∴R是集合A上的一个偏序关系。(Q.E.D.)例题3.49：分析集合A上的整除关系题目描述：集合A={2,3,6,8,12,16,24,32}，R是定义在集合A上的整除关系。求出R的序偶集合和关系图，并判断R是何种关系。序偶集合R{<2,2>,<2,6>,<2,8>,<2,12>,<2,16>,<2,24>,<2,32>,

<3,3>,<3,6>,<3,12>,<3,24>,<6,6>,<6,12>,<6,24>,

<8,8>,<8,16>,<8,24>,<8,32>,<12,12>,<12,24>,

<16,16>,<16,32>,<24,24>,<32,32>}关系性质分析•自反性：每个元素x∈A均满足xRx，即关系图中每个元素都有自环。•反对称性：若xRy且yRx，则必有x=y，即图中不存在双向边（除自环外）。•传递性：若xRy且yRz，则必有xRz，即图中若有x→y和y→z，则有x→z。结论判定关系R同时满足

自反性、反对称性、传递性偏序关系(Poset)可比(Comparable)与不可比(Incomparable)核心定义在偏序集(S,≼)中，对于其中的任意两个元素a和b：•若满足a≼b或b≼a，则称元素a与b是可比的(Comparable)。•若既不满足a≼b，也不满足b≼a，则称元素a与b是不可比的(Incomparable)。例题解析3.50在偏序集(Z⁺,|)中，整数3和9是否可比？整数5和7是否可比？解：整数3和9是可比的，因为3|9(3整除9)。整数5和7是不可比的，因为5不能整除7，且7也不能整除5。定义3.42：盖住(Cover)核心定义在偏序集合<A,≼>中，如果x,y∈A，且满足：1.x≼y且x≠y；2.不存在任何元素z使得x≼z且z≼y。此时称元素y盖住元素x。COVA={<x,y>|x,y∈A，y盖住x}直观理解“盖住”关系是绘制哈斯图(HasseDiagram)的理论基础。在哈斯图中，如果y盖住x，那么在图中y和x之间会有一条直接相连的线段。这意味着两点之间“没有中间节点”，也没有其他路径。简单来说，它们是“紧挨着”的两个节点。典型示例设集合A={2,3,6,8,12,16,24,32}，关系为“整除”。✅8盖住2，16盖住8。❌16不盖住2，因为中间存在元素8。COVA={<2,6>,<2,8>,<3,6>,<6,12>,<8,16>,<8,24>,<12,24>,<16,32>}3.11.2哈斯图(HasseDiagram)定义：哈斯图是对偏序集的关系图进行简化后得到的图形，能够直观展示偏序集的层次关系，去除冗余信息，仅保留“覆盖关系”的核心结构。01.取消自环利用偏序关系的自反性简化。

因为对于所有元素，均有x≼x，故省略所有元素上的自环，直接用小圆圈代表偏序集中的各个元素。02.取消传递边利用偏序关系的传递性简化。

仅保留“直接”的覆盖关系(COVA)。若x≼y且x≠y，将y画在x的上方，中间不经过其他元素。03.去掉箭头利用偏序关系的反对称性简化。

统一规定图中所有边的方向均“自下而上”，故可以直接省略所有箭头符号，使图形更简洁明了。从关系图到哈斯图示例场景：集合A={2,3,6,8,12,16,24,32}上的“整除”二元关系分析。原始关系图对应图示：图3.31包含所有元素间满足“整除”关系的直接连线，以及每个节点上的自环。虽然信息完整，但存在大量传递性的冗余边，视觉上较为杂乱，难以快速看清核心层级。关键简化步骤❶去自环：偏序关系的自反性无需显式画出。❷去传递边：仅保留覆盖关系（即直接前驱/后继）。❸规范化：重排节点使所有边向上，隐去箭头。最终哈斯图对应图示：图3.32(右图)去除所有冗余信息后，形成的简洁层次结构图。哈斯图完美展示了集合中元素的“覆盖”关系，以及偏序集的极大/极小元，让复杂的代数结构变得一目了然。例题3.51：根据关系图绘制哈斯图题目：设集合A={a,b,c,d,e}，偏序集<A,R>的关系图如下所示。请依据偏序关系的性质，简化并绘制该关系R的哈斯图。关系图(RelationDiagram)包含所有的直接和间接序偶。图中会包含大量的连线（如传递边）和自环，视觉上较为复杂。哈斯图(HasseDiagram)偏序关系的简化图。去除自环、传递边和箭头，通过“自下而上”的位置关系表示序偶，结构清晰。确定极值位置极大元c放在最顶层，极小元e放在最底层，建立基准框架。梳理层级关系左侧列：元素b在a的上方，表示b覆盖a。通过“覆盖”关系建立垂直连接。处理独立分支右侧列：将与左侧无关联的元素d单独列为一支，清晰展示其在偏序中的独立路径。定义3.43：链(Chain)与反链(Antichain)链(Chain)在偏序集<A,≼>的一个子集中，如果每两个元素都是有关系的（即可比的），则称这个子集为链。反链(Antichain)在偏序集<A,≼>的一个子集中，如果每两个元素都是无关的（即不可比的），则称这个子集为反链。偏序集哈斯图利用图形的层次结构，可直观地判断元素间的可比性，快速识别链与反链。典型示例：▍链：{a,b,c,e},{b,c},{c,d,e}▍反链：{a,d},{b,d}定义3.44：全序关系(TotalOrder)定义Definition设<A,≼>是一个偏序集合，如果A是一个链，则称<A,≼>为全序集合或称线序集合，二元关系≼称为全序关系或称线序关系。特征Characteristic对任意x,y∈A，必有x≼y或y≼x成立（任意两元素皆可比）。其哈斯图（HasseDiagram）的形状呈现为一条直线。示例Example•自然数集合N上的“小于等于”(≤)关系是典型的全序关系。

•集合A={3,6,12,24}上的整除关系，哈斯图呈直线排列，是全序集合。图示：全序关系的哈斯图

(所有元素线性连接，两两可比)3.11.3特殊元素：最大元与最小元定义3.45：最大元(GreatestElement)与最小元(LeastElement)最大元(GreatestElement)设<A,≼>是偏序集，B⊆A。若存在b∈B，使得对于集合B中的每一个元素x，都有x≼b，则称元素b为B的最大元。最小元(LeastElement)设<A,≼>是偏序集，B⊆A。若存在b∈B，使得对于集合B中的每一个元素x，都有b≼x，则称元素b为B的最小元。搜索范围最大元/最小元必须在子集B中寻找，不能在父集A\B中。全域关系该元素必须与子集B中的所有其他元素都可比，存在偏序关系。唯一性定理若子集B的最大元或最小元存在，则一定是唯一的（定理3.27）。例题3.53：求子集的最大元与最小元图3.36偏序集的哈斯图示意子集B={6,12}最大元为12，最小元为6。子集B={2,3}2与3不可比，故无最大/最小元。子集B={24,36}24与36不可比，故无最大/最小元。子集B={2,3,6,12}最大元为12，无最小元。子集类型{6,12}{2,3}{24,36}{2,3,6,12}最大元12无无12最小元6无无无定义3.46：极大元(MaximalElement)与极小元(MinimalElement)设<A,≼>是偏序集，且B⊆A。极大元(Maximal)若存在元素b∈B，且在集合B中没有任何元素x满足条件：b≠x且b≼x，则称b为B的极大元。极小元(Minimal)若存在元素b∈B，且在集合B中没有任何元素x满足条件：b≠x且x≼b，则称b为B的极小元。范围限制寻找的对象必须在子集B中，而非全集合A中。比较逻辑在子集B的范围内，不存在比它“大”或“小”的元素。数量特性不一定唯一。根据偏序关系的结构，一个子集B中可以有多个极大元或极小元。哈斯图直观极大元通常位于哈斯图的最上层，极小元通常位于最下层。例题3.54：求子集的极大元与极小元求解思路与分析B={6,12}：6小于12，故极大元为12，极小元为6。B={2,3}：2和3之间没有偏序关系，互不整除，因此二者同为极大元和极小元。B={24,36}：24和36互不整除，不存在序关系，所以两者都是极大元和极小元。B={2,3,6,12}：2和3是“源头”，故为极小元；12是“终点”，故为极大元。结果汇总表子集{6,12}{2,3}{24,36}{2,3,6,12}极大元122,324,3612极小元62,324,362,3定义3.47&3.48：界与确界上界(UpperBound)设<A,≼>是偏序集，B⊆A。若存在元素a∈A，使得对所有x∈B，都满足x≼a，则称a为B的一个上界。下界(LowerBound)设<A,≼>是偏序集，B⊆A。若存在元素a∈A，使得对所有x∈B，都满足a≼x，则称a为B的一个下界。上确界(LeastUpperBound,LUB)若a是B的一个上界，且对于B的任意上界y，均有a≼y，则称a为B的上确界。即：B的最小上界。下确界(GreatestLowerBound,GLB)若b是B的一个下界，且对于B的任意下界z，均有z≼b，则称b为B的下确界。即：B的最大下界。存在范围界和确界均属于整个集合A，不一定在子集B中。核心特征确界是界中具有极值性质的特殊元素：最小的上界或最大的下界。唯一性一个集合的界通常不唯一；若确界存在，则必然唯一。例题3.55：求子集的界与确界📝逐步求解思路•子集B={6,12}：上界为{12,24,36}，故上确界为12；

下界为{2,3,6}，故下确界为6。•子集B={2,3}：上界为{6,12,24,36}，故上确界为6；

该偏序集中不存在比2和3更小的元素，因此无下界与下确界。•子集B={24,36}：该偏序集中不存在比24和36更大的元素，故无上界与上确界；

下界为{2,3,6,12}，故下确界为12。•子集B={2,3,6,12}：上界为{12,24,36}，上确界为12；无下界与下确界。📊结果汇总表子集{6,12}{2,3}{24,36}{2,3,6,12}上界12,24,366,12,24,36无12,24,36上确界126无12下界2,3,6无2,3,6,12无下确界6无12无例题3.57：综合练习例题3.57哈斯图(图3.38)集合A的特殊元素•最大元：x₁；无最小元

•极大元：x₁

•极小元：x₄,x₅子集{x₂,x₃,x₄}•上界：x₁；下界：x₄

•上确界：x₁

•下确界：x₄子集{x₃,x₄,x₅}•上界：x₁,x₃；无下界

•上确界：x₃

•下确界：不存在子集{x₁,x₂,x₃}•上界：x₁；下界：x₄

•上确界：x₁

•下确界：x₄定义3.49：良序(Well-ordered)核心定义Definition任一偏序集合，假如它的每一个非空子集都存在最小元素，这种偏序集称为良序的(Well-ordered)。(S,≼)isawell-orderedsetifitisaposetsuchthat≼isatotalorderingandeverynonemptysubsetofShasaleastelement.正面示例·Positive有限整数集In={1,2,…,n