[Список тем] [Вступление к этой теме] Страницы темы: [1] [2]

Композиция бинарных отношений. Булево произведение матриц

Определение 1
Пусть — бинарное отношение на Х х Y, — бинарное отношение на Y x Z. Определим композицию бинарных отношений о как бинарное отношение на Х х Z, заданное следующим:
x o z y((xy) (yz)) ≡ 1

Очевидно, что композиция ассоциативна, т. е.
( o ) o o( o )
и, вообще говоря, не коммутативна, т.е. существуют и такие, что
o ≠ o
Отмеченное выше соответствие между бинарными отношениями на конечных множествах и булевыми матрицами порождает операцию булева умножения ″0-1″ матриц. (Композиции отношений соответствует булево произведение матриц.) Оно определено следующим правилом:
Определение 2
Пусть А — булева матрица размера m х р с элементами A(ij), В — булева матрица размера р х n с элементами B(ij).
Булевым произведением матриц A и В называется булева матрица AB размера m х n с элементами (A x B)ij, определенными равенством
                  p
(AB)ij= (A)ik(B)kj
                 k=1
Пример. Пусть

Ясно, что булево умножение матриц ассоциативно, т. е.   (A B) C = A (B C)
и, вообще говоря, не коммутативно,
т. е. существуют такие матрицы А и В, для которых AB ≠B A

    Замечания и вопросы в конце параграфа.
  1. Мы определили булевы операции для двуместных отношений. Ясно, что они определяются точно так же для отношений любой местности.

  2. Как сказывается на матрице Аa бинарного отношения а на ХxY изменение нумерации X; изменение нумерации У?

  3. Приведите пример таких отношений, для которых o ≠ o

  4. Приведите пример таких булевых матриц, для которых AB ≠B A

  5. Приведите пример таких отношений, для которых o = o

  6. Приведите пример таких булевых матриц, для которых A B=BA

  7. Пусть А — квадратная n х n булева матрица. Определим ее булевы натуральные степени, положив

    [Список тем] [Вступление к этой теме] Страницы темы: [1] [2]