Se
é um conjunto fechado com relação a uma operação associativa, demonstrar que se colocarmos quantos parênteses quisermos em
, mantendo a ordem dos elementos, obteremos o mesmo elemento em
(por exemplo,
; usar indução sôbre
).
Passo 1
O enunciado dá as seguintes informações e pede isto:
- Dado um conjunto
e uma operação binária (que escrevemos apenas por justaposição, por exemplo ) tal que: -
é fechado para essa operação: isto é, se então . - A operação é associativa: para quaisquer
vale .
-
- O que pedir demonstrar: para quaisquer
e quaisquer elementos , qualquer maneira de inserir parênteses em (mantendo a ordem dos fatores) produz o mesmo elemento de . Em outras palavras, o valor do produto não depende da colocação dos parênteses.
Passo 2
Vou explicar termos importantes para não deixar nada vago.
- Fechamento: significa que qualquer produto de dois elementos de
ainda está em . Isso garante que, ao calcular um produto parcial (quando colocamos parênteses e avaliamos), o resultado continua sendo elemento de e podemos multiplicá‑lo com os restantes. - Associatividade: significa que, ao ter três elementos, a forma de agrupar os dois primeiros ou os dois últimos não altera o resultado, isto é
. Essa propriedade será a única que permite trocar parênteses localmente. - Uma “parentetização” de
é uma maneira de agrupar pares sucessivos até reduzir tudo a um único produto binário (equivalente a uma árvore binária completa com as folhas ). Por exemplo, para temos possíveis parentetizações como ou , etc.
Passo 3
Estratégia do prova: usarei indução forte sobre
.
- Para cada
defino a propriedade : “para quaisquer , todo modo de inserir parênteses em (mantendo a ordem) dá o mesmo resultado”. - Vou provar
(casos base) e depois mostrar que para todo implica .
Passo 4
Casos base.
-
: há apenas um ‘produto’ possível, que é sozinho, logo é trivialmente verdadeira. -
: há apenas um modo de multiplicar (não há parênteses diferentes a considerar), então também é verdadeira.
Passo 5
Caso
(ilustrativo e simples uso da associatividade).
- Há duas parentetizações não-triviais:
e . - Pela hipótese de associatividade,
. - Assim
é verdadeira. Isso mostra como a associatividade elimina a ambiguidade para três fatores.
Passo 6
Hipótese de indução forte.
- Suponha que para todo
com a propriedade é verdadeira: isto é, para qualquer sequência de elementos de toda parentetização dá o mesmo resultado. - Vamos provar
.
Passo 7
Tomemos uma parentetização arbitrária
de
.
- Qualquer parentetização completa de
fatores pode ser vista como o produto binário de duas sub‑parentetizações: existe um com tal que onde é uma parentetização dos fatores e é uma parentetização dos fatores . - Observação: essa decomposição é apenas a leitura natural de uma árvore binária: a raiz corresponde à última multiplicação feita, e os dois ramos são parentetizações de prefixo e sufixo.
Passo 8
Aplicando a hipótese de indução às sub‑parentetizações.
- Como
e , pela hipótese de indução as sub‑parentetizações têm resultados únicos. Ou seja, o valor de é o mesmo que o valor da parentetização “esquerda canônica” dos primeiros fatores; denote esse valor por isto é, o produto dos primeiros fatores com parênteses todos à esquerda (left-associated). - De modo análogo, o valor de
é o mesmo que o valor que é o produto, left-associated, dos fatores . - Portanto o valor de
é o elemento (Aqui o expoente só indica que é o left-associated do sufixo começando em .)
Passo 9
Mostrar que
é igual ao left-associated total
.
- Defina
explicitamente por recorrência: de modo que . - Quero provar que, para todo
com , - Prova desse fato por indução sobre
(índice que vai de até ), construindo progressivamente a concatenação: - Defina para
o elemento Note que e . - Vou mostrar por indução em
que Base . Temos . E , então . OK.
Passo indutivo. Suponha. Então Aplicando a associatividade (que permite reescrever para quaisquer em ), obtemos Mas é exatamente (o left-associated dos fatores ). Logo o que fecha o passo indutivo. - Aplicando o resultado para
obtemos Mas é exatamente porque é a forma left-associated iniciando por seguido de , e isso coincide com a left-association total dos fatores.
- Defina para
- Assim demonstramos que para todo
com vale .
Passo 10
Finalizando a indução.
- Voltando ao passo 8, qualquer parentetização
vale para algum . - Pelo passo 9 esse produto é
. - Portanto
. Como foi uma parentetização arbitrária, toda parentetização de tem valor . - Concluímos
: para os fatores o resultado é independente da colocação dos parênteses.
Passo 11
Conclusão por indução forte.
- Mostramos os casos base e que
para todo implica . Logo por indução forte é verdadeira para todo . - Em palavras: qualquer modo de inserir parênteses em
(mantendo a ordem dos fatores) produz o mesmo elemento de , graças à associatividade e ao fato de ser fechado.
Resposta
Para quaisquer
e quaisquer
, todo modo de inserir parênteses em
(mantendo a ordem dos fatores) produz o mesmo elemento de
.