Текст книги "Дискретная математика. Краткий курс. Учебное пособие"

2.4. Представление отношений

Как и множества, отношения можно изображать графически. Самый известный пример отношений дают уравнения. Рассмотрим отношение Р на множестве вещественных чисел R, т. е. Р является подмножеством множества R × R. Поскольку R2 представляет собой множество точек плоскости, то можно выразить Р через те точки плоскости, которые принадлежат Р. Обычно отношение Р состоит из всех пар вещественных чисел, которые обращают уравнение в ноль. Рассмотрим следующий пример.

Пример 2.5

Пусть имеется отношение Р, определяемое уравнением

2 x + y = 4.

Р содержит все пары (x, y), которые удовлетворяют уравнению. Графиком этого уравнения является прямая (рис. 2.2).

Рис. 2.2

Представление отношений для конечных множеств

Пусть А и В два конечных множества. Отношение R между этими множествами можно представить:

1) в виде прямоугольной матрицы из 0 и 1 – строки матрицы размечены элементами из А, а столбцы – элементами из В:

2) в виде двух непересекающихся дисков – один для множества А и другой для В. Если имеется отношение из А в В, то стрелка направлена от a к b, если (a, b) ∈ R.

Например, если A = {a1, a2, a3}, B = {b1, b2, b3, b4} и R = {(a1, b2), (a1, b4), (a2, b3), (a3, b4)}, то матрица отношений и стрелочная диаграмма для R показаны на рис. 2.3.

Рис. 2.3

Представление отношения в виде ориентированного графа

Имеется еще один способ представления отношений. Он используется, когда имеется отношение R для некоторого конечного множества А с самим собой. Пусть на множестве А = (1, 2, 3, 4, 5} имеется отношение

R = {(1, 2), (2, 3), (3, 1), (3, 3), (3, 4), (4, 5), (5, 2), (5, 4)}.

Поставим в соответствие каждому элементу множества А вершину графа, а каждой паре отношения – ориентированное ребро (дугу), при этом стрелка направлена от вершины, соответствующей первой паре, к вершине второй пары (рис. 2.4).

Рис. 2.4

2.5. Композиция отношений

Пусть имеются множества А, В и С, и пусть R отношение из А в В, а S отношение из В в С. Тогда R будет подмножеством А × В и S будет подмножеством В × С. Отношения R и S позволяют построить новое отношение из А в С, которое обозначается R ○ S и которое определяется как

а(R ○ S)с, если для некоторого b ∈ B выполняется аRb и bSc.

Другими словами,

R ○ S = {(a, c): когда существует b ∈ B, для которого (a, b) ∈ R и (b, c) ∈ S}.

Отношение R ○ S называется композициейR и S (или составным отношением). Иногда композиция обозначается просто RS.

Допустим, что R является отношением на множестве А, т. е. R является отношением из множества А в себя. Тогда R ○ R представляет композицию R с самим собой и иногда обозначается R2. Подобным же образом R3 = R2 ○ R = R ○ R ○ R и так далее для любого положительного n.

Из записи отношений R и S следует, что они применяются слева направо, сначала применяется R и затем S, однако иногда имеется в виду обратный порядок

Пример 2.6. Пусть А = {a1, a2, a3, a4}, B = {b1, b2, b3, b4}, C = = {c1, c2, c3} и пусть

R = {(a1, b1), (a2, b3), (a2, b4), (a3, b2), (a4, b4)} и S = {(b1, c1), (b2, c3), (b3, c2), (b4, c2)}.

Рассмотрим стрелочную диаграмму.

На этой диаграмме имеется стрелка из a1 в b1 и затем из b1 в с1, т. е. имеется путь, который соединяет элемент a1 ∈ А с элементом с1 ∈ С. Другими словами,

a1(R ○ S)с1, поскольку a1Rb1 и b1Sс1.

Кроме этого, есть путь из a2 в с2, путь из a3 в с3 и путь из a4 в c2. Никаких других элементов из А, соединенных с С, нет и поэтому

