최근 수정 시각 : 2022-06-25 09:03:45

드모르간 법칙

수학기초론
Foundations of Mathematics
{{{#!wiki style="margin:0 -10px -5px"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin:-6px -1px -11px"
{{{#!wiki style="letter-spacing: -1px"
다루는 대상과 주요 토픽
수리논리학 논리 · 논증{ 귀납논증 · 연역논증 · 귀추 · 유추} · 공리 및 공준 · 증명{ 자동정리증명 · 귀류법 · 수학적 귀납법 · 반증 · PWW} · 논리함수 · 논리 연산 · 잘 정의됨 · 조건문( 조각적 정의) · 명제 논리( 명제 · 아이버슨 괄호 · · · 대우) · 양상논리 · 술어 논리( 존재성과 유일성) · 형식문법 · 유형 이론 · 모형 이론
집합론 집합( 원소 · 공집합 · 집합족 · 곱집합 · 멱집합) · 관계( 동치관계 · 순서 관계) · 순서쌍( 튜플) · 서수( 하세 다이어그램 · 큰 가산서수) · 수 체계 · ZFC( 선택공리) · 기수( 초한기수) · 절대적 무한
범주론 함자 · 수반 · 자연 변환 · 모나드 · 쌍대성
계산가능성 이론 계산 · 오토마타 · 튜링 기계 · 바쁜 비버 · 정지 문제 · 재귀함수
정리
드모르간 법칙 · 대각선 논법 · 러셀의 역설 · 거짓말쟁이의 역설 · 뢰벤하임-스콜렘 정리 · 슈뢰더-베른슈타인 정리 · 집합-부분합 정리 · 퍼스의 항진명제 · 굿스타인 정리 · 불완전성 정리 · 힐베르트의 호텔 · 연속체 가설 · 퍼지 논리
기타
예비사항( 약어 및 기호) · 추상화 · 벤 다이어그램 · 수학철학 · 논리학 둘러보기 · 이산수학·수리논리학 둘러보기 · 철학 관련 정보 · 논리학 관련 정보 · 수학 관련 정보 }}}}}}}}}}}}


1. 개요2. 벤 다이어그램으로 본 법칙3. 전자회로에서의 응용4. 여담

1. 개요

논리학 수학의 법칙 중 하나이다. 논리 연산에서 논리합은 논리곱과 부정기호로, 논리곱은 논리합과 부정기호로 표현할 수 있음을 가리키는 법칙이다.

일반적인 표현으로
[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)]
[math(\neg (p \land q) = \neg p \lor \neg q)]
집합론
[math({\complement}(A\cup B) = {\complement}A \cap {\complement}B)]
[math({\complement}(A\cap B) = {\complement}A \cup {\complement}B)]
전자회로
[math(\overline{(A + B)} = \overline{A} \cdot \overline{B})]
[math(\overline{(A \cdot B)} = \overline{A} + \overline{B})]

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

2. 벤 다이어그램으로 본 법칙

제일 먼저 이를 접하게 되는 것은 집합에서 벤 다이어그램으로 이 둘이 같다는 것을 보여주는 형태로 나타난다.
파일:나무_드모르간_법칙1_수정.svg 파일:나무_드모르간_법칙2_수정_3차.svg

3. 전자회로에서의 응용

전자회로 등에서는 약간 응용해서 [math(A + B = \overline{ \overline{A} \cdot \overline{B}})] 나 [math(A \cdot B = \overline{\overline{A} + \overline{B}})] 형식으로 표현하는 경우도 있지만, 위의 같은 식이란 것을 쉽게 유도할 수 있다.

파일:나무_드모르간_법칙_회로1_수정.svg 파일:나무_드모르간_법칙_회로2_수정.svg

전자회로는 일반적으로 회로식을 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
NAND 게이트로만 구성된 전가산기

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

4. 여담

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


[1] A 또는 B를 뜻한다. [2] A와 B 둘 다 아님을 뜻한다.