0
A
答えて
2
N
の関数は、truth-tableと2^N
行を持ちます。各行は1つのmintermに対応しています。これは解でもなくてもかまいません。
N
の句は、ソリューションの一部としてmintermのうちの1つだけを除きます。これは、文節のすべての反転された変数で構成されるmintermです。
、K
句はすべて異なっている提供
ソリューションの数は2^Nである - K
例と
K=3
条項N=3
変数:
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の解があります。
関連する問題
- 1. Cazeの迷路解決アルゴリズム
- 2. 番号迷路解決アルゴリズム
- 3. NullReferenceExceptionの解決方法は?
- 4. 解決方法:
- 5. 方程式解法アルゴリズム
- 6. (それは解決方法)
- 7. Xcodeは - 解決方法:
- 8. C-SATとSATの違いは?
- 9. 解決方法java.lang.NullPointerException
- 10. 解決方法アクティブレコードエラー
- 11. 解決方法:java.util.UnknownFormatConversionException:Conversion = '' '?
- 12. 解決方法java.util.concurrent.RejectedExecutionException
- 13. 解決方法LNK2001
- 14. 解決方法:Akka.Remote.EndpointDisassociatedException?
- 15. 解決方法 - java.lang.IncompatibleClassChangeError?
- 16. 反復番号を解決するアルゴリズム
- 17. 迷路解決アルゴリズム。複雑な迷路
- 18. "_tkinter.TclError:unknown option"の解決方法?
- 19. Bootstrap navbarの解決方法
- 20. トラブルの解決方法
- 21. 1045エラーの解決方法
- 22. MACエラーの解決方法
- 23. URLリダイレクトの解決方法
- 24. Androidアプリの解決方法
- 25. JSON解析エラーの解決方法?
- 26. マージ時のgit解決方法は?
- 27. はgitのマージエラー解決方法
- 28. パスを探す:SATを解く
- 29. エラーの解決方法:LNK2019:未解決の外部シンボル「public」?
- 30. 利益を最大化するアルゴリズム:解決する方法/アプローチ? (Advanced NP-Complete)
この宿題はありますか? –
@GeorgSchöllyいいえ、それは宿題ではありません。私は就職のための準備をするアルゴリズムを学んでいます。 – jas7
これは#P(https://en.wikipedia.org/wiki/Sharp-P?)の下に来るのですか?変数の数が節の数と等しいという制限がありますが、通常はもっと多くを期待します変数よりも節。しかし、(X | Y | Z | ...)のような節を追加することで、いくつかの変数の問題は常に埋め尽くされる可能性があります。ここで、X、Y、Z ...は、 – mcdowella