補題：32bit符号なし整数変数間の算術和演算をブール関数で表す　その２

乱数調整

初期seedから日時を求める無謀な挑戦 - Plus Le Toolのための補題。
以下で使う記号の定義については[id:plusletool:20130427:p2]を参照。
また、以下では独自に定義した関数 \mathfrak{C}_{r} を使うが、これについては[id:plusletool:20130612:p1]を参照。

補題：32bit符号なし整数変数間の算術和演算をブール関数で表す - Plus Le Toolの続き。
自力では絶対無理だと思ってたけど、あることに気づいたらあっさり解けちゃった……


とりあえず問題の確認から。
解きたい問題は次の漸化式だった。

（★１）[id:plusletool:20130615:p1]（＊23）再掲
\begin{array}{lclcrcrcl}x_{i}&=&\mathfrak{C}_{1}\left(\Phi_{i}\right)&\oplus&\left(c_{i}\,\oplus\,d_{i}\right)&&&\,&\left(\mathrm{as}\,1\le i\le 32\right)\\c_{i+1}&=&\mathfrak{C}_{2}\left(\Phi_{i}\right)&\oplus&\mathfrak{C}_{1}\left(\Phi_{i}\right)\left(c_{i}\,\oplus\,d_{i}\right)&\oplus&c_{i}d_{i}&\,&\left(\mathrm{as}\,1\le i\le 31\right)\\d_{i+2}&=&\mathfrak{C}_{4}\left(\Phi_{i}\right)&\oplus&\mathfrak{C}_{3}\left(\Phi_{i}\right)\left(c_{i}\,\oplus\,d_{i}\right)&\oplus&\mathfrak{C}_{2}\left(\Phi_{i}\right)c_{i}d_{i}&\,&\left(\mathrm{as}\,1\le i\le 30\right)\end{array}
\begin{array}{lclcl}\\c_{1}&&&=&0\\d_{1}&=&d_{2}&=&0\end{array}

以前解いた時は c_{i}'=c_{i}\,\oplus\,\mathfrak{C}_{2}\left(\Phi_{i-1}\right) と定義して d_{i} を消去してから変形していったが、うまくいかなかった。
失敗の原因は、 c_{i} と d_{i} の対称性を利用せずに安直に d_{i} を消去しちゃったことにあると考える。
よって今回は、 c_{i}' の他に d_{i}' を使って変形していくことにする。

具体的には、 c_{i}' ， d_{i}' を次のように定義する。

（＊１）
\begin{array}{lcl}c_{1}'&=&0\\c_{i}'&=&c_{i}\,\oplus\,\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\;\;\left(\,\mathrm{as}\,i\ge 2\,\right)\\d_{1}'&=&0\\d_{2}'&=&0\\d_{i}'&=&d_{i}\,\oplus\,\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\;\;\left(\,\mathrm{as}\,i\ge 3\,\right)\end{array}

Ｑ．この定義はどこから出てきたのですか？
Ａ．試行錯誤の末の結果なのでなんとも……　ただ、最初にこう置いておくと計算量が減ることだけは確か。
とにかく、（＊１）を使うと（★１）の第２式，第３式はそれぞれ（＊２）（＊３）のように変形できる。

