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

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

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

нию дизъюнкцин и отрицания. О конструктивном понимании дизъюнкцни говорилось выше 13 71. Что же касается отрицания, то мы рассмотрели две его трактовки, успешно прнменяемые в соответствующих случаях (Я 11 и 12). Какое же понимание отрицания следует избрать, если мы остановимся на только что указанной трактовке нмплнкацин? В случае, когда посылка нмплнкации есть полуразрешимое высказывание, представляется естественным понимать ее отрицание как усиленное.

Но тогда пришлось бы понимать нмпликацию (1) «если существует нечетное н совершенное натуральное чнсео, то существует нечетное н совершенное натуральное число» как дизъюнкцню (2) «прн всяком те' Ж четко илн й! несовершенно нли существует й( такое, что й! нечетно н тн' совершенно» ~гл введение МАТЕРИАЛЬНАЯ ИМПЛИКАЦИЯ 57 12 12.1, э 11.41, истинность которой пока не установлена. Таким образом, .нам пришлось бы считать неустановленной истинность импликации (1), у которой заключение совпадает с посылкой. Так как это слишком резко расходится с обыденным употреблением связки «если..., то», то мы не можем признать данную трактовку импликации универсально пригодной. Имеются, однако, случаи, когда рассматриваемое сведение нмпликации к отрицанию и дизъюнкции не ведет к резкому расхождению с обыденным словоупотреблением и когда это сведение представляется естественным.

Это случаи импликацни с разрешимой посылкой. Мы и будем в этих случаях понимать импликацию как дизъюнкцию, первый члей которой есть прямое отрицание посылки импликации, а второй — ее заключение. Так понимаемую импликацию мы будем называть материальной импликацией. Итак, материальной импликацией с посылкой А и заключением В, где А — разрешимое высказывание, мы называем импликацию «если А, то В», понимаемую как дизъюнкция «С или В», где С вЂ” прямое отрицание А. Согласно этому определению материальная импликация всегда имеет разрешимую посылку. 4. Для материальной импликации действуют, как нетрудно видеть, правило шодпз ропелз и правило силлогизма: 4.1. Имея верную материальную импликацию с верной посылкой, мы можем заключить об истинности заключения этой импликации. 4.2. Имея верные материальные импликации: <если А, то В», «если В, то С», можно заключить об истинности материальной импликации «если А, то С».

Легко доказываются также следующие теоремы о материальных импликациях: 4.3, Имея верное высказывание А и разрешимое высказывание В, можно заключить об истинности материальных импликаций «если В, то А н В», «если В, то В и А». 4.4. Имея верные материальные импликации (1) «если А, то В», «если С, то Р», (2) можно заключить об истинности материальных импликаций «еслн А и С, то В и Р», и «если А или С, то В или Р». 4.5. Имея верную материальную импликацию (1), где В разрешимо, можно заключить об ис~пинности материальной импликации (2), где С вЂ” прямое отрицание В, а Р— прямое отрицание А.

4.6. Верна материальная импликация «если А, то А», где А — любое разрешимое высказывание. Непосредственно из определения материальной импликации вытекает истинность следующих утверждений: 4.7. Всякая материальная импликация с истинным заключением верна. 4.8. Всякая материальная импликация с ложной посылкой верна. 5. Ввиду неединственности прямого отрицания 12 11.61 материальная импликация с данными посылкой и заключением также не единственна. В языках, в которых синтаксически выделено стандартное прямое отрицание, материальная импликация также может быть синтаксически стандартизована. 6. Следующее очевидное достаточное условие разрешимости материальной импликации будет использовано в дальнейшем: 6.!.

Для разрешимости материальной импликации достаточно, чтобы ее заключение было разрешимо. вввдвние Докажем следующее предложение, также используемое в дальнейшем: 6.2. Для установления истинности материальной импликации достаточно доказать истинность ев заключения в предположении истинности ее посылки. В самом деле, пусть мы умеем доказывать истинность заключения В материальной импликации 4 (1) в предположении, что истинна ее посылка А. А — разрешимое высказывание, т. е. мы владеем методом распознавания истинности или ложности А. Применим этот метод. Если в результате окажется, что А истинно, то мы сумеем доказать истинность В.

Если же окажется, что А ложно, то истинным будет отрицание А. Таким образом, мы всегда найдем верный член дизъюнкции «отрицание А нли В», т. е. установим истинность материальной импликации 4 (1), 5 14. Усиленная импликация 1, Рассмотрим теперь импликации с полуразрешимой посылкой, т. е. высказывания вида (!) «если существует Х такое, что Р, то А», где г" — разрешимый предикат со свободной переменной Х, а А — высказывание. Как понимать такие импликации? Посылка импликации (1) означает, что в настоящее время мы владеем способом построения слова в рассматриваемом алфавите, удовлетворяющего предикату г. Попробуем истолковать импликацию (1) в духе материальной импликации как дизъюнкцию (2) «в настоящее время мы не владеем способом построения слова в данном алфавите, удовлетворяющего предикату Р, или А».

