Перечислить элементы бинарного отношения. Бинарное отношение
Пусть A - множество. Если задано некоторое подмножество его декартового квадрата, другими словами, задано некоторое подмножество упорядоченных пар , где , то говорят, что на множестве A задано бинарное отношение R . Пишут или .В качестве примеров бинарных отношений на числовых множествах можно рассмотреть хорошо известные из арифметики отношения: ,=”,<”,£”,>”,³”.
Бинарное отношение называется:
Рефлексивным, если для любого
Иррефлексивным, если для любого ;
Симметричным, если из следует ;
Антисимметричным, если и следует a=b ;
Транзитивным, если из и следует ;
Отношение,=” рефлексивно, симметрично и транзитивное, отношения,<” и,>” транзитивны и иррефлексивны, отношения,£” и,³”. рефлексивны, антисимметричны и транзитивны. Последние свойства выбираются в качестве определяющих для отношения частичного порядка на множестве A .
Определение. Бинарное отношение R на множестве A называется отношением частичного порядка, если оно рефлексивно, антисимметрично и транзитивно,
Если , то будем считать элемент a предшествующим элементу b и записывать отношение aRb в виде . Если для любых двух элементов имеет место хотя бы одно из отношений или , то частичный порядок называется полным или линейным порядком.
Примером частичного порядка является система множеств, упорядоченных по включению: . Числовые множества с обычным отношением, £” дают примеры линейных порядков.
Обобщением понятия равенства является отношение эквивалентности.
Определение . Бинарное отношение R на множестве A называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.
Отношение эквивалентности разбивает множество A на непересекающиеся подмножества, называемые классами эквивалентности. Если в качестве A рассмотреть множество людей, проживающих в домах некоторого города, то отношение проживания в одном доме будет отношением эквивалентности. Более математическим примером является отношение сравнения по модулю n в множестве целых чисел Z : , если делится на n . При этом Z разбивается на классы , характеризуемые остатками от деления на n . Более общим примером является эквивалентность элементов группы G по подгруппе H : если . Классами эквивалентности здесь являются правые смежные классы по подгруппе H .
Рассмотрим отношение «уважать», определенное на множестве всех людей %%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} $$
Примеры
- Рассмотрим отношение больше больше рефлексивным? Если да, то каждое число является больше самого себя, что неверно. Поэтому отношение больше не рефлексивно.
- Рассмотрим отношение равно на множестве действительных чисел. Оно является рефлексивным , так как каждое действительное число равно самому себе.
Симметричное бинарное отношение
Бинарное отношение %%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} $$
Примеры
- Рассмотрим отношение больше на множестве действительных чисел. Является ли отношение больше симметричным? Оно не является симметричным, так как если %%a > b%%, то условие %%b > a%% не выполняется. Поэтому отношение больше не симметрично.
- Пусть %%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. $$
Определения
- 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 функция.
Определение . Бинарным отношением 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 матрицей, если:
- R 1 «иметь один и тот же остаток от деления на 5»; M 1 множество натуральных чисел.
- R 2 «быть равным»; M 2 множество натуральных чисел.
- R 3 «жить в одном городе»; M 3 множество людей.
- R 4 «быть знакомым»; M 4 множество людей.
- R 5 {(a,b):(a-b) - чётное; M 5 множество чисел {1,2,3,4,5,6,7,8,9}.
- R 6 {(a,b):(a+b) - чётное; M 6 множество чисел {1,2,3,4,5,6,7,8,9}.
- R 7 {(a,b):(a+1) - делитель (a+b)} ; M 7 - множество {1,2,3,4,5,6,7,8,9}.
- R 8 {(a,b):a - делитель (a+b),a≠1}; M 8 - множество натуральных чисел.
- R 9 «быть сестрой»; M 9 - множество людей.
- 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 .
- R рефлексивно тогда и только тогда, (далее используется знак ⇔) когда I ⊂ R.
- R симметрично ⇔ R = R -1 .
- R транзитивно ⇔ R º R ⊂ R
- R антисимметрично ⇔ R ⌒ R -1 ⊂ I .
- 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.
Бинарные отношения.
Пусть A и B – произвольные множества.
Возьмем по одному элементу из каждого множества, a из A, b из B и
запишем их так:
(сначала элемент первого множества, затем элемент второго множества – т.е. нам
важен порядок, в котором берутся элементы). Такой объект будем называть упорядоченной
парой
. Равными
будем считать только те пары, у которых элементы с
одинаковыми номерами равны. =
Декартовым произведением произвольных множеств A и B (обозначается: AB) называется множество, состоящее из всех возможных упорядоченных пар, первый элемент которых принадлежит A, а второй принадлежит B. По определению: AB = { | aA и bB}. Очевидно, что если A≠B, то AB ≠ BA. Декартово произведение множества A само на себя n раз называется декартовой степенью A (обозначается: A n).
Пример 5. Пусть A = {x, y} и B = {1, 2, 3}.
AB = {
BA = {<1, x>, <2, x>, <3, x>, <1, y>, <2, y>, <3, y>}.
AA = A 2 = {
BB = B 2 = {<1, 1>, <1, 2>, <1, 3>, <2, 1>, <2, 2>, <2, 3>, <3, 1>, <3, 2>, <3, 3>}.
Бинарным
отношением
на множестве M называется множество некоторых
упорядоченных пар элементов множества M. Если r – бинарное отношение и пара
Пример 6. Множество {<1, 2>, <2, 2>, <3, 4>, <5, 2>, <2, 4>} является бинарным отношением на множестве {1, 2, 3, 4, 5}.
Пример 7.
Отношение ³ на множестве целых чисел
является бинарным отношением. Это бесконечное множество упорядоченных пар вида
Пример 8.
Отношение равенства на множестве A является бинарным
отношением: I A = {
Поскольку бинарные отношения являются множествами, то к ним применимы операции объединения, пересечения, дополнения и разности.
Областью определения бинарного отношения r называется множество D(r) = { x | существует такое y, что xry }. Областью значений бинарного отношения r называется множество R(r) = { y | существует такое x, что xry }.
Отношением, обратным
к бинарному отношению r Í M 2 , называется бинарное отношение r -1 = {
Композицией
бинарных отношений r 1 и r 2 , заданных на множестве M, называется бинарное отношение r 2 o r 1 = {
Пример 9. Пусть бинарное отношение r
задано на множестве M = {a, b, c, d}, r = {, ,
Пусть r – бинарное отношение на множестве M. Отношение r
называется рефлексивным
, если x r x для любого x Î M. Отношение r называется симметричным
, если вместе
с каждой парой
Укажем критерии выполнения этих свойств.
Бинарное отношение r на множестве M рефлексивно тогда и только тогда, когда I M Í r.
Бинарное отношение r симметрично тогда и только тогда, когда r = r ‑1 .
Бинарное отношение r на множестве M антисимметрично тогда и только тогда, когда r Ç r ‑1 = I M .
Бинарное отношение r транзитивно тогда и только тогда, когда r o r Í r.
Пример 10. Отношение из примера 6 является антисимметричным, но не является симметричным, рефлексивным и транзитивным. Отношение из примера 7 является рефлексивным, антисимметричным и транзитивным, но не является симметричным. Отношение I A обладает всеми четырьмя рассматриваемыми свойствами. Отношения r ‑1 o r и r o r ‑1 являются симметричными, транзитивными, но не являются антисимметричными и рефлексивными.
Отношением эквивалентности на множестве M называется транзитивное, симметричное и рефлексивное на М бинарное отношение.
Отношением частичного порядка на множестве М называется транзитивное, антисимметричное и рефлексивное на М бинарное отношение r.
Пример 11. Отношение из примера 7 является отношением частичного порядка. Отношение I A является отношением эквивалентности и частичного порядка. Отношение параллельности на множестве прямых является отношением эквивалентности.