Главная » Просмотр файлов » Гильберт, Бернайс - Основания математики. Теория доказательств

Гильберт, Бернайс - Основания математики. Теория доказательств (947376), страница 114

Файл №947376 Гильберт, Бернайс - Основания математики. Теория доказательств (Гильберт Д. - Основания математики и прочие работы) 114 страницаГильберт, Бернайс - Основания математики. Теория доказательств (947376) страница 1142013-09-15СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 114)

(1)), а потому, ввиду выводимости формулы 9! -Ф- (6-у. Я а 6) и формула Я-Р(6-+.6). Укажем на еще один вариант формулировки, которую можно придать полученной нами теореме, характеризующей позитивно тождественные 1-К-формулы как формулы, выводимые с помощью применен " менений к 1-К-формулам схем (8,) — (8,). Заметим, что выводы, производимые в области 1 К.формул при помощи схем (8,) — (,), — 8 протекают совершенно аналогично выводам схем формул, производимым прн помощи указанных пяти схем безотносительно акой-либо конкретной области формул, исключительно путем оперирования с обозначениями формул, связываемые дру друг с гом знаками имплнкации и конъюнкции.

Зто приводит нас к следующей теореме: Схемы формул, выводимые из схем (8,) — (84) без указания какой-лнбо конкретной области формул, совпадают со схемами, получающимися из позитивно тождественных 1-К-формул в результате замены формульиых переменных буквами, обозначающими произвольные формулы. й 3. Тождественные 1-К-й1-формулы В проведенном нами в гл. Ч Ц 5, п. б)1 рассуждении пока отсутствует доказательство утверждения ') о том, что любая схема формул, соответствующая тождественно истинной формуле исчисления высказываний и не содержащая дизъюнкции, выводима с помощью схем (8,) — (84), схем вывода й)-э 6 Я-ъ -16 ~ (Я сс 6) Я-м )6 схемы формул и правила замены любой эквивалентности Я 6 соответствую- 4) См.

с, 433 — 434. (84) )Я 1(Я 8 6) (8,) Я- ~6 ) ~Я вЂ” мЯ. (8,) Легко видеть, что применение этих схем к формулам исчисления высказываний дает только тождественно истинные формулы, Мы должны доказать, что для 1-К-Х-формул имеет место "бращение этого утверждения, а именно что любая тождественно "сти"ная 1-К-К-формула может быть выведена с помощью применений схем (8,) — (8,) к [-К-д-формулам. щим ей выражением (Я -+.6) Зс(6-+.Я) (и, разумеется, этого выражения указанной эквивалентностью]. Б этом утверждении мы можем заменить схемы формул, соответствующие тождественно истинным формулам, самими этими формулами, считая, что используемые в выводах схемы применяются к формулам исчисления высказываний, ке содержащим знака дизъюнкции. Это вытекает из упомянутого в конце предыдущего параграфа результата, утверждающего, что выводы, производимые с помощью схем, применяемых к формулам исчисления высказываний, протекают совершенно аналогично выводам, применяемым к схемам формул, получающимся из соответствующих формул в результате замены формульных переменных буквами, обозначающими произвольные формулы.

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

Формулы этого рода мы будем кратко называть 1-К-М-формулами. Наряду со схемами (8,) — (8,) рассмотрим еще следующие три схемы вывода: П!1 ТОЖДЕСТВЕННЫЕ 1.К-М-ФОРМУЛЫ 534 П РИ ЛОЖЕН ИЕ 4з1 Для этого мы воспользуемся одной модификацией конъюнктнвной нормальной формы ') обычного исчисления высказываний ').

Как мы знаем, при истолковании формул исчисления высказываний, получающемся на основе понимания связок исчисления высказываний как нстинностных функций, любая формула равнозначна некоторой конъюнкции, члены которой являются либо формульными переменными, либо отрицаниями формульных переменных — выражения этих двух типов мы будем называть п римарными выражениями'),— либо дизъюнкциями, состоящими из нескольких примарных выражений. При этом упомянутая равнозначность имеет место в том смысле, что соответствующая конъюнкция задает ту же самую истинностную функцию, что и первоначальная формула. Любая дизъюнкция примарных выражений задает ту же истинностную функцию, что и отрицание некоторой конъюнкции примарных выражений.

Тем самым каждая формула исчисления высказываний в указанном смысле равнозначна такой конъюнкции, у которой каждый член является либо примарным выражением, либо отрицанием конъюнкции примарных выражений. Формулу такого рода в данном' рассмотрении мы будем называть конъюн кти в но норм и рован ной, а какую либо конъюнктивно нормированную формулу, равнозначную формуле 9(, мы будем называть конъюнктиано нормированной формулой, связанной с формулой 6.

