суперпозиция отношения

[OcbMuHor]

Всем доброго времени суток. Собственно есть задача, которую я должен решить, но я не прошу решить, а только разъяснить мне что же такое эта суперпозиция и с чем ее едят. Откровенно говоря, определение в лекции мне ни сколько не облегчило задачу. Вот что у меня есть:
Суперпозицией отношений $\[\rho _1^m,\rho _2^m,...,\rho _{n - 1}^m,{\sigma ^n}\]$ называется m-отношение $\[{\theta ^m} = {\sigma ^n}(\rho _1^m,\rho _2^m,...,\rho _{n - 1}^m)\]$ на множествах $\[{A_1},{A_2},...,{A_m}\]$ такое, что $\[{\theta ^m} = (a_1^i,a_2^i,...,a_m^i)\]$ тогда и только тогда, когда найдутся элементы $\[b_1^j \in {B_1},b_2^j \in {B_2},...,b_{n - 1}^j \in {B_{n - 1}}\]$, для которых $\[\rho _s^m(a_1^i,a_2^i,...,a_{m - 1}^i,b_s^j)\]$ при любом $\[s = 1,2,...,n - 1\]$, причем, $\[{\sigma ^n}(b_1^j,b_2^j,...,b_{n - 1}^j,a_m^i)\]$
Отношения заданы матрицей.
Вот что я понял: нужно сопоставить каждый ряд отношений $\[\rho _1^5,\rho _2^5,...,\rho _5^5\]$, заданых матрицей ( 5 отношений, 5 столбцов в каждой матрице) каждому ряду отношения $\[{\sigma ^6}\]$ на предмет выполнимости условия $\[\rho _s^m(a_1^i,a_2^i,...,a_{m - 1}^i,b_s^j) \wedge {\sigma ^n}(b_1^j,b_2^j,...,b_{n - 1}^j,a_m^i),s = 1,2,...,n - 1\]$. Т.е. это ряды матриц $\[\rho _1^5,\rho _2^5,...,\rho _5^5\]$ где 5-й элемент равен 5-му элементу матрицы $\[{\sigma ^6}\]$ и при этом 6-й элемент $\[{\sigma ^6}\]$ равен 5-му элементу $\[\rho _1^5,\rho _2^5,...,\rho _5^5\]$ (в данном конкретном примере)?

[OcbMuHor]

вопрос не достоин ответа?

[paha]

любой нормальный человек прочтя

OcbMuHor в сообщении #388262 писал(а):

уперпозицией отношений $\[\rho _1^m,\rho _2^m,...,\rho _{n - 1}^m,{\sigma ^n}\]$ называется m-отношение $\[{\theta ^m} = {\sigma ^n}(\rho _1^m,\rho _2^m,...,\rho _{n - 1}^m)\]$ на множествах $\[{A_1},{A_2},...,{A_m}\]$ такое, что $\[{\theta ^m} = (a_1^i,a_2^i,...,a_m^i)\]$

не будет читать дальше (если это ему не надо почему-то)

напишите попонятней... в случае, допустим $m=1$, $n=2$ и $A$ двухэлементное (тогда матрица 2х2) будет
чтобы можно было хоть что-то увидеть глазами

