概要

0 と 1 しか値を取らない変数で論理演算を表現します。

x,y\in\{0,1\}

計算は整数として行い、結果が 0 か 1 に収まるように調整します。

量子ゲートの行列表現の解釈に応用することを想定しています。

AND, NOT

論理積と否定を定義します。

x\land y&:=xy \\
\overline x&:=1 - x

OR

$x \lor y$ において $x=1$ のとき 1 になると定義します。成立条件を掛けることで場合分けを表現します。

x \lor y
:=&\begin{cases}
    y & (x=0) \\
    1 & (x=1)
  \end{cases} \\
=&y\overline{x}+1x \\
=&\overline{x}y+x \\
=&(1-x)y+x \\
=&y-xy+x \\
=&x+y-xy

$x=y=1$ のとき $x+y=2$ から $xy=1$ を引くことで $1$ になります。

ド・モルガンの法則

ド・モルガンの法則により NOT と AND で定義する方法もあります。

\overline{x \lor y}=&\overline x \land \overline y \\
x\lor y=\overline{\overline{x \lor y}}
=&\overline{\overline x \land \overline y} \\
=&1-(1-x)(1-y) \\
=&1-(1-x-y+xy) \\
=&x+y-xy

得られる数式は同じです。

XOR

$x \veebar y$ において $x=1$ のとき $y$ を反転すると定義します。成立条件を掛けることで場合分けを表現します。

x \veebar y
:=&\begin{cases}
    y & (x=0) \\
    \overline{y} & (x=1)
  \end{cases} \\
=&y\overline{x}+\overline{y}x \\
=&\overline{xy}+x\overline{y} \\
=&(1-x)y+x(1-y) \\
=&y-xy+x-xy \\
=&x+y-2xy

$x=y=1$ のとき $x+y=2$ から $2xy=2$ を引くことで $0$ になります。

C 言語

参考までに、XOR を例に場合分けの考え方を C 言語で説明します。（XOR 演算子 ^ は使用しません）

単純に条件分岐で値を返します。

if (x == 0) return  y;
if (x == 1) return !y;

条件が成立するとき条件式が 1 になることを利用して条件分岐をなくします。

(x == 0) * y + (x == 1) * !y

x は 0 か 1 であるという前提で書き換えます。

!x * y + x * !y

これは数式の $\overline{x}y+x\overline{y}$ に対応します。

条件分岐をなくしたため、条件の成立に関わらず式全体が計算対象となることに注意してください。

※ 数式化した AND や OR でも同様で、短絡評価は考慮されません。

なお、C 言語の式で条件分岐するには三項演算子を使用します。

!x ? y : !y