Q

將布爾邏輯電路轉換爲布爾公式的基本算法是什麼？複雜度是多少？

2016-09-21 32 views -1 likes

-1

正如我在想，電路和公式（表達式）應該是同一個布爾值的兩種不同的表示形式，而大O應該只是n。但有人說他們不是一一對應的，爲什麼？將布爾邏輯電路轉換爲布爾公式的基本算法是什麼？複雜度是多少？

2016-09-21 ZHOU YANG

A

回答

2

布爾電路基於任意的非循環圖，而布爾公式可以寫爲樹。所以一個布爾電路可以評估一次子電路，並在多個地方進一步使用這個結果，而如果你試圖以一種明顯的方式把它寫成單個公式，那麼你會得到同樣的子樹的副本在多個地方，這可以按指數規律擴大樹的大小。

您可以通過使用https://en.wikipedia.org/wiki/Tseytin_transformation

2016-09-21 03:50:34 mcdowella

+0

避免這種吹脹以增加變量的數目的費用我只需要添加：單式意味着只有組合邏輯電路，但如果你有電路表示不能排除具有任意複雜性和行爲的時序邏輯電路（具有存儲器或循環）。 – Spektre

相關問題