stringtranslate.com

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

Автоматизированное доказательство теорем (также известное как ATP или автоматизированная дедукция ) является подразделом автоматизированного рассуждения и математической логики, занимающимся доказательством математических теорем с помощью компьютерных программ . Автоматизированное рассуждение по математическому доказательству было основным мотивирующим фактором для развития компьютерной науки .

Логические основы

Хотя корни формализованной логики восходят к Аристотелю , в конце 19-го и начале 20-го веков развивалась современная логика и формализованная математика. Begriffsschrift Фреге ( 1879) представил как полное исчисление высказываний , так и то, что по сути является современной логикой предикатов . [1] Его « Основания арифметики» , опубликованные в 1884 году, [2] выразили (части) математики в формальной логике. Этот подход был продолжен Расселом и Уайтхедом в их влиятельной работе «Principia Mathematica» , впервые опубликованной в 1910–1913 годах, [3] и с пересмотренным вторым изданием в 1927 году. [4] Рассел и Уайтхед считали, что они могут вывести всю математическую истину, используя аксиомы и правила вывода формальной логики, в принципе открывая процесс для автоматизации. В 1920 году Торальф Скулем упростил предыдущий результат Леопольда Лёвенгейма , что привело к теореме Лёвенгейма–Скулема , а в 1930 году — к понятию вселенной Эрбрана и интерпретации Эрбрана , которая позволила свести (не)выполнимость формул первого порядка (и, следовательно, справедливость теоремы) к (потенциально бесконечному числу) проблем пропозициональной выполнимости. [5]

В 1929 году Мойжеш Пресбургер показал, что теория натурального числа первого порядка со сложением и равенством (теперь называемая арифметикой Пресбургера в его честь) разрешима, и дал алгоритм, который мог определить, является ли данное предложение в языке истинным или ложным. [6] [7]

Однако вскоре после этого положительного результата Курт Гёдель опубликовал работу «О формально неразрешимых предложениях Principia Mathematica и связанных с ними систем» (1931), показав, что в любой достаточно сильной аксиоматической системе существуют истинные утверждения, которые не могут быть доказаны в этой системе. Эта тема получила дальнейшее развитие в 1930-х годах у Алонзо Чёрча и Алана Тьюринга , которые, с одной стороны, дали два независимых, но эквивалентных определения вычислимости , а с другой — привели конкретные примеры неразрешимых вопросов .

Первые внедрения

Вскоре после Второй мировой войны появились первые универсальные компьютеры. В 1954 году Мартин Дэвис запрограммировал алгоритм Пресбургера для компьютера JOHNNIAC с электронными лампами в Институте перспективных исследований в Принстоне, штат Нью-Джерси. По словам Дэвиса, «его великим триумфом было доказательство того, что сумма двух четных чисел четна». [7] [8] Более амбициозным был Logic Theorist в 1956 году, система вывода для пропозициональной логики Principia Mathematica , разработанная Алленом Ньюэллом , Гербертом А. Саймоном и Дж. К. Шоу . Также работая на JOHNNIAC, Logic Theorist построил доказательства из небольшого набора пропозициональных аксиом и трех правил вывода: modus ponens , (пропозициональная) подстановка переменных и замена формул их определением. Система использовала эвристическое руководство и сумела доказать 38 из первых 52 теорем Principia . [7]

«Эвристический» подход логика-теоретика пытался подражать математикам-людям и не мог гарантировать, что доказательство может быть найдено для каждой допустимой теоремы даже в принципе. Напротив, другие, более систематические алгоритмы достигли, по крайней мере теоретически, полноты для логики первого порядка. Первоначальные подходы опирались на результаты Эрбрана и Сколема для преобразования формулы первого порядка в последовательно большие наборы пропозициональных формул путем инстанцирования переменных с терминами из вселенной Эрбрана . Затем пропозициональные формулы можно было проверить на невыполнимость с помощью ряда методов. Программа Гилмора использовала преобразование в дизъюнктивную нормальную форму , форму, в которой выполнимость формулы очевидна. [7] [9]

Разрешимость проблемы

В зависимости от базовой логики проблема определения действительности формулы варьируется от тривиальной до невозможной. Для общего случая пропозициональной логики проблема разрешима, но co -NP-полна , и, следовательно, для общих задач доказательства, как полагают, существуют только алгоритмы с экспоненциальным временем . Для исчисления предикатов первого порядка теорема о полноте Гёделя утверждает, что теоремы (доказуемые утверждения) являются в точности семантически допустимыми правильно сформированными формулами , поэтому допустимые формулы вычислимо перечислимы : при наличии неограниченных ресурсов любая допустимая формула в конечном итоге может быть доказана. Однако недопустимые формулы (те, которые не вытекают из данной теории) не всегда могут быть распознаны.

