Propriedade associativa

ImprimirCitar

Propriedade de uma operação matemática

Na matemática, a propriedade associativa é uma propriedade de algumas operações binárias, o que significa que reorganizar os parênteses em uma expressão não alterará o resultado. Na lógica proposicional, associatividade é uma regra válida de substituição de expressões em provas lógicas.

Dentro de uma expressão contendo duas ou mais ocorrências seguidas do mesmo operador associativo, a ordem em que as operações são executadas não importa desde que a sequência dos operandos não seja alterada. Ou seja (após reescrever a expressão com parênteses e em notação infixa, se necessário), reorganizar os parênteses em tal expressão não alterará seu valor. Considere as seguintes equações:

{displaystyle {begin{aligned}(2+3)+4&=2+(3+4)=9,\2times (3times 4)&=(2times 3)times 4=24.end{aligned}}}

Embora os parênteses tenham sido reorganizados em cada linha, os valores das expressões não foram alterados. Como isso é válido ao realizar adição e multiplicação em quaisquer números reais, pode-se dizer que "adição e multiplicação de números reais são operações associativas".

Associatividade não é o mesmo que comutatividade, que aborda se a ordem de dois operandos afeta o resultado. Por exemplo, a ordem não importa na multiplicação de números reais, ou seja, $a \times b = b \times a$ , então dizemos que a multiplicação de números reais é uma operação comutativa. No entanto, operações como composição de funções e multiplicação de matrizes são associativas, mas (geralmente) não comutativas.

As operações associativas são abundantes em matemática; de fato, muitas estruturas algébricas (como semigrupos e categorias) exigem explicitamente que suas operações binárias sejam associativas.

No entanto, muitas operações importantes e interessantes são não associativas; alguns exemplos incluem subtração, exponenciação e o produto vetorial vetorial. Em contraste com as propriedades teóricas dos números reais, a adição de números de ponto flutuante na ciência da computação não é associativa, e a escolha de como associar uma expressão pode ter um efeito significativo no erro de arredondamento.

Definição

Uma operação binária ∗ no conjunto S é associativo quando este diagrama comuta. Isso é, quando os dois caminhos de

S \times S \times S

para

S

compor para a mesma função de

S \times S \times S

para

S

Formalmente, uma operação binária $*$ em um conjunto $S$ é chamada associativo se satisfizer a lei associativa:

(x * Sim.) * zangão. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = x * (Sim. * zangão.)

para todos

x

Sim.

zangão.

S

Aqui, ∗ é usado para substituir o símbolo da operação, que pode ser qualquer símbolo, e até mesmo a ausência de símbolo (justaposição) como na multiplicação.

(x Sim.) zangão. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = x (Sim. zangão.) = x Sim. zangão.

para todos

x

Sim.

zangão.

S

A lei associativa também pode ser expressa em notação funcional assim: $f (f (x, y), z) = f (x, f (y, z))$ .

Lei associativa generalizada

Na ausência da propriedade associativa, cinco fatores

um

b)

c

D

e

resulta em um treliça Tamari da ordem quatro, possivelmente produtos diferentes.

Se uma operação binária for associativa, a aplicação repetida da operação produzirá o mesmo resultado, independentemente de como os pares de parênteses válidos são inseridos na expressão. Isso é chamado de lei associativa generalizada. Por exemplo, um produto de quatro elementos pode ser escrito, sem alterar a ordem dos fatores, de cinco maneiras possíveis:

$(um b)) c) D$
$(um b)) c D)$
$(um (b) c) D$
$um (b) c) D)$
$um (b) (c D)$

Se a operação do produto for associativa, a lei associativa generalizada diz que todas essas expressões produzirão o mesmo resultado. Portanto, a menos que a expressão com parênteses omitidos já tenha um significado diferente (veja abaixo), os parênteses podem ser considerados desnecessários e "o" produto pode ser escrito de forma inequívoca como

um b) c D

À medida que o número de elementos aumenta, o número de maneiras possíveis de inserir parênteses cresce rapidamente, mas eles permanecem desnecessários para a desambiguação.

Um exemplo em que isso não funciona é o bicondicional lógico $\leftrightarrow$ . É associativo; assim, $A \leftrightarrow (B \leftrightarrow C)$ é equivalente a $(A \leftrightarrow B) \leftrightarrow C$ , mas $A \leftrightarrow B \leftrightarrow C$ mais comumente significa $(A \leftrightarrow B) e (B \leftrightarrow C)$ , que não é equivalente.

