Бінарне відношення на багатьох прикладах з рішенням. Бінарні відносини

Поняття відносини поруч із поняттям безлічі «пронизує» всю математику. Інтуїтивне ставлення розуміється як зв'язок об'єктів. Наше завдання полягає в тому, щоб, використовуючи сформульовані вище конструкції теорії множин, визначити математичною мовою, що розуміється в математиці під терміном «відношення».

Бінарні відносини на безлічі

Нехай дано безліч А.Зв'язок елементів хнубезлічі Амоделюється парою (ду>). Якщо елемент хпов'язаний з у,значить, ми маємо пару (л:, у) як елемент деякої множини; якщо д; не пов'язаний з уотже, пара (л:^) не є об'єктом множини. Отже, маємо таке визначення.

Бінарним ставленням на множині Аназивається довільна безліч пар елементів з А.

Іншими словами, бінарне відношення на безлічі А- от підмножина прямого твору АхА = А 2 .Зокрема, саме безліч А 2всіх пар є бінарним ставленням.

За аналогією з бінарним (або двомісним) ставленням можна розглядати п-місцеве відношенняна множині як підмножина прямого твору А".Ми в основному розглядатимемо бінарні відносини, але для стислості мови говорити просто: «відношення на безлічі А».

Позначимо довільне бінарне відношення грецькою літерою.

Якщо (л",у )е р, то кажуть, що л" знаходиться у відношенні р у,та пишуть

Якщо (ду)? то маємо заперечення відповідного затвердження. І тут разом із записом ~|(хру) (чи хру) пишуть д-ру, перекреслюючи знак відносини.

Приклад 8.1.1. Розглянемо безліч А= (1,2,3,4,5). Безліч пар

визначає на Авідношення «менше», що позначається знаком<.>

11а цій же безлічі можна розглянути інше безліч пар

воно визначає відношення рівності.

Приклад 8.1.2. Розглянемо безліч (N, Z, Q, I, R) основних числових множин та безліч пар

Маємо відношення, визначене нами у пункті 2.2 як відношення суворого включення множин. Зауважимо, що, наприклад, пара (Q. I) нс лежить у зазначеній множині, так як Qczl, більше того, ці множини не перетинаються.

Приклад 8.1.3. Дано безліч слів Л = (струм, кіт, шок, кіл, лак). Розглянемо таке ставлення:

р = ((струм, шок), (шок, струм), (шок, кіл), (кіль, шок),

(кіл, лак), (лак, кіль), (кіт, кіль), (кіл, кіт)).

Це відношення можна виразити таким чином: слова множини Азнаходяться щодо р тоді і тільки тоді, коли вони мають дві однакові букви.

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

Оскільки ставлення є безліччю, його можна задати характеристичним властивістю, то мережа предикатом Р(ху):р = ((.*,>>) еЛ 2 Р(ху)).Також використовується запис:

Читають: «г знаходиться у відношенні до утоді і лише тоді, коли істинно Р(ху)».

Приклад 8.1.4.Визначимо на множині/! = (1,2,3,4,5) відношення:

Тут Р(ху)= (л +2 = у). Задамо це відношення переліком пар:

Приклад 8.1.5.Задамо на безлічі Z(або на безлічі N)відношення за допомогою пропозиції: «Існує ціле число /?, таке, що х=п у».Символічно можна записати:

Маємо вже певне раніше відношення ділимості, яке позначається знаком: . Цьому відношенню належать такі пари, як (6,2), (6,3), (4,4), (111, -37) та інші. На відміну від попередніх прикладів, це безліч пар нескінченно, і перерахувати всі пари не вдасться.

Розглянемо найважливіші властивості, якими можуть мати бінарні відносини на множині.

Відношення р на множині Аназивається рефлексивним, якщо будь-який елемент хз Аперебуває щодо р сам із собою, тобто всім д; з Авиконується лрт:

Приклад 8.1.6.Розглянемо ставлення подільності на безлічі Z.Візьмемо довільне ціле число х.Так як х = х 9то х':х.Отже, будь-яке ціле число поділяється на себе: V.veZ (л: л).Тому ставлення подільності є рефлексивним.

Так як будь-яка множина є підмножиною самого себе, то відношення включення множин рефлексивно (на будь-якій сукупності множин).

Відношення р на множині Аназивається аітірефлексивним, якщо жоден елемент множини Ане знаходиться щодо р із самим собою:

Приклад 8.1.7. Rантирефлексивно, тому що жодне число не менше самого себе.

Побудуємо заперечення до пропозиції «Ставлення р рефлексивно»:

Таким чином, відношення р не є рефлексивним тоді і лише тоді, коли існує елемент хеА,який немає щодо р сам із собою. Ставлення, яке є рефлексивним, має бути аитирефлексивным.

Приклад 8.1.8.Розглянемо ставлення на безлічі R,задане пропозицією «Число хпротилежно до числа у».Число хназивається протилежним числу у,якщо сума х+удорівнює 0.

Це ставлення не є рефлексивним. Контрприклад: х = 1. Так як 1 + 1 * 0, число 1 не протилежно 1.

Це ставлення нс антирефлексивне. Контрприклад: , v = 0. Оскільки 0+0=0, число 0 протилежно 0.

Відношення р на множині Аназивається симетричним, якщо з того, що хзнаходиться щодо р з у,випливає, що узнаходиться щодо р з

Приклад 8.1.9.З тотожності х+у=у+.хвипливає твердження: для будь-яких дійсних чисел хі уякщо хпротилежно v, то упротилежно х.Отже, це відношення симетричне. Часто кажуть просто: «Числа хі упротилежні».

Відношення «Число хменше числа у»на безлічі Rне є симетричним: 3 менше 4 але 4 не менше 3.

Відношення р на множині Аназивається антисиметричним, якщо ні для яких різних елементів х і у з А,таких, що хру,не виконується

урх:

Приклад 8.1.10.Відношення «менше» на безлічі Rантисиметрично.

Визначення антисиметричного відношення можна сформулювати іншими способами. Введемо позначення:

Використовуючи таблицю істинності, можна довести, що формула 1 Р л М-рівносильна формулі Мл К -> Р,яка, у свою чергу, за правилом контрапозиції дорівнює 1 Р->~|(Л/л До).На підставі цього можна сказати, що відношення р є антисиметричним тоді і лише тоді, коли виконується одна з рівносильних умов:

А) З того, що хруі урх,слід х = у:

