Бинарное отношение r. Бинарные отношения и их свойства. Возвращаясь к основам T-SQL

Рассмотрим отношение «уважать», определенное на множестве всех людей %%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)%%, где %%a > 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 = \big\{ (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%% антисимметрично.

Построим для каждого из них отрицание выполнения условия %%P%%.

Отрицание рефлексивности

По определению %%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 – некоторое подмножество декартова квадрата множества А: R A A .

Отношением 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 R b .

Такая фигура называется ориентированным графом (или орграфом) бинарного отношения.

Задача 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 А выполняется a R a , то есть (а , а )R. Главная диагональ матрицы рефлексивного отношения состоит из единиц. Граф рефлексивного отношения обязательно имеет петли у каждой вершины.

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

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

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

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

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

    Бинарное отношение R на множестве A называется:

    анти симметричным , если для любых a , b А из a R b и b R a следует, что a =b . То есть, если (a , b )R и(b , a )R , то отсюда вытекает, что a =b . Матрица антисимметричного отношения вдоль главной диагонали имеет все единицы и не имеет ни одной пары единиц, расположенных на симметричных местах по отношению к главной диагонали. Иными словами, все σ ii =1, и если σ ij =1, то обязательно σ ji =0. Граф антисимметричного отношения имеет петли у каждой вершины, а вершины соединяются только одной направленной дугой.

Примеры антисимметричных отношений: , ,  на множестве действительных чисел; ,  на множествах;

    а симметричным , если для любых a , b А из a R b следует невыполнение b R a , то есть если (a , b )R , то (b , a )R . Матрица асимметричного отношения вдоль главной диагонали имеет нули (σ ij =0) все и ни одной симметричной пары единиц (если σ ij =1, то обязательно σ ji =0). Граф асимметричного отношения не имеет петель, а вершины соединены одной направленной дугой.

Примеры асимметричных отношений: <, > на множестве действительных чисел, «быть отцом» на множестве людей.

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

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

    Бинарное отношение R на множестве A называется антитранзитив ным , если для любых a , b , с А из a R b и b R a следует, что не выполняется a R с . То есть если (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.Отношение на множестве слов русского языка определено следующим образом: а Rb тогда и только тогда, когда они имеют хоть одну общую букву. Определить тип отношения на множестве А = {корова, вагон, нить, топор}.

3. Указать примеры бинарных отношений на множестве А = {1, 2) и В = {1, 2, 3}, которые были бы:

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

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

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

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

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

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

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

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

Отношение, заданное на множестве, может обладать рядом свойств, а именно:

2. Рефлексивность

Определение. Отношение R намножестве Х называется рефлексивным, если каждый элемент х множества Х находится в отношении R с самим собой.

Используя символы, это отношение можно записать в таком виде:

R рефлексивно на Х Û("х Î Х ) х R х

Пример. Отношение равенства на множестве отрезков рефлексивно, т.к. каждый отрезок равен себе самому.

Граф рефлексивного отношения во всех вершинах имеет петли.

2. Антирефлексивность

Определение. Отношение R намножестве Х называется антирефлексивным, если ни один элемент х множества Х не находится в отношении R с самим собой.

R антирефлексивно на Х Û("х Î Х )

Пример. Отношение «прямая х перпендикулярна прямой у » на множестве прямых плоскости антирефлексивно, т.к. ни одна прямая плоскости не перпендикулярна самой себе.

Граф антирефлексивного отношения не содержит ни одной петли.

Заметим, что существуют отношения, не являющиеся ни рефлексивными, ни антирефлексивными. Например, рассмотрим отношение «точка х симметрична точке у » на множестве точек плоскости.

Точка х симметрична точке х – истинно; точка у симметрична точке у – ложно, следовательно, мы не можем утверждать, что все точки плоскости симметричны сами себе, также мы не можем и утверждать, что ни одна точка плоскости не симметрична сама себе.

3. Симметричность

Определение . Отношение R намножестве Х называется симметричным, если из того, что элемент х находится в отношении R с элементом у , следует, что и элемент у находится в отношении R с элементом х .

R симметричнона Х Û("х , у Î Х ) х R у Þ у R х

Пример. Отношение «прямая х пересекает прямую у на множестве прямых плоскости» симметрично, т.к. если прямая х пересекает прямую у , то и прямая у обязательно будет пересекать прямую х .

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

4. Асимметричность

Определение . Отношение R намножестве Х называется асимметричным, если ни для каких элементов х , у из множества Х не может случиться, что элемент х находится в отношении R с элементом у и элемент у находится в отношении R с элементом х .

R асимметричнона Х Û("х , у Î Х ) х R у Þ

Пример. Отношение «х < у » асимметрично, т.к. ни для какой пары элементов х , у нельзя сказать, что одновременно х < у и у < х .

Граф асимметричного отношения не имеет петель и если две вершины графа соединены стрелкой, то эта стрелка только одна.

5. Антисимметричность

Определение . Отношение R намножестве Х называется антисимметричным, если из того что х находится в отношении с у , а у находится в отношении с х следует, что х = у.

R антисимметричнона Х Û("х , у Î Х ) х R у Ù у R х Þ х = у

Пример. Отношение «х £ у » антисимметрично, т.к. условия х £ у и у £ х одновременно выполняются только тогда, когда х = у.

Граф антисимметричного отношения имеет петли и если две вершины графа соединены стрелкой, то эта стрелка только одна.

6. Транзитивность

Определение . Отношение R намножестве Х называется транзитивным, если для любых элементов х , у , z из множества Х из того, что х находится в отношении с у , а у находится в отношении с z следует, что х находится в отношении с z.

R транзитивнона Х Û("х , у , z Î Х ) х R у Ù у R z Þ х R z

Пример. Отношение «х кратно у » транзитивно, т.к. если первое число кратно второму, а второе кратно третьему, то первое число будет кратно третьему.

Граф транзитивного отношения с каждой парой стрелок от х к у и от у к z содержит стрелку, идущую от х к z.

7. Связность

Определение . Отношение R намножестве Х называется связным, если для любых элементов х , у из множества Х х находится в отношении с у или у находится в отношении с х или х = у .

R связнона Х Û("х , у , z Î Х ) х R у Ú у R z Ú х = у

Другими словами: отношение R намножестве Х называется связным, если для любых различных элементов х , у из множества Х х находится в отношении с у или у находится в отношении с х или х = у .

Пример. Отношение «х < у » связно, т.к. какие бы мы действительные числа не взяли, обязательно одно из них будет больше другого или они равны.

На графе связного отношения все вершины соединены между собой стрелками.

Пример. Проверить, какими свойствами обладает

отношение «х – делитель у », заданное на множестве

Х = {2; 3; 4; 6; 8}.

1) данное отношение рефлексивно, т.к. каждое число из данного множества является делителем самого себя;

2) свойством антирефлексивности данное отношение не обладает;

3) свойство симметричности не выполняется, т.к. например, 2 является делителем числа 4, но 4 делителем числа 2 не является;

4) данное отношение антисимметрично: два числа могут быть одновременно делителями друг друга только в том случае, если эти числа равны;

5) отношение транзитивно, т.к. если одно число является делителем второго, а второе – делителем третьего, то первое число обязательно будет делителем третьего;

6) отношение свойством связности не обладает, т.к. например, числа 2 и 3 на графе стрелкой не соединены, т.к. два различных числа 2 и 3 делителями друг друга не являются.

Таким образом, данное отношение обладает свойствами рефлексивности, асимметричности и транзитивности.

§ 3. Отношение эквивалентности.
Связь отношения эквивалентности с разбиением множества на классы

Определение. Отношение R на множестве Х называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

Пример. Рассмотрим отношение «х однокурсник у » на множестве студентов педфака. Оно обладает свойствами:

1) рефлексивности, т.к. каждый студент является однокурсником самому себе;

2) симметричности, т.к. если студент х у , то и студент у является однокурсником студента х ;

3) транзитивности, т.к. если студент х - однокурсник у , а студент у – однокурсник z , то студент х будет однокурсником студента z .

Таким образом, данное отношение обладает свойствами рефлексивности, симметричности и транзитивности, а значит, является отношением эквивалентности. При этом множество студентов педфака можно разбить на подмножества, состоящие из студентов, обучающихся на одном курсе. Получаем 5 подмножеств.

Отношением эквивалентности являются также, например, отношение параллельности прямых, отношение равенства фигур. Каждое такое отношение связано с разбиением множества на классы.

Теорема. Если на множестве Х задано отношение эквивалентности, то оно разбивает это множество на попарно непересекающиеся подмножества (классы эквивалентности).

Верно и обратное утверждение: если какое-либо отношение, заданное на множестве Х , порождает разбиение этого множества на классы, то оно является отношением эквивалентности.

Пример. На множестве Х = {1; 2; 3; 4; 5; 6; 7; 8} задано отношение «иметь один и тот же остаток при делении на 3». Является ли оно отношением эквивалентности?

Построим граф данного отношения:


Данное отношение обладает свойствами рефлексивности, симметричности и транзитивности, следовательно, является отношение эквивалентности и разбивает множество Х на классыэквивалентности. В каждом классе эквивалентности будут числа, которые при делении на 3 дают один и тот же остаток: Х 1 = {3; 6}, Х 2 = {1; 4; 7}, Х 3 = {2; 5; 8}.

Считают, что класс эквивалентности определяется любым своим представителем, т.е. произвольным элементом этого класса. Так, класс равных дробей можно задать, указав любую дробь, принадлежащую этому классу.

В начальном курсе математики также встречаются отношения эквивалентности, например, «выражения х и у имеют одинаковые числовые значения», «фигура х равна фигуре у ».

Определение . Бинарным отношением R называется подмножество пар (a,b)∈R декартова произведения A×B, т. е. R⊆A×B . При этом множество A называют областью определения отношения R, множество B – областью значений.

Обозначение: aRb (т. е. a и b находятся в отношении R). /

Замечание : если A = B , то говорят, что R есть отношение на множестве A .

Способы задания бинарных отношений

1. Списком (перечислением пар), для которых это отношение выполняется.

2. Матрицей. Бинарному отношению R ∈ A × A , где A = (a 1 , a 2 ,..., a n), соответствует квадратная матрица порядка n , в которой элемент c ij , стоящий на пересечении i-й строки и j-го столбца, равен 1, если между a i и a j имеет место отношение R , или 0, если оно отсутствует:

Свойства отношений

Пусть R – отношение на множестве A, R ∈ A×A . Тогда отношение R:

    рефлексивно, если Ɐ a ∈ A: a R a (главная диагональ матрицы рефлексивного отношения содержит только единицы);

    антирефлексивно, если Ɐ a ∈ A: a R a (главная диагональ матрицы рефле сивного отношения содержит только нули);

    симметрично, если Ɐ a , b ∈ A: a R b ⇒ b R a (матрица такого отношения симметрична относительно главной диагонали, т.е. c ij c ji);

    антисимметрично, если Ɐ a, b ∈ A: a R b & b R a ⇒ a = b (в матрице такого отношения отсутствуют единицы, симметричные относительно главной диагонали);

    транзитивно, если Ɐ a, b, c ∈ A: a R b & b R c ⇒ a R c (в матрице такого отношения должно выполняться условие: если в i-й строке стоит единица, например в j-ой координате (столбце) строки, т. е. c ij = 1 , то всем единицам в j-ой строке (пусть этим единицам соответствуют k е координаты такие, что, c jk = 1) должны соответствовать единицы в i-й строке в тех же k-х координатах, т. е. c ik = 1 (и, может быть, ещё и в других координатах).

Задача 3.1. Определите свойства отношения R – «быть делителем», заданного на множестве натуральных чисел.

Решение.

отношение R = {(a,b):a делитель b}:

    рефлексивно, не антирефлексивно, так как любое число делит само себя без остатка: a/a = 1 для всех a∈N ;

    не симметрично, антисимметрично, например, 2 делитель 4, но 4 не является делителем 2;

    транзитивно,таккакесли b/a ∈ N и c/b ∈ N, то c/a = b/a ⋅ c/b ∈ N, например, если 6/3 = 2∈N и 18/6 = 3∈N, то 18/3 = 18/6⋅6/3 = 6∈N.

Задача 3.2. Определите свойства отношения R – «быть братом», заданного на множестве людей.
Решение.

Отношение R = {(a,b):a - брат b}:

    не рефлексивно, антирефлексивно из-за очевидного отсутствия aRa для всех a;

    не симметрично, так как в общем случае между братом a и сестрой b имеет место aRb , но не bRa ;

    не антисимметрично, так как если a и b –братья, то aRb и bRa, но a≠b;

    транзитивно, если называть братьями людей, имеющих общих родителей (отца и мать).

Задача 3.3. Определите свойства отношения R – «быть начальником», заданного на множестве элементов структуры

Решение.

Отношение R = {(a,b) : a - начальник b}:

  • не рефлексивно, антирефлексивно, если в конкретной интерпретации не имеет смысла;
  • не симметрично, антисимметрично, так как для всех a≠b не выполняется одновременно aRb и bRa;
  • транзитивно, так как если a начальник b и b начальник c , то a начальник c .

Определите свойства отношения R i , заданного на множестве M i матрицей, если:

  1. R 1 «иметь один и тот же остаток от деления на 5»; M 1 множество натуральных чисел.
  2. R 2 «быть равным»; M 2 множество натуральных чисел.
  3. R 3 «жить в одном городе»; M 3 множество людей.
  4. R 4 «быть знакомым»; M 4 множество людей.
  5. R 5 {(a,b):(a-b) - чётное; M 5 множество чисел {1,2,3,4,5,6,7,8,9}.
  6. R 6 {(a,b):(a+b) - чётное; M 6 множество чисел {1,2,3,4,5,6,7,8,9}.
  7. R 7 {(a,b):(a+1) - делитель (a+b)} ; M 7 - множество {1,2,3,4,5,6,7,8,9}.
  8. R 8 {(a,b):a - делитель (a+b),a≠1}; M 8 - множество натуральных чисел.
  9. R 9 «быть сестрой»; M 9 - множество людей.
  10. R 10 «быть дочерью»; M 10 - множество людей.

Операции над бинарными отношениями

Пусть R 1 , R 1 есть отношения, заданные на множестве A .

    объединение R 1 ∪ R 2: R 1 ∪ R 2 = {(a,b) : (a,b) ∈ R 1 или (a,b) ∈ R 2 } ;

    пересечение R 1 ∩ R 2: R 1 ∩ R 2 = {(a,b) : (a,b) ∈ R 1 и (a,b) ∈ R 2 } ;

    разность R 1 \ R 2: R 1 \ R 2 = {(a,b) : (a,b) ∈ R 1 и (a,b) ∉ R 2 } ;

    универсальное отношение U: = {(a;b)/a ∈ A & b ∈ A}. ;

    дополнение R 1 U \ R 1 , где U = A × A;

    тождественное отношение I: = {(a;a) / a ∈ A};

    обратное отношение R -11 : R -11 = {(a,b) : (b,a) ∈ R 1 };

    композиция R 1 º R 2: R 1 º R 2: = {(a,b) / a ∈ A&b ∈ B& ∃ c ∈ C: aR 1 c & c R 2 b}, где R 1 ⊂ A × C и R 2 ⊂ C × B;

Определение. Степенью отношения R на множестве A называется его композиция с самим собой.

Обозначение:

Определение . Если R ⊂ A × B , то R º R -1 называется ядром отношения R .

Теорема 3.1. Пусть R ⊂ A × A – отношение, заданное на множестве A .

  1. R рефлексивно тогда и только тогда, (далее используется знак ⇔) когда I ⊂ R.
  2. R симметрично ⇔ R = R -1 .
  3. R транзитивно ⇔ R º R ⊂ R
  4. R антисимметрично ⇔ R ⌒ R -1 ⊂ I .
  5. R антирефлексивно ⇔ R ⌒ I = ∅ .

Задача 3.4 . Пусть R - отношение между множествами {1,2,3} и {1,2,3,4}, заданное перечислением пар: R = {(1,1), (2,3), (2,4), (3,1), (3,4)}. Кроме того, S - отношение между множествами S = {(1,1), (1,2), (2,1), (3,1), (4,2)}. Вычислите R -1 , S -1 и S º R. Проверьте, что (S º R) -1 = R -1 , S -1 .

Решение.
R -1 = {(1,1), (1,3), (3,2), (4,2), (4,3)};
S -1 = {(1,1), (1,2), (1,3), (2,1), (2,4)};
S º R = {(1,1), (1,2), (2,1), (2,2), (3,1), (3,2)};
(S º R) -1 = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3)};
R -1 º S -1 = {(1,1), (1,2), (1,3), (2 ,1), (2,2), (2,3)} = (S º R) -1 .

Задача 3.5 . Пусть R отношение «...родитель...», а S отношение «...брат...» на множестве всех людей. Дайте краткое словесное описание отношениям:

R -1 , S -1 , R º S, S -1 º R -1 и R º R.

Решение.

R -1 - отношение«...ребёнок...»;

S -1 - отношение«...брат или сестра...»;

R º S - отношение «...родитель...»;

S -1 º R -1 - отношение «...ребёнок...»

R º R - отношение «...бабушка или дедушка...»

Задачи для самостоятельного решения

1) Пусть R - отношение «...отец...», а S - отношение «...сестра...» на множестве всех людей. Дайте словесное описание отношениям:

R -1 , S -1 , R º S, S -1 º R -1 , R º R.

2) Пусть R - отношение «...брат...», а S - отношение «...мать...» на множестве всех людей. Дайте словесное описание отношениям:

