Материал: 4553

матрицы P P (qij ) удовлетворяют неравенствам qij pij для любых i, j.

Бинарное отношение P на множестве A называется диагональю, если оно состоит из всех пар вида (x, x), где x A. Диагональ на множестве A обозначается id A.

Бинарное отношение P на множестве A называется отношением эквивалентности, если оно является рефлексивным, симметричным и транзитивным. Отношение эквивалентности обозначается символом E или ~.

Классом эквивалентности элемента x A называется множество E(x)

всех элементов y A таких, что x ~ y.

Каждый элемент множества А принадлежит одному из классов эквивалентности. Разные классы эквивалентности не пересекаются. Поэтому говорят, что отношение эквивалентности разбивает множество А на попарно непересекающиеся классы эквивалентности.

Множество всех классов эквивалентности элементов множества А для отношения эквивалентности Е называется фактор – множеством А по Е и обозначается A /E .

Отношения порядка и упорядоченные множества

Бинарное отношение P на множестве A называется отношением частичного порядка, если оно является рефлексивным, антисимметричным и

транзитивным. Оно обозначается символом , а обратное ему отношение 1 обозначается символом . Множество, на котором задано отношение частичного порядка, называется частично упорядоченным множеством.

Бинарное отношение P на множестве A называется отношением строгого порядка, если оно определяется так: (x, y) P x y и x y. Оно обозначается символом < . Это бинарное отношение не является отношением частичного порядка, так как оно не удовлетворяет условию рефлексивности x < x.

17

Если в множестве A есть элементы x и y, о которых нельзя сказать, что x y или y x , то такие элементы называются несравнимыми. Отношение частичного порядка называется отношением линейного порядка, если любые два элемента x и y множества A сравнимы, то есть x y или y x . Множество, на котором задано отношение линейного порядка, называется

линейно упорядоченным множеством.

2.2. Практическая часть

Пример 1. Пусть A = {1, 2, 3}, B = {1, 2, 3, 4, 5, 6}. Перечислить все элементы бинарного отношения P на паре множеств A, В:

P {(a, b) a > b, a A, b B}.

Указать диагональ на множестве А.

Решение. Множество A B содержит 18 упорядоченных пар. Из них пары (2, 1), (3, 1), (3, 2) принадлежат бинарному отношению P, потому что 2 > 1, 3 > 1, 3 > 2. Следовательно, P = {(2, 1), (3, 1), (3, 2)}. Диагональ на множестве A: id A {(1, 1), (2, 2), (3, 3)}.

Пример 2. Пусть A = {1, 2, 3, 4}, B = {3, 4, 5}. Составить матрицу бинарного отношения P = {(1, 3), (1, 4), (2, 4), (2, 5), (3, 3), (3, 4), (4, 4), (4, 5)} на паре множеств A, В.

Решение. Так как множество A состоит из четырех элементов, а множество В – из трех, то матрица P (pij ) имеет четыре строки и три

столбца. Из определения матрицы бинарного отношения вытекает: p11 1 (так как (1, 3) P ),

p12 1 (так как (1, 4) P ), p13 0 (так как (1, 5) P ), p21 0 (так как (2, 3) P ), p22 1 (так как (2, 4) P ),

и так далее. Получаем

Пример 3. Пусть A = {a, b, c}, B = {1, 2, 3, 4}, C = {f, g, h}, множества пар

P1 {(a, 1), (a, 2),(b, 2), (c, 3)},

P2 {(2, f ), (2, g), (4, f ), (4, g), (4, h)}

являются бинарными отношениями между элементами множеств A, B и B, С соответственно. Определить композицию P1 P2 этих отношений и обратное отношение для отношения P1.

Решение. Из определения композиции бинарных отношений вытекает, что P1 P2 {(a, f ), (a, g), (b, f ), (b, g)}. Из определения обратного бинарного

отношения вытекает, что P1 1

Пример 4. Пусть множество A = {в, к, м} состоит из волка, кошки и мышки. Обозначим через P1 множество тех пар зверей (p, q), в которых зверь p может съесть зверя q, а через P2 – множество тех пар (r, s), в которых зверь r не может съесть зверя s. Определить, являются ли бинарные отношения P1, P2 на множестве A рефлексивными, антирефлексивными, симметричными, антисимметричными, транзитивными.

Решение. Очевидно, что

P1 {(в, к), (в, м), (к, м)},

P2 {(в, в), (к, к), (м, м),(к, в), (м, в),(м, к)}.

Так как бинарное отношение P1не содержит пар (в, в), (к, к), (м, м), то оно является антирефлексивным (следовательно, не является рефлексивным). Оно не содержит пар (к, в), (м, в), (м, к), поэтому является антисимметричным (следовательно, не является симметричным). Бинарное отношение P1 является транзитивным. Отношение P2 является рефлексивным, антисимметричным, транзитивным.

Пример 5. Пусть A = {1, 2, 3, 4}, P = {(1, 1), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (4, 2), (4, 4)} – бинарное отношение на множестве А. Определить с помощью

19

матрицы P, является ли отношение P рефлексивным, антирефлексивным, симметричным, антисимметричным, транзитивным.

Решение. Составим матрицу бинарного отношения P:

Так как на главной диагонали матрицы P нет нулей, то отношение P является рефлексивным (следовательно, оно не является антирефлексивным).

q12 > p12 ), следовательно, отношение P не является транзитивным.

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

Решение. Пусть A – множество всех студентов, обучающихся в академии. Рассмотрим бинарное отношение P A A, состоящее из всех пар студентов,

являющихся однокурсниками, то есть P {(a, b) a и b – однокурсники, a A, b A}. Оно является рефлексивным, так как каждый студент является

20

однокурсником по отношению к самому себе, то есть (a, a) P для любого a A. Оно является симметричным (если а – однокурсник по отношению к b, то и b – однокурсник по отношению к а, то есть если (a, b) P, то и (b, a) P ). Оно является транзитивным (если а – однокурсник по отношению к b, b – однокурсник по отношению к c, то a – однокурсник по отношению к c, то есть если (a, b) P и (b, c) P, то (a, c) P ). Следовательно, свойство «быть однокурсником» определяет отношение эквивалентности P на множестве всех студентов, обучающихся в академии.

Пример 7. Пусть A – множество всех пар натуральных чисел. Будем писать (a1, b1)P(a2, b2 ), если a1 a2, b1 b2, где a1, a2, b1, b2 – натуральные числа. Определить, является ли бинарное отношение P на множестве A отношением частичного порядка. Является ли оно отношением линейного порядка?

Решение. Очевидно, что (a, b)P(a, b) для любых натуральных чисел a, b,

неверным), поэтому бинарное отношение P является антисимметричным. Если

(a1, b1)P(a2, b2 ) и (a2, b2 )P(a3, b3), то (a1, b1)P(a3, b3), поэтому отношение P

является транзитивным. Следовательно, бинарное отношение P является отношением частичного порядка. Так как, например, элементы (1, 2) и (2, 1) несравнимы, то оно не является отношением линейного порядка.

2.3. Индивидуальные задания

Задача № 1. Перечислить все элементы бинарного отношения P на паре множеств A, B:

P {(a, b) a > b, a A, b B}.

Задача № 2. Составить матрицу бинарного отношения F на множестве A. Определить, является ли данное отношение рефлексивным, антирефлексивным, симметричным, антисимметричным, транзитивным.

Множества A, B и бинарное отношение F заданы в табл. 3.