WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Нумерації. Теореми про нерухому точку - Реферат

Нумерації. Теореми про нерухому точку - Реферат

Реферат на тему:

Нумерації. Теореми про нерухому точку

1. КОДУВАННЯ ТА НУМЕРАЦІЇ. КАНТОРОВІ НУМЕРАЦІЇ

Під кодуванням множини А на множиніВ будемо розуміти ін'єктивне та сюр'єктивне відображення  : АВ таке, що існують алгоритми A та B:

для кожного аА A(а)(а);

для кожного bB B(b)= -1(b).

Нумерацiєю множини А називають сюр'єктивне функцiональне вiдображення : NА.

Однозначною нумерацiєю множини А називають бієктивне вiдображення : NА.

Нумерацiю : NА називають ефективною, якщо iснують алгоритми A та B такі:

для кожного аА A(а)-1(а);

для кожного nNB(п)=(п).

Таким чином, : NА  ефективна нумерація  -1: АN  кодування А на N.

Введемо однозначні ефективні нумерацiї пар та n-ок натуральних чисел, які називаються канторовими нумераціями.

Всi пари натуральних чисел розташуємо в послiдовнiсть так:

пара (x, y) передує парі (u, v)  x+y<u+vабо (x+y = u+v та x<y).

Номер пари (x, y) в такiй послiдовностi позначають C(x, y) та називають канторовимномером пари (x, y).

Неважко переконатись, що C(x, y) = [(x+y+1)(x+y)/2]+x

Лiву та праву компоненти пари з номером n позначають вiдповiдно l(n) та r(n). Функцiї l(n) та r(n) називають вiдповiдно лiвою та правою координатними функцiями.

Функцiя C(x, y) задає бiєкцiю NNN, пара функцiй (l(n), r(n)) задає бiєкцiю NNN. При цьому функцiї C, l та r зв'язaнi такими тотожностями:

C(l(n), r(n)=n; l(C(x, y))=x; r(C(x, y))=y.

Маючи нумерацiю пар натуральних чисел, можна ввести нумерацiю n-ок натуральних чисел для довiльного n>2:

Cп(x1,x2,..., xп)=Cп1(C(x1, x2), x3,..., xп)=C(...С(C(x1, x2), x3),...), xп).

Координатнi функцiї Cn1, ..., Cnn вводимо так:

Нехай Cп(x1, x2,..., xп)=m; тоді Cn1(m)=x1; Cn2(m)=x2; ... , Cnn(m)=xn.

Для функцiй Cп, Cn1, ..., Cnn справджуються такi тотожностi:

Cп(Cn1(x), ..., Cnn(x))=x;

Cnk(Cп(x1, x2,..., xп))=xk, 1kn.

Теорема 1.1.1)Функцiї C(x, y), l(n) таr(n) є ПРФ.

2) ФункцiїCп, Cn1, ..., Cnnє ПРФ.

Приклад 1. Знайдемо l(100) та r(100). Для х=l(100) та у=r(100) маємо рівняння С(х, у)=100. Нехай х+у=р. Тоді р є найбільшим натуральним числом, для якого р(р+1)2100. Звідси р=13. Маємо х+у=13, х=100-[(1314)/2]=9, y=13-9=4. Отже, l(100)=9 та r(100)=4.

Приклад 2. Розв'яжемо рівняння C4(x,y,z,v)=207. За визначенням маємо С(С(С(x,y),z),v)=207. Нехай С(С(x,y),z)=а, маємо C(а,v)=207. Нехай a+v=р. Тоді р є найбільшим натуральним числом, для якого р(р+1)2207. Звідси р=19, звідки а=17 та v=2. Тепер маємо С(С(x,y),z)=17. Нехай С(x,y)=b, тоді C(b,z)=17. Нехай b+z=q. Тоді q є найбільшим натуральним числом, для якого q(q+1)217. Звідси q=5, звідки b=2 та z=3. Маємо C(x,y)=2, звідки x=1 та y=0.

Приклад 3. Задамо однозначну ефективну нумерацiю всiх скiнченних послiдовностей натуральних чисел на основі наступного кодування :→N таких послідовностей:

()=0;

(а1,..., ап)= C(Cп(а1,..., ап), п-1)+1.

Зрозуміло, що таке відображення бієктивне. Тепер обернене відображення η=-1  шукана однозначна нумерацiя.

Приклад 4. Однозначну ефективну нумерацiю всiх скiнченних послiдовностей натуральних чисел можна задати на основі такого кодування :→N всіх скiнченних послiдовностей:

()=0;

(а1,..., ап)=++...+.

Бiєктивнiсть вiдображення  випливає iз однозначностi подання кожного натурального числа в двiйковiй системi числення. Обернене відображення =-1  шукана однозначна нумерацiя.

Приклад 5. Однозначну ефективну нумерацiю всiх непорожніх скiнченних послiдовностей натуральних чисел задамо на основі кодування :→N, що є модифікацією кодування :

(а1,..., ап)=++...+-1.

Обернене відображення =-1  шукана однозначна нумерацiя.

Приклад 6. Ефективну нумерацiю  множини формул довiльної мови 1-го порядку із злiченним алфавiтом введемо таким чином.

Занумеруємо множини предметних імен x0, x1, ..., константних символiв c0, c1, ... , функцiональних символiв f0, f1, ... та предикат-них символiв p0, p1,... . Кодування  термiв та формул.задамо так:

(xk)=7k ;

(ck)=7k+1;

(fk t1...tn)=7C(Cn+1(k, (t1),...,(tn)), n1)+2;

(pk t1...tn)=7C(Cn+1(k, (t1),...,(tn)), n1)+3;

()=7C(k,())+4;

()=7C((), ())+5;

(xk)=7C(k,())+6.

Номером (індексом) довiльної формули  вважатимемо її код (). Всi тi натуральнi числа, якi не є кодами формул, вважатимемо номером формули x0=x0 . Зрозуміло, що так введена нумерація  неоднозначна. Формулу з номером n позначатимемо n.

Loading...

 
 

Цікаве