「結合法則」の版間の差分

2007年5月17日 (木) 22:47時点における版

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

定義

集合 S に二項演算 · が定義されているとき、

<math>a \cdot (b \cdot c) = (a \cdot b) \cdot c</math>

が S の任意の元 a, b, c について成り立てば、この二項演算は結合的である、あるいは結合法則を満たすという。

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

一般結合律

結合法則の成立は、複数回の演算を行う場合にその意味を発揮する。実際、n ≥ 3 として、n 個の元 a₁, a₂, ..., a_n の（この順番での）結合

<math>a_1 \bowtie a_2 \bowtie \cdots \bowtie a_n</math>

を考えるとき、n − 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>

などとなり、考える元の個数が増えるほどに式の表しうる内容の種類が爆発的に増加する。にもかかわらず、ここで演算が結合法則を満たすことが保証されているならば、そのどの意味にとっても（元の順番を変えない限りは）式の評価（演算の結果）が変わらないことを確認することができる。これを一般化された結合法則、一般結合律と呼ぶこともある。

一般結合律が成立するならば、演算の順序を省略して

<math>a_1 \bowtie a_2 \bowtie \cdots \bowtie a_n</math>

という式を考えることに曖昧さが含まれない。だからこそこの式に意味があるのだということができる。

結合代数系

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

プログラミングにおける結合法則

プログラミングにおける結合法則とは、中置記法の演算式において計算の優先順位の一種。たとえば、四則演算では乗除算から加減算の順で計算されるが、同じ優先順位の演算子が複数存在している場合、左から順に計算されるという法則がある。この法則が結合法則である。もちろんプログラミングでは四則演算以外にもさまざまな演算があり、結合法則が右から左に設定されていることもある。

たとえば、上記の優先順位、結合法則における「1 - 2 + 3 x 4」は「((1 - 2) + (3 x 4))」である。ここで注意したいのが、上のような表があった場合に、結合法則が左から右であるからと「+ が - より優先される」と取ってはならないこと。同じ優先順位の各項を「左から右」に計算するのである。

関連記事

• 交換法則
• 分配法則
• 代数的構造