結合法則

数学における結合性は、一部の二項演算が持つ性質である。演算が結合的であるために満たされるべき条件を結合法則という。命題論理において、結合則は形式的証明における式に対する論理的妥当性な置換規則のひとつに挙げられる。

ひとつの式の中に同じ結合的演算が一度に複数現れる場合、それらの演算を施す順番は、被演算子の並びの順を変えない限りにおいて、結果に影響を与えない。つまり、そのような式における括弧の位置を入れ替えても、式の値は変わることはない。例えば、等式: や を例にとると、各行とも左辺と中辺で括弧の位置が変わっているけれども、その値である右辺は変わりないことを述べている。このような関係式は、被演算子を任意の実数とする加法や乗法を計算する限りにおいて満足されるから、それを「実数の加法および乗法は結合的である」とか、「実数の加法および乗法は結合法則を満足する」などと言い表す。

結合性は、「二つの被演算子の現れる位置を入れ替えても結果が変わらない」ことを意味する可換則とは異なる。例えば、実数の乗法が可換演算であるのは、実数の乗法において被演算子の順番を変えてもよいこと—つまり 1=//a// × //b// = //b// × //a//}}—が満足されることによる。

結合的演算は数学において遍く存在する。事実として、多くの代数的構造では、それらの持つ二項演算が結合的であることを明示的に要請される。

とはいえ、重要で意義のある非結合的演算もたくさん存在する。例えば減法、冪演算、ベクトルの交叉積などはそうである。

1. 定義
-----

厳密に、集合 S}} 上で定義された二項演算 ∗}} が結合的であるとは、結合法則}} を満足するときに言う。ここで、∗}} は考えたい演算を表す記号であって、これは別にどのような記号が用いられてもよいし、あまつさえ「乗法」を表す記号のない併置  記法で と書くこともある。

結合法則を函数記法で表すこともでき、その場合は のようになる。

2. 一般化された結合法則
-------------

二項演算が結合的ならば、その演算が反復して適用されるとき、その式においてきちんと対になる括弧がどのように挿入されるかを気にすることなく、その演算結果が同じであることがわかる。そのことを一般化された結合法則  と言う。実例として、四つの元の積を、それらの因子の順番を変えることなく書き下せば、五種類の異なる計算順序が考えられる:
が、これらの積を得る演算が結合的ならば、一般化された結合法則の述べるに従い、これらすべてが同じ値の積であることが結論される。となればこの積において括弧は「不要」のものと考えることができて、この積を紛れの虞なく と書くことができる。

このような繰り返しの積において、因子となる元の数が増えるにしたがって、釣り合いのとれた括弧の挿入の仕方の総数は急速に増加するけれども、演算が結合的ならばそれらの区別もやはり必要がなくなる。

結合的だからといって単純に括弧を取り去ってはいけない例として、双条件論理結合子 ↔}} を挙げよう。↔}} は結合的であって //A// ↔ }} は  ↔ C}} に同値であるが、A ↔ B ↔ C}} はふつうは math の意味であって先のふたつとは同値でない。

3. 例
----

結合的演算の例をいくつか挙げる:

文字列の連接: 三つの文字列 "hello", " ", "world" の連接を計算するのに、最初の二つをつないで "hello ") を得てから三つ目の "world" をつなぐのと、後の二つをつないで " world" を得てから一つ目の "hello" をつなぐのと、二種類の仕方があるがこれらは同じ結果になる。ゆえに文字列の連接は結合的である。
算術における実数の加法および乗法は結合的である。すなわち が成立する。この結合性により、グループ化を表す括弧は曖昧さを生むことなく除去できる。
右自明演算 1=//x// ∗ //y// = //x//}}は結合的だが可換でない。同様に左自明演算 1=//x// ∘ //y// = //y//}}は結合的であり可換でない。
複素数および四元数の加法および乗法。八元数は加法は結合的だが乗法は結合的でない。
最大公約数をとる演算および最小公倍数をとる演算は結合的である:
集合の交叉および合併:
適当な集合 M}} に対する M}} 上の自己写像全体の成す集合 //S// coloneqq}} [[配置集合について、S}} 上で定義された合成演算 ∘}} は結合的である:
少し一般に、四つの集合 //M, N, P, Q//}} とそれらの間の写像 //h//: //M// → //N//}}, //g//: //N// → //P//}}, //f//: //P// → //Q//}} についてやはり が成り立つ。要するに写像の合成は常に結合的である。
三元集合 mset に演算を以下の乗積表に従って定めたものは結合的である:
通常の行列の積は結合的である。行列は線型写像を表現し、行列の積は線型写像の合成に対応するから、合成について既に見たことから行列の積の結合性は直ちに得られる。

