Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



Лекція поняття відношень

Скачати 147.93 Kb.

Лекція поняття відношень




Скачати 147.93 Kb.
Дата конвертації02.05.2017
Розмір147.93 Kb.
ТипЛекція

Лекція 4

1 Поняття відношень

Відношення реалізують на множинах реальні зв’язки між реальними об’єктами. Відношення застосовують при побудові комп’ютерних баз даних, організованих в вигляді таблиць. Зв’язки між групами даних в таблицях описуються мовою відношень. Такі бази даних називаються реляційними. Відношення також часто використовується в програмуванні. Такі складові структури даних як списки, дерева тощо звичайно використовуються для опису деякої множини даних разом з відношеннями між елементами цієї множини.

Елеме́нт (лат. elementum - стихія, первинна речовина) - нерозкладний (у даній системі) компонент складних тіл, матеріальних систем, теоретичних побудов; будь-який об'єкт, пов'язаний певними відношеннями з іншими об'єктами в єдиний комплекс.
Програмування - процес проектування, написання, тестування, зневадження і підтримки комп'ютерних програм. Програмування поєднує в собі елементи інженерії (існує навіть відповідна спеціальна галузь інженерії - програмна інженерія (англ. software engineering)
В програмуванні та комп'ютерних науках структу́ри да́них - це способи організації даних в комп'ютерах. Часто разом зі структурою даних пов'язується і специфічний перелік операцій, що можуть бути виконаними над даними, організованими в таку структуру.



Приклад. Підприємство займається дизайном інтер’єру приміщень, використовують при цьому продукцію деяких фірм, що розташовані в інших містах.
Примі́щення - частина внутрішнього об'єму будівлі, обмежена будівельними елементами, з можливістю входу і виходу.
Підприє́мство - самостійний суб'єкт господарювання, зареєстрований компетентним органом державної влади або органом місцевого самоврядування, для задоволення суспільних та особистих потреб шляхом систематичного здійснення виробничої, науково-дослідної, торговельної, іншої господарської діяльності в порядку, передбаченому Господарським кодексом України та іншими законами.
Проду́кція (рос. продукция, англ. production, output, produce, нім. Produktion f, Erzeugnisse n pl, Produkte n pl, Güter n pl) - матеріальний результат трудової діяльності або виробничих процесів, що має корисні властивості і призначений для використання споживачем.
Складемо «відношення» комбінації трьох параметрів:

  • Назви фірм;

  • Місця їх знаходження (місто);

  • Вид продукції, що пропонується.

Відомо, що ЧПП «Оріон» (Одеса) продає меблі, ТОВ «День» (Харків) продає світильники, ЧКП «Sit» (Одеса) торгує меблями та світильниками, ТОВ “House” (Харків) продає світильники та матеріали для ремонту.
Матеріа́л - речовина, або суміш речовин, первинний предмет праці, який використовують для виготовлення виробу (основний матеріал), або які сприяють якимось діям. У останньому випадку уточнюють, що це допоміжний, чи витратний матеріал.
Світильник, згідно з міжнародним «Керівництвом зі світлотехніки» - це прилад для розподілу, фільтрації і перетворення світла від лампи або ламп, що включають необхідні компоненти для їхнього захисту, кріплення і постачання електроенергією.
В цьому відношенні беруть участь 3 множини:

  • Фірми = {ЧПП «Оріон», ТОВ «День», ЧКП «Sit», ТОВ “House” };

  • Місто = {Харків, Одеса};

  • Продукція = {Меблі, світильники, матеріали для ремонту}.

Складемо множину, що утворюється з упорядкованих груп:

  • ЧПП «Оріон» (Одеса) – меблі;

  • ТОВ «День» (Харків) – світильники;

  • ЧКП «Sit» (Одеса) - меблі;

  • ЧКП «Sit» (Одеса) - світильники;

  • ТОВ “House” (Харків) - світильники;

  • ТОВ “House” (Харків) - матеріали для ремонту;

До нашого відношення входять не всі можливі комбінації елементів множин Фірма, Місто, Продукція. Наприклад, група ЧКП «Sit» (Одеса) - матеріали для ремонту або ТОВ “House” (Харків) – меблі – не належать нашому відношенню.

