二元关系偏序关系

1离散数学DiscreteMathematics主讲：陈哲云青岛理工大学计算机工程学院2023.09第1页第4章二元关系第2页二元关系4.1二元关系基本概念(重点)4.2关系运算4.3关系性质(重点)4.4关系闭包4.5等价关系和偏序关系(重点及难点)4.6函数基本概念第3页偏序关系偏序关系Hasse图（重点）主要元素（重点）拓扑排序第4页偏序关系定义

偏序关系：设A上二元关系R,假如R是自反,

反对称，传递，则称R为偏序关系，记为“≼”,<A,

≼

>称为偏序集。若<x，y>∈R，称“x不大于等于y”，记作x

≼

y。第5页偏序关系例1

几个常见偏序关系：(1)A上不大于等于关系，A={1,2,3,4,5,6}：Ｒ1={<x，y>｜x≤y，x，y∈A}(2)

A上整除关系，A={1,2,3,4,5,6}：Ｒ2＝{<x，y>｜x|y，x，y∈A}(3)P(A)上包括关系，A={1,2,3}：Ｒ3＝{<s1，s2>｜s1

s2，s1，s2∈P(A)}(4)任务集S={T1,T2,....,Tn}上关系R4={<Ti,Tj>|Ti=Tj或Ti必须在Tj之前完成}≼≼≼≼第6页偏序关系有关例1(4)一种举例：如完成室内闪光拍照任务，任务集T包括任务：1、打开镜头盖；2、照相机调焦；3、打开闪光灯；4、按下快门按钮。在T上定义关系R：<i,j>∈R假如i=j或者任务i必须在任务j之前完成。则R={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<1,4>,<2,4>,<3,4>}第7页偏序关系定义

设R为非空集合A上偏序关系,x,y∈A,则x与y可比

x≼y∨y≼x定义设R为非空集合A上偏序关系,x,y∈A,则y盖住x

x≺y且不存在z∈A使得x≺z≺y第8页Hasse（哈斯）图例2

设A={2,3,6,12,24,36}，“≼”是A上整除关系R，画出其关系图。

关系图236123624236123624简化关系图——Hasse图第9页Hasse图简化关系图——Hasse图（哈斯图）

(1)自反性：每个顶点都有自回路，省去。

(2)反对称性：两个顶点间只也许有一种箭头，从小到大(或从低到高)安顿顶点，可省略箭头。

(3)传递性：由于有<x，y>，<y，z>∈R，则<x，z>∈R，故只画<x，y>，<y，z>对应边，省略边<x，z>。第10页Hasse图Hasse图画法——“层次”与“连线”(1)极小元放在第一层（最底层）。(2)若第n层已放好，则第n+1层元素满足最少能盖住第n层一种元素。（层次）(3)若y盖住x，则x，y之间连线。（连线）注：哈斯图体现了偏序集中元素间“大小”和“层次”关系。第11页Hasse图例3

画出例1中各关系Hasse图：

A＝{1,2,3,4,5,6,7,8,9},

B＝{a,b,c},S={1,2,3,4}

Ｒ1＝｛<x，y>｜x≤y，x，y∈A｝Ｒ2＝｛<x，y>｜x|y，x，y∈A｝Ｒ3＝｛<s1，s2>｜s1

s2，s1，s2∈P(B)｝R4={<Ti,Tj>|Ti=Tj或Ti必须在Tj之前完成且Ti,Tj∈S}

={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<1,4>,<2,4>,<3,4>}第12页Hasse图Ｒ1Ｒ2——全序集第13页Hasse图1243Ｒ3Ｒ4第14页全序关系定义

全序关系——任意两个元素都可比

设<A,≼>是一种偏序集，若对任意x,y∈A，总有x≼y或y≼x，二者必居其一，则称“”为全序关系，或者线序关系。称<A,≤>为全序集，或者线序集，或者链。第15页偏序集中主要元素设偏序集<A,

≼

>,B

A，b表达对应特殊元素，B极小元——B中没有比b小元素

b∈B且x(x∈Bx≺b)B最小元——B中所有元素都比b大b∈B且

x(x∈B→b≼x)极大元和最大元类似定义。

注：上述元素都在B中寻找。第16页偏序集中主要元素设偏序集<A,

≼

>,B

A，b表达对应特殊元素，B上界—B中所有元素都比b小

b∈A且

x(x∈B→x≼b)

B上确界

上确界——B上界最小元下界和下确界类似定义。

注：上述元素都在A中寻找。

第17页偏序集中主要元素例4

设偏序集<A,≼>，求A极小元、极大元、最小元、最大元。设B＝{b,c,d},求B下界、上界、下确界、上确界.解：极小元：a,b,c,g；极大元：a,f,h；没有最小元与最大元.B下界和下确界都不存在；上界有d和f,上确界为d.

第18页偏序集中主要元素性质：

(1)对于有穷集，极小元和极大元一定存在，也许存在多种。(2)最小元和最大元不一定存在，假如存在一定惟一。(3)最小元一定是极小元；最大元一定是极大元。

(4)孤立结点既是极小元，也是极大元。(5)下界、上界、下确界、上确界不一定存在，存在不一定唯一。(6)下确界、上确界假如存在，则惟一。第19页偏序集中主要元素练习

<A，≼>Hasse图如下所示，讨论当B取对应集合时，其最大元，最小元，极大元，极小元，上界，下界，上确界，下确界。B1={a,b},B2={a,b,c},B3={a,b,c,d},B4={b,c,d,f},B5={a,c,f,i}

abcdefghi第20页B极小元极大元最小元最大元{a,b}{a,b,c}a,ba,b无无a,bc无c{a,b,c,d}{b,c,d,f}{a,c,f,i}a,bc,d无bfbaia无fiabcdefghi第21页无bB上界下界上确界下确界{a,b}{a,b,c}c,d,e,f,g,h,i无无c,e,f,h,i无c无{a,b,c,d}{b,c,d,f}{a,c,f,i}f,h,i无f无f,h,ibfiaiaabcdefghi第22页小结偏序关系是“次序”关系，但不一定是“全序”关系。哈斯图是偏序集简化图，通过“层次”关系来体现元素“大小”关系。偏序集中特殊元素能够通过哈斯图来寻找。第23页作业1.下列图中给出了偏序集<A,≼>Hasse图。