帶整數(shù)關(guān)系表達(dá)式的布爾表達(dá)式化簡(jiǎn)方法研究.pdf

1、布爾表達(dá)式化簡(jiǎn)是一個(gè)NP問題，求給定布爾表達(dá)式的最簡(jiǎn)等價(jià)式的系統(tǒng)性算法是一個(gè)仍待解決的問題。布爾表達(dá)式的化簡(jiǎn)在邏輯電路的優(yōu)化設(shè)計(jì)、開關(guān)代數(shù)及編碼設(shè)計(jì)中都有很多應(yīng)用。
　　 為了減少硬件設(shè)計(jì)中的輸入變量，縮短硬件實(shí)現(xiàn)過程中的時(shí)間延遲，現(xiàn)有的方法一般僅考慮對(duì)布爾表達(dá)式實(shí)行化簡(jiǎn)，目前尚沒有發(fā)現(xiàn)對(duì)帶有整數(shù)關(guān)系表達(dá)式的布爾表達(dá)式化簡(jiǎn)方面的研究。
　　 本文的工作以描述和尋找?guī)в姓麛?shù)關(guān)系表達(dá)式的布爾表達(dá)式的若干類可以化簡(jiǎn)的情形為出發(fā)

2、點(diǎn)，目標(biāo)是找到若干可以化簡(jiǎn)的類，將可以化簡(jiǎn)的情形加以描述并結(jié)合實(shí)例說明所給方法的正確性、可行性。
　　 本文工作的主要結(jié)果是：
　　 (1)含加減運(yùn)算的布爾表達(dá)式，根據(jù)關(guān)系運(yùn)算符“=，≠，≥，＞，≤，＜”進(jìn)行分類，實(shí)現(xiàn)了形如f=(R11∧R12∧…∧R1n)∨…∨(Rm1∧Rm2∧…∧Rmn)的表達(dá)式的化簡(jiǎn)，其中Rij表示Aij=Bij，Aij＞Bij，Aij≥Bij或Aij≠Bij且Aij和Bij代表整數(shù)表達(dá)式。

3、>　　 (2)含乘法運(yùn)算的帶有整數(shù)關(guān)系表達(dá)式的布爾表達(dá)式，利用關(guān)系運(yùn)算符分類后，根據(jù)表達(dá)式的形式能否化為范式形式展開進(jìn)一步討論，文中給出形如CiXi=±Xj±Cj和Xi*Xj＞Xi-Xj+1等若干可以化簡(jiǎn)的類。
　　 (3)含除法運(yùn)算的帶有整數(shù)關(guān)系表達(dá)式的布爾表達(dá)式，文中給出形如Ci/Cj=Ck/Ci、Xi＞Xj/和Ci/Xi≥Xi±1等若干可以化簡(jiǎn)的類。
　　 本文工作的結(jié)果雖然是初步的有待于進(jìn)一步研究，但我們相信它