Как сделать матрицу отношения

Обновлено: 07.07.2024

Пусть даны три множества: Х, Y и Z и два отношения: АÌХY и ВÌY Z. Тогда Композиция отношений А и В есть отношение С, состоящее из всех тех пар (Х, Z)ÌX Z, для которых существует такой Y Î Y, что пары (Х, у) Î А и (У, Z) Î В.

Композицию С отношений А и В записывают в виде: С = В. А.

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

На фото ниже приведен пример, который надо реализовать.

покажите ваше решение и мпросите что у вас не получилось. Оператор остаток от деления в Python выглядит так: %. то есть например 4%2 = 0, а 5%3=2 . Думаю - теперь у вас все получится

3 ответа 3

делим каждую строку вспомогательной матрицы на вектор A и проверяем остаток от деления на 1 :

Тест на рефлексивность:

Тест на транзитивность:

Тест этих функций:

Отношение возможно задать прямо как множество пар, на Питоне как

или каким-то предикатом (например вы использовали предикат a делит b ), в случае которого возможно создать множество пар (после нужной подготовки) как абстракцию множества (set comprehension):

После этого вы можете построить вашу таблицу, например, так:

и вывести её, например, командами

то же самое, что и

т.е. функция, которая возвращает True или False в зависимости от условия, в этом случае от условия a делит b (математически b ≡ 0 (mod a) или остаток деления b на a есть 0 ).

Функция product() из модуля itertools делает декартово произведение:

если мы его обозначим как result , тот же самый, как при выполнении команд

Ранее мы уже обсуждали отношения и их основные типы.
Объединяя отношения:
Предположим, что R — это отношение из множества A к B, а S — это отношение из множества B к C, комбинация обоих отношений — это отношение, которое состоит из упорядоченных пар (a, c), где a Є A и c Є C, и существует существует элемент b Є B, для которого (a, b) Є R и (b, c) Є S. Это представляется как RoS.

Обратная связь:
Отношение R определяется как (a, b) Є R из набора A в набор B, тогда обратное отношение определяется как (b, a) Є R из набора B в набор A. Обратное отношение представляется как R -1
R -1 = <(б, а) | (a, b) Є R>.

Дополнительное отношение:
Пусть R отношение из множества A к B, тогда дополнительное отношение определяется как — <(a, b)>, где (a, b) не равно Є R.

Представление отношений:
Отношения могут быть представлены в виде матриц и ориентированных графов.

Отношение как матрицы:
Отношение R определяется как от множества A к множеству B, тогда матричное представление отношения имеет вид M _R = [m _ij ], где

Свойства:

Отношение R является рефлексивным, если диагональные элементы матрицы равны 1.
Отношение R нерефлексивно, если диагональные элементы матрицы равны 0.
Отношение R является симметричным, если транспонирование матрицы отношений равно ее исходной матрице отношений. то есть M _R = (M _R ) T.
Отношение R является антисимметричным, если либо m _ij = 0, либо m _ji = 0, когда i ≠ j.
Отношение следует за свойством соединения, то есть объединением матриц M1 и M2 является M1 V M2, которое представлено как R1 U R2 в терминах отношения.
Отношение следует за свойством удовлетворения, если матрицей M1 и M2 является M1 ^ M2, которая представлена в виде отношения R1 Λ R2.

Отношения как ориентированные графы:

Направленный граф состоит из узлов или вершин, соединенных направленными ребрами или дугами. Пусть R — отношение из множества A к множеству B, определенному как (a, b) Є R, тогда в ориентированном графе это представляется как ребро (стрелка от a до b) между (a, b).

Свойства:

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

Пример:

Направленный граф отношения R = <(a, a), (a, b), (b, b), (b, c), (c, c), (c, b), (c, a)>представляется как:

Поскольку в каждом узле есть петля, она является рефлексивной, но она не является ни симметричной, ни антисимметричной, поскольку существует ребро от a до b, но нет противоположного ребра от b до a, а также направленное ребро от b до c в обоих направлениях. R не транзитивен, поскольку существует ребро от a до b и от b до c, но нет ребра от a до c.

Эта статья предоставлена Нитика Бансал .

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рассмотрим два конечных множества A =1,a₂,…,a_m> и B=1,b₂,…,b_n> и бинарное отношение . Определим матрицу размера m×n бинарного отношения Р по следующему правилу:

Полученная матрица содержит полную информацию о связях между элементами.

Любая матрица, состоящая из 0 и 1, является матрицей некоторого бинарного отношения.

ПРИМЕР 1. Матрица бинарного отношения , A=, заданного

на рисунке имеет вид

Основные свойства матриц бинарных отношений:

Если то и , где сложение осуществляется по правилам 0+0=0, 1+1=0+1=1+0=1, а умножение – обычным способом.

Итак,

Матрица получается перемножением соответствующих элементов из и : .

Если , то , где умножение матриц производится по обычному правилу умножения матриц, но произведение и сумма элементов – по определённым в свойстве 1 правилам.

Матрица обратного отношения Р -1 равна транспонированной матрице отношения Р: .

Если , то .

Матрица тождественного отношения id_A единична:

ПРИМЕР 2. Пусть - матрицы отношений P и Q. Тогда

ПРИМЕР 3. Если , то

Рассмотрим свойства отношений на языке матриц.

Пусть Р – бинарное отношение на множестве . Отношение Р:

рефлексивно, если на главной диагонали матрицы отношения расположены только единицы;

симметрично, если матрица симметрична относительно главной диагонали;

антисимметрично, если в матрице все элементы вне главной диагонали являются нулевыми;

транзитивно, если выполнено соотношение .

ПРИМЕР 4. Проверим, какими свойствами обладает отношение , А=, изображённое на рисунке.

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

Так как в матрице на главной диагонали имеются нулевые элементы, отношение Р не рефлексивно.

Несимметричность матрицы означает, что отношение Р не симметрично.

Для проверки антисимметричности вычислим матрицу .

Поскольку в полученной матрице все элементы, стоящие вне главной диагонали, нулевые, отношение Р антисимметрично.

Так как (проверьте!), то , то есть Р является транзитивным отношением.

Тут вы можете оставить комментарий к выбранному абзацу или сообщить об ошибке.

Читайте также: