Лекція 2 Відношення
Дослідника завжди цікавлять різні властивості об'єктів: властивості, що належать до окремих об'єктів (наприклад, "бути жінкою", "бути білим", "мати низьку теплопровідність") та властивості, що характеризують зв'язки між кількома об'єктами (наприклад, властивості "бути родичами" та " бути більше" відносяться до пар об'єктів, властивість "перебувати між" - до трійок об'єктів, властивість "розташовуватися у вершинах квадрата" - до четвірок об'єктів).
Такі властивості прийнято називати стосунками. При цьому властивості окремих об'єктів називаютьсяунарними (одномісними) відносинами, властивості, що відносяться до пар об'єктів, -бінарними відносинами, властивості, що відносяться до наборів зnоб'єктів, -n-арними відносинами
Поняття відносини є дуже важливим не лише з математичної точки зору. Поняття відносини фактично є основою всієї теорії баз даних. Відносини є математичним аналогомтаблиць.
ВизначенняВідносини– один із способів завдання взаємозв'язків між елементами множини.
Прикладвідносин зі шкільного курсу математики є:
на безлічі цілих чисел Z відношення "ділиться", "ділить", "рівно", "більше", "менше", "взаємно прості";
на безлічі прямих просторів відносини "паралельні", "взаємно перпендикулярні", "схрещуються", "перетинаються", "збігаються";
на безлічі кіл "перетинаються", "стосуються".
Факт приналежності кортежу (x,y) відношеннюR, часто позначають за допомогоюінфіксноїформи запису:xRy.
Прикладами таких записів з курсу математики є:x>y,a=b,ml.
Способи завдання відносин
Відносини можуть задаватися:
формулиy = x2+5x - 6- бінарні відносини на безлічі дійсних чисел;
формулаx+y= любов-бінарне відношення на множині людей.
ВизначенняМатрицею бінарного відношення–називається матриця
або1 –якщо має місце співвідношення
поставити ставлення»бути суворо менше»
графічне уявленняПри такому поданні елементи множиниXзображуються вершинами графа (точками площини), а елементи (x,y) відношеннядугами (стрілками), що з'єднують першу компонентуxвідносини з другою компонентоюy.
Декартове твір множин
У математиці досить часто доводиться мати справу не лише з окремими елементами будь-якої множини, але і з упорядкованими парами його елементів. Використовуючи дві цифри 3 і 5, можна записати 4 числа, важливий порядок слідування цифр або впорядкований набір.
ВизначенняНехай-множини. Вираз виду, деі, називаєтьсяупорядкованою парою.У загальному випадку, можна розглядатиупорядковану n-куз елементів абонабірабокортеж.
Визначення.Два кортежі рівні між собою, тобто. (a1. an) = (b1. bn) тоді і лише тоді, коли для будь-якого i виконано рівність ai = bi.
ВизначенняДекартовим (прямим) твором множинназивається безліч кортежів виду
декартовим творомціх множин є сукупність всіх можливихn‑місцевих елементарних кортежів, у яких на першому місці стоїть елемент множини
Тут безліч міститьпариелементів, у яких на відміну від множин порядок суворо визначено (тобто їх не можна міняти місцями). Щоб відрізнити (упорядковані) пари від множин, їх укладають над фігурні, а прості круглі дужки.
ЗауваженняXY
ВизначенняСтепенею декартового творуназивається числоnмножин, що входять до цього декартового твору.
Зауваження.Якщо всі множини однакові, то використовують позначення
Зауваженнятермін «декартове твір»Причому тут великий французький математик і філософ Рене Декарт? Він винайшов координати, що так і називаються декартовими. Безліч точок площини можна як пряме твір координатних осей.
ВизначенняБезліч елементарних кортежів однієї і тієї ж розмірностіnназиваютьбагатоміснимабоn-місцевимвідношенням.
Прикладвідношення "менше" для безлічі цілих чисел можна представити як безліч пар чисел
Теорема Ккількість всіх елементів (тобто. елементарних кортежів) декартового твору дорівнюватиме твору потужностей всіх використовуваних у цьому творі множин, тобто.
ЗавданняЗ міста А до міста В веде три дороги, а з міста В до міста С – 4 дороги. Скількими способами можна дістатися з А до С через В?
Завдання спочатку формулюється не як математичне, бо як завдання реального життя, і тому потрібно її переробка в математичне завдання. При цьому потрібно відокремити суттєві фактори від несуттєвих.
Справді, якщо за підрахунком способів ми будемовраховувати час доби, швидкість і спосіб переміщення (пішки, на автомобілі, велосипеді тощо), то завдання стає надзвичайно простою, при врахуванні зазначених факторів відповідь задачі: "Є безліч способів".
Якщо ж відволіктися від усіх зазначених факторів і під способом потрапити з А в С через В розуміти впорядковану пару (дорога, якою переміщуємося з А в В; дорога, якою переміщуємося з В в С), то рішення задачі можна отримати, використовуючи поняття декартові твори. Позначимо:
АВ - безліч доріг, що ведуть з А в В;
НД - безліч доріг, що ведуть з У в С.
Тоді математичне завдання, до якої звелося вихідне завдання, має такий вигляд: "Знайти число елементів у декартовому творі АВ×ВС".
AB×BC = AB·BC = 3·4 = 12.
Відповідь: 12 способів.
ЗауваженняБудь-яка множина можна розглядати як декартове твір ступеня 1, то будь-яке підмножина, як і будь-яка множина, можна вважати ставленням ступеня 1.
ЗауваженняНетривіальність поняття відносини проявляється, коли ступінь відношення більше 1.
Ключовими тут є два моменти:
Всі елементи відношення є однотипні кортежі.
ставлення, що складається з трьох кортежів
Безліч, що складається зрізнотипнихчислових кортежів. Це безліч не є ставленням ні в 20, ні в 21, ні в 22.
2. Відношення включає в себе не всі можливі кортежі з декартового твору. Це означає, що з кожного відносини єкритерий, що дозволяє визначити, які кортежі входять у відношення, а які - ні.
ВизначенняКортеж
