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

Гильберт, Бернайс - Основания математики. Логические исчисления и формализация арифметики (947375), страница 25

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

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

Следует обратить внимание на тот факт, что во всех этих доказательствах независимости определение символа-+. остается прежним, так что каждая приведенная в таблице оценка обладает тем свойством, что если две формулы Я и 1О -э 2 тождественно принимают значение а, то и Й также обладает этим свойством.

Таблицу доказательств независимости для формул Н вЂ” т' мы аададим следующим образом: $ 11 МЕТОД ОЦЕНОК И ДОКАЗАТЕЛЬСТВА НЕЗАВИСИМОСТИ тээ ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИИ 1ГЛ. 111 $08 Из приведенных в атой таблице оценок моясно также извлечь и некоторые дополнительные следствия. Например, оценка, доказывающая независимость формулы 11 3), вместе с тем показывает так«ке, что в системе формул 1 — У эту формулу нельзя заместить формулой (А -«. В) & (А «- С) «- (А — «- В & С); действительно, при этой оценке, которая задается определяющим равенством А &В=р, рассматриваемая формула, равно как и формулы1, 11 1), 2), 111— У, всякий раэ принимает значение а, в то время как для формулы 11 3) это неверно. Далее, используемая для доказательства независимости формулы У 3) оценка, задаваемая определяющим равенством )А=а, показывает, что формула Ч 3) не может быть Выведена из формул 1 — 1У, У 1), 2) и формулы АУ ~А и что, стало быть, в системе формул 1 — Ч формулу У 3) нельзя ааместить формулой А 1/ ~А.

Действительно, при упомянутой оценке все формулы 1 — 1У, У 1), 2), а также формула А 1/ ~ А тождественно принимают значение а, в то время как для У 3) это места не имеет. Теперь осталось провести доказательства независимости для формул группы 1. Здесь дело обстоит не так просто, как в предыдущих случаях, ввиду того, что символ-«- встречается в формулах всех пяти групп. Независимость формул 1 1), 2), 3) мы докажем с помощью трех существепно отличающихся друг от друга оценок. Общим у этих оценок будет то, что всякий раз в качестве единственного выделенного значения мы будем брать а. Условие, состоящее в том, что если Я н б-э;ь тождественно принимают значение а, то и ь тождественно принимает это значение, будет выполняться вследствие того, что во всех трех оценках выражение а -«.

А для А ~ и будет принимать значение, отличное от и. Далее, эти оценки будут обладать следующим, общим для них свойством: Для любых значений А и В имеют место равенства А&В=В&А, А«/В=В)/А, А В=В А, А-«А=а, А&А=-А, А ««/А=А, А А=и, А -«-а=а, р — «-А=а, А&а=-А, А ~/а=а, А&р=(6, А 1/р=А, а также 1а = р, 1() = и. Эти условия, как легко убедиться, совместимы друг с другом. Получающиеся из них определяющие равенства мы будем называть основными равенствами. К ним всякий раз будут добавляться те или иные дополнительные определяющие равенства. Для доказательства независимости формулы 1 1) мы возьмем оценку с четырьмя значениями и, р, у, 6.

Для нее дополнительными определяющими равенствами будут Для так определенной оценки значение каждой из формул 1 2), 3), П вЂ” У тождественно равняется и. В целях облегчения проверки следует заметить, что: А-«- В всегда принимает одно из значений и или р; А & В и А ««/ В всегда принимают одно из значений А, В. Следует также отметить еще и ту особенность нашей оценки, что для выражений, построенных из а и р с помощью наших пяти логических символов, она согласуется с нормальной оценкой. То, что формула 1 1) А — «- ( — ~ А) не всегда принимает значение и, можно обнаружить при помощи различных систем значений переменных: например, при А = 6 и В = а рассматриваемая формула принимает значение р.

Для указанных значений А и В значение р принимает также и формула А -«. (В -«. А & В). Отсюда следует, что она не может быть выведена из формул 1 2), 3), 11 — У. Тем же самым способом можно убедиться, что формулы А ~/ 1А, 1(А & 1А), (А †«- ~А) †«- 1А, А †«-( 1А -э 1В) также не выводятся из формул 1 2), 3), 11 — Ч. Далее, иэ того обстоятельства, что при рассматриваемой оценке формулы А «- А и В -«- (А -«. А) тождественно принимают значение а, следует, что в системе формул 1 — У формулу 1 1) а — р=р, ау =(6=0, у-«б=р, 17=6, А-В=р у=~, и- 6=(), 6- у=и, уЧ6=Ъ ~6=у, для А чь В.

$43 МЕТОД ОЦЕНОК И ДОКАЗАТЕЛЬСТВА НЕЗАВИСИМОСТИ 1гл. н> ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИИ нельзя заместить формуламиА-+ А и В- (А- А). Формула 11) будет невыводимой и в том случае, если к формулам 1 2), 3), 11 — Ч добавить не только формулы А ->- А и  — (А >- А), но, кроме того, еще и формулы А Ч' > А, ~ (А & ~ А), а такясе схему И-' 1сс . Действительно, в этом случае выводимыми оказались ~и бы лишь такие формулы, которые при рассматриваемой оценке принимают только значения а и у. Независимостьформулы1 2) устанавливается с помощью оценки с тремя зкачениями и, Р и у, впервые рассмотренной Лукасевичем. Для этой оценки дополнительные равенства имеют следующий вид: и р = р, и у = у, и р = р, и1-у=-у, р1-у =у, ~у=у (А & В и А Ч' В вполне определяются уже при помощи основных равенств).

То, что эта оценка доставляет каждой из формул 1 1), 3), 11— — Ч значение а, легко усматривается из следующей арифметической интерпретации: и, р и у суть соответственно числа О, ! и — „; А — ~ В при А -~В представляет собой арифметическую разность  — А, а в противном случае А — ~ В равно О; А & В представляет собой наибольшее, а А 1/  — наименьшее из значений А и В; А В есть абсолютная величина А — В; 1 А равно 1 — А.

