補題：新しい関数“Ｃr（Ω）”を定義する

初期seedから日時を求める無謀な挑戦 - Plus Le Toolのための補題。
使う記号の定義は[id:plusletool:20130427:p2]参照。

ここでは関数 $\mathfrak{C}_{r}\left(\Omega\right)$ を定義する。
なぜ定義するのか、何に使うのか、どんな意味なのか、……ｅｔｃは次回の記事で分かるはずなので、今回は細かいことは置いておいてとりあえず定義だけしておく。

【追記】
やっぱりここでちゃんと書いておく。
$\mathfrak{C}_{r}\left(\Omega\right)$ は、ブール代数における $r$ 次の基本対称式を表している。
普通の代数においては任意の対称式は基本対称式の和と差と積の組み合わせで一意に表せるが、ブール代数においても同様の性質があって、任意の対称式は基本対称式の排他的論理和と論理積の組み合わせで一意に表せる。
また対称式でなくても、対象構造を多く含む式なら部分的に基本対称式で表すことでより簡単に記述できることが多い。
そこで基本対称式を $\mathfrak{C}_{r}\left(\Omega\right)$ で表し、これを使って式を簡略化しようというのがこの関数の目的である。
ちなみに基本対称式は慣例的には $\mathfrak{C}$ でなく $\sigma$ （文献によっては $s$ ）を使って $\sigma_{r}\left(\omega_{1}\,,\,\omega_{2}\,,\,\dots\,,\,\omega_{n}\right)$ のように表すらしい。
この追記の時点ではじめて知った……（手遅れ）

ああそうそう、今回の記事にはちゃんと証明できなかった定理が多数あるので気に入らない人は読まない方が精神衛生上いいと思うの。

単刀直入に行ってみよう。
関数 $\mathfrak{C}_{r}\left(\Omega\right)$ を次のように定義する。

（＊Ａ） $\mathfrak{C}_{r}\left(\Omega\right)$ の定義
$n$ 個のbool型変数を要素に持つある集合 $\Omega$ について、 $\Omega$ の $n$ 個の要素から $r$ 個を選び論理積を求めることを考える。
この時、どの変数を選んだかによって ${}_{n}C_{r}$ 通りの論理積の項ができるが、それら ${}_{n}C_{r}$ 項すべての排他的論理和を $\mathfrak{C}_{r}\left(\Omega\right)$ と定義する。
※ $r<0$ または $r>n$ の場合は、 $\mathfrak{C}_{r}\left(\Omega\right)=0$ とする。
※ $r=0$ の場合は、 $\mathfrak{C}_{r}\left(\Omega\right)=1$ とする。

関数名の「 $\mathfrak{C}$ 」は“Ｃ”の飾り文字で、これは組み合わせ（Combination） ${}_{n}C_{r}$ の“Ｃ”から来ている。
“Ｃ”はこれ以外でも比較的よく使われる文字なので、重複を避けるために飾り文字にした（ちなみにＴｅＸ記法で「\mathfrak{C}」と書く）。

$\Omega=\left\{\omega_{1},\dots,\omega_{n}\right\}$ の場合 $\mathfrak{C}_{r}\left(\Omega\right)=\mathfrak{C}_{r}\left(\left\{\omega_{1},\dots,\omega_{n}\right\}\right)$ だが、これを $\mathfrak{C}_{r}\left(\omega_{1},\dots,\omega_{n}\right)$ のように略記してもよいことにする。
また、文脈などにより $\Omega$ が明らかである場合、 $\mathfrak{C}_{r}\left(\Omega\right)$ を単に $\mathfrak{C}_{r}$ と略記してもよいことにする。

言葉による定義はあいまいなところがあるので式でも表しておこうか。

（＊１）
$\begin{eqnarray}\mathfrak{C}_{r}\left(\Omega\right)&=&\bigoplus_{\omega_{1}\in\Omega}\left(\bigoplus_{\omega_{2}\in\Omega-\left\{\omega_{1}\right\}}\left(\bigoplus_{\omega_{3}\in\Omega-\left\{\omega_{1},\omega_{2}\right\}}\left(\,\dots\,\left(\bigoplus_{\omega_{r}\in\Omega-\left\{\omega_{1},\dots,\omega_{r-1}\right\}}\left(\prod_{j=1}^{r}\omega_{j}\right)\right)\right)\right)\right)\\&=&\bigoplus_{\omega_{1}\in\Omega}\left(\bigoplus_{\omega_{2}\in\Omega-\left\{\omega_{1}\right\}}\left(\bigoplus_{\omega_{3}\in\Omega-\left\{\omega_{1},\omega_{2}\right\}}\left(\,\dots\,\left(\bigoplus_{\omega_{r}\in\Omega-\left\{\omega_{1},\dots,\omega_{r-1}\right\}}\left(\omega_{1}\omega_{2}\dots\omega_{r}\right)\right)\right)\right)\right)\end{eqnarray}$

また、 $\Omega=\left\{\omega_{1},\dots,\omega_{n}\right\}$ の場合は次のようにも書ける。