и множества $B$ непонятно откуда взялись:((

-- Пт дек 17, 2010 21:26:24 --

и напомните, что такое $m$-отношение, чтоб не гуглить

[OcbMuHor]

Цитата:

не будет читать дальше (если это ему не надо почему-то)

почему не будет?

Цитата:

и множества $\[B\]$ непонятно откуда взялись:((

Это определение из конспекта лекций по дискретной математике. Я его не понимаю и спросить мне не у кого. Хорошо что есть интернет. Вот задача:
Для отношений $\[{R_1},{R_2},{R_3},{R_4},{R_5},S\]$ на множестве З, заданных с помощью матрицы найти суперпозицию $\[S({R_1},{R_2},{R_3},{R_4},{R_5})\]$, наличие функциональности в суперпозиции.
$\[{R_1} = \begin{array}{*{20}{c}} 1&3&1&1&4 \\ 2&4&2&2&3 \\ 4&1&3&2&7 \\ 4&9&4&4&1 \end{array}\]$,$\[{R_2} = \begin{array}{*{20}{c}} 2&4&4&2&3 \\ 1&3&1&1&7 \\ 3&2&3&5&2 \\ 1&3&1&1&2 \\ 4&1&3&2&5 \end{array}\]$,$\[{R_3} = \begin{array}{*{20}{c}} 4&1&3&2&4 \\ 1&3&1&1&5 \\ 2&3&4&3&2 \\ 3&3&4&1&5 \end{array}\]$,$\[{R_4} = \begin{array}{*{20}{c}} 1&3&1&1&2 \\ 6&8&5&5&2 \\ 4&1&3&2&1 \end{array}\]$,$\[{R_5} = \begin{array}{*{20}{c}} 1&3&1&1&3 \\ 3&2&1&4&4 \\ 4&1&3&2&9 \\ 1&3&1&1&4 \end{array}\]$,$\[S = \begin{array}{*{20}{c}} 1&1&2&4&3&6 \\ 4&2&5&2&4&8 \\ 7&5&4&1&9&7 \\ 2&4&3&1&6&7 \\ 4&2&5&2&3&9 \\ 4&7&5&2&3&5 \\ 7&5&4&1&9&8 \end{array}\]$

[paha]

OcbMuHor в сообщении #388587 писал(а):

почему не будет?

потому что много букв и среди них мало знакомых

paha в сообщении #388535 писал(а):

и напомните, что такое $m$-отношение, чтоб не гуглить

-- Сб дек 18, 2010 11:07:46 --

OcbMuHor в сообщении #388587 писал(а):

Это определение из конспекта лекций по дискретной математике. Я его не понимаю и спросить мне не у кого.

по всей видимости, Вы неудачно законспектировали -- я не могу из этих объяснений понять

Давайте наметим такой план
1) что такое "отношение" и как его задать с помощью матрицы

2) что такое m-отношение и как его задать с помощью матрицы

3) что такое суперпозиция отношений -- на каком множестве она задается, как его задать с помощью матриц

4) что такое "функциональность в суперпозиции"

[OcbMuHor]

Цитата:

по всей видимости, Вы неудачно законспектировали -- я не могу из этих объяснений понять

Я к сожалению не имею физической возможности посещать лекции, и по этой причине преподаватели идут на встречу, высылая конспекты своих лекций на мой email. Так что конспект составлен именно преподавателем.

