离散数学(二)布尔代数部分离散数学(二)布尔代数部分.pdfVIP

离散数学(二)第十一讲 计算机学院: 焦晓鹏 布尔代数 主要内容: 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← 定义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′,证明见下页. 一、布尔代数两个定义 例1 (1) B ,∧,∨, , 0, 1, |B |=20 1 1 (2) B ,∧,∨, , 0, 1, |B |=21 2 2 (3) B ,∧,∨, , 0, 1, |B |=22 4 4 n (4) S={a ,…,a }, |ρ(S)|=2 , ρ(S),∩, ∪ 为布尔代数. 1 n (5) X={A|A是由变元p ,p ,…,p , ﹁,∧,∨,→,↔构成的合式公 1 2 n n n 式集}。等价公式视为同一公式，最小项有2 个, X共2^(2 ) 个命题公式, X,∧,∨, ┒, F, T 为布尔