2017-01-29 10 views
0

変数の数Nと句数Kが等しいとします。節を満たすさまざまな方法の数を返すアルゴリズムを見つけます。アルゴリズム:SATの解決方法は?

私はSATが独立したセットに関連していると読んでいます。

+0

この宿題はありますか? –

+0

@GeorgSchöllyいいえ、それは宿題ではありません。私は就職のための準備をするアルゴリズムを学んでいます。 – jas7

+0

これは#P(https://en.wikipedia.org/wiki/Sharp-P?)の下に来るのですか?変数の数が節の数と等しいという制限がありますが、通常はもっと多くを期待します変数よりも節。しかし、(X | Y | Z | ...)のような節を追加することで、いくつかの変数の問題は常に埋め尽くされる可能性があります。ここで、X、Y、Z ...は、 – mcdowella

答えて

2

Nの関数は、truth-table2^N行を持ちます。各行は1つのmintermに対応しています。これは解でもなくてもかまいません。

Nの句は、ソリューションの一部としてmintermのうちの1つだけを除きます。これは、文節のすべての反転された変数で構成されるmintermです。

K句はすべて異なっている提供

ソリューションの数は2^Nである - K


例と

K=3条項N=3変数:

可能8つの用語真のままの

A B C output 
0 0 0 0   // excluded by A or B or C 
0 0 1 0   // excluded by A or B or !C 
0 1 0 1 
0 1 1 1 
1 0 0 0   // excluded by !A or B or C  
1 0 1 1 
1 1 0 1 
1 1 1 1 

5:3つの入力用

A or B or C 
!A or B or C 
A or B or !C 

真理値表。したがって、この例には2^3 - 3 = 5の解があります。