1. Под n-арным отношением или n - отношением $\[{\rho ^n}\]$ на множествах $\[{A_1},{A_2},...,{A_n}\]$ понимается закон (характеристическое свойство), выделяющий в декартовом произведении $\[{A_1} \times {A_2} \times ... \times {A_n}\]$ некоторое подмножество $\[\rho _{{A_1},...,{A_n}}^n \subseteq {A_1} \times {A_2} \times ... \times {A_n}\]$, называемое графиком (n-мерным) отношения $\[{\rho ^n}\]$. Если $\[{A_1} = {A_2} = ... = {A_n} = A\]$, то говорят об n-отношении $\[{\rho ^n}\]$ на множестве А с графиком $\[\rho _A^n \subseteq {A^n}\]$.
2.Так как n-отношение $\[{\rho ^n}\]$ можно рассматривать как подмножества декартова произведения $\[{A_1} \times {A_2} \times ... \times {A_n}\]$, существуют различные способы задания n-отношений, аналогичные способам задания множеств. Так график $\[\rho _{{A_1},...,{A_n}}^n\]$ удобно задавать матрицей, строками которой являются векторы отношения $\[{\rho ^n}\]$.
3. определение суперпозиции детально описано в первом топе. Вот пример (тоже из конспекта лекций):
$\[\rho _1^3 = \begin{array}{*{20}{c}} 0&1&1 \\ 1&0&0 \\ 1&1&1 \end{array}\]$, $\[\rho _2^3 = \begin{array}{*{20}{c}} 0&0&0 \\ 0&1&0 \\ 1&1&1 \\ 1&1&1 \end{array}\]$, $\[\rho _3^3 = \begin{array}{*{20}{c}} 0&0&1 \\ 0&1&1 \\ 1&1&0 \end{array}\]$, $\[{\sigma ^4} = \begin{array}{*{20}{c}} 0&0&0&0 \\ 1&0&1&1 \\ 1&1&0&0 \\ 1&1&1&1 \end{array}\]$, $\[{\theta ^3} = {\sigma ^4}(\rho _1^3,\rho _2^3,\rho _3^3) = \begin{array}{*{20}{c}} 0&1&1 \\ 1&1&0 \\ 1&1&1 \end{array}\]$
4. Отношение $\[{\varphi ^n}\]$ на множествах $\[{A_1},{A_2},...,{A_n}\]$ называется функциональным при отображении его в бинарное отношение $\[{\varphi ^2}\]$ на множествах $\[({A_1} \times {A_2} \times ... \times {A_n})\]$ и $\[{A_n}\]$, если для каждой последовательности элементов $\[(a_i^1,a_i^2,...,a_i^{n - 1}) \in {A_1} \times {A_2} \times ... \times {A_{n - 1}}\]$ сечение $\[{S^n}a_i^1,a_i^2,...,a_i^{n - 1}({\varphi ^n})\]$ содержит не более одного элемента $\[a_i^{(n - }) \in {A_n}\]$.Очепятка. Что должно быть на самом деле - могу только догадываться, либо $\[a_i^{(n - 1)} \in {A_n}\]$, либо $\[a_i^n \in {A_n}\]$. [url]http://ru.math.wikia.com/wiki/Функциональное_отношение[/url] определение простое и понятное. Поскольку суперпозиция отношений тоже является отношением(!?) то и свойствами обладает теми же.

[paha]

OcbMuHor в сообщении #388830 писал(а):

Так график $\[\rho _{{A_1},...,{A_n}}^n\]$ удобно задавать матрицей

Если множества $A_i$ конечны и каждое состоит из $k_i$ элементов -- каких размеров будет матрица?

OcbMuHor в сообщении #388830 писал(а):

определение суперпозиции детально описано в первом топе

и оно непонятное: откуда там взялись множества $B$?

OcbMuHor в сообщении #388830 писал(а):

Вот пример (тоже из конспекта лекций)

в этом примере матрицы, задающие отношения, состоят из 0 и 1, как и должно быть. В Вашем же примере там натуральные числа, что непонятно

[mkot]

paha в сообщении #388844 писал(а):

в этом примере матрицы, задающие отношения, состоят из 0 и 1, как и должно быть. В Вашем же примере там натуральные числа, что непонятно

Тут как раз всё в порядке. Матрица строится, как я понял следующим образом, это просто список тех наборов $(a_1, \ldots, a_n) \in A_1 \times \ldots \times A_n$ на которых отношение выполнено.

paha в сообщении #388844 писал(а):

и оно непонятное: откуда там взялись множества $B$?

Смею предположить, что для отношений $\rho _1^m,\rho _2^m,...,\rho _{n - 1}^m,{\sigma ^n}$ верно, что
$\rho_1^m \subseteq A_1 \times \ldots \times A_{m-1} \times B_1$,
$\rho_2^m \subseteq A_1 \times \ldots \times A_{m-1} \times B_2$,
...
$\rho_{n-1}^m \subseteq A_1 \times \ldots \times A_{m-1} \times B_{n-1}$,
$\sigma^n \subseteq B_1 \times \ldots \times B_{n-1} \times A_m$.

После того, как мы вкурили на чём определены отношения уже можно осознать, что говорится здесь:

OcbMuHor в сообщении #388262 писал(а):

