2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 суперпозиция отношения
Сообщение17.12.2010, 01:03 


29/11/10
107
Всем доброго времени суток. Собственно есть задача, которую я должен решить, но я не прошу решить, а только разъяснить мне что же такое эта суперпозиция и с чем ее едят. Откровенно говоря, определение в лекции мне ни сколько не облегчило задачу. Вот что у меня есть:
Суперпозицией отношений $\[\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\]$ (в данном конкретном примере)?

 Профиль  
                  
 
 Re: суперпозиция отношения
Сообщение17.12.2010, 14:31 


29/11/10
107
вопрос не достоин ответа?

 Профиль  
                  
 
 Re: суперпозиция отношения
Сообщение17.12.2010, 21:25 
Заслуженный участник
Аватара пользователя


03/02/10
1928
любой нормальный человек прочтя

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$-отношение, чтоб не гуглить

 Профиль  
                  
 
 Re: суперпозиция отношения
Сообщение17.12.2010, 23:02 


29/11/10
107
Цитата:
не будет читать дальше (если это ему не надо почему-то)

почему не будет?
Цитата:
и множества $\[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}\]$

 Профиль  
                  
 
 Re: суперпозиция отношения
Сообщение18.12.2010, 10:59 
Заслуженный участник
Аватара пользователя


03/02/10
1928
OcbMuHor в сообщении #388587 писал(а):
почему не будет?

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

paha в сообщении #388535 писал(а):
и напомните, что такое $m$-отношение, чтоб не гуглить


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

OcbMuHor в сообщении #388587 писал(а):
Это определение из конспекта лекций по дискретной математике. Я его не понимаю и спросить мне не у кого.

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

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

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

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

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

 Профиль  
                  
 
 Re: суперпозиция отношения
Сообщение18.12.2010, 18:01 


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

Я к сожалению не имею физической возможности посещать лекции, и по этой причине преподаватели идут на встречу, высылая конспекты своих лекций на мой 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] определение простое и понятное. Поскольку суперпозиция отношений тоже является отношением(!?) то и свойствами обладает теми же.

 Профиль  
                  
 
 Re: суперпозиция отношения
Сообщение18.12.2010, 18:35 
Заслуженный участник
Аватара пользователя


03/02/10
1928
OcbMuHor в сообщении #388830 писал(а):
Так график $\[\rho _{{A_1},...,{A_n}}^n\]$ удобно задавать матрицей


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

OcbMuHor в сообщении #388830 писал(а):
определение суперпозиции детально описано в первом топе

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

OcbMuHor в сообщении #388830 писал(а):
Вот пример (тоже из конспекта лекций)

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

 Профиль  
                  
 
 Re: суперпозиция отношения
Сообщение18.12.2010, 19:57 
Аватара пользователя


18/10/08
454
Омск
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$, но на них закроем глаза.

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

 Профиль  
                  
 
 Re: суперпозиция отношения
Сообщение18.12.2010, 20:07 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: суперпозиция отношения
Сообщение18.12.2010, 20:24 
Заслуженный участник


27/04/09
28128

(Оффтоп)

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

 Профиль  
                  
 
 Re: суперпозиция отношения
Сообщение18.12.2010, 20:28 


29/11/10
107
Одно дело матрица $\[{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.

 Профиль  
                  
 
 Re: суперпозиция отношения
Сообщение18.12.2010, 20:32 
Заслуженный участник


27/04/09
28128

(Оффтоп)

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

 Профиль  
                  
 
 Re: суперпозиция отношения
Сообщение19.12.2010, 01:50 
Аватара пользователя


18/10/08
454
Омск
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 писал(а):
Да и вообще, разве не принято сначала определять всякие штуки на двух объектах, а потом ассоциативностью или как-нибудь ещё доопределять для многих?

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

 Профиль  
                  
 
 Re: суперпозиция отношения
Сообщение19.12.2010, 03:12 


29/11/10
107
Большое спасибо. теперь всё понятно :appl:

 Профиль  
                  
 
 Re: суперпозиция отношения
Сообщение19.12.2010, 07:11 
Аватара пользователя


18/10/08
454
Омск
OcbMuHor в сообщении #389040 писал(а):
Большое спасибо. теперь всё понятно :appl:

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 17 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group