Дискретна математика

1.Множин — одне з основних понять сучасної математики. Строго воно не визначається, але може бути дано інтуїтивне визначення множини як сукупності певних і різних об'єктів довільної природи, яка розглядається як одне ціле. Об'єкти, які складають множину, називаються її елементами. Наприклад, можна говорити про множину усіх книг в певній бібліотеці, множину літер українського алфавіту або про множину всіх коренів певного рівняння тощо.

Основні поняття

Множина вважається озн ченою, якщо про кожен об'єкт, що розглядається, можна казати, що він або належить, або не належить множині. Ідентичні (тобто однакові) об'єкти в множині не допускаються. На письмі множини позначаються, як правило, великими літерами. Для деяких множин у математиці вживаються сталі позначення. Наприклад:

- множина натуральних чисел,

- множина цілих чисел,

- множина раціональних чисел,

- множина дійсних чисел,

- множина комплексних чисел.

Порожня множин в математиці — множина, яка не містить жодного елемента. Така множина позначається як Ø або {}.

Наприклад, якщо досліджується множина об'єктів, які повинні задовольняти певній властивості, і в подальшому з'ясовується, що таких об'єктів не існує, то зручніше сказати, що шукана множина порожня, ніж оголосити її неіснуючою. Порожню множину можна означити за допомогою будь-якої суперечливої властивості, наприклад: Ø = {x|x≠x} тощо. Разом із тим, твердження множина M — непорожня можна замінити рівносильним йому твердженням існують елементи, які належать множині M.

Розбиття множини

У математиці розбиттям множини А називають поділ цієї множини на непорожні підмножини, які не перекриваються (тобто немає жодного елемента, який би належав двом підмножинам одночасно). Розбиття множини - це подання її у вигляді об'єднання довільної кількості попарно непересічних підмножин. Множини, над якими виконується операція, назвемо опер нд ми, а множину, яка одержується в результаті виконання операції – результатом. У залежності від числа операндів операції над множинами розділяють на унарні (наприклад, доповнення), бінарні (наприклад, , ,\). До бінарних відноситься ще одна важлива операція – декартів добуток множин. Універсальною множиною називається така множина, яка включає в себе всі множини, що розглядаються в задачі.

2. Опер ції н д множин ми Доповнення т різниця множин

Нехай задана деяка множина U (універсальна множина або універсум). Якщо A U, то елементи множини U, які не належать А, називаються доповненням множини А до множини Uі позначають як CUA або UCA. Якщо A U, B U, то доповнення множини B до А називають різницею множин А та B (саме в такому порядку) і позначають А \ B або А-B, тобто A \ B = {x:x A x B}.

Примітка: Тут символ означає вимогу одночасної справедливості обох частин твердження (логічна зв'язка

"І", кон'юнкція). Парний з ним символ означає вимогу справедливості щонайменш одного з двох

тверджень (чи обох одночасно) (диз'юнкція, логічне АБО). Приклади:

{1, 2} − {червоний, білий} = {1, 2}

{1, 2, зелений} − {червоний, білий, зелений} = {1, 2}

{1, 2} − {1, 2} =

Якщо U - множина цілих чисел, то доповнення її підмножини A всіх парних чисел є підмножина В всіх непарних чисел.

1

Деякі вл стивості опер ції доповнення:

A A′ = U

A ∩ A′ =

(A′)′ = A

A − B = A ∩ B′

Об'єдн ння множин

Об'єднанням множин А та B називається множина, яка складається з усіх тих елементів, які належать хоча б одній з множин A, B:

A B = {x: x A A B}.

Приклади:

{1, 2} {червоний, білий} = {1, 2, червоний, білий}

{1, 2, зелений} {червоний, білий, зелений} = {1, 2, червоний, білий, зелений}

{1, 2} {1, 2} = {1, 2}

Деякі властивості операції об'єднання:

A B = B A

A A B

A A = A

A = A

Перетин множин

Перетином множин А та B називається множина, яка складається з усіх тих елементів, які належать кожній із множин А, B:

A ∩ B = {x: x A A B}.

Кажуть, що множини не перетин ються, якщо A ∩ B = Приклади:

{1, 2} ∩ {червоний, білий} =

{1, 2, зелений} ∩ {червоний, білий, зелений} = {зелений}

{1, 2} ∩ {1, 2} = {1, 2}

Деякі властивості перетину:

A ∩ =

Симетричн різниця множин

Симетрична різниця множин A та B є така множина елементів, які містяться в одній з цих двох множин, але не в обох. Позначається як A B.

Наприклад, симетрична різниця множин {1,2,3} та {3,4} є {1,2,4}.

Деякі вл стивості симетричної різниці:

A B = (A − B) (B − A)

A B = (A B) − (A ∩B)

3.Властивості операцій над множинами

Операції над множинами, як і операції над числами, мають певні властивості. Ці властивості виражаються сукупністю тотожностей незалежно від конкретного змісту множин, що входять у них, і є

підмножинами деякого універсуму U .

2

10.U , U

11.A \ B A B

12.A B A B \ A B

Ді гр ми Ейлер -Вен .

Довести закони алгебри висловлювань можна

1)побудувавши таблицю істинності

2)виконавши еквівалентні перетворення над правою і лівою частинами формули для приведення їх до одного вигляду.