R ○ S = {((a1, с1), (a2, с2), (a3,с3), (a4,c2)}.

Композиция отношений и матрицы

Если имеются отношения R и S, тогда композицию R ○ S можно найти с помощью матриц. Обозначим через MR и MS матрицы отношений R и S соответственно.

Умножая матрицу MR на матрицу MS, мы получим матрицу M = MRMS, определяющую отношение R ○ S:

Все ненулевые элементы матрицы M определяют отношение R ○ S (можно просто заменить ненулевые элементы на 1 и получится матрица отношения R ○ S).

Композиция отношений ассоциативна (как ассоциативно и умножение матриц).

Теорема 2.1. Пусть A, B, C, D – некоторые множества, и пусть R отношение из А в В, S отношение из В в С и Т отношение из С в D. Тогда

(R ○ S) ○ T = R ○ (S ○ T).

Необходимо показать, что каждый элемент (каждая пара) отношения (R ○ S) ○ T принадлежит также и отношению R ○ (S ○ T). Возьмем пару (a, d) ∈ (R ○ S) ○ T. Тогда существует с в множестве С, что (a, c) ∈ R ○ S, и при этом (c, d) ∈ T, а так как (a, c) ∈ R ○ S, то существует и b в В, что (a, b) R и (b, c) ∈ S.

Поскольку (b, c) ∈ S и (c, d) ∈ T, то мы имеем (b, d)∈ S ○ T, а так как (a, b) ∈ R и (b, d) ∈ S ○ T, то тогда (a, d) ∈ R ○ (S ○ T). Поэтому (R ○ S) ○ T ⊆ R ○ (S ○ T). Аналогично можно показать и обратное включение R ○ (S ○ T) ⊆ (R ○ S) ○ T.

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

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

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

Отношение R на множестве А является рефлексивным, если пара (a, a) ∈ R для каждого a ∈ A, или aRa для каждого a ∈ A. Отношение R не рефлексивно, если существует элемент a ∈ A, такой что (a, a) ∉ R.

Пример 2.7. Пусть на множестве А = {1, 2, 3, 4, 5} имеются следующие отношения:

R1 = { (1, 1), (2, 1), (2, 2), (3, 4), (4, 5)},

R2 = {1, 1), (1, 2), (2, 2)},

R3 = {(1, 1), (1, 2), (2, 2), (3, 3), (4, 4), (4, 5), (5, 5)},

R4 = Ø (пустое отношение),

R5 = A × A = U (универсальное отношение).

Определить, какие из этих отношений рефлексивны.

Рефлексивны только отношения R3 и R5, поскольку только они содержат все пять пар (1, 1), (2, 2), (3, 3), (4, 4), (5, 5). Пять, потому что в множестве А пять элементов.

Пример 2.8. Пусть имеются следующие отношения:

(а) отношение ≤ (меньше или равно) на множестве Z целых чисел,

(b) отношение = (равно) на множестве целых чисел,

(c) отношение

 (перпендикулярно) на множестве прямых на плоскости,

(d) отношение делимости │ на множестве натуральных чисел N (a│b означает, что a делит b, т. е. существует такое натуральное x, что ax = b).

Определить, какие из этих отношений рефлексивны.

Отношение (c) не рефлексивно, поскольку прямая на плоскости неперпендикулярна сама себе. Остальные отношения рефлексивны.

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

Отношение R на множестве А является симметричным, если для каждой пары (a, b) ∈ R имеется пара (b, а) ∈ R, т. е. всякий раз, когда выполняется aRb, выполняется и bRа. Отношение R не симметрично, если существуют a∈А и b∈В, такие что (a, b) ∈ R, но (b, а) ∉ R.

Пример 2.9. Пусть А = {1, 2, 3} и отношения R представлены следующими орграфами (рис. 2.6 и 2.7). Симметричны ли эти отношения?

Рис. 2.6

Рис. 2.7

Отношение R1 на рис. 2.6 симметрично, а отношение R2 на рис. 2.7 не симметрично, поскольку для пары (1, 2) нет пары (2, 1).

Пример 2.10. Рассмотрим следующие отношения:

(a) отношение параллельности прямых на плоскости,

(b) отношение «учиться в одной группе» (для множества студентов университета),

(c) отношение «быть выше ростом» (для множества студентов университета),

(d) пусть А = {1, 2, 3, 4, 5} и отношение R означает, что если (a, b) ∈ R, то a + b является простым числом.

Определить, симметричны ли эти отношения.

(a) Отношение симметрично, поскольку если прямая a параллельна прямой b, то и прямая b будет параллельна прямой a.

(b) Отношение симметрично.

(c) Отношение не симметрично, если a выше ростом b, то b не выше чем а.

(d) Отношение симметрично, поскольку если a + b простое число, то и b + a простое число.

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

Отношение R на множестве А является антисимметричным, если для каждой пары (a, b) ∈ R имеется пара (b, а) ∈ R; только тогда, когда a = b, т. е. если aRb и bRа, то тогда a = b. Отношение R не антисимметрично, если существуют a ∈ А и b ∈ В, такие что (a, b) ∈ R и (b, а) ∈ R, но a ≠ b.

Пример 2.11. Пусть А = {1, 2, 3, 4} и отношения R1 и R2 представлены следующими орграфами (рис. 2.8 и 2.9). Антисимметричны ли эти отношения?

