轉化與AND和OR的邏輯條件

我有一個複雜的條件下，隨着AND和OR，例如： (c1 OR c2) AND (c3 OR c4 OR c5)轉化與AND和OR的邏輯條件

這相當於：

(c1 AND c3) OR (c1 AND c4) OR (c1 AND c5) OR (c2 AND c3) OR (c2 AND c4) OR (c2 AND c5)

這條件可以是然後發生爆炸的條件的列表只包含AND：

c1 AND c3 
c1 AND c4 
c1 AND c5 
c2 AND c3 
c2 AND c4 
c2 AND c5

這是變換始終可能嗎？和什麼算法可以做到這一點？

條件被存儲在內存中的樹木，如：

OR 
/\ 
    AND c1 
/! \ 
c2 c3 c4

我認爲我們應該試圖「移動」或向上的樹，用分配律：

(a OR b) AND c = (a AND c) OR (b AND c)。

這是一個很好的方法嗎？

這可能只解決了存儲在列表NOT ONLY對，但也有1或3,4等數字通過AND組合。示例條件c1 AND c2 AND c3。不能簡化。 – 2013-02-19 12:06:39

查看Disjunctive normal form（或Conjunctive one）。但是它們不僅使用AND和OR而且使用NOT。

注意：如果我們只OR S和AND禁止入內（而不能使用任何其他布爾函數），那麼我們甚至不能表達任何布爾函數，因爲Post's functional completeness theorem（AND和OR都是調查真相保存並不構成基礎）。因此也許有一個公式，不能被轉換。

2013-02-19 12:04:57

這是使用NOT運算符。 – 2013-02-19 12:08:38

@Толя，謝謝，我錯過了不禁止。 – 2013-02-19 12:17:15

(a or b) and c在邏輯上等同於(a and c) or (b and c)。但是，在支持短路布爾表達式的語言中，我最終可能會將其寫爲c and (a or b)，理由是如果c爲假，則不需要評估(a or b)。

如果a或b是昂貴的函數調用而不是變量引用，則尤其如此。

2013-02-19 12:06:35 Vatine

回答