「充足可能性問題」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
("充足可能性問題" を保護しました。 [edit=sysop:move=sysop])
(相違点なし)

2007年7月20日 (金) 11:15時点における版

【じゅうそくかのうせいもんだい (satisfiability problem)】

真または偽を表す論理変数とそれらの否定からなる和積形論理式, 例えばが与えられているとき, この式が真になるような論理変数への割り当てが存在するとき充足可能といい, それを判定する問題をいう. クック (Cook) が1971年にNP完全性を示した最初の問題. デイビス・プットナム (Davis-Putnam) のアルゴリズムなどが知られている. 以上は命題論理における充足可能性問題であるが, 述語論理における充足可能性問題は決定不能である.