Матрица бинарных отношений

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

Рассмотрим два конечных множества

, и бинарное отношение

Определим матрицу бинарного отношения [P]=(p_ij) размера mxn по следующему правилу:

Пример

A={1, 2, 3},

P={(1, 2), (2, 3), (3, 2), (1, 1)}

Если и даны матрицы этих отношений [P]=(p_ij), [Q]=(q_ij), то

1) [P Q]=(p_ij+q_ij)

+ - здесь логическое сложение (дизъюнкция)

2) [P Q]=(p_ijq_ij)

умножение выполняется обычным способом

Пример

3) Если , , то

умножение выполняется по обычным правилам умножения матриц

Пример

Число строк первой матрицы должно быть равно числу столбцов второй матрицы.

4) матрица обратного отношения равна транспонированной матрице

транспонированная матрица – строки становятся столбцами

Пример

если мы вернемся к свойствам отношений, то

1) у рефлексивного отношения на главной диагонали единицы

2) у антирефлексивного отношения на главной диагонали нули

3) в симметричном отношении ,

То есть по виду матрицы можно делать выводы относительно свойств отношений.