Определить свойства отношения R, заданного матрицей

Предмет: Дискретная математика Раздел: Отношения, матрицы отношений, операции над отношениями

Даны: Отношение \( R \), заданное матрицей:

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

Шаг 1. Проверим свойства отношения, основываясь на матрице

1. Рефлексивность (наличие единиц на главной диагонали): Главная диагональ матрицы: \( 1, 1, 1 \) (все единицы), значит, отношение рефлексивно.
2. Симметричность (матрица должна быть симметричной относительно главной диагонали):
   • Проверим сравнение элементов \( a_{ij} \) и \( a_{ji} \):
     • \( R_{12} = 0 \) и \( R_{21} = 0 \) (совпадают),
     • \( R_{13} = 1 \) и \( R_{31} = 1 \) (совпадают),
     • \( R_{23} = 1 \) и \( R_{32} = 0 \) (не совпадают).
     Следовательно, отношение не симметрично.
3. Антисимметричность (если \( a_{ij} = 1 \) и \( a_{ji} = 1 \), то \( i = j \)): В отношении \( R \), есть несоответствие в \( R_{23} \) и \( R_{32} \), что нарушает антисимметричность. Следовательно, отношение не антисимметрично.
4. Транзитивность (если \( R(i,j) = 1 \) и \( R(j,k) = 1 \), то \( R(i,k) = 1 \)): Проверим условия транзитивности для троек индексов:
   • \( R(1,3) = 1 \) и \( R(3,2) = 0 \), транзитивность нарушена.
   Следовательно, отношение не транзитивно.

Шаг 2. Выполним операции над отношением \( R \)

1. \( R^{-1} \) — обратное отношение

Это отношение, у которого строки и столбцы исходной матрицы поменяны местами (транспонирование).

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

2. \( \overline{R} \) — дополнение отношения

Это отношение, у которого единицы заменяются на нули, а нули — на единицы.

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

3. \( R \cup R \) — объединение отношений

Поскольку \( R \cup R \) — это просто \( R \), результат остается прежним:

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

4. \( R \cap R \) — пересечение отношений

Аналогично, пересечение отношения с самим собой — это просто \( R \).

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

5. \( R \cdot R \) — композиция отношений

Правила композиции отношений: если есть путь от элемента \( i \) до элемента \( j \) через промежуточные вершины, то \( R \cdot R(i, j) = 1 \). Выполним произведение матрицы \( R \) на саму себя:

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

Заменим все элементы, которые больше 0, на 1, так как в матрицах отношений используются значения 0 и 1:

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

Ответ:

1. Отношение \( R \) обладает следующими свойствами: - Рефлексивно. - Не симметрично. - Не антисимметрично. - Не транзитивно.
2. Выполненные операции:
   • \( R^{-1} = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 1 & 1 \end{pmatrix} \)
   • \( \overline{R} = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix} \)
   • \( R \cup R = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{pmatrix} \)
   • \( R \cap R = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{pmatrix} \)
   • \( R \cdot R = \begin{pmatrix} 1 & 0 & 1 \\ 1 & 1 & 1 \\ 1 & 0 & 1 \end{pmatrix} \)