3)За допомогою діаграм Ейлера-Вена

Леонард Ейлер при розв‘язуванні задач зображав множини кругами, і на його честь був названий цей метод. Однак при розв‘язуванні логічних задач такими колами корисно зображати висловлювання. Будь-яке висловлювання зображається кругом, а його заперечення – частиною площини, що знаходиться поза кругом.

4. Функцією (відображенням, трансформацією) f множини X в множину Y (позначається f : X → Y)

називається така відповідність між множинами X та Y, яка задовольняє наступним умовам: 1. Відповідність f всюди визначена, тобто, для будь-якого x з X існує такий y з Y,

що x f y (y є образом x для функції f), тобто, для будь-якого x з X існує хоча б один образ y з Y.

2.Відповідність f є відповідністю багато-до-одного, або функціональною, тобто, якщо x f y та x f z, то y = z, тобто, y може бути образом зразу декількох елементів з X, але один елемент x не може

породжувати більше одного образа з Y.

Елемент y з Y, який відповідає елементові x з X позначається як f(x).

Також можна сказати, що відображенням (функцією) з X в Y є така відповідність f A×B, в якій кожному елементові a Pr1f відповідає тільки один елемент з Pr2f (тут × — Декартів добуток множин, Pr1f та Pr2f — відповідні проекції відображення).

Множина всіх функцій f : X → Y позначається як YX. При цьому потужність множини |YX| = |Y||X|. Відповідність між X та Y, яка задовольняє тільки умові (1) називається багатозначною функцією. Будь-яка функція є багатозначною функцією, але не кожна багатозначна функція є функцією. Відповідність, яка задовольняє тільки умові (2) є часткова функція. Будь-яка функція є частковою, але не кожна часткова

3

функція є функцією. В цій енциклопедії функцією є така відповідність між множинами, яка задовольняє одночасно умовам (1) та (2), якщо інше не вказується додатково.

Функції багатьох змінних, де y=f(x1, … , xn), тобто де y одночасно залежить від n змінних, можна визначити як відображення виду f: Xn → Y, де Xn — n-степень множини X .

Існують спеці льні н зви для деяких в жливих різновидів функцій:

Ін'єктивна функція — функція, в якій різним значенням аргумента відповідають різні результати, тобто, для двох елементів x, y з Y виконується: f(x) = f(y) тоді й тільки тоді, якщо x =y.

Сюр'єктивна функція — функція f:X→Y, область значень якої збігається з множиною Y, тобто, для кожного y з Y існує x з X такий, що f(x) = y.

Бієктивна функція — функція, яка є одночасно сюр'єктивною та ін'єктивною, тобто встановлює взаємно однозначну відповідність між елементами множин X та Y.

Композиція функцій

З функцій f: X → Y та g: Y → Z можна побудувати композицію функцій таким чином: спершу

застосувавши f до аргумента x з X, а потім застосувавши g до результата. Така композиція функцій позначається g o f: X → Z, тобто (g o f)(x) = g(f(x)) для всіх x з X.

Тотожн функція, вкл дення, продовження т звуження

Відображення (функція) E: X → X, таке, що E(x) = x для будь-якого x з X, має назву тотожного відображення, про яке говорять, що воно відображує X в себе.

Відображення I: X → Y, яке відображує елемент x з X в такий же елемент, але в Y, називається вкладенням

Відображення g': X → Y називається звуженням (обмеженням) відображення g: X' → Y' , якщо X та Y є підмножинами X' та Y' відповідно. Відображення g, в свою чергу,

називається продовженням відображення g'.

Обернен функція

Деякі функції мають відповідні обернені функції. Нехай f: X → Y та g: Y → X деякі функції.

Якщо композиція функцій f o g = EY, де E: Y→Y — тотожне відображення, то f має назвулівого

оберненого до g, а g — правого оберненого до f. Якщо справедливо і f o g = EY і g o f = EX, то g має до f і позначається як f−1.

5. Сюр'єкція (сюр'єктивне відображення, сюр'єктивна функція, відображення на) —