Рис. 2.8

Рис. 2.9

Отношение R1 на рис. 2.8 антисимметрично, а R2 на рис. 2.9 нет, потому что наряду с парой (1, 2) имеется пара (2, 1) и 1 ≠ 2.

Пример 2.12. Определить, какие из отношений антисимметричны:

(a) отношение ≤ (меньше или равно) на множестве целых чисел Z,

(b) отношение включения ⊆ на совокупности множеств,

(c) деление на множестве натуральных чисел N (m | n означает, что m является делителем n),

(d) пусть М – множество квадратных матриц порядка n с элементами из нулей и единиц. Пусть отношение R означает, что для матриц А, В ∈ M произведение А × В равно единичной матрице I, т. е. (А, В) ∈ R, если А × В = I.

(a) Отношение ≤ является антисимметричным, потому что если а ≤ b, то b ≤ a, только если a = b.

(b) Отношение включения ⊆ антисимметрично, потому что если А ⊆ В и В ⊆ А, то тогда А = В.

(c) Отношение деления на множестве натуральных чисел антисимметрично, поскольку m делит n (m | n) и n делит m (n | m) только тогда, когда m = n.

(d) Отношение R для матриц из М не является антисимметричным, потому что если А × В = I, то и В × А = I. Например:

Необходимо заметить, что отношения симметричности и антисимметричности не являются отрицанием одно другого. Если отношение не симметрично, то оно не обязательно должно быть антисимметричным, и наоборот. Например, пусть А = {1, 2, 3} и пусть отношение R1 = {(1, 1), (2, 2), (3, 3)}, а отношение R2 = {(1, 2), (2, 1), (2, 3)}. Тогда отношение R1 симметрично и антисимметрично, а отношение R2 не симметрично и не антисимметрично.

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

Отношение R на множестве А транзитивно, если для каждых пар (a, b) ∈ R и (b, c) ∈ R, пара (a, c) ∈ R, т. е. если имеются aRb и dRc, то обязательно aRc. Отношение R не транзитивно, существуют такие элементы a, b, c ∈ A, что (a, b) ∈ R и (b, c) ∈ R, но пара (a, c) ∉ R.

Пример 2.13. Определить, какие из отношений транзитивны:

(a) пусть А = {1, 2, 3, 4} и R = {(1, 2),(1, 3), (2, 3), (4, 4)},

(b) пусть отношение R задано на множестве натуральных чисел N и означает (a, b) ∈ R, если a ≡ b (mod m) (числа a и b называются конгруэнтными по модулю m, если m является делителем (a-b), где m – целое число),

(с) отношения R1, R2, R3 на рис. 2.10.

Рис. 2.10

(a) Отношение R транзитивно.

(b) Отношение R транзитивно, потому что если a ≡ b (mod m) и b ≡ c (mod m), то тогда a ≡ с (mod m).

Например, пусть а = 3, b = 7, с = 11 и m = 4, тогда 3 ≡ 7(mod 4), 7 ≡ 11 (mod 4) и 3 ≡ 11 (mod 4), т. е. числа 3, 7 и 11 конгруэнтны по модулю 4, потому что все они имеют один и тот же остаток 3 при делении на 4.

(с) R1 и R2 – транзитивны, R3 не транзитивно.

2.7. Замыкание свойств

Пусть имеется множество А и семейство всех отношений на А, и пусть Р некоторое свойство этих отношений, например симметричность или транзитивность. Отношение со свойством Р называется Р-отношением. Отношение называется Р-замыканием некоторого отношения R на А (пишется P(R)), если оно является Р-отношением и R ⊆ P(R) ⊆ S, для каждого P-отношения S, содержащего R. Принято писать рефлексивное замыкание (R), симметричное замыкание (R), транзитивное замыкание (R), для рефлексивного, симметричного и транзитивного замыканий.

Отношение P(R) может, вообще говоря, и не существовать, однако в целях обобщения оно может быть всегда построено.

Обозначим

А = {(a, a): a ∈ A} диагональное отношение или отношение равенства на множестве А. Тогда замыкания отношений можно получать следующим образом.

Пусть R отношение на А, тогда:

1) R ∪

А является рефлексивным замыканием R;

2) R ∪ R-1 является симметричным замыканием R.

Пример 2.14. Рассмотрим следующее отношение R на А = {1, 2, 3, 4, 5 }.