Б) Ніякі різні елементи що неспроможні одночасно перебувати щодо р друг з одним.

Приклад 8.1.11.Розглянемо ставлення включення довільному сімействі множин. Оскільки ЛсУл Y^X=>X=Y,то включення є антисиметричне відношення.

Приклад 8.1.12.Відношення подільності на безлічі Zне є ні симетричним, ні антисиметричним. Оскільки 4:2, але 2?4, то відношення не симетричне. Оскільки 2:(-2) і (-2):2, але (-2)^2, то відношення не є антисиметричним.

Однак на безлічі N натуральних чисел маємо антисиметричне відношення: Vjt^eN (х: у лу: х -> х = у).Перевірте це твердження, використовуючи визначення ділимості.

Відношення р на множині Аназивається транзитивним, якщо з того, що хзнаходиться щодо р з у,а узнаходиться у відношенні р с z, слід, что.V перебуває щодо р с z:

Приклад 8.1.13.Відношення ділимості транзитивно (і на множині Z і на множині N): х: у л у: z => x: z.Покажемо це. Нехай х:уі y:z.Тоді х = пуі y=kzдля деяких цілих чисел пі до.Тоді х = n(kz) = (nk)z = mz,де тє ціле число. Тому xz.

Відношення включення множин також транзитивно: XcYл YcZ => XezZ.Доведіть.

Відношення «Числа хі упротилежні» не є транзитивним. Контрприклад: х=2,у=-2, 2 = 2. Тоді числа 2 та (-2) протилежні, а також (-2) та 2 протилежні. Але числа х = 2та z=2 нс є протилежними.

Приклад 8.1.14. Розглянемо деякі приклади відносин із попереднього пункту.

Відношення з прикладу 8.1.3 антирефлексивно та симетрично. Відношення з прикладу 8.1.4 антирефлексивно та антисиметрично. Жодне з цих відносин не є транзитивним. Доведіть це, розглянувши відповідні контрприклади.

Деяким відносинам, які мають одночасно ряд властивостей, дано загальні називання. З розглянутих вище прикладів одночасно властивостями рефлексивності, антисимегричності і транзитивності мають відношення включення множин з і відношення подільності на множині N. Також цими трьома властивостями має відношення «хменше чи одно у», визначене на множині R (або на будь-якій його підмножині):

Рефлексивне, антисиметричне та транзитивне відношення називається ставленням порядку.

Безліч А, на якому встановлено ставлення порядку р, називається впорядкованою безліччю. Пишуть (А,р).

В даний час теорія впорядкованої множини - це великий розділ математики, якому присвячені цілі книги. Ми відзначимо лише низку особливостей поняття «упорядковане безліч».

Інтуїтивно слова «упорядковане безліч» часто розуміються у вужчому значенні. Розглянемо впорядковану л-ку, складену з попарно різних елементів. Наприклад, п'ятірка букв (III,К,О,Л,А) визначає слово ШКОЛА. І тут слова «елементи записані у порядку» розуміються тому, що ми занумерували їх натуральними числами 1, 2, 3, 4, 5 і розташували у порядку зростання номерів. Узагальним цей приклад.

Нехай дано «-елементне безліч А.Занумерувавши якимось чином нею елементи а, а 2 >а„,ми дійсно отримаємо впорядковану множину, визначивши відношення порядку наступним чином:

Співвідношення розуміється так: те, що елемент хпов'язаний з іншим елементом у,означає, що хзаписаний у кортежі ліворуч у.

Приклад 8.1.15.Дано безліч /4 = (а, б. в, г). Упорядкована четвірка його різних елементів (б, в, а, г) задасть таке ставлення до порядку:

((б, б), (б, в), (б, а), (б, г), (в, в), (в, а), (в, г), (а, а), ( а, г), (г, г)).

Зауважимо, що порядок не повинен мати так звану властивість лінійності.

Приклад 8.1.16.Розглянемо на безлічі А =(2,4,6,8) відношення подільності:. Задайте це відношення безліччю пар. Бо в Алежать лише натуральні числа, то відношення порядку. Маємо впорядковану множину А, :).

Такий порядок не можна подати у вигляді впорядкованої четвірки наступних один за одним елементів. Можна навести графічну ілюстрацію відносини за допомогою точок та стрілок: з точки хв точку уведе стрілка тоді і лише тоді, коли х:у.

Розглянемо числа 6 і 4. Жодне їх нс ділиться інше. Говорять, що це незрівнянні елементи.

Нехай на безлічі Азадано ставлення порядку нар. Елементи * та уназиваються порівняннимиякщо виконується хоча б одне з двох співвідношень хруабо урх.

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

