Алгоритмічні проблеми — страница 3

  • Просмотров 6797
  • Скачиваний 62
  • Размер файла 80
    Кб

позначення і терміни, що будуть використані надалі. 1. Множини Для позначення множин звичайно будуть використовуватися прописні букви А, В, С…. Тут хА позначає, що х є елементом множини А чи належить множині А, а хА означає, що х не належить множині А. Позначення {х/… х…}, де…х… є деяке твердження, що включає х, означає множину всіх об'єктів х, для яких…х… вірно. Так, {х/х є парним натуральним числом} є множина {0,2, 4,6,…}. Якщо А, В суть

множини, то запис A В означає, що А міститься (як частина) в В (чи А є підмножиною В); запис АВ означає, що АВ, але АВ (тобто А є власною підмножиною В). Об'єднання множин А, В, є множина {х| хА чи хВ (чи відразу двом множинам А, В)} і позначається А U В; перетин А, В є множина {х/хА і хВ} і позначається через АВ. Різниця (чи відносне доповнення) множин А, В є множина {х / хА і хВ} і позначається А\В. Порожня множина позначається через 0. Стандартний

символ N позначає множину натуральних чисел {0, 1, 2, 3,…}. Якщо А – множина натуральних чисел (тобто АN), то А позначає доповнення до А до N, тобто N\А. Через N+ позначається множина додатніх натуральних чисел {1,2,3,…}, а множина цілих чисел позначається через Z. Упорядкована пара елементів х, у позначається (х, у); таким чином, (х, у)(у, х). Картезіанським, чи декартовым, добутком множин А и В називається множина {(х, у)/хА, уВ}, і позначається

вона через АВ. Більш узагальнено, запис (х1…, хn) позначає упорядкований n-набір (п-ку) елементів х1,…, хn; часто цей n-набір позначається однією жирною буквою х. Якщо А1,…, Аn суть множини, те А1…Аn позначає множину n-ок {(х1,…, хn) /х1 А1 і х2 А2…хnАn}. Добуток АА…А (п разів) скорочено позначають як Аn; а А1 означає просто А. 2. Функції Ми припускаємо, що читач знайом з основним поняттям функції і розходженням між функцією f і окремим значенням f(х)

на даному х, на якому функція визначена. Областю (визначення) функції f називається множина {x/f(x) визначена} і позначається Dom(f); ми будемо говорити, що f (х) не визначена, якщо xDom(f). Множина {f (х) | х Dom (f)} називається множиною значень, чи образом (range), функції f і позначається через Ran (f). Якщо А и В – множиниі, то будемо говорити, що f є функція з A в В, якщо Dom (f)A и Ran(f)В. Коли Dom(f)=A, буде застосовуватися позначення f: Ar. Функція називається

ін’єктивною, якщо з х, у 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 є функцією,