将二进制公式转换为香农范式

Question

我想知道将二进制公式转换为香农范式的步骤。

a⪯b⪯c⪯d - variable ordering.
F = b&c&!d|c&d&!b|d&!c|!c&!d

如何将其转换为香农范式？

Answer 1

您首先计算 F|{a=0} 和 F|{a=1}。因为 F 不依赖于变量 a，所以两种情况都会得到 F：

F|{a=0} = F
F|{a=1} = F

您继续计算 F|{a=0,b=0}、F|{a=0,b=1}、F|{a=1,b=0} 和 F|{a =1,b=1}。你将获得

F|{a=0,b=0} = F|{a=1,b=0} = c&d|d&!c|!c&!d = !c|d
F|{a=0,b=1} = F|{a=1,b=1} = c&!d|d&!c|!c&!d = !c|!d

你继续使用变量 c 和变量 d，最后你得到：

F = !a(!b(!c(!d&1+d&1)|c(!d&0+d&1))|b(!c(!d&1+d&1)|c(!d&1+d&0))|
     a(!b(!c(!d&1+d&1)|c(!d&0+d&1))|b(!c(!d&1+d&1)|c(!d&1+d&0))

如果您需要相反的顺序，只需按变量的倒序计算，您可能会得到完全不同的结果。

这是 BDD Scout (http://biddy.meolic.com/) 的屏幕截图，不幸的是，此工具尚不支持没有补边的 BDD。

convert binary formula to Shannon Normal Form