離散數(shù)學(xué)課件：6-4布爾表達(dá)式

1、（一）布爾表達(dá)式 設(shè)設(shè)是布爾代數(shù)，是布爾代數(shù)，布爾常元布爾常元：A中的元素；中的元素；布爾變?cè)紶栕冊(cè)阂裕阂訟為取值范圍的變?cè)?；為取值范圍的變?cè)?布爾表達(dá)式布爾表達(dá)式 (Boolean expressions ) ：(1)A中任何元素（即布爾常元）是布爾表達(dá)式；中任何元素（即布爾常元）是布爾表達(dá)式；(2)任何布爾變?cè)遣紶柋磉_(dá)式；任何布爾變?cè)遣紶柋磉_(dá)式；(3)若若e1, e2是布爾表達(dá)式，則是布爾表達(dá)式，則 (e1 e2), (e1 e2)都是布都是布爾表達(dá)式；爾表達(dá)式；(4)有且只有通過(guò)有且只有通過(guò)有限次有限次地運(yùn)用規(guī)則地運(yùn)用規(guī)則(2), (3)所構(gòu)造的符所構(gòu)造的符號(hào)串是布爾表達(dá)式號(hào)串

2、是布爾表達(dá)式.1,eF我們見(jiàn)過(guò)類(lèi)似的定義方式：命題演算的合式公式；謂詞演我們見(jiàn)過(guò)類(lèi)似的定義方式：命題演算的合式公式；謂詞演算的合式公式算的合式公式.設(shè)設(shè)是布爾代數(shù)，則是布爾代數(shù)，則(1)a, (1 x1) x2,1 x1,l含有兩個(gè)變?cè)袃蓚€(gè)變?cè)獂1, x2的布爾表達(dá)式；的布爾表達(dá)式；這里這里(2), (3), (4)式分別稱(chēng)為式分別稱(chēng)為都是布爾表達(dá)式，這里都是布爾表達(dá)式，這里x1, x2, x3是布爾變?cè)遣紶栕冊(cè)?四、布爾表達(dá)式四、布爾表達(dá)式123,xxx(2)(3)(4)l含有單個(gè)變?cè)袉蝹€(gè)變?cè)獂1的布爾表達(dá)式；的布爾表達(dá)式；l含有三個(gè)變?cè)腥齻€(gè)變?cè)獂1, x2, x3的布爾表達(dá)式

3、的布爾表達(dá)式.n元布爾表達(dá)式元布爾表達(dá)式布爾表達(dá)式的值布爾表達(dá)式的值：設(shè)：設(shè)是布爾代數(shù)，是布爾代數(shù)，n元元布爾表達(dá)式布爾表達(dá)式E(x1, x2, , xn)的值是指：將的值是指：將A中的布爾中的布爾常元作為變?cè)Ｔ鳛樽冊(cè)獂i的值來(lái)代替表達(dá)式中相應(yīng)的變?cè)闹祦?lái)代替表達(dá)式中相應(yīng)的變?cè)磳?duì)變?cè)x值），從而計(jì)算得出的表達(dá)式的值（即對(duì)變?cè)x值），從而計(jì)算得出的表達(dá)式的值.n元布爾表達(dá)式元布爾表達(dá)式：一個(gè)含：一個(gè)含n個(gè)相異變?cè)牟紶柋磉_(dá)個(gè)相異變?cè)牟紶柋磉_(dá)式，稱(chēng)為式，稱(chēng)為n元布爾表達(dá)式，記作元布爾表達(dá)式，記作E(x1, x2, , xn),其中其中x1, x2, , xn為布爾變?cè)獮椴紶栕冊(cè)?n元布爾