Суперпозицией отношений $\[\rho _1^m,\rho _2^m,...,\rho _{n - 1}^m,{\sigma ^n}\]$ называется m-отношение
$\[{\theta ^m} = {\sigma ^n}(\rho _1^m,\rho _2^m,...,\rho _{n - 1}^m)\]$ на множествах $\[{A_1},{A_2},...,{A_m}\]$ такое, что $\[{\theta ^m} = (a_1^i,a_2^i,...,a_m^i)\]$ тогда и только тогда, когда найдутся элементы $\[b_1^j \in {B_1},b_2^j \in {B_2},...,b_{n - 1}^j \in {B_{n - 1}}\]$, для которых $\[\rho _s^m(a_1^i,a_2^i,...,a_{m - 1}^i,b_s^j)\]$ при любом $\[s = 1,2,...,n - 1\]$, причем, $\[{\sigma ^n}(b_1^j,b_2^j,...,b_{n - 1}^j,a_m^i)\]$

Меня правда смущают верхие индексы у букв $a$ и $b$, но на них закроем глаза.

Тогда уже и понятно что делать.

[paha]

mkot в сообщении #388883 писал(а):

Тут как раз всё в порядке. Матрица строится, как я понял следующим образом, это просто список тех наборов $(a_1, \ldots, a_n) \in A_1 \times \ldots \times A_n$ на которых отношение выполнено.