（＊２）
\begin{array}{lcl}c_{i+1}'&=&\mathfrak{C}_{1}\left(\Phi_{i}\right)\left(c_{i}\,\oplus\,d_{i}\right)\,\oplus\,c_{i}d_{i}\\&=&\mathfrak{C}_{1}\left(\Phi_{i}\right)\left(c_{i}'\,\oplus\,\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\,\oplus\,d_{i}'\,\oplus\,\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\right)\,\oplus\,\left(c_{i}'\,\oplus\,\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\right)\left(d_{i}'\,\oplus\,\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\right)\\&=&\mathfrak{C}_{1}\left(\Phi_{i}\right)\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\,\oplus\,\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\,\oplus\,\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\mathfrak{C}_{1}\left(\Phi_{i}\right)\\&\oplus&\left(\mathfrak{C}_{1}\left(\Phi_{i}\right)\,\oplus\,\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\right)c_{i}'\,\oplus\,\left(\mathfrak{C}_{1}\left(\Phi_{i}\right)\,\oplus\,\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\right)d_{i}'\,\oplus\,c_{i}'d_{i}'\end{array}

（＊３）
\begin{array}{lcl}d_{i+2}'&=&\mathfrak{C}_{3}\left(\Phi_{i}\right)\left(c_{i}\,\oplus\,d_{i}\right)\,\oplus\,\mathfrak{C}_{2}\left(\Phi_{i}\right)c_{i}d_{i}\\&=&\mathfrak{C}_{2}\left(\Phi_{i}\right)\left(\mathfrak{C}_{1}\left(\Phi_{i}\right)\left(c_{i}\,\oplus\,d_{i}\right)\,\oplus\,c_{i}d_{i}\right)\\&=&\mathfrak{C}_{2}\left(\Phi_{i}\right)c_{i+1}'\end{array}

（＊２）を適当に移項すると、

（＊４）
\begin{array}{lcl}c_{i}'d_{i}'&=&\mathfrak{C}_{1}\left(\Phi_{i}\right)\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\,\oplus\,\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\,\oplus\,\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\mathfrak{C}_{1}\left(\Phi_{i}\right)\\&\oplus&\left(\mathfrak{C}_{1}\left(\Phi_{i}\right)\,\oplus\,\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\right)c_{i}'\,\oplus\,\left(\mathfrak{C}_{1}\left(\Phi_{i}\right)\,\oplus\,\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\right)d_{i}'\,\oplus\,c_{i+1}'\end{array}

また（＊３）の添字を１下げることで、

（＊５）
d_{i+1}'=\mathfrak{C}_{2}\left(\Phi_{i-1}\right)c_{i}'

よって（＊２）と（＊５）の辺々を論理積して整理すると、次のようになる。

（＊６）
\begin{array}{lcl}c_{i+1}'d_{i+1}'&=&\left({\mathfrak{C}_{1}\left(\Phi_{i}\right)\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\,\oplus\,\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\,\oplus\,\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\mathfrak{C}_{1}\left(\Phi_{i}\right)\\\;\;\,\oplus\,\left(\mathfrak{C}_{1}\left(\Phi_{i}\right)\,\oplus\,\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\right)c_{i}'\,\oplus\,\left(\mathfrak{C}_{1}\left(\Phi_{i}\right)\,\oplus\,\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\right)d_{i}'\,\oplus\,c_{i}'d_{i}'}\right)\mathfrak{C}_{2}\left(\Phi_{i-1}\right)c_{i}'\\&=&\mathfrak{C}_{1}\left(\Phi_{i}\right)\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\mathfrak{C}_{4}\left(\Phi_{i-2}\right)c_{i}'\,\oplus\,\mathfrak{C}_{1}\left(\Phi_{i}\right)\mathfrak{C}_{2}\left(\Phi_{i-1}\right)c_{i}'d_{i}'\end{array}

（＊６）の右辺の c_{i}'d_{i}' に（＊４）を代入して、

（＊７）
\begin{array}{lcl}c_{i+1}'d_{i+1}'&=&\mathfrak{C}_{1}\left(\Phi_{i}\right)\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\mathfrak{C}_{4}\left(\Phi_{i-2}\right)c_{i}'\\&\oplus&\mathfrak{C}_{1}\left(\Phi_{i}\right)\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\left({\mathfrak{C}_{1}\left(\Phi_{i}\right)\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\,\oplus\,\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\,\oplus\,\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\mathfrak{C}_{1}\left(\Phi_{i}\right)\\\;\;\,\oplus\,\left(\mathfrak{C}_{1}\left(\Phi_{i}\right)\,\oplus\,\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\right)c_{i}'\,\oplus\,\left(\mathfrak{C}_{1}\left(\Phi_{i}\right)\,\oplus\,\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\right)d_{i}'\,\oplus\,c_{i+1}'}\right)\\&=&\mathfrak{C}_{1}\left(\Phi_{i}\right)\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\,\oplus\,\mathfrak{C}_{1}\left(\Phi_{i}\right)\mathfrak{C}_{2}\left(\Phi_{i-1}\right)c_{i+1}'\,\oplus\,\mathfrak{C}_{1}\left(\Phi_{i}\right)\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\mathfrak{C}_{2}\left(\Phi_{i-1}\right)c_{i}'\\&=&\mathfrak{C}_{1}\left(\Phi_{i}\right)\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\,\oplus\,\mathfrak{C}_{1}\left(\Phi_{i}\right)\mathfrak{C}_{2}\left(\Phi_{i-1}\right)c_{i+1}'\,\oplus\,\mathfrak{C}_{1}\left(\Phi_{i}\right)\mathfrak{C}_{2}\left(\Phi_{i-1}\right)d_{i+1}'\end{array}