в математиці відповідність між двома множинами, в якій з кожним елементом другої множини асоціюється

щонайменш один (або більше) елементів першої множини. Властивості

Функція f: X → Y сюр'єктивна тоді й тільки тоді, якщо існує функція g: Y → X така, що композиція функцій f o g є тотожним відображенням на Y.

За визначенням, функція бієктивна тоді й тільки тоді, коли вона одночасно сюр'єктивна та ін'єктивна.

Якщо f o g сюр'єктивна, то f також сюр'єктивна.

Якщо f та g обидві сюр'єктивні, то f o g сюр'єктивна.

f: X → Y сюр'єктивна тоді й тільки тоді, якщо для будь-яких g,h:Y → Z, якщо g o f = h o f, то g = h.

Якщо f: X → Y сюр'єктивна і B є підмножиною Y, то f(f −1(B)) = B. Таким чином, B може бути відновлена за прообразом f −1(B).

Будь-яка функція h: X → Z може бути визначена як композиція деяких функцій h = g o f для деякої сюр'єкції f та ін'єкції g.

Якщо f: X → Y сюр'єктивна, то X має щонайменш стільки ж елементів, як і Y, в сенсі потужності множин.

Якщо обидві множини X та Y є скінченні з однаковою кількістю елементів, то f : X → Y сюр'єктивна тоді

й тільки тоді, якщо f ін'єктивна.

Ін'єкція (ін'єктивне відображення, ін'єктивна функція) — в математиці таке співвідношення між елементами двох множин, яке одному елементу з першої множини зіставляє один і тільки один елемент з другої множини.

Вл стивості

Функція f : X → Y є ін'єктивною тоді й тільки тоді, якщо X є порожня множина, або існує функція g : Y → X така, що композиція функцій g o f є тотожним відображенням на X.

4

За визначенням, функція є бієктивною, якщо вона є ін'єктивною та сюр'єктивною.

Якщо g o f є ін'єктивною, то f також ін'єктивна.

Якщо обидві f та g ін'єктивні, то g o f ін'єктивна.

f : X → Y ін'єктивна тоді й тільки тоді, коли для будь-яких функцій g, h : W → X, де f o g = f o h, виконується рівність g = h.

Якщо f : X → Y — ін'єктивна і A є підмножиною X, то f−1(f(A)) = A. Тобто, A може бути відновлений з образу функції f(A).

Якщо f : X → Y є ін'єктивним, і A та B є підмножинами X, то f(A ∩ B) = f(A) ∩ f(B).

Якщо f : X → Y — ін'єкція, то в Y щонайменше стільки ж елементів, скільки в X, в сенсі потужності множин.

Якщо X та Y — скінченні з однаковою кількістю елементів, то f : X → Y ін'єктивне тоді й тільки тоді, коли f є сюр'єктивним.

Бієкція (бієктивна функція, бієктивне відображення, взаємно однозначна відповідність) —

в математиці відображення, яке є одночасно сюр'єктивним та ін'єктивним.

Інтуїтивно можна визначити бієкцію як відповідність, яка асоціює один елемент вхідної множини з одним і тільки одним елементом результуючої множини і навпаки, одному елементу результуючої множини співставляється один і лише один елемент вхідної множини.

Тобто, відображення f: X→Y є бієктивним, коли кожному елементу y з множини Y співставлений один і лише один елемент x з множини X, і f(x) = y.

Властивості

Відображення f: X → Y є бієктивним тоді й тільки тоді, якщо існує відображення g: Y → X таке,

що композиція g та f (позначається g o f) є тотожним (нейтральним) відображенням наX, а f o g є тотожним відображенням на Y. Відображення g позначається як f−1 і має назву оберненого відображення.

Якщо f o g — бієктивна, то f сюр'єктивна, а g ін'єктивна.

Якщо f та g є бієктивні, то f o g також бієктивна.

6. Існують т кі способи з д ння функцій:

-за допомогою графіка, тобто перерахування пар підмножини декартового добутку, що визначає функцію (наприклад, функції F1, F2, F3, F4, F5 задані таким способом);

-за допомогою матриць;

-за допомогою виразів, аналітично, наприклад, y = x2;

-за допомогою алгоритму, що дозволяє для аргумента х отримати значення y.

A B називаєтьсяA B

бінарним відношенням між A і B (або просто на A, якщо A= B ). Для впорядкованої пари

a,b R використовують позначення aRb і кажуть, що a знаходиться у відношенні R з b .

Якщо ж два елементи a ,b не зв‘язані відношенням R , то записуємо (a,b) R, або (a,b).