По конъюнктивно нормированной формуле можно непосредственно установить, является ли она тождественно истинной, Действительно„ это, как легко убедиться, имеет место тогда и только тогда, когда каждый ее дизъюнктивный член является отрицанием 1) См. т. 1, с, 82 — 85 н 96 — 98. я) Как некоторую моднфннапню получаемого с помощью конъюнктнвной нормальной формы метода доказательства полноты систем аксиом исчисления высказываний можно рассматривать доказательство, которое недавно дали ' Гермес н Шалая для первоначально установленного Лукасевнчем факта, что формулы Г» вместе с формулой () А -» ) В)-ь(В -~ А) прн использовании подстановок н схемы заключения представляют собой систему, достаточную для вывода всех тождественно истинных формул нсчнслення высказываний, построенных с помощью одних' толька знаков нмплнкацнн н отрицания. Смл Нег»лез Н,, 8сь о! я Н.

Е!и пеаег»о1!я!апб!Е)ге1!зьеже)я Гйг бая ге., бцх!ег!е Ргейеясье Ах!ошепяуя!оп бея Апяяайеп)га!йй!я. — Рогзсьппйеп хпг 1.ой!й ппб япг с»гцпб!ейная бег ехай!еп Цг!яяепясьа((еп, !937, № !. Роль аналога конъюнкции»простых» днзъюнкцнй в случае канъюнктнвной нормальной формы здесь нграют конечные множества нмплнкацнй некоторого специального вида. ») Это понятие прнмарного выражения не находится нн в какой сааза с введенным в т. 1 (с. 188 н 280) понятием прнмарной Е)армрлы.

такой конъюнкции, у которой имеются два члена, один из которых является отрицанием другого. Такая структура тождественно истинных конъюнктивно нормированных формул позволяет заключить, что каждая из них выводима с помощью применяемых к 1-К-)х)-формулам схем (Зг) — (Зя). Действительно, если Й является конъюнкцией примарных выражений, среди которых имеется некоторое выражение Н вместе с его отрицанием, то с помощью схем (51) — (Бз) будут выводимы ') формулы й-+!! н й — ь )Ц) но из них с помощью схемы (За) мы получим формулу ) Й. Поэтому тождественно истинная конъюнктивно нормированная формула является коньюнкцней формул, выводимых с помощью схем (Ях) — (Бе), а из этих формул с помощью схем (Ях) — (Зя) может быть выведена и сама эта конъюнктивно нормированная формула.

Если мы теперь заметим, что конъюнктивно нормированная формула, связанная с тождественной истинной формулой, является тождественно истинной, то отсюда яо только что доказанному получится, что для обоснования нашего утверждения о выводи- мести любой тождественно истинной 1-К-)х)-формулы путем применения схем (Ят) †(5я) к 1-К-ц»)-формулам достаточно показать, что для каждой 1-К-Х-формулы можно указать такую связанную с ней конъюнктнвно нормированную формулу, которая дедуктивно равна ей относительно схем (51) — (Ья), применяемых к 1-К-)ч(-формулам.

Это мы проделаем следующим образом: сначала мы укажем некоторую процедуру, сопоставляющую каждой 1-К-Х-формуле некоторую связанную с ней конъюнктивно нормированную формулу, а затем покажем, что формула, полученная при помощи этои процедуры, дедуктивно равна относительно схем (51) — (Яз) исходной формуле, Для того чтобы изложить упомянутую процедуру, мы воспользуемся одной классификацией формул, построенных нз формульных переменных с помощью знаков конъюнкции и отрицания (такие формулы мы будем называть К-)ч)-формулами).

Каждой Такой формуле мы припишем следующим образом некоторый параметр, который назовем ее порядком. Знак отрицания будет назы- 1 ) Г)рн дедуктивных преобразованнях конъюнкций нужно помаять, что а саответствнн с вашими соглашениями бесскобочная конъюннцня Г»»аг...мз( авл 1 " в вляется сокращением лля выра»кення (" ° (Ц»ййя)й ..бгйн 1)йяв. ТОЖДЕСТВЕННЫЕ 1-К-Н.ФОРМУЛЫ пн ПРИЛОЖЕНИЕ ваться примариым, если он входит в примарное выражение. Далее, два или большее число знаков отрицания, входящих в какую-либо К-И-формулу, будут называться н а с л а и в а ющимися друг на друга, если по меньшей мере одна формульная переменная данной формулы попадает в область действия каждого из этих знаков. Порядок данной К-Ы-формулы мы определим как максимальное число входящих в нее наслаивающихся друг на друга непримарных отрицаний.

Согласно этому определению примарное выражение всегда имеет нулевой порядок. Отрицание какой-либо К-М-формулы и-го порядка, не состоящей из одной только формульной переменной, является формулой (и+1)-го порядка, а порядок конъюнкции К-(ч-формул равен максимальному из порядков ее членов. К-1ч-формула является конъюнктивно нормированной тогда и только тогда, когда ее порядок не превосходит единицы. Далее, из определения порядка можно извлечь следующие два предложения: 1. Любая К-М-формула порядка выше первого содержит в качестве составной части по меньшей мере одно отрицание какой- либо формулы первого порядка.

Характеристики

Тип файла
DJVU-файл
Размер
7,04 Mb
Тип материала
Предмет
Учебное заведение
Неизвестно

Список файлов книги

Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6418
Авторов
на СтудИзбе
307
Средний доход
с одного платного файла
Обучение Подробнее