Ассоциативность произвольного числа сомножителей

[ewert]

Утундрий в сообщении #1412171 писал(а):

Пусть это будет просто порядок выполнения умножений.

А он не вполне однозначен -- я ведь в самом начале об этом упомянул.

Вы намекаете на то, что порядок выполнения задаётся присвоением каждой точечке некоторого уникального номера. А это неправда -- он задаётся присвоением уровня вложенности.

[Утундрий]

ewert в сообщении #1412174 писал(а):

он не вполне однозначен

Поясните. Два порядка приводят к одному результату? Так нам того и надо. Или какой-то заданный порядок нельзя реализовать?

[ewert]

Так. Вот берём опять: $((a\cdot b)\cdot(c\cdot d))$.

Уровни вложенности тут однозначны: $2,1,2$ (и это важно, между кстати, для синтаксического анализа при программировании; кто из нас тут программист, между кстати?...)

А вот порядок выполнения, увы, неоднозначен: это или $2,1,3$, или $3,1,2$. И то, и другое такой расстановке скобок вполне соответствует.

Если же нет хоть какого-то однозначного соответствия, хоть в каком-то смысле -- любая попытка формального доказательства заведомо развалится.

[Утундрий]

ewert в сообщении #1412177 писал(а):

порядок выполнения, увы, неоднозначен

Почему "увы"? Всего расстановок $n$ скобок $n!$ штук, а различных среди них (после слияния по доказанному на предыдущем шаге индукции) всего $n$.

ewert в сообщении #1412177 писал(а):

Если же нет хоть какого-то однозначного соответствия, хоть в каком-то смысле -- любая попытка формального доказательства заведомо развалится

Это напоминает не рассуждение, а предубеждение.

[ewert]

Утундрий в сообщении #1412193 писал(а):

Это напоминает не рассуждение, а предубеждение.

Да, предубеждение. (злобно) Против Вас. Пока задача точно не поставлена -- какой смысл её решать?...

А Вы её изначально и не поставили. Не сформулировали, что в точности следует понимать под набором скобок. Соответственно, и решать оказалось непонятно что, увы.

Я попытался восполнить этот явный пробел. Ну как мог, извините.

[Утундрий]

ewert в сообщении #1412198 писал(а):

Пока задача точно не поставлена -- какой смысл её решать?...

Недоумение есть функция времени. На данный момент мне не ясна необходимость приведения к "стандартному виду".

[ewert]

Да хоть к какому-то виду. Что в точности понималось под "набором скобок"?..

Изначально этот термин не определён (Вами). Да, есть, конечно, обязательное требование "ненарушения парности". Но оно ж заведомо и недостаточно.

[beroal]

С синтаксической точки зрения произведение — это последовательность букв, то есть слово (строка, текст). Расстановка скобок — это добавление скобок в это слово. Можно работать со словами (как и делают в учебниках по логике), но ведь скобки можно расставить неправильно, и надо вводить грамматику.

В данной задаче более естественный тип данных — дерево. Каждый узел или имеет 2-х детей и обозначает бинарную операцию группы, или помечен буквой и не имеет детей. Ассоциативность даёт следующее отношение $R$: множество всех пар деревьев вида $\langle (a\cdot b)\cdot c, a\cdot(b\cdot c)\rangle$, где $a, b, c$ — деревья. Пусть $S$ есть наименьшее замкнутое множество, включающее $R$, где под замкнутыми множествами подразумеваются замкнутые по операциям $a\mapsto a\cdot b$ и $a\mapsto b\cdot a$ для любых деревьев $b$ (ЕМНИП, это называется «синтаксическое замыкание»). Ещё есть операция «уплощения дерева», которая возвращает список всех букв аргумента-дерева в том порядке, в котором они встречаются в дереве. Надо доказать, что ядерное отношение уплощения дерева равно транзитивному рефлексивному симметричному замыканию $S$. Это если немногословно.

[arseniiv]

(Оффтоп)

beroal в сообщении #1412572 писал(а):

В данной задаче более естественный тип данных — дерево.

Да, в принципе и при рассмотрении логики полезно использовать абстрактный синтаксис и термы-деревья (вместо строк), это не сильно менее фундаментально и финитно, чем традиционные строки, про разбор или подстановку которых приходится отдельно доказывать теоремы.

[Утундрий]

На всякий случай напомню, что требуется доказать независимость результата от порядка выполнения умножений.

[worm2]

Чтобы отключить вредную в данном случае интуицию, можно вместо $a\cdot b$ писать $M(a, b)$. Куча скобок будет, как и раньше, но не надо будет запоминать новые правила манипулирования.

[ewert]

Утундрий в сообщении #1412636 писал(а):

напомню, что требуется доказать независимость результата от порядка выполнения умножений.

Она уже здесь многократно доказана. На всякий случай напомню проблему: что называть порядком выполнения в выражении $(a\cdot b)\cdot(c\cdot d)$ ?..

[beroal]

Утундрий в сообщении #1412636 писал(а):

На всякий случай напомню, что требуется доказать независимость результата от порядка выполнения умножений.

Если вопрос ко мне. Дерево $x$ является результатом расстановки скобок в списке $y$ тогда и только тогда, когда $y$ есть уплощение дерева $x$. Если деревья связаны транзитивным рефлексивным симметричным замыканием $S$, то результаты их вычисления в любой полугруппе при любой оценке букв равны. Отсюда следует искомая теорема: если два дерева являются результатами расстановки скобок в одном и том же списке, результаты их вычисления в любой полугруппе при любой оценке букв равны.

[Утундрий]

ewert в сообщении #1412660 писал(а):

Она уже здесь многократно доказана

Стало быть, тут и сказочке конец.

ewert
beroal
Вы вполне убедили меня, что о скобках в этой задачке лучше вообще не заикаться.

[ewert]

Утундрий в сообщении #1412741 писал(а):

о скобках в этой задачке лучше вообще не заикаться.

Нет, отчего же. Заикаться нужно, только осознанно.

Вот тот самый уровень вложенности, за который я так усердно топил (не помню, кого именно; и давал ли акваланг; но ведь надо ж бежать за комсомолом).

А как его отследить -- если вообще без скобок?..

Со скобками-то всем ежам всё понятно. Подсчитываем разность открывающих и закрывающих скобок -- и вот он, уровень.

Это я как профессиональный дилетант в программировании разных компиляторов.