Тобто, наше відношення – це певна підмножина множини всіляких комбінацій елементів множин Фірма, Місто, Продукція.

Для формального опису всіляких комбінацій з елементів множин, що входять до відношення використовується поняття декартового добутку множин. Розглянемо це поняття, а потім, використовуючи його визначимо формальне поняття відношення.

Декартовим добутком множин Х1 Х2 Х3…. Хn називається множина всіх можливих упорядкованих наборів (х1, х2, х3, …, хn) з n елементів (які називають кортежами з n елементів), в якій перший елемент належить множині Х1, другий - Х2,…, n –й належить Хn.


Декртовий добуток Х Х Х…. Х, в якому одна множина Х помножується сама на себе n разів називається декатовим степенем множини і позначається Хn. Множину Х2 називають декартовим квадратом множини Х, Х3 – декартовим кубом.
Приклад. A = (a1, a2, a3); B = (b1, b2); C = (c1, c2). Тоді

А В = {( a1, b1), ( a1, b2), ( a2, b1), ( a2, b2), ( a3, b1), ( a3, b2)}.

B A = {( b1, a1), ( b1, a2), ( b1, a3), ( b2, a1), ( b2, a2), ( b2, a3)}.

А В  C = {( a1, b1, c1), ( a1, b2, c1), ( a2, b1, c1), ( a2, b2, c1), ( a3, b1, c1), ( a3, b2, c1),

(a1, b1, c2), ( a1, b2, c2), ( a2, b1, c2), ( a2, b2, c2), ( a3, b1, c2), ( a3, b2, c2)}.

В2 = {( b1, b1), ( b1, b2), ( b2, b1), ( b2, b2)}.

Порядок проходження пар (груп) може бути довільним, але розміщення елементів у кожній парі визначається порядком проходження відповідної множини в добутку.

Проходження (в астрономії) - видиме пересування небесного тіла на тлі видимого диска іншого.

n-арне відношення R на множинах Х1, Х2, Х3,…. ,Хn - це підмножина декартова добутку цих множин : RХ1 Х2 Х3…. Хn.


Під n-арним відношенням R на множині Х розуміється підмножина n-ого степеня цієї множини: RХn.

2 Способи задання бінарних відношень


Якщо R – бінарне відношення на множинах X, Y, то факт (x, y)R часто записується xRy, і говорять, що елемент xX знаходиться у відношенні R з елементом yY.

  1. Будь-яке бінарне відношення може бути задане у вигляді списку, елементами якого є пари, з якого складається відношення.

Приклад. На множинах А={1, 2, 3, 4, 5, 6, 7, 8, 9}; B={24, 25, 26} побудуємо відношення «дільник», яке складається з упорядкованих пар (x, y), де х – дільник у, xА, yВ. Позначимо це відношення через R:

R={(1,24), (1,25), (1, 26), (2, 24), (2, 26), (3, 24), (4, 24), (5, 25), (6, 24), (8, 24)}.




  1. А\В

    24

    25

    26

    1

    1

    1

    1

    2

    1

    0

    1

    3

    1

    0

    0

    4

    1

    0

    0

    5

    0

    1

    0

    6

    1

    0

    0

    7

    0

    0

    0

    8

    1

    0

    0

    9

    0

    0

    0
    Бінарне відношення R на множинах X, Y може бути задане за допомогою матриці W=W(R), рядки якої відповідають елементам множини Х, а стовпці – елементам множини Y. Кожен елемент цієї матриці wij відповідає парі (xi, yj) А В, причому wij=0, якщо (xi, yj) R, і wij=1, якщо (xi, yj) R.

  2. Бінарне відношення R на множинах X, Y може бути задане графічно. Позначимо на площині точками елементи множин X і Y, якщо пара (xi, yj) R, поєднаємо відповідні точки лінією, що спрямована від xi до yj. Лінії називаються дугами, а точки – вершинами графа.

Приклад. Як приклад графічного задання відношення зобразимо генеалогічне дерево деякої родини:


Розглянемо деякі часткові випадки відношень.

