Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
Топ:
Генеалогическое древо Султанов Османской империи: Османские правители, вначале, будучи еще бейлербеями Анатолии, женились на дочерях византийских императоров...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Процедура выполнения команд. Рабочий цикл процессора: Функционирование процессора в основном состоит из повторяющихся рабочих циклов, каждый из которых соответствует...
Интересное:
Национальное богатство страны и его составляющие: для оценки элементов национального богатства используются...
Мероприятия для защиты от морозного пучения грунтов: Инженерная защита от морозного (криогенного) пучения грунтов необходима для легких малоэтажных зданий и других сооружений...
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Дисциплины:
2022-10-04 | 20 |
5.00
из
|
Заказать работу |
|
|
2.1. Понятие бинарного отношения. Способы задания бинарных отношений
Бинарным отношением R на множестве X произвольной природыназывается подмножество R множества : . Если пара входит в R, то есть , то принято обозначать . Бинарные отношения задаются следующими способами:
1. Перечисление всех пар элементов (x,y), которые содержатся в R.
2. Задание отношения матрицей смежности.
Пусть X состоит из n элементов, R - бинарное отношение на X. Занумеруем элементы X целыми числами от 1 до n.
Матрицей смежности бинарного отношения называется квадратная матрица , элементы которой формируются по следующему правилу:
3. Задание графом.
Под графом бинарного отношения понимается схема, в которой элементы множества X изображаются точками на плоскости, элементы такие, что пара соединяются стрелкой, направленной от x к y, пары изображаются петлей вокруг точки x.
4. Задание сечениями. Данный способ задания бинарного отношения, в отличие от способов 1-3, пригоден для задания отношений и на бесконечных множествах.
Верхним сечением элемента элемента называется множество элементов таких, что : .
Аналогично определяется нижнее сечение: .
Отношение R полностью задано, если для каждого задано либо множество , либо множество .
Отношение R называется пустым (Æ), если оно не выполняется ни для одной пары .
Для Æ справедливо: 1) , ; 2) граф G(Æ) не имеет дуг; 3) для любого .
Отношение R называется полным (U), если оно выполняется для всех пар .
Для U справедливо: 1) , ; 2) в графе G(U) дуги соединяют любую пару вершин; 3) для любого .
Отношение R называется диагональным (E), если оно выполняется для тех и только для тех пар, которые состоят из совпадающих элементов: .
|
Для E справедливо: 1) 2) в графе G(E) присутствуют только петли при вершинах, других дуг нет; 3) , .
Отношение R называется антидиагональным (), если оно выполняется для тех и только для тех пар, которые состоят из несовпадающих элементов: .
Примеры
1. – диагональное бинарное отношение.
2. – пустое бинарное отношение.
3. – антидиагональное бинарное отношение.
Операции над отношениями
1. Вложение (включение).
Отношение вложено (включено) в отношение , если множество пар, для которых выполнено , содержится в множестве пар, для которых выполнено .
, если , .
2. Дополнение.
Отношение называется дополнением отношения R, если оно выполняется для тех и только для тех пар, для которых не выполняется отношение R, т.е. .
Справедливо: =1- ; в графе G() присутствуют те и только те дуги, которые отсутствуют в графе G(R).
3. Пересечение.
Пересечением отношений и называется отношение .
4. Объединение.
Объединением отношений и называется отношение .
5. Обращение.
Обратным к отношению R называется отношение , определяемое условиями: .
Справедливо: ; граф получается из графа изменением направления дуг, , (см. задачу № 6)
6. Переход к двойственному отношению.
Отношение называется двойственным к отношению R, если .
7. Произведение.
Произведением и называется отношение , определяемое следующим образом: , если существует , для которого и .
8. Сужение.
Отношение называется сужением отношения на множество , если и .
9. Изоморфизм.
Отношения и называются изоморфными, если существует взаимно-однозначное отображение такое, что .
Примеры
1. Для отношений , справедливо: .
2. 1) Если , то .
2) Если , то .
3. Если , , то .
4. Для и из примера 3: .
5. 1.Если , то .
2. Если , то .
6. 1.Если , то .
2. Если , то .
7. Пусть , , где Z – множество целых чисел. Пара , если существует такое, что , . В качестве такого z можно выбрать . Таким образом, = .
8. Отношение является сужением отношения на множество целых чисел Z.
|
Свойства отношений
1. Отношение R называется рефлексивным, если . Другими словами, если для любого выполнено: .
Для рефлексивного отношения R справедливо: ; в графе G(R) в каждой вершине имеется петля; , , .
2. Отношение R называется антирефлексивным, если Æ (или ). Другими словами, если , .
Для антирефлексивного отношения R справедливо: ; в графе G(R) петли отсутствуют; , , .
3. Отношение R называется симметричным, если , т.е. если , то , .
Для симметричного отношения R справедливо: ; в граф G(R) вместе с дугой входит дуга ; .
4. Отношение R называется асимметричным, если Æ, т.е. если , то , .
Для асимметричного отношения R справедливо: ; в граф G(R) дуги и одновременно входить не могут; для любых и сечение не содержит x.
5. Отношение R называется антисимметричным, если , т.е. , только тогда, когда .
Для антисимметричного отношения R справедливо: , если ; в граф G(R) дуги и при одновременно входить не могут; для любых и () сечение не содержит x.
6. Отношение R называется транзитивным, если , т.е. если , , то .
В матрице транзитивного отношения R длялюбых i, k: ; в графе существует дуга (x, y), если существует путь от x к y; для любых и справедливо .
7. Отношение R называется отрицательно транзитивным, если транзитивно.
8. Отношение R называется сильно транзитивным, если оно одновременно транзитивно и отрицательно транзитивно.
9. Отношение R называется ацикличным, если Æ, , то есть из , , …, следует .
10. Отношение R называется связным (полным), если для любых элементов выполнено или .
Связи между свойствами бинарных отношений
1. Если отношение рефлексивно (симметрично, антисимметрично, асимметрично, транзитивно), то – рефлексивно (симметрично, антисимметрично, асимметрично, транзитивно).
2. Если отношение рефлексивно, то – антирефлексивно и если антирефлексивно, то – рефлексивно.
3. Отношение асимметрично тогда и только тогда, когда связно.
4. Если отношение асимметрично, то оно антирефлексивно.
5. Оъединение и пересечение произвольного числа рефлексивных (антирефлексивных, симметричных) есть отношение рефлексивное (антирефлексивное, симметричное).
6. Отношение отрицательно транзитивно тогда и только тогда, когда транзитивно.
7. Если бинарное отношение антирефлексивно и транзитивно, то оно асимметрично.
|
8. Если отношение асимметрично и отрицательно транзитивно, то оно транзитивно.
Примеры
1. Отношения «быть не старше», «быть похожим», являются рефлексивными.
2. Антирефлексивными являются следующие отношения: «быть моложе», «быть родителем», .
3. Отношения: «быть родственником», симметричные.
4. Отношение асимметрично.
5. Отношение антисимметрично.
6. Отношения: , , являются транзитивными.
Отношение «выиграть футбольный матч» транзитивным не является.
7. Отношение , заданное графом:
1 2
3,
является ацикличным.
Отношение , заданное графом
2
1 3,
ацикличным не является, так как , , .
|
|
Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...
Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!