数学 では、結合法則 [ 1 ] は、式中の括弧 を並べ替えても結果が変わらないという、一部の二項演算 の性質です。命題論理 では、結合法則は 論理証明 における式 の有効な 置換規則 です。
同じ結合演算子が連続して2回以上出現する式では、被演算子 の順序が変わらない限り、演算の順序は関係ありません。 つまり、（必要に応じて括弧を使って中置記法で式を書き直した後）、そのような式の括弧の順序を変えても、その値は変わりません。次の式を考えてみましょう。
（ 2 + 3 ） + 4 = 2 + （ 3 + 4 ） = 9 2 × （ 3 × 4 ） = （ 2 × 3 ） × 4 = 24. {\displaystyle {\begin{aligned}(2+3)+4&=2+(3+4)=9\,\\2\times (3\times 4)&=(2\times 3)\times 4=24.\end{aligned}}}
各行で括弧の順序が入れ替わっても、式の値は変わりません。実数 の加算と乗算は結合法則を満たす演算であるため、実数の加算と乗算を行う場合は常にこのことが当てはまります。
結合法則は、2つの被演算項の順序が結果に影響するかどうかを示す交換法則 とは異なります。例えば、実数の乗算では順序は関係なく、 a × b = b × a 関数合成 や行列乗算 などの演算は結合法則を満たしますが、（一般的には）交換法則を満たしません。
数学には結合法則を満たす演算が豊富に存在します。実際、半群 や圏 など多くの代数構造で は、二項演算が結合法則を満たすことが明示的に求められます。しかし、重要かつ興味深い演算の中には、結合法則を満たさないものも多くあります。例えば、減算 、べき乗 、ベクトル積など が挙げられます。実数の理論的な性質とは対照的に、コンピュータサイエンスにおける浮動小数点 数の加算は結合法則を満たさず、式の結合方法の選択は丸め誤差に大きな影響を与える可能性があります。
例 実数の加算は結合法則を満たす。 結合法則が成り立つ演算の例としては、以下のようなものがあります。
3 つの文字列、、の連結は 、最初の 2 つの文字列を連結してを得て、3 番目の文字列 ( ) を追加する方法、または 2 番目の文字列と 3 番目の文字列を結合して を得て、最初の文字列 ( ) をその結果に連結する方法の 2 つの方法で計算できます。どちらの方法でも同じ結果が得られます。文字列の連結は結合法則を満たしますが、可換法則は満たしません。"hello"" ""world""hello ""world"" world""hello" 算術 では、実数 の加算 と乗算は 結合法則を満たす。つまり、 （ x + y ） + z = x + （ y + z ） = x + y + z （ x y ） z = x （ y z ） = x y z } すべての人々のために x 、 y 、 z ∈ R 。 {\displaystyle \left.{\begin{行列}(x+y)+z=x+(y+z)=x+y+z\quad \\(x\,y)z=x(y\,z)=x\,y\,z\qquad \qquad \qquad \quad \ \ \,\end{行列}}\right\}{\mbox{すべての}}x,y,z\in \mathbb {R} .} 自明な演算x ∗ y = x x ∘ y = y {\displaystyle x\circ y=y} 複素数 と四元数 の加算と乗算は結合法則を満たす。八元数 の加算も結合法則を満たすが、八元数の乗算は結合法則を満たさない。最大公約数と最小公倍数の関数 は 結合法則に従う。 gcd （ gcd （ x 、 y ） 、 z ） = gcd （ x 、 gcd （ y 、 z ） ） = gcd （ x 、 y 、 z ） 最小公倍数 （ 最小公倍数 （ x 、 y ） 、 z ） = 最小公倍数 （ x 、 最小公倍数 （ y 、 z ） ） = 最小公倍数 （ x 、 y 、 z ） } すべての人々のために x 、 y 、 z ∈ Z 。 {\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,z\in \mathbb {Z} .} 集合 の共通部分 または和集合 を取る： （ A ∩ B ） ∩ C = A ∩ （ B ∩ C ） = A ∩ B ∩ C （ A ∪ B ） ∪ C = A ∪ （ B ∪ C ） = A ∪ B ∪ C } すべてのセットについて A 、 B 、 C 。 {\displaystyle \left.{\begin{matrix}(A\cap B)\cap C=A\cap (B\cap C)=A\cap B\cap C\quad \\(A\cup B)\cup C=A\cup (B\cup C)=A\cup B\cup C\quad \end{matrix}}\right\}{\mbox{すべての集合}}A,B,Cについて} M がある集合であり、Sが Mから M へのすべての関数の集合を表す場合、 S 上の関数合成 演算は結合法則を満たす。（ f ∘ g ） ∘ h = f ∘ （ g ∘ h ） = f ∘ g ∘ h すべての人々のために f 、 g 、 h ∈ S 。 {\displaystyle (f\circ g)\circ h=f\circ (g\circ h)=f\circ g\circ h\qquad {\mbox{すべての }}f,g,h\in S について} もう少し一般的に言うと、4つの集合M 、N 、P 、Q があり、h : M → N g : N → P f : P → Q （ f ∘ g ） ∘ h = f ∘ （ g ∘ h ） = f ∘ g ∘ h {\displaystyle (f\circ g)\circ h=f\circ (g\circ h)=f\circ g\circ h} 圏論 において、射の合成は定義により結合法則を満たす。関手と自然変換の結合性は、射の結合性から導かれる。3つの要素A 、B 、C を持つ集合を考えます。次の操作を行います。 結合法則が成り立つ。したがって、例えば、A ( B C ) = ( A B ) C = A 行列は 線形関数 を表し、行列の乗算は 関数の合成を表すため、行列の乗算は結合法則を満たすとすぐに結論づけることができる。[ 3 ] 実数 （および任意の全順序集合 ）の場合、最小値と最大値の演算は結合法則を満たす。最大 （ 1 、 最大 （ b 、 c ） ） = 最大 （ 最大 （ 1 、 b ） 、 c ） そして ミニ （ 1 、 ミニ （ b 、 c ） ） = ミニ （ ミニ （ 1 、 b ） 、 c ） 。 {\displaystyle \max(a,\max(b,c))=\max(\max(a,b),c)\quad {\text{ および }}\quad \min(a,\min(b,c))=\min(\min(a,b),c).}
命題論理
置換規則 標準的な真理関数命題論理では、結合[ 4 ] [ 5 ]または 性 [ 6 ] は、置換の 有効な 規則の2つです。これらの規則により、論理式中の括弧を論理 証明 の中で移動することができます。規則（論理結合子 表記を使用）は次のとおりです。
（ P ∨ （ Q ∨ R ） ） ⇔ （ （ P ∨ Q ） ∨ R ） {\displaystyle (P\lor (Q\lor R))\Leftrightarrow ((P\lor Q)\lor R)}
そして
（ P ∧ （ Q ∧ R ） ） ⇔ （ （ P ∧ Q ） ∧ R ） 、 {\displaystyle (P\land (Q\land R))\Leftrightarrow ((P\land Q)\land R),}
どこ "⇔ {\displaystyle \Leftrightarrow } 証明の 中で に置き換えることができる」を表すメタ論理 記号 です。
真理関数的結合子 結合性は 、真理関数命題論理のいくつかの 論理結合子 の性質です。以下の論理的同値関係は、結合性が特定の結合子の性質であることを示しています。以下（および ↔ は可換であるため、それらの逆）は真理関数トートロジー です。
選言の結合性 （ （ P ∨ Q ） ∨ R ） ↔ （ P ∨ （ Q ∨ R ） ） {\displaystyle ((P\lor Q)\lor R)\leftrightarrow (P\lor (Q\lor R))} 結合の連想性 （ （ P ∧ Q ） ∧ R ） ↔ （ P ∧ （ Q ∧ R ） ） {\displaystyle ((P\land Q)\land R)\leftrightarrow (P\land (Q\land R))} 等価性の結合法則 （ （ P ↔ Q ） ↔ R ） ↔ （ P ↔ （ Q ↔ R ） ） {\displaystyle ((P\leftrightarrow Q)\leftrightarrow R)\leftrightarrow (P\leftrightarrow (Q\leftrightarrow R))} 共同否定は、結合法則を満たさ ない 真理関数結合子の例である。
非連想演算 二項演算* {\displaystyle *} Sは 非結合的と 呼ばれる。記号的には、
（ x * y ） * z ≠ x * （ y * z ） 一部の人にとって x 、 y 、 z ∈ S 。 {\displaystyle (x*y)*z\neq x*(y*z)\qquad {\mbox{一部の }}x,y,z\in S.}
このような演算においては、評価の順序が重要になります 。例えば：
引き算 （ 5 − 3 ） − 2 ≠ 5 − （ 3 − 2 ） {\displaystyle (5-3)-2\,\neq \,5-(3-2)} 分割 （ 4 / 2 ） / 2 ≠ 4 / （ 2 / 2 ） {\displaystyle (4/2)/2\,\neq \,4/(2/2)} 指数関数 2 （ 1 2 ） ≠ （ 2 1 ） 2 {\displaystyle 2^{(1^{2})}\,\neq \,(2^{1})^{2}} ベクトル外積 私 × （ 私 × j ） = 私 × k = − j （ 私 × 私 ） × j = 0 × j = 0 {\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}}} また、有限和では加算は結合法則を満たしますが、無限和（級数 ）の中では結合法則を満たしません。例えば、 （ 1 + − 1 ） + （ 1 + − 1 ） + （ 1 + − 1 ） + （ 1 + − 1 ） + （ 1 + − 1 ） + （ 1 + − 1 ） + ⋯ = 0 {\displaystyle (1+-1)+(1+-1)+(1+-1)+(1+-1)+(1+-1)+(1+-1)+\dots =0} 1 + （ − 1 + 1 ） + （ − 1 + 1 ） + （ − 1 + 1 ） + （ − 1 + 1 ） + （ − 1 + 1 ） + （ − 1 + 1 ） + ⋯ = 1. {\displaystyle 1+(-1+1)+(-1+1)+(-1+1)+(-1+1)+(-1+1)+(-1+1)+\dots =1.}
数学において、非結合的な演算の中には基本的なものがあります。これらは、非結合代数 と呼ばれる構造における乗算としてよく現れ、非結合代数には加算とスカラー乗算 も存在します。例としては、八元数 とリー代数 があります。リー代数では、乗算は結合法則ではなくヤコビ恒等式を満たします。これにより 、無限小変換 の代数的な性質を抽象化することができます。
その他の例としては、準群 、準場 、非結合環 、可換非結合マグマ などがある。
浮動小数点演算の非結合性 数学では、実数の加算と乗算は結合法則を満たします。対照的に、コンピュータサイエンスでは、浮動小数点数の加算と乗算は結合法則を満たし ません 。これは、大きさの異なる値を異なる順序で結合すると、異なる丸め誤差が生じる可能性があるためです。[ 7 ]
これを説明するために、4ビットの仮数部 を持つ浮動小数点表現を考えてみましょう。
(1.000 2 ×2 0 + 1.000 2 ×2 0 ) + 1.000 2 ×2 4 = 1.000 2 ×2 1 2 ×2 4 = 1.00 1 2 ×2 4
1.000 2 ×2 0 + (1.000 2 ×2 0 + 1.000 2 ×2 4 ) = 1.000 2 ×2 0 2 ×2 4 = 1.00 0 2 ×2 4
ほとんどのコンピュータは24ビットまたは53ビットの仮数部で計算を行うが、[ 8 ] Kahan加算アルゴリズム などのアプローチは誤差を最小限に抑える方法である。これは並列コンピューティングでは特に問題となる可能性がある。[ 9 ] [ 10 ]
非結合演算の表記法 一般的に、式の中に非結合演算が複数回出現する場合は、評価の順序 を示すために括弧を使用する必要があります（ただし、表記法が別の方法で順序を指定している場合は除きます）。2 3 / 4 {\displaystyle {\dfrac {2}{3/4}}} 数学者たちは 、いくつかの一般的な非結合演算について、特定の評価順序で合意している。これは単に括弧を避けるための表記上の慣例である。
左結合 演算は、慣習的に左から右に評価される非結合演算です。
1 * b * c = （ 1 * b ） * c 1 * b * c * d = （ （ 1 * b ） * c ） * d 1 * b * c * d * e = （ （ （ 1 * b ） * c ） * d ） * e 等 } すべての人々のために 1 、 b 、 c 、 d 、 e ∈ S {\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)*e\quad \\{\mbox{etc.}}\end{array}}\right\}{\mbox{for all }}a,b,c,d,e\in S}
一方、右結合 演算は慣例的に右から左に評価される。
x * y * z = x * （ y * z ） w * x * y * z = w * （ x * （ y * z ） ） v * w * x * y * z = v * （ w * （ x * （ y * z ） ） ） 等 } すべての人々のために z 、 y 、 x 、 w 、 v ∈ S {\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,v\in S}
左結合演算と右結合演算の両方が発生します。左結合演算には以下が含まれます。
実数の減算と除算[ 11 ] [ 12 ] [ 13 ] [ 14 ] [ 15 ] x − y − z = （ x − y ） − z {\displaystyle x-y-z=(x-y)-z} x / y / z = （ x / y ） / z {\displaystyle x/y/z=(x/y)/z} 機能適用 （ f x y ） = （ （ f x ） y ） {\displaystyle (f\,x\,y)=((f\,x)\,y)} この表記法は、部分的な適用を可能にするカリー化 同型性によって動機づけられる。
右結合演算には以下のものが含まれます。
べき乗 x y z = x （ y z ） {\displaystyle x^{y^{z}}=x^{(y^{z})}} べき乗は、括弧を用いるか、右結合的に用いられるのが一般的です。なぜなら、左結合的なべき乗演算を繰り返してもあまり意味がないからです。べき乗が繰り返される場合は、ほとんどの場合、乗算で書き換えられます。
（ x y ） z = x （ y z ） {\displaystyle (x^{y})^{z}=x^{(yz)}} 正しくフォーマットすると、上付き文字は本質的に括弧のセットとして機能します。たとえば、次の式では2 x + 3 {\displaystyle 2^{x+3}} の前に実行されます。 2 （ x + 3 ） {\displaystyle 2^{(x+3)}} x y z {\displaystyle x^{y^{z}}} y z {\displaystyle y^{z}} x {\displaystyle x} x y z = （ x y ） z {\displaystyle {x^{y}}^{z}=(x^{y})^{z}} x y z = x （ y z ） {\displaystyle x^{yz}=x^{(yz)}} x y z = x （ y z ） {\displaystyle x^{y^{z}}=x^{(y^{z})}}
関数定義 Z → Z → Z = Z → （ Z → Z ） {\displaystyle \mathbb {Z} \rightarrow \mathbb {Z} \rightarrow \mathbb {Z} =\mathbb {Z} \rightarrow (\mathbb {Z} \rightarrow \mathbb {Z} )} x ↦ y ↦ x − y = x ↦ （ y ↦ x − y ） {\displaystyle x\mapsto y\mapsto x-y=x\mapsto (y\mapsto x-y)} これらの演算に右結合記法を用いるのは、カリー・ハワード対応 とカリー化 同型性によって正当化される。
従来の評価順序が定義されていない非結合演算には、以下のものが含まれます。
中置記法による実数のべき乗[ 16 ] （ x ∧ y ） ∧ z ≠ x ∧ （ y ∧ z ） {\displaystyle (x^{\wedge }y)^{\wedge }z\neq x^{\wedge }(y^{\wedge }z)} クヌースの上向き矢印演算子 1 ↑ ↑ （ b ↑ ↑ c ） ≠ （ 1 ↑ ↑ b ） ↑ ↑ c {\displaystyle a\uparrow \uparrow (b\uparrow \uparrow c)\neq (a\uparrow \uparrow b)\uparrow \uparrow c} 1 ↑ ↑ ↑ （ b ↑ ↑ ↑ c ） ≠ （ 1 ↑ ↑ ↑ b ） ↑ ↑ ↑ c {\displaystyle a\uparrow \uparrow \uparrow (b\uparrow \uparrow \uparrow c)\neq (a\uparrow \uparrow \uparrow b)\uparrow \uparrow \uparrow c} 3つのベクトルの外積 をとる 1 → × （ b → × c → ） ≠ （ 1 → × b → ） × c → 一部の人にとって 1 → 、 b → 、 c → ∈ R 3 {\displaystyle {\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}} 実数のペアワイズ平均を取る （ x + y ） / 2 + z 2 ≠ x + （ y + z ） / 2 2 すべての人々のために x 、 y 、 z ∈ R と x ≠ z 。 {\displaystyle {(x+y)/2+z \over 2}\neq {x+(y+z)/2 \over 2}\qquad {\mbox{for all }}x,y,z\in \mathbb {R} {\mbox{ with }}x\neq z.} 集合の相対補集合 を取る （ A ∖ B ） ∖ C ≠ A ∖ （ B ∖ C ） {\displaystyle (A\backslash B)\backslash C\neq A\backslash (B\backslash C)} （論理学における実質的非含意 と比較せよ。）
特定の特殊な場合における可換性との関係 一般に、結合法則を満たす演算は可換ではありません。しかし、特定の特別な条件下では、結合法則が可換性を意味する場合があります。実数直線の区間上で定義された結合法則を満たす演算子は、両方の引数に対して連続かつ単射である場合に可換です。[ 19 ] [ 20 ]
参考文献 ↑ ハンガーフォード、トーマス W. (1974). 代数学 (第 1 版). スプリンガー . p. 24. ISBN 978-0387905181 定義 1.1 (i) a(bc) = (ab)c は、G のすべての a, b, c に対して成り立つ 。↑ ダービン、ジョン・R. (1992). 現代代数学入門 （第3 版）. ニューヨーク：ワイリー. p. 78. ISBN 978-0-471-51001-7 。もし1 1 、 1 2 、 … 、 1 n （ n ≥ 2 ） {\displaystyle a_{1},a_{2},\dots ,a_{n}\,\,(n\geq 2)} 1 1 1 2 ⋯ 1 n {\displaystyle a_{1}a_{2}\cdots a_{n}} ↑ 「行列積の結合法則」 . Khan Academy . 2016年 6月5日 取得 。 ↑ ムーア、ブルック・ノエル、パーカー、リチャード (2017)。 『クリティカル・シンキング』 （第12 版）。ニューヨーク：マグロウヒル・エデュケーション。321 ページ 。ISBN 9781259690877 。↑ Copi, Irving M.; Cohen, Carl; McMahon, Kenneth (2014). Introduction to Logic (14th ed.). Essex: Pearson Education. p. 387. ISBN 9781292024820 。↑ ハーレー、パトリック・J.、ワトソン、ロリ（2016）。 『論理学入門』 （第13 版）。ボストン：センゲージ・ラーニング。427 ページ 。ISBN 9781305958098 。↑ ドナルド・クヌース著『 コンピュータプログラミングの技法 』第3巻、第4.2.2節↑ IEEEコンピュータソサエティ（2008年8月29日）。IEEE 浮動 小数点 演算 規格 。doi ： 10.1109/IEEESTD.2008.4610935。ISBN 978-0-7381-5753-5 IEEE Std 754-2008。↑ Villa, Oreste; Chavarría-mir, Daniel; Gurumoorthi, Vidhya; Márquez, Andrés; Krishnamoorthy, Sriram、「 大規模マルチスレッドシステムにおける数値計算に対する浮動小数点非結合性の影響 （PDF）」 、 2013年2月15日に オリジナル （PDF） からアーカイブ、 2014年 4月8日 に取得 ↑ Goldberg, David (1991 年 3 月). 「浮動小数点演算についてすべてのコンピュータ科学者が知っておくべきこと」 (PDF) . ACM Computing Surveys . 23 (1): 5– 48. doi : 10.1145/103162.103163 . S2CID 222008826 . 2022 年 5 月 19 日にオリジナルから アーカイブ (PDF) . 2016 年 1 月 20 日 に取得 . ↑ ジョージ・マーク・バーグマン「算術演算の順序」 ↑ 「演算順序」。エデュケーションプレイス。 ↑ 「演算順序」、タイムスタンプ5分40秒。カーンアカデミー 。 ↑ 「演算順序の使用と性質の探求」Wayback Machine に2022年7月16日に アーカイブ済み、セクション9。バージニア州教育省。 ↑ Bronstein、 de:Taschenbuch der Mathematik ISBN 978-3-8085-5673-3 ↑ 指数法則と標準数学表記法Codeplea。2016年8月23日。2016年9月20日取得。 ↑ ハミルトン、WR （1844–1850）。 「四元数または代数学における虚数系の新しい体系について」 。デイビッド・R・ウィルキンス・コレクション。 フィロソフィカル・マガジン 。 トリニティ・カレッジ・ダブリン 。 ↑ Baez, John C. (2002). "The Octonions" (PDF) . Bulletin of the American Mathematical Society . 39 (2): 145– 205. arXiv : math/0105155 . doi : 10.1090/S0273-0979-01-00934-X . ISSN 0273-0979 . MR 1886087 . S2CID 586512 . ↑ Aczél, J. (1966-01-01). 関数方程式とその応用に関する講義 . Academic Press. p. 267. ISBN 978-0-08-095525-4 . OL 46920179M . ↑ Ling, Cho-Hsin (1964年9月1日). 「結合関数の表現」 (PDF) . Publicationes Mathematicae . 12 : 189– 212. 
