На этом шаге мы рассмотрим примитивно рекурсивный предикат.

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

В качестве примера предикатов можно привести следующие логические функции:

;
;
.

Определение. Функция φ(x₁, ..., x_n) называется представляющей функцией для предиката p(x₁, ..., x_n), если выполняются следующие условия:

D_φ = D_p = D, т.е. их областb определения совпадают;
для любого набора (x₁, ..., x_n) из области определения D
(17)

Определение. Предикат р(х) называется примитивно рекурсивным, если его представляющая функция является примитивно рекурсивной функцией.

Например, следующие предикаты p₁(x,y) = (x=y); p₂(x,y) = (x<y) являются примитивно рекурсивными, так как их представляющие функции являются ПРФ.

Действительно, в качестве представляющей функции первого предиката можно взять функцию вида φ₁(x) = sg|x-y|, (18) где

является ПРФ. Покажем, что данная функция - ПРФ.

По определению операции примитивной рекурсии получаем, что:

Следовательно, ПРО данной функции является последовательность функций:

Функция f(x,y) = |x-y| определяется следующим образом:

(19)

Прежде чем доказать, что функция f(x,y) = |x-y| является примитивно рекурсивной, рассмотрим следующие функции:

1) (20)
2) (21)

Покажем, что эти функции являются ПРФ.

1) Рассмотрим функцию (20). По определения операции примитивной рекурсии получаем, что

Следовательно, ПРО для данной функции является последовательность функций:

2) Рассмотрим теперь функцию (21). По определения операции примитивной рекурсии получаем, что:

где в последнем равенстве f(x,y) = i(f(x,y)), т.е. получили функцию сходную с функцией в первом случае, следовательно, в качестве ПРО данной функции можно взять последовательность функций:

Исходя из последнего примера, функцию (19), будем представлять следующим образом:

Очевидно, данная функция является ПРФ.

Теперь можно говорить, что выбранная представляющая функция (18), т.е. φ₁(x) = sg|x-y| для предиката p₁(x,y) = (x=y) является ПРФ и удовлетворяет исходным условиям, т.е.

Для предиката p₂(x,y) = (x<y) в качестве представляющей функции можно брать

и очевидно, она удовлетворяет исходным условиям и является ПРФ.

Определение. Функция f(x₁, ..., x_n) называется ПРФ относительно совокупности функций и предикатов Ψ = {φ₁, ..., φ_m, p₁, ..., p_k}, если она ПРФ относительно совокупности функций φ₁, ..., φ_m, Ψ₁, ..., Ψ_k, где Ψ_i, 1<=i<=k - представляющая функция предиката p_i.

Определение. Предикат p(x₁, ..., x_n) называется ПРФ относительно совокупности функций и предикатов Ψ = {φ₁, ..., φ_m, p₁, ..., p_k}, если представляющая функция предиката p является примитивно рекурсивной относительно совокупности функций φ₁, ..., φ_m, Ψ₁, ..., Ψ_k, где Ψ_i, 1<=i<=k - представляющая функция предиката p_i.

Теорема 2.

Логические операции над предикатами сохраняют свойства примитивной рекурсивности предикатов.

Доказательство.

Приведем в виде таблицы истинностные значения логических операций: конъюнкции, дизъюнкции, импликации и отрицания.

Таблица 1. Результаты логических операций
p(x) q(x) p(x)∧q(x) p(x)Vq(x) p(x)->q(x)

0 1 0 0 0 1

0 1 1 0 1 1

1 0 0 0 1 0

1 0 1 1 1 1

Таблица 1. **Результаты логических операций**
p(x)		q(x)	p(x)∧q(x)	p(x)Vq(x)	p(x)->q(x)
0	1	0	0	0	1
0	1	1	0	1	1
1	0	0	0	1	0
1	0	1	1	1	1

Пусть φ_p(x) - представляющая функция предиката р(х); φ_q(x) - представляющая функция предиката q(x), где в общем случае x = (x₁, ..., x_n).

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

(23)
(24)
(25)
(26)

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

На следующем шаге мы рассмотрим операцию навешивания ограниченного квантора над предикатами.

Предыдущий шаг Содержание Следующий шаг