ОСНОВНЫЕ КЛАССЫ БИНАРНЫХ ОТНОШЕНИЙОтношение эквивалентности. Бинарное отношение 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) транзитивности не нарушает. Получаем новое отношение R1 нестрого порядка: 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, потому что они не входят ни в одну пару отношения. Следовательно, наше новое отношение R1 является частично упорядоченным. Задачи для самостоятельного решения. 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 ______________________________________ Редакційно-видавничий відділ НМетАУ
|
