logo

부정논리합, NOR 게이트 📂양자정보이론

부정논리합, NOR 게이트

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

정의1

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

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

0↓0=1,0↓1=0,1↓0=0,1↓1=0 0\downarrow 0 = 1,\quad 0\downarrow 1 = 0,\quad 1\downarrow 0 = 0,\quad 1\downarrow 1 = 0

설명

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

↓=¬∘∨ \begin{equation} \downarrow = \lnot \circ \lor \end{equation}

a↓b=¬(a∨b) a \downarrow b = \lnot (a \lor b)

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

부울 함수기호진리표
NOR\text{NOR}
aabba↓ba \downarrow b
000011
001100
110000
111100

정리

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

증명

정리

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

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

  • NOT\text{NOT} 게이트

    ¬=↓∘cl⁡¬a=a↓a \lnot = \downarrow \circ \operatorname{cl} \\ \lnot a = a \downarrow a

    가 성립한다.

    ↓∘cl⁡(0)=0↓0=1=¬0↓∘cl⁡(1)=1↓1=0=¬1 \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*}

  • OR\text{OR} 게이트

    ∨=↓∘cl⁡∘↓a∨b=(a↓b)↓(a↓b) \lor = \downarrow \circ \operatorname{cl} \circ \downarrow \\ a \lor b = (a \downarrow b) \downarrow (a \downarrow b)

    가 성립한다.

    (0↓0)↓(0↓0)=(1↓1)=0=0∨0(0↓1)↓(0↓1)=(0↓0)=1=0∨1(1↓0)↓(1↓0)=(0↓0)=1=1∨0(1↓1)↓(1↓1)=(1↓1)=1=1∨1 \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*}

■

같이보기

  1. 김영훈·허재성, 양자 정보 이론 (2020), p86-87 ↩︎