（＊２）
$\begin{eqnarray}\mathfrak{C}_{r}\left(\Omega\right)&=&\mathfrak{C}_{r}\left(\omega_{1},\dots,\omega_{n}\right)\\&=&\bigoplus_{i_{1}=1}^{n-r+1}\left(\bigoplus_{i_{2}=i_{1}+1}^{n-r+2}\left(\bigoplus_{i_{3}=i_{2}+1}^{n-r+3}\left(\,\dots\,\left(\bigoplus_{i_{r}=i_{r-1}+1}^{n}\left(\prod_{j=1}^{r}\omega_{i_{j}}\right)\right)\right)\right)\right)\\&=&\bigoplus_{i_{1}=1}^{n-r+1}\left(\bigoplus_{i_{2}=i_{1}+1}^{n-r+2}\left(\bigoplus_{i_{3}=i_{2}+1}^{n-r+3}\left(\,\dots\,\left(\bigoplus_{i_{r}=i_{r-1}+1}^{n}\left(\omega_{i_{1}}\omega_{i_{2}}\dots\omega_{i_{r}}\right)\right)\right)\right)\right)\end{eqnarray}$

たぶん定義や式を見てもイメージがつかめないだろうから、具体例を見てみよう。めんどうだから箇条書きで。
初めての人はたぶん３変数か４変数の場合あたりを最初に見ると分かりやすいと思う。

