부울 함수
| 양자정보이론 | ||||||||||||||||
[ 펼치기 · 접기 ]
| ||||||||||||||||
정의1
다음과 같은 함수를 부울 함수Boolean function라 한다. $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} $$
벡터값 부울 함수vector-valued Boolean function라 한다.
설명
영국의 수학자 조지 부울George Boole의 이름을 딴 것이다. 조지 부울은 부울 대수의 창시자로 논리학을 대수적으로 다루어 기호논리학에 큰 영향을 끼쳤다.
부울 함수는 부울 연산Boolean expression 혹은 논리 연산logical operation/connective이라고도 불린다.
컴퓨터 이론에서는 $1$과 $0$이 각각 전기 신호가 "있음"과 "없음"을 의미하므로, 전기 신호가 들어가고 나온다는 의미에서 게이트gate라 부른다. 따라서 여러 게이트들의 합성을 회로circuit라고 한다.
가역 함수
란다우어의 정리에 따라 정보가 사라질 때마다 에너지도 같이 쓰이는데, 따라서 컴퓨팅 효율의 측면에서 일대일 대응인 부울 함수에 관심을 갖는다. 일대일 대응인 부울 함수를 가역reversible, 그렇지 않은 부울 함수를 비가역non reversible이라 한다. 가역이 되려면 자명하게도 $m=n$이어야 한다. 가역 함수로는 다음의 것들이 있다.
종류
- $\text{AND}$ 게이트논리곱
- $\text{OR}$ 게이트논리합
- $\text{NOT}$ 게이트논리 부정
- $\text{XOR}$ 게이트배타적 논리합
- $\text{NAND}$ 게이트부정논리곱
- $\text{NOR}$ 게이트부정논리합
${}$ - 복제 함수 $\text{cl}$
- 사영 $p_{i}$
- 주입 $\imath_{i}$, $\jmath_{i}$
김영훈·허재성, 양자 정보 이론 (2020), p85 ↩︎