Exemplos

A adição de números reais é associativa.

Alguns exemplos de operações associativas incluem o seguinte.

The concatenation of the three strings "hello", " ", "world" can be computed by concatenating the first two strings (giving "hello ") and appending the third string ("world"), or by joining the second and third string (giving " world") and concatenating the first string ("hello") with the result. The two methods produce the same result; string concatenation is associative (but not commutative).
In arithmetic, addition and multiplication of real numbers are associative; i.e.,
${displaystyle left.{begin{matrix}(x+y)+z=x+(y+z)=x+y+zquad \(x,y)z=x(y,z)=x,y,zqquad qquad qquad quad ,end{matrix}}right}{mbox{for all }}x,y,zin mathbb {R}.}$
Because of associativity, the grouping parentheses can be omitted without ambiguity.
The trivial operation $x * y = x$ (that is, the result is the first argument, no matter what the second argument is) is associative but not commutative. Likewise, the trivial operation $x \circ y = y$ (that is, the result is the second argument, no matter what the first argument is) is associative but not commutative.
Addition and multiplication of complex numbers and quaternions are associative. Addition of octonions is also associative, but multiplication of octonions is non-associative.
The greatest common divisor and least common multiple functions act associatively. ${displaystyle left.{begin{matrix}operatorname {gcd} (operatorname {gcd} (x,y),z)=operatorname {gcd} (x,operatorname {gcd} (y,z))=operatorname {gcd} (x,y,z) quad \operatorname {lcm} (operatorname {lcm} (x,y),z)=operatorname {lcm} (x,operatorname {lcm} (y,z))=operatorname {lcm} (x,y,z)quad end{matrix}}right}{mbox{ for all }}x,y,zin mathbb {Z}.}$
Taking the intersection or the union of sets: ${displaystyle left.{begin{matrix}(Acap B)cap C=Acap (Bcap C)=Acap Bcap Cquad \(Acup B)cup C=Acup (Bcup C)=Acup Bcup Cquad end{matrix}}right}{mbox{for all sets }}A,B,C.}$
If $M$ is some set and $S$ denotes the set of all functions from $M$ to $M$ , then the operation of function composition on $S$ is associative: ${displaystyle (fcirc g)circ h=fcirc (gcirc h)=fcirc gcirc hqquad {mbox{for all }}f,g,hin S.}$
Slightly more generally, given four sets $M$ , $N$ , $P$ and $Q$ , with $h : M \to N$ , $g : N \to P$ , and $f : P \to Q$ , then ${displaystyle (fcirc g)circ h=fcirc (gcirc h)=fcirc gcirc h}$ as before. In short, composition of maps is always associative.
In category theory, composition of morphisms is associative by definition. Associativity of functors and natural transformations follows from associativity of morphisms.
Consider a set with three elements, $A$ , $B$ , and $C$ . The following operation:

× $A$ $B$ $C$

$A$ $A$ $A$ $A$

$B$ $A$ $B$ $C$

$C$ $A$ $A$ $A$
is associative. Thus, for example, $A (B C) = (A B) C = A$ . This operation is not commutative.
Because matrices represent linear functions, and matrix multiplication represents function composition, one can immediately conclude that matrix multiplication is associative.
For real numbers (and for any totally ordered set), the minimum and maximum operation is associative: ${displaystyle max(a,max(b,c))=max(max(a,b),c)quad {text{ and }}quad min(a,min(b,c))=min(min(a,b),c).}$

×	$A$	$B$	$C$
$A$	$A$	$A$	$A$
$B$	$A$	$B$	$C$
$C$	$A$	$A$	$A$

Lógica proposicional

Regra de substituição

Na lógica proposicional verofuncional padrão, associação ou associatividade são duas regras válidas de substituição. As regras permitem mover parênteses em expressões lógicas em provas lógicas. As regras (usando notação de conectivos lógicos) são:

{displaystyle (Plor (Qlor R))Leftrightarrow ((Plor Q)lor R)}

{displaystyle (Pland (Qland R))Leftrightarrow ((Pland Q)land R),}

Onde " $Leftrightarrow$ "é um símbolo metalógico que representa "pode ser substituído em uma prova com".