Приклади. 1. Нехай A 1,2,3,4,5,6 . Визначимо на цій множині відношення

R A A: R x, y : x, y A, x дільник y, x 3, y 6 . Явний запис

відношення має вигляд:

R 1,1 , 1,2 , 1,3 , 1,4 , 1,5 , 2,2 , 2,4 , 3,3 .

2. Множина (x, y) R : x y є відношенням на множині N : (7,9) ; (9,9); (9,7) . 3. Множина (x, y) N : x y є відношенням на множині N : (4,2); (4,4), (2,4),

(9,7) .

4.Множина (x, y) R : x y є відношенням на множині R .

5.Множина всіх пар точок (x1, y1) , (x2 , y2 ) площини R2 таких, що x1 x2 , y1 y2

євідношенням ‖бути симетричним відносно осі Ox ‖.

5

6. Множина (x, y) : x R, y R задає добре знайомі декартові координати точки на

площині. Оскільки ця множина дорівнює множині R2 , то за означенням вона є відношенням.

7. На множині людей також можна вказати відношення: „бути начальником‖, „бути братом‖, „бути молодшим‖, „жити в одному місті‖, «вчитися в одній академгрупі».

Властивості бінарних відношень

Нехай R – бінарне відношення на довільній множині A ( R A2 ). Якщо для двох елементів a ,b (a,b) R , тобто a ,b знаходяться у відношенні R , то це записують як aRb . Якщо для двох елементів a ,b не виконується (a,b) R , то це записують як aRb .

Бінарне відношення R на довільній множині A можна зобразити за допомогою графа – стрілкової схеми, вузли якої відповідають елементам множини A, а дуга, спрямована від a до b

показує, що виконується (a,b) R .

Означення. Відношення R називається рефлексивним, якщо воно завжди виконується між елементом і ним самим. ( a A aRa ).

Приклади.

1.Відношення нестрогої нерівності на множинах N, Z, R .

На графі рефлексивного відношення для кожного вузла існує стрілка, яка починається і закінчується в цьому вузлі .

Означення. Відношення R називається антирефлексивным, якщо воно не виконується для будьякого елемента. ( a AaRa ).

Приклади.

1.Відношення строгої рівності на множинах N, Z, R .

2.Відношення „бути начальником‖, „бути братом‖, „бути молодшим‖ на множині людей. Приклад відношення, яке не є ні рефлексивним, ні антирефлексивним :

Відношення ‖бути симетричним відносно осі Ox ‖ не є ні рефлексивним, ні антирефлексивним

(точка є симетричною самій собі, якщо вона лежить на осі Ox , і не є симетричною самій собі в протилежному випадку)

Означення. Відношення R називається симетричним, якщо для будь-яких елементів a ,b при виконанні aRb виконується bRa . ( a,b A aRb bRa ).

Приклади:

1.Відношення рівності на множинах N, Z, R .

2.‖Бути симетричним відносно осі Ox ‖.

3.Відношення „бути братом‖ на множині людей.

На графі симетричного відношення для кожної стрілки, яка з‘єднує два вузла існує також стрілка, яка з‘єднує ці вузли у зворотному напрямку.

Означення. Відношення R називається антисиметричним, якщо aRb і bRa виконуються одночасно тоді і тільки тоді, коли a b . ( a,b A aRb i bRa a b)

Приклади:

1. Відношення нестрогої нерівності на множинах N, Z, R .

a b и b a a b .

На графі антисиметричного відношення існує хоча б одна пара вузлів, які зв‘язані двома стрілками. Зауваження. Властивості симетричності і антисиметричності не є взаємно виключними.

Означення. Відношення R називається асиметричним, якщо для будь-яких елементів a ,b або

aRb або bRa . ( a,b A aRb або bRa )

Приклади.

1.Відношення строгого включення в множині всіх підмножин деякого універсуму.

2.Відношення „бути батьком‖ в множині людей.

6

Означення. Відношення R називається транзитивним, якщо для будь-яких a,b, c A з

aRb і bRc випливає aRc . ( a,b, c A aRb i bRc aRc )

Приклади.

1.Відношення =, , «жити в одному місті».

2.Відношення ‗‗мати непорожній переріз‘‘ на системі множин не є транзитивним.

8.Відношення ч сткового порядку. Для дискретної математики характерне використання класів відношень, що визначені на різних множииах, але володіють тим ж набором властивостей.

Визначення. Бінарне відношення на множини R, що має властивості рефлексивності, антисиметричності і транзитивності, назвемо відношенням часткового порядку і будемо позначати .

Приклади відношення часткового порядку: 4 ; відношення на множині позитивних цілих чисел,