я не понимаю(((
приведите пример простой 2х2

[arseniiv]

(Оффтоп)

Да и вообще, разве не принято сначала определять всякие штуки на двух объектах, а потом ассоциативностью или как-нибудь ещё доопределять для многих?

[OcbMuHor]

Одно дело матрица $\[{A_i}\]$, и совсем другое матрица $\[\rho _{{A_1},{A_2},...,{A_i}}^i\]$. Поскольку $\[\rho _{{A_1},{A_2},...,{A_i}}^i \subseteq {A_1} \times {A_2} \times ... \times {A_i}\]$ и совсем не обязательна эквивалентность отношения и прямого произведения множеств (на множестве). Например, $\[A = \left\{ {1,2,3} \right\}\]$, $\[{A^2} = \left\{ { < 1,1 > , < 1,2 > , < 1,3 > , < 2,1 > , < 2,2 > , < 2,3 > , < 3,1 > , < 3,2 > , < 3,3 > } \right\}\]$, $\[{\rho _A} = \left\{ {(x,y) \in \rho |x < y{,(x,y) \in A}} \right\} = \left\{ { < 1,2 > , < 1,3 > , < 2,3 > } \right\}\]$, согласно определению топа №6 п.2. $\[{\rho _A} = \begin{array}{*{20}{c}} 1&2 \\ 1&3 \\ 2&3 \end{array}\]$
Что касается множества В, то именно это меня и вводит в заблуждение. Но следуя неумолимой логике можно предположить что на множестве В задано отношение S, а на множестве А - отношения R1,R2,R3,R4,R5. И что множества $\[A,B\]$ есть подмножества одного множества, на котором по условию задачи заданы отношения S,R1,R2,R3,R4,R5.

[arseniiv]

(Оффтоп)

$<> \,\, \mapsto \, \langle\rangle$

[mkot]

OcbMuHor в сообщении #388902 писал(а):

Одно дело матрица $\[{A_i}\]$, и совсем другое матрица $\[\rho _{{A_1},{A_2},...,{A_i}}^i\]$. Поскольку $\[\rho _{{A_1},{A_2},...,{A_i}}^i \subseteq {A_1} \times {A_2} \times ... \times {A_i}\]$ и совсем не обязательна эквивалентность отношения и прямого произведения множеств (на множестве). Например, $\[A = \left\{ {1,2,3} \right\}\]$, $\[{A^2} = \left\{ { < 1,1 > , < 1,2 > , < 1,3 > , < 2,1 > , < 2,2 > , < 2,3 > , < 3,1 > , < 3,2 > , < 3,3 > } \right\}\]$, $\[{\rho _A} = \left\{ {(x,y) \in \rho |x < y{,(x,y) \in A}} \right\} = \left\{ { < 1,2 > , < 1,3 > , < 2,3 > } \right\}\]$, согласно определению топа №6 п.2. $\[{\rho _A} = \begin{array}{*{20}{c}} 1&2 \\ 1&3 \\ 2&3 \end{array}\]$
Что касается множества В, то именно это меня и вводит в заблуждение. Но следуя неумолимой логике можно предположить что на множестве В задано отношение S, а на множестве А - отношения R1,R2,R3,R4,R5. И что множества $\[A,B\]$ есть подмножества одного множества, на котором по условию задачи заданы отношения S,R1,R2,R3,R4,R5.

Для вашего примера выше можете считать, что все $A_i$ и $B_i$ равны $\{1, 2, 3, 4, 5, 6, 7, 8, 9\}$.
Что вам нужно сделать? для начала нарисовать вот так линии:

OcbMuHor в сообщении #388587 писал(а):

$\[{R_1} = \begin{array}{cccc|c} 1&3&1&1&4 \\ 2&4&2&2&3 \\ 4&1&3&2&7 \\ 4&9&4&4&1 \end{array}\]$,$\[{R_2} = \begin{array}{cccc|c} 2&4&4&2&3 \\ 1&3&1&1&7 \\ 3&2&3&5&2 \\ 1&3&1&1&2 \\ 4&1&3&2&5 \end{array}\]$,$\[{R_3} = \begin{array}{cccc|c} 4&1&3&2&4 \\ 1&3&1&1&5 \\ 2&3&4&3&2 \\ 3&3&4&1&5 \end{array}\]$,$\[{R_4} = \begin{array}{cccc|c} 1&3&1&1&2 \\ 6&8&5&5&2 \\ 4&1&3&2&1 \end{array}\]$,$\[{R_5} = \begin{array}{cccc|c} 1&3&1&1&3 \\ 3&2&1&4&4 \\ 4&1&3&2&9 \\ 1&3&1&1&4 \end{array}\]$,$\[S = \begin{array}{ccccc|c} 1&1&2&4&3&6 \\ 4&2&5&2&4&8 \\ 7&5&4&1&9&7 \\ 2&4&3&1&6&7 \\ 4&2&5&2&3&9 \\ 4&7&5&2&3&5 \\ 7&5&4&1&9&8 \end{array}\]$

Дальше -- понять, что можно перебирать не все элементы их $\{1, 2, 3, 4, 5, 6, 7, 8, 9\}^4$, а только те наборы, которые в $R_i$ встречаются слева от линии.
Ну и пошли смотреть по строкам:
Видим в $R_1$: $(1, 3, 1, 1 \,|\,4)$, таким образом нужно найти в остальных отношениях строки с такими же первыми четырьмя элеметами:
$R_2$: $(1, 3, 1, 1 \,|\, 7)$,
$R_3$: $(1, 3, 1, 1 \,|\, 5)$,
$R_4$: $(1, 3, 1, 1 \,|\, 2)$,
$R_5$: $(1, 3, 1, 1 \,|\, 3)$,
а из пятых элементов составляем строку $(4,7,5,2,3)$ и ищем в $S$ строку с таким началом:
$(4,7,5,2,3 \,|\, 5)$ откуда следует, что композиции будет принадлежать элемент
$(1, 3, 1, 1 \,|\, 5)$.
И т. д.

-- Вс дек 19, 2010 05:56:25 --

(Оффтоп)

arseniiv в сообщении #388898 писал(а):

Да и вообще, разве не принято сначала определять всякие штуки на двух объектах, а потом ассоциативностью или как-нибудь ещё доопределять для многих?

Я слабо представляю как такую вещь определить сначала на двух объектах, а потом воспользоваться ассоциативностью. Такое хорошо, когда что-то бинарное есть. И ассоциативное. Тут бинарного ничё нет.
(А так вы даже декартово произведение множеств не определите, кстати.)

[OcbMuHor]

Большое спасибо. теперь всё понятно

[mkot]

OcbMuHor в сообщении #389040 писал(а):

Большое спасибо. теперь всё понятно

Хорошо. Только заметьте, что например $(1, 3, 1, 1, \ldots)$ в $R_2$ и $R_4$ встречаются два раза. И поймите, что с этим делать. Если заметили и поняли, то ваще отлично.