Гра́фіка (нім. Graphik, грец. graphikos «написаний») - вид образотворчого мистецтва, для якого характерна перевага ліній і штрихів, використання контрастів білого і чорного та менше, ніж у живописі, використання кольору.
Генеалóгія (дав.-гр. γενεαλογία - «родовід», що дослівно перекладається як: дав.-гр. γενεά - «сім'я», дав.-гр. λόγος - «наука») - родознавство, допоміжна історична дисципліна, що вивчає походження та родинні зв'язки осіб, родовід якоїсь людини, історію родів і сімей.
Генеалогічне дерево, родовідне древо (генеалогічний розпис, генеалогічна таблиця, родовідне древо) - фрагмент (витяг) зі списком нащадків, на якому розмішені носії одного і того ж прізвища та їхнє подружжя, та в якому суворо дотримується таке правило, наприклад: зміна прізвища, усиновлення (або удочеріння), іноземне юридичне ім'я фізичної особи і т. д.
Нехай задане бінарне відношення R
на множині А: R  A2. Можливий випадок, коли R = A2, - таке відношення називається повним.

Відношення називається порожнім при R=. Якщо відношення містить всі можливі пари виду (а, а), і не містить інших пар елементів, то таке відношення називається тотожним.

Якщо повне відношення задане за допомогою матриці, то всі елементи цієї матриці дорівнюють одиниці. Матриця порожнього відношення складається з нульових елементів.



Для розглянутих способів задання відношень треба завважити, що у вигляді матриці і графа зручно зображувати тільки бінарні відношення, а для для n-арних відношень виконується просте їх перелічення.

Запитання.

  1. Як зв’язані теорія відношень та теорія множин?
    Перелічення - стилістичний засіб, який означає однорідні позначення предметів, дій або ознак чогось, які стоять один після одного у реченні.
    Тео́рія множи́н - розділ математики, в якому вивчаються загальні властивості множин (переважно нескінченних). Виділення теорії множин в самостійний розділ математики відбулося на рубежі XIX і XX століть.


  2. Нехай А – деяка множина. Що означає запис А2, А3, An?

  3. Нехай А і В – множини. Поясніть, чому А В ≠ B A?

  4. Які способи задання відношення вам відомі?

  5. Пояснити поняття «граф», «вершина», «дуга».

  6. Що таке тотожне відношення, повне відношення, порожнє відношення?

Завдання.

  1. Побудуйте матрицю і граф для таких відношень, визначених на множині A={1, 2, 3}:

    1. {(1,1), (1,2), (1,3)};

    2. {(1,1), (2,1), (2,2), (2,3)};

    3. {(1,1), (1,2), (1,3), (2,2), (2,3), (3,3)};

    4. {(1,3), (3,1)}.

  2. Побудуйте граф і список елементів для таких відношень, визначених на множині A={a, b, c} матрицями:




a

b

c







a

b

c







a

b

c







a

b

c

a

1

0

1




a

0

1

0




a

1

1

1




a

1

0

0

b

0

1

0




b

0

1

0




b

1

0

1




b

0

1

0

c

1

0

1




c

0

1

0




c

1

1

1




c

0

0

1

a) b) c) d)

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

a) b) c)



  1. Запишіть список елементів для 3-арного відношення R, що задане на множині натуральних чисел (a, b, c)R, якщо 0

  2. Запишіть список елементів для 4-арного відношення R, що задане на множині натуральних чисел (a, b, c, d)R, якщо abcd = 6.

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

Тема: Операції над відношеннями.

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

Завдання

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

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

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

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

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

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

  1. Бондаренко М.Ф. Комп’ютерна дискретна математика – Х: Компанія СМІТ, 2004р.
    Практика (грец. πράξις «діяльність») - доцільна і цілеспрямована діяльність, яку суб'єкт здійснює для досягнення певної мети. Практика має суспільно-історичний характер і залежить від рівня розвитку суспільства, його структури.
    Дискре́тна матема́тика - галузь математики, що вивчає властивості будь-яких дискретних структур. Як синонім іноді вживається термін дискре́тний ана́ліз, що вивчає властивості структур скінченного характеру.


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