R = {(1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (3, 4), (3, 5), (5, 5) }.

Рефлексивное замыкание (R) = R ∪ {(2, 2), (3, 3), (4, 4)}.

Симметричное замыкание (R) = R ∪ {(3, 2), (4, 3), (5,3)}.

Нахождение транзитивного замыкания можно выполнить с помощью композиции отношений. Так, R2 = R ○ R, Rn = Rn-1 ○ R. Поскольку нахождение транзитивных замыканий отношения при большом числе элементов является весьма трудоемкой задачей(эквивалентной определению ориентированных путей в орграфе), то одним из способов ее решения оказывается возведение в степень матрицы отношений(матрицы смежности орграфа). Так, если R отношение на множестве А с n элементами, то транзитивное замыкание (R) = R ∪ R2 ∪ … Rn.

2.8. Отношение эквивалентности

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

1) для каждого a ∈ S, (a, a) ∈ R;

2) если (a, b) ∈ R, то (b, a) ∈ R;

3) если (a, b) ∈ R и (b, c) ∈ R, тогда (a, с) ∈ R.

Общая идея отношения эквивалентности состоит в том, что оно позволяет классифицировать объекты, которые в некотором смысле «похожи». Фактически, отношение равенства “—” на любом множестве S это отношение эквивалентности:

1) а = а для каждого a ∈ S.

2) если a = b, тогда b = a.

3) если a = b и b = c, тогда a = c.

Следует заметить, что отношение неравенства не является отношение эквивалентности. Например, 2 ≠ 3 и 3 ≠ 2, но 2 = 2.

Пример 2.15.

Пусть имеется множество треугольников на плоскости. Отношение конгруэнтности и подобия треугольников являются отношениями эквивалентности.

Классификация животных по видам. Отношение «в том же виде» есть отношение эквивалентности на множестве животных.

Отношение эквивалентности и разбиения

Разбиением Р множества S называется семейство {Ai} непустых подмножеств S со следующими свойствами:

1) каждый элемент а ∈ S, принадлежит к некоторому Аi;

2) если Аi ≠ Aj, тогда Ai ∩ Aj = Ø.

Иначе говоря, разбиение Р является разбиением S на непересекающиеся непустые подмножества.

Пусть R-отношение эквивалентности на множестве S. Для каждого а из S пусть [a] определяет множество элементов из S, с которыми а связано по отношению R, т. е.

[a] = {x: (a, x) ∈ R}

и называется классом эквивалентности а в S. Любой элемент из [a] называется представителем класса эквивалентности.

Семейство всех классов эквивалентности из S по отношению эквивалентности R обозначается как S / R и S / R = {[a]: a ∈ S}.

Пример 2.16.

(a) Пусть S = {1, 2, 3, 4, 5} и отношение

R = {(1, 1), (1, 2), (2, 1), (1, 3), (2, 2), (2, 3), (3, 2), (3,3), (3, 1), (4, 4), (4, 5), (5, 4), (5, 5)}.

Можно показать, что R рефлексивно, симметрично и транзитивно, т. е. является отношением эквивалентности. Найдем представителей каждого класса эквивалентности.

{1] = {1, 2, 3}, [2] = {1, 2, 3}, [3] = {1, 2, 3}, [4] = {4, 5}, [5]={4, 5}.

Классы [1] = [2] = [3] и [4] = [5] и S / R = {[1], [4] } являются разбиением S. В качестве представителей класса эквивалентности можно выбрать также либо {[1], [5]}, либо {2], [4]}, {[2], [5]} и т. д.

(b) Пусть R4 является отношением на множестве целых чисел Z и определяется как a ≡ b (mod 4), что читается «a конгруэнтно b по модулю 4» и означает, что разность a – b делится нацело на 4, или, иначе говоря, a при делении на 4 имеет такой же остаток, что и b при делении на 4. R4 является отношением эквивалентности на Z и порождает 4 класса эквивалентности в множестве Z / R4:

A0 = {…, – 8, – 4, 0, 4, 8, …},

A1 = {…, – 7, – 3, 1, 5, 9, …},

A2 = {…, – 6, – 2, 2, 6, 10, …},

A3 = {…, – 5, – 1, 3, 7, 11, …}.

2.9. Отношение частичного порядка

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

1) Для каждого а ∈ S, (a, a) ∈ R.

2) Если (a, b) ∈ R и (b, a) ∈ R, то a = b.

3) Если (a, b) ∈ R и (b, c) ∈ R, то (a, c) ∈ R.

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

Пример 2.17.

(a) Отношение ≤ на множестве вещественных чисел R рефлексивно, антисимметрично и транзитивно, поэтому оно является отношением частичного порядка.

(b) Отношение включения множеств ⊆ является частичным порядком, поскольку выполняются все три свойства:

1) а ⊆ А, для любого множества А (рефлексивность);

2) если А ⊆ В и В ⊆ А, то тогда А = В (антисимметричность);

