ОСНОВНЫЕ КЛАССЫ БИНАРНЫХ ОТНОШЕНИЙ

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

Важное значение этого отношения состоит в том, что оно даёт признак разбиения множества А на непересекающиеся подмножества, которые называются классами эквивалентности. Класс эквивалентности – это множество вторых координат пар (а, b)ÎR, у которых первая координата одна и та же. Обозначается: К(а) = { b | b ÎA, (а, b)ÎR}. Для каждого элемента а ÎA можно определить его класс эквивалентности. Множество всех классов эквивалентности называется фактор-множеством по данному отношению R. Обозначается F/R. Мощность фактор-множества называется индексом разбиения исходного множества А.

Граф отношения эквивалентности представляет собой объединение (сумму) полных подграфов, каждый из которых соответствует классу эквивалентности.

Отношение порядка.

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

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

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

Если для произвольных элементов а и b такого множества имеет место соотношение a R b либо b R a, то такое множество называется линейно (полностью) упорядоченным.

Если же для произвольных элементов а и b такого множества соотношение a R b либо b R a определено не для всех, а лишь для некоторых элементов а и b, то такое множество называется частично упорядоченным.

Для линейно упорядоченного множества любые два его элемента а и b называются сравнимыми.

Для частично упорядоченного множества некоторые элементы сравнимы, а некоторые не сравнимы.

Элемент р ÎА называется наименьшим элементом множества А, если для всех а ÎА имеет место соотношение: p R a. Обозначается так: p = min A.

Элемент q ÎА называется наибольшим элементом множества А, если для всех а ÎА имеет место соотношение: a R q. Обозначается так: q = max A.

Задача 4.11.1. Показать, что отношение R = {(a, a), (a, b), (b, a), (b, b), (c, c), (d, d), (d, e), (e, d), (e, e)} а множестве A = { a, b, c, d, e } является отношением эквивалентности. Найти фактор-множество по данному отношению и индекс разбиения данного множества.

Решение. Очевидно, что отношение R рефлексивно, так есть все пары вида (а, а). Оно симметрично, поскольку содержит пары (a, b) и (b, a), (d, e) и (e, d). Транзитивно: (a, b), (b, a) и (a, a); (d, e), (e, d) и (d, d). Следовательно, отношение R – отношение эквивалентности.

Классы эквивалентности: К(а) ={ a, b }; K(b) ={ a, b }; K(c) = { c }; K(d) ={ d, e }; K(e) = { d, e }.

Фактор-множество по отношению R: F/R = { { a, b }; { c }; { d, e }}.

Индекс разбиения данного множества А: | F/R | = 3.

Задача 4.11.2.

Является ли множество А линейно упорядоченным отношением R?

А = {Петров (рост 180 см); Сидоров (рост 175 см); Данилов (рост 174 см); Орлов (рост 171 см); Васильев (рост 176 см)}; R = «а выше b».

Решение. Построим матрицу и граф данного отношения.