3 Операції над відношеннями


Повернимося до наведеного раніше відношення, яке назвемо «Батько».


Якщо упорядкована пара елементів (х, у) визначає факт, що х – є батьком у, то у – є дитиною х. То ж з цього виходить, що крім відношення «Батько» існує ще відношення «Дитина», якому належить пара (у, х). Очевидно, що граф відношення «Дитина» можна отримати, помінявши в графї «Батько» напрямки дуг:

Цей приклад пояснює поняття оберненого відношення.

Нехай R-бінарне відношення. Обернене відношення до R позначається R-1. Упорядкована пара (у, х) R-1 тоді і тільки тоді, коли (х, у) ) R.

Якщо R  X2, то R-1 X2, де Х – деяка множина. Якщо R  X  Y, то R-1 Y  X.

Якщо бінарне відношення задане на 2-х множинах, то граф відношення можна побудувати таким чином. Вершини графа, що відповідають елементам першої множини розташуємо ліворуч, вершини, що відповідають елементам другої множини – праворуч. Нехай задані множини: A = {a, b, c, d, e, f}, B = {1, 2, 3, 4} і відношення R = {(a,1), (a,2), (b,4), (d,1), (f,4)}.


Тепер вивчимо спосіб одержання відношення з двох відношень, використовуючи операцію композиції.

Нехай задані множини: A = {a, b, c, d, e, f}, B = {1, 2, 3, 4} і відношення R = {(a,1), (a,2), (b,4), (d,1), (f,4)}. Ще визначимо множину С = {w, x, y, z} і відношення S = {(1,x), (2,y), (3,x). (3,z)}, S B  C.

Нехай R і S – відношення, такі, що R  X  Y, S Y  Z, де X, Y, Z – деякі множини. Композицією відношень R і S називається відношення, що складається з упорядкованих (x,z), xX, zZ, для яких існує елемент yY, такий, що виконуються умови (x,y)R, (y,z)S. Композиція відношень R і S позначається S∘R.

Зокрема, для відношень R  А  В і S B  C композиція S∘R є відношення зображене на малюнку і є підмножиною декартового добутку А  C.

Операція композиції відношень дозволяє ввести поняття бінарного відношення, що задане на одній множині.

Нехай R – деяке відношення, визначене на множині X: R X  X. Тоді n-ий степінь відношення R позначається R2 і визначається рекурсивно так:

R0 – тотожне відношення на множині Х;

Рекурсія (лат. Recursion) - метод визначення класу чи об'єктів методів попереднім заданням одного чи декількох (звичайно простих) його базових випадків чи методів, а потім заданням на їхній основі правила побудови класу, який визначається.

Rn = Rn-1∘R.

Із визначення маємо, що R2 = R∘R, R3 = R2∘R.

Озна́чення, ви́значення чи дефіні́ція (від лат. definitio) - роз'яснення чи витлумачення значення (сенсу) терміну чи поняття. Слід зауважити, що означення завжди стосується символів, оскільки тільки символи мають сенс що його покликане роз'яснити означення.


Приклад. Нехай відношення R на множині A = {a, b, c, d} задане графом:


Розглянемо ще одну операцію, яка називається перерізом бінарного відношення.

Нехай R  X  Y – відношення на множинах X і Y. Якщо xX, то перерізом відношення R за х (позначається R(x)) є множина R(x)  Y, що складається з елементів yY, таких, що (х, у)  R.

Об’єднання перерізів за елементами деякої множини Z X називається перерізом R(Z) відносно підмножини Z.

Множина, що складається з перерізів відношення R X  Y за кожним елементом з Х, називається фактор-множиною множини Y за відношенням R і позначається Y/R. Формально можна записати, що Y/R = {R(x), хX}.

Приклад. Розглянемо перерізи відношення R на множинах A = {a, b, c, d, e, f}, B = {1, 2, 3, 4}, R = {(a,1), (a,2), (b,4), (d,1), (f,4)}.

Перерізи : R(a)={1,2}, R(b)={4}, R(c)=, R(d)={1}, R(e)= , R(f)={4}.

Фактор-множина B/R={{1,2}, {4}, {1}, }.

