-1

次のことが理解できなくて困っています。

充足可能性の問題を接続正規形で見ると、制約不足の問題は、変数を制約する節が比較的少ない問題です。たとえば。これは、ランダムに生成された、5 つの記号と 5 つの句を含む 3-CNF 文です。(各節には、ランダムに選択された 3 つの異なる記号が含まれており、それぞれが 50% の確率で否定されます。)

 (¬D ∨ ¬B ∨ C) ∧ (B ∨ ¬A ∨ ¬C) ∧ (¬C ∨ ¬B ∨ E) ∧ (E ∨ ¬D ∨ B) ∧ (B ∨ E ∨ ¬C)

32 の可能な割り当てのうち 16 がこの文のモデルであるため、平均して、モデルを見つけるのに 2 回のランダムな推測が必要です。

最後の行がわかりません - 32 の可能な割り当てがあると言っています。32はどうですか？そして、そのうちの 16 個だけがどのように文のモデルになるのでしょうか? 申し訳ありませんが、この概念は少し混乱しています。ありがとう。

4

1 に答える 1

0

trueとfalseの 2 つの値を 5 つの変数に割り当てるには、2^5=32 の可能性があります。

1:  00000
2:  00001
3:  00010
    ...
31: 11110
32: 11111

これらの割り当てのうち 16 個は、指定された式を満たしています (私は確認していません)。したがって、そのモデルです。

于 2012-09-25T11:38:25.207 に答える