R -1 , S -1 , S º R, R -1 º S -1 , S º S.

3) Пусть R - отношение «...дед...», а S - отношение «...сын...» на множестве всех людей. Дайте словесное описание отношениям:

4) Пусть R - отношение «...дочь...», а S - отношение «...бабушка...» на множе- стве всех людей. Дайте словесное описание отношениям:

5) Пусть R - отношение «...племянница...», а S - отношение «...отец...» на множестве всех людей. Дайте словесное описание отношениям:

R -1 , S -1 , S º R, R -1 º S -1 , R º R.

6) Пусть R - отношение «сестра...», а S - отношение «мать...» на множестве всех людей. Дайте словесное описание отношениям:

R -1 , S -1 , R º S, S -1 º R -1 , S º S.

7) Пусть R - отношение «...мать...», а S - отношение «...сестра...» на множе- стве всех людей. Дайте словесное описание отношениям:

R -1 , S1, R º S, S1 º R1, S º S.

8) Пусть R - отношение «...сын...», а S - отношение «...дед...» на множестве всех людей. Дайте словесное описание отношениям:

R -1 , S -1 , S º R, R -1 º S -1 , R º R.

9) Пусть R - отношение «...сестра...», а S - отношение «...отец...» на множе- стве всех людей. Дайте словесное описание отношениям:

