Способы задания бинарных отношений

Способы задания бинарных отношений

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

Бинарные отношения, определяемые на конечном множестве обычно задаются списком (пар элементов), бинарной матрицей, или ориентированным графом.

Матрица бинарного отношения, заданного на множестве это квадратная матрицаС порядка n, в которой (гдеi – номер строки, j — номер столбца) определяется так:

Для любого множества М отношение Е, заданное единичной матрицей, в которой по главной диагонали стоят “1”, а остальные “0” – называется отношением равенства.

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

Способы задания бинарных отношений

Бинарное отношение можно задать различными способами:

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

2) Указать общие свойства, характеризующие данное отношение. Это наиболее общий способ, позволяющий задать практически любые отношения.

3) Графический способ, или задание отношения с помощью графа. В этом случае элементы множеств X и Y обозначаются точками, а элементы, связанные отношениями, соединяются направленными стрелками (рис. 2.1а). В случае рисуется одно множество (рис. 2.1б).

а) б)
Рис.2.1. Граф бинарного отношения

4) Матричный способ. При этом отношение описывается матрицей, количество столбцов которой соответствует количеству элементов множества X, а строк – Y. Элемент матрицы, находящийся на пересечении j столбца и i строки равен 1, если соответствующие элементы множеств X и Y связаны бинарным отношением, и 0 — в противном случае.

Если отношение R задано в множестве X, то матрица будет квадратной.

Если в матрице отношения возникает нулевой столбец, то это значит, что соответствующий элемент не связан ни с одним другим элементом этим отношением. То же самое можно сказать про нулевую строку.

Читайте также:  Just another wordpress site как убрать

Область определения отношения R – это подмножество всех элементов х множества Х ,для которыхнайдется элемент y, связанный с данным элементом отношением R.

.

Область значения отношения R – подмножество всех элементов y множества У, для которых найдутся элементы x, связанные с y отношением R ().

Пример:

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

Заслуживают внимания три частных случая отношений в Х:

1) полное (универсальное) отношение Р = Х ´ X, которое имеет место для каждой пары элементов из Х (например, отношение «учиться в одной группе» на множестве студентов данной группы);

2) тождественное (диагональное) отношение Е, равносильное х=х (например, равенство на множестве действительных чисел);

3) пустое отношение, которому не удовлетворяет ни одна пара элементов из Х (например, отношение «быть братом» на мно­жестве женщин).

Полному отношению соответствует матрица, все клетки кото­рой заполнены единицами, тождественному — единичная матрица, пустому — нулевая матрица. Графы полного, тождественного и пустого отношений изобра­жены на рис. 2.2 (для пустого отношения граф состоит из изолиро­ванных вершин).

а) б) в)
Рис.2.2. Графы полного (а), тождественного (б) и пустого (в) отношений.

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Сдача сессии и защита диплома — страшная бессонница, которая потом кажется страшным сном. 9270 — | 7454 — или читать все.

Существует четыре разных способа задания отношений:

ОПИСАНИЕ ВЫБОРА НА ЯЗЫКЕ БИНАРНЫХ ОТНОШЕНИЙ

Задание матрицы пред почтении

Задание графа предпочтении

преимущества каждого проявляются при разных характеристиках множества X.

Первый, очевидный, способ состоит в непосредственном перечислении таких пар. Ясно, что он приемлем лишь в случае конечного множества X.

Второй удобный способ задания отношения R на конечном множестве — матричный. Все элементы нумеруются, и матрица отношения R определяется своими элементами aij(R)=<1: xiRxj; 0: xiRxj] для всех i и j. Известным примером такого задания отношений являются турнирные таблицы (если ничьи обозначить нулями, как и проигрыш, то матрица изобразит отношение "xi — победитель xj").

Читайте также:  Как снести виндовс 10 на компьютере

Третий способ-задание отношения графом. Вершинам графа G(R) ставят в соответствие (пронумерованные) элементы множества X, и если xiRxj, то от вершины xi проводят направленную дугу к вершине xj, если же xiRxj, то дуга отсутствует.

Для определения отношений на бесконечных множествах используется четвертый способ — задание отношения R сечениями. Множество R + (х)= Х|(у, х) R> называется верхним сечением отношения R, а множество R (х)= Х|(x, y) R> нижним сечением. Иначе говоря, верхнее сечение — это множество всех у X, которые находятся в отношении yRx с заданным элементом х X, а нижнее сечение- множество всех у X, с которыми заданный элемент х находится в отношении R. Отношение однозначно определяется одним из своих сечений.

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

Пример 1. Полное бинарное отношение U:

3) граф G(U) такой, что его дуги соединяют любую пару вершин;

Пример 2. Диагональное отношение Е:

в Е входят только пары с одинаковыми номерами: хiЕхj верно только при i =j;

граф G(E) такой, что каждая его вершина имеет петлю, а остальные дуги отсутствуют;

Отношения эквивалентности, порядка и доминирования

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

Для их определения нам понадобятся некоторые свойства отношений вообще. Бинарное отношение R на множестве Х называется:

антирефлексивным, если xх X (т.е. R может выполняться только для несовпадающих элементов);

отрицательно транзитивным, если отношение R транзитивно;

Читайте также:  Как восстановить файлы chk на флешке

сильно транзитивным, если отношение R одновременно транзитивно и отрицательно транзитивно.

Теперь можно охарактеризовать отношения, используемые в теории выбора.

Отношение R на множестве Х называется отношением эквивалентности (обозначение

), если оно рефлексивно, симметрично и транзитивно. Примеры отношений эквивалентности: "быть четным", "иметь одинаковый остаток от деления на 3" — на множестве натуральных чисел; "быть одноклассниками" — на множестве учеников данной школы; "быть подобными" -на множестве многоугольников. Задание отношения эквивалентности равносильно разбиению множества Х на непересекающиеся классы (X= |iXi; Xi Xj= при i j) эквивалентных элементов: х

у тогда и только тогда, когда х, у X, (т.е. если х и у принадлежат одному классу эквивалентности),

Верхнее сечение отношения Р есть первый квадрант с началом в точке х; теперь понятно, как находится паретовское множество альтернатив: в паретовское множество включаются альтернативы, верхнее сечение которых пусто.

В общем же случае выделение наиболее предпочтительных альтернатив возможно с помощью понятия оптимальности по отношению R, позволяющего придавать разный смысл понятию "наилучший" (задавая разные отношения R). Элемент х Х называется мажорантой по отношению R на X, если для всех у Х выполнено условие yRх. Множество X+(R) всех мажорант называется множеством R-оптимальных элементов.

Ссылка на основную публикацию
Сколько рублей получают ютуберы
Видеохостинг YouTube — не только развлекательная площадка, но и хороший источник дохода. Тысячи пользователей выкладывают ролики, пытаясь привлечь внимание аудитории....
Самый дорогой самсунг 2018
Samsung / Самсунг - южнокорейская компания, ведущий производитель смартфонов в мире. В первом квартале 2018 года доля Самсунг на мировом...
Самый лучший smart tv
Ежегодные обновления телевизионных технологий делают телевизоры уже больше, чем обычным экраном для демонстрации каналов. Растет популярность функции Smart TV, которая...
Сколько света мотает компьютер
Выбирая комплектующие для персонального компьютера (ПК) обычно обращают внимание на производительность и объем памяти, порой забывая о том, сколько же...
Adblock detector