markov_teorija_algorifmov (522344), страница 11

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

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

Тогда верно высказывание «при всяком Х имеет место Р или 6». Оно означает, что мы способны доказать любую дизъюнкцию «А нли В», где А и В получаются соответственно из Р и 6 путем замены переменной Х любым допустимым значением этой переменной. Но доказательство этой дизъюнкции дает способ распознавать одно из высказываний А и В как верное.

При этом в силу несовместимости А и В высказывание А будет верным лишь в том случае, когда именно оно будет распознано как верное. Таким образом, в случае разрешимости предиката Р со свободной переменной Х мы владеем общим методом, распознающим для любого допустимого значения свободной переменной Х, верен ли результат замены в Е переменной Х этим ее допустимым значением. 5.

Ясно, что разрешимое высказывание ложно, если нам удалось построить верное прямое отрицание этого высказывания. Легко доказываются следующие теоремы: 5.1. Всякое верное высказывание разрешимо. Всякое ложное высказывание есть его прямое отрицание. 5.2. Всякое ложное высказывание разреишмо. Всякое верное высказывание есть его прямое отрицание. 5.3. Всякое разрешимое высказывание верно или ложно. 6.

Теоремы 5.1 — 5.3 показывают, что во всяком достаточно богатом языке разрешимое высказывание имеет очень мною прямых отрицаний. Иногда бывает желательно иметь простой формальный способ, строящий по любому данному разрешимому высказыванию данного языка одно из его прямых отрицаний. Во многих случаях такой способ действительно имеется. 7. Примерами разрешимых предикатов являются двуместные предикаты одинаковости букв данного алфавита и графического равенства слов в данном алфавите. Применяя знак Х для выражения графического равенства слов (и, в частности, букв), мы можем записать эти предикаты в виде $Х«) РХ !г, где допустимыми значениями литеральных переменных $ н т) являются буквы данного алфавита, а допустимыми значениями вербальных переменных Р н 9 являются слова в нем.

Их прямыми отрицаниями являются двуместные предикаты графического различия букв и слов. С применением знака различия ~С онн записываются в виде Для предикатов графического равенства и различия имеют место законы исключенного третьего: 71 Каковы бы ни были буквы $ и ц алфавипш А, верна дизъюнкция ~4Х«) или $~Ет)». 7.2. Каковы бы ни были слова Р и 1~ в алфавите А, верна дизъюнкция «Р Х () или Р ~ ()».

Верны также следующие высказывания. 7.3. Каковы бы ни были буквы $ и т! алфавита А, ложна конъюнкция «$Хц н $,е т)». 1гл, ВВЕДЕНИЕ $!21 УСИЛЕННОЕ ОТРИЦАНИЕ 52 7.4. Каковы бы ни бвиш слова Р и Я в алфавите А, ложна конъюнкция <Р ~ Я и Р зс Я». Высказывания 7.1 — 7.4 выражают тот факт, что предикаты ~хт1 и й~гт) являются прямыми отрицаниями друг друга, равно как и предикаты Рм 1;1 и Р 7« Я. й 12. Полуразрешимые высказывания. Усиленное отрицание 1.

Рассмотрим теперь высказывание о существовании слова в данном алфавите, удовлетворяющего данному требованию, выраженному разрешимым. предикатом, т. е. высказывание вида (1) «существует Х такое, что Р», где Х вЂ” свободная вербальная переменная, а Р— разреши- мый одноместный предикат с этой переменной. Высказывания этого вида мы будем называть полуразрешиПримером полуразрешимого высказывания является вы- сказывание 2 10.3(5): (2) «существует 7з' такое, что й( нечетно и совершенно» *).

Если бы в нашем распоряжении было его прямое отрицание, то мы имели бы способ, с помощью которого можно было выяснить, верно ли это высказывание. Однако такого способа у нас нет. В настоящее время мы не только не знаем, существует ли нечетное совершенное число, но даже не знаем, каким образом мы могли бы это узнать. Это означает, что в настоящее время мы не умеем строить прямое отрицание этого высказывания и, значит, не можем утверждать, что оно существует, Какой же смысл можно придать отрицанию рассматриваемого высказывания (2)? Вспомним, какой смысл имеет само это высказывание. Оно означает, что мы в настоящее время владеем способом построения нечетного и совершенного натурального числа.

Казалось бы, что отрицание этого высказывания должно пониматься как высказывание (3) «в настоящее время мы не владеем способом построения нечетного и совершенного натурального числа». ») Вопрос об истинности этого высказывания представляет собой одну из самых древних математических проблем, Так понимаемое отрицание нашего высказывания (2) верно в момент, когда пишутся эти строки; в настоящее время (1984 г.) мы действительно не умеем строить нечетное и совершенное натуральное число. Однако у нас нет гарантии того, что через некоторое время, например к 2084 г., не будет найден способ построения такого числа, и тогда высказывание (3) перестанет быть верным.

