計(jì)算機(jī)問(wèn)題求解-布爾代數(shù)

1、計(jì)算機(jī)問(wèn)題求解-論題1-13-布爾代數(shù) 2022年2月16日問(wèn)題1：這個(gè)是布爾代數(shù)的定義，你有沒(méi)有一種熟悉的感覺(jué)?它和另一個(gè)定義有什么異同之處？你能想到什么？“這個(gè)”代數(shù)和格問(wèn)題2：顯然，這個(gè)代數(shù)一定是個(gè)格！那么：多出來(lái)的那些特性（有補(bǔ)、分配、恒等），有什么用呢？我們可以很容易的驗(yàn)證B3是布爾代數(shù)001111110011101010100000B3問(wèn)題3：從這個(gè)B3中，我們能否設(shè)計(jì)一個(gè)“類(lèi)似”的格？ 元素有哪些？偏序關(guān)系是什么？ meet和join分別是什么？ Bn有幾個(gè)元素？其實(shí)，布爾代數(shù)是一類(lèi)特別的格：1，我們可以從布爾代數(shù)和偏序集兩個(gè)角度共同定義一個(gè)“系統(tǒng)”2，布爾代數(shù)和有界有補(bǔ)分配格，

2、可以談及“同構(gòu)”請(qǐng)問(wèn)：二個(gè)系統(tǒng)，是如何同構(gòu)的？布爾代數(shù)的代表：Bn有界有補(bǔ)分配格的代表：n元素集合的冪集偏序格問(wèn)題4：有限有補(bǔ)分配格一定有2n個(gè)元素因?yàn)锽1，B2，B3，,Bn有2n個(gè)元素？其實(shí)，我們還可以這樣來(lái)觀察：1，這樣的格中，原子個(gè)數(shù)是n個(gè)2,，除0外，所有元素都可以表示為一個(gè)或者多個(gè)原子的join，所有由一個(gè)或者多個(gè)原子的join的結(jié)果都是格中元素。3，這樣的元素有2n-1個(gè)問(wèn)題5：我們?yōu)槭裁匆诩媳硎旧隙xsum-of-products form?顯然，任意的集合運(yùn)算表達(dá)式不外乎表達(dá)了1-8個(gè)區(qū)域的組合，均可以標(biāo)準(zhǔn)表達(dá)為“積”的“和”問(wèn)題6：視線轉(zhuǎn)到布爾代數(shù)中：任意的布爾代數(shù)運(yùn)算

3、表達(dá)式，是否都可以表達(dá)為某個(gè)”sum-of-products form”？這個(gè)定理為我們證明兩個(gè)邏輯（布爾）表達(dá)式的等價(jià)帶來(lái)了極大的便利！“復(fù)習(xí)”幾個(gè)概念：Literal？Fundamental product？Contained in?Contained in?布爾表達(dá)式的積和表達(dá)：1，如果該布爾表達(dá)式是一個(gè)基本積項(xiàng)；2，如果該布爾表達(dá)式是兩個(gè)或者多個(gè)基本積項(xiàng)的和任意積項(xiàng)都不包含于另外的積項(xiàng)中X求和E等價(jià)的積和表達(dá)式樣例：Finally：求解布爾表達(dá)式E的完全積和表達(dá)式Full sum-of-products form: 每個(gè)基本積項(xiàng)都包含了表達(dá)式中的所有變?cè)覀兺ㄟ^(guò)sum-of-produ

4、cts范式，尋找任意一個(gè)邏輯表達(dá)式的唯一的完全析取范式，在判定兩個(gè)表達(dá)式是否等價(jià)方面起到作用一個(gè)邏輯表達(dá)式由“簡(jiǎn)”到“繁”由“繁”到“簡(jiǎn)”？我們是否有方法，尋找任意一個(gè)邏輯表達(dá)式的最簡(jiǎn)單等價(jià)式(留白：什么叫最簡(jiǎn)單?),便于我們?cè)O(shè)計(jì)對(duì)應(yīng)的數(shù)字電路？回到舉重裁判的問(wèn)題xzy000011110011001101010101f(x,y,z)00010111相應(yīng)的邏輯表達(dá)式:(xyz) (xyz) (xyz) (xyz)問(wèn)題7:相應(yīng)的布爾代數(shù)表達(dá)式是什么？x yz+ xy z+ xyz+ xyz問(wèn)題8:相應(yīng)的最簡(jiǎn)布爾代數(shù)表達(dá)式是什么？ yz+xz+xy問(wèn)題7：有沒(méi)有科學(xué)辦法，從任意的一個(gè)布爾邏輯表達(dá)式出

