Лекція 6

6 Функціональні відношення.

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

Відношення R між множинами X і Y (R X Y) є функціональним, якщо всі його елементи (упорядковані пари) різні за першим елементом: кожному xX відповідає тільки один елемент yY, такий, що xRy, або такого елементу у взагалі не існує.

П

a₁

b₁

b₂

a₁

b₁

a₂

b₂

a₁

b₁

a₂

b₂

a) функціональне відношення

b) функціональне відношення

риклади функціонального і не функціонального відношення зображено в вигляді графів:

a₂

c) нефункціональне відношення

Нехай R – деяке відношення між множинами X і Y (R X Y). Областю визначення відношення R називається множина D_R, що складається з усіх елементів множини Х, які зв’язані відношенням R з елементами множини Y: D_R X, D_R = {x: yY, (x, y)R}

Областю значень відношення R називається множина Е_R, що складається з усіх елементів множини Y, які зв’язані відношенням R з множиною Х: Е_R Y, E_R = {y: xX, (x, y)R}.

Нехай F – функціональне відношення між множинами X і Y (F X Y). Відповідність xy від першого до другого елементу кожної пари (x, y)F відношення F називається функцією f або відображенням f множини D_R в Y і позначається як f: D_R  Y, або як .

Якщо множина А Х, то через f(A)={yY: y=f(x), xX} позначається образ множини А. Множина f(Х)  Y називається образом або областю значень відображення f.

Якщо множина B Y, то множина f ^-1(B)={xX: f(x)Y} називається прообразом множини В відносно відображення f.

Запис функціональної залежності y=f(x), що використовується в алгебрі, менш інформативний, ніж запис у вигляді відображення f: D_f Y, оскільки повинен доповнюватися інформацією про область визначення.

Графіком функції називається сукупність двовимірних точок (х, у) у вигляді (x, f(x)) у декартовому добутку XY. Таким чином, якщо FXY – вихідне функціональне відношення, що породжує функцію f, то F в точності є графік функції f.

Не слід змішувати поняття «графік функції f» і «граф відображення F»: граф за допомогою дуг зі стрілками описує відображення на кожному значенні аргументу х.

7 Види відображенень

1. Відображення f: XY називається сур’єктивним відображенням, якщо Е_R= Y.

На графі, що зображує сур’єктивне відображення XY, з будь-якої вершини х виходить точно одна дуга, а до будь-якої вершини у заходить не менше однієї дуги.

2. Ф ункція f: XY називається ін’єктивним відображенням, якщо з х₁≠х₂ виходить у₁≠у₂.

На графі, що зображує ін’єктивне відображення XY, з будь-якої вершини х виходить точно одна дуга, а до будь-якої вершини у заходить не більше однієї дуги.

3. Ф ункція f: XY називається бієктивним відображенням, якщо вона сур’єктивна та ін’єктивна.

На графі, що зображує ін’єктивне відображення XY, з будь-якої вершини х виходить точно одна дуга, а до будь-якої вершини у заходить одна і тільки одна дуга. Тобто бієктивне відображення – є взаємно однозначним відображенням і тому XY, а |X|=|Y|.

Властивість бієктивного відображення забезпечує існування оберненого відображення. Це означає, що якщо f: XY – бієктивне, то існує обернене відображення f ^-1: Y X, причому .

Запитання.

1. Яке відношення називається функціональним?

2. Що таке область визначення і область значень відношення?

3. Яке відношення R X Y задає відображення XY ?

4. Дайте визначення сур’єктивного, ін’єктивного і бієктивного відображення. Чим характеризується граф кожного з цих відображень?

 Завдання

1. Які з наведених відношень R A², що задані на множині A={-20, -19,…0, 1, …19, 20}, є функціональним? Для функціональних відношень вказати відповідні функції:

1. (a, b)R, якщо a = b²;

2. (a, b)R, якщо a² = b;

3. (a, b)R, якщо a  b;

4. (a, b)R, якщо a b= 6;

5. (a, b)R, якщо a = b³;

6. (a, b)R, якщо b = a³;

7. (a, b)R, якщо a = b⁴;

8. (a, b)R, якщо a = 1/b;

2. Які з функцій f, знайдених в попередній задачі, є відображенням виду f: АА?

3. Нехай задані множини А, В, С і відношення R AB і S BC. Покажіть на прикладах, що наведені висновки не правильні:

   1. Якщо R – функціональне відношення, то S∘ R – функціональне відношення;

   2. Якщо R – задає відображення А в В, то S∘ R – відображення А в С;

   3. Якщо S – визначає сур’єкцію ВС, то S∘ R – сур’єкцію А С;

   4. Якщо S – визначає ін’єкцію ВС, то S∘ R – ін’єкцію А С

4. Нехай А і В – скінченні множини, |A| = n, |B| = m. Визначте співвідношення між n і m, якщо:

   1. Існує ін’єктивне відображення з А в В;

   2. Існує сур’єктивне відображення з А в В;

   3. Існує бієктивне відображення з А в В;

Самостійна робота №6

Тема: Реляшійна модель відношень

Мета: Засвоїти нові знання, закріпити їх при виконанні практичних завдань.

Завдання

1. Засвоїти теоретичний матеріал згідно теми;

2. Дати відповіді на поставлені питання;

3. Виконати письмово приведені завдання;

4. Випишіть питання, що виникли в ході засвоєння матеріалу;

5. Зробіть висновки.

Рекомендована література:

1. Бондаренко М.Ф. Комп’ютерна дискретна математика – Х: Компанія СМІТ, 2004р.

2. Новіков Ф.А. Дискретна математика для програмістів – К: Питер, 2006р