Приклад 8.1.17.Відношення R є лінійним порядком, оскільки Vx^yeR (х Тому (R,

впорядковане безліч.

Ставлення ділимості натуральних чисел у випадку є лінійним порядком. Контрприклад наведено в прикладі 8.1.16.»

Помстимо, що будь-який лінійний порядок на кінцевій множині задається нумерацією його елементів. Щоб підкреслити, що порядок може бути нс лінійним, впорядкована множина в загальному випадку іноді називають частково впорядкованим.

Розглянемо ставлення «поважати», визначене на багатьох людей %%M%%. Для повної інформаціїпро те, хто кого поважає, складемо таку множину %%R%%. Переберемо всі пари %%(a, b)%%, де %%a, b%% пробігають безліч всіх людей. Якщо %%a%% поважає %%b%%, то пару %%(a,b)%% віднесемо до безлічі %%R%%, інакше — ні.

Цей перелік повністю відбиває ставлення «поважати». Якщо потрібно дізнатися, чи поважає людина %%a%% людини %%b%%, то переглянемо безліч %%R%%. Якщо пара %%(a, b) \in R%%, то укладаємо, що %%a%% поважає %%b%%. У випадку %%(a,b) \notin R%% — %%a%% не поважає %%b%%.

Визначення

Бінарним ставленням, визначеним на множині %%M%%, називається довільне підмножина %%R%% з декартового твору %%M^2%%.

приклад

Розглянемо ставлення більшена множині %%M = \(1, 2\)%%. Тоді

$$ M^2 = \big\((1, 1), (1,2), (2,1), (2,2)\big\) $$ З нього виберемо всі пари %%(a,b )%%, де %% > b%%. Отримаємо $$ R = \big\((2,1)\big\) $$

Види бінарних відносин

Рефлексивне бінарне відношення

рефлексивним, якщо для будь-якого елемента %%a%% з %%M%%, виконується умова %%a~R~a%%. $$ \begin(array)(l) \forall a\in M~~a~R~a \text( або)\\ \forall a\in M~~(a,a) \in R. \end( array) $$

Приклади

  1. Розглянемо ставлення більше більшерефлексивним? Якщо так, то кожне число є більшесамого себе, що не так. Тому ставлення більшене рефлексивно.
  2. Розглянемо ставлення однона безлічі дійсних чисел. Воно є рефлексивним, оскільки кожне дійсне число дорівнює самому собі.

Симетричне бінарне відношення

Бінарне відношення %%R%% на безлічі %%M%% називається симетричним, якщо для будь-яких двох елементів %%a, b%% з %%M%%, з умови %%a~R~b%% слід умова %%b~R~a%%.

$$ \begin(array)(l) \forall a,b\in M~~a~R~b \rightarrow b~R~a \text( або)\\ \forall a,b\in M~~( a, b) \in R \rightarrow (b,a) \in R. \end(array) $$

Приклади

  1. Розглянемо ставлення більшена безлічі дійсних чисел. Чи є ставлення більшесиметричним? Воно не є симетричним, тому що якщо %% a > b % %, то умова % % b > a % % не виконується. Тому ставлення більшене симетрично.
  2. Нехай %%R%% — відношення, визначене на множині %%M = \(a,b,c\)%%. При цьому %% R = b ((a, b), (b, c), (a, a), (b, a), (c, b) \ big \) %%. Для цього відносини маємо %%forall x,y \in M ~~ (x,y) \in R \rightarrow (y,x) \in R%%. За визначенням %%R%% симетрично.

Транзитивне бінарне відношення

Бінарне відношення %%R%% на безлічі %%M%% називається транзитивним, якщо для будь-яких елементів %%a, b, c%% з %%M%%, з умов %%a~R~b%% і %%b~R~c%% слід умова %%a~R~ c%%.

$$ \begin(array)(l) \forall a,b,c\in M~~a~R~b \land b~R~c \rightarrow a~R~c \text( або)\\ \forall a,b,c\in M~~(a,b) \in R \land (b,c) \in R \rightarrow (a,c) \in R. \end(array) $$

приклад

Розглянемо ставлення більшена безлічі діючих чисел. Воно є транзитивним, так як для будь-яких елементів виконується умовні %%forall a,b,c\in M~~a > b \land b > c \rightarrow a > c%%. Так, наприклад, підставивши замість %%a, b%% і %%c%% числа %%2, 1%% і %%0%% відповідно, отримаємо: якщо %%2 > 1%% і %%1 > 0%%, то %2 > 0%% — вірне твердження (згадайте імплікацію, з істини випливає істина).

Антисиметричне бінарне відношення

Бінарне відношення %%R%% на безлічі %%M%% називається антисиметричним, якщо для будь-яких елементів %%a, b%% з %%M%%, з умов %%a~R~b%% і %%b~R~a%% слід умова %%a = b%%.

$$ \begin(array)(l) \forall a,b,c\in M~~a~R~b \land b~R~a \rightarrow a = b \text( або)\\ \forall a, b\in M~~(a,b) \in R \land (b,a) \in R \rightarrow a = b. \end(array) $$

приклад

Ставлення більше або дорівнюєна безлічі дійсних чисел антисиметрично. Дійсно, якщо %%a \geq b%% і %%b \geq a%%, %%a = b%%.

Еквівалентне бінарне відношення

еквівалентностіякщо воно рефлексивно, симетричноі транзитивно.

Неважко перевірити, що ставлення паралельностіна безлічі прямих площин є відношенням еквівалентності.

Відношення часткового порядку

Бінарне відношення %%R%% на безлічі %%M%% називається ставленням часткового порядкуякщо воно рефлексивно, антисиметричноі транзитивно.

Ставлення більше або дорівнюєна багатьох дійсних чисел є ставленням часткового порядку.

Побудова заперечень

Нехай %%R%% — бінарне відношення на безлічі %%M%%, і %%P%% — одна з наступних умов:

  • відношення %%R%% рефлексивно,
  • відношення %%R%% симетрично,
  • відношення %%R%% транзитивно,
  • відношення %%R%% антисиметричне.

Побудуємо для кожного з них заперечення виконання умови %%.

Заперечення рефлексивності

За визначенням %%R%% рефлексивно, якщо кожен елемент множини %%M%% знаходиться у відношенні %%R%% до самого себе, тобто %%forall a \in M~~a~R~a%%. Тоді розглянемо заперечення рефлексивності як справжнє висловлювання %% overline (forall a in M~~a~R~a)%%. Використовуємо рівносильність %%\overline(\forall x P(x)) \equiv \exists x \overline (P(x))%%. У нашому випадку отримуємо %% forall a in M~~a~R~a \equiv \exists a\in M~~a~\not\text(R )~a%%, що і потрібно.

Аналогічно отримуємо та інші заперечення. У результаті отримуємо такі твердження:

    %%R%% не рефлексивно тоді і тільки тоді, коли

    $$ \exists a \in M~~a~\not R~a $$

    %%R%% не симетрично тоді і тільки тоді, коли

    $$ \exists a, b \in M~~ a~R~b \land b~\not R~a $$

    %%R%% не транзитивно тоді і тільки тоді, коли

    $$ \exists a, b, c \in M a~R~b \land b~R~c \land a~\not R~c $$

    %%R%% не антисиметрично тоді і тільки тоді, коли

    $$ \exists a, b \in M~~ a~R~b \land b~R~a \land a \neq b. $$

Нехай задано деяку непорожню множину А і R - деяке підмножина декартового квадрата множини А: RAA.

Відношенням Rна безлічі Аназивають підмножину множини АА(або А 2 ). Таким чином ставленняє окремий випадок відповідності, де область прибуття збігається з областю відправлення. Так само, як і відповідність, ставлення – це впорядковані пари, де обидва елементи належать одному й тому безлічі.

R  A  A = ((a, b) | aA, bA, (a, b)R).

Той факт, що ( a, b)R можна записати так: a R b. Читається: « азнаходиться у відношенні R до b» або «між аі bмає місце відношення R». В іншому випадку записують: ( a, b)R або aR b.

Прикладом відношень на множині чисел є такі: «=», «», «», «>» і т.д. На безлічі співробітників будь-якої фірми - відношення "бути начальником" або "бути підлеглим", на безлічі родичів - "бути предком", "бути братом", "бути батьком" і т.д.

Розглянуті відносини звуться бінарних (двомісних) однорідних відносин і є найважливішими в математиці. Поряд із ними розглядають також п-місцеві або п-арні відносини:

R  A  A … A = A n = ((a 1 , a 2 ,…a n) | a 1 , a 2 ,…a n  A).

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

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

При геометричному (графічному) зображенні відносини ми отримаємо схему, що включає:

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

    і дуги (лінії), що відповідають парам елементів, що входять у бінарні відносини, що позначаються лініями зі стрілками, спрямованими від вершини, що відповідає елементу a до вершини, що відповідає елементу b , якщо a Rb .

Така постать називається орієнтованим графом (або орграфом) бінарного відношення.

Завдання 4.9.1 . Відношення R «бути дільником на множині M = (1, 2, 3, 4)» може бути поставлено матрицею:

перерахуванням: R = ((1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), ((4,4) ));

геометрично (графічно):

1. Виписати упорядковані пари, що належать наступним бінарним відносинам на множині А = (1, 2, 3, 4, 5, 6, 7):

    R1 = ((x, y)|x, yA; x + y = 9);

    R2 = ((x, y)|x, yA; x< y}.

2. Відношення R на множині X = (a, b, c, d) задано матрицею

,

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

3. Відношення на множині А = (1, 2, 3, 4) представлене графом. Необхідно:

    перелічити упорядковані пари, що належать R;

    виписати відповідну матрицю;

    визначити це ставлення з допомогою предикатів.

(Відповідь: a-b= 1).

4.10. Основні типи (властивості) бінарних відносин

Нехай поставлено бінарне ставлення Rна безлічі А 2 : R  A  A = (( a, b) | aA, bA, ( a, b)R)

    Бінарне відношення R на безлічі А називається рефлексивним, якщо для будь-кого aА виконується aRa, тобто ( а,а)R. Головна діагональ матриці рефлексивного відношення складається із одиниць. Граф рефлексивного відношення обов'язково має петлі кожної вершини.

Прикладирефлексивних відносин: , =,  на множині дійсних чисел, «не бути начальником» на множині співробітників.

    Бінарне відношення Rна множині А називається антирефлексивним (іррефлексивним), якщо для будь-кого aА не виконується відношення aRa, тобто ( а,а)R. Головна діагональ матриці іррефлексивного відношення складається з нулів. Граф іррефлексивного відношення не має петель.

Прикладиантирефлексивних відносин:<, >на множині дійсних чисел, перпендикулярність прямих на множині прямих.

    Бінарне відношення R на множині A називається симетричним, якщо для будь-яких a, bАз aRbслід bRa, тобто якщо ( a, b)R, то і ( b, a)R. Матриця симетричного відношення симетрична щодо своєї головної діагоналі ( σ ij = σ ji). Граф симетричного відношення не є орієнтованим (ребра зображуються без стрілок). Кожна пара вершин тут з'єднана неорієнтованим ребром.

Прикладисиметричних відносин:  на безлічі дійсних чисел, «бути родичем» на множині людей.

    Бінарне відношення R на множині A називається:

    антисиметричним, якщо для будь-яких a, bАз aRbі bRaвипливає, що a=b. Тобто, якщо ( a, b)Rі( b, a)R, то звідси випливає, що a=b. Матриця антисиметричного відношення вздовж головної діагоналі має всі одиниці і немає жодної пари одиниць, розташованих на симетричних місцях стосовно головної діагоналі. Іншими словами, все σ ii=1, і якщо σ ij=1, то обов'язково σ ji=0. Граф антисиметричного відношення має петлі у кожної вершини, а вершини з'єднуються лише однією спрямованою дугою.

Прикладиантисиметричних відносин: , ,  на безлічі дійсних чисел; ,  на множинах;

    асиметричним, якщо для будь-яких a, bАз aRb слід невиконання bRa, тобто якщо ( a, b)R, то ( b, a) R. Матриця асиметричного відношення вздовж головної діагоналі має нулі. σ ij=0) все і жодної симетричної пари одиниць (якщо σ ij=1, то обов'язково σ ji=0). Граф асиметричного відношення не має петель, а вершини з'єднані однією спрямованою дугою.

Приклади асиметричних відносин:<, >на безлічі дійсних чисел, «бути батьком» на багатьох людей.

    Бінарне відношення R на множині A називається транзитивним, якщо для будь-яких a, b, зАз aRbі bRaслід, що і aRз. Тобто якщо ( a, b)Rі( b, з)Rвипливає, що ( а, з)R. Матриця транзитивного відношення характеризується тим, що якщо σ ij=1 і σ jm=1, то обов'язково σ im=1. Граф транзитивного відношення такий, що якщо з'єднані дугами, наприклад, перша-друга та друга-третя вершини, то обов'язково є дуги з першої до третьої вершини.

Прикладитранзитивних відносин:<, , =, >,  на безлічі дійсних чисел; «Бути начальником» на безлічі співробітників.

    Бінарне відношення R на множині A називається антитранзитивним, якщо для будь-яких a, b, зАз aRbі bRaслід, що не виконується aRз. Тобто якщо ( a, b)Rі( b, з)Rвипливає, що ( а, з) R. Матриця антитранзитивного відношення характеризується тим, що якщо σ ij=1 і σ jm=1, то обов'язково σ im=0. Граф антитранзитивного відношення такий, що якщо з'єднані дугами, наприклад, перша-друга та друга-третя вершини, то обов'язково немає дуги з першої до третьої вершини.

Приклади антитранзитивних відносин: «Несупадність парності» на безлічі цілих чисел; «Бути безпосереднім начальником» на безлічі співробітників.

Якщо відношення не володіє деякою властивістю, то, додавши пари, можна отримати нове відношення з даною властивістю. Безліч таких відсутні пар називають замиканнямвідносини по даною властивістю. Позначають його як R* . Так можна отримати рефлексивне, симетричне та транзитивне замикання.

Завдання 4.10.1. На множині А = (1, 2, 3, 4) задано ставлення R=(( a,b)| a,bA, a+bпарне число). Визначити тип цього відношення.

Рішення. Матриця цього відношення:

. Очевидно, що ставлення є рефлексивним, тому що вздовж головної діагоналі розташовані одиниці. Воно симетрично: σ 13 = σ 31 , σ 24 = σ 42 . Транзитивно: (1,3)R, (3,1)R та (1,1)R; (2,4)R, (4,2)R та (2,2)R і т.д.

Завдання 4.10.2. Якими властивостями на множині А = ( a, b, c, d) має бінарне відношення R = (( a,b), (b,d), (a,d), (b,a), (b,c)}?

Рішення . Побудуємо матрицю даного відношення та його граф:

Ставлення іррефлексивно, тому що всі σ ii= 0. Воно не симетрично, оскільки σ 23 =1, а σ 32 =0, проте σ 12 = σ 21 =1. Ставлення не транзитивно, Оскільки 12 =1, 23 =1 і 13 =0; 12 = 1, 21 = 1 і 11 = 0; але при цьому 12 =1, 24 =1 і 14 =1.

Завдання 4.10.3. На множині А = (1,2,3,4,5) задано ставлення R = ((1,2), (2,3), (2,4), (4,5)). Визначити тип відношення та знайти наступні замикання для R:

    рефлексивне;

    симетричне;

    транзитивний.

Рішення. Відношення іррефлексивне, оскільки немає жодного елемента виду ( а,а). Асиметрично, тому що не містить пар виду ( a,b) та ( b,a) і всі діагональні елементи дорівнюють 0. Антитранзитивно, оскільки (1,2)R, (2,3)R, але (1,3)R. Аналогічно (2,4)R, (4,5)R, а (2,5)R тощо.

    рефлексивне замикання цього відношення R * = ((1,1), (2,2), (3,3), (4,4), (5,5));

    симетричне замикання: R*=((2,1), (3,2), (4,2), (5,4));

    транзитивне замикання: R * = ((1,3), (1,4), (2,5)). Розглянемо граф вихідного відношення та отриманого транзитивного.

Завдання для самостійного вирішення.

1. Задано ставлення R = ((1,1), (1,2), (1,3), (3,1), (2,3)). Визначити його тип і знайти замикання з рефлексивності, симетричності та транзитивності.

2.Ставление на безлічі слів російської визначено так: а R bтоді й лише тоді, коли вони мають хоч одну спільну букву. Визначити тип відношення на множині А = (корова, вагон, нитка, сокира).

3. Вказати приклади бінарних відносин на безлічі А = (1, 2) та В = (1, 2, 3), які були б:

    не рефлексивний, не симетричний, не транзитивний;

    рефлексивний, не симетричний, не транзитивний;

    симетричне, але не рефлексивне та не транзитивне;

    транзитивне, але не рефлексивне та не симетричне;

    рефлексивний, симетричний, але не транзитивний;

    рефлексивний, транзитивний, але не симетричний;

    не рефлексивний, симетричний, транзитивний;

    рефлексивний, симетричний, транзитивний.

У повсякденному життінам доводиться стикатися з поняттям «відносини». Відносини – один із способів завдання взаємозв'язків між елементами множини.

Унарні (одномісні) відносини відображають наявність якоїсь однієї ознаки R у елементів множини M (наприклад, «бути червоною» на безлічі куль в урні).

Бінарні (двомісні) відносини використовуються для визначення взаємо

зв'язків, якими характеризуються пари елементів у множині M.

Наприклад, на багатьох людей можуть бути задані такі відносини: «жити в одному місті», « xпрацює під керівництвом y», «Бути сином», «Бути старшим» і т.д. на безлічі чисел: «число aбільше числа b», «число aє дільником числа b», «числа aі bдають однаковий залишок при розподілі на 3».

У прямому творі, де A- безліч студентів будь-якого вузу, B- безліч предметів, що вивчаються, можна виділити велику підмножину впорядкованих пар (a, b), які мають властивість: «студент aвивчає предмет b». Побудована підмножина відображає відношення «вивчає», що виникає між множинами студентів та предметів. Число прикладів можна продовжити

Відносини між двома об'єктами є предметом дослідження економіки, географії, біології, фізики, лінгвістики, математики та інших наук.

Для суворого математичного опису будь-яких зв'язків між елементами двох множин вводиться поняття бінарного відношення.

Бінарним ставленням між множинами A та Bназивається підмножина R прямого твору. У тому випадку, коли можна просто говорити про ставлення Rна A.

Приклад 1. Випишіть упорядковані пари, що належать бінарним відносинам R 1і R 2, заданими на множинах Aта : , . Підмножина R 1складається з пар: . Підмножина.

Область визначення Rє безліч всіх елементів з Aтаких, що для деяких елементів маємо . Іншими словами область визначення Rє безліч усіх перших координат упорядкованих пар з R.

Безліч значеньвідносини Rє безліч всіх таких, що для деяких . Тобто безліч значень Rє безліч всіх других координат упорядкованих пар з R.

У прикладі 1 для R 1область визначення: , множина значень - . Для R 2Область визначення: , безліч значень: .

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

У першому випадку вибирають дві взаємно перпендикулярні лінії як горизонтальну і вертикальну осі. На горизонтальній осі відкладають елементи множини Aта через кожну точку проводять вертикальну лінію. На вертикальній осі відкладають елементи множини Bчерез кожну точку проводять горизонтальну лінію. Точки перетину горизонтальних та вертикальних ліній зображують елементи прямого твору.

Приклад 5. Нехай,.

Нехай R 1поставлено на перерахуванням упорядкованих пар: . Бінарне відношення R 2на безлічі задано за допомогою правила: упорядкована пара, якщо aділиться на b. Тоді R 2складається з пар: .

Бінарні відносини, приклад 2, R 1і R 2зображено графічно на рис. 6 та рис.7.

Мал. 6 Мал. 7

Щоб зобразити бінарне відношення за допомогою стрілок, ліворуч зображуються крапками елементи множини A, праворуч - множини B. Для кожної пари (a, b), що міститься у бінарному відношенні R, проводиться стрілка від aдо b, . Графічне зображення бінарного відношення R 1, наведеного у прикладі 6, показано на рис.8.

Рис.8

Бінарні відносини на кінцевих множинах можуть бути задані матрицями. Припустимо, що поставлено бінарне ставлення Rміж множинами Aі B. , .

Рядки матриці нумеруються елементами множини A, а стовпці – елементами множини B. Осередок матриці, що стоїть на перетині i- ого рядка та j- ого стовпця прийнято позначати через C ij , а заповнюється вона так:

Отримана матриця матиме розмір.

Приклад 6.Нехай задано безліч. На безлічі задайте списком та матрицею відношення R- «Бути суворо менше».

Ставлення Rяк безліч містить усі пари елементів ( a, b)з Mтакі, що .

Матриця відносини, побудована за вищевказаними правилами, має такий вигляд:

Властивості бінарних відносин:

1. Бінарне відношення Rна безлічі називається рефлексивним, якщо для будь-якого елемента aз Mпара (a, a)належить R, тобто. має місце для будь-кого aз M:

Відносини "жити в одному місті", "вчитися в одному вузі", "бути не більше" є рефлексивними.

2. Бінарне ставлення називається антирефлексивнимякщо воно не володіє властивістю рефлексивності для будь-яких a:

Наприклад, «бути більше», «бути молодшими» - це антирефлексивні відносини.

3. Бінарне відношення Rназивається симетричним, якщо для будь-яких елементів aі bз Mз того, що пара (a, b)належить R, , Випливає, що пара (b, a)належить R, тобто.

Симетричнапаралельність прямих, т.к. якщо то // . Симетричне відношення"бути рівним" на будь-якій множині або "бути взаємнопростим на N".

Відношення R симетрично тоді і лише тоді, коли R=R -1

4. Якщо для несупадних елементів правильне ставлення, але хибно, то відношення антисиметрично. Можна сказати інакше:

Антисиметричними є стосунки«Бути більше», «Бути дільником на N», «Бути молодшим».

5. Бінарне відношення Rназивається транзитивним, якщо для будь-яких трьох елементів з того, що пари (a, b)і (b, c)належать Rслід, що пара (a, c) належить R:

Транзитивні відносини: «Бути більше», «Бути паралельним», «Бути рівним» та ін.

6. Бінарне відношення R антитранзитивно, якщо воно не має властивості транзитивності.

Наприклад, «бути перпендикулярним» на безлічі прямих площин ( , , але невірно, що ).

Т.к. бінарне відношення може бути поставлене не лише прямим перерахуванням пар, а й матрицею, то доцільно з'ясувати, якими ознаками характеризується матриця відношення Rякщо воно: 1) рефлексивно, 2) антирефлексивно, 3) симетрично, 4) антисиметрично, 5) транзитивно.

Нехай Rзадано на , .R або виконується в обидві сторони, або не виконується взагалі. Таким чином, якщо в матриці стоїть одиниця на перетині i- ого рядка та j- ого стовпця, тобто. C ij=1, то вона має стояти і на перетині j- ого рядка та i- ого стовпця, тобто. C ji=1, і навпаки, якщо C ji=1, то C ij=1. Таким чином, матриця симетричного відношення симетрична щодо головної діагоналі.

4. Rантисиметрично, якщо і слід: . Це означає, що у відповідній матриці для жодних i, jне виконується C ij =C ji=1. Таким чином, у матриці антисиметричного відношення відсутні одиниці, симетричні щодо головної діагоналі.

5. Бінарне відношення R на непустому множині A називається транзитивнимякщо

Наведена вище умова повинна виконуватися для будь-яких елементів матриці. І, навпаки, якщо у матриці Rє хоча б один елемент C ij=1, для якого ця умоване виконується, то Rне транзитивно.

лекція 3.

п.3. Відносини на множинах. Властивості бінарних відносин.

3.1. Бінарні відносини.

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

У математиці серед усіх упорядкованих пар прямого твору двох множин Aі B (A´ B) теж виділяються «особливі» пари у зв'язку з тим, що між їх компонентами є деякі «родинні» відносини, яких немає в інших. Як приклад розглянемо безліч Sстудентів якогось університету та безліч Kчитаних курсів. У прямому творі S´ Kможна виділити велику підмножину упорядкованих пар ( s, k), які мають властивість: студент sслухає курс k. Побудована підмножина відображає відношення «…слухає…», що природно виникає між множинами студентів та курсів.

Для суворого математичного опису будь-яких зв'язків між елементами двох множин введемо поняття бінарного відношення.

Визначення 3.1. Бінарним (або двомісним )ставленням rміж множинами Aі Bназивається довільне підмножина A´ B, тобто.

Зокрема, якщо A=B(тобто rÍ A 2), то кажуть, що r є відношення на множині A.

Елементи aі bназиваються компонентами (або координатами ) Відношення r.

Зауваження. Домовимося, що з позначення відносин між елементами множин використовувати грецький алфавіт : r, t, j, s, w тощо.


Визначення 3.2. Областю визначення D r=( a| $ b, що a r b) (ліва частина). Область значень бінарного відношення r називається безліч R r=( b| $ a, що a r b) (права частина).

приклад 3. 1. Нехай дані дві множини A=(1; 3; 5; 7) та B= (2; 4; 6). Відношення поставимо наступним чином t=(( x; y)Î A´ B | x+y=9). Це відношення складатиметься з наступних пар (3; 6), (5; 4) та (7; 2), які можна записати у вигляді t=((3; 6), (5; 4), (7;2) ). У цьому прикладі D t=(3; 5; 7) та R t= B={2; 4; 6}.

приклад 3. 2. Відношення рівності на безлічі дійсних чисел є множина r=(( x; y) | xі y– дійсні числа та xодно y). І тому відносини існує спеціальне позначення «=». Область визначення збігається з областю значень і є безліччю дійсних чисел, D r= R r.

приклад 3. 3. Нехай A– безліч товарів у магазині, а B- Багато дійсних чисел. Тоді j=(( x; y)Î A´ B | y- ціна x) - відношення множин Aі B.

Якщо звернути увагу приклад 3.1., можна помітити, що це ставлення було поставлено спочатку як t=(( x; y)Î A´ B | x+y=9), та був записано як t=((3; 6), (5;4), (7;2)). Це говорить про те, що відносини на множинах (або одній множині) можна ставити різними способами. Розглянемо методи завдання бінарних відносин.

Способи завдання відносин:

1) за допомогою відповідного предикату;

2) безліч упорядкованих пар;

