文档详情

离散数学 第11讲 布尔代数.ppt

发布:2018-07-07约6.43千字共22页下载文档
文本预览下载声明
* 离散数学(二) 布尔代数 布尔代数两个定义 11 布尔同态 2 主要内容: 布尔代数的定义 重点: 重点和难点: 有限布尔代数的结构 3 有限布尔代数的结构 难点: 一、布尔代数两个定义 布尔代数的定义: 定义1 布尔代数:有界有补的分配格L,∧,∨, , 0, 1. 定义1′ B,*,⊕是代数系统, *和⊕是B上的二元运算,如果对任意的元素a,b,c∈B,满足下列4条,则称B,*,⊕为布尔代数: (1) 交换律 a*b=b*a 和 a⊕b=b⊕a (2) 分配律 a*(b⊕c)=(a*b)⊕(a*c)和 a⊕(b*c)=(a⊕b)*(a⊕c) (3) 全上(下)界 B中存在两个元素0和1, 对B中任意元素a,满足 a*1=a 和 a⊕0=a (4)补元存在性 对B中每一元素a都存在一元素a′,满足 a*a′=0 和 a⊕a′=1 一、布尔代数两个定义 定义1→定义1′, 显然。下面证明定义1←定义1′: (1) 交换律:运算*和⊕是可交换的 (2) 吸收律 :要证明 a*(a⊕b)=a 和 a⊕(a*b)=a a *(a⊕b)=(a⊕0)*(a⊕b)=a⊕(0*b)=a⊕0=a 同理可证 a⊕(a*b)=a 一、布尔代数两个定义 (3)结合律: 要证明 (a⊕b)⊕c=a⊕(b⊕c) (i)首先证明a*c=b*c, a*c=b*c,则a=b. a=a*1=a*(c⊕c)=(a*c)⊕(a*c)=(b*c)⊕(b*c)=b*(c⊕c)=b (ii)现证明[(a⊕b)⊕c]*a=[a⊕(b⊕c)]*a, [(a⊕b)⊕c]*a=[a⊕(b⊕c)]*a. [(a⊕b)⊕c]*a=[(a⊕b)*a]⊕(c*a)=a⊕(c*a)=a. [a⊕(b⊕c)]*a=a, 所以[(a⊕b)⊕c]*a=[a⊕(b⊕c)]*a. [(a⊕b)⊕c]*a=[(a⊕b)*a]⊕(c*a)=(a*a)⊕(b*a)⊕(c*a) =0⊕(b*a)⊕(c*a)=(b*a)⊕(c*a), [a⊕(b⊕c)]*a=(a*a)⊕(b*a)⊕(c*a)=(b*a)⊕(c*a). 所以, [(a⊕b)⊕c]*a=[a⊕(b⊕c)]*a. 一、布尔代数两个定义 例1 (1) B1,∧,∨, , 0, 1 (2) B2,∧,∨, , 0, 1 (3) B4,∧,∨, , 0, 1 (4) S={a1,…,an}, |ρ(S)|=2n, ρ(S),∩,∪为布尔代数. (5) X={A|A是由变元p1,p2,…,pn,﹁,∧,∨,→,?构成的合式公 式集}。等价公式视为同一公式,最小项有2n个, X共2^(2n) 个命题公式, X,∧,∨, ┒, F, T 为布尔代数. 结论: (1)每一正整数n∈N,一定存在2n个元素的布尔代数。 S={a1,…,an}, |ρ(S)|=2n, ρ(S),∩,∪, ˉ, ?, S; (2) 反之, 对于任一有限布尔代数L, 总存在自然数n∈N,使得|L|=2n (它的元素个数必为2的幂次)。 二、布尔同态 定义2 具有有限个元素的布尔代数称为有限布尔代数. 定义3 设A,*,⊕,′,0,1和B,∩,∪, - ,α,β是两个布尔代数。定义一个映射f:A→B,如果在f的作用下能够保持布尔代数的所有运算,且常数相对应,亦即对于任何a,b∈A有: f(a*b)=f (a)∩f(b) f(a⊕b)=f (a)∪f(b) f(a′)=f(a) f(0)=α f(1)=β 则称映射f:A→B是一个布尔同态。 三、有限布尔代数的结构 定义4 L, ≤(L,∧,∨)是格,有全下界0, a∈L,满足 (1) a≠0; (2) 不?b∈L使得0ba; 则称a为该布尔代数的一个原子。 定义5 设L, ≤
显示全部
相似文档