Search on the blog

2012年2月23日木曜日

2要素集合上でassociativeな演算

集合X = {0, 1}上で閉じた任意の二項演算*を考えます。関数の入力パターンは2*2=4通り、その4通りの入力それぞれについて2通りの出力を考えることができるので全部で24 = 16通りの演算を考えることができます。

例えば以下のような演算を定義することができます。いわゆるAND演算です。
aba * b
000
010
100
111

 ここで「考えうる16パターンすべての演算についてassociativeな演算はいくつあるのか?」という興味が湧いてきました。associativeな演算とは、すべてのa, b, c ∈ Xについて(a * b) * c = a * (b * c)をみたす演算です。それぞれの関数につき2*2*2=8通りの入力パターンすべてを手で検証するのは大変なので、コンピュータの力を借りることにしました。

 今回は集合の要素が0, 1なので二進数を使うと上手くコーディングができそうです。0*0の結果を0ビット目に、0*1の結果を1ビット目に・・・のように格納すると4ビットのビット列で演算を一意に表すことができます。例えば、上記のANDなら"1000"です。あとは、このビット列をどう関数と結び付けるかです。
 C++では関数オブジェクト(functor)を利用することでクロージャのようなものが実現できるので、それを利用します。以下のソースでは、関数オブジェクトfは生成時に与えられたビット列に対応した入出力機構を持つ関数のようにふるまいます。
class Functor {
    int mask;
public:
    Functor (int mask) {
        this->mask = mask;
    }

    int operator()(int a, int b) {
        return mask >> (a << 1 | b) & 1;
    }
};

int main() {
    for (int k = 0; k < 1<<4; k++) {
        Functor f(k);

        bool ck = true;
        for (int x = 0; x <= 1; x++) {
            for (int y = 0; y <= 1; y++) {
                for (int z = 0; z <= 1; z++) {
                    if (f(x, f(y, z)) != f(f(x, y), z)) {
                        ck = false;
                    }
                }
            }
        }

        if (ck)
            cout << bitset<4>(k) << endl;
    }

    return 0;
}

 以下の8つの演算がassociativeであることが分かりました。それぞれの関数に適当に名前を付けました。名前をつけると確かにassociativeだなあと感覚的に納得できます。この中でFSTとSNDは仲間外れの演算です。他の6つの演算と違ってcommutativeではありません。

0000ZERO
0110XOR
1000AND
1001EQ
1010SND
1100FST
1110OR
1111ONE

0 件のコメント:

コメントを投稿