markov_teorija_algorifmov (Марков - Теория алгоритмов), страница 9

а й. Высказывания общности 1. В математике большую роль играют еысказыеания оби1- ности, т. е. высказывания, начинающиеся словамн «всякий», «всякая», «для всякого», «каков бы ни был» и т. п. Каким мо. жет быть их конструктивное понимание? 2. Проблема решается просто, когда имеется список всех объектов того вида, к которому относится высказывание общности.

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

е. когда нет объектов 40 ВВЕДЕНИЕ 1гл. этого вида. Мы будем тогда понимать наше высказывание общности как тривиальную истину Лм.Л (независимо от того, в чем состоит требование, которому должен удовлетворять объект). При таком понимании высказываний общности в тех случаях, когда имеется список объектов рассматриваемого вида, имеет место следующее. При добавлении к этому виду одного нового объекта высказывание о том, что всякий объект расширенного вида удовлетворяет поставленному требованию, оказывается равносильным конъюнкции прежнего высказывания общности (относящегося к первоначальному виду) и высказывания о том, что добавленный объект удовлетворяет этому требованию.

3. Все сказанное в п. 2 относилось к случаю, когда имеется список объектов рассматриваемого вида. Такого списка может, однако, не быть, и он даже может быть неосуществим из-за того, что этих объектов „слишком много". К счастью, имеется иная возможность конструктивного понимания общих высказываний.

Для некоторых объектов рассматриваемого вида может быть установлено путем надлежащих рассуждений, что эти объекты удовлетворяют поставленному требованию. Эти рассуждения могут иметь такой характер, что будет ясна возможность провести аналогичные рассуждения для любого другого объекта рассматриваемого вида. Тогда у нас сложится убеждение в том, что, какой бы нам ни был предъявлен объект этого вида, мы сумеем доказать (сделать очевидным путем рассуждений), что этот объект удовлетворяет предъявленному требованию.

Именно эту ситуацию мы и констатируем, говоря, что всякий объект данного вида удовлетворяет данному требованию. Итак, мы пришли к следующему пониманию высказываний о том, что всякий конструктивный объект данного вида удовлетворяет данному требованию. Это высказывание констатирует нашу способность доказать для любого данного нам объекта рассматриваемого вида, что этот объект удовлетворяет предъявленному требованию.

Источником нашей уверенности в том, что мы сумеем провести требуемое доказательство, каков бы ни был предъявляемый нам объект, может быть наш ограниченный опыт по таким доказательствам, если нам в результате этого опыта станет ясно, как действовать в любом случае. Эту нашу способность убеждаться в инстинности общих высказываний на основании ограниченного опыта мы будем в дальнейшем назыв,зть интуицией общности, ВЫСКАЗЫВАНИЯ ОБЩНОСТИ 41 4. В случае, когда утверждается, что данному требованию удовлетворяет любое слово в некотором алфавите А, можно широко пользоваться методом, основанным на особом, индук- тивном характере определения слов. Он заключается в следую- щем. Сначала мы показываем„ что 1) пустое слово Л удовлетворяет данному требованию.

'Затем показываем, что 2) если какое-нибудь слово Р в А удовлетворяет данному требованию, то, какова бы ни была буква й алфавита А, слово РК также удовлетворяет этому требованию. Тогда можно утверждать, что всякое слово в А удонлетворяет поставленному требованию. В самом деле, прослеживая процесс построения какого- нибудь слова, мы видим, что на каждом шаге этого процесса строится некоторое слово, удовлетворяющее поставленному требованию. В частности, это относится и к последнему шагу, когда получается интересующее нас слово.