Обнаруживается, что эта дизъюнкция может быть верной в данный момент, но не застрахованной от опровержения в дальнейшем. Так будет, когда А ложно и мы не будем уметь строить искомое слово сейчас, но сумеем впоследствии. Как мы уже отмечали, высказывания этого рода едва ли стоит относить к математике. Таким образом, истолкование импликации (1) как дизъюнкции (2) приходится отвергнуть.

! Ф. $ ы1 усиленнАя имплнкхция Заметим, однако, что высказывание (2) было бы застраховано от опровержения, если бы было доказано высказывание '; (3) «при всяком Х, еслу г", то А», где имплнкация, возникающая из текста (4) «если Р, то А» после замены переменной Х любым словом в нашем алфавите, должна пониматься как материальная.

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

Подставим это слово вместо Х в предикат г, что даст верное высказывание В. Верна и материальная импликация «если В, то А», возникающая из текста (4) в результате замены переменной Х найденным словом. Следовательно, в данном случае верно А (2 13.4.1!. Таким образом, у нас есть способ, указывающий верный член дизъюнкции (2), т.

е. эта дизъюнкция верна. Этим доказано, что установление истинности высказывания (3) обеспечивает истинность высказывания (2) на все времена. Само высказывание (3) при этом не „портится" с течением времени. Ф Все это наводит нас на мысль рассматривать именно вы. сказывание (3) как истолкование импликации (1). Так понимаемую импликацию (1) мы будем называть усиленной импликацией с посылкой «существует Х такое, что г"» :) и заключением А. Согласно этому определению усиленная импликация всегда имеет полуразрешимую посылку. 2. Дчя усиленной импликации действуег правило шодпз ропепз: 2.1. Имея верную усиленную импликацию с верной посылкой, мы можем заключить об истинности заключения этой имплинации. «[61 ДЕДУКТИВНАЯ ИМПЛИКАЦИЯ [гл.

[ ВВЕДЕНИЕ В самом деле, истинность усиленной импликации (1) означает истинность высказывания (3). Предполагая истинной также посылку этой импликации и рассуждая, как выше, убеждаемся в истинности заключения усиленной импликацни (1). Нетрудно видеть, что для усиленной импликации действует правило силлогизма, т. е. что имеем теорему: 2,2. Имея верные усиленные импяикации «если А, то В» и «если В, то С>, можно заключить об истинности усиленной импликации «если А, то С>, 3.

Высказывание может одновременно быть материальной импликацией и усиленной импликацией. Так обстоит дело в том и только в том случае, когда оно имеет вид: «если существует Х такое, что Р, то А», где предикат Р разрешим и таков, что высказывание «существует Х такое, что Р> также разрешимо. В этом случае возникает два понимания данного высказывания: первое понимание, когда высказывание понимается как материальная импликация; второе понимание, когда оно понимается как усиленная импликация.

К счастью, эти два высказывания согласованы друг с другом в следующем смысле: коль скоро рассматриваемое высказывание верно при одном его понимании, оно верно и при другом понимании. Докажем это. Обозначим через В высказывание «если существует Х такое, что Р, то А». Пусть В оказалось верным при его рассмотрении как материальной импликации. Пусть Х вЂ” какое-нибудь допустимое значение фигурирующей здесь переменной. Выясним, удовлетворяет ли оно предикату Р, что возможно ввиду разрешимости этого предиката. Если окажется, что Х удовлетворяет Р, то существует Х такое, что Р, и в силу истинности материальной импликации В верно А [2 13.4.11, и потому верна материальная импликация «если Х удовлетворяет Р, то А». Эта материальная импликация верна и в том случае, когда Х не удовлетворяет Р, так как ее посылка в этом случае ложна.

Таким образом, каково бы ни было Х, верна материальная импликация «если Р, то А». Это означает, что В верно при его рассмотрении как усиленной импликации. Допустим с другой стороны, что высказывание В верно при его рассмотрении как усиленной импликации, т. е. что верно высказывание «каково бы ни было Х, если Р, то А>.

Выясним, верно ли разрешимое высказывание (1) «существует Х такое, что Рм Если оно окажется верным, то, взяв Х так, чтобы Р удовлетворялось, мы увидим, что верны оба высказывания: Р и «если Р, то А». Поэтому в данном случае верно А 12 13.4.1) и верно высказывание В, рассматриваемое как материальная импликация. Оно верно в этом смысле и в том случае, когда высказывание (1), являющееся посылкой высказывания В, ложно.

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

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