1.6.4. Композиция отображений и отношений

Если даны два отображения h¹: XY и h²: YZ, у которых существуют элементы y_kY, принадлежащие h¹ и h², то можно найти их композицию, формирующую новое отображение

h=(h¹_h²)={(x, z)| если ₂(h¹)=₁(h²)},

где ₂(h¹) - проекция первого отображения на вторую компоненту, а ₁(h²)- проекция второго отображения на первую компоненту.

Если даны отношения r¹:XX и r²:XX, у которых существуют элементы x_kX, принадлежащие r¹ и r², то можно найти их композицию, формирующую новое отношение:

r=(r¹_r²)={(x_i¹, x_j²)| r(x_i¹, x_j²)=_k=1ⁿr¹(x_i¹, x_k¹)r²(x_k², x_j²)}.

Пример: даны множества 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

b

c

d



x

y

z

=

a

b

c

d

x

x

y

z

d

c

f

d

d

c

f

Ответ: h=(h¹_h²)={(a, d); (b, d); (c, c); (d, f)}(AC).

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

Ответ: операция умножения двух булевых матриц формирует матрицу нового отношения r. В таблицах приведены результаты исполнения этой операции.

	r^1	x1	x2	x3	x4		r^2	x1	x2	x3	x4		r	x1	x2	x3	x4
	x1	1	0	0	1		x1	0	1	0	1		x1	1	1	1	1
	x2	0	0	1	0		x2	1	0	0	0	=	x2	0	0	0	0
	x3	0	1	0	0		x3	0	0	0	1		x3	0	0	0	0
	x4	1	0	0	1		x4	1	0	1	0		x4	1	1	1	1