在数学中,结合律(associative property)是
二元运算可以有的一个性质,意指在一个包含有二个以上的可结合运算子的表示式,只要运算数的位置没有改变,其运算的顺序就不会对运算出来的值有影响。例如,加法结合律表明三个数相加,无论是先把前面两个数相加再加第三个数,还是先把后面两个数相加再和第一个数相加,它们的和不变。结合律不应该和
交换律相混淆,交换律会改变表示式中运算元的位置,而结合律则不会。
定义
群论中的概念。给定一个集合S上的二元运算·,如果对于S中的任意a,b,c。有:
a·(b·c) = (a·b)·c,
则称运算·满足结合律。形式上,一个在集合S上的二元运算*被称之为可结合的若其满足下面的结合律:
(x*y)*z=x*(y*z) ∀ x,y,z∈S。
运算的顺序并不会影响到表示式的值,且可证明这在含有“任意”多个*运算的表示式之下也依然是成立的。
举例
加法和乘法
在算术中,实数的加法和乘法都是可结合的,即:
(x+y)+z=x+(y+z)=x+y+z
(x*y)z=x(y*z)=x*y*z
对于所有的实数x,y,z。复数和四元数的加法与乘法也是可结合的。八元数的加法是可结合的,但其乘法则是不可结合的。
最大公因数和最小公倍数
最大公因数和最小公倍数的运算都是可结合的:
gcd(gcd(x,y),z)=gcd(x,gcd(y,z))=gcd(x,y,z)
lcm(lcm(x,y),z)=lcm(x,lcm(y,z))=lcm(x,y,z)
对于所有的整数x,y,z。
集合交并
集合的交,并运算都满足结合律:
交:(A∩B)∩C=A∩(B∩C)
并:(A∪B)∪C=A∪(B∪C)
矩阵乘法
矩阵乘法满足结合律。一个A x B的矩阵乘以一个B x C的矩阵将得到一个A x C的矩阵,时间复杂度为A x B x C。因为线性变换是个可表示成矩阵的函数,其中的函数复合则可以用矩阵乘法来表示,立即可知矩阵乘法为可结合的。
函数复合
若M是某个集合且S为所有从M映射至M的函数所组成的集合,则在S上的函数复合的运算是可结合的:
(f∘g)∘h=f∘(g∘h)=f∘g∘h ∀ f,g,h∈S。
更一般性地,给定四个集合M、N、P和Q,且h:M→N,g:N→P、f:P→Q,则
(f∘g)∘h=f∘(g∘h)=f∘g∘h
和前面一样。简单地说,映射的复合总会是可结合的。
不可结合性
一个在集合S上的
二元运算*若不满足结合律,则称之为不可结合的。表示成符号即为:
(x*y)*z≠x*(y*z) ∃ x,y,z∈S。
在此一运算下,运算的顺序是有影响的。减法、除法和幂都是不可结合运算的简单例子:
(5-3)-2≠5-(3-2)
(4/2)/2≠4/(2/2)
2^(1^2)≠(2^1)^2.
一般,当不可结合运算在一个表示出现多于一次时,
括号就必须被使用来表示其运算顺序。不过,数学家会对若干常见的不可结合运算采用一种特别的运算顺序的规则。这单纯只是个为了减少括号的语法约定。
二进制浮点数
在
计算机科学中,由于采用二进制浮点数运算,因此加法不符合结合律。例如,以下两个运算的结果在电脑中不
相等:
(0.1+0.2)+0.3
0.1+(0.2+0.3)
使用相等运算符进行比较,会传回假(false)。