バイナリ式をShannon Normal Formに変換する

Question

バイナリ式をShannon Normal Formに変換する手順を知りたいと思います。

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

これをどのようにしてShannon Normal Formに変換できますか？

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(!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)) 

をあなたは逆の順序付けが必要な場合：あなたはあなたが得る最終的変数cと変数dを続行し、

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 

を取得します結果。

ここではBDD Scout（http://biddy.meolic.com/）のスクリーンショットですが、残念ながらこのツールは補完エッジのないBDDをサポートしていません。