第5章布尔代数.ppt

1、第5章 布尔代数,5.1 布尔代数 5.2 布尔表达式与布尔函数,5.1 布尔代数,5.1.1 布尔代数的基本概念 5.1.2 对偶原理 5.1.3 布尔代数的基本性质,5.1.1 布尔代数的基本概念,定义5. 1 由集合B及其上定义的二元运算(布尔加)和(布尔乘)组成的代数系统，如果对B中任意元素a,b,c满足下列条件： (1)结合律: (ab)ca(bc), (ab)ca(bc) (2)交换律: abba, abba (3)分配律: a(bc)(ab)(ac), a(bc)(ab)(ac) (4)在集合B中存在如下两个元素0(零元素)和1(单位元素)，具有如下性质：a00aa, a11aa

2、 (5)互补律：对于B中任一元素a，存在对应的元素a(称作a的补元素)，使得：aa1, aa0 则称该代数系统为布尔代数。,布尔代数通常用序偶来表示。其中为一元求补运算。 这种表示并不意味着布尔代数至少有两个不同元素，当B只有一个元素0时，可以认为仍是布尔代数，这是称它为退化了的布尔代数。 例5.1 设A是任意有限集合，则A的一切子集所组成的集合对于并、交、补运算构成布尔代数，空集和A集合本身分别为它的零元素和单位元素。该布尔代数系统表示为。,定义5.2 具有有限个元素的布尔代数称为有限布尔代数。 定义5.3 设有布尔代数，若A是B的子集，且也是布尔代数，则称为的子布尔代数。 定理5.1 设为

3、布尔代数，若且A含有元素0和1，并且对、运算封闭，那么为的子布尔代数。 例5.2 对任意布尔代数恒有子布尔代数和，它们被称为B的平凡子布尔代数。,5.1.2 对偶原理,对偶公式：把一个布尔表达式中和分别用和代换，0和1分别用1和0代换，得到的式子就是原式子的对偶公式。 例：写出 a(b0)和(a1)(0b)的对偶公式。 定理5.2(对偶原理)在任一个由布尔代数定义中的基本性质所导出的等式中，同时交换与以及0与1所得到的式子也可以从相应的性质导出。,5.1.3 布尔代数的基本性质,定理5.3 零元素是唯一的。 定理5.4 单位元1是唯一的。 定理5.5 元素a的补a是唯一的。 定理5.6 对B中

4、的任意元素a，有(a)a。 定理5.7 零元素与单位元素是互补的。 定理5.8 (等幂律)对于B中元素a，有 aaa，aaa 定理5.9 对于B中每个元素a，有 a11，a00 定理5.10 (吸收律) 对于B中任意元素a,b，有 a(ab)a，a(ab)a 定理5.11 (德摩根律) 对于B中任意元素a,b，有 (ab)ab， (ab)ab,5.2 布尔表达式与布尔函数,5.2.1 布尔表达式与布尔函数 5.2.2 布尔表达式的范式,5.2.1 布尔表达式与布尔函数,定义5.4 设是布尔代数，如下递归定义B上布尔表达式：(1)布尔常元和布尔变元(取值于布尔代数B的常元和变元)是布尔表达式。通

5、常布尔常元用a,b,c表示，布尔变元用x,y,z表示。(2)如果e1, e2为布尔表达式，那么(e1), ( e1e2), ( e1e2)也都是布尔表达式。 (3)除有限次使用条款(1)(2)生成的表达式是布尔表达式外，没有别的布尔表达式。 为了省略括号，我们约定运算的优先级高于运算和，并约定表达式最外层括号省略。,例 设是一个布尔代数，那么0 x，(1x)y，(23)(xy)(xz)都是布尔表达式，并分别称为含有一个变元、两个变元、三个变元的布尔表达式。 常用f(x1, x2, xn), g(x1, x2, xm)等表示含有n个变元或m个变元的布尔表达式。 给定布尔表达式并确定其中变元的取值

6、后，该表达式对应于一个确定的B中的元素，该元素就是布尔表达式的值. 定义5.5 布尔表达式f(x1, x2, xn)所定义的函数f：BnB 称为布尔函数.,例 设是一个布尔代数，其上有表达式 f(x1, x2)=( x1a)x2f(x1, x2, x3) =( x1x2x3)(x1x2 x3)则有： f(1, b)=(1a)b= ab=0f(a, b,0)=(ab0)(ab 0) = 0(ab)=1 其中a=b.(否则a=0,1,a都会得到矛盾。),5.2.2 布尔表达式的范式,定义5.6 布尔表达式 a1a2an 称为n个变元的极小项，其中ai为变元xi或xi。 布尔表达式 a1a2an 称

