Cтраница 1
Метод натурального вывода позволяет оперировать с формальными объектами, представляющими рассуждения. [1]
Эта система ( натурального вывода) является адекватной: если выводы в числителе произвольного правила общезначимы, то вывод в знаменателе того же правила также общезначим. [2]
Введенная в исчислении высказываний система натурального вывода ( § 2.1.7) обобщается на исчисление предикатов путем добавления правил введения и удаления кванторов общности и существования. [3]
Описана дедуктивная система, в которой аспекты резолюции ( в частности, унификация и использование функций Сколема) соединены с аспектами натурального вывода. Действие системы удачно сравнивается с наилучшими программами доказательств теорем исчисления предикатов. [4]
Затем Правицу [3] для исчисления натуральных выводов удалось получить даже более сильный результат: а именно, оказалось, что для системы редукций Правица всякий натуральный вывод приводится к нормальному виду произвольной последовательностью редукций. Что касается полного исчисления секвенций, то Цукер привел конкретный пример бесконечной последовательности редукций ( из предложенного им набора редукций), не ведущий к нормальному выводу. [5]
Для подобных программ, по всей видимости, можно разработать системы автоматического поиска вывода, действующие, быть может, во взаимодействии с пользователем. Обе они основаны на системах натурального вывода. Наконец, вывод логических процедур был применен также Кларком и ван Эмденом ( 1981) к доказательству правильности традиционных программ. Они показали, как можно выводить логические процедуры, представляющие логическое содержание блок-схем программ, а затем верифицировать последние посредством доказательства того, что найденные процедуры удовлетворяют заданным спецификациям. [6]
Первоначально формализации логических и мате-матич. Логические исчисления); решающее продвижение в этом направлении составило исчисление натуральных выводов ( см. Генцена формальная система ], имитирующее форму обычных математич. [7]
Точнее, можно показать, что доказательство устранимости сечения из выводов ограниченной сложности само формализуется в интуиционистской простой теории типов с аксиомой бесконечности. Мы проводим доказательство в стиле Жирара-Мартин - Лефа-Правица для обычного исчисления секвенций, а не для натурального вывода или систем типа секвенциальной системы Шютте ( см., например, Освальд [2], Буххольц [1]), метод доказательства распространен на теорию с правилом объемности и, наконец, наше доказательство имеет специальную алгебраическую форму. В действительности строится конкретная модель для рассматриваемого исчисления такая, что из истинности секвенции в этой модели следует ее выводимость без сечений. Логика модели образует алгебру с пополнением, так что модель является примером применения алгебр с пополнением в конкретных исследованиях по теории интуиционистского вывода. [8]
Затем Правицу [3] для исчисления натуральных выводов удалось получить даже более сильный результат: а именно, оказалось, что для системы редукций Правица всякий натуральный вывод приводится к нормальному виду произвольной последовательностью редукций. Что касается полного исчисления секвенций, то Цукер привел конкретный пример бесконечной последовательности редукций ( из предложенного им набора редукций), не ведущий к нормальному выводу. [9]
В настоящее время не существует полностью автоматической реализации, способной строить выводы эффективных логических программ из произвольных спецификаций, и по всей видимости в ближайшем будущем они не появятся. Тем не менее имеется ряд реализаций, которые могут удовлетворительно работать во взаимодействии с пользователем, причем они способны не только проверять собственные выводы пользователя, но и сами проявлять некоторую инициативу, направленную на построение выводов. В такого рода реализациях, обсуждаемых Ханссоном и Тарнлундом ( 1979), используется, как правило, система построения натурального вывода, и поэтому они могут обрабатывать спецификации, представленные в неограниченном языке логики первого порядка. Пока у нас еще нет достаточно полного представления о том, как связана общая проблема эффективного управления синтезом программ с уровнем ограничений, накладываемых на язык спецификаций. Для работы с неограниченной логикой первого порядка неизбежно потребуется довольно богатый запас различных правил вывода, наличие которых может привести в ходе каждого конкретного синтеза к появлению большого числа аморфных на вид и не ведущих к цели выводов. [10]
Эти логические средства можно применять довольно непосредственно. Логические языки служат опорой для выражения знаний, которые также представлены декларативно в виде логических выражений. Рассуждение определяется как операция доказательства общезначимости или выполнимости логического утверждения. Рассуждения осуществляются окольным путем, посредством манипулирования дедуктивными компонентами рассматриваемой логической системы. Например, такими компонентами являются классические аксиоматические системы ( § § 2.1.3, 2.1.8), системы натурального вывода ( § § 2.1.7, 2.1 9) или семантика рассматриваемой логической системы. Так как процесс доказательства должен быть автоматизирован, то это очень часто реализуется методами поиска, причем производится систематическая манипуляция с дедуктивной компонентой. [11]