文档介绍：第三讲安全策略与安全模型
一数学基础

a∈ A HS

2A =P(A) ={H A}

A×B={(a,b)| a∈A ,b ∈B}

设是A上的关系,a ∈A 均aa--------自反
设是A上的关系,a,b ∈A若ab,则ab与ba不能同时出现
--------反对称
设是A上的关系,a,b,c ∈A若ab, bc则一定有ac
---------可传递的
1
偏序关系:集合 A 上的关系ρ, 如果它是自反、反对称且
可传递的,则称ρ为 A 上的一个偏序关系。
“偏序关系”也叫做“偏序”,用“≤”符号表示。
可比:设≤是集合 A 上的偏序,对于 a、b∈A,若有 a ≤ b
或 b ≤ a,则称 a 和 b 是可比的,否则称 a 和 b 是不可比的
全序:一个集合 A 上的任意两个元素之间都满足偏序关系,
则称该偏序为 A 上的一个全序。
良序:一个集合 A 上的偏序,若对于 A 的每一个非空子集 S  A,
在 S 中存在一个元素 as(称为 S 的最小元素),使得对于
所有的 s ∈ S,有as ≤s,则称它为 A上的一个良序。

2
ab若存在a c,c b则a,b无边
由于偏序是反对称的,关系图上每两个节点之间,若要有边,只有一条边,一个方向。
例1: A={2,3,4,6,8,12,36,60} 上的整除关系ρ是
一个偏序,其关系图如图1:
可以用结点的上下位置代替边的方向,省略箭头,如图2
3
60
6
12
2
36
4
8
图 2
6
3
4
2
12
8
36
60
图 1
3
3
60
6
12
2
36
4
8
图 3
图 3 是偏序ρ的关系图的一种特殊形式。
它虽然省略了箭头和许多边,却仍然很明确地表示了
集合上所有元素间的整除关系,而且更加简单明了
把偏序的关系图中省略了箭头和间接方向的图称为次序图。
还把可以间接到达的路省略。于是得到图 3
3
60
6
12
2
36
4
8
图 2
6
3
4
2
12
8
36
60
图 1
4
注:⑴次序图是偏序关系的关系图的一种特殊表示形式。
它只能表示有限集合上的偏序关系。
⑵次序图用结点的上下位置表示元素之间的偏序关
系,所以在次序图不能有水平线
⑶次序图中,能间接到达的两个结点之间不要连一边,
因此,次序图中不能有三角形
5

命题:若<A;≤1>和<B;≤2>是两个偏序集,在笛卡尔积A×B上定义关系≤,对任意(a1,b1), (a2,b2) ∈A×B 当且仅当
a1≤1a2, b1≤2b2时,有(a1,b1) ≤(a2,b2)
可以证明:<A×B;≤>也是一个偏序集。
6
因为<A;≤1>、<B;≤2>为偏序关系,所以
a1 ∈A 有a 1≤1 a1, b1 ∈B 有b 1≤1 b1
所以(a1,b1) ≤(a1,b1) 自反
由(a1,b1) ≤(a2,b2) (a2,b2) ≤(a1,b1),可得
a1≤1a2, a2≤1a1 可得 a1=a2;同理有b1=b2,此即(a2,b2) =(a1,b1)
反对称
又由(a1,b1) ≤(a2,b2) (a2,b2) ≤(a3,b3),此即 a1≤1a2, a2≤1a3
可得 a1≤1a3
同理: b1≤2b2, b2≤2b3 可得 b1≤2b3
最后有(a1,b1) ≤(a3,b3) 传递性
7
亦即
(i)(a,b)∈A×B ,均有(a,b) ≤(a,b)
(ii)(a1,b1),(a2,b2),∈ A×B,若(a1,b1)(a2,b2), 则(a1,b1) ≤(a2,b2) 与(a2,b2) ≤(a1,b1) 不能同时出现
(iii)(a1,b1) ,(a1,b1) ,(a1,b1) ∈ A×B,若(a1,b1) ≤(a2,b2) , (a1,b1) ≤(a2,b2) 则一定有(a1,b1) ≤(a2,b2)
设是A上的关系,a ∈A 均aa --------自反
设是A上的关系,a,b ∈A若ab,则ab与ba不能同时出现
--------反对称
设是A上的关系,a,b,c ∈A若ab, bc则一定有ac
---------可传递的
8
如果有aρ b 且 bρ c成立,则有bβ a 且 cβ b 成立
由β的可传递性,有cβa 成立,因而 aρc 成立
∴ρ是可传递的
∴