Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Бінарне відношення



План:


Введення

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


1. Пов'язані визначення

  • R називають бінарним відношенням на множині A , Якщо R \ subset A \ times A . При цьому замість запису (X, \; y) \ in R часто використовують запис x R y.
  • Якщо R \ subset A \ times B, то кажуть, що R визначено на парі множин A і B .
  • Безліч всіх перших елементів пар з R називається областю визначення ставлення R і позначається як \ Mathrm {Dom} \, R .
\ Mathrm {Dom} \, R = \ {x \ mid \ exists y ((x, \; y) \ in R) \}.
  • Безліч усіх других елементів пар з R називається областю значення відносини R і позначається як \ Mathrm {Im} \, R .
\ Mathrm {Im} \, R = \ {y \ mid \ exists x ((x, \; y) \ in R) \}.
  • Інверсія (Зворотне відношення) R - Це безліч \ {(X, \; y) \ mid (y, \; x) \ in R \} і позначається, як R - 1 .
  • Композиція (суперпозиція) бінарних відносин R і S - Це безліч \ {(X, \; y) \ mid \ exists z (xSz \ and zRy) \} і позначається, як R \ circ S .

2. Властивості відносин

Бінарні відносини можуть володіти різними властивостями, такими як


3. Види відносин


3.1. Види двомісних відносин

  • Зворотне відношення [ уточнити ] (відношення, зворотне до R) - це двомісне відношення, що складається з пар елементів (у, х), отриманих перестановкою пар елементів (х, у) даного відношення R. Позначається: R -1. Для даного відношення і зворотного йому вірно рівність: (R -1) -1 = R.
  • Взаємо-зворотні відносини (взаімообратних відносини) - відносини, які є зворотними один по відношенню до одного. Область значень одного з них служить областю визначення іншого, а область визначення першого - областю значень іншого.
  • Рефлексивне ставлення - двомісне відношення R, визначене на деякій множині і відрізняється тим, що для будь-якого х цієї множини елемент х знаходиться у відношенні R до самого себе, тобто для будь-якого елемента х цього безлічі має місце xRx. Приклади рефлексивних відносин: рівність, одночасність, подібність.
  • Антірефлексівное ставлення (Іррефлексівное ставлення, омета, що також як антисиметричність не співпадає з несиметричною іррефлексівность не співпадає з Нерефлексівное.) - двомісне відношення R, визначене на деякій множині і відрізняється тим, що для будь-якого елемента х цієї множини не так, що воно знаходиться у відношенні R до самого себе (не так, що xRx), тобто можливий випадок, що елемент множини не знаходиться у відношенні R до самого себе. Приклади нерефлексвних відносин: "піклуватися про", "розважати", "нервувати".
  • Транзитивне відношення - двомісне відношення R, визначене на деякій множині і відрізняється тим, що для будь-яких х, у, z цієї множини з xRy і yRz слід xRz (xRy & yRz \ To xRz). Приклади транзитивних відносин: "більше", "менше", "дорівнює", "подібно", "вище", "північ".
  • Нетранзітівное ставлення [ уточнити ] - двомісне відношення R, визначене на деякій множині і відрізняється тим, що для будь-яких х, у, z цієї множини з xRy і yRz не слід xRz ( \ Neg (XRy & yRz \ To xRz)). Приклад нетранзітівного відносини: "x батько y"
  • Симетричне відношення - двомісне відношення R, визначене на деякій множині і відрізняється тим, що для будь-яких елементів х і у цієї множини з того, що х знаходиться к у в відношенні R (xRy), випливає, що і у знаходиться в тому ж відношенні до х (уRx). Прикладом симетричних відносин можуть бути рівність (=), відношення еквівалентності, подібності, одночасності, деякі відносини споріднення (приміром, ставлення братства).
  • Антисиметричною ставлення - двомісне відношення R, визначене на деякій множині і відрізняється тим, що для будь-яких х и у з xRy і xR -1 y слід х = у (тобто R і R -1 виконуються одночасно лише для рівних між собою членів).
  • Асиметричне відношення [ уточнити ] - двомісне відношення R, визначене на деякій множині і відрізняється тим, що для будь-яких х и у з xRy слід \ Neg yRx. Приклад: ставлення "більше" (>) і "менше" (<).
  • Відношення еквівалентності (відношення тотожності [ уточнити ], відношення типу рівності) - двомісне відношення R між предметами х і у в предметної області D, яке задовольняє наступним аксіомам ( умовами):
    1. аксіомі рефлексивності (див. вище): xRx (предмет знаходиться у відношенні R до самого себе);
    2. аксіомі симетричності (див. вище): xRy \ To yRx (якщо предмет х перебуває у відношенні R до предмета в, то й у знаходиться у відношенні R до х);
    3. аксіомі транзитивності (див. вище): xRy & yRz \ To xRz (якщо предмет х перебуває у відношенні R до предмету у і у знаходиться у відношенні R до z, то х знаходиться у відношенні R до г).
    Таким чином, відношення типу рівності є одночасно рефлексивним, симетричним і транзитивним. Приклади: рівність, рівнопотужних двох множин, обмениваемость товарів на ринку , подобу, одночасність. Приклад відносини, що задовольняє аксіомі (3), але не задовольняє аксіомам (1) і (2): "більше".
  • Відносини порядку - відносини, що володіють лише деякими з трьох властивостей відносини еквівалентності. Зокрема, ставлення рефлексивне і Транзитивне, але несиметричне (наприклад, "не більше") утворює "нестрогий" порядок. Ставлення Транзитивне, але нерефлексивне і несиметричне (наприклад, "менше") - "строгий" порядок.
  • Функція - двомісне відношення R, визначене на деякій множині, що відрізняється тим, що кожному значенню x відносини xRy відповідає лише одне-єдине значення y. Приклад: "y батько x". Властивість функціональності відносини R записується у вигляді аксіоми: (xRy і xRz)(yz). Оскільки кожному значенню x у виразах xRy і xRz відповідає одне і те ж значення, то y і z збіжаться, виявляться одними і тими ж. Функціональне ставлення однозначно, оскільки кожному значенню x відносини xRy відповідає лише одне-єдине значення y, але не навпаки.
  • Біекція (одно-однозначне ставлення) - двомісне відношення R, визначене на деякій множині, що відрізняється тим, що в ньому кожному значенню х відповідає єдине значення у, і кожному значенню у відповідає єдине значення х. Одно-однозначне ставлення є окремим випадком однозначного ставлення.
  • Пов'язане ставлення - це двомісне відношення R, визначене на деякій множині, що відрізняється тим, що для будь-яких двох різних елементів х и у з цієї множини, одне з них знаходиться у відношенні R до іншого (тобто виконано одну з двох співвідношень: xRy або yRx). Приклад: ставлення "менше" (<).

