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

Допустимыми значениями свободной переменной могут быть слова в данном алфавите А. Такие свободные переменнь<е мы будем называть вербальными переменными в алфавите А. Вербальные переменные в алфавите ( мЫ будем называть натуральными. Допустимыми значениями свободной переменной могут быть буквы данного алфавита. Такие свободные переменные будут называться литеральными.

В дальнейшем, как правило, заглавные латинские буквы А, В, С будут фигурировать в качестве пропозициональных свободных переменных; заглавные латинские буквы М, А<— в качестве натуральных свободных переменных; заглавные латинские буквы Р, Я, Я вЂ” в качестве вербальных свободных переменных; строчные греческие буквы $, т), Ь вЂ” в качестве литеральных свободных переменных. 2. Применение свободных переменных порождает такие тексты как «й< нечетно», «М совершенно» '), «М меньше, чем А<». (1) (2) (3) яое число, равное сумме своих делителей, отличных от него самого, Напри мер, число 6 совершенно, так как делителями его являются числа 1, 2, 3 и 6, причем 6=1+2+3.

К настоящему времени найдено 24 совершенных числа. Все овя оказались четкымя. десятичная запись вальшего из яих содержит свыше 12 тысяч знаков. Существуют ли нечетные совершенные числа, в настоящее время кеязвестко. Заменив в них натуральные свободные переменные их допустимыми значениями — натуральными числами,— «олу- чим, в частности, высказывания (4) «))) нечетно», (5) «) ) ) ) ) ( совершенно», (8) «))(()) меньше, чем )))». Тексты, дающие высказывания в результате замены сво- бодных переменных их допустимыми значениями, называются предикатпми. Тексты (1), (2) и (3) могут служить примерами предикатов. В зависимости от того, сколько различных свободных пере- менных входит в предикат, различают предикаты одноместные, двуместные, трехместные и т. д. Предикаты (1) и (2) одноместны, а предикат (3) двуместен.

