§ 12.7. Предикаты. Ограниченный оператор наименьшего числа

Предикаты (см. гл. I) вводятся в логике там, где необходимо символически отобразить соотношение между несколькими предметами. В общем случае предикат определен на некотором множестве предметов (конечном или бесконечном) и может принимать два значения: истинно или ложно (1 или 0).

Мы рассматриваем здесь лишь арифметические предикаты, определенные на множестве натуральных чисел .

Предикат зависит вообще от переменных (-местный предикат). Если некоторые переменные входят под знаки кванторов, стоящих перед предикатом, то они называются связанными переменными; остальные переменные свободные.

Например, предикат зависит от четырех переменных. Предикат же имеет связанные переменные и у и зависит от свободных переменных z и . Поэтому выражение является по сути дела предикатом

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

Предикат, как и функция, может быть определен по индукции. Например, по схеме

определяется предикат четно».

Поэтому открывается возможность построения схемы определения предикатов по аналогии со схемой определения примитивно-рекурсивных функций и введения понятия «примитивно-рекурсивный предикат».

Мы, однако, не пойдем по этому пути и приведем иное определение примитивно-рекурсивного предиката, предложенное Гёделем в 1931 г.

Назовем представляющей функцией предиката такую функцию , которая обращается в нуль лишь для тех и только тех , для которых истинно. Тогда истинность соответствует равенству

Очевидно, что один и тот же предикат может иметь несколько представляющих функций, нули которых должны совпадать.

Определение. Предикат называется примитивнорекурсивным, если существует примитивно-рекурсивная функция, представляющая этот предикат.

При рассмотрении рекурсивных предикатов часто вводятся ограниченные кванторы всеобщности и существования, и ограниченный оператор наименьшего числа.

Предположим, что предикат определен через примитивно-рекурсивный предикат с помощью применения ограниченного квантора всеобщности

(12.8)

или, подробнее,

Предикат соответствует высказыванию, что при данных для всех значение истинно. Определенный так предикат будет примитивно-рекурсивным, так как его представляющая функция может быть выражена через представляющую функцию предиката Р:

Отметим, что 2, вообще говоря, может зависеть от для того, чтобы все выводы остались в силе, эта зависимость должна быть примитивно-рекурсивной.

Аналогичный вывод можно сделать для предиката Q, определенного с помощью применения ограниченного квантора существования

или, подробнее,

Здесь представляющая функция предиката Q определяется через произведение

Введем в рассмотрение ограниченный оператор наименьшего числа.

Пусть дан некоторый примитивно-рекурсивный предикат и заранее известно, что выполняется условие

(12.10)

т. е. при любом наборе найдется хоть одно такое, что будет истинно.

Тогда с помощью предиката можно определить функцию следующим образом: за значение функции заданных будем принимать то наименьшее число , при котором истинно. Обозначим это так:

(12.11)

В силу условия (12.10), при любых , такое у найдется; следовательно, будет всюду определена.

Если вместо предиката рассматривать его представляющую функцию , то (12.11) можно записать в виде

т. е. в качестве значения нужно взять то наименьшее у, при котором обращается в нуль.

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

Покажем, что определенная с помощью ограниченного оператора наименьшего числа функция является примитивно-рекурсивной. Для этого выразим явно функцию через представляющую функцию УС у у) предиката Р

(12.12)

В том, что (12.12) действительно выражает , можно убедиться следующим образом: развернем запись (12.12):

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

Так как определена с помощью построения сумм, произведений и функции , она является примитивно-рекурсивной.

В § 12.6 была приведена в качестве примера примитивно-рекурсивная функция -остаток от деления а на . С помощью этой функции легко подсчитать число делителей числа а.

Будем последовательно делить а на и считать, сколько раз деление произошло без остатка. Таким образом мы определим число делителей числа а.

Обозначим это число . Функция — примитивно-рекурсивная, так как

Если а — простое число, то , так как простое число делится лишь на 1 и на самого себя. Тогда если а простое число,

Теперь легко подсчитать число простых чисел, не превосходящих у. Обозначим его через :

Здесь суммирование начинается с , так как 0 и 1 мы за простые числа считать не будем. За нулевое простое число примем 2, за первое — 3 и т. д.:

Приведем несколько значений функции и :

Определим теперь функцию как функцию, которая по позволяет найти простое число, обладающее номером .

Из теории чисел известно, что простое число не превосходит . Поэтому можно записать

ибо простое число есть наименьшее число, обладающее тем свойством, что среди не превосходящих его чисел есть ровно простых.

Например,

Функция является примитивно-рекурсивной, так как определена с помощью ограниченного оператора наименьшего числа (роль границы ) здесь играет примитивно-рекурсивная функция и примитивно-рекурсивного отношения равенства .

Определим еще одну функцию, которая позволяет узнать показатель, с которым простое число входит в разложение числа на множители. Эта функция обозначается .

Очевидно, что значение есть такое наибольшее число у, что делит , или, иначе, такое наименьшее у, что уже не делит . Тогда можно записать

или

(12.13)

Из (12.13) делаем вывод, что -примитивно-рекурсивная функция.

Вспомним теперь, что гёделизация связана с разложением заданного числа на простые множители и определением показателя, с которым простое число входит в это разложение. Следовательно, процесс гёделизации связан лишь с примитивно-рекурсивными функциями.

Выпишем в заключение еще две примитивно-рекурсивные функции (без вывода).

Пусть имеется набор чисел , гёделевский номер которого равен а, и набор , гёделевский номер которого равен . Образуем теперь строку путем приписывания последовательности к последовательности .

Требуется по известным гёделевским номерам а и определить гёделевский номер у составной строки. Функция, которая позволяет провести это вычисление, сокращенно обозначается и оказывается примитивно-рекурсивной.

Пусть теперь имеется последовательность чисел , которая имеет гёделевский номер а. Вырежем из этой последовательности «кусок», начинающийся с и кончающийся (этот кусок подчеркнут снизу), и на его место вставим другую последовательность чисел с гёделевским номером . Требуется определить гёделевский номер у полученной последовательности.

Функция, которая дает этот номер в зависимости от и b, называется функцией включения и обозначается

Эта функция также оказывается примитивно-рекурсивной.

Вспомним теперь преобразование слов в ассоциативном исчислении. Операция подстановки после гёделизации ассоциативного исчисления сводится к описанной выше операции включения. Следовательно, преобразование слов в ассоциативном исчислении связано лишь с примитивно-рекурсивными функциями.

Эти выводы будут полезны нам в дальнейшем при изучении общерекурсивных функций.