WikiDer > Метамат

Метамат

Разработчики)	Норман Мегилл
Написано в	ANSI C
Операционная система	Linux, Windows, macOS
Тип	Проверка документов с помощью компьютера
Лицензия	Стандартная общественная лицензия GNU (Creative Commons Всеобщее достояние Посвящение базам данных)
Интернет сайт	метамат.org

Метамат это формальный язык и соответствующая компьютерная программа ( корректор) для архивирования, проверки и изучения математических доказательств.^[1] Несколько баз данных доказанных теорем были разработаны с использованием Metamath, охватывающие стандартные результаты в логика, теория множеств, теория чисел, алгебра, топология и анализ, среди прочего.^[2]

По состоянию на июль 2020 года набор доказанных теорем с использованием Metamath является одним из крупнейших корпусов формализованной математики, содержащим, в частности, доказательства 74^[3] из 100 теорем «Формализация 100 теорем» вызов, став третьим после HOL Light и Изабель, но прежде Coq, Мицар, ProofPower, Худой, Nqthm, ACL2, и Нупрл. Существует как минимум 17 верификаторов для баз данных, использующих формат Metamath.^[4]

Язык метаматов

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

Дизайн языка Metamath ориентирован на простоту; язык, используемый для формулирования определений, аксиом, правил вывода и теорем, состоит только из нескольких ключевых слов, и все доказательства проверяются с использованием одного простого алгоритма, основанного на подстановке переменных (с необязательными оговорками, какие переменные должны оставаться различными после замены).^[5]

Основы языка

Набор символов, которые можно использовать для построения формул, объявляется с помощью $ c(постоянные символы) и $ v (переменные символы) утверждения; Например:

$ (Объявите постоянные символы, которые мы будем использовать $) $ c 0 + = -> () term wff | - $. $ (Объявите метапеременные, которые мы будем использовать $) $ v t r s P Q $.

Грамматика формул задается с помощью комбинации $ f (плавающие (переменные) гипотезы) и $ а (аксиоматическое утверждение) утверждения; Например:

$ (Укажите свойства метапеременных $) tt $ f term t $. tr $ f срок r $. ts $ f термин s $. wp $ f wff P $. wq $ f wff Q $. $ (Определить «wff» (часть 1) $) weq $ a wff t = r $. $ (Определить «wff» (часть 2) $) wim $ a wff (P ​​-> Q) $.

Аксиомы и правила вывода определены с помощью $ а заявления вместе с ${ и $} для определения объема блока и опционально $ e (основные гипотезы) утверждения; Например:

$ (Аксиома состояния a1 $) a1 $ a | - (t = r -> (t = s -> r = s)) $. $ (Аксиома состояния a2 $) a2 $ a | - (t + 0) = t $. $ {min $ e | - P $. maj $ e | - (P -> Q) $. $ (Определите правило вывода modus ponens $) mp $ a | - Q $. $}

Используя одну конструкцию, $ а операторов, для захвата синтаксических правил, схем аксиом и правил вывода предназначены для обеспечения уровня гибкости, аналогичного логические структуры более высокого порядка без зависимости от системы сложных типов.

Доказательства

Теоремы (и производные правила вывода) записываются с $ p заявления; например:

$ (Докажите теорему $) th1 $ p | - t = t $ = $ (Вот его доказательство: $) tt tze tpl tt weq tt tt weq tt a2 tt tze tpl tt weq tt tze tpl tt weq tt tt weq wim tt a2 tt tze tpl tt tt a1 mp mp $.

Обратите внимание на включение доказательства в $ p заявление. Это сокращает следующее подробное доказательство:

 1 тт            $ж срок т 2 цзы           $а срок 0 3 1,2 tpl       $а срок ( т + 0 ) 4 3,1 weq       $а wff ( т + 0 ) = т 5 1,1 weq       $а wff т = т 6 1 а2          $а |- ( т + 0 ) = т 7 1,2 tpl       $а срок ( т + 0 ) 8 7,1 weq       $а wff ( т + 0 ) = т 9 1,2 tpl       $а срок ( т + 0 )10 9,1 weq       $а wff ( т + 0 ) = т11 1,1 weq       $а wff т = т12 10,11 слабак     $а wff ( ( т + 0 ) = т -> т = т )13 1 а2          $а |- ( т + 0 ) = т14 1,2 tpl       $а срок ( т + 0 )15 14,1,1 а1     $а |- ( ( т + 0 ) = т -> ( ( т + 0 ) = т -> т = т ) )16 8,12,13,15 mp $а |- ( ( т + 0 ) = т -> т = т )17 4,5,6,16 mp   $а |- т = т

«Основная» форма доказательства опускает синтаксические детали, оставляя более традиционное представление:

1 а2             $а |- ( т + 0 ) = т2 а2             $а |- ( т + 0 ) = т3 а1             $а |- ( ( т + 0 ) = т -> ( ( т + 0 ) = т -> т = т ) )4 2,3 mp         $а |- ( ( т + 0 ) = т -> т = т )5 1,4 mp         $а |- т = т

