第十三章格与布尔代数介绍.ppt

同一律就是指运算含有单位元的性质，这里的1是* 运算的单位元,0是 ??运算的单位元。 可以证明这个定义与有补分配格的定义是等价的。 例13.11? 设S110={1,2,5,10,11,22,55,110}是110的正因子集合。令gcd,lcm分别表示求最大公约数和最小公倍数的运算。问S110,gcd,lcm是否构成布尔代数？为什么？ 例13.12 设B为任意集合,证明B的幂集格P(B),∩,∪,~, ????,B 构成布尔代数,称为集合代数。 解：只需验证gcd,lcm运算是否满足：交换律、分配律、 同一律和补元律。 解：只需验证∩,∪运算是否满足：交换律、分配律、 同一律和补元律。 二．布尔代数的子代数及实例 定义13.14 设B,∧,∨,‘,0,1是布尔代数,S是B的非空 子集,若0,1∈S,且S对∧,∨和‘运算都是封 闭的,则称S是B的子布尔代数。 例13.13 设B,∧,∨,＇,0,1是布尔代数,a,b∈B,且a ???b. 令 　　S={x|x∈B,且a ????x ????b}称S为B中的区间,可简记为[a,b]. 证明[a,b]是一个布尔代数。 证明: S为B的非空子集,且a,b分别为S的全上界和全下界. 对任意的x,y∈S,都有 a x∧y b 和 a x∨y b 这说明S关于∧和∨运算是封闭的.易见∧和∨运算在 S上适合交换律和分配律. 对任意的x∈S,都有 x∨a=x , x∧b=x ,满足同一律 对任意的x∈S,令 y=(a∨x ＇) ∧b a a∨x ＇ 　 , 　a b, 故　ａ 　(a∨x ’) ∧b　ｂ　 所以 y∈S, x∨y=x ∨( (a∨x ＇) ∧b) =x ∨ (a ∧b )∨(x ＇ ∧b) (分配律) =(x ∨x ＇ ) ∧ (x ∨ b) (分配律) =1 ∧ (x ∨ b) (补元律) = x ∨ b (交换律,同一律) =x ∨ a∨(x ＇ ∧b) (由a b) =x ∨(x ＇ ∧b) (由a x) = b (由x b) 下面证明y是x的补元 x ∧ y=x ∧( (a ∨ x ＇) ∧ b) =(x ∧ a)∨(x ∧x ＇) (分配律) =(x ∧ a) ∨ 0 (补元律) = a (由a x) =x ∧ (a ∨ x ＇) (由x b) = x ∧ a (同一律) 由定义S,∧,∨构成一布尔代数,其全下界为a,全上界为b, 对任意的x∈S, x关于这个全上界和全下界的补元是 (a∨x ＇) ∧b 当a=0且b=1时,这时S是B的子布尔代数. 但当a≠0或b≠1时, S不是B的子布尔代数. S满足补元律 例13.14 考虑110的正因子集合S110关于gcd,lcm运算构成 的布尔代数。 它有以下的子布尔代数： {1,110}{1,2,55,110}{1,5,22,110}{1,10,11,110}{1,2,5,10,11,22,55,110} 三．布尔代数的同态映射及实例 定义13.15 设B1,∧,∨, ＇ ,0,1和B2,∩,∪, -,θ,E 　　　　　是两个布尔代数。 这里的∩,∪, -泛指布尔代数B2中的求最大下界,最小 上界和补元的运算。θ和E分别是B2的全下界和全上界。 f: B1→B2.如果对于任意的a,b∈B1有 f(a∨b)=f(a)∪f(b) f(a∧b)=f(a)∩f(b) f(a ＇ )=-f(a) 则称f是布尔代数B1到B2的同态映射,简称布尔代数的同态。 　　类似于其它代数系统,也可以定义布尔代