Вышеизложенное относится к теориям первого порядка, таким как арифметика Пеано . Однако для конкретной модели, которая может быть описана теорией первого порядка, некоторые утверждения могут быть истинными, но неразрешимыми в теории, используемой для описания модели. Например, по теореме Гёделя о неполноте мы знаем, что любая непротиворечивая теория, аксиомы которой истинны для натуральных чисел, не может доказать, что все утверждения первого порядка истинны для натуральных чисел, даже если список аксиом может быть бесконечно перечислимым. Из этого следует, что автоматизированный доказатель теорем не сможет завершить работу при поиске доказательства именно тогда, когда исследуемое утверждение неразрешимо в используемой теории, даже если оно истинно в интересующей модели. Несмотря на этот теоретический предел, на практике доказательчики теорем могут решать множество сложных задач, даже в моделях, которые не полностью описываются какой-либо теорией первого порядка (например, целыми числами ).

Связанные проблемы

Более простая, но связанная проблема — проверка доказательства , где существующее доказательство теоремы сертифицировано как действительное. Для этого обычно требуется, чтобы каждый отдельный шаг доказательства мог быть проверен примитивной рекурсивной функцией или программой, и, следовательно, проблема всегда разрешима.

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

Помощники доказательства требуют, чтобы пользователь-человек давал подсказки системе. В зависимости от степени автоматизации, доказывающий может быть по сути сведен к проверке доказательств, когда пользователь предоставляет доказательство формальным способом, или значительные задачи доказательства могут быть выполнены автоматически. Интерактивные доказывающие используются для различных задач, но даже полностью автоматические системы доказали ряд интересных и сложных теорем, включая по крайней мере одну, которая долгое время ускользала от математиков-людей, а именно гипотезу Роббинса . [10] [11] Однако эти успехи спорадичны, и работа над сложными проблемами обычно требует опытного пользователя.

Иногда проводится еще одно различие между доказательством теорем и другими методами, где процесс считается доказательством теорем, если он состоит из традиционного доказательства, начинающегося с аксиом и производящего новые шаги вывода с использованием правил вывода. Другие методы включают проверку модели , которая в простейшем случае включает в себя полный перебор многих возможных состояний (хотя фактическая реализация проверки моделей требует большого ума и не сводится просто к полному перебору).

Существуют гибридные системы доказательства теорем, которые используют проверку модели в качестве правила вывода. Существуют также программы, которые были написаны для доказательства конкретной теоремы, с (обычно неформальным) доказательством того, что если программа завершается с определенным результатом, то теорема верна. Хорошим примером этого было машинное доказательство теоремы о четырех красках , которое было очень спорным, поскольку первое заявленное математическое доказательство было по сути невозможно проверить людям из-за огромного размера вычислений программы (такие доказательства называются необозримыми доказательствами ). Другим примером программного доказательства является доказательство, которое показывает, что игру Connect Four всегда может выиграть первый игрок.

Приложения

Коммерческое использование автоматизированного доказательства теорем в основном сосредоточено в проектировании и проверке интегральных схем. После ошибки Pentium FDIV сложные блоки с плавающей точкой современных микропроцессоров были разработаны с особой тщательностью. AMD , Intel и другие используют автоматизированное доказательство теорем для проверки того, что деление и другие операции правильно реализованы в их процессорах. [12]

Другие применения доказателей теорем включают синтез программ , построение программ, которые удовлетворяют формальной спецификации . [13] Автоматизированные доказатели теорем были интегрированы с помощниками по доказательству , включая Isabelle/HOL . [14]

Приложения для доказательства теорем также можно найти в обработке естественного языка и формальной семантике , где они используются для анализа представлений дискурса . [15] [16]

Доказательство теоремы первого порядка

В конце 1960-х годов агентства, финансирующие исследования в области автоматизированной дедукции, начали подчеркивать необходимость практического применения. [ требуется ссылка ] Одной из первых плодотворных областей была верификация программ , в которой доказыватели теорем первого порядка применялись к проблеме проверки правильности компьютерных программ на таких языках, как Pascal , Ada и т. д. Среди ранних систем верификации программ выделялся Stanford Pascal Verifier, разработанный Дэвидом Лакхэмом в Стэнфордском университете . [17] [18] [19] Он был основан на Stanford Resolution Prover, также разработанном в Стэнфорде с использованием принципа резолюции Джона Алана Робинсона . Это была первая автоматизированная система дедукции, продемонстрировавшая способность решать математические задачи, которые были объявлены в Notices of the American Mathematical Society до того, как решения были официально опубликованы. [ требуется ссылка ]

