Формальная система — это абстрактная структура и формализация аксиоматической системы , используемая для вывода теорем из аксиом с помощью набора правил вывода . [1]
В 1921 году Давид Гильберт предложил использовать формальные системы в качестве основы знаний в математике . [2]
Термин «формализм» иногда является приблизительным синонимом формальной системы , но он также относится к определенному стилю записи , например, к скобочной записи Поля Дирака .
Формальная система имеет следующее: [3] [4] [5]
Формальная система называется рекурсивной (т.е. эффективной) или рекурсивно перечислимой, если множество аксиом и множество правил вывода являются разрешимыми множествами или полуразрешимыми множествами соответственно.
Формальный язык — это язык, который определяется формальной системой. Как и языки в лингвистике , формальные языки обычно имеют два аспекта:
Обычно только синтаксис формального языка рассматривается через понятие формальной грамматики . Две основные категории формальной грамматики — это генеративные грамматики , которые представляют собой наборы правил для записи строк в языке, и аналитические грамматики (или редуктивные грамматики [6] [7] ), которые представляют собой наборы правил для анализа строки с целью определения ее принадлежности к языку.
Дедуктивная система , также называемая дедуктивным аппаратом , [8] состоит из аксиом (или схем аксиом ) и правил вывода , которые могут быть использованы для вывода теорем системы. [9]
Такие дедуктивные системы сохраняют дедуктивные качества в формулах , которые выражены в системе. Обычно качество, которое нас интересует, — это истина в противовес лжи. Однако вместо этого могут сохраняться другие модальности , такие как обоснование или вера .
Чтобы поддерживать свою дедуктивную целостность, дедуктивный аппарат должен быть определяемым без ссылки на какую-либо предполагаемую интерпретацию языка. Цель состоит в том, чтобы гарантировать, что каждая строка вывода является просто логическим следствием строк, которые ей предшествуют. Не должно быть ни одного элемента какой-либо интерпретации языка, который был бы связан с дедуктивной природой системы.
Логическое следствие (или вывод) системы из ее логического основания — это то, что отличает формальную систему от других, которые могут иметь некоторую основу в абстрактной модели. Часто формальная система будет основой или даже отождествлена с более крупной теорией или областью (например, евклидовой геометрией ), соответствующей использованию в современной математике, например, теории моделей . [ необходимо разъяснение ]
Примером дедуктивной системы могут служить правила вывода и аксиомы относительно равенства, используемые в логике первого порядка .
Два основных типа дедуктивных систем — это системы доказательств и формальная семантика. [8]
Формальные доказательства — это последовательности правильно сформированных формул (или WFF для краткости), которые могут быть либо аксиомой , либо продуктом применения правила вывода к предыдущим WFF в последовательности доказательств. Последний WFF в последовательности распознается как теорема .
Как только формальная система задана, можно определить множество теорем, которые могут быть доказаны внутри формальной системы. Это множество состоит из всех WFF, для которых есть доказательство. Таким образом, все аксиомы считаются теоремами. В отличие от грамматики для WFF, нет гарантии, что будет процедура принятия решения для решения, является ли данное WFF теоремой или нет.
Точка зрения, что генерация формальных доказательств — это всё, что есть в математике, часто называется формализмом . Дэвид Гильберт основал метаматематику как дисциплину для обсуждения формальных систем. Любой язык, который используется для обсуждения формальной системы, называется метаязыком . Метаязык может быть естественным языком или он может быть частично формализован сам по себе, но он, как правило, менее полно формализован, чем формальный языковой компонент формальной системы, который затем называется объектным языком , то есть объектом рассматриваемого обсуждения. Понятие теоремы, только что определённое, не следует путать с теоремами о формальной системе , которые, во избежание путаницы, обычно называются метатеоремами .
Логическая система — это дедуктивная система (чаще всего логика первого порядка ) вместе с дополнительными нелогическими аксиомами . Согласно теории моделей , логической системе могут быть даны интерпретации , которые описывают, удовлетворяет ли данная структура — отображение формул в определенное значение — правильно сформированной формуле. Структура, которая удовлетворяет всем аксиомам формальной системы, известна как модель логической системы.
Логическая система — это:
Примером логической системы является арифметика Пеано . Стандартная модель арифметики устанавливает областью дискурса неотрицательные целые числа и придает символам их обычное значение. [10] Существуют также нестандартные модели арифметики .
Ранние логические системы включают индийскую логику Панини , силлогистическую логику Аристотеля, пропозициональную логику стоицизма и китайскую логику Гунсуня Луна (ок. 325–250 до н. э.). В более позднее время вклад внесли Джордж Буль , Август Де Морган и Готтлоб Фреге . Математическая логика была разработана в Европе 19 века .
Давид Гильберт инициировал формалистское движение, называемое программой Гильберта , как предлагаемое решение фундаментального кризиса математики , которое в конечном итоге было смягчено теоремами Гёделя о неполноте . [2] Манифест КЭД представлял собой последующую, пока безуспешную, попытку формализации известной математики.
Медиа, связанные с формальными системами на Wikimedia Commons
