На головну

 Основні позначення |  Діаграми (кола) Ейлера-Венна |  докази |  Вектори, прямі твори, проекції векторів |  Бінарні відносини. Основні визначення |  Властивості бінарних відносин |  Еквівалентність і порядок |  операції |  Гомоморфізми і ізоморфізми |  Підручники і навчальні посібники |

Відповідності та їх властивості. Основні визначення

  1.  B.1.1 Основні положення
  2.  ER-модель бази даних. Основні нотації зображення ER-моделі.
  3.  I Основні категорії педагогіки
  4.  I Розрахунок витрат для визначення повної собівартості вироби (роботи, послуги), визначення рентабельності його виробництва
  5.  I. Основні положення
  6.  I. Основні принципи
  7.  I. ОСНОВНІ СТРАХОВІ ПОНЯТТЯ

відповідність G між множинами A и B: GIA?B. якщо (a, b) IG, То кажуть, що "b відповідає a при відповідності G".

Область визначення відповідності G - Безліч ін1G= {a: (a, b) IG}. область значень відповідності G - Безліч ін2G= {b: (a, b) IG}.

властивості відповідностей GIA?B:

· усюди (повністю) певне відповідність - якщо пр1G=A. Частково певну відповідність - в іншому випадку.

· Сюр'ектівное відповідність - Якщо пр2G=B.

чином елемента a в безліч B при відповідності G називається безліч всіх bIB, Відповідних елементу aIA. прообразом елемента b в безліч A при відповідності G називається безліч всіх aIA, Яким відповідає bIB.

чином безлічі CIпр1G називається об'єднання образів усіх елементів aIC. прообразом безлічі DIпр2G називається об'єд-нання прообразів всіх елементів bID.

· Функціональне (однозначне) відповідність - якщо чином будь-якого елементу a з області визначення ін1G є єдиний елемент b з області значень ін2G.

· Взаємна однозначна відповідність - якщо воно: а) усюди визна-лено; б) сюр'ектівно; в) функціонально; г) прообразом будь-якого елементу b з області значень ін2G є єдиний елемент a з області визначення ін1G.

· Якщо між множинами A и B існує взаємно однозначна відповідність, то потужності цих множин рівні, тобто |A| = |B|. У такому випадку говорять, що безлічі A и B рівнопотужні.

Безлічі, рівнопотужності безлічі натуральних чисел N, Називаються вають рахунковими. Безлічі, рівнопотужності безлічі дійсних чисел R, називаються континуальними.

зауваження. Різниця між поняттями відповідності та відносини наступна: відповідність має напрямок від області визначення (відправлення) До області значень (прибуття); якщо (a, b) IG, то першій компоненті пари а відповідає друга компонента пари b; елементи а и b не рівноправною.

Відносини характеризують властивості пар з M2; якщо а j b, То елементи а и b при цьому рівноправні, просто пара (а, b) Має властивість j.

Бінарне відношення на множині є окремим випадком відповідності.

Приклад 1.нехай G - Безліч всіх пар дійсних чисел (x, y), Що задовольняють співвідношенню (x-3)2+ (y-2)2? 1. Графічно таке відповідність G являє собою коло радіуса 1 з центром в точці (3, 2). Таким чином, коло G задає відповідність між R и R (Віссю абсцис і віссю ординат, рис 3.1).

Визначити, чому дорівнюють:

а) образи і прообрази чисел 2, 3, 4;

б) образи і прообрази відрізків [2, 3], [2, 4].

Які властивості відповідності G?

а) Образом числа 2Iпр1G (На осі абсцис) при відповідно G (Див. Рис. 3.1) є однина 2Iпр2G (На осі ординат). Образ числа 3 при відповідно G є безліч всіх дійсних чисел відрізка [1, 3], а образ числа 4 - число 3.

Прообразом числа 2Iпр2G (На осі ординат) при відповідно G буде безліч всіх дійсних чисел відрізка [2, 4] Iпр1G (На осі абсцис), прообразом числа 3 при відповідно G - Число 3, а прообразу числа 4 при відповідно G не існує.

б) Образом безлічі чисел відрізка [2, 3] I ін1G є об'єднаннями-ня образів всіх чисел відрізка, тобто відрізок [1, 3] Iпр2G. Аналогічно чином відрізка [2, 4] буде відрізок [1, 3] при відповідно G.

