Дискретная математика

16 Образом элемента хвА при отношении R называется множество 1тц(х) элементов уe S таких, что xRy, т.е. 1тк(х) = {уеВ: (x,y)eR}. Прообразом элемента уеВ при отношении R называется множество kei-ft(yj элементов л: е/4 таких, что xRy, т.е. кегц(у) = {х £ А: (x,y) €R}. Единичным отношением Е (или I) называется бинарное отношение на множестве А такое, что Е={{а,а): аеЛ}. Пустое отногиение определяется пустым подмножеством множества АуВ. Универсальное отношение U на множествах А и В совпадает с АхВ: и={(а,Ь}: аеАк ЬеВ}. Способы задания отношения Л: 1) перечислением упорядоченных пар (х,у), принадлежащих й; 2) предикатом Р: R={(x,y): Р(х,у)}-, 3) порождающей процедурой; R={(x,y): x=f, у-ф)', 4) бинарное отношение R на конечном множестве А можно задать матрицей отношения. Пусть имеем множество A-{ai, а2, ..., Ял}, тогда Aiompui^a отношения R есть пт матрица М;г =(mij) такая, что [1, если (oj.a Л е R, 1о, если (ajiOj) i R. 5) отношение R на конечных множествах А я В тоже можно задать пхт матрицей отношения Мя =(mij), здесь п w т числа элементов в множествах Л и S соответственно и [1, если (ai.bf ) е R, Qj € А, Ь, е В, 171 \ " {^0, если (ai,bj)iR, а,- е А, bj е В. 6) отношение R на конечных множествах А к В можно задать п^т (логической) матрицей отношения вида L r =(1ф, здесь и и га числа элементов в множествах Л и S соответственно и {и, если {a^,bj)s.R, а,- е А, bj еВ, " |„7, если {a,,bj)i R, а^ s А, bj е В. 7) бинарное отношение R на конечном множестве А можно задать графом. Пусть A={aj, а2, ..., а„}, тогда элементы а, (1< i < п) рассматриваются как вершины графа. Если (a,.aj}eR. то из вершины Oi идёт дуга в вершину Oj, иначе - из а,- нет дуги в а^. В результате получим орграф, представляющий отношение R. Ясно, что бинарное отношение R на конечных множествах А и В тоже можно задать графом, выбирая в качестве вершин элементы из АиВ. При этом