Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Декартів (прямий) добуток множин
Поряд з операціями (1.2) – (1.8) впроваджується операція декартова (прямого) добутку множин. Визначення 2.3. Прямий (декартів) добуток двох множин A і B є множина всіх пар таких, що , : . (2.1) Приклад 2.3. Дано множини , . Складемо їх декартів добуток за правилом (2.1): . Приклад 2.4. Декартів добуток множин , є множина, що містить позначення всіх 64 клітинок шахівниці. Приклад 2.5. Координатне подання точок площини, що ввів Рене Декарт – французький математик і філософ, – є історично першим прикладом прямого добутку. Множина точок площини , тобто множина пар виду , : . Декартів добуток множин не є комутативним: . Визначення 2.4. Якщо , тобто – декартів квадрат. Визначення 2.5. Прямий добуток n множин є сукупність всіх векторів довжини таких, що , ,..., , тобто , (2.2) Ототожнивши множини в декартовому добутку (2.3), одержимо декартову ступінь множини. Визначення 2.6. Декартів добуток n однакових множин є декартова ступінь: . (2.3) Декартова ступінь множини поряд з іншими n-мірними векторами містить вектори, що складаються з однакових координат, тобто -мірні вектори виду . Кількість таких векторів визначається потужністю множини й дорівнює n. Потужність декартова добутку визначається як добуток потужностей множин, що входять у нього. Нехай – кінцеві множини, потужності яких відповідно дорівнюють . Тоді потужність декартова добутку множин дорівнює добутку потужностей цих множин: . (2.4) З формули (2.4) випливає, що потужність декартова ступеня визначається як ступінь потужності множини : . (2.5) 2.3 Відповідності Визначення 2.7. Відповідністю між множинами і називається підмножина декартового добутку двох множин : . Запис означає, що елемент відповідає елементу в значенні , і впорядкована пара належить множині : . При цьому називають областю визначення (множиною відправлення) відповідності : ; – областю значень (множиною прибуття) відповідності : . Визначення 2.8. Множина всіх елементів , що відповідають елементу , називається образом елемента у множині при відповідності . Визначення 2.9. Множина всіх елементів , яким відповідає елемент , називається прообразом елемента в множині при відповідності . Приклад 2.6. Дано множини і . Для відповідності область визначення є проекція на першу вісь: ; область значень – проекція на другу вісь: ; Відповідності прийнято ілюструвати за допомогою діаграм. Для прикладу 2.6 діаграма наведена на рис. 2.1.
Рисунок 2.1 – Діаграма відповідності із прикладу 2.6 Визначення 2.10. Відповідність називається всюди визначеною, якщо її проекція на першу вісь співпадає з множиною відправлення: , тобто у відповідності задіяні всі елементи з області визначення . У протилежному випадку відповідність є частковою. Приклад 2.6 ілюструє часткову відповідність, тому що . Приклад 2.7. Для відповідності
S Рисунок 2.2 – Діаграма відповідності S із прикладу 2.7 Визначення 2.11. Відповідність називається сур’єктивною, якщо її проекція на другу вісь співпадає з множиною прибуття: , тобто у відповідності задіяні всі елементи з області значень . Приклад 2.8. Для відповідності
Т Рисунок 2.3 – Діаграма відповідності Т із прикладу 2.8 Визначення 2.12. Відповідність називається ін’єктивною (in), якщо різні елементи з його області визначення мають різні образи в його області значень , тобто прообразом будь-якого елемента з області значень є єдиний елемент із області визначення (інакше – різні елементи з області визначення мають різні образи): . (2.6) Отже, при ін’єктивній відповідності кожний образ має єдиний прообраз. Це означає, що в діаграмі ін’єктивної відповідності нема збіжних стрілок. Приклад 2.9. Відповідності , і із прикладів 2.6 – 2.8 не є ін’єктивними, оскільки образ має два прообрази – елементи 1, 2 у множині . До того ж у відповідності образ також має два прообрази – елементи 2 і 3. Приклад 2.10. Відповідність де , , є ін’єктивною, оскільки образи з множини мають єдині прообрази в множині (рис. 2.4).
Р Рисунок 2.4 – Діаграма відповідності Р із прикладу 2.10 Визначення 2.13. Відповідність називається функціональною (однозначною), якщо образом будь-якого елемента з області визначення є єдиний елемент із області значень, тобто – функціонально, якщо . (2.7) Діаграма функціональної відповідності не має розбіжних стрілок. Приклад 2.11. Відповідність із прикладу 2.6 є функціональною, тому що кожному прообразу відповідає єдиний образ: прообразу 1 відповідає образ , прообразу 2 відповідає також один образ – . Відповідність із прикладу 2.7. не є функціональною, оскільки існує прообраз – елемент 2, у якого одночасно два образи – елементи й . Визначення 2.14. Бієктивна (взаємо-однозначна) відповідність – це відповідність, що є всюди визначеною, сур’єктивною, ін’єктивною, функціональною, тобто має всі властивості одночасно. Біекцію (бієктивну або взаємо-однозначну відповідність) можна встановити тільки між множинами однакових потужностей. Приклад 2.12. Для відповідності (рис. 2.5), де , , характерні всі властивості, отже, вона є бієктивною.
Рисунок 2.5 – Діаграма відповідності із прикладу 2.12 Приклад 2.13. Розглядається відповідність , що геометрично зображена на рис. 2.6. Вона переводить відрізок дійсної осі у відрізок дійсної
Рисунок 2.6 – Ілюстрація відповідності до прикладу 2.13
2.4 Функції. Відображення Визначення 2.15. Функцією називається функціональна відповідність , (2.8) де х – аргумент; у – значення функції на елементі х. Визначення 2.16. Відображенням множини в множину називається всюди визначена функція; – образ множини при відображенні . Приклад 2.14. Відповідність (рис. 2.7) є функціональною (функцією), оскільки кожному прообразу відповідає єдиний образ; всюди визначеною, тому що ; отже, f – відображення; не є сур’єктивною: (елемент d не має прообразу в множині ).
Рисунок 2.7 – Приклад функції і відображення Визначення 2.17. Якщо для відповідності існує відповідність така, що тоді й тільки тоді, коли , тоді відповідність називається зворотною до і позначається , тобто . Визначення 2.18. Зворотною функцією називається відповідність, зворотна до функції , тобто якщо зворотна до відповідність є функціональною, то вона називається зворотною функцією й позначається . Приклад 2.15. Різні види кодування (кодування букв абеткою Морзе, подання чисел у різних системах числення, секретні шифри, вхідні та вихідні номери в діловій переписці) є відповідностями між кодованими об’єктами й кодами, що привласнюються їм. Ці відповідності, як правило, мають всі властивості взаємо-однозначної відповідності, крім сур’єктивності. Єдиність образу й прообразу в кодуванні гарантує однозначність шифрування й дешифрування. Відсутність сур’єктивності означає, що не кожний код має сенс. Наприклад, кодування телефонів сьомизначними номерами не є сур’єктивним, оскільки деякі номери не відповідають ніяким телефонам. Для кодувальної функції, що кожному об'єкту зі своєї області значень ставить у відповідність деякий код, зворотною буде декодувальна функція, що кожному коду ставить у відповідність закодований цим кодом об’єкт. Якщо кодувальна функція, не є сур’єктивною, то декодувальна функція не всюди визначена. Визначення 2.19. Нехай дані функції й . Функція називається композицією функцій і (позначення ), якщо має місце рівність , де . Композиція є послідовне застосування функцій і , при цьому застосовується до результату функції . Приклад 2.16. Розглядається триелементна множина і два перетворення й цієї множини: і , де запис означає, що елементу ставиться у відповідність елемент , тобто переходить у . Для задання перетворення кінцевих множин використовується запис: , . Композиція перетворень – є нове перетворення: , . Приклад 2.17. При діагностуванні мікросхем напівпровідникової пам’яті роботу дешифратора адреса можна подати у вигляді графа адресної дешифрації, що показує відповідність між адресами й елементами пам’яті. При правильній роботі спостерігається взаємо-однозначна відповідність між призначеною адресою ліворуч і місцем елемента праворуч (рис. 2.8, а). При несправності дешифратора спостерігається порушення взаємо-однозначної відповідності в графі адресної дешифрації (рис. 2.8, б).
а б Рисунок 2.8 – Граф адресної дешифрації: а – випадок справної схеми; б – випадок з несправністю
2.5 Контрольні запитання
1. Чи можуть повторюватися елементи вектора? 2. Як визначається довжина вектора? 3. Як визначається декартів добуток двох множин? 4. Як визначається декартів добуток множин? 5. Що є елементами декартова добутку двох множин? 6. Що є об'єктами декартова добутку множин? 7. Як визначається вектор? 8. Як визначається довжина (розмірність) вектора? 9. Чому дорівнює потужність декартова добутку множин? 10. Чи є декартів добуток множин комутативним? 11. Що являє собою декартовий ступінь? 12. Чи правильно: ? 13. Що таке відповідність? 14. Що називається проекцією вектора на -у вісь?
3 ВІДНОШЕННЯ. АЛГЕБРА ВІДНОШЕНЬ
|