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

1、第5章 布爾代數(shù),5.1 布爾代數(shù) 5.2 布爾表達(dá)式與布爾函數(shù),5.1 布爾代數(shù),5.1.1 布爾代數(shù)的基本概念 5.1.2 對(duì)偶原理 5.1.3 布爾代數(shù)的基本性質(zhì),5.1.1 布爾代數(shù)的基本概念,定義5. 1 由集合B及其上定義的二元運(yùn)算(布爾加)和(布爾乘)組成的代數(shù)系統(tǒng)，如果對(duì)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中存在如下兩個(gè)元素0(零元素)和1(單位元素)，具有如下性質(zhì)：a00aa, a11aa

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

3、布爾代數(shù)，若且A含有元素0和1，并且對(duì)、運(yùn)算封閉，那么為的子布爾代數(shù)。 例5.2 對(duì)任意布爾代數(shù)恒有子布爾代數(shù)和，它們被稱為B的平凡子布爾代數(shù)。,5.1.2 對(duì)偶原理,對(duì)偶公式：把一個(gè)布爾表達(dá)式中和分別用和代換，0和1分別用1和0代換，得到的式子就是原式子的對(duì)偶公式。 例：寫出 a(b0)和(a1)(0b)的對(duì)偶公式。 定理5.2(對(duì)偶原理)在任一個(gè)由布爾代數(shù)定義中的基本性質(zhì)所導(dǎo)出的等式中，同時(shí)交換與以及0與1所得到的式子也可以從相應(yīng)的性質(zhì)導(dǎo)出。,5.1.3 布爾代數(shù)的基本性質(zhì),定理5.3 零元素是唯一的。 定理5.4 單位元1是唯一的。 定理5.5 元素a的補(bǔ)a是唯一的。 定理5.6 對(duì)B中

4、的任意元素a，有(a)a。 定理5.7 零元素與單位元素是互補(bǔ)的。 定理5.8 (等冪律)對(duì)于B中元素a，有 aaa，aaa 定理5.9 對(duì)于B中每個(gè)元素a，有 a11，a00 定理5.10 (吸收律) 對(duì)于B中任意元素a,b，有 a(ab)a，a(ab)a 定理5.11 (德摩根律) 對(duì)于B中任意元素a,b，有 (ab)ab， (ab)ab,5.2 布爾表達(dá)式與布爾函數(shù),5.2.1 布爾表達(dá)式與布爾函數(shù) 5.2.2 布爾表達(dá)式的范式,5.2.1 布爾表達(dá)式與布爾函數(shù),定義5.4 設(shè)是布爾代數(shù)，如下遞歸定義B上布爾表達(dá)式：(1)布爾常元和布爾變?cè)?取值于布爾代數(shù)B的常元和變?cè)?是布爾表達(dá)式。通

5、常布爾常元用a,b,c表示，布爾變?cè)脁,y,z表示。(2)如果e1, e2為布爾表達(dá)式，那么(e1), ( e1e2), ( e1e2)也都是布爾表達(dá)式。 (3)除有限次使用條款(1)(2)生成的表達(dá)式是布爾表達(dá)式外，沒有別的布爾表達(dá)式。 為了省略括號(hào)，我們約定運(yùn)算的優(yōu)先級(jí)高于運(yùn)算和，并約定表達(dá)式最外層括號(hào)省略。,例 設(shè)是一個(gè)布爾代數(shù)，那么0 x，(1x)y，(23)(xy)(xz)都是布爾表達(dá)式，并分別稱為含有一個(gè)變?cè)?、兩個(gè)變?cè)?、三個(gè)變?cè)牟紶柋磉_(dá)式。 常用f(x1, x2, xn), g(x1, x2, xm)等表示含有n個(gè)變?cè)騧個(gè)變?cè)牟紶柋磉_(dá)式。 給定布爾表達(dá)式并確定其中變?cè)娜≈?/p>

6、后，該表達(dá)式對(duì)應(yīng)于一個(gè)確定的B中的元素，該元素就是布爾表達(dá)式的值. 定義5.5 布爾表達(dá)式f(x1, x2, xn)所定義的函數(shù)f：BnB 稱為布爾函數(shù).,例 設(shè)是一個(gè)布爾代數(shù)，其上有表達(dá)式 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都會(huì)得到矛盾。),5.2.2 布爾表達(dá)式的范式,定義5.6 布爾表達(dá)式 a1a2an 稱為n個(gè)變?cè)臉O小項(xiàng)，其中ai為變?cè)獂i或xi。 布爾表達(dá)式 a1a2an 稱

7、為n個(gè)變?cè)臉O大項(xiàng)，其中ai為變?cè)獂i或xi。 n個(gè)變?cè)臉O小項(xiàng)和極大項(xiàng)各有2n個(gè)，我們分別用 m0, m1, , m2n-1和M0, M1, , M2n-1 來表示它們。 極小項(xiàng)和極大項(xiàng)滿足以下性質(zhì)： (1) i=j時(shí)， mimj =0，MiMj =1 (2) m0m1m2n-1=1, M0M1M2n-1 =0,定義5.7 布爾表達(dá)式f(x1, x2, xn)的主析取范式和主合取范式分別指下列布爾表達(dá)式： 其中，ai為布爾常元，mi和Mi分別是極小項(xiàng)與極大項(xiàng)，且兩式對(duì)x1, x2, xn一切的取值均與f(x1, x2, xn)等值。,求主析取范式和主合取范式的方法： 1. 將布爾常元看作變?cè)?/p>

8、，做同樣處理。 2. 利用德摩根律將運(yùn)算符號(hào)深入到每個(gè)變?cè)?常元)上。 3. 利用分配律展開。 4. 構(gòu)成極小項(xiàng)或極大項(xiàng)缺少變?cè)獂時(shí)，用添加合取項(xiàng)(xx)或析取項(xiàng)(xx)來處理。 5. 計(jì)算合并常元、變?cè)捅磉_(dá)式(只要可能，這一步驟可隨時(shí)進(jìn)行)。,例 求布爾代數(shù)上的布爾函數(shù)： f(x1, x2)= ( (ax1)(bx1) )(x1x2)的主析取范式和主合取范式。 解法一：首先證明 a和b是互補(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是互補(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元主析取范式和主合取范式分別是 個(gè)。這就表明，B上不同的n元布爾函數(shù)至多是 個(gè)。 因此并非所有的Bn到B的函數(shù)都是布爾函數(shù)，Bn到B的函數(shù)共有個(gè) 。 當(dāng)主析取范式中ai(i=0,1,2n-1)均取0時(shí)，該式值為0，因此0的主析取范式常簡單的規(guī)定為0，它表示函數(shù)f(x1, x2, xn)=0。 同樣在主合取范式中ai(i=0,1,2n-1)均取1時(shí)，該式值為1，因此1的主合取范式常簡單的規(guī)定為1，它表示函數(shù)f(x1,x2,xn)=1

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