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

UptoLike

ВУЗ: 

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

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

Рубрика: 

51
1. Определить функцию ),( y
x
f
, полученную из функций )(
x
ϕ
и ),,( zy
x
ψ
по
схеме примитивной рекурсии.
1)
x
x
=)(
ϕ
, zzy
x
=),,(
ψ
.
2)
x
x
=)(
ϕ
, z
x
zy
x
+=),,(
ψ
.
3)
x
x
=)(
ϕ
, zy
x
zy
x
−+=),,(
ψ
.
4)
x
x
=)(
ϕ
,
2
),,( zzyx =
ψ
.
5)
1)( =
x
ϕ
,
x
zzy
x
=),,(
ψ
.
6)
1)( =
x
ϕ
,
xy
zy
x
=),,(
ψ
.
7)
0)( =
x
ϕ
, zxzyx +=
2
),,(
ψ
.
8)
1)( =
x
ϕ
,
z
x
zyx =),,(
ψ
.
9)
0)( =
x
ϕ
, xzzyx −=),,(
ψ
.
10)
0)( =
x
ϕ
, y
x
zy
x
+=),,(
ψ
.
2.
Доказать, что следующие функции примитивно-рекурсивны.
1)
a
x
f
=)(.
2)
a
x
x
f
+=)(.
3)
⎩
⎨
⎧
>
=
=
.0 если ,1
,0 если ,0
)sgn(
x
x
x
4)
xy
y
x
f
=),(.
5)
!),(
x
y
x
f
= .
6)
⎩
⎨
⎧
>
=
=
.0 если ,0
,0 если ,1
)(sgn
x
x
x
7)
y
xyxf =),(.
3. Записать схему примитивной рекурсии для произвольных примитивно-
рекурсивных функций при
1)
1=n ;
2)
2=n ;
3)
3=n .
4. Найти функции, получаемые из данной числовой функции ),,(
321
xxxf с
помощью оператора минимизации по каждой ее переменной.
1)
2
2
1321
),,( xxxxxf −= .
2)
(
)
12),,(
2321
1
+= xxxxf
x
.
3)
21321
),,( xxxxxf −= .
4)
1),,(
2
21321
+= xxxxxf
.
5)
2
3
1321
),,( xxxxxf += . 
       1. Определить функцию f ( x, y ) , полученную из функций ϕ (x) и ψ ( x, y, z ) по
схеме примитивной рекурсии.
1) ϕ ( x) = x , ψ ( x, y, z ) = z .
2) ϕ ( x) = x , ψ ( x, y, z ) = x + z .
3) ϕ ( x) = x , ψ ( x, y, z ) = x + y − z .
4) ϕ ( x) = x , ψ ( x, y, z ) = z 2 .
5) ϕ ( x) = 1, ψ ( x, y, z ) = xz .
6) ϕ ( x) = 1 , ψ ( x, y, z ) = xy .
7) ϕ ( x) = 0 , ψ ( x, y, z ) = x 2 + z .
                                x
8) ϕ ( x) = 1 , ψ ( x, y, z ) = .
                                z
9) ϕ ( x) = 0 , ψ ( x, y, z ) = z − x .
10) ϕ ( x) = 0 , ψ ( x, y, z ) = x + y .

          2. Доказать, что следующие функции примитивно-рекурсивны.
1)    f ( x) = a .
2)    f ( x) = x + a .
                  ⎧0, если x = 0,
3)   sgn( x) = ⎨
                  ⎩1, если x > 0.
4)    f ( x, y ) = xy .
5)    f ( x, y ) = x! .
                  ⎧1, если x = 0,
6)   sgn ( x) = ⎨
                  ⎩0, если x > 0.
7) f ( x, y ) = x y .

      3. Записать схему примитивной рекурсии для произвольных примитивно-
рекурсивных функций при
1) n = 1 ;
2) n = 2 ;
3) n = 3 .

       4. Найти функции, получаемые из данной числовой функции f ( x1 , x2 , x3 ) с
помощью оператора минимизации по каждой ее переменной.
                          2
1) f ( x1 , x2 , x3 ) = x1 − x2 .
2) f ( x1 , x2 , x3 ) = 2 x1 ( x2 + 1) .
3) f ( x1 , x2 , x3 ) = x1 − x2 .
                              2
4) f ( x1 , x2 , x3 ) = x1 x2 + 1 .
5) f ( x1 , x2 , x3 ) = x13 + x2 .



                                            51

Страницы