最後の行は（＊５）を使った。
これはやや強引なやり方で、答えを知ってないとこの変形には普通気づかないだろうが、説明の都合なので許して(・ω<)ﾃﾍﾍﾟﾛ

（＊７）の添字を１下げると、

（＊８）
c_{i}'d_{i}'=\mathfrak{C}_{1}\left(\Phi_{i-1}\right)\mathfrak{C}_{2}\left(\Phi_{i-2}\right)\,\oplus\,\mathfrak{C}_{1}\left(\Phi_{i-1}\right)\mathfrak{C}_{2}\left(\Phi_{i-2}\right)c_{i}'\,\oplus\,\mathfrak{C}_{1}\left(\Phi_{i-1}\right)\mathfrak{C}_{2}\left(\Phi_{i-2}\right)d_{i}'

（＊８）を（＊２）の右辺の c_{i}'d_{i}' に代入し、さらに（＊５）の辺々を排他的論理和して整理すると、（＊９）のようになる。

（＊２）再掲
\begin{array}{lcl}c_{i+1}'&=&\mathfrak{C}_{1}\left(\Phi_{i}\right)\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\,\oplus\,\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\,\oplus\,\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\mathfrak{C}_{1}\left(\Phi_{i}\right)\\&\oplus&\left(\mathfrak{C}_{1}\left(\Phi_{i}\right)\,\oplus\,\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\right)c_{i}'\,\oplus\,\left(\mathfrak{C}_{1}\left(\Phi_{i}\right)\,\oplus\,\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\right)d_{i}'\,\oplus\,c_{i}'d_{i}'\end{array}

（＊５）再掲
d_{i+1}'=\mathfrak{C}_{2}\left(\Phi_{i-1}\right)c_{i}'

