布爾代數(shù),布爾代數(shù)是什么意思

布爾代數(shù),布爾代數(shù)是什么意思

布爾代數(shù)最初是作為對(duì)邏輯思維法則的研究出現(xiàn)的。英國(guó)哲學(xué)家George Boole于1847年的論文“邏輯之?dāng)?shù)學(xué)分析”及“思維法則之研究”中引入了布爾代數(shù)。本世紀(jì)30年代C.E. Shannon發(fā)表了“繼電器和開關(guān)電路的符號(hào)分析”一文，為布爾代數(shù)在工藝技術(shù)中的應(yīng)用開創(chuàng)了道路。50年代蘇聯(lián)科學(xué)家把布爾代數(shù)發(fā)展成為接點(diǎn)網(wǎng)絡(luò)實(shí)用中的通用理論，從而使布爾代數(shù)成為計(jì)算機(jī)科學(xué)中的重要基礎(chǔ)理論。

從邏輯上講，布爾代數(shù)是一個(gè)命題演算系統(tǒng);

從抽象代數(shù)觀點(diǎn)講，布爾代數(shù)是一個(gè)代數(shù)系統(tǒng);

從集合的觀點(diǎn)講，它是一個(gè)集合代數(shù);

從工程技術(shù)的觀點(diǎn)講，布爾代數(shù)是電路代數(shù)，電子線路的設(shè)計(jì)離不開它;

布爾代數(shù)的基本定義和性質(zhì)：

反演規(guī)則是反演律的推廣，運(yùn)用它可以簡(jiǎn)便地求出一個(gè)函數(shù)的反函數(shù)。

運(yùn)用反演規(guī)則時(shí)應(yīng)注意兩點(diǎn)：

①不能破壞原式的運(yùn)算順序——先算括號(hào)里的，然后按“先與后或”的原則運(yùn)算。

②不屬于單變量上的非號(hào)應(yīng)保留不變.

對(duì)偶原理:

在布爾代數(shù)中，若P是某個(gè)已經(jīng)得到證明的定理，將定理中的條件和結(jié)論(1) ⊕與⊙互換; (2) 0與1 互換則由此而得的新定理仍然成立.

布爾代數(shù)的原子表示:

推論 有限布爾代數(shù)的基數(shù)一定為2的冪次;

布爾表達(dá)式及其范式定理:

定義1 設(shè)< S，⊕，⊙，′，0，1>為布爾代數(shù)，則S中的元素稱為布爾常元; 取值于S中的變?cè)Q為布爾變量(Boole Variable)。

定義2 設(shè)< S，⊕，⊙，′，0，1>為布爾代數(shù)，x1，x2，…，xn為布爾變?cè)?，則由這n個(gè)布爾變?cè)a(chǎn)生的布爾表達(dá)式(Boole Expression)可遞歸定義如下:

1)S中的任何元素和變?cè)獮橐粋€(gè)布爾表達(dá)式;

2)若F和G都是布爾式，則F′，F(xiàn)⊕G，F(xiàn)⊙G也是布爾式;

3)只有有限次使用1)或2)構(gòu)造而成的符號(hào)串才是一個(gè)布爾式;

(a)為了簡(jiǎn)便起見，規(guī)定⊕的運(yùn)算優(yōu)先級(jí)低于⊙

(b) 任一n元布爾式都可定義為是一個(gè)從Sn到S的一個(gè)函數(shù);

(c)兩個(gè)布爾式相等:

布爾表達(dá)式f(x1，x2，…，xn)的值是將S中的元素作為xi（i=1，2，…，n）的值代入表達(dá)式以后計(jì)算出來(lái)的表達(dá)式的值;

若對(duì)n個(gè)布爾變?cè)娜我庵概?即給每個(gè)變?cè)∩蟂中的元素)，兩個(gè)布爾表達(dá)式的值均相等，則稱這兩個(gè)布爾表達(dá)式是相等或等價(jià)的。

