부정논리곱

1. 개요

부정논리곱은 두 논리값에 대한 논리 연산으로, 적어도 하나의 명제가 거짓일 경우 참 값을 생성한다. 일반적으로 A NAND B는 NOT(A AND B)로 정의되며, NAND는 교환 법칙이 성립하지만 결합 법칙은 성립하지 않는다. NAND는 그 자체로 기능적으로 완전한 연산자 집합이며, 다른 모든 논리 연산을 표현할 수 있다. 1913년 헨리 모리스 쉐퍼에 의해 처음 소개되었으며, 초기 집적 회로 설계에 널리 사용되었다.

2. 정의

부정논리곱(NAND)은 두 논리값에 대한 논리 연산으로, 적어도 하나의 명제가 거짓일 때 참 값을 갖는다.

일반적으로 부정논리곱은 다음과 같이 정의된다.

A NAND B = NOT (A AND B)

2.1. 진리표

2.2. 논리식

$P$와 $Q$의 부정논리곱(Sheffer stroke)은 이들의 논리곱(AND)의 부정과 같다.

👆

좌우로 밀어서 보기

📌 열 고정 해제

$P\; \backslash uparrow\; Q$	$\backslash Leftrightarrow$	$\backslash neg\; (P\; \backslash land\; Q)$
	$\backslash Leftrightarrow$	$\backslash neg$

👆

좌우로 밀어서 보기

📌 열 고정 해제

$P\; \backslash uparrow\; Q$	$\backslash Leftrightarrow$	$\backslash neg\; P$	$\backslash lor$	$\backslash neg\; Q$
	$\backslash Leftrightarrow$		$\backslash lor$

3. 성질

부정논리곱(NAND) 연산은 교환 법칙이 성립한다. 즉, 입력값의 순서를 바꾸어도 결과는 같다. 하지만, 결합 법칙은 성립하지 않는다. 즉, 연산 순서에 따라 결과가 달라질 수 있다.

* 교환 법칙: $P\; \backslash uparrow\; Q\; \backslash leftrightarrow\; Q\; \backslash uparrow\; P$
* 결합 법칙: $(P\; \backslash uparrow\; Q)\; \backslash uparrow\; R\; \backslash not\backslash leftrightarrow\; P\; \backslash uparrow\; (Q\; \backslash uparrow\; R)$

3.1. 기능적 완전성

부정논리곱(NAND)은 그 자체로 기능적으로 완전한 연산자 집합이다. 즉, NAND 연산 하나만으로 다른 모든 논리 연산(AND, OR, NOT 등)을 표현할 수 있다. 이는 부정논리곱이 진리 보존, 거짓 보존, 선형성, 단조성, 자기 쌍대성의 다섯 가지 속성을 모두 갖지 않기 때문이다. 기능적으로 완전한 연산자 집합은 이 다섯 가지 속성 중 적어도 하나는 갖지 않아야 하며, 모두 부재하는 것은 기능적 완전성의 충분조건이다.

다음은 NAND 연산으로 다른 논리 연산을 구성하는 예시이다.

* NOT A = A NAND A
* A AND B = ( A NAND B ) NAND ( A NAND B )
* A OR B = ( A NAND A ) NAND ( B NAND B )

진리표를 사용하면 $\backslash neg\; A$가 $A\; \backslash uparrow\; A$와 진리 함수적으로 동등함을 보일 수 있다. 또한, $A\; \backslash uparrow\; B$가 $\backslash neg\; (A\; \backslash land\; B)$와 동등하고, $A\; \backslash lor\; B$가 $\backslash neg(\backslash neg\; A\; \backslash land\; \backslash neg\; B)$와 동등하므로, 부정논리곱은 선언적 정규 형식 정리에 의해 진리 함수적으로 완전한 연결 연산자 집합 $\backslash \{\backslash land,\; \backslash lor,\; \backslash neg\backslash \}$를 정의하기에 충분하다.

다음은 부정논리곱 $\backslash uparrow$을 사용하여 표현한 명제 논리의 일반적인 연산자들이다.

👆

좌우로 밀어서 보기

📌 열 고정 해제