Таким образом; предлагаемое понимание отрицания высказывания (2) заставило бы нас заниматься высказываниями, верными в данный момент, но не гарантированными от последующего опровержения. Такого рода высказывания едва ли следует относить к математике. Оставаясь же в области математики, мы вынуждены отвергнуть понимание отрицания высказывания (2) как высказывания (3). Заметим теперь, что высказывание (3) было бы гарантировано от опровержения, если бы было доказано высказывание 2 10.3 (б): (4) «каково бы ни было Ж, Лт четно или несовершенно», В самом деле, тогда при подстановке любого натурального числа вместо свободной натуральной переменной в предикат 2 11.4 (2) получилось бы верное высказывание, и так как этот предикат есть прямое отрицание предиката 2 1!.4 (3), то при подстановке любого натурального числа вместо свободной переменной в предикат 2 11.4 (3) получилось бы ложное высказывание.

В этом случае мы никогда не имели бы способа построения нечетного и совершенного натурального числа. Зто наводит на мысль считать отрицанием высказывания (2) высказывание (4), гарантирующее истинность высказывания (3) „на веки вечные" и само оказывающееся истинным на веки вечные, коль скоро его истинность будет установлена. Именно так мы и предлагаем понимать отрицание высказывания (2). Рассмотрения, аналогичные только что проведенным, очевидно, могут быть проведены для любого полуразрешимого высказывания. Они наводят нас иа мысль рассматривать в качестве отрицания полуразрешимого высказывания (1) высказывание (5) «при всяком Х имеет место 6», где 6 — прямое отрицание Р, Мы будем называть высказывание (5) усиленным отрицанием высказывания (1).

В частности, высказывание.(4) есть усиленное отрицание высказывания (2). % |а! материал ьн кя импликхция !гл. ВВЕДЕНИЕ 2. Для так определенного усиленного отрицания полуразрешимого высказывания естественно возникает вопрос о законе исключенного третьего, т. е. вопрос, всегда лн верна дизьюнкцня (1) «А илн В», где А — полуразрешнмое высказыванне, а  — его усиленное отрицание. Для положительного ответа на этот вопрос у нас нег никаких оснований.

Нетрудно видеть, что в случае истинности дизъюнкции (1) В есть прямое отрицание А, так как А и В, очевидно, несовместимы. В этом случае А разрешимо. Мы же видели, что разрешимость высказывания 1(2) не установлена. Установление истинности днзъюнкции (1) в том случае, когда роль А играет высказывание 1(2), утверждающее существование нечетного совершенного натурального числа, пока представляет собой нерешенную проблему *). 3. Термин «полуразрешнмое высказывание» оправдывается следующим соображением.

Имеется общий метод, устанавливающий истинность всякого верного полуразрешнмого высказывания (1). Он состоит в последовательном систематическом переборе слов в данном алфавите, причем для каждого нз ннх выясняется с помощью общего метода, указанного в 3 11.4, верно лн высказывание, получаемое из Р путем замены Х этим словом. В случае, когда высказывание (1) верно, т. е. когда может быть построено слово, для которого результат замены верен, мы в ходе перебора натолкнемся на такое слово н тогда оборвем процесс.

$!3. Материальная нмпликацня 1. Импликациями называются высказывания, образуемые из двух высказываний, соединяемых связкой «если..., то», причем первое высказывание, называемое посылкой импликации, ставится между «если» и «то», а второе, называемое заключением импликации, ставится после «то». Примером нмплнкацнн может служить высказывание (1) «если существует нечетное н совершенное натуральное число, то существует нечетное и совершенное натуральное число, большее десятн». 2, Наивное объяснение смысла имплнкацнн состоит в следующем. '1 Лая сравнения см. Л.

Г аль бе р т н П. Б е р н а Я с !!1, гк. П, 13.!. Всякая импликация утверждает, что, признав посылку верной, мы должны будем признать верным заключение. Это объяснение порождает следующие вопросы. Как можно предполагать посылку верной (а вдруг она неверна, что, например, пока не исключено для нмплнкацни 1 (! ))? Какая снла заставят нас признать верным заключение (а вдруг оно нам настолько не по вкусу, что мы уж лучше возьмем назад наше нрнзнанне посылки, чем согласимся с заключением)? Не можем ли мы все же как-то сопротивляться этой силе? Так как отве.

тить на этн вопросы нелегко, то приходится признать данное объяснение смысла нмпликации недостаточным. 3. В классической математической логике принято следующее объяснение смысла имплнкации: нмплнкация утверждает то же, что дизъюнкцня, первый член которой есть отрицание посылкн нмпликацнн, а второй — ее заключенне. Например, имплнкацня 1 (1) при этой трактовке понимается как дизъюнкция «неверно, что существует нечетное и совершенное натуральное число, нлн существует нечетное н совершенное натуральное число, большее десятн». Понимание нмпликацин сводится, таким образом, к поннма.

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

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