第5章布爾代數(shù).ppt

1、第5章 布爾代數(shù),5.1 布爾代數(shù) 5.2 布爾表達式與布爾函數(shù),5.1 布爾代數(shù),5.1.1 布爾代數(shù)的基本概念 5.1.2 對偶原理 5.1.3 布爾代數(shù)的基本性質(zhì),5.1.1 布爾代數(shù)的基本概念,定義5. 1 由集合B及其上定義的二元運算(布爾加)和(布爾乘)組成的代數(shù)系統(tǒng)，如果對B中任意元素a,b,c滿足下列條件： (1)結(jié)合律: (ab)ca(bc), (ab)ca(bc) (2)交換律: abba, abba (3)分配律: a(bc)(ab)(ac), a(bc)(ab)(ac) (4)在集合B中存在如下兩個元素0(零元素)和1(單位元素)，具有如下性質(zhì)：a00aa, a11aa

2、 (5)互補律：對于B中任一元素a，存在對應(yīng)的元素a(稱作a的補元素)，使得：aa1, aa0 則稱該代數(shù)系統(tǒng)為布爾代數(shù)。,布爾代數(shù)通常用序偶來表示。其中為一元求補運算。 這種表示并不意味著布爾代數(shù)至少有兩個不同元素，當B只有一個元素0時，可以認為仍是布爾代數(shù)，這是稱它為退化了的布爾代數(shù)。 例5.1 設(shè)A是任意有限集合，則A的一切子集所組成的集合對于并、交、補運算構(gòu)成布爾代數(shù)，空集和A集合本身分別為它的零元素和單位元素。該布爾代數(shù)系統(tǒng)表示為。,定義5.2 具有有限個元素的布爾代數(shù)稱為有限布爾代數(shù)。 定義5.3 設(shè)有布爾代數(shù)，若A是B的子集，且也是布爾代數(shù)，則稱為的子布爾代數(shù)。 定理5.1 設(shè)為

3、布爾代數(shù)，若且A含有元素0和1，并且對、運算封閉，那么為的子布爾代數(shù)。 例5.2 對任意布爾代數(shù)恒有子布爾代數(shù)和，它們被稱為B的平凡子布爾代數(shù)。,5.1.2 對偶原理,對偶公式：把一個布爾表達式中和分別用和代換，0和1分別用1和0代換，得到的式子就是原式子的對偶公式。 例：寫出 a(b0)和(a1)(0b)的對偶公式。 定理5.2(對偶原理)在任一個由布爾代數(shù)定義中的基本性質(zhì)所導(dǎo)出的等式中，同時交換與以及0與1所得到的式子也可以從相應(yīng)的性質(zhì)導(dǎo)出。,5.1.3 布爾代數(shù)的基本性質(zhì),定理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 布爾表達式與布爾函數(shù),5.2.1 布爾表達式與布爾函數(shù) 5.2.2 布爾表達式的范式,5.2.1 布爾表達式與布爾函數(shù),定義5.4 設(shè)是布爾代數(shù)，如下遞歸定義B上布爾表達式：(1)布爾常元和布爾變元(取值于布爾代數(shù)B的常元和變元)是布爾表達式。通

5、常布爾常元用a,b,c表示，布爾變元用x,y,z表示。(2)如果e1, e2為布爾表達式，那么(e1), ( e1e2), ( e1e2)也都是布爾表達式。 (3)除有限次使用條款(1)(2)生成的表達式是布爾表達式外，沒有別的布爾表達式。 為了省略括號，我們約定運算的優(yōu)先級高于運算和，并約定表達式最外層括號省略。,例 設(shè)是一個布爾代數(shù)，那么0 x，(1x)y，(23)(xy)(xz)都是布爾表達式，并分別稱為含有一個變元、兩個變元、三個變元的布爾表達式。 常用f(x1, x2, xn), g(x1, x2, xm)等表示含有n個變元或m個變元的布爾表達式。 給定布爾表達式并確定其中變元的取值

6、后，該表達式對應(yīng)于一個確定的B中的元素，該元素就是布爾表達式的值. 定義5.5 布爾表達式f(x1, x2, xn)所定義的函數(shù)f：BnB 稱為布爾函數(shù).,例 設(shè)是一個布爾代數(shù)，其上有表達式 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 來表示它們。 極小項和極大項滿足以下性質(zhì)： (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. 構(gòu)成極小項或極大項缺少變元x時，用添加合取項(xx)或析取項(xx)來處理。 5. 計算合并常元、變元和表達式(只要可能，這一步驟可隨時進行)。,例 求布爾代數(shù)上的布爾函數(shù)： 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 ),例 求布爾代數(shù)上的布爾函數(shù)： 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 假設(shè)主析取范式為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)。 假設(shè)主合取范式為 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 ),布爾代數(shù)的不同的n元主析取范式和主合取范式分別是 個。這就表明，B上不同的n元布爾函數(shù)至多是 個。 因此并非所有的Bn到B的函數(shù)都是布爾函數(shù)，Bn到B的函數(shù)共有個 。 當主析取范式中ai(i=0,1,2n-1)均取0時，該式值為0，因此0的主析取范式常簡單的規(guī)定為0，它表示函數(shù)f(x1, x2, xn)=0。 同樣在主合取范式中ai(i=0,1,2n-1)均取1時，該式值為1，因此1的主合取范式常簡單的規(guī)定為1，它表示函數(shù)f(x1,x2,xn)=1

12、。,計算機中的電路就是根據(jù)布爾代數(shù)的規(guī)則來設(shè)計的。電路的基本元件是門，每種類型的門實現(xiàn)一種布爾運算。下圖所示是電路設(shè)計中的三種基本門：反相器，或門，與門 用反相器、或門和與門 可以構(gòu)造組合電路。如右 圖所示構(gòu)造了(xy)(xy) 的輸出電路。,例 對于下表中的函數(shù)f求其主析取范式和主合取范式,解： f: 0,12 0,1,f(0,0)=0,f(0,1)=1,f(1,0)=0,f(1,1)=1,假設(shè)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),假設(shè)f的主