연산	표현	벤 다이어그램 표현
$\backslash neg\; P$	$P\; \backslash uparrow\; P$	$\backslash Leftrightarrow$ $\backslash uparrow$
$P\; \backslash rightarrow\; Q$	$~P\; \backslash uparrow\; (Q\; \backslash uparrow\; Q)$ 또는 $~P\; \backslash uparrow\; (P\; \backslash uparrow\; Q)$	$\backslash Leftrightarrow$ $\backslash uparrow$ $\backslash Leftrightarrow$ $\backslash uparrow$
$P\; \backslash leftrightarrow\; Q$	$(P\; \backslash uparrow\; Q)\; \backslash uparrow\; ((P\; \backslash uparrow\; P)\; \backslash uparrow\; (Q\; \backslash uparrow\; Q))$	$\backslash Leftrightarrow$ $\backslash uparrow$
$P\; \backslash land\; Q$	$(P\; \backslash uparrow\; Q)\; \backslash uparrow\; (P\; \backslash uparrow\; Q)$	$\backslash Leftrightarrow$ $\backslash uparrow$
$P\; \backslash lor\; Q$	$(P\; \backslash uparrow\; P)\; \backslash uparrow\; (Q\; \backslash uparrow\; Q)$	$\backslash Leftrightarrow$ $\backslash uparrow$

3.2. 교환 법칙 및 결합 법칙

NAND는 교환 법칙이 성립하지만 결합 법칙은 성립하지 않는다. 즉, $P\; \backslash uparrow\; Q\; \backslash leftrightarrow\; Q\; \backslash uparrow\; P$이지만, $(P\; \backslash uparrow\; Q)\; \backslash uparrow\; R\; \backslash not\backslash leftrightarrow\; P\; \backslash uparrow\; (Q\; \backslash uparrow\; R)$이다.

4. 표기법

퍼스는 부정논리곱의 기능적 완전성을 처음으로 보여주었지만($\backslash overline\{\backslash curlywedge\}$로 표현) 결과를 발표하지는 않았다. 퍼스의 편집자가 부정논리합에 $\backslash overline\{\backslash curlywedge\}$을 추가했다. 1911년, 에드워드 브로니스와프 슈탐^폴란드어은 $\backslash sim$('슈탐 갈고리')으로 표현하여 부정논리곱의 완전성을 처음으로 출판했으며, 최초로 부정논리합의 완전성을 인쇄물로 보여주었다.

1913년, 쉐퍼는 $\backslash mid$를 사용하여 부정논리합을 설명하고 기능적 완전성을 보여주었다. 쉐퍼는 또한 부정논리합에 $\backslash wedge$를 사용했다. 1917년 니코드를 시작으로 화이트헤드, 러셀 등 많은 사람들이 쉐퍼가 $\backslash mid$를 사용하여 부정논리곱을 설명했다고 오해하여 이를 쉐퍼 스트로크라고 명명했다.

1928년, 힐베르트와 아커만은 연산자 $/$를 사용하여 부정논리곱을 설명했다.

1929년, 우카시에비치는 그의 폴란드 표기법에서 부정논리곱을 위해 $D$를 $Dpq$에 사용했다.

부정논리곱의 또 다른 표기법은 $\backslash uparrow$이다. 이 표기법을 처음 도입한 사람이 누구인지는 불분명하지만, 이에 해당하는 부정논리합 $\backslash downarrow$는 1940년에 콰인에 의해 사용되었다.

5. 역사

찰스 샌더스 퍼스는 1880년에 "ampheck"(양쪽을 자른다는 의미)라는 용어를 사용하여 NAND 또는 NOR의 함수적 완전성을 발견했지만, 발표하지 않았다. 1911년, Edward Stamm^폴란드어은 NAND 및 NOR 연산자를 설명하고 다른 부울 연산을 이 연산자로 표현할 수 있음을 보여주었다.

1913년, 헨리 모리스 셰퍼는 논문에서 부정 논리곱을 사용하여 부울 대수의 공리화를 제시하고, 명제 논리의 일반적인 연산자(AND, OR, NOT)를 사용하는 에드워드 버밀리에 헌팅턴의 표준 공식과의 동등성을 증명했다. 셰퍼는 논문에서 부정 논리곱을 NOR의 기호로 해석했으며, 논리곱 부정은 각주에서만 언급했고 별도의 기호는 사용하지 않았다. 1917년, 장 니코는 논문에서 부정 논리곱을 NAND의 기호로 처음 사용했으며, 이후 이 표기법이 널리 사용되었다. 1927년, 러셀과 화이트헤드는 수학 원리 제2판에서 셰퍼 스트로크를 사용하여 초판의 "OR" 및 "NOT" 연산을 대체할 것을 제안했다.

6. 응용

초기에 집적 회로(표준 논리 IC)는 부품 가격이 비쌌기 때문에 회로 구성이 가장 간단한 NAND를 이용하여 다양한 논리 회로를 설계하였다. 더 자세한 내용은 NAND 게이트 문서를 참조하라.