4. 命題論理
-------

4.1. 結合規則
---------

標準的な真理函数的命題論理において、結合則  は二つの論理的妥当性な置換規則を言う。それは、形式的証明における論理式に現れる括弧の位置を動かしてもよい規則を述べるもので、論理結合子を用いて書けば

のふたつである。ただし、"" はメタ論理の形式的記号で、「形式的証明において置換してよい」ことを表す。

4.2. 論理演算の結合性
-------------

真理函数的命題論理における真理函数の結合子のいくつかは結合性  を持つ。以下の論理同値は結合性が特定の結合子の持つ性質であることを示している :

選言の結合性: 連言の結合性 論理同値の結合性:接合否定  は結合的でない真理函数結合子の例である。

5. 非結合的演算
---------

集合 S}} 上の二項演算 ∗}} が結合法則を満足しない—記号で書けば —となるとき、非結合的  である、必ずしも結合的でないなどという。

そのような演算では、計算順序は結果に影響する。非結合演算の例として

減法:
除法:
冪演算: などがある。あるいは無限和もまた一般には非結合的である。例えば:

非結合的構造の研究は、古典代数学の主流からはいくらか異なった理由から生じてくるものである。非結合多元環の領域にあってすでに一大分野へと発展したリー代数の理論では、結合法則の代わりにヤコビ恒等式が採用される。リー代数は無限小変換の本質的な特質を抽象化するものであり、数学に遍在するものとなった。

既に深く調べられているほかの特定種類の非結合的構造もあり、それらは何らかの特定の応用から、あるいは組合せ論のような分野から生じたものである。その他の例は、Quasigroup、準体、非結合的環、非結合的多元環、可換マグマなど。

5.1. 非結合的演算の記法
--------------

非結合的演算が一つの式の中で複数回現れるときには、評価の順を指し示すために括弧を挿入することは一般には不可避である。とはいえ、いくつかのよく用いられる非結合的演算については、特定の順番に評価することにして括弧の使用を回避する簡便記法が、受け入れられている。

左結合  演算とは、規約として左から右に評価する—式で書けば を意味する—演算を言う。同様に右結合  演算は、右から左に評価するものと約束する: 左結合演算も右結合演算もどちらも生じ得る。左結合演算の例:

実数の減法および除法:
函数の適用: この記法はカリー化の同型によって動機づけられる。右結合演算の例:

実数の冪: 冪演算は、反復的な左結合冪演算にあまり需要がないため、括弧が付かない場合にはふつう右結合的とする。
正しく組まれている限り、上付き添字それ自体に括弧で括るのと本質的に同じ効果が期待できる。例えば 2exp という式では右肩の和の計算が冪をとるよりも先に行われ、それは括弧で括って 2exp と明示的に書いたときに期待される計算順序になっている。それゆえ、xexp のような式が与えられたときは、底 x}} に対する全体の冪指数 yexp がまず計算されるのは必定である。とはいえ、手書きする場合などは特にそうだが、文脈によっては の判別が難しいこともある。そういった場合には、ふつう右結合性が暗黙に用いられている。
写像の合成: これらの演算の右結合記法は、カリー–ハワード対応およびカリー化同型に動機づけられる。評価順について特定の規約がない演算の例:

実数の冪演算:
クヌースの矢印記法:
ベクトルの交叉積:
実数の対ごとの算術平均:
集合の差: は と一致しない。

6. プログラミング言語
------------

中置記法を採用しているプログラミング言語においては、任意の演算子について数学で言うところの結合法則が成り立たないことを仮定して、その式の意味をどういった順序で、値を演算子により結合させたものとするかについて、それぞれの言語にそれぞれ法則がある。「演算子の優先順位」 と「演算子の結合性」