离散数学第7章-格.ppt

* 2 6 1 12 练习 1． 设 L={1，2，3，4，6，12}，在L上定义 整除关系，构成偏序集L; ≤. （1） glb(6,4)= ; lub(2,3)= ； （2） 该偏序集的最小元素是 ; 最大元素是 . 12 6 4 3 2 1 3 4 1 10 （1） glb(6,9) = ; glb(8,12) = ； （2） glb(9,7) = ; lub(5,10) = . 12 2．设L={1，2，3，…，11，12}，在L上定义 整除关系，构成偏序集. 8 4 2 1 10 5 6 3 9 7 11 下面给出的三个次序图，其中哪些是格？在图 下方相应的括号内键入“Y”或“N”表示肯定或否定. ( ) ( ) ( ) N Y Y Y Y N N 4．对下图所给出的格判断以下子集是否能构成它的 子格，在相应的括号内键入“Y”或“N”来回答. （1）S1={e,c,b} ( ) （2）S2={d,b,a} ( ) （3）S3={c,d,b} ( ) （4）S4={c,d,a} ( ) e d c b a 定义7-7 设L； ， 是一个格，若对于任意的l1, l2, l3∈ L，有 则称 L ； ， 是分配格. 7．4 分配格和有补格 一、分配格 1．分配格的定义 d c b a e c d b a d b c a 例1 对任意的集合A，2A ；∪，∩是一个分配格. 因此 b∧(c∨d)≠（b∧c）∨（b∧d） 而 (b∧c)∨(b∧d） e b c d a 例2 ???????? b∧(c∨d) = b∧e = b = a∨a =a 不是分配格. 2． 分配格中运算特点 定理7-11 在格L；∨，∧中，如果交运算对并运算是可分配的，则并运算对交运算也是可分配的；如果并运算对交运算是可分配的，则交运算对并运算也是可分配的. 证明 设在格L； ， 中，对任意 l1, l2, l3 ∈L，有 例如 设 L ={1，2，4，16，32，64}, 定义在L上的整除关系≤与L构成一个链L;≤. 设L; ≤ 是一个偏序集，若对于任意的l1, l2 ∈L，或者l1 ≤ l2, 或者l2 ≤ l1 ,则称L; ≤是一个链. 64 32 16 4 2 1 例3 每一个链L; ≤都是一个分配格. 证明 （1）先证明L; ≤是一个格. 由链的定义，对于任意 l1, l2 ∈L，或者 l1 ≤ l2, 或者 l2 ≤ l1 . 若 l1≤ l2 ，则 glb(l1, l2 )=l1 , lub(l1, l2 )=l2 ; 所以 L; ≤ 是一个格，可将其表示为 L;∨,∧. 对任意 l1, l2 ∈ L， l1∨l2 =lub(l1, l2), l1 ∧ l2 =glb(l1, l2). 若 l2≤ l1 ，则 glb(l1, l2 )=l2 , lub(l1, l2 )=l1 . (2) 证明 L；∨，∧是一个分配格. 对任意 l1, l2, l3 ∈L, 必有 l2 ≤ l3 或者 l3 ≤ l2 ， 不妨设 l2 ≤ l3. 于是有 l1 ∧(l2 ∨ l3)= l1 ∧ l3 . 又因为 l1 ∧ l2 ≤ l1 ∧ l3 , 所以 ( l1 ∧l2) ∨( l1 ∧l3 ) = l1 ∧ l3 , 因此 l1 ∧(l2 ∨ l3)=( l1 ∧l2) ∨( l1 ∧l3 ) . 若 l3 ≤ l2 ，其证明方法类似，因此链L; ≤ 是一个 分配格. 3．分配格的性质 定理7-12 设 l1, l2, l3是分配格 L；∨, ∧ 中的任意三个元素， 那么 证明 (1)