Данное отношение является иррефлексивным, асимметричным и транзитивным. Следовательно, R - это отношение строгого порядка. Множество А является линейно упорядоченным, поскольку для любых двух его элементов выполняется соотношение: либо а выше b, либо а не выше b (то есть либо a R b, либо a` R b). Поэтому любые два элемента множества А будут сравнимы. Найдём минимальный и максимальный элементы множества А. Так для элемента П ÎА выполняется соотношение П R a для всех а ÎА (то есть П етров выше С идорова, выше Д анилова и т.д.). По определению элемент П – наименьший на множестве А: П = min A. Для элемента О ÎА выполняется соотношение а R O для всех а ÎА (то есть П етров выше О рлова, С идоров выше О рлова, Д анилов выше О рлова и т.д.). По определению элемент О – наибольший на множестве А: О = max A.

Задача 4.11.3. Для данного отношения R ={(1,2), (2,3), (3,4), (5,5)} на множестве А = {1, 2, 3, 4, 5} проделать следующее:

1) изобразить графически;

2) достроить до отношения порядка (строгого или нестрогого);

3) упорядочить частично и линейно;

4) найти наибольший и наименьший элементы и указать пары несравнимых элементов.

Решение.

Достроить до отношения строгого порядка нельзя, поскольку имеется элемент (5,5). Поэтому можем лишь добавить пары (1,1), (2,2) и (3,3) и тем самым сделаем отношение рефлексивным. С учётом добавленных пар отношение становится антисимметричным. Найдём транзитивное замыкание данного отношения. Для пар (1,2) и (2,3) добавим (1,3); для (2,3) и (3,4) – (2,4); для вновь добавленной (1,3) и данной (3,4) – (1,4). Элемент (5,5) транзитивности не нарушает. Получаем новое отношение R₁ нестрого порядка:

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

1. Полученное отношение является частично упорядоченным, поскольку элемент 5 не может быть сравним с остальными. То есть, например, если для элементов 1 и 2 выполняется 1R2, то для 1 и 5 не выполняется ни 1R5, ни 5R1.

2. Минимальный элемент множества А – это 1, поскольку он входит во все пары: (1,2), (1,3), (1,4). Максимальный – элемент 4: (1,4), (2,4), (3,4). Однако, минимальным также будет и элемент 5, поскольку имеем пару (5,5). По этой же причине элемент 5 есть и максимальным. Несравнимыми будут элементы 1 и 5, 2 и 5, 3 и 5, 4 и 5, потому что они не входят ни в одну пару отношения. Следовательно, наше новое отношение R₁ является частично упорядоченным.

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

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

а) изобразить R графом;

б) достроить R до отношения эквивалентности, указать фактор-множество и индекс разбиения;

в) достроить до отношения порядка и частично упорядочить, указать максимальный и минимальный элементы, а также пары несравнимых элементов;

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

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

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

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

ЛИТЕРАТУРА

1. Галушкина Ю. И. Конспект лекций по дискретной математике / Ю. И. Галуш­кина, А. Н. Марьямов. — М.: Айрис-пресс, 2007. — 176 с. — (Выс­шее образование).

2. Капитонова Ю. В. Лекции по дискретной математике. — БХВ-Петербург, 2004. — 614 с.

3. Ерусалимский Я. М. Д Дискретная математика: теория, задачи, приложения. М.: Вузовская книга, 2000. — 280 с.

4. Судоплатов С. В. Элементы дискретной математики / С. В. Судоплатов, Е. В. Овчинникова. - М.-Новосибирск: ИНФРД-М НГТУ, 2002. — 280 с.

5. Нефёдов В.Н. Курс дискретной математики / В. Н. Нефёдов, В. А. Осипова - М.: Изд-во МАИ, 1992. — 264 с.

6. Кузнецов О.П. Дискретная математика для инженеров. 6-е узд.,стер. СПб: издательство «Лань», 2009. — 400 с.

7. Романовский И. В. Дискретный анализ. 4-е изд., испр. и доп. СПб.: Невский Диалект, БХВ-Петербург, 2008. — 336 с.

8. Горбатов В.А. Фундаментальные основы дискретной математики. — М.: Наука; Физматлит, 2000. — 544 с.

9. Шапорев С.Д. Математическая логика. Курс лекций и практических за­нятий. - СПб.: БХВ-Петербург, 2005. — 416 с.

Навчальне видання

 

 

Швачич Геннадій Григорович

Сазонова Марина Сергіївна

Бартенєв Георгій Михайлович

 

 

«ДИСКРеТНА МАТЕМАТИКА»

Розділ 1. Теорія множин. Алгебра множин

 

Навчальний посібник

 

Тем план 2015, поз..

 

 

Підписано до друку ______2015. Формат 60х84 _1/16. Папір друк. Друк плоский. Облік.-вид. арк.. Умов. друк. арк.. Тираж 100 пр. Замовлення № ____

 

 

Національна металургійна академія України

49600, Дніпропетровськ-5, пр. Гагаріна, 4

______________________________________

Редакційно-видавничий відділ НМетАУ