3) у графічній формі: нехай Aі B– дві кінцеві множини та r – бінарне відношення між ними. Елементи цих множин зображаємо крапками на площині. Для кожної впорядкованої пари відношення r малюють стрілку, що з'єднує точки, що становлять компоненти пари. Такий об'єкт називається орієнтованим графомабо орграфом, Точки ж, що зображають елементи множин, прийнято називати вершинами графа.

4) у вигляді матриці: нехай A={a 1, a 2, …, an) та B={b 1, b 2, …, bm), r - ставлення на A´ B. Матричним уявленням r називається матриця M=[mij] розміру n´ m, визначена співвідношеннями

.

До речі, матричне уявлення є уявленням в комп'ютері.

приклад 3. 4. Нехай дані дві множини A=(1; 3; 5; 7)і B= (2; 4; 6). Ставлення задано так t=(( x; y) | x+y=9). Задати це ставлення як безліч упорядкованих пар, орграфом, як матриці.

Рішення. 1) t=((3; 6), (5; 4), (7; 2)) - є завдання відношення як безлічі упорядкованих пар;

2) відповідний орієнтований граф показаний малюнку.

https://pandia.ru/text/78/250/images/image004_92.gif" width="125" height="117">.

приклад 3. 5 . Ще як приклад можна розглянути запропоновану Дж. фон Нейманом(1903 - 1957) блок-схему ЕОМ послідовної дії, яка складається з безлічі пристроїв M:

