Композиция множеств

[Nogin Anton]

Подскажите пожалуйста алгоритм нахождения композиции двух множеств..

Я запутался и у меня ничего не получается..

Например, для множеств $A=\{<a,a>,<b,e>,<c,k>,<f,g>\}$ и $B=\{<a,d>,<c,b>,<g,f>,<e,c>,<b,b>\}$

композиция $A\circ B$ должна состоять из кортежей длины 2.. а как получаются сами кортежи не пойму..

Заранее большое спасибо за помощь!

[Someone]

Берёте в первом множестве первый кортеж (у Вас это $\alpha=\langle a,a\rangle$). Во втором множестве находите все кортежи, у которых первый элемент совпадает со вторым элементом выбранного кортежа (в данном случае такой один, это $\beta=\langle a,d\rangle$). И составляете кортежи из первого элемента кортежа $\alpha$ и второго элемента кортежа $\beta$ (получится $\langle a,d\rangle$; если во втором множестве найдётся не один подходящий кортеж, то столько же кортежей мы и получим). Затем в первом множестве берём второй кортеж $\langle b,e\rangle$...

P.S. Угловые скобки - это не <...>, а \langle...\rangle.

[Nogin Anton]

Большое спасибо за пояснения!

у меня что-то не сходится с ответом..

$A\circ B=\{ \langle a,b\rangle ,\langle b,b\rangle , \langle c,b\rangle \}$

[Nogin Anton]

Всё получилось! Большое спасибо

Посмотрите пожалуйста такое:

Даны соответствия $\Gamma$ и $\Delta$. Нужно найти композицию $\Gamma ^{-1} \circ \Delta ^{-1}$



Перевёл всё в буквенный вид:

$\Gamma =\{\langle x_1,y_1\rangle ,\langle x_2,y_5 \rangle, \langle x_3,y_1 \rangle ,\langle x_3 , y_5 \rangle \}$

$\Delta =\{ \langle y_1, w_1\rangle ,\langle y_1,w_3 \rangle ,\langle y_2,w_1 \rangle , \langle y_2,w_2 \rangle , \langle y_3,w_2 \rangle \}$

Теперь инвертировал их:

$\Gamma ^{-1}=\{ \langle y_1,x_1 \rangle ,\langle y_5,x_2 \rangle , \langle y_1,x_3 \rangle ,\langle y_5,x_3 \rangle \}$

$\Delta ^{-1}=\{ \langle w_1,y_1 \rangle ,\langle w_3, y_1 \rangle , \langle w_1, y_2 \rangle , \langle w_2,y_2 \rangle , \langle w_2, y_3 \rangle \}$

Беру первый кортеж из $\Gamma ^{-1}$, и ищу в $\Delta ^{-1}$ кортеж в котором первый элемент совпадает со вторым элементом выбранного кортежа.. таковых вообще нет..

[arseniiv]

(А зачем их назвали соответствиями, если они как-то не очень отличаются от отношений?)

Могли бы и в графической форме всё найти, раз прям так и дано.

[Nogin Anton]

Так у меня в буквенной не получилось

Можно ли правило, описанное someone, использовать для соответствий?

[arseniiv]

Насколько я понял, текущие «соответствия» вообще ничем от просто отношений не отличаются. Обычно «соответствие» вроде бы однозначным должно быть, а тут этого нет.

-- Чт июн 09, 2011 14:59:45 --

И вообще, даже если бы это были, например, какие-нибудь функции из узкого класса, они всё ещё остались бы отношениями, и потому

Nogin Anton в сообщении #455943 писал(а):

Можно ли правило, описанное Someone, использовать для соответствий?

конечно, можно.

[Nogin Anton]

Только скорее всего в задании опечатка, потому что получается пустое множество..

А если в композиции элементы поменять местами, то будет вроде норм..