3) если А ⊆ В и В ⊆ С, то тогда А ⊆ С (транзитивность).

(с) Отношение «a делит b» является отношением частичного порядка на множестве положительных целых чисел N. Однако если это отношение определить на множестве целых чисел Z, то оно не будет отношением частичного порядка, поскольку нарушено свойство антисимметричности, например 5 | – 5 (5 является делителем – 5) и – 5 | 5 (и – 5 является делителем 5), но 5 × – 5.

Отношение R на множестве S называется называют частичным порядком, потому что оно может выполняться не для всех пар декартова произведения S × S. Если оно выполняется для всех пар, то тогда оно называется линейно упорядоченным, или цепью.

В примере 2.17(а) отношение не только частично упорядочено, но и является цепью. Отношение включения множеств (b) является частично упорядоченным, но не является цепью.

2.10. Решенные задачи

Произведение множеств

2.1. Даны множества A = {a, b, c}и B = {1, 2, 3 }. Найти декартово произведение следующих множеств

(a) А × В, (b) B × A, (c) A × A.

(a) Элементами А × В являются все упорядоченные пары (a, b), где a ∈ A и b ∈ B.

А × В = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3), (c, 1), (c, 2), (c, 3)}.

(b) Элементами B × A являются все упорядоченные пары (b, a), где b ∈ B и a ∈ A.

B × A = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c), (3, a), (3, b), (3, c)}.

(c) Элементами A × A являются все упорядоченные пары (x, y), где x, y ∈ A.

A × A = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)}.

Число пар в каждом произведении равно произведению числа элементов обеих множеств этого произведения.

2.2. Доказать, что если А ⊆ Y и B ⊆ Z, то A × B ⊆ Y × Z.

Рассмотрим произвольную пару (a, b) из прямого произведения A × B, т. е. пусть (a, b) ∈ A × B. Тогда a ∈ A и b ∈ B. Поскольку А ⊆ Y, то тогда a ∈ Y, а поскольку B ⊆ Z, то тогда b ∈ Z. Из этого следует, что (a, b) ∈ Y × Z. Иначе говоря, любая пара из A × B принадлежит также и Y × Z, поэтому A × B ⊆ Y × Z.

2.3. Пусть A = {1, 2, 3}, B = {a, b, c, d}, C = {b, c, d, e}. Найти A × (B ∩ C) и (A × B) ∩ (A × C).

Найдем B ∩ C = {b, c, d}, тогда

A × (B ∩ C) = {(1, b), (1, c), (1, d), (2, b), (2, c), (2, d), (3, b), (3, c), (3, d)}.

Найдем далее.

A × B = {(1, a), (1, b), (1, c), (1, d), (2, a), (2, b), (2, c), (2, d), (3, a), (3, b), (3, c), (3, d)}.

A × C = {(1, b), (1, c), (1, d), (1, e), (2, b), (2, c), (2, d), (2, e), (3, b), (3, c), (3, d), (3, e)}.

Найдем теперь пересечение этих множеств.

(A × B) ∩ (A × C) = {(1, b), (1, c), (1, d), (2, b), (2, c), (2, d), (3, b), (3, c), (3, d)}.

2.4. Доказать, что декартово произведение множеств дистрибутивно относительно операции пересечения множеств

A × (B ∩ C) = (A × B) ∩ (A × C).

A × (B ∩ C) = {(x, y): x ∈ A и y ∈ B ∩ C} = {(x, y): x ∈ A, y ∈ B и x ∈ A, y ∈ C} = {(x, y): (x, y) ∈ A × B и (x, y) ∈ A × C} = (A × B) ∩ (A × C).

2.5. Доказать, что для любого непустого конечного множества А и универсального множества U выполняется

Ø × А = Ø.

Предположим противное, что Ø × А не пусто и имеется элемент (x, a) ∈ Ø × А. Тогда Ø × А = {(x, a): (x, a) ∈ Ø × А} = = {(x, a): x ∈ Ø и x ∈ A}. Это предположение приводит к противоречию, поскольку оказывается, что пустое множество Ø имеет элемент х, что невозможно. Поэтому Ø × А = Ø.

2.6. Все рассмотренные ранее отношения строились для пар элементов, т. е. были бинарными отношениями. Однако существуют отношения, образованные из большего числа элементов. Если таких элементов n, то отношения называют n-арными отношениями, т. е. для любого множества S подмножество произведения Sn называется n-арными отношением на S и, в частности, подмножество множества S3 называется тернарным отношением на S.

Пусть А = {1, 2, 3}, B = {4, 5, 6}, C = {7, 8}. Найти A × B × C.

