布爾邏輯的代數表示及其應用研究

摘要：目前布爾邏輯已成為計算機科學的重要理論基礎之一，是研究人類思維規律的重要工具。文章提出了一種系統化的布爾邏輯的代數表示方法，其基本思想是把布爾集合用一組多項式來表示，在此基礎上定義完備的邏輯運算符集。文章對該方法在可滿足性問題(sAT)求解和測試模式自動生成(ATPG)中的應用進行了討論。關鍵詞：布爾邏輯；多項式；代數簇；可滿足性問題；測試模式自動生成。

引言

布爾邏輯自19世紀中期公開發表之時起就已逐步成為研究人類思維規律的重要工具，20世紀30年代以后廣泛應用于電路及芯片設計，目前布爾邏輯已成為計算機科學的重要理論基礎之一。

本文提出了一種布爾邏輯體系的系統化的代數表示方法，其基本思想是把布爾集合用一組實數域上的多項式的公共零點集合來表示。例如，多項式組(x，xl-1，x2-1)的公共零點實際上表示了集合(x=0，x1=l，x2=1)，這樣，一組多項式實際上提供了一種布爾集合的符號化表示方法。在此基礎上，我們定義完備的邏輯連接符號集，∧，∨從而給出了布爾邏輯的系統化代數表示方法。最后，給出了代數化的布爾邏輯表示在實際工程中的兩個應用：SAT和ATPG。