Розглянемо множину D = {d, e, f}, D A. Переріз відношення R за множиною D виглядає таким чином: R(D)=R(d)R(e)R(f)={{1}, {4}, }.



Крім наведених операцій до відношень застосовані множинні операції об’єднання, перетин, різниця та доповнення. Розглянемо два відношення R  X  Y і S  X  Y. В результаті операцій RS, RS, R\ S одержимо множини упорядкованих пар, що є відповідно об’єднанням, перетином, різницею множин R і S.
Результат, пі́дсумок, (заст. ску́ток, вислід) - кінцевий наслідок послідовності дій. Можливі результати містять перевагу, незручність, вигоду, збитки, цінність і перемогу. Результат є етапом діяльності, коли визначено наявність переходу якості в кількість і кількості в якість.


Запитання.

  1. Що називається оберненим відношенням і як воно позначається?

  2. Як отримати граф відношення, оберненого до даного?

  3. Що називається композицією відношень?

  4. Нехай R – деяке відношення. Що означає запис R2, R3 ?

  5. Дайте визначення перерізу відношення R і фактор-множини за відношенням R.

  6. Назвіть операції, які застосовуються до відношень.

Завдання.

  1. Нехай R1 і R2– бінарні відношення на множині А ={a, b, c, d}, де R1={(a,a), (a,b), (b,d)}; R2={(a,d),(b,c),(b,d),(c,d)}:

    1. побудуйте відношення, R2∘R1, R12, R23;

    2. побудуйте перерізи відношень R1, R2 за елементами a, d і відносно підмножини {a, b};

    3. побудуйте фактор-множину за відношенням R2.

  2. Знайдіть відношення R-1, якщо відношення R задане таким чином:

    1. (a,b)R a, bN, a>b;

    2. (a,b)R a, bN, a – дільник b;

    3. А – множина країн світу;
      Краї́на - це територія з визначеними кордонами й населенням, що являє собою єдине ціле з погляду історії, культури, нації та в політико-географічному відношенні може бути незалежною або залежною. Країна не завжди є державою, наприклад Україна в 1900 р.
      (a,b)  R, якщо a,b А і країна a межує з b.

  3. Нехай А ={1, 2, 3}, В ={1, 2, 3, 4} і відношення R1, R2 AB:

R1={(1,2), (2,3), (3,4)}; R2={(1,1),(1,2),(2,2),(2,3) ),(3,1) ),(3,2) ),(3,3) ),(3,4d)}.

    1. R1R2;

    2. R1R2;

    3. R1\R2;

    4. R2\R1;

  1. Нехай А – множина студентів технікуму, В – множина книг в бібліотеці.
    Те́хнікум - у СРСР назва основного типу навчальних закладів, що готують фахівців з середньою спеціальною освітою для різних галузей промисловості, будівництва, сільського господарства, транспорту і зв'язку, економіки й права (фахівців середньої кваліфікації не індустріального типу готують середні професійні училища: педагогічні, медичні, художні, театральні та ін.).
    Студе́нт (лат. studens, родовий відмінок studentis - «ретельно працюючий», «такий, що займається») - учень вищого, у деяких країнах і середнього навчального закладу.
    Нехай задані відношення R1, R2: R1 AB, такі, що (a,b)  R1, якщо студент а згідно з навчальною програмою повинен під час навчання прочитати книгу b, і R2 AB, такі, що (a,b)  R2, якщо студент а вже прочитав книгу b. Дайте словесний опис відношень, що одержуються в результаті виконання операцій:

    1. R1R2;
      Програма (фр. programme письмове оголошення, порядок денний, від грец. prógramma вказівка) - заздалегідь затверджена (визначена) дія.
      Сло́во - найменша самостійна і вільно відтворювана в мовленні відокремлено оформлена значима одиниця мови, яка співвідноситься з пізнаним і вичленуваним окремим елементом дійсності (предметом, явищем, ознакою, процесом, відношенням та ін.)


    2. R1R2;

    3. R1\R2;






Скачати 147.93 Kb.

  • 2 Способи задання бінарних відношень
  • 3 Операції над відношеннями