тобто 7 = (1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (2,2), (2,3), (2,4), (2,5), (2,6), (3,3), (3,4), (3,5), (3,6), (4,4), (4,5),

(4,6), (5,5), (5,6), (6,6)}; відношення включення R S на булеані P(U) і ін.

Визначення. Множина R, на якій задане відношення часткового порядку називається частково упорядкованою.

Для такої множини важливими характеристиками є: верхня універсальна границя I, якщо I ri для будь-якого ri R; нижня універсальна границя О, якщо О ri для будь-якого ri R.

Говорять ще, що О – найменший, а I – найбільший елемент множини R.

Лема 1. У будь-якій частково впорядкованій множині може існувати не більш однієї верхньої і не більш однієї нижньої універсальних границь.

Доведення. Дійсно, нехай існує два найменших елементи О і О*. Тоді справедливо О О* і О* О. Звідси по властивості антисиметричності О = О*. Аналогічно доводиться і випадок для I і I*. Лема доведена.

Існують частково впорядковані множини без універсальних границь, наприклад множина Z не має ні нижньої, ні верхньої універсальної границі, а множина N має тільки нижню універсальну границю.

Існують і скінченні частково впорядковані множини без універсальних границь, наприклад множина R={a,b,c,d,e,f} з визначеним на ній частковим порядком 8 = {(a,a), (b,b), (c,c), (a,b), (b,c), (a,c), (d,d), (e,e), (f,f), (d,e), (e,f), (d,f)}. Претенденти на нижні і верхні універсальні границі – елементи a, d і c, f означенню в дійсності не задовольняють.

Визначення. Якщо в частково впорядкованій множині виконується умова, що для будь-яких х,у має місце х у або у х, то вона називається лінійно впорядкованою.

Звідношенням часткового порядку пов'язаний ряд інших відношень:

строгого порядку х < y, що означає, що х у, але х у (ясно, що це іррефлексивне, асиметричне

ітранзитивне відношення);

незрівнянності х у, що означає, що ні х у, ні у х.

Тоді для кожної пари (х,у) R, де R – частково упорядкована множина, справедливо: або х = у, або х < у, або х > у, або х у.

Чому ми приділяємо багато часу відношенням порядку? Це пов'язано з тим, що в комп'ютеризованих системах у сфері керування реалізуються процедури застосування рішень на основі аналізу оцінок можливих рішень, причому множина оцінок звичайно становить собою частково упорядковану множину.

Природно, розроблювач пропонує процедуру, що за безпечує вибір екстремальної оцінки. У такий спосіб ми переходимо до необхідності введення на упорядкованих множинах границь. З універсальними границями ми вже знайомі, але їх недостатньо для аналізу всіх можливих ситуацій.

Елемент m частково упорядкованої множини R називається мінімальним (максимальним), якщо не існує такого ri R, що ri < m (ri > m).

Очевидно, якщо частково упорядкована множина має універсальну границю О (чи I), то вона є мінімальним (максимальним) елементом.

Легко привести приклад частково упорядкованої множини, що має декілька мінімальних і максимальних елементів: на множини R={a, b, c, d, e, f} розглянемо вже знайомий нам частковий порядок 8

= {(a,a), (b,b), (c,c), (d,d), (e,e), (f,f), (a,b), (b,c), (a,c), (d,e), (e,f), (d,f)}. Тоді a і d – мінімальні елементи, а c і f -

максимальні елементи.

Крім того, в частково упорядкованій множини можна погодити порядок з нумерацією.

Лема 2. Елементи скінченної частково впорядкованої множини R={r1,...,rn} завжди можна перенумерувати таким чином: R={х1 ...хn }, що з xi < xj буде випливати i < j.

Доведення. Початкову нумерацію виконаємо яким завгодно шляхом. Потім проведемо послідовно ряд перестановок: елементи в отриманій нумерації змінюємо місцями, якщо у відповідній парі графіку відношення вони стоять у зворотньому порядку. Очевидно, число таких перестановок рівне чи менше

7

числа пар. За побудовою нумерації для будь-якої пари xi < xj елемент xi отримає менший номер. Лема доведена.

Для аналізу мінімальних чи максимальних елементів по приналежності до частково впорядкованої множини R по відношенню до її підмножини S також вводять нові поняття.

Визначення. Назвемо елемент а R нижньою (верхньою) границею підмножини S, якщо а x (a x) для всіх х S.

Визначення. Назвемо елемент b R нижньою гранню підмножини S, якщо:

1)b – нижня границя підмножини S;

2)b b , де b - будь-яка нижня границя підмножини S.

Визначення. Назвемо елемент c R верхньою гранню підмножини S, якщо:

1)c – верхня границя множини S;

