半環

 ABC009 D問題を解くにあたって、解説に出てきた半環。何も分からずに使うのが気持ち悪いので、ざっと触りだけ調べて備忘録がわりにする。とりあえずネットの情報を鵜呑みにして書き連ねるので間違いだらけだと思います。優しく指摘してください。

 

 とりあえず半環の前に環の話をします。 

そもそも環って何?ドーナツ?

集合と演算からなる代数系には、どのような性質があるだろうか、という議論 *1

 なるほど。

 要するに、自然数の足し算・掛け算とブール代数のAND・ORって同じようなものだから、まとめて考えちゃっていいよね!みたいな。

 そんな感じで同じような性質でひとまとめにしたものに、群・環・体なんていう仰々しい名前がついてると。

環の公理

  • 加法は可換
  • 加法、乗法は結合的
  • 乗法は加法の上に分配的
  • 加法単位元が存在する
  • 各元は加法逆元を持つ *2

 …なるほど(?)。

一つ一つ見ていく

 以下、便宜上、加法は+、乗法は*、アルファベットは任意の元として扱います。

加法は可換

 可換って何さ!と思ってWikipedia先生に聞いたら交換法則に飛ばされる。なるほど、a+b=b+aってことね。

加法、乗法は結合的

 もしかして結合法則のこと?と思ったらその通りらしい。a+(b+c)=(a+b)+c、(a*b)*c=a*(b*c)。

乗法は加法の上に分配的

 多分だけど、分配法則のこと。で、a*(b+c)=a*b+a*c、(a+b)*c=a*c+b*c。

加法単位元が存在する

 加法単位元って何かというと、a+0=0+a=aとなるような0のこと。数字で書くと当たり前だけど、意味が違う代数系じゃ当然こういう定義も必要だよね。

各元は加法逆元を持つ

 a+b=b+a=0となるようなbの存在。こういうbを-aって表記する。

やっと半環の話

 今まで見てきたような公理を全て満たす代数系が環。じゃあ半環は、っていうと、「各元が加法逆元を持つ」っていう条件がなくなって、a*0=0*a=0が条件に入ってきた形。0*a=a*0=0は環なら持ってる性質なんだけど、半環になると保証されなくなるっぽい?

 ちなみにこの半環の全ての定義は解説スライドp.92-99にでています。

結局なんの役にたつの

 結論だけ言うと、加法をXOR、乗法をANDとして行列の和や積を取っても、半環の公理を全て満たすので、同じく半環である行列と同じように扱ってもいいってことです。

 ここだけの話、なんとなく半環を理解して解説スライドを見直したらすんなりと理解できてしまったので続きを書く気力がなくなりました。RIP。

TODO

なっとくする群・環・体 (なっとくシリーズ)

なっとくする群・環・体 (なっとくシリーズ)

 

  夏休みになったら読む。