Формула 1 2): (А — +- (А -~ В)) >. (А — ~ В) принимает при этой оценке значение у, если положить А = у и В=)). Точно так же устанавливается, что ни одна из формул (А -+- (А ->. В)) ->. (А & А ->- В), А ~/ 1А, ~(А & 1А), (А — >- 1А) >- ~А не является тождественно равной и. Таким образом, эти формулы не выводимы из формул 1 1), 3), 11 — Ч. И наконец, чтобы доказать неаависимость формулы 1 3), возьмем оценку с четырьмя значениями и, р, у, 6 и со следующими допол- нительными определяющими равенствами: ~у=6, ~6 =у, у & 6 = р, у 'Ч' 6 = и, а ->.

р = у, у ->- (1 = 6, 6->- б = у; далее, для А, В~~, А~В А-~В=В; наконец, для любых значений А и В А В = (А ->. В) & ( — >. А). Легко убедиться, что эти равенства совместимы друг с другом, а также и с основными равенствами, и что рассматриваема н оценка вполне ими определяется. 2 1 Теперь можно проверить, что при этой оценке формулы 1 1), ), 1 — Ч тождественно принимают значение а. Между тем формула 1 3): (А ->- В) — +- ((В -+.

С) -э (А ->- С)) при А = а, В =- р и С = 6 принимает значение 6. При этой оценке формула А -~ ((А ->- В) — В) при А = а и В = р принимает значение 6. Следовательно, эта формула,не может быть выведена из системы формул 1 — Ч без использования формулы 1 3). Тем самым независимость всех формул 1 — Ч доназана. В до- полнение к сказанному, воспользовавшись еще одной оценкой, мы покажем, что формула ((А — >- В) ->. А) — >- А, которую мы приводили выше >) в качестве примера тождественно истинной, но не позитивно тождественной импликативной форму- лы, не может быть выведена из системы формул 1 — Ч без исполь- зования формулы Ч 3).

Для этого мы возьмем оценку с тремя значениями а Я и "„. Д нее как ивп , как и в предыдущих случаях, должны будут выполняться основные равенства и, кроме того, мы добавим к ним следующие дополнительные: и->-()=р, и ~.у — ., ~ р а р = 'р, а у = у, () у =- р 3 у = р При так определенной оценке все формулы 1 — 1Ч, Ч 1), 2) тождественно принимают значение а, а формула ((А ->- В) ->. А) ->- А при А = у и В = (1 принимает значение у.

Значит, зта формула действительно не выводима из формул 1 — 1Ч, Ч 1), 2). То же самое верно и в отношении тоя<дественно истинной формулы А >/ (А — 1- В), которая в рассматриваемой оценке при А = у и В = () также принимает значение у. >) См. с. 101. ?гл, хп ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИИ ?12 3.

Применение метода оценок к вопросу о замене формул схемами, Наш метод введения функций, подходящим образом заданных па конечных областях, может быть без изменений использован также и в таких доказательствах независимости, в которых речь идет об изменении не только системы формул, но и набора применяемых правил. Так, например, оценка, которую мы построили для докааательства независимости формулы 1 1), показывает, что формулу 1 1) нельзя заместить схемой и 6-» и Действительно, от любой формулы, тождественно принимающей при упомянутой оценке значение и, зта схема снова ведет к формуле с тем ясе свойством, так как при этой оценке значение А — «и тождественно равно и.

Таким образом, и при добавлении упомянутой схемы выводимыми из формул? 2), 3), 11 — У окажутся лишь такие формулы, которые в рассматриваемой оценке тождественно принимают значение а, в то время как формула 1 1) зтим свойством не обладает. Таким же способом можно доказать и то, что формула 11 3): (А — «В) -«((А — «С) -«(А -«В & С)) не может быть замещена схемой Р?-«З Я-«6 если мы ограничимся формулами групп 1 — П1. Таким образом, даже если мы добавим схему (8) в качестве формального правила вывода, то формула П 3) будет не выводима из формул 1, 11 1), 2), 1П. Для доказательства мы рассмотрим оценку, состоящую из четырех элементов и, р, у и б. Среди ннх выделенным снова будет только а.

По-прежнему будем считать, что имеют место основные равенства, а з качестве дополнительных равенств возьмем А — «В = В для А ~ В, А чь ~; у & б = р, у ~/ б = и. Прежде всего, в силу этих определяющих равенств значение каждой из формул 1, 11 1), 2), Н1 тождественно равно а. Затем, если значения выражений Я и Я вЂ” «Й тождественно равны а, то тогда н;ь обладает этим свойством; таким образом, применяя з ы метод оцннок и доклзлтельствл ннзлвисимости 118 схему заключения к формулам, которые тождественно принимают значение и, мы снова получаем формулу с этим свойством. Но то же самое справедливо и в отношении присоединяемой схемы (8): именно, если Я, З и 6 — выражения такие, что Я -«З и Я -«6 тоя<дественно принимают значение и, то и выражение Я -«3 & 6 всегда будет принимать зто значение.

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

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

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

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