4、表達(dá)式元布爾表達(dá)式E(x1, x2, x3)=121223()()()xxxxxx設(shè)布爾代數(shù)設(shè)布爾代數(shù)上的一個(gè)三元上的一個(gè)三元布爾表達(dá)式為布爾表達(dá)式為當(dāng)賦值為當(dāng)賦值為x1=1, x2=0, x3=1時(shí)時(shí), 其值為：其值為：E(1,0,1)=(10)(10)(01)=1 1 0=0.布爾表達(dá)式的等價(jià)布爾表達(dá)式的等價(jià)布爾表達(dá)式的等價(jià)布爾表達(dá)式的等價(jià)：設(shè)：設(shè) E1(x1, x2, , xn)和和E2(x1, x2, , xn)是布爾代數(shù)是布爾代數(shù)上的兩個(gè)上的兩個(gè)n元布爾表達(dá)式，若對(duì)元布爾表達(dá)式，若對(duì)n個(gè)變?cè)娜我赓x值個(gè)變?cè)娜我赓x值xi=ai, ai A, i=1, 2, n均有均有E1(a1, a

5、2, , an)= E2(a1, a2, , an)則稱(chēng)布爾表達(dá)式則稱(chēng)布爾表達(dá)式E1, E2是等價(jià)的，記作：是等價(jià)的，記作：E1(x1, x2, , xn)=E2(x1, x2, , xn).F這類(lèi)似于定義這類(lèi)似于定義“命題公式的等價(jià)命題公式的等價(jià)”、“謂詞公式的等謂詞公式的等價(jià)價(jià)”.驗(yàn)證在布爾代數(shù)驗(yàn)證在布爾代數(shù)上的兩個(gè)上的兩個(gè)布爾表達(dá)式布爾表達(dá)式是等價(jià)的是等價(jià)的.E1(x1, x2, x3)=1213()()xxxxE2(x1, x2, x3)=123()xxx方法一方法一：對(duì)：對(duì)x1, x2, x3的的8組可能取值一一驗(yàn)證，比如：組可能取值一一驗(yàn)證，比如：E1(0, 0, 0)=0 0 =

6、0,(00)(00)E2(0, 0, 0)=0(00)=0 1=0.方法二方法二：直接由運(yùn)算規(guī)律驗(yàn)證：直接由運(yùn)算規(guī)律驗(yàn)證：E2(x1, x2, x3)=123()xxx1213()()xxxx=E1(x1, x2, x3).（二）布爾函數(shù) 設(shè)設(shè) E(x1, x2, , xn)是布爾代數(shù)是布爾代數(shù)上的上的一個(gè)一個(gè)n元布爾表達(dá)式，因?yàn)檫\(yùn)算元布爾表達(dá)式，因?yàn)檫\(yùn)算 , , 在在A上封閉，上封閉，任意有序任意有序n元組元組(ai A), 可以對(duì)應(yīng)著布爾可以對(duì)應(yīng)著布爾表達(dá)式表達(dá)式E(x1, x2, , xn)的一個(gè)值，這個(gè)值必屬于的一個(gè)值，這個(gè)值必屬于A.因此，因此，E(x1, x2, , xn)確定了一

7、個(gè)由確定了一個(gè)由An到到A的函數(shù)的函數(shù).布爾函數(shù)布爾函數(shù)： 設(shè)設(shè)是布爾代數(shù)，一個(gè)由是布爾代數(shù)，一個(gè)由An到到A的函數(shù)若能用的函數(shù)若能用上的一個(gè)上的一個(gè)n元布爾表元布爾表達(dá)式來(lái)表示，則稱(chēng)該函數(shù)為達(dá)式來(lái)表示，則稱(chēng)該函數(shù)為布爾函數(shù)布爾函數(shù).F一個(gè)由一個(gè)由An到到A的函數(shù)不一定能用的函數(shù)不一定能用上的上的一個(gè)布爾表達(dá)式來(lái)表示一個(gè)布爾表達(dá)式來(lái)表示.設(shè)設(shè)A=0, 1, 下面的表格表示了一個(gè)從下面的表格表示了一個(gè)從A3到到A的函數(shù)的函數(shù)f,問(wèn)該函數(shù)是否是布爾函數(shù)問(wèn)該函數(shù)是否是布爾函數(shù)? 解：解：因?yàn)橐驗(yàn)閒可以表示為布爾表達(dá)式：可以表示為布爾表達(dá)式：E1(x1, x2, x3)=123123123123()(

8、)()()xxxxxxxxxxxxx100001111x200110011x301010101 f 0010110112312123()()()xxxxxxxx所以所以f是布爾函數(shù)是布爾函數(shù).小項(xiàng)小項(xiàng)&大項(xiàng)大項(xiàng) 一個(gè)含有一個(gè)含有n個(gè)變?cè)獋€(gè)變?cè)獂1,x2, xn 的布爾表達(dá)式，的布爾表達(dá)式，如果它有形式如果它有形式( ) ( ) ( )其中其中()是是xi或或 中的任一個(gè)，則我們稱(chēng)這個(gè)布爾中的任一個(gè)，則我們稱(chēng)這個(gè)布爾表達(dá)式為表達(dá)式為小項(xiàng)小項(xiàng).ix 如果它有形式如果它有形式( ) ( ) ( )其中其中()是是xi或或 中的任一個(gè)，則我們稱(chēng)這個(gè)布爾中的任一個(gè)，則我們稱(chēng)這個(gè)布爾表達(dá)式為表達(dá)式

