2014 dxdy logo

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

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




 
 Коммутативная композиция перестановок
Сообщение19.05.2013, 20:50 
Здравствуйте, уважаемые участники форума.

Я не математик, прошу отнестись к моей проблеме с пониманием.

Имеются следующие перестановки (показаны в графическом и традиционном виде).
Изображение
Мне необходимо доказать, что результат композиции таких перестановок не зависит от порядка операндов.

Из курса высшей математики технического ВУЗа я знаю, что в общем случае композиция перестановок не коммутативна. Но, судя по всему, указанные мною перестановки дают коммутативные композиции.

Программа минимум – доказать, что такие перестановки дают коммутативную композицию.
Программа максимум – доказать, что композиции таких перестановок с любым количеством операндов дают одинаковые результаты.

Уважаемые математики, подскажите с какой стороны подойти к этой проблеме?

 
 
 
 Re: Коммутативная композиция перестановок
Сообщение19.05.2013, 21:21 
Аватара пользователя
Самое простое - записать, как работают эти перестановки, если элементы записать в двоичной системе.

 
 
 
 Re: Коммутативная композиция перестановок
Сообщение19.05.2013, 22:41 
Xaositect в сообщении #725916 писал(а):
Самое простое - записать, как работают эти перестановки, если элементы записать в двоичной системе.
Эти перестановки изначально имеют двоичную природу.

Перестановка А переставляет значения отличающиеся только младшем двоичном разряде (с весом 1), а по остальным разрядам не отличающиеся; перестановка B – переставляет значения отличающиеся только в двоичном разряде с весом 2; перестановка C – отличающиеся только в двоичном разряде с весом 4; перестановка D – отличающиеся только в двоичном разряде с весом 8.

Но что это мне дает в плане доказательства коммутативности композиции и независимости сложной композиции от порядка операндов?

 
 
 
 Re: Коммутативная композиция перестановок
Сообщение19.05.2013, 23:22 
Аватара пользователя
files в сообщении #725952 писал(а):
Но что это мне дает в плане доказательства коммутативности композиции и независимости сложной композиции от порядка операндов?
Ну если у нас каждая перестановка действует на своем бите, то переставлять их можно произвольно.
Это вообще очевидно, но если очень хочется доказательство, то если у нас есть две функции $F_1$ и $F_2$, которые заданы на аргументах длины $k$ как $F_1(a_0,\dots,a_k)= (a_0, \dots, f(a_i),\dots, a_k)$ и $F_2(a_0,\dots,a_k)= (a_0, \dots, g(a_j),\dots, a_k)$ с $i\neq j$, то простейшими преобразованиями доказывается $F_1\circ F_2 = F_2\circ F_1$, а дальше по индукции, что в любой последовательности таких функций можно сделать любую перестановку функций, и результат останется тем же самым.

 
 
 
 Re: Коммутативная композиция перестановок
Сообщение20.05.2013, 06:41 
А просто проверить выполнение 6 равенств
1) $AB = BA$,
2) $AC = CA$,
3) $AD = DA$,
4) $BC = CB$,
5) $BD = DB$
6) $CD = DC$
не пробовали? Это займет максимум 10 минут.

 
 
 
 Posted automatically
Сообщение20.05.2013, 13:21 
Аватара пользователя
 i  Тема перемещена из форума «Математика (общие вопросы)» в форум «Помогите решить / разобраться (М)»
Перенёс в соответствующий раздел

 
 
 
 Re: Коммутативная композиция перестановок
Сообщение20.05.2013, 20:34 
files в сообщении #725905 писал(а):
Программа максимум – доказать, что композиции таких перестановок с любым количеством операндов дают одинаковые результаты.
Ну, это-то как раз всегда просто, если «программа минимум» готова. Если $ab = ba, \; ac = ca, \; bc = cb$, то $abc = bac = bca = cba = cab = acb$ (меняем то первый и второй элемент, то второй и третий). Возьми мы вообще $a_1, \ldots, a_n$, все $n!$ их перестановок можно получить как произведения перестановок, меняющихдва соседних элемента (можно доказать по индукции). Каждая транспозиция не меняет произведение, и тут уже по индукции по количеству транспозиций любое произведение будет равно любому другому.

 
 
 [ Сообщений: 7 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group