Найти матрицу композиции (произведения)

Предмет: дискретная математика

Раздел: отношения и бинарные отношения на множествах, композиция отношений.

Шаг 1: Определение бинарного отношения

Дано множество \( M = \{1, 2, 4\} \) и бинарное отношение \( \rho = \{(a, b) \mid a - b \text{ делитель } b\} \). Бинарная операция означает, что \( a \) должен быть делителем \( b \), то есть \( b \% a = 0 \).

Шаг 2: Создание бинарного отношения \( \rho \) на множестве \( M \)

Теперь проверим для каждой пары элементов из множества \( M \), выполняется ли условие, что \( a \) — делитель \( b \):

• \( a = 1, b = 1 \) → \( 1 \) делитель \( 1 \) (выполняется).
• \( a = 1, b = 2 \) → \( 1 \) делитель \( 2 \) (выполняется).
• \( a = 1, b = 4 \) → \( 1 \) делитель \( 4 \) (выполняется).
• \( a = 2, b = 1 \) → \( 2 \) не делитель \( 1 \) (не выполняется).
• \( a = 2, b = 2 \) → \( 2 \) делитель \( 2 \) (выполняется).
• \( a = 2, b = 4 \) → \( 2 \) делитель \( 4 \) (выполняется).
• \( a = 4, b = 1 \) → \( 4 \) не делитель \( 1 \) (не выполняется).
• \( a = 4, b = 2 \) → \( 4 \) не делитель \( 2 \) (не выполняется).
• \( a = 4, b = 4 \) → \( 4 \) делитель \( 4 \) (выполняется).

Множество \( \rho \) = \( \{(1, 1), (1, 2), (1, 4), (2, 2), (2, 4), (4, 4)\} \).

Шаг 3: Построение матрицы бинарного отношения \( \rho \)

Матрица отношения \( \rho \), где на пересечении строки \( a \) и столбца \( b \) стоит 1, если пара \( (a, b) \) принадлежит отношению \( \rho \):

\[ R = \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix} \]

Шаг 4: Матрица композиции \( \rho \circ \rho \)

Для вычисления композиции бинарного отношения \( \rho \circ \rho \), требуется применить операцию к матрице множества \( R \). Для этого умножим матрицу \( R \) на саму себя.

\[ R \circ R = R \times R = \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix} \times \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix} \]

Проводим поэлементное умножение:

1. Элемент (1,1): \( 1 \cdot 1 + 1 \cdot 0 + 1 \cdot 0 = 1 \).
2. Элемент (1,2): \( 1 \cdot 1 + 1 \cdot 1 + 1 \cdot 0 = 2 \) (принимаем как 1, так как композиция).
3. Элемент (1,3): \( 1 \cdot 1 + 1 \cdot 1 + 1 \cdot 1 = 3 \) (пишем 1).
4. Элемент (2,1): \( 0 \cdot 1 + 1 \cdot 0 + 1 \cdot 0 = 0 \).
5. Элемент (2,2): \( 0 \cdot 1 + 1 \cdot 1 + 1 \cdot 0 = 1 \).
6. Элемент (2,3): \( 0 \cdot 1 + 1 \cdot 1 + 1 \cdot 1 = 2 \) (принимаем 1).
7. Элемент (3,1): \( 0 \cdot 1 + 0 \cdot 0 + 1 \cdot 0 = 0 \).
8. Элемент (3,2): \( 0 \cdot 1 + 0 \cdot 1 + 1 \cdot 0 = 0 \).
9. Элемент (3,3): \( 0 \cdot 1 + 0 \cdot 1 + 1 \cdot 1 = 1 \).

В итоге получаем композиционную матрицу:

\[ R \circ R = \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix} \]

Ответ

\[ \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix} \]

Матрица композиции (произведения) \( \rho \circ \rho \) имеет вид: