Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Відповідність, відображення і функції

Відповідність. Відповідністю між множинами А і В називається підмножина G Í А ´ В. Відповідність G називається функціональною або однозначною, якщо образом будь-якого елемента множини G1 є єдиний елемент множини G2, причому G1, G2 Í G.

Приклад. Англійсько-російський словник встановлює відповідність між множиною англійських і російських слів. Ця відповідність не є функціональною.

Функцією називається функціональна відповідність. Якщо функція f встановлює відповідність між множинами А і В, то кажуть, що функція f має тип А®В (позначення f: А®В). Цілком визначена функція f: А®В називається відображенням А в В. Образ А при відображенні f позначається f(A).

Якщо f(A) складається з єдиного елемента, то f називається функцією- константой.

Відображення типу А®А називається перетворенням множини А.

Важливим поняттям при побудові математичних моделей дискретної математики є поняття відношення між елементами двох множин. Якщо для кожного елемента x Î X можна сказати, що елемент x знаходиться або не знаходиться в даному відношенні a з елементом y Î Y, то кажуть, що між елементами множини X і Y задане відношення a і пишуть x a y у тому випадку, коли x знаходиться у відношенні a з елементом y. Наприклад, між множиною Х студентів даного курсу і множиною Y усіх навчальних предметів за даною спеціальністю існує відношення a таке, що х a y означає "студент х склав екзамен з предмету y". Між елементами множин Х і Y може існувати багато різноманітних змістовних відношень, якщо Х та Y - змістовні множини. Наприклад, такими відношеннями є всілякі функціональні відношення або відображення.

Відношення a між елементами множин X і Y називають відображенням множини Х в множину Y, якщо кожний елемент х Î Х обов'язково знаходиться у відношенні з деяким елементом y Î Y, причому цей елемент y Î Y - єдиний для даного елемента х Î Х. Відображення множини Х в множину Y позначають через j (або іншою підхожою буквою) і пишуть j: Х ® Y, при цьому замість х j y для х Î Х і y Î Y часто пишуть y = j(х) і кажуть, що y є зображення елемента х при відображенні. На рисунку відображення j: Х ® Y зручно наводити у вигляді двочасткового графа. Розглянемо приклад (рис.1.9).

х₁ х₂ х₃ х₄

X

Y

у₁ у₂ у₃ у₄

Рис.1.9. Двочастковий граф

Тут точки верхнього ряду зображують елементи множини Х, нижнього ряду - множини Y, і якщо має місце y = j(x), то з точки х виходить стрілка, що заходить або входить у точку y. Таку форму представлення називають двочастковим графом відображення j: X ® Y, причому точки цього рисунка іменують вершинами графа, а стрілки - дугами графа і кажуть, що відображення j є:

а) ін'єктивним, якщо в кожну вершину y Î Y заходить або входить не більш однієї дуги;

б) сюрєктивним, якщо в кожну вершину y Î Y входить не менше однієї дуги;

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

Для будь-якого відображення j: X ® Y і будь-якої не порожньої підмножини А Í Х множина образів усіх елементів х Î А при відображенні j називають образом множини А і позначають j(А), так що j(А) = íy ÎY: y = j(x) для деякого х Î Аý.

Для спільності і стрункості суджень приймається j(Æ) = Æ. Якщо j(Х) = Y, то, очевидно, j є сюрєктивним відображенням.

У додатках часто використовується відображення j: Х ® R⁺, при цьому j(х) виступає в ролі ціни або ваги, або довжини, або пропускної спроможності елемента х Î Х.

Очевидно, завдання бієкції j: X ® Y рівнозначно встановленню взаємно однозначної відповідності між елементами множин Х і Y.

Відображення j: Х®Y і Y1: Х®Y називаються рівними, якщо з х j y випливає x j₁ y і навпаки, тобто якщо ці відображення можна зобразити двочастковим графом відображення.