,

де a- Пристрій введення, b- арифметичний пристрій (процесор), c- пристрій керування, d- запам'ятовуючий пристрій, e- Влаштування виведення.

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

Це бінарне відношення можна задати перерахуванням усіх його 14 упорядкованих пар елементів:

Відповідний орграф, який задає це бінарне відношення, представлений на малюнку:


Матричне уявлення цього бінарного відношення має вигляд:

. ,

Для бінарних відносин звичайним чином визначені теоретико-множинні операції: об'єднання, перетин тощо.


Введемо узагальнене поняття відносини.

Визначення 3.3. n-місцеве (n-арне ) відношення r – це підмножина прямого твору nмножин, тобто безліч упорядкованих наборів ( кортежів )

rÍ A 1´…´ An={(a 1, …, an)| a 1Î A 1Ù … Ù anÎ An}

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

Слово « реляційна» походить від латинського слова relation, що у перекладі російською мовою означає «відношення». Тому в літературі для позначення відносин використовують букву R(латинську) або r (грецьку).

Визначення 3.4.Нехай rÍ A´ Bє відношення на A´ B.Тоді відношення r-1 називається зворотним ставленням до цього відношення r на A´ B, Яке визначається наступним чином:

r-1=(( b, a) | (a, b) Îr).

Визначення 3.5.Нехай r Í A´ Bє відношення на A´ B,а s Í B´ C –ставлення на B´ C. Композицієювідносин s і r називається відношення t Í A´ C, Яке визначається наступним чином:

t=s◦r= (( a, c)| $bÎ B, що (a, b)Îr і (b, c) Îs).

приклад 3. 6 . Нехай і C=(, !, d, à). І нехай відношення r на A´ Bі ставлення s на B´ Cзадані у вигляді:

r=((1, x), (1, y), (3, x)};

s=(( x,), (x, !), (y, d), ( y, à)}.

Знайти r-1 та s◦r, r◦s.

Рішення. 1) За визначенням r-1=(( x, 1), (y, 1), (x, 3)};

2) Використовуючи визначення композиції двох відносин, отримуємо

s◦r=((1,), (1, !), (1, d), (1, à), (3,), (3, !)),

оскільки з (1, x)Îr та ( x,)Îs слід (1,)Îs◦r;

з (1, x)Îr та ( x, !)Îs слід (1, !)Îs◦r;

з (1, y)Îr та ( y, d)Îs слід (1, d)Îs◦r;

з (3, x)Îr та ( x, !)Îs слід (3, !)Îs◦r.

Теорема 3.1.Для будь-яких бінарних відносин виконуються такі властивості:

2) ;

3) - асоціативність композиції.

Доведення.Властивість 1 очевидна.

Доведемо властивість 2. Для доказу другої властивості покажемо, що множини, записані в лівій та правій частинах рівності, складаються з одних і тих самих елементів. Нехай ( a; b) Î (s◦r)-1 ¢ ( b; a) Î s◦r û $ cтаке, що ( b; c) Î r та ( c; a) Î s û $ cтаке, що ( c; b) Î r-1 та ( a; c) Î s-1 ¢ ( a; b) Î r -1◦s -1.