R -1 , S -1 , R º S, S -1 º R -1 , S º S.

10) Пусть R - отношение «...мать...», а S - отношение «...брат...» на множестве всех людей. Дайте словесное описание отношениям:

R -1 , S -1 , S º R, R -1 º S -1 , R º R.

Определения

  • 1. Бинарным отношением между элементами множеств А и В называется любое подмножество декартова произведения RAB, RAА.
  • 2. Если А=В, то R - это бинарное отношение на A.
  • 3. Обозначение: (x, y)R xRy.
  • 4. Область определения бинарного отношения R - это множество R = {x: существует y такое, что (x, y)R}.
  • 5. Область значений бинарного отношения R - это множество R = {y: существует x такое, что (x, y)R}.
  • 6. Дополнение бинарного отношения R между элементами А и В - это множество R = (AB) R.
  • 7. Обратное отношение для бинарного отношения R - это множество R1 = {(y, x) : (x, y)R}.
  • 8. Произведение отношений R1AB и R2BC - это отношение R1 R2 = {(x, y) : существует zB такое, что (x, z)R1 и (z, y)R2}.
  • 9. Отношение f называется функцией из А в В, если выполняется два условия:
    • а) f = А, f В
    • б) для всех x, y1, y2 из того, что (x, y1)f и (x, y2)f следует y1=y2.
  • 10. Отношение f называется функцией из А на В, если в первом пункте будет выполняться f = А, f = В.
  • 11. Обозначение: (x, y)f y = f(x).
  • 12. Тождественная функция iA: AA определяется так: iA(x) = x.
  • 13. Функция f называется 1-1-функцией, если для любых x1, x2, y из того, что y = f(x1) и y = f(x2) следует x1=x2.
  • 14. Функция f: AB осуществляет взаимно однозначное соответствие между А и В, если f = А, f = В и f является 1-1-функцией.
  • 15. Свойства бинарного отношения R на множестве А:
    • - рефлексивность: (x, x)R для всех xA.
    • - иррефлексивность: (x, x)R для всех xA.
    • - симметричность: (x, y)R (y, x)R.
    • - антисимметричность: (x, y)R и (y, x)R x=y.
    • - транзитивность: (x, y)R и (y, z)R (x, z)R.
    • - дихотомия: либо (x, y)R, либо (y, x)R для всех xA и yA.
  • 16. Множества А1, A2, ..., Аr из Р(А) образуют разбиение множества А, если
  • - Аi , i = 1, ..., r,
  • - A = A1A2...Ar,
  • - AiAj = , i j.

