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

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。