n変数のBoole関数は, 定数関数も含めて22n(2の2のn乗乗)あるが, n変数の対称関数は2n+1しかない.
3変数対称関数の図を眺めると, 各立方体で, 同じ色の対称同士の点は, 000の(赤の)点から, 等距離にあることが分かる. 距離の計測法は, 000から立方体の稜にそって目的地まで進む最短距離, いわゆるマンハッタン距離である.
改めて眺めると, 赤までの距離は0, 緑までは1, 橙までは2, 青までは3である.
つまり対称の要素は4個あり, その要素を採用するか, しないかの問題であった. n変数は000...0の点から111...1まで行く辺の種類はn個なので, 要素の数は両端を含めてn+1, 従って2n+1になるのであった.
0 件のコメント:
コメントを投稿