Дискретная математика: Учебное пособие. Часть I - Основания дискретной математики, страница 14

h=(h¹Äh²)={(y¹;x₁¹;x₂¹;...x_n¹;y²;x₁²;x₂²;...x_n²)| yÎ(Y¹ÈY²), x_i¹ÎX¹; x_i²ÎX²}. Операторная запись прямого произведения h:=product(h¹, h²).

Композиция отображений. Если для двух отображений h¹: X®Y и

 h²: Y®Z существуют элементы y_kÎY, принадлежащие  h¹(x_i; y_k) и h²(y_k; z_j), то можно найти отображение: h=(h¹×h²)={(x, z)| xÎX, yÎY, p₂(h¹)=p₁(h²)} Í(XÄZ), где p₂(h¹)- проекция первого отображения на вторую компоненту (образ отображения h¹), а p₁(h²)- проекция второго отображения на первую компоненту (прообраз отображения h²). Если образ отображения h¹ есть кортеж, то прообраз отображения h² есть равный ему кортеж.

Пример: пусть даны A={a, b, c, d}, B={x, y, z}, C={c, d, e, f} и отображения

 h¹={(a; x); (b; x); (c; y); (d; z)}Í(AÄB),

 h²={(x; d); (y; c); (z; f)}Í(BÄC).

Тогда h=(h¹×h²)={(a, d); (b, d); (c, c); (d, f)}Í(AÄC).

Композицию отображений удобно представлять таблицами, верхние строки которых представляют прообразы отображения, а нижние образы отображения:

Композиция отношений. . Если для двух отношений r¹ и r² существуют элементы x_kÎX, которые принадлежат r¹(x_i; x_k) и r²(x_k; x_j), то можно найти отношение r=(r¹×r²), т. е. R={r(x_i, x_j)| r¹(x_i, x_k)=r²(x_k, x_j), x_i, x_j, x_kÎX, }, значения

r(x_i; x_j) которого определяются по правилу произведения двух булевых матриц:

 r(x_i; x_j)=Úr¹(x_i; x_k)×r²(x_k; x_j).

Пример: Даны отношения r¹ и r². Найти r= (r¹× r²).