Декартово произведение A × B × C содержит все упорядоченные тройки (a, b, c), где a ∈ A, b ∈ B и c ∈ C. Эти тройки представлены в виде дерева на рис. 2.11, при этом n(A × B × C) = n(A) · n(B) · n(C) = = 3 · 3 · 2 = 27.

Рис. 2.11

Отношения и их матрицы и графы

2.7. Пусть А = {1, 2, 3, 4} и B = {x, y, z}. Найти количество отношений из А в В.

Декартово произведение A × B имеет 4 × 3 = 12 элементов. Поэтому имеется 212 = 4096 подмножеств A × B и, следовательно, 4096 отношений из А в В.

2.8. Имеется множество A = {a, b, c, d} и множество B = {x, y, z}, а также отношение R из А в В.

R = {(a, y), (b, x), (b, z), (d, y), (d, z)}.

(a) Нарисовать стрелочную диаграмму R.

(b) Найти матрицу отношения R.

(c) Найти обратное отношение R-1.

(d) Найти область определения и область значений R.

(e) Сечение по элементу d ∈ А отношения R.

(f) Фактор-множество множества В по отношению R.

(а) Стрелка из а ∈ А в b ∈ В должна присутствовать, если (a, b) ∈ R.

Рис. 2.12

(b) Строки матрицы определяются элементами из А, столбцы из В. Элемент матрицы, стоящий на пересечении i-й строки и j-го столбца равен 1, если определяемые им элементы ai ∈ А и bj ∈ В образуют пару (ai, bj) ∈ R и равен 0 в противном случае.

(с) Обратное отношение:

R-1 = {(y, a), (x, b), (z, b), (y, d), (z, d)}.

Чтобы получить диаграмму обратного отношения, надо поменять направления всех стрелок на противоположные на рис. 2.12.

(d) Область определения отношения R состоит из первых элементов всех пар, входящих в R, и это будет множество {a, b, d}. Область значений образована вторыми элементами пар для R, и это множество {x, y, z}.

(e) Сечением по элементу d ∈ А отношения R будет множество {y, z}.

(f) Фактормножество множества В по отношению R:

2.8. Имеется множество A = {5, 7, 11, 35, 55,154} и отношение R на А, которое означает, что «x делит y» и записывается обычно x | y. Иначе говоря, x делит y, если при делении y на x остаток равен 0, т. е. существует такое целое число z, называемое частным, что x · y = z.

(a) Записать R в виде упорядоченных пар.

(b) Нарисовать ориентированный граф отношения R.

(c) Найти обратное отношение R-1 и дать его словесное описание.

(a) Найдем все пары (x, y) ∈ R, в которых x является делителем y.

R = {(5, 5), ((5, 35), (5, 55), (7, 7), (7, 35), (7, 154), (11, 11), (11, 55), (11, 154), (35, 35), (55, 55), (154, 154)}.

(b) Орграф R представлен на рис. 2.13.

Рис. 2.13

(с) Обратное отношение состоит из пар:

R-1 = {(5, 5), ((35, 5), (55, 5), (7, 7), (35, 7), (154, 7), (11, 11), (55, 11), (154, 11), (35, 35), (55, 55), (154, 154)}. Словесное описание для (x, y) ∈ R-1 выражается следующим образом: «x кратно y».

2.9. Пусть R и S являются отношениями на X = {a, b, c}.

R = {(a, a), (a, b), (b, c), (a, c)}, S = {(a, a), (a, b), (b, a), (b, c), (b, b)}.

Найти (a) R ∩ S, R ∪ S, RC,

(b) R ○ S,

(c) S2 = S ○ S.

(a) Рассмотрим множество пар R и S и выберем пересечение и объединение из этих пар. Чтобы найти дополнение RC, необходимо знать универсальное множество, которым в данном случае является декартово произведение А × А.

R ∩ S = {(a, a), (a, b), (b, c)},

R ∪ S = {(a, a), (a, b), (b, c), (a, c), (b, a), (b, b)},

RC = {(b, a), (b, b), c, c), c, a)}.

(b) Для каждой пары (a, b) из R, найдем все пары (b, c) из S и получим все пары (а, c) ∈ R ○ S:

R ○ S = {(a, a), (a, b), (a, c)}.

(c) По аналогии с (b) для каждой пары (a, b) из R найдем все пары (b, c) также из R:

S2 = S ○ S = {(a, a), (a, b), (a, c)}.

2.10. Дано: A = {a, b, c}, B = {1, 2, 3, 4}, C = {x, y, z}. Имеются отношения R и S из A в B и из B в C соответственно.

R = {(a, 1), (b, 1), (c, 2), (c, 3), (c,4)}, S = {(1,y), (2, z), (3, x), (4, z)}.