Conectivos funcionais verdadeiros

Associatividade é uma propriedade de alguns conectivos lógicos da lógica proposicional verofuncional. As equivalências lógicas a seguir demonstram que a associatividade é uma propriedade de conectivos particulares. O seguinte (e seus inversos, já que $\leftrightarrow$ é comutativo) são tautologias verofuncionais.

Associatividade da disjunção: ${displaystyle ((Plor Q)lor R)leftrightarrow (Plor (Qlor R))}$
Associatividade da conjunção: ${displaystyle ((Pland Q)land R)leftrightarrow (Pland (Qland R))}$
Associatividade da equivalência: $((Pleftrightarrow Q)leftrightarrow R)leftrightarrow (Pleftrightarrow (Qleftrightarrow R))$

A negação conjunta é um exemplo de um conectivo funcional de verdade que não é associativo.

Operação não associativa

Uma operação binária $*$ em um conjunto S que não satisfaz a lei associativa é chamada não associado. Simbolicamente,

{displaystyle (x*y)*zneq x*(y*z)qquad {mbox{for some }}x,y,zin S.}

Para tal operação, a ordem de avaliação não importa. Por exemplo:

Substância: $(5-3)-2,neq ,5-(3-2)$
Divisão: $(4/2)/2,neq ,4/(2/2)$
Exponenciação: $2^{(1^{2})},neq ,(2^{1})^{2}$
Produto cruzado do vetor: ${displaystyle {begin{aligned}mathbf {i} times (mathbf {i} times mathbf {j})&=mathbf {i} times mathbf {k} =-mathbf {j} \(mathbf {i} times mathbf {i})times mathbf {j} &=mathbf {0} times mathbf {j} =mathbf {0} end{aligned}}}$

Além disso, embora a adição seja associativa para somas finitas, ela não é associativa dentro de somas infinitas (séries). Por exemplo,

{displaystyle (1+-1)+(1+-1)+(1+-1)+(1+-1)+(1+-1)+(1+-1)+dots =0}

{displaystyle 1+(-1+1)+(-1+1)+(-1+1)+(-1+1)+(-1+1)+(-1+1)+dots =1.}

Algumas operações não associativas são fundamentais em matemática. Eles aparecem frequentemente como a multiplicação em estruturas chamadas álgebras não associativas, que também possuem uma adição e uma multiplicação escalar. Exemplos são os octônios e as álgebras de Lie. Nas álgebras de Lie, a multiplicação satisfaz a identidade de Jacobi em vez da lei associativa; isso permite abstrair a natureza algébrica das transformações infinitesimais.

Outros exemplos são magmas quasigrupo, quasicampo, anel não associativo e magmas não associativos comutativos.

Não associatividade do cálculo de ponto flutuante

Na matemática, a adição e a multiplicação de números reais são associativas. Por outro lado, na ciência da computação, a adição e a multiplicação de números de ponto flutuante não são associativas, pois erros de arredondamento são introduzidos quando valores de tamanhos diferentes são unidos.

Para ilustrar isso, considere uma representação de ponto flutuante com uma mantissa de 4 bits:

(1.000)₂×⁰ + 1.000₂×⁰) + 1.000.₂×⁴ = 1.000₂×¹ + 1.000₂×⁴ = 1.001₂×⁴

1.000.₂×⁰ + (1.000₂×⁰ + 1.000.₂×⁴) = 1.000₂×⁰ + 1.000₂×⁴ = 1.000₂×⁴

Embora a maioria dos computadores compute com 24 ou 53 bits de mantissa, essa é uma fonte importante de erro de arredondamento, e abordagens como o algoritmo de soma de Kahan são maneiras de minimizar os erros. Pode ser especialmente problemático na computação paralela.

Notação para operações não associativas

Em geral, os parênteses devem ser usados para indicar a ordem de avaliação se uma operação não-associativa aparecer mais de uma vez em uma expressão (a menos que a notação especifique a ordem de outra forma, como ${displaystyle {dfrac {2}{3/4}}}$ ). No entanto, os matemáticos concordam em uma determinada ordem de avaliação para várias operações não-associativas comuns. Esta é simplesmente uma convenção nominal para evitar parênteses.

Uma operação associativa à esquerda é uma operação não associativa que é avaliada convencionalmente da esquerda para a direita, ou seja,

