Реферат на тему:
Eфективні операції на функціях та множинах
Множину всіх n-арних функцій на N, тобто функцiй iз Nп в N, позначимо Fп. Об'єднання множин Fп для всіх п(1 позначимо F. Множину всіх тотальних функцій із Fп та множину всіх тотальних функцій із F відповідно позначимо Tп та T . Cкінченні множини в цьому розділі позначаємо F, скінченні функції позначаємо (.
Довільну функцію вигляду (: (2N)m\x21922N назвемо m-арним множинним оператором (скорочено МО).
Довільну функцію вигляду \x03A8: (F)m\x2192F назвемо m-арним функціональним оператором (скорочено ФО).
Функціональні оператори називають також операціями на функціях, або композиціями.
Приклад. Операції суперпозиції Sn+1 : (F)m\x2192F, примітивної рекурсії R : F(F \x2192F та мінімізації M : F(F\x2192F є прикладами ФО.
МО (: (2N)m\x21922N називається монотонним, якщо із умови А1(В1 , А2 (В2 , ..., Ат (Вт випливає ((А1 , ..., Ап) (((В1 , ..., Вп).
ФО (: (F)m\x2192F називається монотонним, якщо із умови f1 (g1 , f2 (g2 , ..., fт (gт випливає ((f1 , ..., fп) (((g1 , ..., gп).
МО (: (2N)m\x21922N називається неперервним, якщо для всіх х(N, A((2N)m маємо х(((A) ( ( F(A : х(((F).
ФО (: Fп\x2192F називається неперервним, якщо для всіх х(Nп, y(N та f(Fп маємо (х, у)(((f) ( (( (f : (х, у)(((().
Легко довести, що кожний неперервний оператор є монотонним.
11.1. ОПЕРАТОРИ ПЕРЕЛІКУ. ЧАСТКОВО РЕКУРСИВНІ ТА РЕКУРСИВНІ ОПЕРАТОРИ
Ефективність множинного оператора (: 2N\x21922N означає можли-вість ефективно задати множину ((A), якщо ефективно задається множина А. Ефективні множинні оператори називаються [10] операторами переліку (скорочено ОП).
Для кожного z(N оператор переліку (z : 2N\x21922N задається співвідношенням (z(A) ={x | (u(Fu (А ( C(x, u)(Dz)}.
Інакше кажучи, x((z(A) ( (u(Fu (А ( C(x, u)(Dz).
Теорема 11.1.1. Кожний оператор переліку є неперервним та монотонним.
Множина А(N однозначна, якщо С -1(А)={(l(x), r(x))} є функціо-нальним відношенням. Зрозуміло, що A однозначнa ( (Сm+1)-1(A) є функціональним відношенням для кожного m(1. Отже, множина A однозначнa ( (m(1 (f(Fm : A=Сm+1(f). Тому для множини всіх однозначних множин можна ввести наступне позначення:
CF ={С(f) | f(F1}={Сm+1(f) | f(Fm}.
Кожний функціональний оператор (: Fm\x2192Fn задає множинний оператор (: CF\x2192CF та навпаки:
( : Fm \x2192 Fn
Сm+1(((Сm+1)-1 Сn+1(((Сn+1)-1
( : CF \x2192 CF
Звідси ((f)=(Сn+1)-1(((Сm+1(f))) та ((A)=Сn+1((((Сm+1)-1(A))).
ФО (: Fm\x2192Fn називається частково рекурсивним оператором (ЧРО), якщо існує z(N таке, що для всіх f(Fm маємо:
В цьому випадку кажуть, що ОП (z визначає ЧРО (.
Тотальний ЧРО назвемо рекурсивним оператором (РО).
Інакше кажучи, ФО (: Fm\x2192Fn \xF02D\xF020рекурсивний оператор, якщо
існує z(N таке: для всіх f(Fm ((f)=(Сn+1)-1((z(Сm+1(f))) (df1)
|
Скачати "Реферат на тему Eфективні операції на функціях та множинах"
