부정논리곱

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
- 2.1. 진리표
- 2.2. 논리식
3. 성질
- 3.1. 기능적 완전성
- 3.2. 교환 법칙 및 결합 법칙
4. 표기법
5. 역사
6. 응용
참조

1. 개요

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

2. 정의

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

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

'''A''' NAND '''B''' = NOT ('''A''' AND '''B''')

2. 1. 진리표

명제 P	명제 Q	P NAND Q
참	참	거짓
참	거짓	참
거짓	참	참
거짓	거짓	참

2. 2. 논리식

P

와

Q

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

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

드 모르간의 법칙에 의해, 이것은 또한 $P$ 와 $Q$ 의 부정의 논리합(OR)과 동치이다.

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

3. 성질

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

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

3. 1. 기능적 완전성

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

다음은 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''' )

진리표를 사용하면

\neg A

가

A \uparrow A

와 진리 함수적으로 동등함을 보일 수 있다.^[13] 또한,

A \uparrow B

가

\neg (A \land B)

와 동등하고,

A \lor B

가

\neg(\neg A \land \neg B)

와 동등하므로, 부정논리곱은 선언적 정규 형식 정리에 의해 진리 함수적으로 완전한 연결 연산자 집합

\{\land, \lor, \neg\}

를 정의하기에 충분하다.^[13]

다음은 부정논리곱

\uparrow

을 사용하여 표현한 명제 논리의 일반적인 연산자들이다.

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

초기의 집적 회로(표준 논리 IC)는 부품 가격이 비쌌기 때문에, 회로 구성이 가장 간단한 NAND를 이용하여 다양한 논리 회로를 설계하였다.

3. 2. 교환 법칙 및 결합 법칙

NAND는 교환 법칙이 성립하지만 결합 법칙은 성립하지 않는다. 즉,

P \uparrow Q \leftrightarrow Q \uparrow P

이지만,

(P \uparrow Q) \uparrow R \not\leftrightarrow P \uparrow (Q \uparrow R)

이다.^[9]

4. 표기법

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

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

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

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

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

5. 역사

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

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

6. 응용

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

참조

_[1] 서적 Logic with trees: an introduction to symbolic logic Routledge 1997
_[2] 간행물 A Boolian Algebra with One Constant Harvard University Press 1933
_[3] 간행물 The Simplest Mathematics Harvard University Press 1933
_[4] 웹사이트 Sheffer stroke before Sheffer: Edward Stamm https://richardzach.[...] 2023-02-18
_[5] 서적 Grundzügen der theoretischen Logik Verlag von Julius Springer 1928
_[6] 서적 Principles of Mathematical Logic Chelsea Publishing Company 1950
_[7] 서적 Elementy logiki matematycznej Państwowe Wydawnictwo Naukowe 1958
_[8] 서적 Mathematical Logic Harvard University Press 1981
_[9] 서적 Mathematical Foundations of Computer Science https://books.google[...] I. K. International Pvt Ltd 2006
_[10] 웹사이트 Propositional Calculus https://mathworld.wo[...] 2024-03-22
_[11] 간행물 Propositional Logic https://plato.stanfo[...] Metaphysics Research Lab, Stanford University 2023
_[12] 서적 The Two-Valued Iterative Systems of Mathematical Logic https://dokumen.pub/[...] Princeton University Press 1941
_[13] 서적 Logic with trees: an introduction to symbolic logic Routledge 1997

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com