9、為大項(xiàng)大項(xiàng).ixF每個(gè)位置每個(gè)位置xi或或 必出現(xiàn)且僅出現(xiàn)一次必出現(xiàn)且僅出現(xiàn)一次.ix小項(xiàng)小項(xiàng)&大項(xiàng)大項(xiàng)小項(xiàng)小項(xiàng)二進(jìn)制二進(jìn)制下標(biāo)下標(biāo)十進(jìn)制十進(jìn)制下標(biāo)下標(biāo)m00m0m01m1m10m2m11m3xx12 12xx&兩個(gè)布爾變?cè)蓸?gòu)成兩個(gè)布爾變?cè)蓸?gòu)成22個(gè)小項(xiàng)和個(gè)小項(xiàng)和22個(gè)大項(xiàng)：個(gè)大項(xiàng)： xx12xx12大項(xiàng)大項(xiàng)二進(jìn)制二進(jìn)制下標(biāo)下標(biāo)十進(jìn)制十進(jìn)制下標(biāo)下標(biāo)M00M0M01M1M10M2M11M3xx12 1xx2xx12xx12&n個(gè)布爾變?cè)獋€(gè)布爾變?cè)獂1,x2, xn可構(gòu)成可構(gòu)成2n個(gè)?。ù螅╉?xiàng)個(gè)?。ù螅╉?xiàng). 析取范式析取范式&合取范式合取范式析取范式析取范式：形

10、如：形如m0 m1 mt的表達(dá)式稱(chēng)為的表達(dá)式稱(chēng)為析取范式析取范式；合取范式合取范式：形如：形如M0 M1 Mt的表達(dá)式稱(chēng)為的表達(dá)式稱(chēng)為合取范式合取范式.F簡(jiǎn)言之，簡(jiǎn)言之，l析取范式：小項(xiàng)之并；析取范式：小項(xiàng)之并；l合取范式：大項(xiàng)之交合取范式：大項(xiàng)之交.其中其中mi表示小項(xiàng)，表示小項(xiàng)，Mi表示大項(xiàng)，表示大項(xiàng)，i=1,2,t. 對(duì)于一個(gè)從對(duì)于一個(gè)從0,1n到到0,1的函數(shù)，先用那些的函數(shù)，先用那些使函數(shù)值為使函數(shù)值為1的有序的有序n元組分別構(gòu)造小項(xiàng)元組分別構(gòu)造小項(xiàng)定理一定理一：對(duì)于兩個(gè)元素的布爾代數(shù)：對(duì)于兩個(gè)元素的布爾代數(shù),任意一個(gè)從任意一個(gè)從0,1n到到0,1的函數(shù)都是布爾函數(shù)的函數(shù)都是布爾函數(shù)

11、.證明：證明：其中其中ix nxxx12,xi,若有序若有序n元組中的第元組中的第i個(gè)分量為個(gè)分量為1,若有序若有序n元組中的第元組中的第i個(gè)分量為個(gè)分量為0.ix ,然后，再由這些小項(xiàng)所構(gòu)成的析取范式，它就是給然后，再由這些小項(xiàng)所構(gòu)成的析取范式，它就是給定函數(shù)對(duì)應(yīng)的布爾表達(dá)式，從而該函數(shù)是布爾函數(shù)定函數(shù)對(duì)應(yīng)的布爾表達(dá)式，從而該函數(shù)是布爾函數(shù).定理一定理一：對(duì)于兩個(gè)元素的布爾代數(shù)：對(duì)于兩個(gè)元素的布爾代數(shù),任意一個(gè)從任意一個(gè)從0,1n到到0,1的函數(shù)都是布爾函數(shù)的函數(shù)都是布爾函數(shù).F注：當(dāng)然，也可用那些使函數(shù)值為注：當(dāng)然，也可用那些使函數(shù)值為0的有序的有序n元元組分別構(gòu)造大項(xiàng)組分別構(gòu)造大項(xiàng)其中其

12、中ix nxxx12,xi,若有序若有序n元組中的第元組中的第i個(gè)分量為個(gè)分量為0,若有序若有序n元組中的第元組中的第i個(gè)分量為個(gè)分量為1.ix ,由這些大項(xiàng)所構(gòu)成的合取范式，也是給定函數(shù)對(duì)應(yīng)由這些大項(xiàng)所構(gòu)成的合取范式，也是給定函數(shù)對(duì)應(yīng)的布爾表達(dá)式的布爾表達(dá)式.求由下表所給定的函數(shù)求由下表所給定的函數(shù)f(x1, x2,x3)的析取的析取范式、合取范式范式、合取范式.解：解：函數(shù)函數(shù)f(x1, x2,x3)的析取范式：的析取范式：f(x1, x2, x3)=xxxxxxxxx123123123()()()x100001111x200110011x301010101 f 10100001求由下表所

