1、11.2 布爾表達式與布爾函數(shù),定義 設(shè)是布爾,代數(shù),如下遞歸定義B上布爾表達式,(1)布爾常元和布爾變元(取值于,布爾代數(shù)B的常元和變元)是布爾,表達式.通常布爾常元用a,b,c表示,布爾變元用x,y,z表示。,(2)如果e1, e2為布爾表達式，,那么(e1),( e1e2),( e1e2)也都是,布爾表達式。,(3)除有限次使用條款(1)(2)生成的,表達式是布爾表達式外，,沒有別的布爾表達式。,為了省略括號，我們約定運算的,優(yōu)先級高于運算和，,并約定表達是最外層括號省略。,例 設(shè)是一個,布爾代數(shù),那么,(23)(xy)(xz),一個變元布爾表達式,0 x,(1x)y,兩個變元布爾表達式

2、,三個變元布爾表達式,常用f(x1, x2, xn), g(x1, x2, xm),等表示含有n個變元或m個變元的,布爾表達式。,給定布爾表達式并確定其中變元,的取值后,該表達式對應(yīng)于一個確,定的B中的元素，,該元素就是布爾表達式的值。,定義 布爾表達式f(x1, x2, xn),所定義的函數(shù),稱為布爾函數(shù)。,例 設(shè)是一個,布爾代數(shù)，其上有表達式,f(x1, x2)=( x1a)x2,f(x1, x2, x3)=,( x1x2x3)(x1x2x3),則有：,f(1, b),=(1a)b,= ab=0,f(a, b,0)=(ab0)(ab0),=0(aa)=1,定義 布爾表達式 a1a2an,稱

3、為n個變元的極小項，其中ai為,變元xi或xi。,布爾表達式 a1a2an 稱為,n個變元的極大項，其中ai為變元,xi或xi。,n個變元極小項和極大項各有2n個,極小項,極大項,滿足以下性質(zhì)：,定義 布爾表達式f(x1, x2, xn),的主析取范式和主合取范式分別,指下列布爾表達式：,其中，ai為布爾常元，mi和Mi分別,是極小項與極大項，且兩式對,x1, x2, xn一切的取值均與,f(x1, x2, xn)等值。,求主析取范式和主合取范式方法,將布爾常元看作變元,做同樣處理,利用德摩根律將運算符號深入到,每個變元(常元)上。,利用分配律展開。,構(gòu)成極小項或極大項缺少變元x時,加合取項(

4、xx)或析取項(xx),處理,計算合并常元、變元和表達式,(只要可能，這一步驟可隨時進行),例,求布爾代數(shù),上的布爾函數(shù)：,f(x1, x2)= ( (ax1)(bx1) )(x1x2),的主析取范式和主合取范式。,解：,f(x1, x2)= ( (ax1)(bx1) )(x1x2),f(0, 0)= 0,f(1, 0)= a,f(1, 1)= a,f(0, 1)= a,主析取范式,主合取范式,另解,主析取范式為：,f(x1, x2)= ( (ax1)(bx1) )(x1x2),= ( (ax1)(x1x2) )( (bx1),(x1x2) ),= (ax1)(ax1x2),(bx1x1)(b

5、x1x2),= (ax1)(bx1x2),= ( (ax1)(x2x2 ) )(bx1x2),= (ax1x2)(ax1x2 ),(ax1x2),主合取范式為：,f(x1, x2)= ( (ax1)(bx1) )(x1x2),=( (ax1)(bx1 ) )(x1x2),= ( (ax1)b )( (ax1)x1 )(x1x2),= (ab )(bx1)(ax1 ),(x1x2),= a(ax1)(ax1 )(x1x2),(b=a),= a(x1x2),=(ax1x2)( ax1x2 ),( ax1x2)( ax1x2 ),(x1x2 ),= (x1x2 )( ax1x2 ),( ax1x2)

6、( ax1x2 ),從主析取范式和主合取范式定義,可看出，的不同的,n元主析取范式和主合取范式分別,是,個。,因在主析取范式和主合取范式中,各有|B|種取值可能。,表明,B上不同的n元布爾函數(shù)至多,是,個。,因此應(yīng)當注意并非所有的Bn到B的,函數(shù)都是布爾函數(shù)，,Bn到B的函數(shù)共有,個。,另一點值得注意的是，,當主析取范式中,均取0時，該式值為0。,故0的主析取范式常簡單規(guī)定為0,它表示函數(shù)f(x1, x2, xn)=0。,在主合析取范式中,均取1時，該式值為1。,故1的主析取范式常簡單規(guī)定為1,它表示函數(shù)f(x1, x2, xn)=1。,計算機或其他電子裝置是由許多,電路構(gòu)成的,而電路就是根據(jù)布爾,代數(shù)的規(guī)則來設(shè)計的。,電路的基本元件是所謂的門，,每種類型的門實現(xiàn)一種布爾