[ Pobierz całość w formacie PDF ]

jest także rekurencyjna.
D o w ó d. Ponieważ ��(x) = � (h1(x), . . . , hk(x)), to na mocy warunku (iv) definicji
rodziny funkcji rekurencyjnych mamy, że � "Rec.
Twierdzenie. Jeżeli relacja � jest rekurencyjna oraz jeśli "x"y�(x, y), to f(x) =�x�(x, y)
jest także rekurencyjna.
Do wó d. Ze względu na fakt, że f(x) =�x[� (x, y) =0] mamy na mocy definicji rodziny
funkcji rekurencyjnych iż f "Rec.
Twierdzenie. Każda funkcja stała jest rekurencyjna.
Do wó d. Jeśli fk jest symbolem n-argumentowej funkcji stałej przyjmującej wartość k,
to posługując się metodą indukcji matematycznej względem k wykażemy, że fk jest rekurencyjna
dla każdego k "N .
Jeśli k =0, to mamy:
n+1
f0(x) =�x(In+1 (x, y) =0).
Przypuśćmy teraz, że fk jest rekurencyjna. Wykażemy, że fk+1 jest także rekurencyjna. Mamy
wtedy:
fk+1(x) =�x(fk(x)
 94 
Na mocy założenia indukcyjnego oraz poprzedniego twierdzenia funkcja fk+1 jest rekurencyjna.
Dla relacji i � możemy posługując się spójnikami zdaniowymi określić nowe relacje. Mamy
mianowicie:
(
( (" �)(x) a" (x) (" �(x)
( '" �)(x) a"
( �! �)(x) a"
( a" �)(x) a"(
Twierdzenie. Jeśli relacja jest rekurencyjna, to relacja
Jeżeli rekurencyjną są relacje i �, to rekurencyjne są także relacje: (" �, �! �, '" � oraz
a" �.
Do wó d. Pomijamy.
Twierdzenie. Relacje
Do wó d. Pomijamy.
Twierdzenie. Jeśli jest relacją rekurencyjną, to funkcja określona rónością
f(x, x) =�yy
jest funkcją rekurencyjną.
Do wó d. Pomijamy.
Okazuje się, że kwantyfikatory, w odróżnieniu od spójników zdaniowych wyprowadzają poza
klasę relacji rekurencyjnych. Jednak kwantyfikatory o ograniczonym zakresie uważane niekiedy
za  słabsze zachowują włąsność spójników zdaniowych tzn. nie wyprowadzają poza kladę Rec.
Mamy mianowicie, że jeśli t jest dowolną liczbą naturalną natomiast �(x) dowolną formułą
zawierającą x jako zmienną wolną (niekoniecznie jedyną), to możemy określić dwie operacje:
"x
"x
"x
Bezpośrednio w tych definicji mamy nstępujący wynik.
Twierdzenie. Jeśli jest relacją rekurencyjną, to relacje � oraz � spełniające warunki:
�(x, x) a""y
�(x, x) a""y
są także relacjami rekurencyjnymi.
Nierówności ostre (w zbiorze liczb naturalnych) możemy zastąpić poprzez nierówności słabe.
Mianowicie nierówność x d" t jest z tym zbiorze równoważna nierówności x
 95 
.
Jeśli x i y są liczbami naturalnymi, to funkcję : N� N�!N określamy warunkiem:
x - y, gdy x e", y
.
x y =
0, gdy x
.
Twierdzenie. Funkcja : N� N�!N jest rekurencyjna.
.
Do wó d. x y = �t(y + t = x (" x
Twierdzenie. Dla funkcji rekurencyjnych g1, . . . , gk oraz n-członowych relacji rekuren-
cyjnych 1, 2, . . . , k o tej własności, że dla każdego układu x liczb naturalnych zachodzi dokład-
nie jedna z relacji 1(ux), 2(x), . . . , k(x) jeśli funkcja f spełnia warunki:
�#
g1(x), gdy 1(x),
�#
�#
. . .
. . .
f(x) =
. . .
�#
�#
gk(x), gdy k(x),
to f jest funkcją rekurencyjną.
Do wó d. Ma miejsce równość:
f(x) =g1(x) � �
1 k
Bezpośrednio z definicji funkcji rekurencyjnej oraz twierdzenia o rekurencyjności relacji gen-
erowanych przez spójniki zdaniotwórcze wynika rekurencyjność tak określonej funkcji f.
Twierdzenie. Dla relacji rekurencyjnych �1, . . . , �k oraz relacji rekurencyjnych 1, . . . , k
o tej własności, że dla każdego układu x liczb naturalnych zachodzi dokładnie jedna z relacji
1(ux), . . . , k(x) jeśli relacja � spełnia warunki:
�#
�1(x), gdy 1(x),
�#
�#
. . .
. . .
�(x) =
. . .
�#
�#
�k(x), gdy k(x),
to � jest relacją rekurencyjną.
Do wó d. Ma miejsce równość:
�#
�� (x), gdy 1(x),
�#
1
�#
�#
. . .
. . .
��(x) =
. . .
�#
�#
�#
�� (x), gdy k(x),
k
Przedstawiony ciąg twierdzeń pozwala uzasadnić fakt, że następujące funkcje są rekuren-
cyjne. Są takimi funkcje:
1. funkcja poprzednika P (x):
.
x 1, gdy x>0,
P (x) =
0, gdy x =0,
 96 
2. funkcja |x - y|:
.
x y, gdy x e" y,
|x - y| =
.
y x, gdy x
3. funkcja signum:
1, gdy x =0,
sgn (x) =
0, gdy x =0,
4. funkcja mniejsza z dwóch liczb min(x, y)
. .
min(x, y) =x (x y),
5. funkcja najmniejsza z n liczb min(x1, x2, . . . , xn):
min(x1, . . . , xn+1) = min(min(x1, . . . , xn), xn+1)
6. funkcja większa z dwóch liczb max(x, y):
.
max(x, y) =y +(x y),
7. funkcja największa z n liczb max(x1, x2, . . . , xn):
max(x1, . . . , xn+1) = max(max(x1, . . . , xn), xn+1)
8. relacja podzielności Div(y, x) (liczba y dzieli liczbę x):
Div(y, x) a""zd"x(x = y � z),
9. relacja bycia liczbą pierwszą Pr(x)
Pr(x) a" x =0 '" x =1 '" x = �zzd"x(z >1 '" Div(x, z)).
Jeśli potraktujemy zbiór jako relację jednoczłonową (unarną), to dostajemy następujące
fakty.
Twierdzenie.
(i) Dopełnienie dowolnego zbioru rekurencyjnego jest zbiorem rekurencyjnym.
(ii) Suma i iloczyn zbiorów rekurencyjnych jest zbiorem rekurencyjnym.
(iii) Każdy zbiór skończony jest rekurencyjny.
D o w ó d. Ponieważ zbiory można traktować jako relacje jednoczłonowe (unarne), to
punkty (i) oraz (ii) są tego faktu bezpośrednimi kinsekwencjami.
Rozpatrzmy teraz przypadek (iii). W sytuacji, gdy A jest zbiorem pustym, to mamy a "
A a" a
rekurencyjna, to zbiór A jest na mocy tego twierdzenia rekurencyjny. Przyjmijmy obecnie, że
A = {k1, . . . , kn}. Wówczas mamy:
a " A a" a = k1 (" . . . (" a = kn [ Pobierz całość w formacie PDF ]