第六章幻灯片[精彩].pptVIP

欢迎进入 离散数学第六章格与布尔代数;第六章 格与布尔代数;目 录; 对于计算机科学来说，格与布尔代 数是两个重要的代数系统。; §6.1 格;一． 格的定义 1．偏序集合的一些概念 ①?若集合A上的二元关系R满足自反性、 反对称性、传递性，称〈A，R〉为偏序集合。 aRb记为a≤b, 它可用哈斯图表示。 ;(2)设〈A，≤〉是偏序集合，B是A的子集。 若? b∈B,b≤a,则a是子集B的上界。 ;例：; 设〈L，≤〉是偏序集合，若?a，b?L， 都有最大下界、最小上界; 则称〈L，≤〉是个格，且记glb(a,b)=a?b, lub(a,b)=a?b,并称它们为交和并。 ;一． 格的定义; n=24 Sn={1, 2, 3, 4, 6, 8, 12, 24} ;设S是任意集合，?(S)是幂集， 偏序集合 ?(S) , ?是个格，其中 ?A,B??(S), A*B=A∩B, A?B=A∪B. ;一． 格的定义;②因为S, ≤的交是S, ≥的并， S, ≤的并是S, ≥ 的交， 所以，关于格的一般性质的任意命题， 如用≥替换≤，用?替换?，用?替换?， 格的一般性质的任意命题仍成立，这称为格的对偶原理。 ;一． 格的定义;1) 自反性 a≤a 对偶: a≥a 2) 反对称性 a≤b ? b≤a ? a=b 对偶:a≥b ? b≥a ? a=b 3) 传递性 a≤b ? b≤c ? a≤c 对偶:a≥b ? b≥c ? a≥c ;一． 格的定义;一． 格的定义;3.???格的基本性质 7)??等幂律 a?a=a 对偶 a?a=a ;一． 格的定义;一． 格的定义;一． 格的定义;一． 格的定义;一． 格的定义;一． 格的定义;§ 6.1.2 格是代数系统 ;二. 格是代数系统;二. 格是代数系统;二. 格是代数系统;偏序集合的格、代数系统的格二者定义是等价的证明 1) 证明R是L上的偏序关系 自反性：?a?L 由等幂律a?a=a, ? aRa 反对称性：?a,b?L, 若aRb, bRa 则a?b=a,b?a=b ?a=a?b=b?a =b 交换律;传递性： ?a,b,c?L, 若 aRb,bRc 则a?b=a, b?c=b ? a?c=(a?b)?c = a?(b?c)= a?b=a ? aRc ;二. 格是代数系统;b) 设c 是a,b 的任一下界， 即c≤a, c≤b 因为c?(a?b)= (c?a)?b=c?b=c c≤a?b ?a?b 是a,b的最大下界。 ;二. 格是代数系统;?由1）2）3）知：L,≤是一个格。 ? 以后可根据需要， 随意使用这二种定义和记法。 ;三 子格、格同态; 则 {b,c,d}, ?,?不是{a,b,c,d}, ?,? 的子格 {b,d}, ?,?是{a,b,c,d}, ?,? 的子格 {a,d}, ?,?是{a,b,c,d}, ?,? 的子格 ;三 子格、格同态;三 子格、格同态; 〈S12，整除 〉 〈S12，小于等于 〉 f: S12 ? S12 ,f(x)=x 则f是保序的 即a≤b ? f(a)≤f(b) 但f不是同态的: f(3*2)=f(1)=1 f(3)?f(2)=2 ;三 子格、格同态;? 已知?a,b? A1, a≤b ? f(a)≤’f(b) 需证f是同构, 即证:f(a?b)= f(a)*f(b) 证明: 令 c= a?b 则 c≤a ? f(c)≤’f(a) c≤b ? f(c)≤’f(b) ? f(c)≤’f(a)*f(b) 令 f(a)*f(b)=f(d) 则 f(d)≤’f(a) ? d≤a f(d)≤’f(b) ? d≤b ? d≤a?b=c ? f(d) ≤’f(c