Математическая логика и теория алгоритмов. Сергиевская И.М. - 43 стр.

UptoLike

ВУЗ: 

ПГУТИ | Самара

Составители: 

Рубрика: 

48
Докажем, что предположение индукции верно при 1+= ny , то есть, верна
формула
=
+ )1,( n
x
f
2+n
x
. Выразим )1,(
+
n
x
f
с помощью схемы примитивной
рекурсии.
=+ )1,( nxf =)),(,,( n
x
f
n
x
ψ
211
),,(
+++
=⋅=
nnn
xxxxnx
ψ
.
Таким образом, на основании метода математической индукции формула
=),(
y
x
f
1+y
x
доказана для всех
0
Ny
∈
.
Теперь строго определим примитивно-рекурсивные функции.
Определение.
1) Простейшие примитивно-рекурсивные функции
примитивно-рекурсивны.
2)
Примитивно-рекурсивными являются функции, полученные из примитивно-
рекурсивных функций с помощью операторов суперпозиции и (или)
примитивной рекурсии.
3)
Функция является примитивно-рекурсивной тогда и только тогда, когда это
следует из 1) и 2).
Пример. Покажем, что функция yxyxf
+
=
+
),( примитивно-рекурсивна.
Доказательство. 21 =+n , 1
=
n , следовательно, функция
ϕ
должна зависеть
от одной переменной, а функция
ψ
– от трех. Пользуясь заданием функции, найдем
ее значения:
)()()0,(
1
1
xxIxxf
ϕ
===
+
.
)
==+=++=+
+++
),(1),(1)1,(
1
yxfsyxfyxyxf
()
,),(,, yxfyx
+
=
ψ
то есть
() ()
)
zyxIszszyx ,,)(,,
3
3
==
ψ
.
Таким образом, функция
yxyxf
+
=
+
),(
получена по схеме примитивной
рекурсии (
()
ψ
ϕ
,
1
Rf =
+
) из примитивно-рекурсивных функций, следовательно, сама
является примитивно-рекурсивной.
Примитивно-рекурсивными, в частности, являются следующие функции:
a
x
f
=)(, a
x
x
f
+
=)(, y
x
y
x
f
+
=
),(,
xy
y
x
f
=
),(,
y
xyxf =),(
, !),(
x
y
x
f
=
,
⎩
⎨
⎧
>
=
=
,0 если ,1
,0 если ,0
)sgn(
x
x
x
⎩
⎨
⎧
>
=
=
.0 если ,0
,0 если ,1
)(sgn
x
x
x
Операция минимизации по
i
-ой переменной функции
)
n
n
xxxf ,...,,
21
обозначается следующим образом:
)
inii
n
y
xxxyxxxf =
+−
,...,,,,...,,
1121
μ
, и
определяется так.
Рассмотрим уравнение относительно
y :
()
inii
n
xxxyxxxf =
+−
,...,,,,...,,
1121
. (1) 
         Докажем, что предположение индукции верно при y = n + 1 , то есть, верна
формула f ( x, n + 1) = x n + 2 . Выразим f ( x, n + 1) с помощью схемы примитивной
рекурсии.
                                                   n +1       n +1
 f ( x, n + 1) = ψ ( x, n, f ( x, n)) = ψ ( x, n, x ) = x ⋅ x      = x n+ 2 .
          Таким образом, на основании метода математической индукции формула
 f ( x, y ) = x y +1 доказана для всех y ∈ N 0 .
          Теперь строго определим примитивно-рекурсивные функции.

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

          Пример. Покажем, что функция f + ( x, y ) = x + y примитивно-рекурсивна.
          Доказательство. n + 1 = 2 , n = 1 , следовательно, функция ϕ должна зависеть
от одной переменной, а функция ψ – от трех. Пользуясь заданием функции, найдем
ее значения:
 f + ( x,0) = x = I11 ( x) = ϕ ( x) .
f + ( x, y + 1) = x + y + 1 = f + ( x, y ) + 1 = s1 ( f + ( x, y ) ) =
= ψ ( x, y, f + ( x, y ) ),
                                          (
то есть ψ ( x, y, z ) = s ( z ) = s I 33 ( x, y, z ) .   )
      Таким образом, функция f + ( x, y ) = x + y получена по схеме примитивной
рекурсии ( f + = R1 (ϕ ,ψ ) ) из примитивно-рекурсивных функций, следовательно, сама
является примитивно-рекурсивной.

         Примитивно-рекурсивными, в частности, являются следующие функции:
 f ( x) = a , f ( x) = x + a , f ( x, y ) = x + y , f ( x, y ) = xy , f ( x, y ) = x y , f ( x, y ) = x! ,
            ⎧0, если x = 0,             ⎧1, если x = 0,
sgn( x) = ⎨                  sgn ( x) = ⎨
            ⎩1, если x > 0,             ⎩0, если x > 0.

     Операция минимизации по i -ой переменной функции f n ( x1 , x2 ,..., xn )
обозначается следующим образом:    μ y ( f n ( x1 , x2 ,..., xi −1 , y, xi +1 ,..., xn ) = xi ) , и
определяется так.
     Рассмотрим уравнение относительно y :
f n ( x1 , x2 ,..., xi −1 , y, xi +1 ,..., xn ) = xi .                   (1)




                                                             48

Страницы