（＊９）
\begin{array}{lcl}c_{i+1}'\,\oplus\,d_{i+1}'&=&\mathfrak{C}_{1}\left(\Phi_{i}\right)\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\,\oplus\,\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\,\oplus\,\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\mathfrak{C}_{1}\left(\Phi_{i}\right)\\&\oplus&\left(\mathfrak{C}_{1}\left(\Phi_{i}\right)\,\oplus\,\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\right)c_{i}'\,\oplus\,\left(\mathfrak{C}_{1}\left(\Phi_{i}\right)\,\oplus\,\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\right)d_{i}'\\&\oplus&\mathfrak{C}_{1}\left(\Phi_{i-1}\right)\mathfrak{C}_{2}\left(\Phi_{i-2}\right)\,\oplus\,\mathfrak{C}_{1}\left(\Phi_{i-1}\right)\mathfrak{C}_{2}\left(\Phi_{i-2}\right)c_{i}'\,\oplus\,\mathfrak{C}_{1}\left(\Phi_{i-1}\right)\mathfrak{C}_{2}\left(\Phi_{i-2}\right)d_{i}'\\&\oplus&\mathfrak{C}_{2}\left(\Phi_{i-1}\right)c_{i}'\\&=&\mathfrak{C}_{1}\left(\Phi_{i}\right)\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\,\oplus\,\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\,\oplus\,\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\mathfrak{C}_{1}\left(\Phi_{i}\right)\,\oplus\,\mathfrak{C}_{1}\left(\Phi_{i-1}\right)\mathfrak{C}_{2}\left(\Phi_{i-2}\right)\\&\oplus&\left(\mathfrak{C}_{1}\left(\Phi_{i}\right)\,\oplus\,\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\,\oplus\,\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\,\oplus\,\mathfrak{C}_{1}\left(\Phi_{i-1}\right)\mathfrak{C}_{2}\left(\Phi_{i-2}\right)\right)c_{i}'\\&\oplus&\left(\mathfrak{C}_{1}\left(\Phi_{i}\right)\,\oplus\,\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\,\oplus\,\mathfrak{C}_{1}\left(\Phi_{i-1}\right)\mathfrak{C}_{2}\left(\Phi_{i-2}\right)\right)d_{i}'\\&=&\mathfrak{C}_{1}\left(\Phi_{i}\right)\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\,\oplus\,\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\,\oplus\,\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\mathfrak{C}_{1}\left(\Phi_{i}\right)\,\oplus\,\mathfrak{C}_{1}\left(\Phi_{i-1}\right)\mathfrak{C}_{2}\left(\Phi_{i-2}\right)\\&\oplus&\left(\mathfrak{C}_{1}\left(\Phi_{i}\right)\,\oplus\,\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\,\oplus\,\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\,\oplus\,\mathfrak{C}_{1}\left(\Phi_{i-1}\right)\mathfrak{C}_{2}\left(\Phi_{i-2}\right)\right)\left(c_{i}'\,\oplus\,d_{i}'\right)\,\oplus\,\mathfrak{C}_{4}\left(\Phi_{i-2}\right)d_{i}'\end{array}

（＊５）より最後の項は \mathfrak{C}_{4}\left(\Phi_{i-2}\right)d_{i}'=\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\mathfrak{C}_{2}\left(\Phi_{i-2}\right)c_{i-1}'=\mathfrak{C}_{6}\left(\Phi_{i-2}\right)c_{i-1}'=0 （∵ [tex:n\left(\Omega\right)

（＊10）
\begin{array}{lcl}c_{i+1}'\,\oplus\,d_{i+1}'&=&\mathfrak{C}_{1}\left(\Phi_{i}\right)\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\,\oplus\,\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\,\oplus\,\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\mathfrak{C}_{1}\left(\Phi_{i}\right)\,\oplus\,\mathfrak{C}_{1}\left(\Phi_{i-1}\right)\mathfrak{C}_{2}\left(\Phi_{i-2}\right)\\&\oplus&\left(\mathfrak{C}_{1}\left(\Phi_{i}\right)\,\oplus\,\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\,\oplus\,\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\,\oplus\,\mathfrak{C}_{1}\left(\Phi_{i-1}\right)\mathfrak{C}_{2}\left(\Phi_{i-2}\right)\right)\left(c_{i}'\,\oplus\,d_{i}'\right)\end{array}

式（＊10）は c_{i}'\,\oplus\,d_{i}' の漸化式になっているので、 b_{i}' を次のように定義するとうまくいきそうだ。

（＊11）
b_{i}'=c_{i}'\,\oplus\,d_{i}'

（＊11）を使えば、（★１）の第１式（ x_{i} の式）および（＊10）はそれぞれ（＊12）（＊13）のように変形できる。

（★１）再掲
x_{i}=\mathfrak{C}_{1}\left(\Phi_{i}\right)\,\oplus\,c_{i}\,\oplus\,d_{i}

