任何人都知道簡化布爾表達式的算法嗎？簡化布爾表達式算法
我記得布爾代數和Karnaught地圖，但是這是爲數字硬件，其中EVERITHING是布爾值。我想要考慮到某些子表達式不是布爾值。
例如：
a == 1 && a == 3
這可以轉換爲純布爾表達式：
a1 && a3
但這是表達是不可約的，而具有算術的知識的一點點everibody可以確定該表達式就是：
false
一些機構知道s ome鏈接？使用谷歌
第一槍發現本文：
http://hopper.unco.edu/KARNAUGH/Algorithm.html
當然，這並不與非布爾子表達式處理。但是後一部分的一般形式確實很難，因爲肯定沒有算法來檢查任意的算術表達式是真的，假的還是其他的。你所要求的是深入到compiler optimization的領域。
我以前正在閱讀這篇論文，但是我也發現它很無細節，沒有提供任何代碼。 – Olmo 2011-03-15 23:53:29
您可能感興趣的K-maps和Quine–McCluskey algorithm。
我覺得SymPy能夠解決和簡化布爾表達式，查看源可能是有用的。
可能的不同值的數量是否有限且已知？如果是這樣，你可以將每個表達式轉換爲布爾表達式。例如，如果a有3個不同的值，那麼你可以有變量a1,a2和a3，其中a1爲真意味着a == 1等等。一旦你這樣做了，你可以依靠Quine-McCluskey算法（這對於更大的例子來說可能更好比卡諾地圖）。以下是Quine-McCluskey的Java code。
我無法在這個設計是否會真正簡化問題或使其更加複雜說話，但你可能要至少考慮一下。
究竟！，這就是我的意思，但是就像這樣，算法將不知道，在我的例子中，a1 && a3實際上是錯誤的。因爲a不能同時爲1和3。我認爲我需要的是將數值綁定到變量上，並發現卡爾諾指數中的矛盾。 – Olmo 2011-03-15 23:48:39
你的特別的例子就是由SMT solver來解決。 （它會確定沒有變量的設置可以使表達真實的，因此它總是假的更一般的簡化是超出範圍對於這樣求解。）顯示一個表達式相當於true或false當然是NP-即使沒有將算術帶入交易也很困難，所以即使有這麼多實用軟件也很酷。取決於範圍內有多少算術知識，問題may be undecidable。
這個問題有兩個部分，邏輯簡化和表示簡化。
爲了邏輯簡化，Quine-McCluskey。爲了簡化表示，使用分佈標識遞歸地提取術語（012）。
我詳細的過程here。這隻給出了使用&和|的解釋，但可以修改它以包含所有布爾運算符。
這是很難的人。該算法以我找到的最簡單的方式匹配每個輸入組合的每個輸出組合。但這是基本的算法，並沒有解決每一個表達式。
如果所有的輸出（Q1，Q2，Q3，Q4）一樣與即輸入的組合則簡化的結果將是A.
如果沒有，你會嘗試另一個variabel /輸入依賴。
如果'a'在語言/運行時被聲明爲volatile變量/字段允許這些變量，並且值在另一個線程上的1和3之間波動？我並不是說這是一個很好的設計，但在軟件中，「永遠」和「從不」通常是相對的術語。 – 2011-03-15 11:35:29
這不是問題，實際使用的是LINQ Provider，實際值是查詢翻譯時的值。如果他們的查詢再次執行，簡化將再次運行，並帶有更新的值。 – Olmo 2011-03-15 11:44:09
這是不可能的。例如'a> 0和b> 0和n> 2和a^n + b^n = c^n'總是錯誤的，但並不容易證明。這意味着你被困在特別的簡化中，並且你的問題沒有清晰的答案（因爲它將取決於你可能會看到的表達的性質）。 – 2011-03-15 11:56:50