13、給定的函數(shù)求由下表所給定的函數(shù)f(x1, x2,x3)的析取的析取范式、合取范式范式、合取范式.解（續(xù)）：解（續(xù)）：函數(shù)函數(shù)f(x1, x2,x3)的合取范式：的合取范式：f(x1, x2, x3)=xxxxxxxxxxxxxxx123123123123123()()()()()x100001111x200110011x301010101 f 10100001一般布爾代數(shù)上的析（合）取范式一般布爾代數(shù)上的析（合）取范式 布爾代數(shù)布爾代數(shù)上的布爾表達(dá)式的析上的布爾表達(dá)式的析取范式、合取范式可以擴(kuò)充到一般的布爾代數(shù)上取范式、合取范式可以擴(kuò)充到一般的布爾代數(shù)上.若若E(x1,x2, xn)能表示成能

14、表示成(a0 m0) (a1 m1) (at mt)(1)則稱(chēng)形如則稱(chēng)形如(1)式的布爾表達(dá)式為式的布爾表達(dá)式為析取范式析取范式；若若E(x1,x2, xn)能表示成能表示成(a0 M0) (a1 M1) (at Mt)(2)則稱(chēng)形如則稱(chēng)形如(2)式的布爾表達(dá)式為式的布爾表達(dá)式為合取范式合取范式. 設(shè)設(shè)E(x1,x2, xn)是布爾代數(shù)是布爾代數(shù)上任上任一布爾表達(dá)式，一布爾表達(dá)式，其中其中ai表示布爾常元，表示布爾常元， mi表示小項(xiàng)，表示小項(xiàng)，Mi表示大項(xiàng)，表示大項(xiàng)，i=1,2,t.定理二定理二：設(shè)：設(shè)E(x1,x2, xn)是布爾代數(shù)是布爾代數(shù)上上任一布爾表達(dá)式，則它一定可化為析（合）取范

15、式任一布爾表達(dá)式，則它一定可化為析（合）取范式.F作為布爾代數(shù)的直接應(yīng)用，作為布爾代數(shù)的直接應(yīng)用，l命題邏輯可用布爾代數(shù)命題邏輯可用布爾代數(shù)來(lái)描述來(lái)描述. 一個(gè)原子命題可視為一個(gè)布爾變?cè)?，其值非一個(gè)原子命題可視為一個(gè)布爾變?cè)渲捣荰即即F. 因此，因此，任一復(fù)合命題都能用布爾代數(shù)任一復(fù)合命題都能用布爾代數(shù)上的一個(gè)布爾函數(shù)來(lái)表示上的一個(gè)布爾函數(shù)來(lái)表示.證明略證明略.l開(kāi)關(guān)代數(shù)可用布爾代數(shù)開(kāi)關(guān)代數(shù)可用布爾代數(shù)來(lái)描述來(lái)描述. 一個(gè)開(kāi)關(guān)可視為一個(gè)布爾變?cè)?，其值非一個(gè)開(kāi)關(guān)可視為一個(gè)布爾變?cè)渲捣菙嚅_(kāi)斷開(kāi)即即閉合閉合. 因因此，任一開(kāi)關(guān)線路都能用布爾代數(shù)此，任一開(kāi)關(guān)線路都能用布爾代數(shù)上的一個(gè)布爾函數(shù)來(lái)

16、表示上的一個(gè)布爾函數(shù)來(lái)表示.將布爾代數(shù)將布爾代數(shù)上的布爾表達(dá)式上的布爾表達(dá)式E(x1, x2, x3)=(x1 x2) x3化為合取范式化為合取范式.解法一：解法一：E(x1, x2, x3)=(x1 x2) x3=(x1 x3) (x2 x3)123123123()()()xxxxxxxxx 12231123()()xxxxxxxx=M0 M2 M4將布爾代數(shù)將布爾代數(shù)上的布爾表達(dá)式上的布爾表達(dá)式E(x1, x2, x3)=(x1 x2) x3化為合取范式化為合取范式.解法二：解法二：先寫(xiě)出先寫(xiě)出E(x1, x2, x3)對(duì)應(yīng)的函數(shù)表：對(duì)應(yīng)的函數(shù)表：x100001111x200110011x301010101 E 01010111由上表可得，由上表可得，E(x1, x2,x3)的合取范式為的合取范式為E(x1, x2, x3)123123123()()()xxxxxxxxx 設(shè)設(shè)是布爾代數(shù)是布爾代數(shù)上的一個(gè)布爾表達(dá)式，上的一個(gè)布爾表達(dá)式，試寫(xiě)出試寫(xiě)出E(x1,x2, x3)的析取范式和的析取范式和合取范式合取范式.123122323(,)()(