Замена

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

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

Пошаговое доказательство

Вот подробный пример того, как работает этот алгоритм. Шаги 1 и 2 теоремы 2p2e4 в Metamath Proof Explorer (set.mm) изображены слева. Давайте объясним, как Metamath использует свой алгоритм подстановки, чтобы проверить, что шаг 2 является логическим следствием шага 1, когда вы используете теорему opreq2i. Шаг 2 утверждает, что ( 2 + 2 ) = ( 2 + ( 1 + 1 ) ). Это вывод теоремы opreq2i. Теорема opreq2i заявляет, что если А = B, тогда (C F A) = (C F B). Эта теорема никогда не появилась бы в такой загадочной форме в учебнике, но ее грамотная формулировка банальна: когда две величины равны, одна может заменить одну на другую в ходе операции. Чтобы проверить доказательство, Metamath пытается объединить (C F A) = (C F B) с ( 2 + 2 ) = ( 2 + ( 1 + 1 ) ). Есть только один способ сделать это: объединить C с 2, F с +, А с 2 и B с ( 1 + 1 ). Итак, теперь Metamath использует предпосылку opreq2i. В этой предпосылке говорится, что А = B. Как следствие своих предыдущих вычислений, Metamath знает, что А следует заменить на 2 и B к ( 1 + 1 ). Предпосылка А = B становится 2=( 1 + 1 ) и таким образом создается шаг 1. В свою очередь, шаг 1 объединен с df-2. df-2 это определение числа 2 и заявляет, что 2 = ( 1 + 1 ). Здесь унификация - это просто вопрос констант и проста (нет проблемы с заменой переменных). Итак, проверка завершена, и эти два шага доказательства 2p2e4 верны.

Когда Metamath объединяется ( 2 + 2 ) с B он должен проверить соблюдение синтаксических правил. Фактически B имеет тип класс таким образом, Metamath должен проверить, что ( 2 + 2 ) также набирается класс.

Проверка доказательства Metamath

Программа Metamath - это оригинальная программа, созданная для управления базами данных, написанными с использованием языка Metamath. Он имеет текстовый интерфейс (командная строка) и написан на языке C. Он может считывать базу данных Metamath в память, проверять доказательства базы данных, изменять базу данных (в частности, добавляя доказательства) и записывать их обратно в хранилище.

Оно имеет доказывать команда, которая позволяет пользователям вводить доказательство, а также механизмы поиска существующих доказательств.

Программа Metamath может преобразовывать операторы в HTML или TeX обозначение; например, он может выводить modus ponens аксиома из set.mm как:

${displaystyle vdash varphi quad & quad vdash (varphi ightarrow psi) quad Rightarrow quad vdash psi}$

Многие другие программы могут обрабатывать базы данных Metamath, в частности, существует не менее 17 верификаторов доказательств для баз данных, использующих формат Metamath.^[6]

Базы данных Metamath

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

Metamath Proof Explorer

Metamath Proof Explorer

Доказательство Metamath Proof Explorer
Тип сайта	Интернет-энциклопедия
Штаб-квартира	Соединенные Штаты Америки
Владелец	Норман Мегилл
Сделано	Норман Мегилл
URL	нас.metamath.org/ mpeuni/ ммсет.html
Коммерческий	Нет
Постановка на учет	Нет

The Metamath Proof Explorer (записано в set.mm) является основной и, безусловно, самой большой базой данных, по состоянию на июль 2019 года в ее основной части насчитывалось более 23000 доказательств. Она основана на классических логика первого порядка и ZFC теория множеств (с добавлением Теория множеств Тарского-Гротендика при необходимости, например в теория категорий). База данных поддерживается более двадцати лет (первые доказательства в set.mm датированы августом 1993 г.). База данных содержит разработки, среди других областей, теории множеств (ординалы и кардиналы, рекурсия, эквиваленты выбранной аксиомы, гипотеза континуума ...), построение систем действительных и комплексных чисел, теория порядка, теория графов, абстрактная алгебра, линейная алгебра, общая топология, вещественный и комплексный анализ, гильбертовы пространства, теория чисел и элементарная геометрия. Эта база данных была впервые создана Норманом Мегиллом, но по состоянию на 2019-10-04 в ней участвовало 48 участников (включая Нормана Мегилла).^[7]

Metamath Proof Explorer ссылается на многие учебники, которые можно использовать вместе с Metamath.^[8] Таким образом, люди, заинтересованные в изучении математики, могут использовать Metamath в связи с этими книгами и проверить соответствие доказанных утверждений литературным данным.

Интуиционистский исследователь логики

Эта база данных развивает математику с конструктивной точки зрения, начиная с аксиом интуиционистская логика и продолжая аксиомные системы конструктивная теория множеств.