7、为n个变元的极大项，其中ai为变元xi或xi。 n个变元的极小项和极大项各有2n个，我们分别用 m0, m1, , m2n-1和M0, M1, , M2n-1 来表示它们。 极小项和极大项满足以下性质： (1) i=j时， mimj =0，MiMj =1 (2) m0m1m2n-1=1, M0M1M2n-1 =0,定义5.7 布尔表达式f(x1, x2, xn)的主析取范式和主合取范式分别指下列布尔表达式： 其中，ai为布尔常元，mi和Mi分别是极小项与极大项，且两式对x1, x2, xn一切的取值均与f(x1, x2, xn)等值。,求主析取范式和主合取范式的方法： 1. 将布尔常元看作变元

8、，做同样处理。 2. 利用德摩根律将运算符号深入到每个变元(常元)上。 3. 利用分配律展开。 4. 构成极小项或极大项缺少变元x时，用添加合取项(xx)或析取项(xx)来处理。 5. 计算合并常元、变元和表达式(只要可能，这一步骤可随时进行)。,例 求布尔代数上的布尔函数： f(x1, x2)= ( (ax1)(bx1) )(x1x2)的主析取范式和主合取范式。 解法一：首先证明 a和b是互补元素。 主析取范式: f(x1, x2)=( (ax1) (bx1)(x1x2) = ( (ax1)(x1x2) )( (ax1)(x1x2) ) = (ax1)(ax1x2)(ax1x1)(ax1x2

9、) = (ax1)(ax1x2) = ( (ax1)(x2x2 ) )(ax1x2) = (ax1x2)(ax1x2 )(ax1x2) 主合取范式：f(x1, x2)=( (ax1)(bx1 ) )(x1x2) = ( (ax1)a )( (ax1)x1 )(x1x2) = a(ax1)(ax1 )(x1x2) = a(x1x2) =(ax1x2)( ax1x2 )( ax1x2)( ax1x2 )(x1x2 ) = (x1x2 )( ax1x2 )( ax1x2)( ax1x2 ),例 求布尔代数上的布尔函数： f(x1, x2)= ( (ax1)(bx1) )(x1x2)的主析取范式和主合

10、取范式。 解法二：首先证明 a和b是互补元素。 f(0,0)=0, f(0,1)=a, f(1,0)=a, f(1,1)=a 假设主析取范式为f(x1,x2)=(a0 x1x2)(a1x1x2 )(a2x1x2) (a3x1x2 ) 则f(0,0)= a3=0, f(0,1)= a2 =a, f(1,0)=a1 =a, f(1,1)=a0=a， 所以主析取范式为f(x1,x2)=(ax1x2)(ax1x2 )(ax1x2)。 假设主合取范式为 f(x1,x2)=(b0 x1x2)(b1x1x2)(b2x1x2) (b3x1x2 ) 则f(0,0)= b0=0, f(0,1)= b1 =a, f

11、(1,0)=b2 =a, f(1,1)=b3=a， 所以主合取范式为f(x1,x2) =(x1x2)(ax1x2)(ax1x2) (ax1x2 ),布尔代数的不同的n元主析取范式和主合取范式分别是 个。这就表明，B上不同的n元布尔函数至多是 个。 因此并非所有的Bn到B的函数都是布尔函数，Bn到B的函数共有个 。 当主析取范式中ai(i=0,1,2n-1)均取0时，该式值为0，因此0的主析取范式常简单的规定为0，它表示函数f(x1, x2, xn)=0。 同样在主合取范式中ai(i=0,1,2n-1)均取1时，该式值为1，因此1的主合取范式常简单的规定为1，它表示函数f(x1,x2,xn)=1

12、。,计算机中的电路就是根据布尔代数的规则来设计的。电路的基本元件是门，每种类型的门实现一种布尔运算。下图所示是电路设计中的三种基本门：反相器，或门，与门 用反相器、或门和与门 可以构造组合电路。如右 图所示构造了(xy)(xy) 的输出电路。,例 对于下表中的函数f求其主析取范式和主合取范式,解： f: 0,12 0,1,f(0,0)=0,f(0,1)=1,f(1,0)=0,f(1,1)=1,假设f的主析取范式为 f(x1,x2)= (a0 x1 x2)(a1x1x2) (a2x1x2)(a3x1x2) 则f(0,0)=a3=0, f(0,1)=a1=1, f(1,0)=a2=0, f(1,1)=a0=1 从而 主析取范式为 f(x1,x2)= (1x1 x2)(1x1x2),假设f的主