Доказательство теорем первого порядка является одним из наиболее зрелых подполей автоматизированного доказательства теорем. Логика достаточно выразительна, чтобы позволить спецификацию произвольных проблем, часто достаточно естественным и интуитивным способом. С другой стороны, она все еще полуразрешима, и было разработано несколько надежных и полных исчислений, что позволяет создавать полностью автоматизированные системы. [20] Более выразительные логики, такие как логики высшего порядка , позволяют удобно выражать более широкий круг проблем, чем логика первого порядка, но доказательство теорем для этих логик менее развито. [21] [22]

Отношения с СМТ

Существует существенное совпадение между автоматическими доказывателями теорем первого порядка и решателями SMT . Как правило, автоматические доказыватели теорем фокусируются на поддержке полной логики первого порядка с кванторами, тогда как решатели SMT больше фокусируются на поддержке различных теорий (интерпретированных предикатных символов). ATP преуспевают в задачах с большим количеством кванторов, тогда как решатели SMT хорошо справляются с большими задачами без кванторов. [23] Граница достаточно размыта, так что некоторые ATP участвуют в SMT-COMP, в то время как некоторые решатели SMT участвуют в CASC . [24]

Тесты, соревнования и источники

Качество реализованных систем улучшилось благодаря наличию большой библиотеки стандартных контрольных примеров — Библиотеки задач «Тысячи задач для доказательств теорем» (TPTP) [25] , а также благодаря CADE ATP System Competition (CASC), ежегодному конкурсу систем первого порядка для многих важных классов задач первого порядка.

Ниже перечислены некоторые важные системы (все они выиграли как минимум один дивизион соревнований CASC).

The Theorem Prover Museum [27] — это инициатива по сохранению источников систем доказательства теорем для будущего анализа, поскольку они являются важными культурными/научными артефактами. Он содержит источники многих из упомянутых выше систем.

Популярные техники

Системы программного обеспечения

Бесплатное программное обеспечение

Собственное программное обеспечение

Смотрите также

