离散数学课件-次序关系

离散数学 离散数学
1
学习内容
7.2 等价关系
7.3 次序关系
2
次序关系

偏序关系 拟序关系 全序关系 良序关系
3
偏序关系

定义1：R是A上的关系，如果它是自反、反对称和传递的， 则称R 是A上的偏序关系。并称<A,R>是偏序集。 例 试判断下列关系是否为偏序关系 是 (1)集合A的幂集P(A)上的包含关系“”； 是 (2)实数集合R上的小于或等于关系“≤” 因为数值的“≤”是熟知的偏序关系，所以用符号 “≤”表示任意偏序关系 但要注意：“≤”不一定是“小于或等于”的含义; 不是指数值的大小而是指偏序中元素位置的先后。 例 : A={1,2,4,6}, 设≤是A中的整除关系。显然“≤” 是自反、反对称和传递的，即它是个偏序。
7
例 A={1,2,4,6}, ≤表示整除关系，则≤是个偏序。 1
。 。
关系图
6
６
。
２
４
。
2
。 4
。 １。
哈斯图
画法：一般先从最下层结点(全是射出的边与之相连)， 逐层向上画，直到最上层结点(全是射入的边与之相连)。
8
例7.3.7 A={2,3,6,12,24,36}, ≤ 是A上整除关系。画出关系 图及哈斯图。
例：<Ｎ，|>是偏序集，
Ａ＝｛２，３，４，５，６，７，８，９｝ 则 Ａ中极大元：８，６，９，５，７ 极小元：２，３，５，７
13
二.最小元与最大元 （1）如果存在一个元素b∈B对每一个b’∈B 均有b ≤ b’ 则 称b是B的最小元 (最小元b是B中元素，该元素比B中所有元素都小) （2）如果存在一个元素b∈B对每一个b’∈B 均有b’ ≤ b 则称 b是B的最大元 (最大元b是B中元素，该元素比B中所有元素都大) 举例，给定<C,≤>的Hasse图如图所示： 从Hasse图找最小(大)元：子集中如果只有唯一的极 小(大)元，则这个 24。 36。 最小元 最大元 子集B 极小(大)元，就是 12。 {2,3} 无 无 最小(大)元。否则 {1,2,3} 1 无 ６。 就没有最小(大)元。 {6,12,24} 24 6 ２。 ３。 1 C 无 １。 下面介绍最小(大)元的唯一定理。
4
补充定义： x与y是可比较的： <A,≤>是偏序集，如果对x,y∈A，必有x≤y,或y≤x, 则称x与y是可比较的。 上例中1,2,4或1,2,6间是可比较的，而4与6间是不可比较的 【注意】若“≤”是集合A上的一个偏序关系，这意味着对于 任意x,y∈A，当x≠y时，x≤y和y≤x至多一个成立。
(3) 画出关系图
6
偏序关系的关系图特点：
(1) 每个结点都有环
(2) 两个不同结点之间要么有且仅有一条边相连，要么没有 边相连 偏序关系的关系图：不能直观地反映出元素之间的次序，所以 下面介绍另外一种图---哈斯图(Hasse图)。通过这个图，就能够 清晰地反映出元素间的层次。下面介绍Hasse图。 哈斯图(Hasse图) (1). 用小圆圈或点表示A中的元素，省掉关系图中所有 的自环。 (2).如果x≤y,且x≠y，则结点x要画在结点y的下方。 (3). 如果x≤y,且在集A中不存在任何z∈A,使得z介于x 与y之间，则 x与y之间用一条直线连接。
小结：(A,≤)是偏序集，B是A的非空子集，则 ⑴B的极小(大)元总是存在的，就是子集中处在最下(上) 层的元素是极小(大)元。 ⑵如果有唯一的极小(大)元，则这个极小(大)元就是最 小(大)元。否则就没有最小(大)元。
15
3.上界与下界 (Upper Bound and Lower Bound)
Φ
。
<D,≤>
<P(A), >
10
偏序集中的特殊元素
一.极小元与极大元 设集合A上有一个偏序关系≤且设B是 A的子集，则 (1）如果存在一个元素b∈B且在B中找不到元素b’有b’ ≠b且b ≤ b’ 则称b是B的极小元 .） （在B中没有比b更小的元素了，b就是极小元） （2）如果存在一个元素b∈B且中找不到元素b’有b’ ≠b且 b’ ≤ b ，则称b是B的极大元 . (在B中没有比b更大的元素了，b就是极大元)
9
课堂小测验：
(1) D={1,2,3,5,6,10,15,30},≤ 是D上整除关系， 求<D, ≤ >Hasse图， （2）A={a,b,c} ，求<P(A),>的Hasse图
30 6
。
{a,b}
{a,b,c}
。
。 １5。 3。 2。 5。 １。
１0
。
。 {a,c}。 {b,c}。 {b}。 {a}。 {c}。
(1)设<A，≤>是偏序集，BA，若存在a∈A，使得 对 b∈B，b≤a,称a为B的上界。
（上界a是A中元素，该元素比B中所有元素都大) (2) 设<A，≤>是偏序集，BA，若存在a∈A，使得
对 b∈B，a≤b,称a为B的下界。 （下界a是A中元素，该元素比B中所有元素都小) 举例，给定<C,≤>的Hasse图如图所示： 24。 36。 从Hasse图找上(下)界：注意是在A中找！ 12。
14
定理2：<A,≤>是偏序集，B是A的非空子集，如果B有 最小元(最大元)，则最小元(最大元)是唯一的。 证明：假设B有两个最小元x、y,则 因为x是最小元，y∈B，根据最小元定义，有x≤y; 类似地，因为y是最小元，x∈B，根据最小元定义，有 y≤x。因为≤有反对称性，所以有x=y。 同理可证最大元的唯一性。
5
例7.3.5 考虑任务集T，它包含了拍摄一张室内开启闪光 灯的照片必须按顺序完成的任务。
1. 打开镜头盖 2. 照相机调焦 3. 开启闪光灯 4. 按下快门按钮 在T上定义关系R如下： i, j R 如果i j或者任务i必须在任务j之前完成 试判断R是否是T上的偏序关系并画出它的关系图。 解：(1)列出R中的元素 (2) 判断是否满足属性
11
举例给定<C,≤>,Hasse图如图所示： 从Hasse图找极小(大)元：子集中处在最下(上)层 的元素是极小(大)元。
24
子集B
极小元
极大元
{2,3} {1,2,3} {6,12,24} C
2, 3 1 6 1
2, 3 2, 3 24 24,36
。 ６。 ２。 ３。 １。
12
。
36
。
12
定理 1：设 <A， ≤ >是偏序集， B 是 A 的非空有限子集， 则B一定存在极大（小）元。