Нехай Х і Y - кінцеві непорожні множини, причому |X| = m, |Y| = n. Тоді кількість усіх відображень j: X ® Y дорівнює nm. Дійсно, щоб одержати довільне відображення j: X ® Y, треба побудувати двочастковий граф цього відображення, для чого вибрати для кожної вершини x Î X одну і тільки одну дугу серед n дуг (n = |Y|), що можуть виходити з вершини х і заходити у вершини y Î Y, причому для різних вершин х, х₁Î Х зазначений вибір дуг відбувається незалежно. Тому кількість усіх таких виборів, а виходить і всіх двочасткових графів відображень, буде n*n*... *n, де кількість співмножників дорівнює m = |X|, так що утворюється шукана кількість n*m.

Множину усіх відображень j:X®Y іноді позначають як Y^х, тому що для кінцевих X і Y тоді одержують формулу |Y^х| = |Y^|х||. Але ніщо не заважає розглядати останню формулу для нескінченних X і Y і вважати цю формулу правилом зведення в кардинальний ступінь |X| кардинального числа |Y|.

Наприклад, с = 2^а. Далі, суму |X| + |Y| довільних кардинальних чисел визначають як потужність |X + Y| множини X + Y, створеної з усіх вершин х Î Х та y Î Y двочасткового графа довільного відображення j: X ® Y, а добуток |X| * |Y| визначають як потужність |X * Y| множини X * Y, створеної з всіляких упорядкованих пар (x, y), де x Î X, y Î Y. Такі визначення суми і добутки кардинальних чисел узгоджуються зі звичним змістом m + n і m * n для кінцевих множин X і Y при m = |X|, n = |Y|.

Перетворення. Відображення j:X®X називають перетворенням множини Х, на рисунку зображують у вигляді орграфа (орієнтованого графа) перетворення, вершинами якого є елементи x Î X, а дугами - пари (х₁, х₂) такі, що х₁ j х₂, тобто х₂ = j(х₁). Перетворення j: X ® X можна зображати дворядковим записом, вміщуючи в першому рядку цього запису елементи x Î X, а в другому - під ними їх представлення j(х). Наприклад, для Х = í1,2,…,7ý одне з перетворень зобразимо дворядковим записом і орграфом (рис. 1.10):

1 2 3 4 5 6 7 1 3

j = 2 4 5 6

3 7 2 5 4 6 1 7

Рис.1.10. Приклад перетворення

Очевидно, що це перетворення бієктивне, причому j(А) = А для множин А=Æ, А = í1,2,3,7ý, А = í4,5ý, А = í6ý і тільки для них.

Бієктивні перетворення називають підстановками. Як видно, орграф підстановки j кінцевої множини розпадається на частини, однозначно обумовлені підмножинами А, такими що А = j(А). Такі частини (вершини разом із дугами) прийнято називати циклами підстановки j. Максимальна кількість циклів має тотожні підстановки j, тобто такі, що х = j(х) виконується для довільного х Î Х. Підстановки, що мають один цикл, називаються одноцикловими. Одноциклові підстановки служать, наприклад, моделями для опису обходу одною людиною n різноманітних пунктів (почавши рух у вихідному пункті, людина обходить всі інші по одному разу і повертається у вихідний пункт). Зауважимо, що кількість усіх підстановок n-елементної множини Х дорівнює n! = n * (n-1)*... *2*1, тому що елементу x₁ Î X можна поставити у відповідність довільний із n елементів множини Х, але елементу х₂ при х₂ ¹ х₁ можна поставити у відповідність по підстановці j будь-який елемент із тих n-1 елементів, що залишилися і що не є образом елемента х₁ тощо.

У зв'язку зі сказаним вище зручно позначити через Х! множину всіх бієктивних перетворень множини Х, тому що тоді | X! | = | X |! для кінцевих множин Х.

Рекомендується пам'ятати, що 10! = 3628800, а 0! = 1 (за угодою).

Зрозуміло, що кількість всіх одноциклових підстановок n-елементної множини дорівнює (n-1)!.

Приклад 1. Кожне натуральне число можна розкласти на добуток простих чисел. Якщо розташувати прості дільники у певному порядку, наприклад не зменьшення, то одержимо функцію

G(42)=(2, 3, 7); G(23)=23;

G(100)=(2, 2, 5, 5) і т.д.

Приклад 2. Кожній людині відповідає множина її знайомих.

G(Іванов)=(Сидоров, Миколаїв,...,Семенов)