Прообраз відрізка [2, 3] при відповідно G - Це відрізок [2, 4], а прообраз відрізка [2, 4] - також [2, 4].

Якщо допустити, що відповідність G встановлено на множині дійсних чисел, тобто GIR?R, То воно є:

· Частково певним, так як пр1G?R (пр1GIR);

· Не сюр'ектівним, оскільки ін2G?R (пр2GIR);

· Не функціональним, бо для будь-якого числа відрізка [2, 4] = ін1G (Крім чисел 2, 4) відсутній єдиність способу;

· Не взаємно однозначним, так як відсутні необхідні умови: G не є всюди певним на R, Що не сюр'ектівно, що не функціонально, а також для будь-якого числа відрізка [1, 3] = ін2G (Крім чисел 1, 3) відсутній єдиність прообразу.

Якщо визначити відповідність GI [2, 4] '[1, 3], то, очевидно, воно буде скрізь певним і сюр'ектівним, однак залишиться не функціональним і не взаємно однозначним.

Приклад 2.Нехай безлічі b (U), Де U= {a, b, c}, І B3 визначені в такий спосіб:

b (U) - Безліч всіх підмножин (булеан) безлічі U= {a, b, c};

B3 - Безліч всіх двійкових векторів довжини 3, тобто B3=A?A?A, де A= {0, 1}.

Показати, що між множинами b (U) і B3, де U= {a, b, c}, Має місце взаємно однозначна відповідність.

b (U) = {?, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}; | B (U) | = 8.

B3= {(000), (001), (010), (011), (100), (101), (110), (111)}; |B3| = 8.

(Для спрощення позначень коми між компонентами векторів опущені).

Встановимо наступне відповідність G між множинами з b (U) І векторами з B3:

· Якщо в безлічі з b (U) Присутній елемент а, То в відповід-ствующая йому векторі з B3 перша компонента дорівнює 1, а якщо відсутній - то 0;

· Якщо в безлічі з b (U) Присутній елемент b, То в відповід-ствующая йому векторі з B3 друга компонента дорівнює 1, а якщо відсутній - то 0;

· Аналогічне відповідність встановимо між елементом с в мно-дружність з b (U) І значенням третьої компоненти вектора з B3.

Наприклад, безлічі {b} З b (U) Відповідає вектор (010) з B3, Безлічі {a, c} - Вектор (101) і т.д .:

G: ?® (000), {a} ® (100), {b} ® (010), {c} ® (001), {a, b} ® (110), {a, c} ® (101), {b, c} ® (011), {a, b, c} ® (111).

Очевидно, що встановлене таким чином відповідність G є взаємно однозначним, так як виконуються всі умови для взаємно однозначної відповідності.

Приклад 3.Які властивості відповідності між безліччю N натуральних чисел і множиною M2n ступенів двійки:

G= {(n, 2n-1): nIN, 2n-1IM2n } IN?M2n?

відповідність G взаємно однозначно:

· Всюди визначено, так як пр1G=N;

· Сюр'ектівно, оскільки ін2G=M2n;

· Функціонально, так як будь-якій nIN відповідає єдність-ний образ 2n-1IM2n ;

· Характеризується одиничністю прообразу, бо для будь-якого 2n-1IM2n існує єдине nIN;

Приклад 4.Використовуючи визначення рівнопотужності множин, показати, що безліч M2n натуральних чисел, які є ступенями двійки, лічильно.

Для доказу слід встановити взаємно однозначну відповідність між множинами M2n и N. Якщо кожному натуральному nIN поставити у відповідність число 2n-1IM2n, То встановлене таким чином відповідність GIN?M2n, Очевидно, є взаємно однозначним (задовольняє всім вимогам для взаємно однозначного відповідності, см. Приклад 3) і представляє безліч всіх векторів G= {(n, 2n-1): nIN}. А так як потужність безлічі N Рахункова, то з встановленої взаємної однозначності між множинами N и M2n, Згідно з визначенням рівнопотужності нескінченних множин, слід, що безліч M2n також лічильно.

Питання для самоперевірки та вправи:

1.Які властивості відповідності G між безліччю N натурал-них чисел і безліччю M2n натуральних парних чисел:

GIN?M2n; G= {(n, 2n): nIN, 2nIM2n }.

2.Використовуючи визначення рівнопотужності множин, показати, що безліч M2n натуральних парних чисел лічильно.

 



 Операції над бінарними відносинами |  Функції та відображення
© um.co.ua - учбові матеріали та реферати