Бинарные отношения. Понятие отношения на множестве Основы дискретной математики

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

Бинарные отношения на множестве

Пусть дано множество А. Связь элементов хну множества А моделируется парой (ду>). Если элемент х связан с у, значит, мы имеем пару (л:,у) в качестве элемента некоторого множества; если д; не связан с у , значит, пара (л:^) не является объектом множества. Итак, имеем следующее определение.

Бинарным отношением на множестве А называется произвольное множество пар элементов из А.

Другими словами, бинарное отношение на множестве А - ото подмножество прямого произведения АхА=А 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.»

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

Определения

  • 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 функция.

Декартовым произведением двух множеств X и Y называется множество всех упорядоченных пар (x , y ) таких, что
, а
.

Пример 1 . Пусть .

Тогда , .

Очевидно, что
, т.е. операция декартова произведения множеств не является коммутативной.

Декартовым произведением множеств
называется множество
всех упорядоченных наборов
таких, чтоЕсли
, то декартово произведение обозначают
.

Будем говорить, что задано соответствие q между множествами X и Y , если задана упорядоченная тройка
, где
.Множество X называется областью отправления, а Y – областью прибытия соответствия q (обозначают
). Каждый элементy в паре
называется образом элементаx (x – прообразом элемента y ) при данном соответствии q .

Соответствие
называетсяотображением множества X во множество Y , если каждый элемент
имеет образ
, т.е..

Отображение
называетсяфункциональным , если каждый элемент
имеетединственный образ
:. Множество образов при данном отображении
обозначается
:.

Если множество
совпадает с множествомY , то говорят, что
осуществляет отображениена множество Y .

Соответствие
называетсявзаимно однозначным (биекцией) , если а) является отображением; б) функционально; в) отображает X «на» множество Y ; г) из условия
следует
.

Другими словами,
является биекцией, если каждый элемент
имеет единственный образ
, а каждый элемент
имеет единственный прообраз
при данном отображении:

(1.2)

1.2.2 Определение бинарного отношения

Определение. Говорят, что на множестве X задано бинарное отношение R , если задано подмножество декартова произведения
(т.е.
).

Пример 2 . Пусть
Зададим наХ следующие отношения:

–отношение равенства;

–отношение предшествования;

делится на – отношение делимости.

Все эти отношения заданы с помощью характеристического свойства. Ниже перечислены элементы этих отношений:

Тот факт, что пара (x , y ) принадлежит данному отношению R , будем записывать:
или xRy . Например, для отношения Q запись 4Q 2 означает, что 4 делится на 2 нацело, т.е.

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

Так, для отношения Р из примера 2 областью определения является множество
, а областью значений –
.

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

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

График отношения изображается в декартовой системе координат; на горизонтальной оси отмечается область определения, на вертикальной – множество значений отношения; элементу отношения (х,у ) соответствует точка плоскости с этими координатами. На рис. 1.7,а) приведен график отношения Q примера 2.

Схема отношения изображается с помощью двух вертикальных прямых, левая из которых соответствует области определения отношения, а правая – множеству значений отношения. Если элемент (х,у ) принадлежит отношению R , то соответствующие точки из
и
соединяются отрезком прямой. На рис. 1.7,б) приведена схема отношения Q из примера 2.

Граф отношения
строится следующим образом. На плоскости в произвольном порядке изображаются точки – элементы множестваХ . Пара точек х и у соединяется дугой (линией со стрелкой) тогда и только тогда, когда пара (х,у ) принадлежит отношению R . На рис. 1.8,а) приведен граф отношения Q примера 2.

Пусть
. Матрица отношения
имеет n строк и n столбцов, а ее элемент определяется по правилу:

На рис.1.8,б) приведена матрица отношения Q примера 2.

Определение . Бинарным отношением 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.

Бинарные отношения.

Пусть A и B – произвольные множества. Возьмем по одному элементу из каждого множества, a из A, b из B и запишем их так: (сначала элемент первого множества, затем элемент второго множества – т.е. нам важен порядок, в котором берутся элементы). Такой объект будем называть упорядоченной парой . Равными будем считать только те пары, у которых элементы с одинаковыми номерами равны. = , если a = c и b = d. Очевидно, что если a ≠ 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 – бинарное отношение и пара принадлежит этому отношению, то пишут: r или x r y. Очевидно, r Í M 2 .

Пример 6. Множество {<1, 2>, <2, 2>, <3, 4>, <5, 2>, <2, 4>} является бинарным отношением на множестве {1, 2, 3, 4, 5}.

Пример 7. Отношение ³ на множестве целых чисел является бинарным отношением. Это бесконечное множество упорядоченных пар вида , где x ³ y, x и y – целые числа. Этому отношению принадлежат, например, пары <5, 3>, <2, 2>, <324, -23> и не принадлежат пары <5, 7>, <-3, 2>.

Пример 8. Отношение равенства на множестве A является бинарным отношением: I A = { | x Î A}. I A называется диагональю множества A.

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

Областью определения бинарного отношения r называется множество D(r) = { x | существует такое y, что xry }. Областью значений бинарного отношения r называется множество R(r) = { y | существует такое x, что xry }.

Отношением, обратным к бинарному отношению r Í M 2 , называется бинарное отношение r -1 = { | Î r}. Очевидно, что D(r ‑1) = R(r), R(r ‑1) = D(r), r ‑ 1 Í M 2 .

Композицией бинарных отношений r 1 и r 2 , заданных на множестве M, называется бинарное отношение r 2 o r 1 = { | существует y такое, что Î r 1 и Í r 2 }. Очевидно, что r 2 o r 1 Í M 2 .

Пример 9. Пусть бинарное отношение r задано на множестве M = {a, b, c, d}, r = {, , , }. Тогда D(r) = {a, c}, R(r) = {b, c, d}, r ‑1 = {, , , }, r o r = {, , , }, r ‑1 o r = {, , , }, r o r ‑1 = {, , , , , , }.

Пусть r – бинарное отношение на множестве M. Отношение r называется рефлексивным , если x r x для любого x Î M. Отношение r называется симметричным , если вместе с каждой парой оно содержит и пару . Отношение r называется транзитивным , если из того, что x r y и y r z следует, что x r z. Отношение r называется антисимметричным , если оно не содержит одновременно пары и различных элементов x ¹ y множества M.

Укажем критерии выполнения этих свойств.

Бинарное отношение 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 является отношением эквивалентности и частичного порядка. Отношение параллельности на множестве прямых является отношением эквивалентности.