📂양자정보이론

부정논리합, NOR 게이트

양자정보이론

[ 펼치기 · 접기 ] 양자계산 논리게이트 비트 · 부울함수(AND · OR · NOT · XOR · NAND · NOR · CNOT · CCNOT · CSWAP) · 범용 게이트 · 복제 함수 · 사영 · 주입 양자게이트 큐비트 · 양자 얽힘 · 양자 회로 · 양자 게이트(파울리 게이트 · 위상 게이트 · 아다마르 게이트 · 양자 CNOT · 교환 게이트 · 양자 CSWAP · 양자 CSWAP) · 솔베이-키타예프 정리 · 복제 불가 정리 정보이론 고전정보이론 정보량 · 엔트로피(결합 엔트로피 · 조건부 엔트로피 · 상대적 엔트로피 · 상호 정보 ) · 부호화 · 복호화 양자정보이론 TBD · TBD · TBD 관련 분야 선형대수 · 양자역학

정의¹

다음과 같은 부울함수를 $\text{NOR}$ 게이트^{NOR gate} 혹은 부정논리합이라 하고 다음과 같이 표기한다.

$$ \downarrow : \left\{ 0, 1 \right\}^{2} \to \left\{ 0, 1 \right\} $$

$$ 0\downarrow 0 = 1,\quad 0\downarrow 1 = 0,\quad 1\downarrow 0 = 0,\quad 1\downarrow 1 = 0 $$

설명

$\text{NOT}$ 게이트와 $\text{OR}$ 게이트의 합성이고, $\text{N(OT)}$과 $\text{OR}$을 따와서 $\text{NOR}$라고 명명하였다.

$$ \begin{equation} \downarrow = \lnot \circ \lor \end{equation} $$

$$ a \downarrow b = \lnot (a \lor b) $$

$\text{OR}$ 게이트와 반대로 작동하며, 모든 입력이 거짓일 때만 참을 출력한다. 또한 $\left\{ \downarrow \right\}$는 함수적으로 완전한데, $(1)$에 의해서 당연하다고 볼 수 있다.

부울 함수	기호	진리표
$\text{NOR}$		$a$ $b$ $a \downarrow b$ $0$ $0$ $1$ $0$ $1$ $0$ $1$ $0$ $0$ $1$ $1$ $0$

정리

(복제함수를 허용하면) $\left\{ \downarrow \right\}$는 함수적으로 완전하다. 다시말해 $\downarrow$는 범용 게이트이다.

증명

정리

$\text{NOT}$와 $\text{OR}$ 게이트의 집합 $\left\{ \lnot, \lor \right\}$은 함수적으로 완전하다.

위의 정리에 따라, 복제함수 $\text{cl}$과 $\downarrow$만으로 $\text{NOT}$ 게이트와 $\text{OR}$ 게이트를 만들 수 있음을 보이면 된다.

• $\text{NOT}$ 게이트

  $$ \lnot = \downarrow \circ \operatorname{cl} \\ \lnot a = a \downarrow a $$

  가 성립한다.

  $$ \begin{align*} \downarrow \circ \operatorname{cl}(0) = 0 \downarrow 0 = 1 = \lnot 0 \\ \downarrow \circ \operatorname{cl}(1) = 1 \downarrow 1 = 0 = \lnot 1 \\ \end{align*} $$

• $\text{OR}$ 게이트

  $$ \lor = \downarrow \circ \operatorname{cl} \circ \downarrow \\ a \lor b = (a \downarrow b) \downarrow (a \downarrow b) $$

  가 성립한다.

  $$ \begin{align*} (0 \downarrow 0) \downarrow (0 \downarrow 0) = (1 \downarrow 1) = 0 = 0 \lor 0 \\ (0 \downarrow 1) \downarrow (0 \downarrow 1) = (0 \downarrow 0) = 1 = 0 \lor 1 \\ (1 \downarrow 0) \downarrow (1 \downarrow 0) = (0 \downarrow 0) = 1 = 1 \lor 0 \\ (1 \downarrow 1) \downarrow (1 \downarrow 1) = (1 \downarrow 1) = 1 = 1 \lor 1 \\ \end{align*} $$

■

같이보기

• $\text{AND}$ 게이트^논리곱
• $\text{OR}$ 게이트^논리합
• $\text{NOT}$ 게이트^{논리 부정}
• $\text{XOR}$ 게이트^{배타적 논리합}
• $\text{NAND}$ 게이트^{부정논리곱}
• $\operatorname{CNOT}$ 게이트
• 토폴리 게이트^{$\text{CCNOT}$ 게이트}
• 프레드킨 게이트^{$\text{CSWAP}$ 게이트}