Студопедия  
Главная страница | Контакты | Случайная страница

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

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

Читайте также:
  1. Банк Англії, його утворення, організація і управління, роль і функції
  2. Бенчмаркінг як альтернатива маркетингового дослідження: сутність, функції, види.
  3. В.Г. Афанасьєв називає наступні основні управлінські функції: вироблення і ухвалення управлінського рішення; організація; регулювання і корегування; облік і контроль.
  4. Взаємозв’язок операційної функції з іншими функціями організації
  5. Визначення, функції та типи електронного архіву.
  6. Відображення в обліку окремих господарських операцій
  7. Відображення даних обліку надходження основних засобів в статтях фінансової звітності
  8. ВІДОБРАЖЕННЯ ІНФОРМАЦІЇ В МКП
  9. Відображення обліку готівки в касі встаттях фінансової звітності
  10. Відображення обліку готівки в регістрах обліку та статтях фінансової звітності

Відповідність. Відповідністю між множинами А і В називається підмножина 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).

х1 х2 х3 х4

X

 

Y

у1 у2 у3 у4

 

Рис.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 j1 y і навпаки, тобто якщо ці відображення можна зобразити двочастковим графом відображення.

Нехай Х і Y - кінцеві непорожні множини, причому |X| = m, |Y| = n. Тоді кількість усіх відображень j: X ® Y дорівнює nm. Дійсно, щоб одержати довільне відображення j: X ® Y, треба побудувати двочастковий граф цього відображення, для чого вибрати для кожної вершини x Î X одну і тільки одну дугу серед n дуг (n = |Y|), що можуть виходити з вершини х і заходити у вершини y Î Y, причому для різних вершин х, х1Î Х зазначений вибір дуг відбувається незалежно. Тому кількість усіх таких виборів, а виходить і всіх двочасткових графів відображень, буде 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, а дугами - пари (х1, х2) такі, що х1 j х2, тобто х2 = j(х1). Перетворення 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, тому що елементу x1 Î X можна поставити у відповідність довільний із n елементів множини Х, але елементу х2 при х2 ¹ х1 можна поставити у відповідність по підстановці j будь-який елемент із тих n-1 елементів, що залишилися і що не є образом елемента х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(Іванов)=(Сидоров, Миколаїв,...,Семенов)

 




Дата добавления: 2014-12-15; просмотров: 76 | Поможем написать вашу работу | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2024 год. (0.01 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав