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

74 ните данное определение композиции отношений с определением композиции отображений , данное гл . 2). Если 2 R A ⊂ – бинарное отношение , заданное на или во множестве A , то композиция : раз ... , 1 ( 1) n k n k n R R R R R R k n − = = ∀ ∈ − − o o o o 1442443 (7.4) называется n - й степенью отношения R . Считается , что 0 A R = θ , 1 R R = . Здесь A θ – отношение тождества на множестве A . Очевидно , что отношение тождества является нейтральным элементом относительно композиции , т . е . ( ) A B R A B R R R ∀ ⊂ × θ = = θ o o . (7.5) Ядром соответствия R A B ⊂ × называется отношение 1 2 Q R R A − = ⊂ o . Операции композиции и обращения отношений обладают следующими свойствами . Теорема 7.1 . Пусть соответствия 1 2 3 , , R R R в каждом из слу - чаев определены так , что имеют смысл все записанные операции . Тогда 1 2 3 1 2 3 1 2 3 1 2 1 3 1 2 3 1 2 1 3 1 1 2 1 2 1 1 1 1 1 1 2 2 1 1 1 2 1 2 1 1 1 1 2 1 2 1 1. ( ) ( ); 2. ( ) ( ) ( ); 3. ( ) ( ) ( ); 4. ; 5. ( ) ; 6. ( ) ; 7. ( ) . R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R − − − − − − − − − − − = ∪ = ∪ ∩ ⊂ ∩ ⊂ → ⊂ = ∪ = ∪ ∩ = ∩ o o o o o o o o o o o o (7.6)