結合法則のソースを表示

[[数学]]、殊に[[代数学]]における'''結合法則'''（けつごうほうそく、{{lang-en-short|''associative law''}}) 、'''結合則'''、'''結合律'''あるいは演算の'''結合性'''（けつごうせい、{{lang-en-short|''associativity''}}）は[[二項演算]]に対して考えられる性質の一つ。ひとつの数式中で演算が一度よりも多く行われるとき、その演算を評価する順番に関わらず結果が同じになるような演算は結合的 ({{lang-en-short|''associative''}}) であるといわれる。

== 定義 ==
[[集合]] ''S'' に[[二項演算]] &middot; が定義されているとき、
:<math>a \cdot (b \cdot c) = (a \cdot b) \cdot c</math>
が ''S'' の任意の元 ''a'', ''b'', ''c'' について成り立てば、この二項演算は'''結合的'''である、あるいは'''結合法則'''を満たすという。

*[[実数]]や[[複素数]]に関する足し算やかけ算は結合法則を満たしている。
*引き算や割り算はそうではない。
*[[ベクトル]]や[[行列]]の和と積は結合法則を満たす。
*3次元[[数ベクトル空間]]に関するベクトル積は結合法則を満たさない。

== 一般結合律 ==
結合法則の成立は、複数回の演算を行う場合にその意味を発揮する。実際、''n'' &ge; 3 として、''n'' 個の元 ''a''<sub>1</sub>, ''a''<sub>2</sub>, ..., ''a''<sub>''n''</sub> の（この順番での）結合
:<math>a_1 \bowtie a_2 \bowtie \cdots \bowtie a_n</math>
を考えるとき、''n'' &minus; 1 回行われる評価を（演算が意味を持つ限り）どういう順番で指定するかによって式の意味が異なるために、どの意味であるかを考える必要が生じる。たとえば 3 個の元の結合なら「括弧の中から計算する」という規則を立てれば
:<math>(a \bowtie b) \bowtie c,\ a \bowtie(b \bowtie c)</math>
の二通りあり、一般にはたとえ一方の式が定義されたとしても、それだけでは両者の値の一致はおろか他方の式の存在すら保証されない。各演算が異なる定義域をもつ異なる演算である場合
:<math>(a \bowtie b) \boxtimes c,\ a \bowtie (b \boxtimes c)</math>
も同様だが、その結合性の意味はなおさらはっきりと重要である。

''n'' = 4 とすれば
:<math>((a_1 \bowtie a_2) \bowtie a_3) \bowtie a_4,\ (a_1 \bowtie (a_2 \bowtie a_3)) \bowtie a_4,\ 
  a_1 \bowtie ((a_2 \bowtie a_3) \bowtie a_4),</math>
:<math> a_1 \bowtie (a_2 \bowtie (a_3 \bowtie a_4)),\ (a_1 \bowtie a_2) \bowtie (a_3 \bowtie a_4)</math>
などとなり、考える元の個数が増えるほどに式の表しうる内容の種類が爆発的に増加する（具体的には n-1 番目の[[カタラン数]]となる）。にもかかわらず、ここで演算が結合法則を満たすことが保証されているならば、そのどの意味にとっても（元の順番を変えない限りは）式の評価（演算の結果）が変わらないことを確認することができる。これを'''一般化された結合法則'''、一般結合律と呼ぶこともある。

一般結合律が成立するならば、演算の順序を省略して
:<math>a_1 \bowtie a_2 \bowtie \cdots \bowtie a_n</math>
という式を考えることに曖昧さが含まれない。だからこそこの式に意味があるのだということができる。

== 結合代数系 ==
結合法則を満たす二項演算が定義された[[代数系]]を[[半群]]という。

== プログラミング言語 ==
[[中置記法]]を採用している[[プログラミング言語]]においては、任意の演算子について数学で言うところの結合法則が成り立たないことを仮定して、その[[式 (プログラミング)|式]]の[[プログラム意味論|意味]]をどういった順序で、値を演算子により結合させたものとするかについて、それぞれの言語にそれぞれ法則がある。「[[演算子の優先順位]]」({{lang-en-short|''Operator precedence''}}) と「演算子の結合性」（{{lang-en-short|''Operator associativity''}}) と言う。

