「充足可能性問題」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: ''''【じゅうそくかのうせいもんだい (satisfiability problem)】''' 真または偽を表す論理変数とそれらの否定からなる和積形論理式, 例え...') |
|||
| 1行目: | 1行目: | ||
'''【じゅうそくかのうせいもんだい (satisfiability problem)】''' | '''【じゅうそくかのうせいもんだい (satisfiability problem)】''' | ||
| − | 真または偽を表す論理変数とそれらの否定からなる和積形論理式, 例えば | + | 真または偽を表す論理変数とそれらの否定からなる和積形論理式, 例えば<math>(x_1 \lor \bar{x}_2 \lor x_3) \land (\bar{x}_1 \lor \bar{x}_3) \land (x_2 \lor \bar{x}_3)\,</math>が与えられているとき, この式が真になるような論理変数への割り当てが存在するとき充足可能といい, それを判定する問題をいう. クック (Cook) が1971年にNP完全性を示した最初の問題. デイビス・プットナム (Davis-Putnam) のアルゴリズムなどが知られている. 以上は命題論理における充足可能性問題であるが, 述語論理における充足可能性問題は決定不能である. |
2007年7月12日 (木) 22:36時点における版
【じゅうそくかのうせいもんだい (satisfiability problem)】
真または偽を表す論理変数とそれらの否定からなる和積形論理式, 例えばが与えられているとき, この式が真になるような論理変数への割り当てが存在するとき充足可能といい, それを判定する問題をいう. クック (Cook) が1971年にNP完全性を示した最初の問題. デイビス・プットナム (Davis-Putnam) のアルゴリズムなどが知られている. 以上は命題論理における充足可能性問題であるが, 述語論理における充足可能性問題は決定不能である.