2) 任何兩個(gè)不同小項(xiàng)的布爾積(⊙)為0，任何兩個(gè)不同大項(xiàng)的布爾和(⊕)為1; 所有不同小項(xiàng)的布爾和為1;所有不同大項(xiàng)的布爾積為0;

3) 大項(xiàng)(小項(xiàng))的補(bǔ)是一個(gè)小項(xiàng)(大項(xiàng));

定理(范式定理)在布爾代數(shù)< S，⊕，⊙，′，0，1>中每個(gè)n元布爾表達(dá)均可表示成:

f(x1，x2，…，xn)= ⊕k (ck⊙mk) 其中k=δ1δ2…δn

f(x1，x2，…，xn)= ⊙l (dl⊕Ml) 其中l(wèi)=σ1σ2…σn

其中ck= f(δ1，δ2，…，δn)，dl= f(σ1，σ2，…，σn)

定義5 在布爾代數(shù)< S，⊕，⊙，′，0，1>中，一個(gè)S上的n元函數(shù)，如果能表示成n元布爾表達(dá)式，則稱之為布爾函數(shù)。

特別地當(dāng)S={0，1}時(shí)，即二值布爾代數(shù)S上的n元布爾式均是布爾函數(shù)。其中二值布爾式的主析(合)取范式就是小(大)項(xiàng)的布爾和(積)。

如何求一個(gè)二值布爾式的主析取范式和主合取范式:

1)列表法

注：同一布爾式的主合取范式中大項(xiàng)的項(xiàng)數(shù)和主析取范式中小項(xiàng)的項(xiàng)數(shù)之和等于2n。

2) 布爾代數(shù)性質(zhì)法

注:若f的主析取范式為g，則f′的主析取范式就是2n個(gè)小項(xiàng)中不在g中出現(xiàn)的小項(xiàng)的布爾和h，且h′就是f的主合取范式;反之，若f的主合取范式為g，則f′的主合取范式就是2n個(gè)大項(xiàng)中不在g中出現(xiàn)的大項(xiàng)的布爾積h，且h′就是f的主析取范式;

布爾式的范式定理與布爾式的簡(jiǎn)化在電子線路中的應(yīng)用:

二值布爾代數(shù)可用于邏輯電路的設(shè)計(jì)。具有若干輸入和某種邏輯功能的組合線路可以用一個(gè)定義在電路代數(shù)上的電路函數(shù)表示，而一個(gè)電路函數(shù)則可以用二值布爾式來(lái)表示。但是，表示同一種邏輯功能的電路函數(shù)可以有許多種，那么用其中最簡(jiǎn)單的電路函數(shù)來(lái)設(shè)計(jì)組合線路，是一個(gè)經(jīng)濟(jì)、可靠、簡(jiǎn)便的方法。

另外，布爾代數(shù)的應(yīng)用極為廣泛，其中最明顯的是在計(jì)算機(jī)技術(shù)中分析、綜合、設(shè)計(jì)邏輯電路中的應(yīng)用。

我們將若干個(gè)開關(guān)的串聯(lián)與并聯(lián)構(gòu)成的電路稱為開關(guān)電路。整個(gè)開關(guān)電路從功能上可看作是一個(gè)開關(guān)，把電路接通記為1，把電路斷開記為0。

一個(gè)具有n個(gè)獨(dú)立開關(guān)組成的開關(guān)電路稱為n元開關(guān)電路，可以寫成一個(gè)二值n元布爾式。開關(guān)是一種具有一個(gè)輸入和一個(gè)輸出的器件。對(duì)于多輸入單輸出的情形則可以用邏輯門電路來(lái)實(shí)現(xiàn)。邏輯門電路可以用來(lái)作與、或、非等邏輯運(yùn)算，一個(gè)邏輯門的輸出可以用為另一個(gè)邏輯門的輸入。這樣得到的邏輯電路可以用一個(gè)布爾式表示。通過(guò)對(duì)邏輯電路所對(duì)應(yīng)的布爾式進(jìn)行化簡(jiǎn)，我們就能分析電路有功能，并簡(jiǎn)化電路，既降低成本又提高可靠性。