Этот метод мы будем называть методом правой индукции по построению слова или просто правой индукцией. 5. Правая индукция в случае, когда алфавит А состоит из одной буквы [, представляет собой обычный арифметический «метод полной индукцииз. В этом случае слова в алфавите А суть натуральные числа, число нуль совпадает с пустым словом, а сам метод состоит в следующем. Пусть мы хотим доказать, что всякое натуральное число удовлетворяет некоторому условию Р с натуральной перемен- ной М.

Для этого мы.доказываем, что: 1) нуль удовлетворяет Р, 2) для всякого М имеет место импликация: если М удовлетворяет Р, то и М[ удовлетворяет Р. Тогда всякое натуральное число удовлетворяет Р. В качестве примера на применение этого метода мы докажем с его помощью высказывание (1) «каково бы ни было натуральное число М, имеет место графическое равенство И М1Ч И».

В самом деле, при М~Л *) сы. первый абзац и. 5 4 й. ВВЕДЕНИЕ «93 ВыскАзыВАния ОБщности т. е. (2) Ц, Л]х[Л, П. Пусть теперь У вЂ произвольн натуральное число, и пусть имеет место равенство (3) Ц, ж]х[У, И. Тогда Ц. ЛгПЗ~Ц. Л(]1 ~[)У П! [(3Н х[Ф, л]1! ~е)у!! ц[л'1* П т. е. (4) Ц л'П~[л'1 И. Следовательно, если имеет место равенство (3), то имеет место и равенство (4). В сочетании с равенством (2) это позволяет нам заключить об истинности высказывания (1). В качестве еще одного примера мы установим истинность высказывания (5) «каково бы ни было натуральное число У, имеет место графическое равенство Ц Р' Шп:[Ц й П' При этом мы воспользуемся истинностью высказывания (1).

Действительно, при УХЛ Ц, [л, П]хЦ, [л, л]И хЦ, л1] ~П П ~[Ц л] И (5) Ц, [л, П]х[Ц, л], И. Пусть теперь У вЂ произвольн натуральное число, и пусть имеет место равенство (7) П Р(Ш~[Ц ЧП Тогда П, [3~1, И]хЦ, [371, л]П 3Ч! Л1!П 'е Р(11 И [(1Н ~[[м], л]1, И 3'[[Л'! И 1] Зе[Ц, й(И, И [(1Н, т. е (8) Ц, [л~1, Ш~[Ц й7Ц П Снова, принимая во внимание (б) и учитывая, что из (7) вытекает (8), мы, полъзуясь правой индукцией, заключаем, что высказывание (5) истинно.

6. Только что изложенный метод правой индукции требует некоторых пояснений. Прежде всего, мыдолжны объяснить, какойсмысл мы вкладываем в термин «требование, предъявляемое к слову». Оставляяя детальное обсуждение этого вопроса на будущее, мы в следующем параграфе дадим разъяснения, достаточные для первоначального понимания. Кроме того, как мы убедимся в дальнейшем в 313, специального анализа требует пункт 2) нашего метода, трактующий об индукционном шаге. В каком смысле должен пониматься фигурирующий в этом пункте словооборот «если ..., то» (импликация)? Не должен ли он в разных ситуациях пониматься поразному? Откладывая обсуждение данной проблемы до Я 13— 15, мы отметим, что в обосновании нашего метода было использовано следующее свойство импликации: 6.1.

Возиожность, исходя из истинности двух высказываний А и «если А, то В», заключить 'об истинности высказывания В (так называемое «правило шодцз ропепз»). 7. Метод полной индукции мы будем применять и в других, часто употребляемых в математике формах. Например, чтобы показать, что всякое натуральное число Ж удовлетворяет условию В, мы иногда будем доказывать, что при ироизвольном натуральном М верна следующая импликация: ° если все числа, меньшие У, удовлетворяют )', то У также удовлетворяет Р».

Доказав эту импликацию, мы будем вправе считать доказанным и интересующее нас утверждение,'что всякое натуральное М удовлетворяет г. Обоснование этой формы метода полной индукции обычное. Здесь нам потребуется свойство импликации, заключающееся в том, что <гл.

ВВЕДЕНИЕ пеееменные. Неедикдты 4 <а< 7.1. Всякая импликация с ложной посылкой является истинной. Проводя конкретные доказательства по индукции, мы для начала, как правило, будем указывать, в каком именно смысле в данном рассуждении употребляетея импликация. Однако но мере того, как у читателя будет накапливаться опыт, мы все более и более будем перекладывать эту работу на него, не оговаривая этого особо. 8. У нас нет достаточных оснований считать метод индукции исчерпывающим. Отметим, однако, что с его помощью удается установить практически все интересующие нас высказывания общности, встречающиеся в элементарной теории слов. й 10.

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

Так используемые буквы мы называем свободными переменными. Применение свободных переменных является некоторым расширением обыденного языка. Когда свободная переменная будет употребляться для обозначения произвольного объекта данного вида, сами объекты этого вида будут называться допустимыми значениями этой свободной переменной. В частности, допустимыми значениями свободной переменной могут быть высказывания какого-нибудь фиксированного языка. Такие свободные переменные мы будем называть пропозиционольными.