なお、優先順位と結合性は値の扱いに関する規則であって、'''式の評価の順序に関する規則ではない'''ことに注意が必要である。評価順は優先順位と結合性に直感的に従っていることもあれば、従っていないこともある。言語仕様としては決められていないこともある（評価順と関連するものとして、[[短絡評価]]がある。短絡評価のためには評価順が決まっている必要があるため、一般に演算子の左辺と右辺の評価順を決めていないC言語だが、短絡評価される演算子については決まっている。[[Java]]は仕様で全て決めている）。

優先順位と結合性は、仕様上の表現としては構文規則の一部として決まっているものが多い（たいていは便利さのために別表にまとめられている。[[yacc]]のように通常の規則とは別建てで定義できるものもある）。ここでは例として、四則演算を主に挙げるが、他の演算子についても規則は同様にある。

=== 優先順位 ===
{{main|演算子の優先順位#プログラミング言語}}
（ここでの前提である、中置記法を採用している）たいていのプログラミング言語の四則演算の演算子において、加減算より乗除算のほうが優先順位が高い、としているものが多い。

すなわち a * b + c は (a * b) + c という意味であり、a - b / c は a - (b / c) という意味である。

多くの演算子を持ち、その数に応じて多くの優先順位を定めているC言語のような言語もあれば、ほとんど優先順位が無く、次節で説明する結合性のみで、どんな演算も左から右、あるいは右から左（たとえば[[APL]]）といったように決めている言語もある。

=== 結合性 ===
（前節と同様、中置記法を採用している）たいていのプログラミング言語の四則演算の演算子において、加算と減算、乗算と除算のそれぞれの間には優先順位に差が無い。加減算の連続、たとえば a + b - c + d - e というような式は、左から順に (((a + b) - c) + d) - e という意味となる。このような結合を"'''左結合'''" ({{lang-en-short|''left-associative''}})、あるいは"左から右" ({{lang-en-short|''left to right''}}) と言う。逆が"'''右結合'''"（{{lang-en-short|''right-associative''}})、あるいは"右から左" ({{lang-en-short|''right to left''}}) である。

右結合の例としては、C系の言語に特徴的な代入演算子 = は右結合である。a = b = 1; という式文における式は a = (b = 1) という意味であり b = 1 という代入演算子による式の値は 1 なので、それが a に(も)代入され、結果として a と b に 1 が代入される。

[[冪乗]]の演算子として ** 乃至 ^ がある言語があるが、数学の記法では<math>a^{b^c}</math>と<math>(a^b)^c</math>のように、左を先にしたい場合に括弧が要るので、右結合すなわち a**b**c は a**(b**c) という意味であるとしたほうが数学の記法とは一致するが（たとえば[[Ruby]]では ** は右結合である（オブジェクトの種類等によるものではなく、構文上の規則である））、[[Microsoft Visual Basic|VB]]のように算術演算は全て左結合としているため冪乗の ^ も左結合<ref>http://msdn.microsoft.com/en-us/library/vstudio/zh100ckf.aspx</ref>、という言語もある。

'''非結合'''（non-associative）は、右結合でも左結合でもない、たとえば比較演算子 &lt; のように、a &lt; b &lt; c の意味が (a &lt; b) &lt; c でも a &lt; (b &lt; c) でもない、というような演算子の結合性である（C言語では左結合として解釈し、比較結果の真理値を整数0か1として、次の比較を行うという通常は意図しない意味を持ってしまう。Pythonのように a &lt; b &lt; c と書いて、意図した通りの意味になる言語もある）。加算や乗算のみの演算のような順序によらない演算には順序を定めない、という言語も考えられるが、あまり見られない（算術と違いコンピュータ上の計算ではオーバーフロー等のために、真に順序によらない計算は実はあまりない、という事情もある）。

==注==
<references/>

==関連記事==
*[[交換法則]]
*[[分配法則]]
*[[代数的構造]]

[[Category:代数的構造|けつこうほうそく]]
[[Category:初等数学|けつこうほうそく]]
[[Category:数学の法則|けつこうほうそく]]
[[Category:数学に関する記事|けつこうほうそく]]