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

82 Доказательство . По условию теоремы ( ) [ ] 1 ( , ) ( , ) [ ] 1 i j ij i j i j ij a A b B Q a b Q a b R R ∀ ∈ ∀ ∈ = ↔ ∈ → ∈ ↔ = . Это значит , что [ ] [ ] Q R ≤ . Теорема 8.3. Пусть , Q A B R B C ⊂ × ⊂ × , где множества , A B определены так же , как ранее , а C – конечное множество , равное 1 { ,..., } k C c c = . Тогда [ ] [ ] [ ] Q R Q R = o o . (8.10) Здесь символ o в правой части равенства обозначает опера - цию композиции матриц , т . е . операцию , которая выполняется по правилу : 1 ([ ] [ ]) ( & ) m ij is sj s Q R q r = = ∨ o . (8.11) Это правило такое же , как обычное правило умножения мат - риц , но с заменой операции сложения чисел Σ на дизъюнкцию ∨ , а операции умножения на конъюнкцию &. Заметим , что Q R A C ⊂ × o и [ ] Q R o – матрица порядка n k × . Доказательство . 1 1, 1, ([ ] [ ]) 1 ( , ) (( , ) & ( , ) ) 1, ( 1& 1) 1, (( & 1) ( & ) 1 ([ ] [ ]) 1. ij i j l i l l j il lj m il lj is sj ij s i n j k Q R a c Q R b B a b Q b c R l m q r l m q r q r Q R = ∀ ∈ ∀ ∈ = ↔ ∈ ↔ ∃ ∈ ∈ ∈ ↔ ∃ ∈ = = ↔ ↔ ∃ ∈ = ↔ ∨ = ↔ = o o o Последнее равенство получено по определению операции композиции матриц (8.11). Проиллюстрируем равенства (8.2) – (8.10) примерами . Пример 8.1. Допустим , что { } { } { } 1 2 3 1 2 3 4 , , , , , , , ( , ) : 1,3& 1,4 ; i j A a a a B b b b b A B a b i j = = × = = =