格与布尔代数.ppt

格与布尔代数
1
格的定义与性质
设<S, ≼>是偏序集，如果x,yS，{x,y}都有最小上
界和最大下界，则称S关于偏序≼作成一个格. （偏序关系P126）
求{x,y} 最小上界和最大下界看成 x 与 y 的二元运算∨和∧，
例1 设n是正整数，Sn是n的正因子的集合. D为整除关系，则
偏序集<Sn,D>构成格. x,y∈Sn，x∨y是lcm(x,y)，即x与y的
最小公倍数. x∧y是gcd(x,y)，即x与y的最大公约数.
2
图2
例2 判断下列偏序集是否构成格，并说明理由.(1) <P(B), >，其中P(B)是集合B的幂集.(2) <Z, ≤>，其中Z是整数集，≤为小于或等于关系.(3) 偏序集的哈斯图分别在下图给出.
实例
(1) 幂集格. x,y∈P(B)，x∨y就是x∪y，x∧y就是x∩y.
(2) 是格. x,y∈Z，x∨y = max(x,y)，x∧y = min(x,y)，
(3) 都不是格. 可以找到两个结点缺少最大下界或最小上界
3
格的性质：算律
设<L, ≼>是格, 则运算∨和∧适合交换律、结合律、
幂等律和吸收律, 即
(1) a,b∈L 有
a∨b = b∨a, a∧b = b∧a
(2) a,b,c∈L 有(a∨b)∨c = a∨(b∨c), (a∧b)∧c = a∧(b∧c)
(3) a∈L 有 a∨a = a, a∧a = a
(4) a,b∈L 有 a∨(a∧b) = a, a∧(a∨b) = a
4
格的性质：序与运算的关系
设L是格, 则a,b∈L有a ≼ b  a∧b = a  a∨b = b
可以用集合的例子来验证 幂集格
<P(B), >，其中P(B)是集合B的幂集.
幂集格. x,y∈P(B)，x∨y就是x∪y，x∧y就是x∩y.
5
格的性质：保序
设L是格, a,b,c,d∈L，若a ≼ b 且 c ≼ d, 则
a∧c ≼ b∧d, a∨c ≼ b∨d
例4 设L是格, 证明a,b,c∈L有
a∨(b∧c) ≼ (a∨b)∧(a∨c).
证 a∧c ≼ a ≼ b, a∧c ≼ c ≼ d
因此 a∧c ≼ b∧d. 同理可证 a∨c ≼ b∨d
证 由 a ≼ a, b∧c ≼ b 得 a∨(b∧c) ≼ a∨b
由 a ≼a, b∧c ≼ c 得 a∨(b∧c) ≼ a∨c从而得到a∨(b∧c) ≼ (a∨b)∧(a∨c) （注意最大下界）
注意：一般说来, 格中的∨和∧运算不满足分配律.
6
格作为代数系统的定义
设<S,∗,◦>是具有两个二元运算的代数系统, 若对于
∗和◦运算适合交换律、结合律、吸收律, 则可以适当定义S中
的偏序 ≼,使得 <S,≼> 构成格, 且a,b∈S 有
a∧b = a∗b, a∨b = a◦b.
证明省略. , 可以给出格的另一个等价定义.
设<S, ∗, ◦ >是代数系统, ∗和◦是二元运算, 如果
∗和◦满足交换律、结合律和吸收律, 则<S, ∗,◦>构成格.
7
分配格、有补格与布尔代数
设<L,∧,∨>是格, 若a,b,c∈L,有 a∧(b∨c) = (a∧b)∨(a∧c)
  a∨(b∧c) = (a∨b)∧(a∨c)
则称L为分配格.
注意：可以证明以上两个条件互为充分必要条件
L1 和 L2 是分配格, L3 和 L4不是分配格.
称 L3为钻石格, L4为五角格.
实例
8
有界格的定义
设L是格,
(1) 若存在a∈L使得x∈L有 a ≼ x, 则称a为L的全下界
(2) 若存在b∈L使得x∈L有 x ≼ b, 则称b为L的全上界 
说明：
格L若存在全下界或全上界, 一定是惟一的.
一般将格L的全下界记为0, 全上界记为1.
设L是格,若L存在全下界和全上界, 则称L 为有界
格, 一般将有界格L记为<L,∧,∨,0,1>.