{displaystyle left.{begin{array}{l}a*b*c=(a*b)*c\a*b*c*d=((a*b)*c)*d\a*b*c*d*e=(((a*b)*c)*d)*equad \{mbox{etc.}}end{array}}right}{mbox{for all }}a,b,c,d,ein S}

enquanto uma operação associativa à direita é avaliada convencionalmente da direita para a esquerda:

{displaystyle left.{begin{array}{l}x*y*z=x*(y*z)\w*x*y*z=w*(x*(y*z))quad \v*w*x*y*z=v*(w*(x*(y*z)))quad \{mbox{etc.}}end{array}}right}{mbox{for all }}z,y,x,w,vin S}

Ocorrem operações associativas à esquerda e à direita. As operações associativas à esquerda incluem o seguinte:

Subtração e divisão de números reais: ${displaystyle x-y-z=(x-y)-z}$; ${displaystyle x/y/z=(x/y)/z}$
Aplicação de função: $(f,x,y)=((f,x),y)$

Esta notação pode ser motivada pelo isomorfismo currying, que permite a aplicação parcial.

As operações associativas à direita incluem o seguinte:

Exponenciação de números reais na notação de superscrições: ${displaystyle x^{y^{z}}=x^{(y^{z})}}$
A exponenciação é comumente usada com suportes ou de associação direita porque uma repetida operação de exponenciação de esquerda-associativa é de pouca utilidade. Poder repetido seria principalmente reescrito com multiplicação:; ${displaystyle (x^{y})^{z}=x^{(yz)}}$
Formatado corretamente, o superscript comporta-se inerentemente como um conjunto de parênteses; por exemplo, na expressão ${displaystyle 2^{x+3}}$ a adição é realizada antes da exponencialização, apesar de não haver parênteses explícitos ${displaystyle 2^{(x+3)}}$ enrolado à volta. Assim, dada uma expressão como $x^{y^z}$ , o expoente completo ${displaystyle y^{z}}$ da base $x$ é avaliado primeiro. No entanto, em alguns contextos, especialmente na caligrafia, a diferença entre ${displaystyle {x^{y}}^{z}=(x^{y})^{z}}$ , ${displaystyle x^{yz}=x^{(yz)}}$ e ${displaystyle x^{y^{z}}=x^{(y^{z})}}$ pode ser difícil de ver. Nesse caso, a associação direita é geralmente implícita.
Definição da função: $mathbb {Z} rightarrow mathbb {Z} rightarrow mathbb {Z} =mathbb {Z} rightarrow (mathbb {Z} rightarrow mathbb {Z})$; $xmapsto ymapsto x-y=xmapsto (ymapsto x-y)$
O uso de notação associativa para essas operações pode ser motivado pela correspondência Curry-Howard e pelo isomorfismo de cura.

As operações não associativas para as quais nenhuma ordem de avaliação convencional é definida incluem o seguinte.

Exponenciação de números reais em notação infixa: ${displaystyle (x^{wedge }y)^{wedge }zneq x^{wedge }(y^{wedge }z)}$
Operadores de alto nível da Knuth: ${displaystyle auparrow uparrow (buparrow uparrow c)neq (auparrow uparrow b)uparrow uparrow c}$; ${displaystyle auparrow uparrow uparrow (buparrow uparrow uparrow c)neq (auparrow uparrow uparrow b)uparrow uparrow uparrow c}$
Tomando o produto cruzado de três vetores: ${vec {a}}times ({vec {b}}times {vec {c}})neq ({vec {a}}times {vec {b}})times {vec {c}}qquad {mbox{ for some }}{vec {a}},{vec {b}},{vec {c}}in mathbb {R} ^{3}$
Tomando a média pares de números reais: ${(x+y)/2+z over 2}neq {x+(y+z)/2 over 2}qquad {mbox{for all }}x,y,zin mathbb {R} {mbox{ with }}xneq z.$
Tomando o complemento relativo de conjuntos: ${displaystyle (Abackslash B)backslash Cneq Abackslash (Bbackslash C)}$ .
(Compare a nonimplicação material na lógica.)

História

William Rowan Hamilton parece ter cunhado o termo "propriedade associativa" por volta de 1844, uma época em que ele estava contemplando a álgebra não associativa dos octônios que havia aprendido com John T. Graves.

Contenido relacionado

Más resultados...