(а) Найти композицию отношений R ○ S.

(b) Найти матрицы MR,MS и MR ○ S для отношений R, S и R ○ S соответственно. Сравнить матрицу MR ○ S с матрицей произведения MR на MS.

(а) На рис. 2.14 показана стрелочная диаграмма отношений R и S. Чтобы найти композицию этих отношений, надо построить все пути для каждого элемента из множества А в множество С. Например, для элемента a существует путь a → 1 → y, поэтому (a, y) ∈ R ○ S.

Рис. 2.14

R ○ S={(a, y), (b, y), (c, x), (c, z)}.

Найдем матрицы для каждого из отношений R, S и R ○ S.

Найдем теперь произведение матриц MR и MS.

Матрицы MR ○ S и MRMS имеют одни и те же нулевые элементы, поэтому если в произведении матриц MRMS заменить все элементы большие 1 на 1, то мы получим матрицу композиции отношений MR ○ S.

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

2.11. Дано множество А = {1, 2, 3, 4, 5} и отношение R на А.

R = {(1, 2), (2, 1), (3, 3), (3, 4), (3, 5), (4, 5), (5, 5)}.

(a) Нарисовать орграф для R.

(b) Определить свойства R.

(a) Орграф представлен на рис. 2.15

Рис. 2.15

(b) R не рефлексивно, поскольку нет, например, пары (1, 1), т. е. (1, 1) ∉ R.

R не симметрично, например, (3, 4) ∈ R, но (4, 3) ∉ R.

R не антисимметрично, потому что (1, 2) ∈ R и (2, 1) ∈ R, но 1≠2.

R транзитивно, поскольку (3, 4) ∈ R, (4, 5) ∈ R и (3, 5) ∈ R.

2.12. Имеются следующие отношения на множестве A = {1, 2, 3, 4 }:

R = {(1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (3, 2), (4, 4)},

S = {(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3), (3, 4), (4, 4)},

T = {(1, 2), (1, 3), (2, 2), (2, 3), (4, 3)},

Ø = пустое отношение,

A × A = универсальное отношение.

Определить, какие из этих отношений на А: (a) рефлексивны, (b) симметричны, (c) антисимметричны, (d) транзитивны.

(a) Рефлексивны только S и A × A. Отношение Ø не рефлексивно, R не рефлексивно, потому что не содержит пары (3, 3), T не рефлексивно, потому что нет пар (1, 1), (3, 3) и (4, 4).

(b) Симметричны отношения R, Ø и A × A. S не симметрично, потому что есть пара (1, 2), но нет пары (2, 1). По этой же причине не симметрично отношение T.

(c) Антисимметричны все отношения, кроме R, которое имеет (1, 2) ∈ R и (2, 1) ∈ R, но 1 ≠ 2.

(d) Транзитивны отношения T, Ø и A × A. R не транзитивно, потому что (1, 2) ∈ R и (2, 3) ∈ R, но (1, 3) ∉ R, S не транзитивно так как (1, 3) ∈ R и (3, 4) ∈ R, но (1, 4) ∉ R.

2.13. Пусть имеются следующие отношения на множестве N. Найти их свойства.

(a) (a, b) ∈ R1, если a ∈ N, b ∈ N и число (a + b) является четным.

(b) (a, b) ∈ R2, если a ∈ N, b ∈ N и число (a + b) является нечетным.

(c) (a, b) ∈ R3, если a ∈ N, b ∈ N и

 является правильной дробью

(d) (a, b) ∈ R4, если a ∈ N, b ∈ N и a · b является степенью числа три.

(a) R1 рефлексивно, поскольку (а + а) = 2 · а и четно для любого а, симметрично, поскольку если (a + b) четно, то четно и (b + a). R1 не антисимметрично, так как 3 ≠ 5, но 3 + 5 = 5 + 3 = 8 и является четным числом. Транзитивность следует из того факта, что сумма любых двух четных чисел четна и сумма любых двух нечетных чисел также четна. Например, (1 + 3) четно и (3 + 5) четно и (1 + 5) также четно.

(b) R2 не рефлексивно, но симметрично, поскольку если (a + b) нечетно, то (b + a) также нечетно. R2 не антисимметрично, например (2 + 3) = 5 нечетно и (3 + 2) нечетно, но 2 ≠ 3. Отношение R2, кроме того, не транзитивно, например (2, 1) ∈ R2 и (1, 4) R2, но (2, 4) ∉ R2.

(c) R3 не рефлексивно, поскольку

 = 1 и не является правильной дробью. Это отношение также не симметрично, если (1, 2) ∈ R3 поскольку

 является правильной дробью, то (2, 1) ∉ R3, так как

 не является правильной дробью. R3 антисимметрично, потому что для любых a ∈ N, b ∈ N, если (a, b) ∈ R3, то (b, a) ∉ R3. Отношение R3 транзитивно.

(d) Отношение R4 не рефлексивно, например 2 ∈ N, но (2, 2) ∉ R4, потому что 2 × 2 = 4 и не является степенью тройки R4 симметрично и транзитивно, но не антисимметрично.

2.14. Дать примеры отношений R на А = {1, 2, 3, 4} со следующими свойствами:

(a) R – антисимметрично, но не симметрично.

(b) R – антисимметрично и симметрично.

(c) R – только транзитивно.

Возможно несколько различных примеров для каждого случая. Ниже представлен один из возможных вариантов.

(a) R = {(1, 2), (1, 4), (2, 3)}.

(b) R = {(1, 1), (2, 2), (4, 4)}.

(c) R = {(1, 2), (1, 3), (1, 4), (2, 3), (3, 3), (4, 1)}.

2.15. Отношение R антисимметрично, если всякий раз, когда (a, b) ∈ R и (b, a) ∈ R, то тогда a = b. Следует ли из этого, что если отношение антисимметрично, то оно рефлексивно?

Нет не следует, потому что определение антисимметричности не требует, чтобы это условие выполнялось для всех пар отношения R.

2.16. Если отношение R транзитивно, то для всех a, b, c ∈ A таких, что если (a, b) ∈ R и (b, с) ∈ R, то тогда (a, с) ∈ R. Заменим с на а, тогда, по определению транзитивности, из того, что (a, b) ∈ R и (b, а) ∈ R следует, что (a, a) ∈ R и, значит, если отношение транзитивно, то оно и рефлексивно. В чем ошибка этого утверждения?

Ошибка в том, что все три элемента a, b, c ∈ A в определении транзитивности должны быть различны.

2.17. Дать пример двух симметричных отношений R и S на А = {1, 2, 3}, композиция которых R ○ S:

(a) симметрична,

(b) не симметрична.

(a) R = {(1,2), (2, 1), (3, 2), (2, 3)}, S = {(1, 1), (2, 2), (1, 3), (3, 1)}.

R ○ S = {(1,2), (2, 1), (3, 2), (2, 3)}.

(b) R = {1, 2), (2, 1)}, S={(2, 3), (3, 2)}.

