| 수학기초론 Foundations of Mathematics | |||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | 다루는 대상과 주요 토픽 | ||
| 수리논리학 | 논리 · 논증{귀납논증 · 연역논증 · 귀추 · 유추} · 공리 및 공준 · 증명{증명보조기 · 자동정리증명 · 귀류법 · 수학적 귀납법 · 반증 · 더블 카운팅 · PWW} · 논리함수 · 논리 연산 · 잘 정의됨 · 조건문(조각적 정의) · 명제 논리(명제 · 아이버슨 괄호 · 역 · 이 · 대우) · 양상논리 · 술어 논리(존재성과 유일성) · 형식문법 · 유형 이론 · 모형 이론 | ||
| 집합론 | 집합(원소 · 공집합 · 집합족 · 곱집합 · 멱집합) · 관계(동치관계 · 순서 관계) · 순서쌍(튜플) · 서수(하세 다이어그램 · 큰 가산서수) · 수 체계 · ZFC(선택공리) · 기수(초한기수) · 절대적 무한 · 모임 | ||
| 범주론 | 범주 · 함자 · 수반 · 자연 변환 · 모나드 · 쌍대성 | ||
| 계산가능성 이론 | 계산 · 오토마타 · 튜링 기계 · 바쁜 비버 · 정지 문제 · 재귀함수 | ||
| 정리 | |||
| 드모르간 법칙 · 대각선 논법 · 러셀의 역설 · 거짓말쟁이의 역설 · 뢰벤하임-스콜렘 정리 · 슈뢰더-베른슈타인 정리 · 집합-부분합 정리 · 퍼스의 항진명제 · 굿스타인 정리 · 완전성 정리 · 불완전성 정리(괴델 부호화) · 힐베르트의 호텔 · 연속체 가설 · 퍼지 논리 | |||
| 기타 | |||
| 예비사항(약어 및 기호) · 추상화 · 벤 다이어그램 · 수학철학 | |||
| 틀:논리학 · 틀:이산수학 · 틀:이론 컴퓨터 과학 · 철학 관련 정보 · 논리학 관련 정보 · 수학 관련 정보 | }}}}}}}}} | ||
1. 개요
논리학과 수학의 법칙 중 하나이다. 논리 연산에서 논리합은 논리곱과 부정기호로, 논리곱은 논리합과 부정기호로 표현할 수 있음을 가리키는 법칙이다.일반적인 표현으로
[math(\begin{aligned}\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)\end{aligned})]
논리곱(합)의 부정은 각각 부정의 논리합(곱)과 같다는 법칙. 이는 논리학과 동일하게 집합론, 전자회로등에서도 똑같이 사용된다.아래는 동일한 내용을 각각의 학문에서 주로 사용하는 수식으로 표현한 것이다. 표기법이 조금씩 다르지만, 모두 동일한 내용이다.
논리학: [math(\neg)](부정), [math(\lor)](논리합), [math(\land)](논리곱)
[math(\begin{aligned} \neg (p \lor q) &= \neg p \land \neg q \\ \neg (p \land q) &= \neg p \lor \neg q\end{aligned})]
[math(\begin{aligned} \neg (p \lor q) &= \neg p \land \neg q \\ \neg (p \land q) &= \neg p \lor \neg q\end{aligned})]
집합론
[math(\begin{aligned} \complement(A\cup B) &= \complement A \cap \complement B \\ \complement(A\cap B) &= \complement A \cup \complement B\end{aligned})]
[math(\begin{aligned} \complement(A\cup B) &= \complement A \cap \complement B \\ \complement(A\cap B) &= \complement A \cup \complement B\end{aligned})]
전자회로
[math(\begin{aligned} \overline{(A + B)} &= \overline A \cdot \overline B \\ \overline{(A \cdot B)} &= \overline A + \overline B\end{aligned})]
[math(\begin{aligned} \overline{(A + B)} &= \overline A \cdot \overline B \\ \overline{(A \cdot B)} &= \overline A + \overline B\end{aligned})]
수학자 오거스터스 드 모르간에 의해 증명되었으며, 이 수학자의 이름이 붙어 있다.
2. 벤 다이어그램으로 본 법칙
제일 먼저 이를 접하게 되는 것은 집합에서 벤 다이어그램으로 이 둘이 같다는 것을 보여주는 형태로 나타난다.| |
3. 전자회로에서의 응용
전자회로 등에서는 약간 응용해서 [math(A + B = \overline{ \overline{A} \cdot \overline{B}})] 나 [math(A \cdot B = \overline{\overline{A} + \overline{B}})] 형식으로 표현하는 경우도 있지만, 위의 같은 식이란 것을 쉽게 유도할 수 있다.| |
| NAND 게이트로만 구성된 전가산기 |
전자회로에서 NAND 게이트는 구조가 가장 간단하고 입력이 많아져도 큰 지장이 없기에 가장 널리 쓰인다. 이것만으로 만든 메모리가 바로 우리가 일반적으로 부르는 낸드 플래시 메모리(NAND flash memory)이다. NAND게이트 만으로 만든 녀석이라 낸드플래시라고 부른다. 비슷한 원리로 NOR만으로 만든 녀석도 있는데, 이쪽은 노어(NOR) 플래시라고 부른다. 다만 속도가 빠르다는 장점이 있지만, 낸드에 비해 가성비가 안 나와서 거의 도태되고, 특수 분야에서 한정된 용도로만 사용된다.