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

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

2008年11月9日 (日) 18:39時点における最新版

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

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

「https://orsj-ml.org/orwiki/wiki/index.php?title=充足可能性問題&oldid=10550」から取得