$\{0, 1\}^2 \to \{0,1\}$ の16個の演算について

論理演算の代数

• 表の元データを生成するコード

• 双対の関係にあるペアは同じ代数構造を持つ。（0 と 1 を入れ替える全単射が同型写像になる）

  • ここでは、真理値表の0, 1をすべて入れ替えた関係にある2つの論理演算を双対と呼んでいる。
  • 例えば XOR と XNOR は双対の関係なので、どちらも代数としては同じもの。どちらもアーベル群（可換な群）になっている

• XOR や XNOR の逆元は自分自身（0の逆元は0、1の逆元は1）

• 双対性

  • const 0 と const 1 は互いに双対
  • x への射影は自己双対に。y への射影も自己双対。
  • XOR と XNOR は互いに双対
  • AND と OR は互いに双対
  • NAND と NOR は互いに双対

• x への射影、yへの射影は結合法則を満たしている

  • （単位元に気をつければ）セグ木に乗る（論理演算に限らず）

• NOT をつけると結合法則を満たさなくなりがち。

半環を成す論理演算

半環を成すのは以下の4つ（(足し算, 掛け算) の順番に記載）

• (AND, OR)
• (OR, AND)
• (XOR, AND)
• (XNOR, OR)