基于分治的布爾可滿足性判定.pdf

1、SAT是最著名的NPC問題。NPC類問題有兩方面的特性，首先，這類問題的解可以在多項式時間復(fù)雜度內(nèi)得到驗證。其次，其它NP問題可以在多項式時間內(nèi)轉(zhuǎn)換為NPC問題來求解。因此，SAT判定技術(shù)的研究具有重要的理論意義。
　　SAT判定技術(shù)還具有很大的實用價值。它可以應(yīng)用到包括人工智能規(guī)劃、模型分析、定理證明、軟件驗證和軟件測試、軟件發(fā)布中的包管理等領(lǐng)域。在電子設(shè)計自動化中，SAT可用于電路的邏輯綜合、布爾匹配、電路等價性驗證、模型檢驗

2、、自動測試用例生成、FPGA的布局布線、設(shè)計調(diào)試與診斷等。
　　本文研究SAT判定問題，SAT判定問題的時間復(fù)雜度是指數(shù)階的，這意味著如果問題的規(guī)模較大時，要完成SAT判定會非常困難。
　　研究利用分治的思想，通過將復(fù)雜的SAT的判定問題劃分為多個規(guī)模更小的子問題來求解，在劃分代價較小的情況下，利用這一方法來降低可滿足性判定的復(fù)雜度。通過系統(tǒng)深入的理論分析和實驗研究，取得了如下創(chuàng)新性成果：
　　提出了CNF形式的布爾公

3、式的子句組劃分的概念，并證明了布爾公式的可滿足性問題可以轉(zhuǎn)化為子句組的可滿足性問題來求解。給出了一種從CNF公式產(chǎn)生子句組劃分，以及利用子句組劃分來進(jìn)行SAT判定的方法。對于不能直接產(chǎn)生子句組劃分的公式，提出利用聚類方法，將子句聚類成多個簇，把包含共同變量多的子句聚類到同一個簇，包含共同變量少的子句聚類到不同的簇，將不同簇之間的共同變量作為割變量，通過對每個簇單獨(dú)判定，必要時再判斷割變量的取值是否沖突來判定公式的可滿足性。
　　由

4、于傳統(tǒng)的聚類方法并不能很好地適應(yīng)CNF子句的聚類要求，因此本文針對CNF公式的特點，提出一種兩階段的聚類方法，先用基于連接的方法來產(chǎn)生初始聚類，在一定程上避免聚類的局部最優(yōu)性，然后再用基于簇間相似度進(jìn)行合并的方法來生成最終的聚類結(jié)果。算法的第一階段通過指定聚類結(jié)果簇與原始簇個數(shù)的比值來確定生成的簇的個數(shù)，第二階段則通過相似度閾值來確定何時終止聚類，因此無需指定最終生成的簇的個數(shù)。
　　在聚類完成之后，如果要消去所有簇之間的共同變量

5、，將所有的簇都劃分開，在某些情況下，由于公共變量太多，可能需要付出太大的代價。為解決這一問題，本文提出將聚類結(jié)果中的簇作為頂點，用簇間的公共變量來標(biāo)記邊，將聚類結(jié)果變換成一個無向圖，然后利用無向圖最小割的方法來尋找將簇劃分成兩組的最小割變量集，以產(chǎn)生子句組劃分。
　　在某些情況下，將問題變換為CNF公式，可能會導(dǎo)致一些結(jié)構(gòu)信息的丟失。針對組合電路的等價性驗證問題和AIG電路的特點，本文提出一種方法，直接在電路上通過電路的特點進(jìn)行推