离散数学ch11.ppt

第十一章 格与布尔代数 主要内容 格的定义及性质 子格 分配格、有补格 布尔代数 11.1 格的定义与性质 定义11.1 设S, ?是偏序集，如果?x,y?S，{x,y}都有最小上 界和最大下界，则称S关于偏序?作成一个格. （偏序关系P126） 求{x,y} 最小上界和最大下界看成 x 与 y 的二元运算∨和∧， 格的性质：算律 定理11.1 设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 格的性质：序与运算的关系 定理11.3 设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. 格的性质：保序 定理11.4 设L是格, ?a,b,c,d∈L，若a ? b 且 c ? d, 则 a∧c ? b∧d, a∨c ? b∨d 格作为代数系统的定义 定理11.4 设S,?,?是具有两个二元运算的代数系统, 若对于 ?和?运算适合交换律、结合律、吸收律, 则可以适当定义S中 的偏序 ?,使得 S,? 构成格, 且?a,b∈S 有 a∧b = a?b, a∨b = a?b. 证明省略. 根据定理11.4, 可以给出格的另一个等价定义.? 11.2 分配格、有补格与布尔代数 定义11.5 设L,∧,∨是格, 若?a,b,c∈L,有 a∧(b∨c) = (a∧b)∨(a∧c)   a∨(b∧c) = (a∨b)∧(a∨c) 则称L为分配格. 注意：可以证明以上两个条件互为充分必要条件 有界格的定义 定义11.6 设L是格, (1) 若存在a∈L使得?x∈L有 a ? x, 则称a为L的全下界 (2) 若存在b∈L使得?x∈L有 x ? b, 则称b为L的全上界? 说明： 格L若存在全下界或全上界, 一定是惟一的. 一般将格L的全下界记为0, 全上界记为1. 定义11.7 设L是格,若L存在全下界和全上界, 则称L 为有界 格, 一般将有界格L记为L,∧,∨,0,1. 定理11.6 设L,∧,∨,0,1是有界格, 则?a∈L有a∧0 = 0, a∨0 = a, a∧1 = a, a∨1 = 1 有界格中的补元及实例 定义11.8 设L,∧,∨,0,1是有界格, a∈L, 若存在b∈L 使得 a∧b = 0 和 a∨b = 1 成立, 则称b是a的补元. 注意：若b是a的补元, 那么a也是b的补元. a和b互为补元. 解答 (1) L1中 a 与 c 互为补元, 其中 a 为全下界, c为全上界, b 没有 补元. (2) L2中 a 与 d 互为补元, 其中 a 为全下界, d 为全上界, b与 c 也互为补元. (3) L3中a 与 e 互为补元, 其中 a 为全下界, e 为全上界, b 的补 元是 c 和 d ; c 的补元是 b 和 d ; d 的补元是 b 和 c ; b, c, d 每个元素都有两个补元.? (4) L4中 a 与 e 互为补元, 其中 a 为全下界, e 为全上界, b 的补 元是 c 和 d ; c 的补元是 b ; d 的补元是 b . 有界分配格的补元惟一性 定理11.7 设L,∧,∨,0,1是有界分配格. 若L中元素 a 存在 补元, 则存在惟一的补元. 证 假设 c 是 a 的补元, 则有  a∨c = 1, a∧c = 0, 又知 b 是 a 的补元, 故   a∨b = 1, a∧b = 0  从而得到 a∨c = a∨b, a∧c = a∧b, 由于L是分配格. b=b ∧ (b∨a) = b ∧ (c∨a )= (b ∧ c)∨ (b ∧ a )= (a∨c ) ∧c=c