Дискретная математика. Множества. Отображения. Отношения

80 Теорема 8.1. Пусть , Q R A B ⊂ × – бинарные отношения во множествах A и B , 2 A A θ ⊂ – отношение тождества на A ; [ ] ( ) , [ ] ( ) ij n m ij n m Q q R × × = = γ , [ ] ( ) A ij n n × θ = δ – матрицы отношений , , A Q R θ . Здесь ij δ – символ Кронекера . Тогда [ ] 0 , [ ] 1 n m n m A B × × ∅ = × = ; (8.2) [ ] [ ] [ ] [ ] [ ] [ ] [ ] Q R Q R Q R Q R ∪ = ∨ = + − × ; (8.3) [ ] [ ]&[ ] [ ] [ ] Q R Q R Q R ∩ = = × ; (8.4) [ ] [ ] 1 [ ] n m Q Q Q × = ¬ = − ; (8.5) [ \ ] [ ]& (1 [ ]) [ ] (1 [ ]) n m n m Q R Q R Q R × × = − = × − ; (8.6) 1 [ ] [ ] T Q Q − = ; (8.7) [ ] A n E θ = . (8.8) Здесь символ 0 n m × обозначает нулевую матрицу порядка n m × ; 1 n m × – матрица порядка n m × , все элементы которой равны 1 ; в выражениях [ ] [ ] Q R × символ × обозначает операцию поэлемент - ного умножения матриц ; , &, ∨ ¬ – булевские операции сложения ( дизъюнкции ), умножения ( конъюнкции ) и отрицания . Над матри - цами эти операции выполняются поэлементно . Напомним , что 0 0 0, 0 1 1 0 1 1 1; 0&0 0&1 1&0 0, 1&1 1; 0 1, 1 0. ∨ = ∨ = ∨ = ∨ = = = = = ¬ = ¬ = Индекс T обозначает операцию транспонирования матриц ; n E – единичная матрица порядка n .