Product Design, Manufacturing & Innovation Resources
» 自動定理証明(ATP)

自動定理証明(ATP)

1960
Computer scientist conducting automated theorem proving in a 1960s office.

(画像はイメージです)

自動定理証明(ATP)は、コンピュータプログラムを用いて数学の定理を証明することに特化した、コンピュータ科学と数理論理学の一分野です。ATPシステム、すなわち証明器は、論理的推論を用いて、一連の公理と仮説から新しい定理を導き出します。これらは、より多くの人間の介入を必要とする証明支援システムとは異なりますが、両分野は大きく重なり合っています。

Automated theorem provers work by representing mathematical knowledge in a formal language, typically first-order logic or higher-order logic. They then apply rules of inference in a systematic way to search for a proof. A key breakthrough was John Alan Robinson’s development of the resolution principle in 1965, a single, efficient rule of inference that is complete for first-order logic. This made it practical to build automated systems that could search for proofs by refutation (a form of proof by contradiction). The system takes the axioms and the negation of the desired theorem and tries to derive a contradiction (the empty clause). If successful, the theorem is proven. ATP systems have been used to solve long-standing open problems, most famously the proof of the Robbins conjecture in 1996 by the EQP prover. They are also critical in industry for formal verification, where they are used to prove the correctness of critical systems like microprocessors and flight control software, ensuring they are free from logical errors.

UNESCO Nomenclature: 1203
コンピュータサイエンス

タイプ

ソフトウェア/アルゴリズム

混乱

増分

使用法

ニッチ/専門分野

前駆物質

  • ライプニッツの「計算論理式」(普遍的な論理計算)の夢
  • ブール、フレーゲ、ラッセルによる形式論理の発展
  • チューリングの計算可能性に関する研究とチューリングマシン
  • デジタルコンピュータの出現
  • 論理理論家プログラム(1956年)

アプリケーション

  • ハードウェア(CPU設計など)およびソフトウェアの形式検証
  • 人工知能研究
  • 数学における未解決問題の解決(例:ロビンス予想)
  • 論理プログラミングとエキスパートシステム
  • CoqやIsabelle/HOLのような対話型証明支援システム

特許:

NA

潜在的なイノベーションのアイデア

ボットによるトラフィック(現在1日あたり4万件以上)を排除するため、このコンテンツはコミュニティメンバー限定となっています。
> ログイン < または > 登録 < (100%無料)でこれにアクセスできます。他のすべての制限付きコンテンツとツールも同様です。

関連キーワード:自動定理証明、ATP、形式検証、人工知能、論理学、分解原理、定理証明器、証明支援システム、コンピュータサイエンス、形式手法。

歴史的背景

自動定理証明(ATP)

1950
1953
1960
1960
1967
1970
1970
1950
1952
1956
1960
1967
1967
1970
1970

(日付が不明または関連性がない場合、例えば「流体力学」などでは、その注目すべき出現時期の概算値が提示されます。)

関連する発明、革新、および技術原理

フルサイズの画像とダウンロードは、登録会員のみが100%無料で利用できます。