Автоматизированный доказатель теорем Isabelle [a] — это доказатель теорем логики высшего порядка (HOL) , написанный на Standard ML и Scala . Как доказатель теорем в стиле Logic for Computable Functions (LCF), он основан на небольшом логическом ядре (ядре) для повышения достоверности доказательств, не требуя, но поддерживая, явные объекты доказательств.
Isabelle доступен в гибкой системной структуре, позволяющей логически безопасные расширения, которые включают как теории, так и реализации для генерации кода, документирования и специальной поддержки для различных формальных методов . Его можно рассматривать как интегрированную среду разработки (IDE) для формальных методов. В последние годы значительное количество теорий и расширений систем было собрано в Архиве формальных доказательств Isabelle ( Isabelle AFP ) [2]
Изабель была названа Лоуренсом Полсоном в честь дочери Жерара Юэ . [3]
Доказательство теоремы Изабеллы — это свободное программное обеспечение , выпущенное под пересмотренной лицензией BSD .
Isabelle является обобщенной: она предоставляет металогику (слабую теорию типов ), которая используется для кодирования объектных логик, таких как логика первого порядка (FOL), логика высшего порядка (HOL) или теория множеств Цермело–Френкеля (ZFC). Наиболее широко используемой объектной логикой является Isabelle/HOL, хотя значительные разработки теории множеств были завершены в Isabelle/ZF. Основной метод доказательства Isabelle — это версия резолюции высшего порядка, основанная на объединении высшего порядка .
Несмотря на интерактивность, Isabelle предлагает эффективные инструменты автоматического рассуждения, такие как механизм переписывания терминов и доказатель таблиц , различные процедуры принятия решений и, через интерфейс автоматизации доказательств Sledgehammer , решатели внешних теорий выполнимости по модулю (SMT) (включая CVC4 ) и автоматизированные доказательные устройства теорем (ATP) на основе резолюций , включая E , SPASS и Vampire ( метод доказательства Metis [b] реконструирует доказательства резолюций, сгенерированные этими ATP). [4] Он также предлагает два поисковика моделей ( генератора контрпримеров ): Nitpick [5] и Nunchaku . [6]
Isabelle предлагает локали, которые являются модулями, структурирующими большие доказательства. Локаль фиксирует типы, константы и предположения в указанной области действия [5], так что их не нужно повторять для каждой леммы .
Isar (« понятное полуавтоматическое рассуждение ») — формальный язык доказательств Изабель. Он вдохновлен системой Mizar . [5]
Isabelle позволяет писать доказательства в двух разных стилях: процедурном и декларативном . Процедурные доказательства определяют ряд тактик ( функций/процедур доказательства теорем ), которые следует применять. Хотя они отражают процедуру, которую математик-человек может применить для доказательства результата, их обычно трудно читать, поскольку они не описывают результат этих шагов. Декларативные доказательства (поддерживаемые языком доказательств Isabelle, Isar), с другой стороны, определяют фактические математические операции, которые необходимо выполнить, и поэтому их легче читать и проверять людям.
Процедурный стиль устарел в последних версиях Isabelle. [ необходима ссылка ]
Например, декларативное доказательство от противного в языке Изар того, что квадратный корень из двух не является рациональным числом, можно записать следующим образом.
теорема sqrt2_not_rational: "sqrt 2 ∉ ℚ" доказательство пусть ?x = "sqrt 2" предположим "?x ∈ ℚ" тогда получим mn :: nat где sqrt_rat: "¦?x¦ = m / n" и lower_terms: "взаимно простое m n" по (правило Rats_abs_nat_div_natE) следовательно "m^2 = ?x^2 * n^2" по (auto simp add: power2_eq_square) следовательно eq: "m^2 = 2 * n^2" используя of_nat_eq_iff power2_eq_square по fastforce следовательно "2 dvd m^2" по simp следовательно "2 dvd m" по simp имеем "2 dvd n" доказательство - из ‹2 dvd m› получим k где "m = 2 * k" .. с eq имеем "2 * n^2 = 2^2 * k^2" по simp следовательно "2 dvd n^2" по simp таким образом "2 dvd n" по simp qed с ‹2 dvd m› имеем "2 dvd gcd m n" по (правило gcd_greatest) с lower_terms имеем "2 dvd 1" по simp таким образом False используя odd_one по blast qed
Isabelle использовался для поддержки формальных методов спецификации, разработки и проверки программных и аппаратных систем.
Изабель использовалась для формализации многочисленных теорем из математики и компьютерных наук , таких как теорема Гёделя о полноте , теорема Гёделя о непротиворечивости аксиомы выбора , теорема о простых числах , корректность протоколов безопасности и свойства семантики языков программирования . Многие из формальных доказательств, как уже упоминалось, поддерживаются в Архиве формальных доказательств, который содержит (по состоянию на 2019 год) не менее 500 статей с более чем 2 миллионами строк доказательств в общей сложности. [7]
Ларри Полсон ведет список исследовательских проектов, в которых используется Isabelle. [10]
Несколько языков и систем предоставляют схожие функции:
.svg/1280px-Free_and_open-source_software_logo_(2009).svg.png){kind=logo}