２要素集合上でassociativeな演算

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

例えば以下のような演算を定義することができます。いわゆるAND演算です。

a	b	a * b
0	0	0
0	1	0
1	0	0
1	1	1

　ここで「考えうる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は生成時に与えられたビット列に対応した入出力機構を持つ関数のようにふるまいます。

view plainprint?

1. class Functor {  
2.     int mask;  
3. public:  
4.     Functor (int mask) {  
5.         this->mask = mask;  
6.     }  
7.   
8.     int operator()(int a, int b) {  
9.         return mask >> (a << 1 | b) & 1;  
10.     }  
11. };  
12.   
13. int main() {  
14.     for (int k = 0; k < 1<<4; k++) {  
15.         Functor f(k);  
16.   
17.         bool ck = true;  
18.         for (int x = 0; x <= 1; x++) {  
19.             for (int y = 0; y <= 1; y++) {  
20.                 for (int z = 0; z <= 1; z++) {  
21.                     if (f(x, f(y, z)) != f(f(x, y), z)) {  
22.                         ck = false;  
23.                     }  
24.                 }  
25.             }  
26.         }  
27.   
28.         if (ck)  
29.             cout << bitset<4>(k) << endl;  
30.     }  
31.   
32.     return 0;  
33. }  

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ではありません。

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