Предикаты, все переменные которых суть вербальные и литеральные переменные в алфавите А, мы будем называть вер- бальными предикатами в алфавите А. Имея одноместный предикат, мы можем заменить в нем все (одинаковые) свободные переменные их одинаковыми допустимыми значениями, что даст высказывание. ч) Читатель, вероятно, помнит, что совершенным яазываечея яатураль- введении [гл. Например, взяв одноместный предикат (2) и заменив в нем натуральную переменную натуральными числами [, [[, [[[ и т. д., мы получим высказывания совершенно», «[ [ совершенно», «[[[ совершенно»... Некоторые нз них оказываются верными, как, например, высказывание «[[[ [ [[ совершенно».

Таким образом, данный одноместный предикат выделяет среди натуральных чисел некоторые натуральные числа и может быть рассматриваем как требование, предъявляемое к натуральному числу. Числа, удовлетворяющие этому требованию, в данном случае — совершенные числа. Ясно, что одноместные предикаты вообще можно рассматривать как требования, предъявляемые к конструктивному объекту данного вида. Аналогичным образом двуместный предикат можно рассматривать как требование, предъявляемое к паре объектов данных видов; трехместный предикат — как требование, предъявляемое к тройке объектов данных видов, ит. д. Свободными предикотными переменными в данном алфавите мы будем называть свободные переменные, допустимыми значениями которых являются вербальные предикаты в данном алфавите.

В дальнейшем заглавные латинские буквы Р и 6, как правило, будут применяться в качестве свободных предикатных переменных. 3. Для формулировки высказываний общности и высказываний о существовании применяются переменные иного рода— так называемые связанные переменные. Например, чтобы выразить тот факт, что прибавление единицы к натуральному числу всегда дает число, отличное от взятого, мы пишем (1) «каково бы ни было У, У ~ У+1»; чтобы выразить, что существует совершенное число, мы пишем (2) «существует У такое, что У совершенно». Оба эти текста суть высказывания, но они ие являются предикатами со свободной переменной У.

Заменив в этих текстах букву У каким-нибудь натуральным числом, мы получилн бы не высказывание, а бессмысленный текет такой, как «каково бы ни было 5, 5-ьб+1», «существует 6 такое, что 6 совершенно, $!и п»ямов От»ицяниа 47 В текстах (1) и (2) буква У называется связанной переменной. Связанные переменные появляются в высказываниях общности и в высказываниях о существовании. Первые могут иметь вид (3) «каково бы ни было Х, имеет место Р», где Р— вербальный предикат со свободной переменной Х; вторые могут иметь вид (4) «существует Х такое, что Р» с таким же Р. Высказывание (3) утверждает, что всякое допустимое значение переменной Х удовлетворяет предикату Р; высказывание (4) утверждает, что может быть построено допустимое значение переменной Х, удовлетворяющее Р.

Переменная Х свободна в предикате Р, но все ее появления в высказываниях (3) и (4) связаны. С применением связанных переменных высказывание «существует нечетное совершенное число» может быть формулировано так: (5) «существует У такое, что У нечетно и У совершенно»; высказывание же «всякое натуральное число четно или несовершенно» может быть формулировано так: (6) «каково бы ни было У, У четно или У несовершенно».

$11. Прямое отрицание. Разрешимые высказывания 1. Изучая нашу способность осуществлять конструктивные процессы„мы формулируем результаты этого изучения в в иде некоторых высказываний, утверждающих, что мы в наеем стоящее время умеем строить такие-то объекты, что мы владес гакими-то общими методами и т. п. Естественно спросить, как могут выглядеть отрицания высказываний этого рода.

Ведь эти отрицания тоже будут что-то говорить о наших конструктивных способностях. Наивный ответ гласит, что отрицанием высказывания (1) «в настоящее время мы умеем строить объект, удовлетворяющий требованию...» ПРЯМОЕ ОТРИЦАНИЕ 1гл. ! введение является высказывание (2) «в настоящее время мы не умеем строить объект, удовлетворяющий требованию.. лч что отрицанием высказывания (3) «в настоящее время мы владеем общим методом для...» является высказывание (4) «в настоящее время мы не владеем общим методом для...». Этот ответ приходится, однако, отвергнуть по той причине, что высказывания вида (2) и (4) вполне могут оказаться верными сегодня и ложными завтра.

Сегодня мы действительно можем не уметь решать данную конструктивную задачу, а завтра научимся. Ме]цду тем к математическим истинам уместно предъявлять требование сохранности: установленная в данный момент истина должна оставаться таковой завтра, послезавтра и т. д. Этому требованию удовлетворяют верные высказывания видов (1) и (3) *), тогда как о верных высказываниях видов (2) и (4) этого, вообще говоря, нельзя сказать. Поэтому верные высказывания видов (2) и (4) не всегда можно считать математическими *а).

Мы видим, таким образом, что наивная трактовка отрицания может вывести нас за пределы математики. Желая оставаться в этих пределах, мы должны позаботиться о надлежащем положительном понимании отрицания, т. е. о таком его понимании, при котором отрицание высказывания тоже свидетельствовало бы о какой-то нашей способности. При этом мы, естественно, будем требовать, чтобы отрицание высказывания всегда оказывалось несовместимым с ним, т. е. чтобы конъюнкция высказывания со своим отрицанием была ложной.

2. Проблема положительного понимания отрицания в некоторых случаях решается просто. Например, так обстоит дело с высказываниями об одинаковости н различии букв данного алфавита. Отрицать, что $ и т) одинаковы, это значит утверждать, что й и т) различны; отрицать, что $ и т) различны, это значит утверждать, что $ и т] одинаковы. Оба эти высказывания повествуют о нашей способности осуществить некоторые конструктивные акты. Требование несовместимости ») Придирчивый читатель усмотрит здесь излишний оптимизм.

Ведь бывало, что люди разучивались что-то делать. Пусть читате.чь вообразит себе, что против такого забвения достигнутого приняты эффективные меры. ь*) В $ 12.1 читатель найдет некоторую конкретизацию этих рассмотрений. высказывания со своим отрицанием здесь, очевидно, соблюдено. Кроме того, соблюден закон исключенноготретьего, т. е. верна дизъюнкция, второй член которой есть данное высказывание, а первыи — его отрицание. Эта дизъюнкция должна, разумеется, пониматься конструктивно, Она означает, что мы в состоянии указать, какое из высказываний — данное либо его отрицание является истинным.

Таким образом, мы в состоянии выяснить, верно ли данное высказывание. Вообще, в том случае, когда высказывания А и В таковы, что их конъюнкция ложна, а дизъюнкция истинна, мы будем говорить, что В есть прямое отрицание А. Мы будем говорить о высказывании А, что оно разрешимо, когда нам удалось подобрать к нему прямое отрицание. В случае разрешимости высказывания А у нас имеется способ распознавать, верно ли А. Мы распознаем это при установлении истинности дизъюнкции «А или В», где  — прямое отрицание А. 3. Легко доказываются следующие теоремы о разрешимых высказываниях и их прямых отрицаниях: 3.1. Конъюнкция двух разрешимых высказываний есть разрешимое выскозьиание.

Дизъюнкция прямых отрицаний двух высказываний есть прямое отрицание их конъюнкции. 3.2. Дизъюнкция двух разрешимых высказываний есть разрешимое высказывание, Коньюнкция прямых отрицаний двух разрешимых высказьианий есть прямое отрицание их дизъюнкции. 3.3. Прямое отрицание всякого разрешимого высказьиания есть разрешимое высказьиание. Всякое разрешимое выскажвание есть прямое отрицание своего прямого отрицания. 4.

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

Будем говорить об одноместном предикате С со свободной переменной Х, что он есть прямое отрицание одноместного предиката Р с той же переменной, если прн замене Х любым допустимым значением этой переменной из Р и 6 возникают высказывания, являющиеся взаимными прямыми отрицаниями. Предикат (1) есть прямое отрицание преднката 3 10,2 (2). Предикат (2) «М четно илн М несовершенно» есть прямое отрицание предиката (3) «М нечетно и М совершенно» (3.1). Мы будем говорить, что одноместный предикат Р разрешим, если имеется его прямое отрицание. Предикаты (1) — (3) и 6 10.2 (2) разрешимы. Допустим, что одноместный предикат Р со свободной переменной Х разрешим и что С есть его прямое отрицание.