7偏序关系(离散数学)

(x,y)∊R当且仅当x|y。 证明(Z+，R)是偏序集
5/49
例2 (p109)证明(Z+，R)是偏序集
对于任意的x,y∊Z+，(x,y)∊R当且仅当x|y。
（1）对于任意的x∊Z+,显然有x|x,所以(x,x)∊R,即R是自 反的。
（2）对于任意的x,y∊Z+,若(x,y)∊R,且(y,x)∊R，则 x|y,即 存在n∊Z+,y=nx 且 y|x,即存在m∊Z+,x=my，所以 x=mnx，而n,m∊Z+，所以只有n=m=1， 即x=y时才有(x,y)∊R,且(y,x)∊R ，即R有反对称性 。 （3）对于任意的x,y,z∊Z+,若(x,y)∊R,且(y,z)∊R；则由 (x,y)∊R,得x|y,即∃n0∊Z+，使得y=xn0; 再由 (y,x)∊R, 得y|x,即∃m0∊Z+，使得z=m0y。所以 z=m0n0x，即 x|z，所以(x,z) ∊R, 即R有传递性。
在实数集R上定义二元关系S’， 对于任意的x，y∊R， (x，y) ∊S’当且仅当 x≥y。 可以证明 S’是R上的一个偏序关系。

集合A上的恒等关系 IA 是A上的偏序关系.
8/49
关于记号 ≺
对于一个偏序关系，往往用记号“≺”来表示。
若(a，b) ∊ ≺，记为a ≺ b，读做“ a小于等于b”。
{1,2}
{3.6}
{4,6}
{1}
{2}
{3}
{4}
17/49
哈斯图实例
例 已知偏序集<A,R> 的哈斯图如右图所示, 试求出集合A和关系 R的表达式.
A={a, b, c, d, e, f, g, h} R={<b,d>,<b,e>,<b,f>,<c,d>, <c,e>,<c,f>,<d,f>,<e,f>,<g,h>}∪IA
36
小结

偏序关系
偏序关系（自反、反对称、传递） 哈斯图
画法 从图写出关系

特定元素
极大、极小元与最大、最小元
上界、下界与上、下确界
37
, (b,e), (e,c)
四、偏序集中的特定元素
1、极大元、极小元
设(A，≺)是一个偏序集，BA, y∈B. 若x (x∈B∧x ≺ y) 成立, 则称 y 为B的极 小元. 若x (x∈B∧y ≺ x) 成立, 则称 y 为B的极 大元.
25/49
例 给出如图所示的偏序集。
上节课内容
等价关系 等价类

定义 性质
等价关系
商集、集合的划分 等价关系和划分的对应

