いきなりですが問題です．
結合法則を使って，以下の等式を証明してください．
- ｛（a×b）×c｝×d＝（a×b）×（c×d）
さっそくですが解答です．乗法の結合法則は，（A×B）×C＝A×（B×C）で表されます．ここでA＝a×b，B＝c，C＝dとおくと，（A×B）×C＝｛（a×b）×c｝×dであり，A×（B×C）＝（a×b）×（c×d）です．したがって，｛（a×b）×c｝×d＝（A×B）×C＝A×（B×C）＝（a×b）×（c×d）です．証明終わり．
ここまで，「｛」「｝」を使い，中学高校スタイルで式を書いていましたが，手間軽減のため「(」「)」に置き換えます．2重，3重，…になっても，すべて半角カッコです．それと，「×」も取り除きます．
そうしたところで問題です．
交換法則と結合法則を使って，以下の等式が証明できますか．
- ((ab)c)d＝((dc)b)a
簡単そうに見えないので，Rubyスクリプトを書きました．ソースはgistよりご覧ください．
ファイル名はcatree.rbです．cはcommutative（交換可能），aはassociative（結合可能），それと対象は木構造（カッコを取り除いた，抽象構文木）にしているのでtreeです．
ruby catree.rbを実行すると，「((ab)c)d」の式を起点に，交換法則・結合法則を適用して得ることのできる式と等式を出力していきます．最後に「4 factors: 120 expressions / 360 commutative / 240 associative」と出力します．4つの文字の積では，((ab)c)dを含め120種類の式があり（詳細は後述），式の間で交換可能なのは360通り，結合可能なのは240通りとなります．
出力行数が多く，ここから((ab)c)dから((dc)b)aに至るまでの式変形を得るのは容易ではありませんが，コマンドを何回か実行して，求めることができます．
$ ruby catree.rb | grep '= ((dc)b)a' | head -n 1 associative: (dc)(ba) = ((dc)b)a $ ruby catree.rb | grep '= (dc)(ba)' | head -n 1 associative: d(c(ba)) = (dc)(ba) $ ruby catree.rb | grep '= d(c(ba))' | head -n 1 commutative: (c(ba))d = d(c(ba)) $ ruby catree.rb | grep '= (c(ba))d' | head -n 1 commutative: ((ba)c)d = (c(ba))d $ ruby catree.rb | grep '= ((ba)c)d' | head -n 1 commutative: ((ab)c)d = ((ba)c)d
最初のコマンドは，証明したい右辺の式，((dc)b)aが，この探索でどんな等式ではじめて出現するかを出力します．内部では幅優先探索を行っているので，これがゴールを得るための最短パス（同じ長さのものは，他にあるかもしれませんが）の一部となります．
そうして，出力のイコールの左側を，新たなサブゴールとして繰り返して検索し，((ab)c)dが左辺に現れたら，後戻り作業は終了です．出現した等式を，下から順に並べていくと，((ab)c)d = ((ba)c)d = (c(ba))d = d(c(ba)) = (dc)(ba) = ((dc)b)a を得まして，証明終わりです．
プログラムですが，（grepを通さない場合の）出力の最終行，「4 factors: 120 expressions (以下略)」は，((ab)c)dと（交換法則・結合法則の0回以上，有限回の適用により）等号で結ばれる式が，120種類あることを意味します．そして，a，b，c，dをちょうど1回ずつ使用した積の式の総数と一致します．
数が一致する理由を，積の式から見ていきます．4つの因数，a，b，c，dがこの順に出現する式は，構文木をすべてかくことで5通りあることが分かります．4つの異なる文字の並びは，順列で4!＝24通りですから，それらをかけて120通りです．なお，「構文木をすべてかくことで5通り」は，作成したRubyスクリプトだと次の実行結果と対応します．
ruby catree.rb | grep 'expression:' | grep -E 'a.*b.*c.*d' new expression: ((ab)c)d new expression: (a(bc))d new expression: (ab)(cd) new expression: a((bc)d) new expression: a(b(cd))
プログラムは正整数を引数にとり，因数の数を指定できます．「ruby catree.rb 5」までは，結果が出るのはほぼ瞬時だと思います．「ruby catree.rb 6」は，手元の環境だと10秒ほど，「ruby catree.rb 7」は10分以上かかりました．あるLinuxサーバで「ruby catree.rb 8」を実行すると，メモリを食いつぶしてしまいました．不要な処理を減らして，ただいま再実行中です．
関連：
The commutative, associative, and distributive laws for sums of any number of terms and products of any number of factors follow immediately from I-V. Thus the product of the factors a, b, c, d, taken in any two orders, is the same, since the one order can be transformed into the other by successive interchanges of consecutive letters.
（私訳：任意個の項の和と任意個の因数の積に関して，交換，結合，分配の法則はI-Vから直接導かれる．ゆえにa，b，c，dという4つの因数の積はどのような順序をとっても答えは同じになる．なぜなら一つの順序は，隣り合う文字の交換を繰り返す*4ことで，他の順序に変換できるからである．）*4: 例えばabcd＝bacd＝bcad＝bcda＝cbda＝cdba＝dcba．各等号が成立するのは，乗法の交換法則と結合法則から確かめられます．
かけ算の「順序」は3種類
