logo

ブール関数

ブール関数

양자정보이론
[ 펼치기 · 접기 ]

定義1

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

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

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

一般化

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

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

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

説明

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

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

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

可逆関数

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

種類


  1. キム・ヨンフン・ホ・ジェソン, 量子情報理論 (2020), p85 ↩︎