わさっきhb

大学(教育研究)とか ,親馬鹿とか,和歌山とか,とか,とか.

情報工学で学ぶ範囲で,非可換な演算は?

いきなりですが問題です.

  • 可換だけれど結合的でない演算の例を挙げなさい.
  • 結合的だけれど非可換な演算の例を挙げなさい.

演算記号をθとしたとき,可換であるとは,xθy=xθyが常に成立することをいい,この等式を満たさないx,yがあるときは非可換といいます.結合的であるとは,(xθy)θz=xθ(yθz)が常に成立することをいいます.
さっそくですが解答例です.情報工学で学習する範囲で,「可換だけれど結合的でない演算」には,NANDとNORがあります.定義から可換なのは分かりますが,結合的でないのは,つい先日,真理値表生成プログラムを作ったばかりです*1
「結合的だけれど非可換な演算」で,最も有名なのは行列の積でしょうね.四元数の積も,挙げておきたいところです.
あともう一つ,地味だけど欠かせないのは,文字列の連接(concatenation)です*2.「和歌山」という文字列と「大学」をくっつけたら,「和歌山大学」になります.「大学和歌山」と同じと言われても,困ります.
きちんと文字列のデータ構造を定義し,そこで連接の操作を定めれば,結合的であることも確認できます.簡単な確かめの例には,x=和歌山,y=大学,z=前駅 を使いましょう.
この問題は,授業で小テストとして与え,答えを書いてもらいました.排他的論理和(XOR)のほか,論理和(AND)と論理積(OR),それとたし算は,可換かつ結合的であることを,アナウンスしています.
答案を見ると,ひき算やわり算がよく書かれていましたが,あいにく可換でも結合的でもありません.ベクトルの外積*3もです.

*1:http://d.hatena.ne.jp/takehikom/20150430/1430341903.証明のページにもリンクしています.

*2:数学的には,文字列の連接は,モノイドとなります.単位元は空文字列です.

*3:内積を挙げる学生は,いませんでしたが,ベクトルの内積は閉じた演算ではない(内積で得られる値はベクトルでない)ので,結合性を確かめるための両辺,すなわち(x・y)・zやx・(y・z)が,意味を持たなくなります.