Властивість 3 довести самостійно.

3.2. Властивості бінарних відносин.

Розглянемо спеціальні властивості бінарних відносин на безлічі A.

Властивості бінарних відносин.

1. Відношення r на A´ Aназивається рефлексивним , якщо ( a,a) належить r для всіх aз A.

2. Відношення r називається антирефлексивним , якщо з ( a,b)Îr слід a¹ b.

3. Відношення r симетрично , якщо для aі b, що належать A, з ( a,b)Îr слід, що ( b,a)Îr.

4. Відношення r називається антисиметричним , якщо для aі bз A, з приладдя ( a,b) та ( b,a) відношенню r випливає, що a=b.

5. Відношення r транзитивно , якщо для a, bі cз Aз того, що ( a,b)Îr та ( b,c)Îr, слідує, що ( a,c)Îr.

приклад 3. 7. Нехай A=(1; 2; 3; 4; 5; 6). На цій множині задано ставлення rÍ A 2, яке має вигляд: r=((1, 1), (2, 2), (3, 3), (4; 4), (5; 5), (6; 6), (1; 2) , (1; 4), (2; 1), (2; 4), (3; 5), (5; 3), (4; 1), (4; 2)). Якими властивостями має це відношення?

Рішення. 1) Це ставлення рефлексивне, оскільки для кожного aÎ A, (a; a)Îr.

