Product Design, Manufacturing & Innovation Resources
Casa » Dimostrazione automatica di teoremi (ATP)

Dimostrazione automatica di teoremi (ATP)

1960
Informatico che conduce una dimostrazione automatica di teoremi in un ufficio degli anni '60.

(Immagine generata a solo scopo illustrativo)

La dimostrazione automatica di teoremi (ATP) è un sottocampo dell'informatica e della logica matematica dedicato alla dimostrazione di teoremi matematici utilizzando programmi per computer. I sistemi ATP, o dimostratori, utilizzano il ragionamento logico per dedurre nuovi teoremi da un insieme di assiomi e ipotesi. Sono diversi dagli assistenti alla dimostrazione, che richiedono una maggiore guida umana, sebbene i due campi si sovrappongano significativamente.

I dimostratori automatici di teoremi funzionano rappresentando la conoscenza matematica in un linguaggio formale, tipicamente la logica del primo ordine o la logica di ordine superiore. Applicano quindi le regole di inferenza in modo sistematico per cercare una dimostrazione. Una svolta fondamentale è stata lo sviluppo, da parte di John Alan Robinson nel 1965, del principio di risoluzione, una singola ed efficiente regola di inferenza completa per la logica del primo ordine. Ciò ha reso possibile la costruzione di sistemi automatizzati in grado di cercare dimostrazioni per confutazione (una forma di dimostrazione per assurdo). Il sistema prende gli assiomi e la negazione del teorema desiderato e cerca di derivare una contraddizione (la clausola vuota). In caso di successo, il teorema è dimostrato. I sistemi ATP sono stati utilizzati per risolvere problemi aperti di lunga data, il più famoso dei quali è la dimostrazione della congettura di Robbins nel 1996 da parte del dimostratore EQP. Sono anche fondamentali nell'industria per verifica formale, dove vengono utilizzati per dimostrare la correttezza di sistemi critici come i microprocessori e controllo di volo software, assicurandosi che siano privi di errori logici.

UNESCO Nomenclature: 1203
Informatica

Tipo

Software/Algoritmo

Interruzione

Incrementale

Utilizzo

Nicchia/Specializzato

Precursori

  • Il sogno di Leibniz di un "calculus ratiocinator" (un calcolo logico universale)
  • Sviluppo della logica formale da parte di Boole, Frege e Russell
  • Il lavoro di Turing sulla computabilità e la macchina di Turing
  • L'avvento dei computer digitali
  • Il programma Logic Theorist (1956)

Applicazioni

  • verifica formale dell'hardware (ad esempio, progettazione della CPU) e del software
  • ricerca sull'intelligenza artificiale
  • risolvere problemi aperti in matematica (ad esempio, la congettura di Robbins)
  • programmazione logica e sistemi esperti
  • assistenti di prova interattivi come Coq e Isabelle/HOL

Brevetti:

NA

Idee e potenziali innovazioni

  • verification of smart contracts on blockchain platforms
  • scoperta automatizzata di vulnerabilità e exploit del software
  • intelligenza artificiale generativa per la creazione di nuove congetture e dimostrazioni matematiche
  • verifica formale delle proprietà di sicurezza e allineamento dell'IA
  • sistemi di valutazione automatizzati per l'insegnamento della matematica e della logica
  • optimization of compilatore design based on provably correct transformations
  • scoperta di farmaci attraverso la modellazione logica delle interazioni molecolari
  • ragionamento giuridico automatizzato e analisi contrattuale
  • progettazione di sistemi di voto elettronico dimostrabilmente equi e sicuri
  • sviluppo di sistemi software autoverificanti
Argomenti correlati: dimostrazione automatica di teoremi, ATP, verifica formale, intelligenza artificiale, logica, principio di risoluzione, dimostratore automatico di teoremi, assistente di dimostrazione, informatica, metodi formali.

Contesto storico

Dimostrazione automatica di teoremi (ATP)

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

(se la data è sconosciuta o non rilevante, ad esempio "meccanica dei fluidi", viene fornita una stima approssimativa della sua notevole comparsa)

decimo anno anniversario

Le immagini a grandezza naturale e i download sono disponibili, gratuitamente al 100%, solo per gli utenti registrati.

> Login <