任何人都知道簡化布爾表達式的算法嗎?簡化布爾表達式算法
我記得布爾代數和Karnaught地圖,但是這是爲數字硬件,其中EVERITHING是布爾值。我想要考慮到某些子表達式不是布爾值。
例如:
a == 1 && a == 3
這可以轉換爲純布爾表達式:
a1 && a3
但這是表達是不可約的,而具有算術的知識的一點點everibody可以確定該表達式就是:
false
一些機構知道s ome鏈接?使用谷歌
任何人都知道簡化布爾表達式的算法嗎?簡化布爾表達式算法
我記得布爾代數和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