ブール関数

定義¹

以下の関数をブール関数と呼ぶ。$n \in \mathbb{N}$に対して,

$$ f : \left\{ 0, 1 \right\}^{n} \to \left\{ 0, 1 \right\} $$

ここで、$1 =$は真(True)、$0 =$は偽(False)とする。

一般化

$n, m \in \mathbb{N} (m \gt 2)$に対して,

$$ f : \left\{ 0, 1 \right\}^{n} \to \left\{ 0, 1 \right\}^{m} $$

これをベクトル値ブール関数と呼ぶ。

説明

イギリスの数学者ジョージ・ブールの名前にちなむ。ジョージ・ブールはブール代数の創設者で、論理学を代数的に扱い、記号論理学に大きな影響を与えた。

ブール関数は、ブール演算または論理演算/接続詞とも呼ばれる。

コンピュータ理論では、$1$と$0$はそれぞれ電気信号が「存在する」「存在しない」を意味するため、電気信号が入って出るという意味でゲートと言われる。したがって、複数のゲートの合成を回路という。

可逆関数

ランダウアーの原理によると、情報が失われるたびにエネルギーも使用されるため、コンピューティング効率の側面から一対一対応のブール関数に関心を持つ。一対一対応のブール関数を可逆、そうでないブール関数を不可逆と呼ぶ。可逆であるためには、自明のように$m=n$でなければならない。可逆関数としては、以下がある。

• $\operatorname{CNOT}$ゲート
• トフォリゲート^{$\text{CCNOT}$ゲート}
• フレドキングート^{$\text{CSWAP}$ゲート}

種類

• $\text{AND}$ゲート^論理積
• $\text{OR}$ゲート^論理和
• $\text{NOT}$ゲート^論理否定
• $\text{XOR}$ゲート^{排他的論理和}
• $\text{NAND}$ゲート^ナンド
• $\text{NOR}$ゲート^ノール
  ${}$
• クローニング関数 $\text{cl}$
• 射影 $p_{i}$
• 注入$\imath_{i}$, $\jmath_{i}$