Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 29
Текст из файла (страница 29)
Пусть Л вЂ” отношение на А х В и  — отношение на В х С. Если М и )т' — матричные представления Л и Я соответственно, то М О АГ— матричное представление В о Л. ПРИМЕР 4.50. Пусть А = (аыаз), В = (ЬОЬз,Ьз) и С = (сиса,сз,с4). Пусть Л = ((ад,Ьз),(аыЬз),(аз,Ьз)) и Я = ((6ыс,),(6ыаз),(Ьз,сз),(6з,с1), (Ьз,сз)). Тогда матричными представлениями В и Я являются, соответственно, 174 ГЛАВА 4. Функции и матрицы ОПРЕДЕЛЕНИЕ 4.52. Пусть М вЂ” матрица размера п х и, в каждой строке и в каждом столбце которой только один элемент равен 1, а все остальные равны О. Такая матрица М называется маосрицей перестановок.
ТЕОРЕМА 4.53. Пусть М вЂ” матрица перестановок, а 1 — матрица размера и х 1 с различными элементами. Тогда М1 — матрица размера их 1, элементы которой образуют перестановку элементов матрицы 1. и 1' = М1. Рассмотрим а в бцой строке. ДОКАЗАТЕЛЬСТВО. Пусть 1 = а1 Поскольку СС2 аз С9 = [ М91 М92 Мсз ''' М179 ] а„ и имеется одна строка р, в которой М = 1 и М ь = О для й ф 2', то р-я строка матрицы 1' есть а.. Далее, поскольку Мь = О для всех й ф р, ас не может появиться ни в какой другой строке матрицы 1'. ПРИМЕР 4.54.
Пусть М = Тогда М1 = ° УПРАЖНЕНИЯ 1. Вычислите 5 ~ 3 О ( — 2 3 — 5 О] ( — 2 3 — 5 О]; г) д) (-2) 2. Пусть А = Вычислите а) А' в) АсАт б) Вычислите: в) АВ', г) АсВ; д) (АВ)с. а) АВ; б) ВА; 9 — 7 ] à — 3 21 3. ПустьА= ~ 7 ~ иВ= 7 51 а1 аз аз 4 4с. ( — 2 9] 79 Мсьаь 19=1 И-'И Е РАЗДЕЛ 4.Э. Матрицы 175 е) В'А', ж) А — В; з)  — А; н) 5А; к) 2 — ЗА. 4. ПустьА= ~ ~ и В= (1 0 5) Вычислите: в) 4г б) ВА а) АВ г) Вс; АсВ». е) (ВА)' Докажите справедливость или постройте контрпример для высказывания Ес- ли для матриц А, В и С имеет место АВ = АС, гпо В = С. Докажите справедливость или постройте контрпример для высказывания Ес- ли для матриц А и В произведение АВ равно нулевой матрице, то либо А, либо В является нулевой матрицей. Докажите, что если произведение матриц А и В определено, то (АВ)' = Вс 4г Докажите, что для отношений Л и Я на конечном множестве А = (ад, аз,..., а„) с матричными представлениями М и )У, соответственно, М~/Х является матричным представлением отношения Л О Я.
9. Докажите, что для отношений Л и Я на конечном множестве А = (ам аз, а„) с матричными представлениями М и йг, соответственно, Мд Х является матричным представлением отношения Л. и если М и Дг — матричные представления Л и Я, соответственно, тогда М О йг является матричным представлением отношения Я о Л. 11. Пусть А = (1,2,3,4,5), В = (6,7,8,9), С = (10,11,12,13), 1) = (П,сХ,О,*) Отношения Л С А х В, Я С В х С и Т С С х 11 определены как Л = ( (1, 7), (4, 6), (5, 6), (2, 8) ), Я = ((6, 10), (6, 11), (7, 10), (8, 13) ), Т = ((11,Ь),(10, Ь),(13,*),(12,П),(13,0)). Найдите матричные представления отношений Л, Я и Т, затем найдите матричные представления отношений а) Л'иЯ', б) ЯоЛ; в) Воя 'ия гоя; г) Л ' оЯ-', д) Т.(Б.Л); е) То Я; ж) (То Я) о Л.
12. Пусть А = ((Ь,а),(с,е),(д,ю), (~,о),(д,и)) и В = ((и,а),(ш,е), (х,1), (у,о), (з, и)). Найдите матричные представления А и В. Затем найдите матричные представления отношений а) А б) В в) А 'иВ; г) В 'оА, 13. Пусть А = (а, Ь,с,д, е) и Я, Т, У и Ъ' — отношения на А, где Я = ((а, а), (а, Ь), (Ь, с), (6, д), (с, е), (е, д), (с, а) ), Т = ((а, Ь), (Ь, а), (Ь, с), (6, д), (е, е), (сК, е), (с, Ь)), У = ((а, Ь), (а, а), (6, с), (Ь, 6), (е, е), (Ь, а), (с, 6), (с, с), (д, д), (а, с), (с, а) ), Ъ" = ((а, Ь),(Ь,с),(Ь,6), (е, е),(Ь,о),(с,Ь),(г(,д),(а,с),(с,а)). Найдите матричные представления Я, Т, бг $'. Затем, используя эти матри- 10. Докажите, что если Л вЂ” отношение на А х В, а Я вЂ” отношение на В х С 176 ГПЯВЯ 4. Функции и матрицы цы, определите какие из этих отношений а) симметричны; б) рефлексивны; в) транзитивны; г) антисимметричны.
14. Пусть А = (а,Ь,с,Ы,е) и В, Т, У и Ъ' — отношения на А, где В = ((а, а),(а, Ь),(6, с),(Ь,сЕ),(с, е),(е,с)),(с, а)), Т = 1(а, 6), (Ь, а),(6, с),(Ь, И), (е, е),(г(, е), (с, Ь)), 6Г = ((а, 6), (а, а), (6, с), (6, 6), (е, е), (Ь, а), (с, Ь), (с, с), (д, гЕ), (а, с), (с, а)), 'к' = ((а, Ь), (Ь, с), (Ь, Ь), (е, е), (Ь, а), (с, 6), (сЕ, г)), (а, с), (с, а)). а) Найдите матричное представление В, Т, У и Ъ'. б) Найдите матричное представление отношений В о Т и 6Го У. в) Найдите матричное представление отношений В П Т и У П Ъ'.
г) Найдите матричное представление бг Ь В. 15. Пусть А = (1,2,3,4,) В = (а,б,с). Найдите отношение на А х В с матричным представлением о о О 1 О] !! ~] б) [ '[ 16. Пусть А = (а, Ь, с, гг,е). Найдите отношение на А с матричным представле- нием а) б) в) г) 17. Пусть А = (а, Ь, с, И, е). Постройте графы со следующими матричными представлениями: 1 0 1 1 0 0 0 0 0 0 1 0 1 0 1 1 0 0 О 1 0 0 1 1 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 1 1 0 1 1 0 0 1 0 1 1 0 1 1 0 1 1 0 1 1 0 а) б) в) 18. Пусть А = (а,Ь,с,й,е). Постройте орграфы со следующими матричными представлениями: 1 0 0 1 0 0 1 0 0 0 0 1 1 0 0 1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 0 0 0 О 1 1 0 1 0 0 1 0 0 1 0 1 0 0 1 0 1 РАЗДЕЛ 4.4.
Мощность 177 в) а) 19. Для каждого отношения В, заданного в предыдущем упражнении матричным представлением, найдите В о В, используя соответствующее матричное представление. 4.4. МОЩНОСТЬ В этом разделе мы обсудим понятие мощности множества. Если множество ко- нечно, то его мощность есть просто количество содержащихся в нем элементов. Таким образом, для определения мощности множества нам достаточно подсчитать количество содержащихся в нем элементов. Сформулируем сказанное формально в виде следующего определения.
ОПРЕДЕЛЕНИЕ 4.55. Пустое множество есть конечное множество мощности О. Если существует взаимно однозначное соответствие между множеством А и множеством (1,2,3,...п), то А есть конечное мноокеетео мощности и. ПРИМЕР 4.56. Множество (а,р,г,х,х) имеет мощность 5, т.к. существует взаимно однозначное соответствие: (1,2,3,4,5) — (а,р, г,х, х), определяемое равенствами ф(1) = а, ф(2) = р, ф(3) = т, ф(4) = х, ф(5) = х. П ОПРЕДЕЛЕНИЕ 4.57. Множество А называется счетно бесконечны.н, если существует взаимно однозначное соответствие между множеством А и множе- ством положительных целых чисел (1,2,3,..., п,...). Множество называется счетным, если оно конечно или счетно бесконечно. ТЕОРЕМА 4.58. а) Пусть А и  — непересекающиеся конечные множества.
Тогда множество А о В конечно. Если А имеет мощность и и В имеет мощность гп, то А и В имеет мощность т+ и. б) Пусть А и  — непересекающиеся счетно бесконечные множества. Тогда А и  — счетно бесконечное множество. в) Пусть А и  — непересекающиеся счетные множества. Тогда Аи — счетное множество. ДОКАЗАТЕЛЬСТВО. а) Поскольку множества А и В конечны, то для положительных целых чисел и и гп существуют взаимно однозначные соответствия фг .
(1,2,3,...,п) — А и фз . (1,2,3,...,т) — В. Определим отображение ф: (1 2 3,...,т+ п) — А 0 В посредством равенств ф(Е) = фг(1г) для 1 ( й < и 1О11О О1О1О 1 О О О О; б) 1 1 О О 1 О 1 1 О 1 ОО1О ОО1О О О1ООО О1ОО О О О О О 1 О О 1 О О 1 О 1 О О 1 О О 1 1 О О О О 178 ГЛАВА 4. Функциц и матрицы и ф(п+ г) = фз(г) для 1 < 1 < ти. Функция ф устанавливает взаимно однозначное соответствие между множествами (1, 2, 3,..., ти + п) и А О В. 6) Поскольку А и  — счетно бесконечные множества, то существуют взаимно однозначные соответствия ф,; (1, 2, 3,... п,...) — А и фз . .(1, 2, 3,...
ги,...)— В. Определим функцию ф: (1,2,3,...) — А О В посредством равенств ф(п) = ф~ ((и+ 1)/2) в случае, когда и нечетно, и ф(п) = фз(п/2) в случае, когда п четно. Функция ф устанавливает взаимно однозначное соответствие между множествами (1,2,3,...) и А О В. в) Пусть А и  — непересекающиеся счетные множества. Единственный случай, который остался не рассмотренным в пунктах (а) и (6), — это когда одно из множеств А или В конечно, а другое счетно бесконечно. Предположим, что А — конечное множество. Тогда существует взаимно однозначное соответствие ф~ . (1, 2, З,...,п) — А. А поскольку  — счетно бесконечное множество, то существует фз . (1,2,3,...,ит,...) — В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