（＊３）０変数（ $\Omega=\emptyset$ ）の場合
$\mathfrak{C}_{r}\left(\Omega\right)=\left\{\begin{array}{lcl}0&\,&\left(r\ne 0\right)\\1&\,&\left(r=0\right)\end{array}\right.$

（＊４）１変数（ $\Omega=\left\{\omega_{1}\right\}$ ）の場合
[tex:\mathfrak{C}_{r}\left(\Omega\right)=\left\{\begin{array}{lcl}0&\,&\left(r<0\,,\,1

（＊５）２変数（ $\Omega=\left\{\omega_{1}\,,\,\omega_{2}\right\}$ ）の場合
[tex:\mathfrak{C}_{r}\left(\Omega\right)=\left\{\begin{array}{lcl}0&\,&\left(r<0\,,\,2

（＊６）３変数（ $\Omega=\left\{\omega_{1}\,,\,\omega_{2}\,,\,\omega_{3}\right\}$ ）の場合
[tex:\mathfrak{C}_{r}\left(\Omega\right)=\left\{\begin{array}{lcl}0&\,&\left(r<0\,,\,3

（＊７）４変数（ $\Omega=\left\{\omega_{1}\,,\,\omega_{2}\,,\,\omega_{3}\,,\,\omega_{4}\right\}$ ）の場合
[tex:\mathfrak{C}_{r}\left(\Omega\right)=\left\{\begin{array}{lcl}0&\,&\left(r<0\,,\,4

（＊８）５変数（ $\Omega=\left\{\omega_{1}\,,\,\omega_{2}\,,\,\omega_{3}\,,\,\omega_{4}\,,\,\omega_{5}\right\}$ ）の場合
[tex:\mathfrak{C}_{r}\left(\Omega\right)=\left\{\begin{array}{lcl}0&\,&\left(r<0\,,\,5

（＊９）６変数（ $\Omega=\left\{\omega_{1}\,,\,\omega_{2}\,,\,\omega_{3}\,,\,\omega_{4}\,,\,\omega_{5}\,,\,\omega_{6}\right\}$ ）の場合
[tex:\mathfrak{C}_{r}\left(\Omega\right)=\left\{\begin{array}{lcl}0&\,&\left(r<0\,,\,6

（＊10）７変数（ $\Omega=\left\{\omega_{1}\,,\,\omega_{2}\,,\,\omega_{3}\,,\,\omega_{4}\,,\,\omega_{5}\,,\,\omega_{6}\,,\,\omega_{7}\right\}$ ）の場合
[tex:\mathfrak{C}_{r}\left(\Omega\right)=\left\{\begin{array}{lcl}0&\,&\left(r<0\,,\,7

えーっと……めんどくさくなってきたからこのくらいでいいかな？　いいよね。
まぁ関数 $\mathfrak{C}_{r}$ がどんな感じの関数かなんとなく分かればいいと思う。

さてここからは $\mathfrak{C}_{r}$ に関する性質（定理？）を見てみる。
まず、 $\mathfrak{C}_{r}$ の項数に関する性質から。

（＊Ｂ） $\mathfrak{C}_{r}$ の項数
$n\overset{\mathrm{def}}{=}n\left(\Omega\right)$ とすると、 $\mathfrak{C}_{r}\left(\Omega\right)$ の項数は ${}_{n}C_{r}$ である。

（※一応補足しておくと、 $n\left(\Omega\right)$ ってのは「 $\Omega$ の要素数」って意味ね。念のため。）
【簡易証明】
「定義より明らか。Ｑ．Ｅ．Ｄ．」でいいと思うの。

次に、 $\mathfrak{C}_{r}$ どうしの論理積に関する性質。

（＊Ｃ） $\mathfrak{C}_{r}$ の論理積
$0\le r_{1}\in\mathbb{Z}$ ， $0\le r_{2}\in\mathbb{Z}$ のとき、次の式が成り立つ。

$\mathfrak{C}_{r_{1}}\left(\Omega\right)\mathfrak{C}_{r_{2}}\left(\Omega\right)=\mathfrak{C}_{r_{1}\cup r_{2}}\left(\Omega\right)$

【簡易証明】
~~残念ながら証明はまだできていない。~~
~~証明はできなかったけど、 $0\le n\left(\Omega\right)\le 7$ のときに（＊Ｃ）が成り立つことは実際に計算して確認したので間違いない。~~
【追記１】さきさんが証明してくれました。ありがとうございます！
【追記２】自分でも証明できた。（→[id:plusletool:20130612:p2]）

（＊Ｃ）に関して、念のため補足しておく。
$r_{1}\,\cup\,r_{2}$ は $r_{1}$ と $r_{2}$ の論理和を表すが、これは $r_{1}$ と $r_{2}$ を二進数表記で表して各bitごとに論理和を計算することを意味する。

余談だが、符号（正負）を最上位bitで表す固定長整数変数を使うなら、（＊Ｃ）は任意の整数 $r_{1}\,,\,r_{2}$ で成り立つ。

続いて、 $\mathfrak{C}_{r}$ の分解について。

（＊Ｄ） $\mathfrak{C}_{r}$ の分解
$\Omega=\Omega_{1}\,\cup\,\Omega_{2}\;,\;\Omega_{1}\,\cap\,\Omega_{2}=\emptyset$ のとき、次の式が成り立つ。

$\mathfrak{C}_{r}\left(\Omega\right)=\bigoplus_{k=0}^{r}\mathfrak{C}_{k}\left(\Omega_{1}\right)\mathfrak{C}_{r-k}\left(\Omega_{2}\right)$

【簡易証明】
残念ながら証明はまだできていない。
証明の代わりにはならないけど、簡単な考え方を書いておく。

組み合わせ ${}_{n}C_{r}$ の公式の１つに次のようなものがある。

${}_{n}C_{r}={}_{n-1}C_{r-1}\,+\,{}_{n-1}C_{r}$

これを繰り返し適用していくと、次の式が得られる。

${}_{n}C_{r}=\sum_{k=0}^{r}{}_{n_{1}}C_{k}\,\cdot\,{}_{n_{2}}C_{r-k}$
ただし、 $0\le n_{1}\,,\,0\le n_{2}\,,\,n_{1}+n_{2}=n$

この式が成り立つ理由を考えれば、同じ考え方で（＊Ｄ）も説明できるはず。
その場合、 $n\,,\,n_{1}\,,\,n_{2}$ をそれぞれ $\Omega\,,\,\Omega_{1}\,,\,\Omega_{2}$ の要素数に対応していると考えればいい。

$\mathfrak{C}_{r}\left(\Omega\right)$ は対称構造を持つ多項式を簡潔に表記するために導入した関数だが、 $\Omega$ の各要素（ブール変数）に具体的な値が代入されれば、当然 $\mathfrak{C}_{r}\left(\Omega\right)$ の値も計算できるはずだ。
このとき $\mathfrak{C}_{r}\left(\Omega\right)$ がどのような値になるかについて、次のような性質がある。

（＊Ｅ） $\mathfrak{C}_{r}$ の値
$\Omega$ の $n$ 個の要素のうち、その値の内訳が $m$ 個の１と $n-m$ 個の０であるとき、次の式が成り立つ。

$\begin{eqnarray}\mathfrak{C}_{r}\left(\Omega\right)&=&{}_{m}C_{r}\,\bmod{2}\\&=&\left\{\begin{array}{lcl}0&\,&\left(\mathrm{as}\,m\ne m\,\cup\,r\right)\\1&\,&\left(\mathrm{as}\,m=m\,\cup\,r\right)\end{array}\right.\end{eqnarray}$

【簡易照明】
☆無☆理☆　……だけどとりあえず、１行目はパスカルの三角形眺めてたら気づいたってことだけ書いとく。
２行目はただの ${}_{n}C_{r}$ の性質。Ｗｉｋｉｐｅｄｉａに書いてあったけど証明は見つからなかった。

$\mathfrak{C}_{r}\left(\Omega\right)$ は $\Omega$ の各要素について対称なので、「１」の個数だけで $\mathfrak{C}_{r}\left(\Omega\right)$ の値が求められるということだ。

----------------

今のところ気づいた性質はこれだけ。
何か新しい性質を見つけたら追記するかも。
$\mathfrak{C}_{r}\left(\Omega\right)$ の性質は ${}_{n}C_{r}$ の性質と近いところが多いので、 ${}_{n}C_{r}$ の公式でも眺めてれば何か思いつきそうな気がしないでもない。