R ○ S = {(1, 3)}.

2.18. Пусть R и S отношения на множестве А. Показать, что если T является пересечением этих отношений Т = R ∩ S и если отношения R и S симметричны и транзитивны, то отношение Т также симметрично и транзитивно.

Пусть имеется (a, b) ∈ T, тогда (a, b) ≈ ∈ R и (a, b) ∈ S и поскольку эти отношения симметричны, имеется пара (b, a) ∈ R и (b, a) ∈ S. Но тогда пара (b, a) ∈ T, поскольку Т представляет собой пересечение элементов S и T и поэтому Т также симметрично. Аналогично, если (a, b) ∈ T и (b, c) ∈ T, то (a, b) ∈ R и (b, c) ∈ R, а поскольку R транзитивно, то (a, c) ∈ R и также (a, c) ∈ S Поскольку Т является пересечением R ∩ S, то Т должно также содержать (a, c), т. е. (a, c) ∈ Т и, значит, Т транзитивно.

2.19. Пусть имеется множество A = {1, 2, 3, 4} и отношение R на A.

R = {(1, 2), (2, 2), (2, 3), (3, 4)}.

Найти:

(a) рефлексивное замыкание (R),

(b) симметричное замыкание (R),

(с) транзитивное замыкание (R).

(a) Для нахождения рефлексивного замыкания на R надо добавить те пары диагонального отношения, которых нет в R.

Рефлексивное замыкание R = R ∪ {(1, 1), (3, 3), (4, 4)} =

= {(1, 1), (1, 2), (2, 2), (2, 3), (3, 3), (3, 4), (4, 4)}.

(b) Для симметричного замыкания надо добавить пары из R-1, которых нет в R.

Симметричное замыкание R = R ∪ {(2, 1), (3, 1), (4, 3)}.

(c) Транзитивное замыкание на R можно получить, если найти объединение R с R2, R3 и R4, поскольку А имеет 4 элемента.

R2 = R ○ R = {(1, 2), (1, 3), (2, 2), (2, 3), (2, 4)}.

R3 = R ○ R ○ R = {(1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4)}.

R4 = R ○ R ○ R ○ R = {(1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4)}.

Транзитивное замыкание R = R ∪ R2 ∪ R3 ∪ R4 =

= {(1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 4)}.

Отношение эквивалентности и разбиения