ブール関数
양자정보이론 | ||||||||||||||||
[ 펼치기 · 접기 ]
|
定義1
以下の関数をブール関数と呼ぶ。$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$でなければならない。可逆関数としては、以下がある。
種類
- $\text{AND}$ゲート論理積
- $\text{OR}$ゲート論理和
- $\text{NOT}$ゲート論理否定
- $\text{XOR}$ゲート排他的論理和
- $\text{NAND}$ゲートナンド
- $\text{NOR}$ゲートノール
${}$ - クローニング関数 $\text{cl}$
- 射影 $p_{i}$
- 注入$\imath_{i}$, $\jmath_{i}$
キム・ヨンフン・ホ・ジェソン, 量子情報理論 (2020), p85 ↩︎