前回の続き
前回挙げた16種類の論理演算と、
{True, False}の2つの値からなる集合とがなす16種類の代数構造のうち、
どれがモノイドや群なのかを調べた。
以下S = {True, False}とする
1. 全てはマグマである
演算の結果がやはりSに属するので16種類全てがマグマである。
これは自明。
2. 8種類が半群である。
結合法則を満たすもののみが半群となる。
Sと以下の演算の組が半群。
TAUTOLOGY, CONTRADICTION, AND, OR, XOR, XNOR, PROPOSITION P, PROPOSITION Q
3. 4種類がモノイドである。
2.の結果のうち、単位元を持つもののみがモノイドである。
Sと以下の演算の組が半群。
AND, OR, XOR, XNOR
4. 2種類が群である。
3.の結果のうち、任意の元について逆元が存在する場合、群である。
Sと以下の演算の組が半群。
XOR, XNOR
5. 2種類がアーベル群である。
4.の結果のうち、可換なものがアーベル群。
Sと以下の演算の組が半群。
XOR, XNOR
さて、これが分かって何が役に立つかというと、実用的な例でいえば
(S, XOR)がアーベル群であることは、XOR交換アルゴリズムに利用されている。
調べるのに使ったscalaソース↓