4. Операції над відносинами

Так як відносини, задані на фіксованій парі множин A , B , Суть підмножини безлічі A \ times B , То сукупність усіх цих відносин утворює булеву алгебру щодо операцій об'єднання, перетину і доповнення відносин. Зокрема, для довільних a \ in A , b \ in B

a \, (R \ cup S) \, b \ Leftrightarrow a \, R \, b \ vee a \, S \, b,
a \, (R \ cap S) \, b \ Leftrightarrow a \, R \, b \ wedge a \, S \, b,
a \, \ overline {R} \, b \ Leftrightarrow \ neg a \, R \, b.

Часто замість об'єднання, перетину і доповнення відносин говорять про їх диз'юнкції, кон'юнкції і запереченні.

Наприклад, ({=} \ Cup {<}) = {\ leqslant} , ({=} \ Cap {<}) = \ varnothing , Тобто об'єднання відносини строгого порядку з відношенням рівності збігається з відношенням нестрого порядку, а їх перетин порожньо.

Крім перерахованих важливе значення мають ще операції звернення і множення відносин, що визначаються наступним чином.

Якщо R \ subseteq A \ times B , То зворотним відношенням називається відношення R - 1 , Визначене на парі B , A і складається з тих пар (B, a) , Для яких a \, R \, b . Наприклад, <- 1 => .

Нехай тепер R \ subseteq A \ times B , S \ subseteq B \ times C . Твором відносин R , S називається відношення RS \ subseteq A \ times C таке, що

a \, RS \, c \ Leftrightarrow \ exists b \ in B \, a \, R \, b \ wedge b \, S \, c.

Якщо R \ subseteq A \ times B , S \ subseteq C \ times D і B \ neq C , То твір відносин не визначено. Якщо ж відносини розглядати визначені на якомусь безлічі A , То такої ситуації не виникає.

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

a \ ,{<}{<} b \ Leftrightarrow a + 1 <b.

Бінарні відносини R і S називаються перестановки, якщо R S = S R . Нескладно помітити, що для будь-якого бінарного відносини R , Визначеного на A , R I A = I A R , Де символом I A позначено рівність, визначене на A . Однак рівність R R - 1 = I не завжди справедливо.

Мають місце наступні тотожності:

  • R (S T) = (R S) T ,
  • (R S) - 1 = S - 1 R - 1 ,
  • \ Overline {R ^ {-1}} = \ overline {R} ^ {-1} ,
  • (R \ cup S) ^ {-1} = R ^ {-1} \ cup S ^ {-1} ,
  • (R \ cap S) ^ {-1} = R ^ {-1} \ cap S ^ {-1} ,
  • R (S \ cup T) = RS \ cup RT ,
  • (R \ cup S) T = RT \ cup ST .

Зазначимо, що аналоги останніх двох тотожностей для \ Cap не мають місця.

Деякі властивості відносини R \ subseteq A \ times A можна визначити, використовуючи операції над відносинами:

  • Рефлексивність: I \ subseteq R ,
  • Симетричність: R ^ {-1} \ subseteq R ,
  • Транзитивність: RR \ subseteq R .

Література

  • А. І. Мальцев Алгебраїчні системи - М .: Наука, 1970.


Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Відношення еквівалентності
Симетричне відношення
Передавальне відношення
Антисиметрична відношення
Відношення (реляційна модель)
Відношення сигнал / шум
Пікове відношення сигналу до шуму
Закон зворотного відношення між змістом і обсягом поняття
© Усі права захищені
написати до нас
Рейтинг@Mail.ru