Подмножества Аi , i = 1, ..., r, называются блоками разбиения.

  • 17. Эквивалентность на множестве А - это рефлексивное, транзитивное и симметричное отношение на А.
  • 18. Класс эквивалентности элемента x по эквивалентности R - это множество [x]R={y: (x, y)R}.
  • 19. Фактор множество A по R - это множество классов эквивалентности элементов множества А. Обозначение: A/R.
  • 20. Классы эквивалентности (элементы фактор множества А/R) образуют разбиение множества А. Обратно. Любому разбиению множества А соответствует отношение эквивалентности R, классы эквивалентности которого совпадают с блоками указанного разбиения. По-другому. Каждый элемент множества А попадает в некоторый класс эквивалентности из A/R. Классы эквивалентности либо не пересекаются, либо совпадают.
  • 21. Предпорядок на множестве A - это рефлексивное и транзитивное отношение на А.
  • 22. Частичный порядок на множестве A - это рефлексивное, транзитивное и антисимметричное отношение на А.
  • 23. Линейный порядок на множестве A - это рефлексивное, транзитивное и антисимметричное отношение на А, удовлетворяющее свойству дихотомии.

Пусть A={1, 2, 3}, B={a, b}. Выпишем декартово произведение: AB = { (1, a), (1, b), (2, a), (2, b), (3, a), (3, b) }. Возьмём любое подмножество этого декартова произведения: R = { (1, a), (1, b), (2, b) }. Тогда R - это бинарное отношение на множествах A и B.