2)c c , де c - будь-яка верхня границя множини S.

Далі будемо писати b = inf S, c = sup S (infimum – наголос на другому i, supremum – наголос на e). Іноді використовуються терміни "точна нижня границя" і "точна верхня границя", відповідно.

Аналогічно тому як було доведено єдиність універсальних границь, можна довести єдиність верхньої і нижньої граней.

9.Відношення еквів лентності. Ще одним важливим класом бінарних відношень є відношення еквівалентності.

Визначення. Бінарне відношення на множині R, що має властивості рефлексивності, симетричності і транзитивності, назвемо відношенням еквівалентності і будемо позначати E або =.

Приклад відношення еквівалентності – відношення рівності.

З поняттям відношення еквівалентності тісно пов‘язане поняття розбиття, яке розглянене в попередній лекції. Розбиття часто застосовують при створенні комп‘ютеризованих систем, наприклад при створенні класифікаторів.

Теорема 1. Відношення Е є відношенням еквівалентності на множині R тоді і тільки тоді, коли воно визначає розбиття ПЕ на множині R.

Доведення. а) Пряме. Нехай задане розбиття П. Розглянемо відношення Е(П) таке, що ri Е(П) rj означає, що ri і rj належать одній і тій ж підмножині Ri розбиття П. Тоді відношення Е(П) – рефлексивне (тому що за побудовою ми включаємо в нього пари вигляду (ri,ri) для кожного ri R), симетричне (тому що за побудовою, якщо ми включаємо в нього пару вигляду (ri,rj), то включаємо і пару вигляду (ri,ri)), транзитивне (тому що за побудовою, якщо ми включаємо в нього пари вигляду (ri,rj) і (rj,rl), то включаємо і пару вигляду (ri,rl)). Таким чином, відношення Е(П) – відношення еквівалентності.

б) Обернене. Нехай задано на R відношення еквівалентності E. Легко побудувати функцію fE : R P(R), котра елементу ri ставить у відповідність підмножину PE (ri) = {rj R | (rj, ri) E}. Тому що відношення Е рефлексивне, то ri PE (ri), а отже PE(r1) PE(r2) PE(r3) ... PE(rn) = R. Залишається показати, що будь-які дві підмножини PE(ri) і PE(rl) або не перетинаються, або є рівними. Нехай це не так і є загальний елемент rj, але підмножини PE(ri) і PE(rl) не рівні. Але тоді справедливо riErj і rlErj. В силу симетричності відношення E, якщо виконується rlErj, то виконується rjErl. За наявності в відношенні E пар (ri,rj) і (rj,rl) в силу транзитивності відношення E в ньому присутня пара (ri,rl). З того, що для будь-якого rt PE(rl) справедливо rl E rt і, отже, в силу транзитивності справедливо ri E rt слідує, що PE(rl) PE(ri). Помінявши місцями елементи rI і rl, аналогічно встановлюємо справедливість PE(ri) PE(rl). Але це означає PE(ri) = PE(rl). Іншими словами, будь-які підмножини PE(ri) і PE(rl) або не перетинаються, або є рівними. З кожної групи таких рівних підмножин залишимо по одній підмножині, отримавши різні підмножини, що задовільняють другому обмеженню на розбиття. Теорема доведена.

Поняття розбиття дозволяє говорити про можливість визначення натуральних чисел на основі розбиття всіх існуючих в природі множин об‘єктів на підмножини, в кожній з яких між будь-якою парою множин можливо встановити взаємно однозначну відповідність. Тоді кожну підмножину можливо було б наділити тою єдиною характеристикою, котра відрізняла б її від інших підмножин і ми прийшли б до числа елементів множини, тобто до натуральних чисел.

Треба ще сказати, що поняття бінарного відношення припускає узагальнення на n-місні відношення через декартів добуток n множин.

10.Лів т пр в композиції. Визначення. Лівою композицією g ○ f будь-яких двох функцій називається функція, отримана в результаті їх застосування в порядку, оберненому написаному. Спочатку застосовується функція f, а потім - функція g за умови, що область функції g співпадає з кообластю функції f. Формально можемо записати: нехай f : S →T і g : T → U , тоді ліва композиція g ○ f є функція g ○ f : S → U, визначена правилом

8

відображень:

Вона ілюструє ту обставину, що ми можемо перейти з множини S в множину U чи безпосередньо, застосовуючи функцію h, чи в два кроки, застосовуючи спочатку функцію f , а потім - функцію g .