1
7.6 偏序关系和格
7.6.1 7.6.2 7.6.3 7.6.4 7.6.5 7.6.6 偏序关系、偏序集 哈斯（Hasse）图 链、反链、全序集 极大元、极小元、最大元、最小元 上界、下界、最小上界、最大下界 格
32/49
例 给出如图所示的偏序集。
j k i g c a
h、i、j和k都是{f，g}的上界， h f a为其下界
b
d
e
33/49
4、上确界、下确界
设(A，≺)是一个偏序集，BA, yA. 令C＝{y | y为B的上界}, 则称C的最小元为 B的最小上界 或 上确界. 令D＝{y | y为B的下界}, 则称D的最大元为 B的最大下界 或 下确界.
即谈到元素是从A中取，讲到关系是在 ≺中 取。
10/49
覆盖
设(A，≺ )是一个偏序集， A是一个有限集， |A|=n。对于任意的x，y∊A，且x≠y，
假设(x, y) ∊≺，即 x ≺ y。 如果对于∀z∊A， 由x ≺ z，且 z ≺ y，一定能够推出x=z或y=z， 那么我们说 y覆盖x。 设R为非空集合A上的偏序关系, x, y∈A, 如 果 x ≺ y且不存在 zA 使得 x ≺ z ≺ y, 则称 y 覆盖x.
e
a
14/49
特点： 每个结点没有环， 两个连通的结点之间的有序关系通 过结点位置的高低表示，位置低的元素 的顺序在前，具有覆盖关系的两个结点 之间连边。
哈斯图实例
例 <{ 1, 2, 3, 4, 5, 6, 7, 8, 9 }, R整除> <P({a, b, c}), R>
16
例 试画出哈斯图
e
c
({ b, e }, ≺) ({ c, e }, ≺)
b
a
22/49
全序集
设(A，≺)是一个偏序集， 如果它本身就是一条链，
那么称之为全序集，并称≺ 为全序关系。
23/49
例
A={ a, b, c, d, e}
c
d c e b a b
d
e
a
≺={ (a,a), (b,b), (c,c), (d,d), (e,e), (a,b), (a,c), (a,d), (a,e), (b,c), (b,d), (c,d), (e,d) }
d 4
2 3 c e b a (b) b h f c a (a) (c) (d) d i g e e f c a g
j
k
Байду номын сангаас
h
b
d
1
29/49
极大、极小与最大最小元的找法： 1、孤立点。 既是极大元也是极小元。 若图中有孤立点，则必无最大、最小元。 2、除孤立点外， 其他极小元是图中所有向下通路的终点； 其他极大元是图中所有向上通路的终点。 3、若极小元唯一则其为最小元； 若极大元唯一则其为最大元；
2/49
一、偏序关系
例 在实数集R上定义二元关系S， 对于任意的x, y∊R， (x，y) ∊S当且仅当 x≤y。 R有自反性、
反对称性、
传递性.
3/49
偏序关系、偏序集
定义1 设A是一个非空集合，R是A上的一个二 元关系，若R有自反性、反对称性、传递性， 则称R是A上的一个偏序关系，记作≼。 并称(A， ≼)是一个偏序集。 如果（x, y)∈≼, 则记作 x≼y, 读作 x“小于或 等于”y。
一个偏序集，通常用符号(A，≺)来表示。
9/49
注意
偏序关系“a小于等于b”，并不意味着平时 意义上的a小于等于b。
一个集合上可以定义不同的偏序关系，得到 不同的偏序集。 还要说明一下，一个偏序集(A，≺ )，包含集 合A与集合A上的偏序关系≺。 不允许x∊(A，≺)出现，
而仅有x∊A，（x，y）∊≺。
例1 A={1, 2, 3, 4} R={(1,1), (2,2), (3,3), (4,4), (1,2), (1,3), (1,4), (2,4)}
R是A上一个偏序关系。
4/49
例2 (p109)
设Z+={n∊Z│n>0}，即Z+是正整数的集合。
在Z+上定义一个二元关系R如下:
对于任意的x,y∊Z+，
34/49
例 给出如图所示的偏 序集。
◆ {b，d}的上界是h和f 下界是a；
e h f c a g d
b 上确界是f，下确界是a。
1、B中的元素向上走共同能到达的即为上界， 上界中的最小元即为上确界； 2、B中元素向下走共同能到达的为下界， 下界中的最大元即为下确界。
35/49
实例
例 设偏序集<A,≼>如下图所示，求 A 的极小元、最 小元、极大元、最大元. 设 B＝{b,c,d}, 求 B 的下界、 上界、下确界、上确界. 极小元：a, b, c, g； 极大元：a, f, h； 没有最小元与最大元. B无下界和下确界, 上界有d 和 f, 上确界为 d.
11/49
A={1, 2, 3, 4}
≺={(1,1), (2,2), (3,3), (4,4), (1,2), (1,3), (1,4), (2,4)} 显然 2覆盖1
4 2 1 3
3覆盖1
4覆盖2，但4不覆盖1
哈斯图
12/49
二、哈斯图（Hasse Diagram)
设(A，≺ )是一个偏序集， A是一个有限集，|A|=n。 可以用一个图形来表示偏序集（A，≺）， 这个图形有 n个顶点，每一个顶点表示A中 一个元素， 两个顶点 x与y，若有y覆盖x，则点x在点y的 下方，且两点之间有一条直线相连结。 哈斯图：利用偏序自反、反对称、传递性 简化的关系图
设A={ {1}, {2}, {3}, {4}, {1,2}, {1,5}, {3,6}, {4,6}, {0,3,6}, {1,5,8}, {0,3,4,6} }
R是A上的一个偏序关系: 对于任意的x,y∊A，(x,y) ∊R当且仅当x⊆y。
{0,3,4,6} {1,5,8} {0,3,6}
{1,5}
13/49
例
A={a, b, c, d, e} ≺={(a,a), (b,b), (c,c), (d,d), (e,e), (a,b), (a,c), (a,d), (a,e), (b,c), (b,d), (c,d), (e,d) }
显然
b覆盖a, e覆盖a c覆盖b d覆盖c d覆盖e
c b
d
1
3
20/49
三、链 、反链
设(A，≺)是一个偏序集，
B是A的一个子集。 (1) 如果Ｂ中任意两个元素都可比,
说(B，≺)是一条链。
(2) 如果Ｂ中任意两个元素都不可比,
说(B，≺)是一条反链。
21/49
例
给出如图所示的偏序集
({ a, b, c, d }, ≺)
d
链 链 反链 反链
({ a, d, e }, ≺)