Учебное пособие: Алгоритмічні проблеми

Функція називається ін’єктивною, якщо з х, у Dom (f) і ху випливає f(х) f (у). Для ін’єктивної функції f через f ^-1 позначається функція, зворотня до f , тобто така єдина функція g, що Dom (g)=Ran (f ) g (f(x))=x для всіх х Dom (f). Функція f з А в В називається сюр’єктивною, якщо Ran(f )=B.

Якщо f: A В и функція f ин’єктивна (сюр’єктивна), то f називається ін'єкцією (з А в В) (сюр’єкцією (з А в В)). Функція, що є одночасно ін'єкцією і сюръекцией, називається биекцией.

Припустимо, що f є функцією, а Х – множина. Обмеженням f на Х називається функція з областю визначення ХDom(f ), значення якої в кожному х Х Dom (f ) дорівнює f(x).

Обмеження f на Х позначається через f|X. Ran (f |X) позначається через f(X). Якщо Y – множина, то прообразом Y відносно f називається множина f^-1 (Y)={x|f(x)Y}. (Помітимо, що прообраз визначений навіть тоді, коли функція не ин’єктивна.)

Якщо f, g-функції , то будемо говорити, що g продовжує f, коли Dom (f) Dom (g) і f(х) = g (х) для всіх х Dom (f); у коротшому запису: f= g/Dom(f). Це відношення функцій f, g записується як f g.

Композиція двох функцій f і g є функція з областю визначення {x/xDom(g) і g(x)Dom(f)}, значення якої, коли вона визначена, є f (g(x)). Цю функцію позначають через fg .

Через f₀ позначаємо ніде не визначену функцію; тобто Dom(f₀ )=Ran(f₀ )=0. Очевидно, що f₀ =g|0 для будь-якої функції g.

В обчисленнях нам часто будуть зустрічатися функції чи вирази, що включають функції, що не усюди визначені. У таких випадках дуже зручне наступне позначення. Нехай a(x) і b(х) – вирази , що включають змінні х =(х₁ ,…, х_n ) . Тоді запис а(x) b(x) означає, що для кожного х вираження а(x) і b(x) або одночасно визначені і рівні, або обидва не визначені. Так, наприклад, для функцій f і g запис f(x)g(x) означає, що f=g; і для довільного числа y запис f(x) y означає, що f(x) визначена і дорівнює y (оскільки y завжди визначене).

Функції від натуральних чисел. У більшій частині цієї книги ми будемо мати справу з функціями від натуральних чисел, тобто з функціями з Nⁿ в N для різних п, здебільшого для п = 1 чи 2.

Функція f з Nⁿ в N називається п-місною функцією. Значення f на п-кі (x₁ ,…, х_n ) Dom (f ) записується як f(x₁ ,…, x_n ) чи f(x), якщо x представляє (x₁ ,…, x_n ). У багатьох книгах і статтях термін часткова функція використовується для позначення функції з Nⁿ у N, область визначення якої не обов'язково збігається з Nⁿ . Для нас слово функція означає часткову функцію. Проте при нагоді ми будемо писати «часткова функция», щоб підкреслити її можливу «не усюди визначеність». Тотальною функцією з Nⁿ у N ми називаємо функцію з Nⁿ у N), область визначення якої є всі Nⁿ . ^l

Ми затушовуємо розходження між функціями і їхнім значеннями в різних крапках, особливо у випадку теоретико-числових функцій у двох досить стандартних і недвозначних ситуаціях. По-перше, ми допускаємо такі фрази як «Нехай f (x₁ ,…, x_n ) – функція…», що означає, що f є n-місною функцією. По-друге, ми часто описуємо функцію в термінах її значення, що задається деякою формулою. Наприклад, «функція х² » означає «одномісна функція f, значення якої в кожному х N є х² »; аналогічно «функція х + у» означає «двомісна функція», значення якої в кожній парі (х, у) N² є х+ у.

Функцію, тотожно рівну 0 на N, ми позначаємо через 0, і взагалі для т N функцію NN, значення якої усюди дорівнює т, ми позначаємо жирним символом т .

3. Відношення і предикати

Якщо А – множина, то властивість М(х₁ ,…, х_n ), що виконується на деяких n-ках з Аⁿ і не виконується (чи помилкове) на всіх інших n-ках з Aⁿ , називається п-місним відношенням, чи предикатом на А.

Наприклад, властивість х<у є двомісне відношення (чи предикат) на N; 2 < 3 виконується (чи істинно), тоді як 9 < 5 не виконується (чи хибно). Інший приклад: кожна n-місна функція f з Nⁿ у N приводить до (п + 1) – місцевого предиката М (х, у), що задається умовою:

М (x_{1 ,} …, х_n, у), якщо і тільки якщо f (x₁ ,…, x_n ) у.

Відношення еквівалентності і порядку. (Читач, не знайомий з цими поняттями, може при бажанні відкласти читання цього параграфа доти, поки він не буде потрібен в гл. 9.) У гл. 9 ми зустрінемося із двома спеціальними видами відносин на множині А.

(a) Бінарне відношення R на множині А називається відношенням еквівалентності, якщо для всіх х, у, zА виконуються три наступні властивості:

(i) (рефлективність) R (х, х);

(іі) (симетрія) R (х, y)R (у, х);

(iii) (транзитивність) якщо R (x, y) і R (у, z ), то R (х, z). Говорячи, що х, y еквівалентні (у деякому спеціальному змісті), ми маємо на увазі відношення R (х, у). Потім ми визначаємо клас еквівалентності х як множина {у | R (х, у)}, що складається з всіх елементів, еквівалентних х.

(b) Двомісне відношення R на множині А називається частковим порядком, якщо для всіх х, у, z A.

(i) (іррефлексивность) не R (х, х);

(іі) (транзитивність) якщо R (х, у) і R (y, z), те R (x, z).

Частковий порядок звичайно позначається символом <, і ми віддаємо перевагу запису х < у запису < (х, у). Часто визначають частковий порядок, вводячи спочатку предикат < (позначающий < чи =) із властивостями:

(i) хх;

(ii) якщо xy і ух, те х=у;

(iii) відношення транзитивно, а потім визначаючи х < у як х у и х у .

4. Логічні позначення