Операцію правої композиції f ◊ g отримуємо з описаної вище операції лівої композиції перестановкою символів: f ◊ g = g ○ f . Нехай, наприклад, φm: R → R — операція піднесення до ступеня m, φm (x) = xm. Подібно показнику ступеня m, символ функції φm можна записати праворуч від аргумента: xm =xφm. Якщо домовитися писати символи функцій φ, ψ,… праворуч від аргументу, то природно записувати їх композицію також в правій формі, тому що тоді виконується правило (x φ) ψ = x (φ ◊ ψ). Так, в попередньому прикладі x (φm ◊ φn) = (xm)n = xmn = x φmn, отже, φm ◊ φn= φmn. Інтуїтивно перевага правої композиції в тому, що функції пишуться в тому ж порядку, у якому вони виконуються.

Далі для зручності та скорочення запису символ операції лівої композиції ○ іноді будемо пропускати: композиція позначається просто записом символів функцій-аргументів у рядок.

Лема 3. Композиція функцій підкорюється асоціативному закону:

(h ○ g) ○ f = h ○ (g ○ f) = f ◊ (g ◊ h) = (f ◊ g) ◊ h

Вважається, що всі записані композиції визначені. Хоча інтуїтивно це очевидно, тому що як h ○ (g ○ f), так і (h ○ g) ○ f отримуються послідовним застосуванням функцій f, g і h саме в такому порядку. Те ж можна сказати стосовно f ◊ (g ◊ h) і (f ◊ g) ◊ h.

Доведення. Нехай f: S → T, g: T → U і h: U → V. Будь-якому елементу x S обидві композиції приписують значення

[(h g) f] x = (h g) (f x) = h (g (f x)) = h ((g f) x) = [h (g f)] x (h g) f h g f h (g f) h (g f)

Перевірка кожної рівності полягає в застосуванні визначення композиції (1) до тієї композиції, котра вказана під знаком рівності. Після цього означення рівності функцій, наведене в лекції 1, доводить асоціативний закон (hg) f = h(gf): S→V. Лема доведена.

Тотожні функції 1S і 1T в композиції з будь-якою функціею f : S → T не змінюють її: f ○ 1S = 1T ○ f = f , 1S ◊ f = f ◊ 1T = f

Щоб перекон тись в цьому, слід звернути ув гу н те, що (f 1S) s = f(1s s) = f (s) для всіх s S в

силу соці тивності композиції, і з стосув ти озн чення рівності функцій.

Визначення. Характеристична функція підмножини S даної множини U, eS: U → {0,1}, визначається

записом

1, якщоx S; eS (x) 0, якщоx S.

Нехай, наприклад, U = {1,2,3} – множина, яку ми позначимо також символом 3. Наведемо список значень функції eS, які відповідають всім можливим підмножинам S U:

Ø (0,0,0), {1} (1,0,0), {2} (0,1,0), {3} (0,0,1), {1,2} (1,1,0), {1,3} (1,0,1), {2,3} (0,1,1), 3 = {1,2,3} (1,1,1).

11. Оборотність функції. Введемо важливі відношення на множинах функцій, які використовуються в процесі аналізу функцівональних залежностей, що описують конкретні об’єкти і системи.

Визначення. Якщо ліва композиція g○f функцій f: S → T і g: T → S співпадає з тотожною функцією 1S на множині S, ми будемо говорити, що функція g – ліва обернена до функції f, а функція f –

права обернена до функції g, функція f - оборотна зліва, функція g - оборотна справа. Якщо, крім того, f ○ g

= 1T, ми будемо говорити, що функція g – двобічно оборотна до f і, за симетрією, функція f – двобічно оборотна до g. Функція, яка має двобічно оборотну, називається оборотною.

Теорема 2. Функція оборотна зліва тоді і тільки тоді, коли вона ін’єктивна. Функція оборотна справа тоді і тільки тоді, коли вона сюр‘єктивна.

