[ 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 ]