第二单元 关系的闭包运算及偏序关系.pptVIP

例：整数集 Z上的“?”关系的自反闭包是“?”关系,对称闭包是“?”；传递闭包是它自身。 例：设有S={1,2,3},且有S上的关系R如下： R={(1,2),(1,3)} r(R)={(1,2),(1,3),(1,1),(2,2),(3,3)} s(R)={(1,2),(2,1),(1,3),(3,1)} t(R)={(1,2),(1,3)}=R 例：设有S={1,2,3}上的关系 R={(1,2),(2,3),(3,2),(3,3)} 试求 r(R),s(R)与t(R) 可用图示法： 2.5两种常用的关系 2.5.1次序关系 三种次序关系：偏序关系、 线性次序关系、 拟序关系。 ?偏序关系—满足自反性的次序关系,即满足自反性、反对称性及传递性。 ?拟序关系—满足反自反性的次序关系,即满足反自反性、反对称性及传递性。 ?线性次序关系—所有元素均能顺序排列的偏序关系。 第2章 关系 1.偏序 定义2.10：偏序关系：集合S上的关系R是自反的、反对称的又是传递的,则称R在S上是偏序的或称R是S上的偏序关系并可记以(S,R)。可用符号：“?”表示偏序。 例：集合S所组成的幂集?(S)上的关系：“?”是自反 的、反对称及传递的,故它是偏序的。它可记为：(?(S),?)。 第2章 关系 例：(Z,?)的哈斯图可见图2.11(a) 。 例：S={2,3,6,12,24,36}上的整除关系R的哈斯图可见图2.11(b)。 例：集合S={a,b,c}上的?(S)所组成的(?(S),?)的哈斯图可见图2.11(C)。 第2章 关系 第2章 关系 定义2.11：最大元素、最小元素、 极大元素、极小元素： 设有(X,?)且集合Y?X,有y?Y： (1)对每个y??Y都有y??y,则称y是Y的最大元素； (2)对每个y??Y都有y?y?,则称y是Y的最小元素； (3)不存在y??Y有y?y?且y?y?,则称y是Y的极大元素； (4)不存在y??Y有y?y?且y??y,则称y是Y的极小元素； 第2章 关系 例：图2.11(b)中(S,?)的几个重要元素： 最大元素：无 最小元素：无 极大元素：24,36 极小元素：2,3 例：(?(S),?)中?(S)的几个重要元素： 最大元素：{a,b,c} 最小元素：? 极大元素：{a,b,c} 极小元素：? 第2章 关系 定义2.12：上界、上确界、下界、下确界：设有(X,?)且集合Y?X,有x?X： (1)对每个y??Y均有y??x,则称x是Y的上界； (2)对每个y??Y均有x?y?,则称x是Y的下界； (3)x?X是Y的上界且对每个Y的上界x?均有x?x?,则称x是Y的上确界(即Y的最小上界)； (4)x?X是Y的下界且对每个Y的下界x?均有x??x,则称x是Y的下确界(即Y的最大下界) ； 第2章 关系 例：(?(S),?)中Y={{a,b},{b,c},{b},{c},?}， Y?={{ a },{c}}的所有8个重要元素： Y Y? 最大元素： 无 无 极大元素： {a,b},{b,c} {a},{C} 最小元素： ? 无 极小元素： ? {a},{C} 上界： {a,b,c} {a,c},{a,b,c} 上确界： {a,b,c} {a,c} 下界： ? ? 下确界： ? ? 第2章 关系 定理2.4：对集合X上的偏序关系?有Y?X有： (1)y是Y的最大(小)元素则它必为Y的极大(小)元素； (2)y是Y的最大(小)元素则它必为Y的上(下)界； (3)x是Y的上(下)确界,且x?Y,则x必为Y的最大 (小)元素。 设S={2,3,4,6,9,12,18},则S上的整除关系R为偏序关系，试求其子集R1={2,4}, R2={4,6,9}, R3={12,18}及R4=S的重要元素. 第2章 关系 2.线性次序 定义2.13：线性次序：设集合S上有偏序关系R,如对 x,y?S必有x?y或y?x则称R是线性次序的(也可叫全序 的)或称R上集合S上的线性次序关系。