Будет ли это отношение являться функцией? Проверим выполнение двух условий 9a) и 9б). Область определения отношения R - это множество R = {1, 2} {1, 2, 3}, то есть первое условие не выполняется, поэтому в R нужно добавить одну из пар: (3, a) или (3, b). Если добавить обе пары, то не будет выполняться второе условие, так как ab. По этой же причине из R нужно выбросить одну из пар: (1, a) или (1, b). Таким образом, отношение R = { (1, a), (2, b), (3, b) } является функцией. Заметим, что R не является 1-1 функцией.

На заданных множествах A и В функциями также будут являться следующие отношения: { (1, a), (2, a), (3, a) }, { (1, a), (2, a), (3, b) }, { (1, b), (2, b), (3, b) } и т.д.

Пусть A={1, 2, 3}. Примером отношения на множестве A является R = { (1, 1), (2, 1), (2, 3) }. Примером функции на множестве A является f = { (1, 1), (2, 1), (3, 3) }.

Примеры решения задач

1. Найти R, R, R1, RR, RR1, R1R для R = {(x, y) | x, y D и x+y0}.

Если (x, y)R, то x и y пробегают все действительные числа. Поэтому R = R = D.

Если (x, y)R, то x+y0, значит y+x0 и (y, x)R. Поэтому R1=R.