（＊12）
\begin{array}{lcl}x_{i}&=&\mathfrak{C}_{1}\left(\Phi_{i}\right)\,\oplus\,c_{i}'\,\oplus\,\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\,\oplus\,d_{i}'\,\oplus\,\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\\&=&\mathfrak{C}_{1}\left(\Phi_{i}\right)\,\oplus\,\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\,\oplus\,\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\,\oplus\,b_{i}'\end{array}

（＊13）
\begin{array}{lcl}b_{i+1}'&=&\mathfrak{C}_{1}\left(\Phi_{i}\right)\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\,\oplus\,\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\,\oplus\,\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\mathfrak{C}_{1}\left(\Phi_{i}\right)\,\oplus\,\mathfrak{C}_{1}\left(\Phi_{i-1}\right)\mathfrak{C}_{2}\left(\Phi_{i-2}\right)\\&\oplus&\left(\mathfrak{C}_{1}\left(\Phi_{i}\right)\,\oplus\,\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\,\oplus\,\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\,\oplus\,\mathfrak{C}_{1}\left(\Phi_{i-1}\right)\mathfrak{C}_{2}\left(\Phi_{i-2}\right)\right)b_{i}'\end{array}

初期値などの条件も含めて（＊12）（＊13）を正確に書くと、次のようになる。

（＊14）
\begin{array}{lclcl}x_{1}&=&\mathfrak{C}_{1}\left(\Phi_{1}\right)\\x_{2}&=&\mathfrak{C}_{1}\left(\Phi_{2}\right)\,\oplus\,\mathfrak{C}_{2}\left(\Phi_{1}\right)\\x_{i}&=&\mathfrak{C}_{1}\left(\Phi_{i}\right)\,\oplus\,\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\,\oplus\,\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\,\oplus\,b_{i}'&\,&\left(\,\mathrm{as}\,i\ge 3\,\right)\\b_{1}'&=&0\\b_{2}'&=&0\\b_{3}'&=&\mathfrak{C}_{1}\left(\Phi_{2}\right)\mathfrak{C}_{2}\left(\Phi_{1}\right)\\b_{i+1}'&=&\mathfrak{C}_{1}\left(\Phi_{i}\right)\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\,\oplus\,\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\,\oplus\,\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\mathfrak{C}_{1}\left(\Phi_{i}\right)\,\oplus\,\mathfrak{C}_{1}\left(\Phi_{i-1}\right)\mathfrak{C}_{2}\left(\Phi_{i-2}\right)\\&\oplus&\left(\mathfrak{C}_{1}\left(\Phi_{i}\right)\,\oplus\,\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\,\oplus\,\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\,\oplus\,\mathfrak{C}_{1}\left(\Phi_{i-1}\right)\mathfrak{C}_{2}\left(\Phi_{i-2}\right)\right)b_{i}'&\,&\left(\,\mathrm{as}\,i\ge 3\,\right)\end{array}

これでようやく、解けそうな形の漸化式に変形できた。

ところで、（＊14）には \mathfrak{C}_{1}\left(\Phi_{i}\right) ， \mathfrak{C}_{2}\left(\Phi_{i-1}\right) ， \mathfrak{C}_{4}\left(\Phi_{i-2}\right) の対称式で表される部分が多く含まれている。
対称式は \mathfrak{C}_{r} を使えば簡略化できるので、そのために集合 \Psi_{i} を次のように定義する。

（＊15）
\begin{array}{lclcl}\Psi_{i}&=&\emptyset&\,&\left(\,\mathrm{as}\,i\le 0\,\right)\\\Psi_{1}&=&\left\{\,\mathfrak{C}_{1}\left(\Phi_{1}\right)\,\right\}\\\Psi_{2}&=&\left\{\,\mathfrak{C}_{1}\left(\Phi_{2}\right)\,,\,\mathfrak{C}_{2}\left(\Phi_{1}\right)\,\right\}\\\Psi_{i}&=&\left\{\,\mathfrak{C}_{1}\left(\Phi_{i}\right)\,,\,\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\,,\,\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\,\right\}&\,&\left(\,\mathrm{as}\,i\ge 3\,\right)\end{array}