5、發(fā)，得到和它等價(jià)的最簡(jiǎn)表達(dá)式？如何“化簡(jiǎn)”下列布爾代數(shù)表達(dá)式x yz+ xy z+ xyz+ xyz= x yz+ xyz+ xy z+ xyz+ xyz+ xyz = yz+xz+xy這個(gè)式子難道就是最簡(jiǎn)的嗎？什么是最簡(jiǎn)？如何去尋找（定義）最?。ㄆ鋵?shí)是極?。┑姆e和表達(dá)式？復(fù)習(xí)幾個(gè)概念：E is simpler than FE is minimal if there is no equivalent sum-of-products expression which is simpler than E.x yz+ xy z+ xyz+ xyz= yz+xz+xyMinimal的定義在數(shù)字邏輯電路

6、設(shè)計(jì)中，意味著什么？關(guān)于積項(xiàng)包含的再觀察“驚艷”的吸收率，必將降低文字?jǐn)?shù)甚至積項(xiàng)個(gè)數(shù)什么是prime implicant？Let E = xyz + xz + xyz + xyz + xyzxy、xy甚至x和xyz都分別包含于E中某個(gè)基本積項(xiàng)但是，它們是E的蘊(yùn)含項(xiàng)嗎？xy、xy、x、xyzXX它是Prime的嗎？什么是prime implicant？Theorem 15.9: A minimal sum-of-products form for a Boolean expression E is a sum of prime implicants of E.這個(gè)素蘊(yùn)含項(xiàng)概念的引入，對(duì)簡(jiǎn)化邏輯表

7、達(dá)式有何幫助？接下來(lái)的問(wèn)題是：如何找到E的素(蘊(yùn)含)項(xiàng)Let E = xyz + xz + xyz首先：設(shè)計(jì)的基本項(xiàng)P必須保證 P+E=E觀察 E=xyz+xyz=xy(z+z)=xy另外一個(gè)角度： E=xyz+xyz =xyz+xyz + xy =xyz+xy+xyz+xy=xy+xy=xy觀察 E=xz+yzHow about: xz+yz+xy?xz+yz+xy=xz+yz+xy(z+z)=xz+yz+xyz+xyz =xz+xyz+yz+xyz=xz+yz這兩個(gè)xy是如何被“構(gòu)造”出來(lái)的？接下來(lái)的問(wèn)題是：如何找到E的素(蘊(yùn)含)項(xiàng)一點(diǎn)突兀和當(dāng)然： Consensus of Fundame

8、ntal Products接下來(lái)的問(wèn)題是：如何找到E的素(蘊(yùn)含)項(xiàng)你能在這個(gè)式子中找到某兩個(gè)基本積的Consensus 嗎？E = xyz + xz + xyz + xyz + xyz共識(shí)項(xiàng)方法求素項(xiàng)和當(dāng)我們運(yùn)氣足夠好，總是能夠找到“更短”的兩個(gè)或多個(gè)基本積項(xiàng)的共識(shí)項(xiàng)時(shí)，我們就可以簡(jiǎn)化(縮短)一個(gè)邏輯表達(dá)式問(wèn)題9：你能說(shuō)說(shuō)看，下例中尋找素項(xiàng)和的每一步的理論依據(jù)嗎？顯然，E有兩個(gè)等價(jià)的素項(xiàng)表達(dá)，并且不是相同simple怎么辦？這一步的結(jié)果是唯一的嗎？如何高效識(shí)別？消除冗余！再回到舉重裁判的問(wèn)題xzy000011110011001101010101f(x,y,z)00010111相應(yīng)的邏輯表達(dá)式:(xyz) (xyz) (xyz) (xyz)問(wèn)題7:相應(yīng)的布爾代數(shù)表達(dá)式是什么？x yz+ xy z+ xyz+ xyz問(wèn)題8:相應(yīng)的最簡(jiǎn)布爾代數(shù)表達(dá)式是什么？ yz+xz+xy我們?yōu)槭裁茨軌颉袄碇睔鈮选钡氐玫絾?wèn)題7,8的結(jié)論？Logic circuits form a Boolean Algebra！針對(duì)一個(gè)具體（邏輯）電路設(shè)計(jì)需求，我們得到一個(gè)滿足需求的邏輯表達(dá)式，利用布爾代數(shù)的基本理論（定義定理算法等），轉(zhuǎn)換成相應(yīng)的布爾代數(shù)表達(dá)式，尋找其最簡(jiǎn)形式，利用與或非門(mén)，設(shè)計(jì)出一個(gè)邏輯電路Open Topic以三元