Для любых xD, yD возьмём z=-|max(x, y)|-1, тогда x+z0 и z+y0, т.е. (x, z)R и (z, y)R. Поэтому RR = RR1 = R1R = D2.

2. Для каких бинарных отношений R справедливо R1= R?

Пусть RAB. Возможны два случая:

  • (1) AB. Возьмём xAB. Тогда (x, x)R (x, x)R1 (x, x)R (x, x)(AB) R (x, x)R. Противоречие.
  • (2) AB=. Так как R1BA, а RAB, то R1= R= . Из R1 = следует, что R = . Из R = следует, что R=AB. Противоречие.

Поэтому если A и B, то таких отношений R не существует.

3. На множестве D действительных чисел определим отношение R следующим образом: (x, y)R (x-y) - рациональное число. Доказать, что R есть эквивалентность.

Рефлексивность:

Для любого xD x-x=0 - рациональное число. Потому (x, x)R.

Симметричность:

Если (x, y)R, то x-y = . Тогда y-x=-(x-y)=- - рациональное число. Поэтому (y, x)R.

Транзитивность:

Если (x, y)R, (y, z)R, то x-y = и y-z =. Складывая эти два уравнения, получаем, что x-z = + - рациональное число. Поэтому (x, z)R.

Следовательно, R - это эквивалентность.

4. Разбиение плоскости D2 состоит из блоков, изображённых на рисунке а). Выписать отношение эквивалентности R, соответствующее этому разбиению, и классы эквивалентности.

Аналогичная задача для b) и c).


а) две точки эквивалентны, если лежат на прямой вида y=2x+b, где b - любое действительное число.

b) две точки (x1,y1) и (x2,y2) эквивалентны, если (целая часть x1 равна целой части x2) и (целая часть y1 равна целой части y2).

с) решить самостоятельно.

Задачи для самостоятельного решения

  • 1. Доказать, что если f есть функция из A в B и g есть функция из B в C, то fg есть функция из A в C.
  • 2. Пусть A и B - конечные множества, состоящие из m и n элементов соответственно.

Сколько существует бинарных отношений между элементами множеств A и B?

Сколько имеется функций из A в B?

Сколько имеется 1-1 функций из A в B?

При каких m и n существует взаимно-однозначное соответствие между A и B?

3. Доказать, что f удовлетворяет условию f(AB)=f(A)f(B) для любых A и B тогда и только тогда, когда f есть 1-1 функция.

Похожие статьи