これを使うと、（＊14）の漸化式部分は次のように書き換えられる。

（＊16）
\begin{array}{lcl}x_{i}&=&\mathfrak{C}_{1}\left(\Psi_{i}\right)\,\oplus\,b_{i}'\\b_{i+1}'&=&\mathfrak{C}_{2}\left(\Psi_{i}\right)\,\oplus\,\mathfrak{C}_{1}\left(\Phi_{i-1}\right)\mathfrak{C}_{2}\left(\Phi_{i-2}\right)\,\oplus\,\left(\mathfrak{C}_{1}\left(\Psi_{i}\right)\,\oplus\,\mathfrak{C}_{1}\left(\Phi_{i-1}\right)\mathfrak{C}_{2}\left(\Phi_{i-2}\right)\right)b_{i}'\end{array}

（＊16）の第２式（ b_{i+1}' の式）は簡単に解くことができて、 b_{i}' の一般式は次のように表される。

（＊17）
b_{i}'=\bigoplus_{k=1}^{i-1}\left(\,\!\left(\mathfrak{C}_{2}\left(\Psi_{k}\right)\,\oplus\,\mathfrak{C}_{1}\left(\Phi_{k-1}\right)\mathfrak{C}_{2}\left(\Phi_{k-2}\right)\right)\bigcap_{l=k+1}^{i-1}\left(\mathfrak{C}_{1}\left(\Psi_{l}\right)\,\oplus\,\mathfrak{C}_{1}\left(\Phi_{l-1}\right)\mathfrak{C}_{2}\left(\Phi_{l-2}\right)\right)\,\!\right)

よって求めたかった x_{i} の一般式は次式で表される。

（＊18）
\begin{eqnarray}x_{i}&=&\mathfrak{C}_{1}\left(\Psi_{i}\right)\,\oplus\,\bigoplus_{k=1}^{i-1}\left(\,\!\left(\mathfrak{C}_{2}\left(\Psi_{k}\right)\,\oplus\,\mathfrak{C}_{1}\left(\Phi_{k-1}\right)\mathfrak{C}_{2}\left(\Phi_{k-2}\right)\right)\bigcap_{l=k+1}^{i-1}\left(\mathfrak{C}_{1}\left(\Psi_{l}\right)\,\oplus\,\mathfrak{C}_{1}\left(\Phi_{l-1}\right)\mathfrak{C}_{2}\left(\Phi_{l-2}\right)\right)\,\!\right)\\&=&\mathfrak{C}_{1}\left(\Phi_{i}\right)\,\oplus\,\mathfrak{C}_{2}\left(\Phi_{i-1}\right)\,\oplus\,\mathfrak{C}_{4}\left(\Phi_{i-2}\right)\\&&\,\oplus\,\bigoplus_{k=1}^{i-1}\left(\,\!\left({\mathfrak{C}_{1}\left(\Phi_{k}\right)\mathfrak{C}_{2}\left(\Phi_{k-1}\right)\,\oplus\,\mathfrak{C}_{2}\left(\Phi_{k-1}\right)\mathfrak{C}_{4}\left(\Phi_{k-2}\right)\\\,\oplus\,\mathfrak{C}_{4}\left(\Phi_{k-2}\right)\mathfrak{C}_{1}\left(\Phi_{k}\right)\,\oplus\,\mathfrak{C}_{1}\left(\Phi_{k-1}\right)\mathfrak{C}_{2}\left(\Phi_{k-2}\right)}\right)\bigcap_{l=k+1}^{i-1}\left({\mathfrak{C}_{1}\left(\Phi_{l}\right)\,\oplus\,\mathfrak{C}_{2}\left(\Phi_{l-1}\right)\,\oplus\,\mathfrak{C}_{4}\left(\Phi_{l-2}\right)\\\,\oplus\,\mathfrak{C}_{1}\left(\Phi_{l-1}\right)\mathfrak{C}_{2}\left(\Phi_{l-2}\right)}\right)\,\!\right)\end{eqnarray}

