Автоматическое доказательство: различия между версиями

Материал из Свод знаний по информационному моделированию
Перейти к навигации Перейти к поиску
(Добавил ссылку на музей систем доказательства теорем)
(Добавлен раздел библиотеки и информация о SMT-библиотеке)
 
(не показано 5 промежуточных версий этого же участника)
Строка 4: Строка 4:
   
 
'''Автоматические генераторы доказательств.''' В них пользователь только ставит задачу («необходимо доказать теорему»), после чего генератор работает до обнаружения доказательства или выполнения условия останова.
 
'''Автоматические генераторы доказательств.''' В них пользователь только ставит задачу («необходимо доказать теорему»), после чего генератор работает до обнаружения доказательства или выполнения условия останова.
  +
  +
= Интерактивные системы доказательства теорем =
   
 
Некоторые системы интерактивного поиска доказательства теорем:
 
Некоторые системы интерактивного поиска доказательства теорем:
   
Coq. Предоставляет язык программирования и окружение для создания формальных доказательств. Позволяет пользователям записывать математические утверждения и применять логические правила для доказательства этих утверждений.
+
[https://coq.inria.fr/ Coq]. Предоставляет язык программирования и окружение для создания формальных доказательств. Позволяет пользователям записывать математические утверждения и применять логические правила для доказательства этих утверждений.
   
Isabelle. Предоставляет окружение для формализации и проверки доказательств. Использует логику второго порядка и предлагает различные инструменты для автоматического и интерактивного доказательства.
+
[https://isabelle.in.tum.de/ Isabelle]. Предоставляет окружение для формализации и проверки доказательств. Использует логику второго порядка и предлагает различные инструменты для автоматического и интерактивного доказательства.
  +
  +
Есть еще ряд решений для интерактивного поиска доказательства теорем, которые используют Python или другой вид высокоуровневых языков, которые формируют интерефейс для системы автоматического доказательства теорем:
  +
  +
[https://www.philipzucker.com/knuckledragger/ Knuckledragger] - это инструмент интерактивного доказательства теорем на python с помощью уже существующих автоматизированных решателей.
  +
  +
= Автоматизированные системы доказательства теорем =
   
 
Некоторые автоматические генераторы доказательств:
 
Некоторые автоматические генераторы доказательств:
Строка 17: Строка 25:
 
[[E]]. Cредство проверки теорем о насыщении для логики первого и более высокого порядка с равенством.
 
[[E]]. Cредство проверки теорем о насыщении для логики первого и более высокого порядка с равенством.
   
Z3. Предоставляет возможность генерации доказательств в различных формальных системах и языках программирования.
+
[https://github.com/Z3Prover Z3]. Это система доказательства теорем от Microsoft Research, получивший несколько наград и имеющий активное сообщество разработчиков с открытым исходным кодом. Предоставляет возможность генерации доказательств в различных формальных системах и языках программирования.
   
  +
[https://leancop.de/nanocop/ nanoCoP] - это компактный неклаузальный автоматический инструмент для доказательства теорем классической логики первого порядка. Он основан на неклаузальном математическом анализе связей для классической логики. Более подробную информацию об этом методе можно найти в документации.
  +
  +
[https://nick8325.github.io/twee/ Twee] - это инструмент для доказательства теорем в области эквациональной логики. Он использует в качестве входных данных два набора уравнений, аксиомы и гипотезы, и пытается доказать гипотезы, исходя из аксиом. Как получить копию, смотрите на странице установки; возможно, вы также захотите ознакомиться с кратким руководством.
  +
  +
[https://cvc5.github.io/ cvc5] - это эффективный автоматический тестер теорем с открытым исходным кодом для задач [https://en.wikipedia.org/wiki/Satisfiability_modulo_theories теории выполнимости по модулю (SMT)]. Он может быть использован для доказательства выполнимости (или, как правило, достоверности) формул первого порядка относительно (комбинаций) различных полезных базовых теорий. Кроме того, он предоставляет [https://sygus-org.github.io/ механизм синтаксического синтеза (SyGuS)] для синтеза функций с учетом базовых теорий и их комбинаций.
  +
  +
[https://yices.csl.sri.com/ Yices 2] - это SMT-решатель, который определяет выполнимость формул, содержащих неинтерпретированные функциональные символы с равенством, действительную и целочисленную арифметику, битовые векторы, скалярные типы и кортежи. Yices 2 поддерживает как линейную, так и нелинейную арифметику.
  +
  +
[https://verify.inf.usi.ch/opensmt OpenSMT] - это компактный SMT-решатель с открытым исходным кодом, написанный на C++, основная цель которого - сделать SMT-решатели простыми для понимания и использования в качестве вычислительного механизма для формальной проверки. OpenSMT построен поверх MiniSat.
  +
  +
= Языковые модели для доказательства теорем =
 
Также существует языковая модель [https://neurohive.io/ru/papers/gpt-f-nejroset-generiruet-dokazatelstva-teorem/ GPT-f], которую обучили генерировать доказательства теорем.
 
Также существует языковая модель [https://neurohive.io/ru/papers/gpt-f-nejroset-generiruet-dokazatelstva-teorem/ GPT-f], которую обучили генерировать доказательства теорем.
   
  +
= Библиотеки =
Ещё можно заглянуть в [https://github.com/theoremprover-museum музей систем доказательства теорем].
 
  +
  +
[https://smt-lib.org SMT-LIB] - это международная инициатива, направленная на содействие исследованиям и разработкам в области теорий выполнимости по модулю (SMT). С момента своего создания в 2003 году инициатива преследовала эти цели, сосредоточившись на следующих конкретных задачах:
  +
С момента своего создания в 2003 году инициатива преследовала эти цели, сосредоточившись на следующих конкретных задачах:
  +
  +
Предоставьте стандартные подробные описания базовых теорий, используемых в SMT-системах.
  +
Разработайте и продвигайте общие языки ввода и вывода для SMT-решателей.
  +
Объедините разработчиков, исследователей и пользователей SMT и создайте вокруг них сообщество.
  +
Создайте и предоставьте в распоряжение исследовательского сообщества большую библиотеку тестов для SMT-решателей.
  +
Собирать и продвигать программные средства, полезные для сообщества SMT.
  +
  +
Этот веб-сайт предоставляет доступ к следующим основным материалам инициативы.
  +
  +
Документы, описывающие язык ввода-вывода SMT-LIB для решателей SMT и его семантику;
  +
Спецификации базовых теорий и логики.;
  +
Большая библиотека входных задач, или тестов, написанных на языке SMT-LIB.
  +
Ссылки на SMT-решатели и связанные с ними инструменты и утилиты.
  +
  +
= Музей систем доказательства теорем =
 
Ещё можно заглянуть в [https://theoremprover-museum.github.io/ музей систем доказательства теорем].
   
 
----
 
----

Текущая версия на 21:35, 22 февраля 2025

Системы доказательства теорем делятся на две группы[1]:

Системы интерактивного поиска доказательства теорем (редакторы доказательств). Они позволяют пользователям конструировать доказательство под контролем системы.

Автоматические генераторы доказательств. В них пользователь только ставит задачу («необходимо доказать теорему»), после чего генератор работает до обнаружения доказательства или выполнения условия останова.

Интерактивные системы доказательства теорем

Некоторые системы интерактивного поиска доказательства теорем:

Coq. Предоставляет язык программирования и окружение для создания формальных доказательств. Позволяет пользователям записывать математические утверждения и применять логические правила для доказательства этих утверждений.

Isabelle. Предоставляет окружение для формализации и проверки доказательств. Использует логику второго порядка и предлагает различные инструменты для автоматического и интерактивного доказательства.

Есть еще ряд решений для интерактивного поиска доказательства теорем, которые используют Python или другой вид высокоуровневых языков, которые формируют интерефейс для системы автоматического доказательства теорем:

Knuckledragger - это инструмент интерактивного доказательства теорем на python с помощью уже существующих автоматизированных решателей.

Автоматизированные системы доказательства теорем

Некоторые автоматические генераторы доказательств:

Prover9. Основана на методе резолюций и может генерировать доказательства в логике первого порядка.

E. Cредство проверки теорем о насыщении для логики первого и более высокого порядка с равенством.

Z3. Это система доказательства теорем от Microsoft Research, получивший несколько наград и имеющий активное сообщество разработчиков с открытым исходным кодом. Предоставляет возможность генерации доказательств в различных формальных системах и языках программирования.

nanoCoP - это компактный неклаузальный автоматический инструмент для доказательства теорем классической логики первого порядка. Он основан на неклаузальном математическом анализе связей для классической логики. Более подробную информацию об этом методе можно найти в документации.

Twee - это инструмент для доказательства теорем в области эквациональной логики. Он использует в качестве входных данных два набора уравнений, аксиомы и гипотезы, и пытается доказать гипотезы, исходя из аксиом. Как получить копию, смотрите на странице установки; возможно, вы также захотите ознакомиться с кратким руководством.

cvc5 - это эффективный автоматический тестер теорем с открытым исходным кодом для задач теории выполнимости по модулю (SMT). Он может быть использован для доказательства выполнимости (или, как правило, достоверности) формул первого порядка относительно (комбинаций) различных полезных базовых теорий. Кроме того, он предоставляет механизм синтаксического синтеза (SyGuS) для синтеза функций с учетом базовых теорий и их комбинаций.

Yices 2 - это SMT-решатель, который определяет выполнимость формул, содержащих неинтерпретированные функциональные символы с равенством, действительную и целочисленную арифметику, битовые векторы, скалярные типы и кортежи. Yices 2 поддерживает как линейную, так и нелинейную арифметику.

OpenSMT - это компактный SMT-решатель с открытым исходным кодом, написанный на C++, основная цель которого - сделать SMT-решатели простыми для понимания и использования в качестве вычислительного механизма для формальной проверки. OpenSMT построен поверх MiniSat.

Языковые модели для доказательства теорем

Также существует языковая модель GPT-f, которую обучили генерировать доказательства теорем.

Библиотеки

SMT-LIB - это международная инициатива, направленная на содействие исследованиям и разработкам в области теорий выполнимости по модулю (SMT). С момента своего создания в 2003 году инициатива преследовала эти цели, сосредоточившись на следующих конкретных задачах: С момента своего создания в 2003 году инициатива преследовала эти цели, сосредоточившись на следующих конкретных задачах:

Предоставьте стандартные подробные описания базовых теорий, используемых в SMT-системах. Разработайте и продвигайте общие языки ввода и вывода для SMT-решателей. Объедините разработчиков, исследователей и пользователей SMT и создайте вокруг них сообщество. Создайте и предоставьте в распоряжение исследовательского сообщества большую библиотеку тестов для SMT-решателей. Собирать и продвигать программные средства, полезные для сообщества SMT.

Этот веб-сайт предоставляет доступ к следующим основным материалам инициативы.

Документы, описывающие язык ввода-вывода SMT-LIB для решателей SMT и его семантику; Спецификации базовых теорий и логики.; Большая библиотека входных задач, или тестов, написанных на языке SMT-LIB. Ссылки на SMT-решатели и связанные с ними инструменты и утилиты.

Музей систем доказательства теорем

Ещё можно заглянуть в музей систем доказательства теорем.