Доведення. Покажемо спочатку, що будь-яка оборотна зліва функція ін’єктивна. Нехай g: T → S – функція, обернена зліва до f: S → T. Припустимо, що f(s) = f(s'). Тоді за означенням,

s = 1S(s) = g ( f (s)) = g ( f (s')) =1S(s' ) = s '

Таким чином, виходячи з припущення, що f(s) = f(s'), ми встановили, що s = s'. Це доводить ін’єктивність f. Залишається перевірити обернене твердження, щоб закінчити доведення першої частини теореми: нам потрібно показати, що якщо f ін’єктивна, то для неї існує ліва обернена g1 функція, тобто g1 f = 1S. З цією метою виберемо елемент s1 S і визначимо g1: T → S таким чином:

g1 (t) s1 , всупротивн омувипадку, тобтоякщоt Im f .

Тоді (g1f)(s) = g1( f (s)) = s для всіх s S, так що, за означенням, g1f = 1S і g1 є лівою оберненою до f. Аналогічно перевіряється друга частина теореми. Якщо t T і fh = 1T, то t = 1T(t) = f(h(t)), тому що

будь-який елемент t T є образом f(s) певного елемента s = h(t) S , і f сюр’єктивна. В інший бік, якщо f: S → T сюр’єктивна, то кожен елемент t T є образом t = f(s) хоча б одного елемента s S. Для кожного елемента t T виберемо з множини всіх s, що переходять в t, одного представника і позначимо його,

9

скажімо, через h(t). Тоді ми отримаємо функцію h: T → S, таку, що f(h(t)) = t для всіх t T, тобто fh = 1T, як стверджувалось. Теорема доведена.

Наслідок. Функція f: S → T є бієкцією тоді і тільки тоді, коли вона є оборотною зліва і справа. Теорема 3. Наведені нижче властивості функції f: S → T еквівалентні:

(i) функція f – бієкція;

(ii)функція f має ліву обернену функцію g і праву обернену функцію h. Якщо ці властивості виконуються, то

(iii)всі обернені до f функції (ліві, праві і двобічні) співпадають. Ця єдина обернена до функції f функція f –1, бієктивна, і

Доведення. Еквівалентність властивостей (i) і (ii) є просто переформулюванням попереднього наслідку. Наслідком умови (ii) є

g = g1T = g(fh) = (gf)h =1s h = h.

Це показує, що всі ліві і праві обернені до функції f функції співпадають, і доводить властивість (iii). Нарешті, бієктивна функція f обернена до своєї оберненої функції g = h, оскільки gf =1s і fh = 1T. Отже, обернена функція бієктивна і має функцію f своєю єдиною оберненою функцією, тобто (f –1)–1 = f.

Визначення. Квадрат будь-якої функції f: S → S визначається як функція f 2 = f f = f ◊ f, тобто як результат дворазового застосування функції f. Коли f2 = f, функція f називається ідемпотентом чи

проектором.

Наприклад, ортогональний проектор (x,y)-площини на x-вісь або y-вісь є ідемпотентом. Відзначимо також, що ці два проектори мають властивість f ○g = g ○f (чи, що те ж саме, g ◊ f = f ◊ g), оскільки f ○g і g ○f відібражують будь-яку точку площини у початок координат (0,0).

теореми 2, функція f має ліву обернену функцію відносно лівої композиції, і тільки тоді, коли f є ін‘єкцією. Значить, те ж відноситься до існування правої оберненої функції до f відносно правої композиції. Аналогічно, функція f має обернену справа функцію відносно лівої композиції тоді і тільки тоді, коли f - сюр‘єкція.

Двобічна обернена існує в точності для бієктивних функцій незалежно від того, яку з композицій (ліву чи праву) ми розглядаємо. Функція, обернена до f, позначається через f –1 . Вона існує у тому і тільки у тому випадку, коли функція f бієктивна, і задовільняє відношенням

f –1 f = f f –1 = 1s (і для лівої і для правої композиції).

12. Спеці льні кл си функцій.

Визначення. Підстановкою множини А називається будь-яка бієкція на А.

Підстановки скінченних множин становляють особливий інтерес для розрахунків. Коли А визначене, ми в змозі розрахувати число різних підстановок А.

Нехай |А| = n N. Позначимо через nPn число таких підстановок. Значення nPn легко розрахувати. Можемо розглянути задачу побудови бієкції на А як задачу заповнення ящиків, занумерованих від 1 до n, a1,...,an (рис.8). Порядок, в якому заповнюються ящики, не суттєвий (будь-який інший порядок можна отримати перемішуванням ящиків). Тому будемо заповнювати їх зліва направо. Перший ящик може бути заповнений n способами, тому що ми маємо вільний вибір з усієї множини А. Забираючи обраний елемент з

...

Рис. 8.

елементів. Отже, другий ящик може бути заповнений n – 1 способами, третій ящик – n – 2 способами і т.д. Продовжуючи цей процес, отримаємо, що (n - 1)-й ящик може бути заповнений двома способами, а ящик з номером n – єдиним элементом з А, що залишився. Отже, число різних підстановок з А рівне

n (n –1) (n - 2) ... 3 2 1.

Цей добуток називається факторіалом n (позначається n!). Отже, nPn = n!.

Нехай Nn підмножина перших n натуральних чисел множини N. Тому що А і Nn мають однакову кількість елементів, можна звести множину А до множини Nn. Будь-яка підстановка на Nn повинна визначати образ кожного элемента в Nn (який, звичайно, повинен бути єдиним і відрізнятися від інших).

10