\mathfrak{C}_{r} を使わずに書くなら、次のようになる。

（＊19）
\begin{eqnarray}x_{i}&=&\left(p_{i}\,\oplus\,q_{i}\,\oplus\,r_{i}\,\oplus\,s_{i}\,\oplus\,t_{i}\right)\\&\oplus&\left({p_{i-1}q_{i-1}\,\oplus\,p_{i-1}r_{i-1}\,\oplus\,p_{i-1}s_{i-1}\,\oplus\,p_{i-1}t_{i-1}\,\oplus\,q_{i-1}r_{i-1}\\\,\oplus\,q_{i-1}s_{i-1}\,\oplus\,q_{i-1}t_{i-1}\,\oplus\,r_{i-1}s_{i-1}\,\oplus\,r_{i-1}t_{i-1}\,\oplus\,s_{i-1}t_{i-1}}\right)\\&\oplus&\left({p_{i-2}q_{i-2}r_{i-2}s_{i-2}\,\oplus\,p_{i-2}q_{i-2}r_{i-2}t_{i-2}\,\oplus\,p_{i-2}q_{i-2}s_{i-2}t_{i-2}\\\,\oplus\,p_{i-2}r_{i-2}s_{i-2}t_{i-2}\,\oplus\,q_{i-2}r_{i-2}s_{i-2}t_{i-2}}\right)\\&\oplus&\bigoplus_{k=1}^{i-1}\left({\,\!\left({\left(p_{k}\,\oplus\,q_{k}\,\oplus\,r_{k}\,\oplus\,s_{k}\,\oplus\,t_{k}\right)\left({p_{k-1}q_{k-1}\,\oplus\,p_{k-1}r_{k-1}\,\oplus\,p_{k-1}s_{k-1}\,\oplus\,p_{k-1}t_{k-1}\\\,\oplus\,q_{k-1}r_{k-1}\,\oplus\,q_{k-1}s_{k-1}\,\oplus\,q_{k-1}t_{k-1}\\\,\oplus\,r_{k-1}s_{k-1}\,\oplus\,r_{k-1}t_{k-1}\,\oplus\,s_{k-1}t_{k-1}}\right)\\\,\oplus\,\left({p_{k-1}q_{k-1}\,\oplus\,p_{k-1}r_{k-1}\,\oplus\,p_{k-1}s_{k-1}\,\oplus\,p_{k-1}t_{k-1}\\\,\oplus\,q_{k-1}r_{k-1}\,\oplus\,q_{k-1}s_{k-1}\,\oplus\,q_{k-1}t_{k-1}\\\,\oplus\,r_{k-1}s_{k-1}\,\oplus\,r_{k-1}t_{k-1}\,\oplus\,s_{k-1}t_{k-1}}\right)\left({p_{k-2}q_{k-2}r_{k-2}s_{k-2}\,\oplus\,p_{k-2}q_{k-2}r_{k-2}t_{k-2}\\\,\oplus\,p_{k-2}q_{k-2}s_{k-2}t_{k-2}\,\oplus\,p_{k-2}r_{k-2}s_{k-2}t_{k-2}\\\,\oplus\,q_{k-2}r_{k-2}s_{k-2}t_{k-2}}\right)\\\,\oplus\,\left({p_{k-2}q_{k-2}r_{k-2}s_{k-2}\,\oplus\,p_{k-2}q_{k-2}r_{k-2}t_{k-2}\\\,\oplus\,p_{k-2}q_{k-2}s_{k-2}t_{k-2}\,\oplus\,p_{k-2}r_{k-2}s_{k-2}t_{k-2}\\\,\oplus\,q_{k-2}r_{k-2}s_{k-2}t_{k-2}}\right)\left(p_{k}\,\oplus\,q_{k}\,\oplus\,r_{k}\,\oplus\,s_{k}\,\oplus\,t_{k}\right)\\\,\oplus\,\left({p_{k-1}\,\oplus\,q_{k-1}\,\oplus\,r_{k-1}\\\,\oplus\,s_{k-1}\,\oplus\,t_{k-1}}\right)\left({p_{k-2}q_{k-2}\,\oplus\,p_{k-2}r_{k-2}\,\oplus\,p_{k-2}s_{k-2}\,\oplus\,p_{k-2}t_{k-2}\\\,\oplus\,q_{k-2}r_{k-2}\,\oplus\,q_{k-2}s_{k-2}\,\oplus\,q_{k-2}t_{k-2}\\\,\oplus\,r_{k-2}s_{k-2}\,\oplus\,r_{k-2}t_{k-2}\,\oplus\,s_{k-2}t_{k-2}}\right)}\right)\\\;\;\bigcap_{l=k+1}^{i-1}\left({\left(p_{l}\,\oplus\,q_{l}\,\oplus\,r_{l}\,\oplus\,s_{l}\,\oplus\,t_{l}\right)\\\,\oplus\,\left({p_{l-1}q_{l-1}\,\oplus\,p_{l-1}r_{l-1}\,\oplus\,p_{l-1}s_{l-1}\,\oplus\,p_{l-1}t_{l-1}\\\,\oplus\,q_{l-1}r_{l-1}\,\oplus\,q_{l-1}s_{l-1}\,\oplus\,q_{l-1}t_{l-1}\\\,\oplus\,r_{l-1}s_{l-1}\,\oplus\,r_{l-1}t_{l-1}\,\oplus\,s_{l-1}t_{l-1}}\right)\\\,\oplus\,\left({p_{l-2}q_{l-2}r_{l-2}s_{l-2}\,\oplus\,p_{l-2}q_{l-2}r_{l-2}t_{l-2}\\\,\oplus\,p_{l-2}q_{l-2}s_{l-2}t_{l-2}\,\oplus\,p_{l-2}r_{l-2}s_{l-2}t_{l-2}\\\,\oplus\,q_{l-2}r_{l-2}s_{l-2}t_{l-2}}\right)\\\,\oplus\,\left({p_{l-1}\,\oplus\,q_{l-1}\,\oplus\,r_{l-1}\\\,\oplus\,s_{l-1}\,\oplus\,t_{l-1}}\right)\left({p_{l-2}q_{l-2}\,\oplus\,p_{l-2}r_{l-2}\,\oplus\,p_{l-2}s_{l-2}\,\oplus\,p_{l-2}t_{l-2}\\\,\oplus\,q_{l-2}r_{l-2}\,\oplus\,q_{l-2}s_{l-2}\,\oplus\,q_{l-2}t_{l-2}\,\oplus\,r_{l-2}s_{l-2}\\\,\oplus\,r_{l-2}t_{l-2}\,\oplus\,s_{l-2}t_{l-2}}\right)}\right)\,\!}\right)\end{eqnarray}

……やっぱり無駄に長い。
（＊19）の各括弧の中は対称式になっているので、それらを別の記号で表したのが（＊18）というわけだ。
ああそうそう、長いから括弧の中で改行してるだけで、行列とかベクトルとかじゃないからね！　紛らわしいけど一応そのへん注意。


さてとにかく、これで漸化式（★１）がようやく解けた。
……が！
これを使って次に進もうとしたら、重大なミスに気づいた。
なんと これ、 x_{i} じゃなくて p_{i} について解くべき問題だったんだorz
このブール代数の漸化式を誰か解いてください！ - Plus Le Toolで　この問題解いてください＞＜　なんて言ってしまったのですごく申し訳ない気持ち。
解けたのに答えを書かないわけにはいかないから一応記事にはしてみたけど……
解けて嬉しいか、というとちょっと複雑なキブン。

ちなみに、 p_{i} について解く方もほぼ同じ手順で解けたので、近いうちに書く予定。書いた（→[id:plusletool:20130714:p1]）。