由集合B及其上定义的二元运算(布尔加)和(布尔乘)组.ppt

第五章 布尔 * * 定义5. 1 由集合B及其上定义的二元运算∨(布尔加)和∧(布尔乘)组成的代数系统，如果对B中任意元素a,b,c满足下列条件： (1)结合律： (a∨b)∨c＝a∨(b∨c) (a∧b)∧c＝a∧(b∧c) (2)交换律： a∨b＝b∨a a∧b＝b∧a (3)分配律：a∧(b∨c)＝(a∧b)∨(a∧c) a∨(b∧c)＝(a∨b)∧(a∨c)(4)在集合B中存在如下两个元素0(零元素)和1(单位元素)，具有如下性质： a∨0＝0∨a＝a a∧1＝1∧a＝a(5)互补律：对于B中任一元素a，存在相应的元素a’(称作a的补元素)，使得： a∨a’＝1 a∧a’＝0则称该代数系统为布尔代数。 布尔代数通常用序偶B,∨,∧,’,0,1来表示。其中’为一元求补运算。 这种表示并不意味着布尔代数至少有两个不同元素，当B只有一个元素0时，可以认为{0},∨,∧,’,0仍是布尔代数，这是称它为退化了的布尔代数。 定义5.2 具有有限个元素的布尔代数称为有限布尔代数。 定义5.3 设有布尔代数B,∨,∧,’,0,1，若A是B的子集，且A,∨,∧,’,0,1也是布尔代数，则称A,∨,∧,’,0,1为B,∨,∧,’,0,1的子布尔代数。 定理5.1 设B,∨,∧,’,0,1为布尔代数，若A?B且A含有元素0和1，并且对∨、∧、’运算封闭，那么A,∨,∧,’,0,1为B,∨,∧,’,0,1的子布尔代数。 下面介绍布尔代数的性质。 首先我们注意到布尔代数的定义中，表达各个运算律的等式都是成对出现的：如果把∨与∧互换，0与1互换，则每对等式中的一个就变成另一个。我们称这种对称的性质为对偶性，并称这种可以互相转换的公式为对偶公式。 例5.3 写出 a∧(b∨0)和(a’∧1)∨(0∨b)的对偶式。 定理5.2(对偶原理)在任一个由布尔代数定义中的基本性质所导出的等式中，同时交换∨与∧以及0与1所得到的式子也可以从相应的性质导出。 定理5.3 零元素是唯一的。 定理5.4 单位元1是唯一的。 定理5.5 元素a的补a’是唯一的。 定理5.6 对B中的任意元素a，有(a’)’＝a。 定理5.7 零元素与单位元素是互补的。 定理5.8 (等幂律) 对于B中每个元素a，有 a∨a＝a，a∧a＝a 定理5.9 对于B中每个元素a，有 a∨1＝1，a∧0＝0 定理5.10 (吸收律) 对于B中任意元素a,b，有 a∨(a∧b)＝a，a∧(a∨b)＝a 定理5.11 (德·摩根律) 对于B中任意元素a,b，有 (a∨b)’＝a’∧b’， (a∧b)’＝a’∨b’ *