Product Design, Manufacturing & Innovation Resources
Maison » Démonstration automatique de théorèmes (ATP)

Démonstration automatique de théorèmes (ATP)

1960
Informaticien effectuant une démonstration automatique de théorèmes dans un bureau des années 1960.

(Image générée à titre d'illustration uniquement)

La démonstration automatique de théorèmes (DAT) est une branche de l'informatique et de la logique mathématique qui consiste à démontrer des théorèmes mathématiques à l'aide de programmes informatiques. Les systèmes de DAT, ou démonstrateurs, utilisent le raisonnement logique pour déduire de nouveaux théorèmes à partir d'un ensemble d'axiomes et d'hypothèses. Ils se distinguent des assistants de preuve, qui nécessitent une intervention humaine plus importante, bien que les deux domaines présentent des similitudes significatives.

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
Informatique

Taper

Logiciel/Algorithme

Perturbation

Incrémentale

Usage

Créneau/spécialité

Précurseurs

  • Le rêve de Leibniz d'un « calculateur de ratio » (un calcul logique universel)
  • Développement de la logique formelle par Boole, Frege et Russell
  • Les travaux de Turing sur la calculabilité et la machine de Turing
  • L'avènement des ordinateurs numériques
  • Le programme du théoricien de la logique (1956)

Applications

  • vérification formelle du matériel (par exemple, la conception du processeur) et du logiciel
  • recherche en intelligence artificielle
  • résoudre des problèmes ouverts en mathématiques (par exemple, la conjecture de Robbins)
  • programmation logique et systèmes experts
  • assistants de preuve interactifs comme Coq et Isabelle/HOL

Brevets:

NA

Idées d'innovations potentielles

En raison du trafic généré par les robots de scraping, actuellement supérieur à 40 000 par jour, ce contenu est réservé aux membres de la communauté.
> Connexion < ou > Registre < (100% gratuit) pour y accéder, ainsi qu'à tous les autres contenus et outils à accès restreint.

Lié à : démonstration automatique de théorèmes, ATP, vérification formelle, intelligence artificielle, logique, principe de résolution, démonstrateur de théorèmes, assistant de preuve, informatique, méthodes formelles.

Contexte historique

Démonstration automatique de théorèmes (ATP)

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

(si la date est inconnue ou non pertinente, par exemple « mécanique des fluides », une estimation arrondie de son émergence notable est fournie)

Inventions, innovations et principes techniques connexes

Les images en pleine résolution et les téléchargements sont uniquement disponibles, et 100% gratuits, pour les membres inscrits.