Исследователь новых основ

Эта база данных развивает математику Куайна. Новые основы теория множеств.

Исследователь логики высшего порядка

Эта база данных начинается с логика высшего порядка и выводит эквиваленты аксиомам логики первого порядка и теории множеств ZFC.

Базы данных без проводников

На веб-сайте Metamath есть еще несколько баз данных, которые не связаны с исследователями, но, тем не менее, заслуживают внимания. База данных peano.mm написано Роберт Соловей формализует Арифметика Пеано. База данных нац.мм^[9] формализует естественный вычет. База данных miu.mm формализует MU головоломка на основе формальной системы MIU, представленной в Гедель, Эшер, Бах.

Старшие исследователи

На веб-сайте Metamath также есть несколько старых баз данных, которые больше не поддерживаются, например, "Hilbert Space Explorer", в котором представлены теоремы, относящиеся к Гильбертово пространство теории, которые теперь объединены в Metamath Proof Explorer и "Quantum Logic Explorer", который разрабатывает квантовая логика начиная с теории ортомодулярных решеток.

Естественный вычет

Поскольку Metamath имеет очень общее понятие о том, что такое доказательство (а именно дерево формул, связанных правилами вывода), и никакая конкретная логика не встроена в программное обеспечение, Metamath может использоваться с различными видами логики, такими как логики или последовательности гильбертова. логики или даже с лямбда-исчисление.

Однако Metamath не предоставляет прямой поддержки для естественный вычет системы. Как отмечалось ранее, база данных нац.мм формализует естественный вывод. The Metamath Proof Explorer (со своей базой данных) set.mm) вместо этого используйте набор соглашений, которые позволяют использовать подходы естественного вывода в логике Гильберта.

Другие работы, связанные с Metamath

Проверки доказательств

Используя идеи дизайна, реализованные в Metamath, Раф Левиен реализовал очень маленькую проверку корректуры, mmverify.py, всего 500 строк кода Python.

Ghilbert - похожий, но более сложный язык, основанный на mmverify.py.^[10] Левиен хотел бы реализовать систему, в которой несколько человек могли бы сотрудничать, и его работа подчеркивает модульность и связь между небольшими теориями.

Используя основополагающие работы Левьена, многие другие реализации принципов проектирования Metamath были реализованы для самых разных языков. Юха Арпиайнен реализовал собственную проверку корректуры в Common Lisp называется Бурбаки^[11] и Марникс Клоостер закодировал контрольную проверку Haskell называется Хм.^[12]

Хотя все они используют общий подход Metamath к кодированию формальной системы проверки, они также реализуют собственные новые концепции.

Редакторы

Мел О'Кат разработал систему под названием Mmj2, что обеспечивает графический пользовательский интерфейс для подтверждения входа.^[13] Первоначальная цель Мела О'Ката заключалась в том, чтобы позволить пользователю вводить доказательства, просто вводя формулы и позволяя Mmj2 найдите соответствующие правила вывода, чтобы связать их. В Metamath, напротив, вы можете вводить только названия теорем. Вы не можете вводить формулы напрямую. Mmj2 также есть возможность вводить доказательство вперед или назад (Metamath позволяет вводить доказательство только назад). более того Mmj2 имеет настоящий грамматический парсер (в отличие от Metamath). Эта техническая разница приносит пользователю больше комфорта. В частности, Metamath иногда колеблется между анализом нескольких формул (большинство из которых бессмысленны) и просит пользователя сделать выбор. В Mmj2 это ограничение больше не существует.

Существует также проект Уильяма Хейла по добавлению графического пользовательского интерфейса в Metamath под названием Ммиде.^[14] Пол Чепмен, в свою очередь, работает над новым браузером доказательств, в котором есть подсветка, позволяющая увидеть указанную теорему до и после того, как была сделана подстановка.

Milpgame - это помощник по проверке и проверка (он показывает сообщение только о том, что что-то пошло не так) с графический пользовательский интерфейс для языка Metamath (set.mm), написанного Филипом Чернатеску, это приложение Java с открытым исходным кодом (лицензия MIT) (кроссплатформенное приложение: Window, Linux, Mac OS). Пользователь может войти в демонстрацию (доказательство) в двух режимах: вперед и назад относительно утверждения, которое нужно доказать. Milpgame проверяет, правильно ли сформирован оператор (имеет синтаксический верификатор). Он может сохранить незавершенные доказательства без использования теоремы фиктивной ссылки. Демонстрация представлена ​​в виде дерева, операторы показаны с использованием определений html (определенных в главе о наборе). Milpgame распространяется как Java .jar (обновление 24 JRE версии 6, написанное в IDE NetBeans).

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

• Автоматическая проверка документов
• Помощник доказательства
• Система Мицар

Рекомендации

внешняя ссылка

• Метамат: Официальный веб-сайт.
• Что математики думают о Metamath: мнения о Metamath.