202420601

「CPU の命令セットやプログラミング言語の基本ビット演算に NOT, AND, OR, XOR を選ぶ根拠は何か」という問いに対する一つの答え。

• 非自明な単項演算子は NOT のみ。
• 入出力の 1 つに NOT 演算を追加することで任意の二項演算を行える、自明な演算子を除いた二項演算子セットの最小要素数は 3.
• そのなかで、交換則と結合則を満たす演算のみで構成されるセットを選ぶことができて、それは AND, OR, X(N)OR. (追記: 交換則がなくても同じ)