結合法則

数学における結合性（けつごうせい、）は、一部の二項演算が持つ性質である。演算が結合的であるために満たされるべき条件を結合法則（けつごうほうそく、; 結合律、結合則）という。命題論理において、結合則（結合規則）はにおける式に対するなのひとつに挙げられる。
ひとつの式の中に同じ結合的演算が一度に複数現れる場合、それらの演算を施す順番は、被演算子の並びの順を変えない限りにおいて、結果に影響を与えない。つまり、（必要ならば中置記法と括弧を使った式に書き換えて）そのような式における括弧の位置を入れ替えても、式の値は変わることはない。例えば、等式: formula_1 や formula_2 を例にとると、各行とも左辺と中辺で括弧の位置が変わっている（そして被演算子の現れる位置は変わっていない）けれども、その値である右辺は変わりないことを述べている。このような関係式は、被演算子を任意の実数とする加法や乗法を計算する限りにおいて満足されるから、それを「実数の加法および乗法は結合的（演算）である」とか、「実数の加法および乗法は（実数全体の成す集合上で）結合法則を満足する」などと言い表す。
結合性は、「二つの被演算子の現れる位置を入れ替えても結果が変わらない」ことを意味する可換則とは異なる。例えば、実数の乗法が可換演算であるのは、実数の乗法において被演算子の順番を変えてもよいこと—つまり —が満足されることによる。
結合的演算は数学において遍く存在する。事実として、多くの代数的構造（例えば半群や圏）では、それらの持つ二項演算が結合的であることを明示的に要請される。
とはいえ、重要で意義のある非結合的演算もたくさん存在する。例えば減法、冪演算、ベクトルの交叉積などはそうである。
定義.
厳密に、集合 上で定義された二項演算 が結合的であるとは、 formula_3 を満足するときに言う。ここで、 は考えたい演算（それを一般に「乗法」や「積」と呼んだりする）を表す記号（演算子）であって、これは別にどのような記号が用いられてもよいし、あまつさえ「乗法」を表す記号のない併置 (juxtaposition) 記法で formula_4 と書くこともある。
結合法則を函数記法で表すこともでき、その場合は formula_5 のようになる。
一般化された結合法則.
二項演算が結合的ならば、その演算が反復して適用されるとき、その式においてきちんと（開きと閉じが）対になる括弧がどのように挿入されるかを気にすることなく、その演算結果が同じであることがわかる。そのことを一般化された結合法則 ("generalized associative law") と言う。実例として、四つの元の積を、それらの因子の順番を変えることなく書き下せば、五種類の異なる計算順序が考えられる:
が、これらの積を得る演算が結合的ならば、一般化された結合法則の述べるに従い、これらすべてが同じ値の積であることが結論される。となれば（これらの式から括弧をすべて取り払った式に既に別の意味が施されているのでない限り）この積において括弧は「不要」のものと考えることができて、この積を紛れの虞なく formula_11 と書くことができる。
このような繰り返しの積において、因子となる元の数が増えるにしたがって、釣り合いのとれた括弧の挿入の仕方の総数は急速に増加するけれども、演算が結合的ならばそれらの区別もやはり必要がなくなる。
結合的だからといって単純に括弧を取り去ってはいけない例として、 を挙げよう。 は結合的であって は に同値であるが、 はふつうは の意味であって先のふたつとは同値でない。
例.
結合的演算の例をいくつか挙げる:
命題論理.
結合規則.
標準的な真理函数的命題論理において、結合則 ("association", "associativity") は二つのなを言う。それは、における論理式に現れる括弧の位置を動かしてもよい規則を述べるもので、論理結合子を用いて書けば
のふたつである。ただし、"formula_19" はので、「形式的証明において置換してよい」ことを表す。
論理演算の結合性.
真理函数的命題論理における真理函数の結合子のいくつかは結合性 ("associativity") を持つ。以下の（これらは真理函数的恒真式である）は結合性が特定の結合子の持つ性質であることを示している :
接合否定 (joint denial) は結合的でない真理函数結合子の例である。
非結合的演算.
集合 上の二項演算 が結合法則を満足しない—記号で書けば formula_26 —となるとき、非結合的 ("non-associative") である、必ずしも結合的でないなどという。
そのような演算では、計算順序は結果に影響する。非結合演算の例として
などがある。あるいは無限和もまた一般には非結合的である。例えば: formula_30
非結合的構造の研究は、古典代数学の主流からはいくらか異なった理由から生じてくるものである。非結合多元環の領域にあってすでに一大分野へと発展したリー代数の理論では、結合法則の代わりにヤコビ恒等式が採用される。リー代数はの本質的な特質を抽象化するものであり、数学に遍在するものとなった。
既に深く調べられているほかの特定種類の非結合的構造もあり、それらは何らかの特定の応用から、あるいは組合せ論のような分野から生じたものである。その他の例は、、、非結合的環、非結合的多元環、など。
非結合的演算の記法.
非結合的演算が一つの式の中で複数回現れるときには、評価の順を指し示すために括弧を挿入することは（例えば のように、ほかの方法で順番を指定する記法を用いているのでない限り）一般には不可避である。とはいえ、いくつかのよく用いられる非結合的演算については、特定の順番に評価することにして括弧の使用を回避する簡便記法が、受け入れられている。
左結合 ("left-associative") 演算とは、規約として左から右に評価する—式で書けば formula_31 を意味する—演算を言う。同様に右結合 ("right-associative") 演算は、右から左に評価するものと約束する: formula_32
左結合演算も右結合演算もどちらも生じ得る。左結合演算の例:
右結合演算の例:
評価順について特定の規約がない演算の例:
プログラミング言語.
中置記法を採用しているプログラミング言語においては、任意の演算子について数学で言うところの結合法則が成り立たないことを仮定して、その式の意味をどういった順序で、値を演算子により結合させたものとするかについて、それぞれの言語にそれぞれ法則がある。「演算子の優先順位」() と「」（) と言う。
なお、優先順位と結合性は値の扱いに関する規則であって、式の評価の順序に関する規則ではないことに注意が必要である。評価順は優先順位と結合性に直感的に従っていることもあれば、従っていないこともある。言語仕様としては決められていないこともある（評価順と関連するものとして、短絡評価がある。短絡評価のためには評価順が決まっている必要があるため、一般に演算子の左辺と右辺の評価順を決めていないC言語だが、短絡評価される演算子については決まっている。Javaは仕様で全て決めている。Adaでは両辺を評価する演算子と短絡評価の演算子とが用意されている。）。
優先順位と結合性は、仕様上の表現としては構文規則の一部として決まっているものが多い（たいていは便利さのために別表にまとめられている。yaccのように通常の規則とは別建てで定義できるものもある）。ここでは例として、四則演算を主に挙げるが、他の演算子についても規則は同様にある。
優先順位.
（ここでの前提である、中置記法を採用している）たいていのプログラミング言語の四則演算の演算子において、加減算より乗除算のほうが優先順位が高い、としているものが多い。
すなわち a * b + c は (a * b) + c という意味であり、a - b / c は a - (b / c) という意味である。
多くの演算子を持ち、その数に応じて多くの優先順位を定めているC言語のような言語もあれば、ほとんど優先順位が無く、次節で説明する結合性のみで、どんな演算も左から右、あるいは右から左（たとえばAPL）といったように決めている言語もある。
結合性.
（前節と同様、中置記法を採用している）たいていのプログラミング言語の四則演算の演算子において、加算と減算、乗算と除算のそれぞれの間には優先順位に差が無い。加減算の連続、たとえば a + b - c + d - e というような式は、左から順に (((a + b) - c) + d) - e という意味となる。このような結合を"左結合" ()、あるいは"左から右" () と言う。逆が"右結合"（)、あるいは"右から左" () である。
右結合の例としては、C系の言語に特徴的な代入演算子 = は右結合である。a = b = 1; という式文における式は a = (b = 1) という意味であり b = 1 という代入演算子による式の値は 1 なので、それが a に(も)代入され、結果として a と b に 1 が代入される。
冪乗の演算子として ** や ^ がある言語があるが、数学の記法では formula_48 と formula_49 のように、左を先にしたい場合に括弧が要るので、右結合すなわち a**b**c は a**(b**c) という意味であるとしたほうが数学の記法とは一致するが（たとえばRubyでは ** は右結合である（オブジェクトの種類等によるものではなく、構文上の規則である））、VBのように算術演算は全て左結合としているため冪乗の ^ も左結合、という言語もある。
非結合（non-associative）は、右結合でも左結合でもない、たとえば比較演算子 < のように、a < b < c の意味が (a < b) < c でも a < (b < c) でもない、というような演算子の結合性である（C言語では左結合として解釈し、比較結果の真理値を整数0か1として、次の比較を行うという通常は意図しない意味を持ってしまう。Pythonのように a < b < c と書いて、意図した通りの意味になる言語もある）。加算や乗算のみの演算のような順序によらない演算には順序を定めない、という言語も考えられるが、あまり見られない（算術と違いコンピュータ上の計算ではオーバーフロー等のために、真に順序によらない計算は実はあまりない、という事情もある）。