Новая философская энциклопедия. Том первый

ДОКАЗАТЕЛЬСТВ ТЕОРИЯ— раздел современной математической логики, изучающий свойства и преобразования формальных доказательств, т.е. формальных объектов, синтаксическая правильность которых гарантирует семантическую. Это определение унифицирует множество разнородных понятий формального доказательства, существующих в математической логике: последовательности формул, графы, диаграммы и т. д. В некоторых областях современного общества понятие доказательства стало практически тоже формальным. В частности, понятие документа в юриспруденции включает в себя прежде всего правильность его формы, которая делает его содержание истинным по определению. Однако формальное определение доказательства может в некоторых случаях быть содержательно неадекватным. Часто составленный по всей форме документ прикрывает результат абсолютно незаконных действий либо обмана. Доказательств теория первоначально появилась в связи с программой Гильберта (см. Формализм), с задачей обоснования того, что каждый формальный вывод содержательно интерпретируемого (реального) утверждения дает содержательно правильный результат, включающий в случае необходимости и соответствующее построение. Одним из шагов по направлению к данной цели казалось доказательство непротиворечивости формальных теорий. Это средство незаметно подменило собой цель, и поэтому первым громко прозвучавшим результатом теории доказательств была теорема Геделя о неполноте и ее следствие — о недоказуемости непротиворечивости. Важным позитивным результатом является теорема Я. С. Новикова: утверждение о существовании результата алгоритмического построения, доказанное в классической арифметике, дает верное следствие, и в том числе (грубую) оценку числа необходимых шагов построения. Эта теорема стала основой целого класса результатов современной теории доказательств, обосновывающих совпадение классической истинности и конструктивной обоснованности для многих видов утверждений (в последнее время такие результаты все чаще доказываются методами моделей теории). Следующим шагом в развитии теории доказательств, надолго предопределившим ее магистральное направление, стала формулировка Г. Генценом исчисления секвенций и естественного вывода и доказательство им теоремы нормализации для классического и интуиционистского исчисления секвенций. Содержательно теорема нормализации означает возможность перестроить любой формальный вывод в нормализованный вывод без лемм. Было ясно, что понятие нормализованного вывода применимо и к естественному выводу, но точную формулировку дал только Д. Правиц (1965). Хотя формально определение Правица является сложным, содержательный смысл его вполне прозрачен. Логических правил для каждой связки обычно два: правило ее введения, показывающее, как доказывать утверждения данного вида, и правило удаления, показывающее, как их применять. Напр., для импликации в классической и во многих других логиках правила имеют вид: Допустим А В, исходя из А А,А=>В А^В В Во втором из данных правил формула А => В используется именно как импликация, формула же А не анализируется и может быть любой. Для того чтобы подчеркнуть данный факт, А => В называется главной посылкой правила удаления импликации. В выводе есть окольный путь, если результат правила введения используется как главная посылка в соответствующем правиле удаления, а такая пара правил называется вершиной окольного пути. Если в выводе нет вершин окольных путей, то он называется прямым либо нормализованные. Теорема нормализации гласит, что любой вывод можно перестроить в нормализованный. Длительное время разные формы нормализации являлись ведущей темой исследований в теории доказательств. Расширялся класс исчислений и теорий, для которых устанавливалась норма- лизуемость выводов. Сейчас она обоснована для теории типов и для множества неклассических логик. Устанавливались и оценки соотношения длины нормализованного и исходного выводов. Здесь была подтверждена правота Гильберта о необходимости идеальных объектов для реальных результатов. В частности, В. А. Оревков построил пример последовательности формул, таких, что доказательство я-й формулы с окольными путями происходит приблизительно за 13« шагов, а нормализованный вывод либо вывод методом резолюций должен делать не менее 22" (п раз) шагов. В косвенном доказательстве (п + 1)-й формулы используется промежуточный результат, содержащий в два раза больше связок, чем в доказательстве л-й. В исчислении высказываний оценка увеличения длины вывода чуть «оптимистичней» — она экспоненциальна. В свою очередь изучение свойств самих преобразований, используемых при нормализации выводов, в частности показало, что предложенная Правицем система операций

682