Примечания

  1. ^ Фреге, Готтлоб (1879). Бегриффсшрифт. Верлаг Луи Нойерт.
  2. ^ Фреге, Готтлоб (1884). Die Grundlagen der Arithmetik (PDF) . Бреслау: Вильгельм Кобнер. Архивировано из оригинала (PDF) 26 сентября 2007 г. Проверено 2 сентября 2012 г.
  3. ^ Рассел, Бертран; Уайтхед, Альфред Норт (1910–1913). Principia Mathematica (1-е изд.). Cambridge University Press.
  4. ^ Рассел, Бертран; Уайтхед, Альфред Норт (1927). Principia Mathematica (2-е изд.). Cambridge University Press.
  5. ^ Эрбран, Дж. (1930). Recherches sur la theorie de la démonstration (PhD) (на французском языке). Парижский университет.
  6. ^ Пресбургер, Мойжес (1929). «Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem ​​die Additions als einzige Operation hervortritt». Comptes Rendus du I Congrès de Mathématiciens de Pays рабов . Варшава: 92–101.
  7. ^ abcd Дэвис, Мартин (2001). «Ранняя история автоматизированной дедукции». Робинсон и Воронков 2001. Архивировано из оригинала 28-07-2012 . Получено 08-09-2012 .
  8. ^ Бибель, Вольфганг (2007). «Ранняя история и перспективы автоматизированной дедукции» (PDF) . Ki 2007 . LNAI (4667). Springer: 2–18. Архивировано (PDF) из оригинала 2022-10-09 . Получено 2 сентября 2012 .
  9. ^ Гилмор, Пол (1960). «Процедура доказательства для теории квантификации: ее обоснование и реализация». IBM Journal of Research and Development . 4 : 28–35. doi :10.1147/rd.41.0028.
  10. ^ Маккьюн, WW (1997). «Решение проблемы Роббинса». Журнал автоматизированного рассуждения . 19 (3): 263–276. doi :10.1023/A:1005843212881. S2CID  30847540.
  11. ^ Колата, Джина (10 декабря 1996 г.). «Компьютерное математическое доказательство демонстрирует силу рассуждения». The New York Times . Получено 11 октября 2008 г.
  12. ^ Гоэль, Шилпи; Рэй, Сандип (2022), Чаттопадхай, Анупам (ред.), «Гарантия микропроцессора и роль доказательства теорем», Справочник по архитектуре компьютеров , Сингапур: Springer Nature Singapore, стр. 1–43, doi :10.1007/978-981-15-6401-7_38-1, ISBN 978-981-15-6401-7, получено 2024-02-10
  13. ^ Basin, D.; Deville, Y.; Flener, P.; Hamfelt, A.; Fischer Nilsson, J. (2004). «Синтез программ в вычислительной логике». В M. Bruynooghe и K.-K. Lau (ред.). Разработка программ в вычислительной логике . LNCS. Том 3049. Springer. стр. 30–65. CiteSeerX 10.1.1.62.4976 . 
  14. ^ Мэн, Цзя; Полсон, Лоуренс К. (2008-01-01). «Перевод предложений высшего порядка в предложения первого порядка». Журнал автоматизированного рассуждения . 40 (1): 35–60. doi :10.1007/s10817-007-9085-y. ISSN  1573-0670. S2CID  7716709.
  15. ^ Бос, Йохан. «Широкий семантический анализ с боксером». Семантика в обработке текста. Материалы конференции Step 2008. 2008.
  16. ^ Маскенс, Рейнхард. «Объединение семантики Монтегю и репрезентации дискурса». Лингвистика и философия (1996): 143-186.
  17. ^ Лакхэм, Дэвид К.; Судзуки, Норихиса (март 1976 г.). Автоматическая проверка программ V: ориентированные на проверку правила доказательства для массивов, записей и указателей (технический отчет AD-A027 455). Defense Technical Information Center . Архивировано из оригинала 12 августа 2021 г.
  18. ^ Лакхэм, Дэвид С.; Судзуки, Норихиса (октябрь 1979 г.). «Проверка операций с массивами, записями и указателями в Паскале». Труды ACM по языкам и системам программирования . 1 (2): 226–244. doi : 10.1145/357073.357078 . S2CID  10088183.
  19. ^ Лакхэм, Д.; Герман, С.; фон Хенке, Ф.; Карп, Р.; Милн, П.; Оппен, Д.; Полак, В.; Шерлис, В. (1979). Руководство пользователя верификатора Stanford Pascal (технический отчет). Стэнфордский университет. CS-TR-79-731.
  20. ^ Лавленд, Д. В. (1986). «Автоматизированное доказательство теорем: отображение логики в ИИ». Труды международного симпозиума ACM SIGART по методологиям для интеллектуальных систем . Ноксвилл, Теннесси, США: ACM Press. стр. 224. doi : 10.1145/12808.12833 . ISBN 978-0-89791-206-8. S2CID  14361631.
  21. ^ Кербер, Манфред. «Как доказать теоремы высшего порядка в логике первого порядка». (1999).
  22. ^ Бенцмюллер, Кристоф и др. «LEO-II — кооперативный автоматический доказатель теорем для классической логики высшего порядка (описание системы)». Международная совместная конференция по автоматизированному рассуждению. Берлин, Германия и Гейдельберг: Springer, 2008.
  23. ^ Blanchette, Jasmin Christian; Böhme, Sascha; Paulson, Lawrence C. (2013-06-01). "Extending Sledgehammer with SMT Solvers". Journal of Automated Reasoning . 51 (1): 109–128. doi :10.1007/s10817-013-9278-5. ISSN  1573-0670. S2CID  5389933. ATP и SMT Solvers имеют взаимодополняющие сильные стороны. Первые справляются с квантификаторами более элегантно, тогда как вторые преуспевают в больших, в основном наземных задачах.
  24. ^ Вебер, Тьярк; Коншон, Сильвен; Дехарб, Дэвид; Хейцманн, Маттиас; Нимец, Айна; Регер, Джайлс (2019-01-01). "The SMT Competition 2015–2018". Журнал Satisfiability, Boolean Modeling and Computation . 11 (1): 221–259. doi : 10.3233/SAT190123 . В последние годы мы наблюдаем размывание границ между SMT-COMP и CASC, когда решатели SMT конкурируют в CASC, а ATP — в SMT-COMP.
  25. ^ Сатклифф, Джефф. "Библиотека задач TPTP для автоматического доказательства теорем" . Получено 15 июля 2019 г.
  26. ^ "История". vprover.github.io .
  27. ^ "Музей доказательства теорем". Михаэль Кольхазе . Получено 2022-11-20 .
  28. ^ Банди, Алан (1999). Автоматизация доказательства с помощью математической индукции (PDF) (Технический отчет). Отчет по исследованию информатики. Том 2. Отделение информатики, Эдинбургский университет. hdl :1842/3394.
  29. ^ Габбай, Дов М. и Ханс Юрген Ольбах. «Устранение квантификаторов в логике предикатов второго порядка». (1992).

Ссылки

Внешние ссылки