OBDDの操作：シャノンの拡大による否定

Question

の適用に問題があります シャノン拡張 フォーミュラブールの否定を取得するために、OBDDに否定演算子を実装する必要があるよりも（バイナリ決定図を注文します）それは、次のことを示しています。

$ qquad displaystyle neg f（x_1、 ldots、x_n）=（ neg x_1 wedge neg f | _ {x_1 = 0}） vee（x_1 wed neg f | _ {x_1 = 1}} ）$

ここで、$ f | _ {x_i = b} $は、$ x_i $をbに置き換える関数ブール値です。

$ qquad displaystyle f | _ {x_i = b}（x_1、 ldots、x_n）= f（x_1、 ldots、x_ {i-1}、b、x_ {i+1}、 ldots、x_n） $。

証拠は言う：

$ qquad displaystyle neg f（x_1、 ldots、x_n）= neg（（ neg x_1 wedge f | _ {x_1 = 0}） vee（x_1 ウェッジF | _ {x_1 = 1}） ）$。

否定を適用する（中間ステップをスキップ）、次のように取得します。

$ qquad displaystyle（x_1 wedge neg x_1） vee（ neg x_1 wedge neg f | _ {x_1 = 0}） vee（x_1 wedge neg f | _ {x_1 = 1}） vee（ neg f | _ {x_1 = 0} wedge neg f | _ {x_1 = 1}）$。

$（x_1 wedge neg x_1）= mathrm {false} $はドロップできます。

$ qquad displaystyle（ neg x_1 wedge neg f | _ {x_1 = 0}） vee（x_1 wed neg f | _ {x_1 = 1}） vee（ neg f | _ {x_1 = 0} wedge neg f | _ {x_1 = 1}）$

これは、最後に、に等しくなります

$ qquad displaystyle（ neg x_1 wedge neg f | _ {x_1 = 0}） vee（x_1 wedge neg f | _ {x_1 = 1}）$。

なぜこれが保持されるのですか？

Answer 1

両方の機能の真理テーブルを作成するかどうかを理解する方が良いかもしれません。 $（ neg f | _ {x_1 = 0} wedge neg f | _ {x_1 = 1}）$がtrueである場合、$（ neg x_1 wedge neg f | _ {x_1 = 0 }） vee（x_1 wedge neg f | _ {x_1 = 1}）$もtrueです。$ f $の用語は真であり、$ x_1 $がtrueまたは$ neg x_1 $がtrueであるためです。そして、$（ neg f | _ {x_1 = 0} wedge neg f | _ {x_1 = 1}）$が偽である場合、ケーススタディを行う必要があります。

• 両方の$ f $項がfalseである場合、$（ neg x_1 wedge neg f | _ {x_1 = 0}） vee（x_1 wed neg f | _ {x_1 = 1}）$も偽です
• 正確に1つの$ f $用語（wlog $ neg f | _ {x_1 = 0} $）が偽である場合、$（x_1 wedge neg f | _ {x_1 = 1}）$に相当します

したがって、両方の式$（ neg x_1 wedge neg f | _ {x_1 = 0}） vee（x_1 wedge neg f | _ {x_1 = 1}） vee（ neg f | _ {x_1 = 0} wedge neg f | _ {x_1 = 1}）$ and $（ neg x_1 wedge neg f | _ {x_1 = 0}） vee（x_1 wedge neg f | _ {x_1 = 1 }）$は同等です。