2) Ставлення перестав бути антирефлексивним, оскільки виконується умова цієї характеристики. Наприклад, (2, 2)Îr, але звідси не випливає, що 2¹2.

3) Розглянемо всі можливі випадки, показавши, що відношення r є симетричним:

(a, b)Îr

(b, a)

(b, a)Îr?

4) Дане відношення не є антисиметричним, оскільки (1, 2) Îr та (2,1) Îr, але звідси не випливає, що 1=2.

5) Можна показати, що відношення r транзитивне, використовуючи метод прямого перебору.

(a, b)Îr

(b, c)Îr

(a, c)

(a, c)Îr?

Як по матриці уявлення

визначити властивості бінарного відношення

1. Рефлексивність:на головній діагоналі стоять всі одиниці, зірочками позначені нулі чи одиниці.

.

2. Антирефлексивність:на головній діагоналі всі нулі.

3. Симетричність:якщо.

4. Антисиметричність:всі елементи поза головною діагоналі дорівнюють нулю; на головній діагоналі також можуть бути нулі.

.

Операція «*» виконується за таким правилом: де , .

5. Транзитивність:якщо. Операція "◦" виконується за звичайним правилом множення, при цьому треба враховувати: .

3.3 Відношення еквівалентності. Відношення часткового порядку.

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

Визначення 3.6.Відношення r на Aє відношення еквівалентності, якщо воно рефлексивно, симетрично та транзитивно.Відношення еквівалентності a r bчасто позначається: a~ b.

приклад 3. 8 . Відношення рівності на багатьох цілих чисел є відношення еквівалентності.

приклад 3. 9 . Ставлення «одного зростання» є відношення еквівалентності на багатьох людей X.

приклад 3. 1 0 . Нехай ¢ – безліч цілих чисел. Назвемо два числа xі yз ¢ порівнянними за модулемm(mÎ¥) і запишемо , якщо рівні залишки цих чисел від розподілу їх на m, Т. е. різниця ( x-y) ділиться на m.

Відношення «порівняних за модулем mцілих чисел» є відношення еквівалентності на безлічі цілих числа ¢. Справді:

це ставлення рефлексивно, т. до. x΢ маємо x-x=0, і, отже, воно поділяється на m;

це відношення симетрично, тому що якщо ( x-y) ділиться на m, то і ( y-x) теж ділиться на m;

це ставлення транзитивно, тому що якщо ( x-y) ділиться на m, то для деякого цілого t 1 маємо https://pandia.ru/text/78/250/images/image025_23.gif" width="73" height="24 src=">, звідси , Т. е. ( x-z) ділиться на m.

Визначення 3.7.Відношення r на Aє відношення часткового порядку, якщо воно рефлексивно, антисиметрично та транзитивнота позначається символом °.

Частковий порядок важливий у тих ситуаціях, коли хочемо якось охарактеризувати старшинство. Іншими словами, вирішити за яких умов вважати, що один елемент множини перевершує інший.

приклад 3. 11 . Ставлення x£ yна багатьох дійсних чисел є відношення часткового порядку. ,

приклад 3. 1 2 . У безлічі підмножин деякої універсальної множини Uставлення AÍ Bє відношення часткового порядку.

приклад 3. 1 3 . Схема організації підпорядкування установі є ставлення часткового порядку на багатьох посад.

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

Формулювання завдання:нехай є сукупність об'єктів Aі потрібно порівняти їх за перевагою, тобто задати відношення переваги на множині Aта визначити найкращі об'єкти.

Відношення переваги P, яке можна визначити як « aPb, a, bÎ A¯ об'єкт aне менш кращий, ніж об'єкт b» є за змістом рефлексивним і антисиметричним (кожен об'єкт не гірший за самого себе, і, якщо об'єкт aне гірше bі bне гірше a, то вони однакові за перевагою). Природно вважати, що ставлення Pтранзитивно (хоча у разі, коли, наприклад, переваги обговорюються групою осіб із протилежними інтересами, ця властивість може бути порушена), тобто. P- Відношення часткового порядку.

Один із можливих способів вирішення завдання порівняння об'єктів за перевагою – ранжування , тобто впорядкування об'єктів відповідно до зменшення їх переваги або рівноцінності. У результаті ранжирування ми виділяємо «найкращі» чи «найгірші» з погляду відношення переваги об'єкти.

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