なんじゃくにっき

二値論理と群論

Scala, math

前回の続き
　
前回挙げた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交換アルゴリズムに利用されている。

http://ja.wikipedia.org/wiki/XOR%E4%BA%A4%E6%8F%9B%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0


調べるのに使ったscalaソース↓

ツイートする

Permalink | コメント(0) | トラックバック(0) | 23:48