フーリエ・モツキンの消去法とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > フーリエ・モツキンの消去法の意味・解説 

フーリエ・モツキンの消去法

(Fourier–Motzkin消去法 から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/03/03 04:35 UTC 版)

フーリエ・モツキンの消去法: Fourier-Motzkin elimination)とは、数理論理学および計算機科学において、一次不等式からなる一階述語論理式の限量子(∀や∃)を除去するアルゴリズム。限量子消去法(: Quantifier elimination)の1つ。1826年ジョゼフ・フーリエが発見し、1918年に L. L. Dines が再発見し、1936年に Theodore Motzkin が再々発見した[1]

アルゴリズム

以下の手順を繰り返し行い、限量子を除去していく[2]。変数の定義域は実数もしくは有理数

  1. 以下の置き換えを行う。
    1. 等式や不等式に ¬ がかかる物は反転させる。
    2. a ≧ b は b ≦ a へ
    3. a > b は b < a へ
    4. a = b は (a ≦ b) ∧ (b ≦ a) へ
    5. ∀x. P(x) は ¬ ∃x. ¬ P(x) へ
  2. 下記簡略化は随時行う。
    1. 常に成り立つ もしくは 常に不成立な不等式は真や偽に置き換える。
    2. 真や偽が ∧ や ∨ や ¬ に付く場合は適切に論理式を簡略化する。
    3. ∃x. P(x) の形式において、P(x) が x を使用してなければ、∃x. を取り除く。
  3. ∃x. P(x) の形式で、P(x) に限量子が出てこない物を探し、P(x) を選言標準形に変換する。
  4. ∃x. (P(x) ∨ Q(x)) ⇔ (∃x. P(x)) ∨ (∃x. Q(x)) の変換を行う。
  5. Q が x を使用していない場合、∃x. (P(x) ∧ Q) ⇔ (∃x. P(x)) ∧ Q の変換を行う。
  6. 下記公式を使い、限量子を除去する。



英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  
  •  フーリエ・モツキンの消去法のページへのリンク

辞書ショートカット

すべての辞書の索引

フーリエ・モツキンの消去法のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



フーリエ・モツキンの消去法のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのフーリエ・モツキンの消去法 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS