帶整數關系表達式的布爾表達式化簡方法研究.pdf

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

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

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