[include(틀:수학기초론)]
[목차]
== 개요 ==
[[논리학]]과 [[수학]]의 법칙 중 하나이다. [[논리 연산]]에서 논리합은 논리곱과 부정기호로, 논리곱은 논리합과 부정기호로 표현할 수 있음을 가리키는 법칙이다.

일반적인 표현으로
> [math(\textsf{not }(A\textsf{ or }B) = (\textsf{not }A)\textsf{ and }(\textsf{not }B) \\ \textsf{not }(A\textsf{ and }B) = (\textsf{not }A)\textsf{ or }(\textsf{not }B))]
논리곱(합)의 부정은 각각 부정의 논리합(곱)과 같다는 법칙. 이는 논리학과 동일하게 집합론, 전자회로등에서도 똑같이 사용된다.

아래는 동일한 내용을 각각의 학문에서 주로 사용하는 수식으로 표현한 것이다. 표기법이 조금씩 다르지만, 모두 동일한 내용이다.

> 논리학 : [math( \neg (\text{부정}),  \lor (\text{논리합}), \land  (\text{논리곱}) )]
> [math(\neg (p \lor q) = \neg p \land \neg q)] [br]  [math(\neg (p \land q) = \neg p \lor \neg q)]

> 집합론
> [math({\complement}(A\cup B) = {\complement}A \cap {\complement}B)] [br] [math({\complement}(A\cap B) = {\complement}A \cup {\complement}B)]

> 전자회로
> [math(\overline{(A + B)} = \overline{A} \cdot \overline{B})] [br] [math(\overline{(A \cdot B)} = \overline{A} + \overline{B})]

수학자 [[오거스터스 드 모르간]]에 의해 증명되었으며, 이 수학자의 이름이 붙어 있다.

== 벤 다이어그램으로 본 법칙 ==
제일 먼저 이를 접하게 되는 것은 집합에서 [[벤 다이어그램]]으로 이 둘이 같다는 것을 보여주는 형태로 나타난다.
{{{#!wiki style="text-align: center"
[[파일:나무_드모르간_법칙1_수정.svg]][[파일:나무_드모르간_법칙2_수정_3차.svg]]
}}}
== [[논리회로|전자회로]]에서의 응용 ==
전자회로 등에서는 약간 응용해서 [math(A + B = \overline{ \overline{A} \cdot \overline{B}})] 나 [math(A \cdot B = \overline{\overline{A} + \overline{B}})] 형식으로 표현하는 경우도 있지만, 위의 같은 식이란 것을 쉽게 유도할 수 있다.

{{{#!wiki style="text-align: center"
[[파일:나무_드모르간_법칙_회로1_수정.svg|width=300]] [[파일:나무_드모르간_법칙_회로2_수정.svg|width=300]]
}}}
전자회로는 일반적으로 회로식을 sum of products 라는 형식으로 구성한다. 입력을 여러 개의 AND 게이트로 묶은 뒤, 이 출력을 모두 OR 로 연결하여 구성이 가능하다. 그런데, 드 모르간 법칙을 이용하면 이들을 모두 NAND 게이트만으로 구성이 가능하게 된다. 예를 들어 [math(X =  A \cdot B + \overline{A} \cdot C + B \cdot C \cdot D )] 라고 할 때, 드 모르간 법칙을 이용해서 변환하면, [math(X =  \overline{\overline{ A \cdot B} \cdot \overline{\overline{A} \cdot C} \cdot \overline{B \cdot C \cdot D}} )] 로 바꿔 쓸 수 있는데, 이는 NAND 게이트만으로 회로 구성이 가능하다는 것을 의미한다. 예컨대 아래처럼 [[전가산기]]를 NAND만으로 구성할 수 있다.

|| [[파일:나무_전가산기_NAND.svg|width=320]] ||
|| NAND 게이트로만 구성된 전가산기 ||

전자회로에서 NAND 게이트는 구조가 가장 간단하고 입력이 많아져도 큰 지장이 없기에 가장 널리 쓰인다. 이것만으로 만든 메모리가 바로 우리가 일반적으로 부르는 낸드 [[플래시 메모리]](NAND flash memory)이다. NAND게이트 만으로 만든 녀석이라 낸드플래시라고 부른다. 비슷한 원리로 NOR만으로 만든 녀석도 있는데, 이쪽은 노어(NOR) 플래시라고 부른다. 다만 속도가 빠르다는 장점이 있지만, 낸드에 비해 [[가성비]]가 안 나와서 거의 도태되고, 특수 분야에서 한정된 용도로만 사용된다.

== 여담 ==
학창 시절 [[영어]] 수업에서 한 번쯤 배웠을 either A or B[* A 또는 B를 뜻한다.]와 neither A nor B[* A와 B 둘 다 아님을 뜻한다.]라는 두 표현의 관계가 다름아닌 드모르간 법칙이다.

[[분류:논리학]][[분류:집합론]]