드모르간 법칙
1. 개요
논리학과 수학의 법칙 중 하나이다. 논리 연산에서 논리합은 논리곱과 부정기호로, 논리곱은 논리합과 부정기호로 표현할 수 있음을 가리키는 법칙이다.
일반적인 표현으로
논리곱(합)의 부정은 각각 부정의 논리합(곱)과 같다는 법칙. 이는 논리학과 동일하게 집합론, 전자회로등에서도 똑같이 사용된다.$$\mathsf{not}(A \ \mathsf{ or } \ B) = (\mathsf{not}\ A)\ \mathsf{ and }\ (\mathsf{not}\ B)$$
$$\mathsf{not} (A \ \mathsf{ and }\ B) = (\mathsf{not}\ A)\ \mathsf{ or }\ (\mathsf{not} \ B)$$
아래는 동일한 내용을 각각의 학문에서 주로 사용하는 수식으로 표현한 것이다. 표기법이 조금씩 다르지만, 모두 동일한 내용이다.
논리학
$$\neg (p \lor q) = \neg p \land \neg q$$
$$\neg (p \land q) = \neg p \lor \neg q$$
집합론
$$(A\cup B)^c = A^c \cap B^c $$
$$(A\cap B)^c = A^c \cup B^c $$
수학자 오거스터스 드 모르간에 의해 증명되었으며, 이 수학자의 이름이 붙어 있다.전자회로
$$\overline{(A + B)} = \overline{A} \cdot \overline{B}$$
$$\overline{(A \cdot B)} = \overline{A} + \overline{B}$$
2. 벤 다이어그램으로 본 법칙
제일 먼저 이를 접하게 되는 것은 집합에서 벤 다이어그램'으로 이 둘이 같다는 것을 보여주는 형태로 나타난다.
[image]
3. 전자회로에서의 응용
전자회로 등에서는 약간 응용해서 $$A + B = \overline{ \overline{A} \cdot \overline{B}}$$ 나 $$A \cdot B = \overline{\overline{A} + \overline{B}}$$ 형식으로 표현하는 경우도 있지만, 위의 같은 식이란 것을 쉽게 유도할 수 있다.
[image]
전자회로는 일반적으로 회로식을 sum of products 라는 형식으로 구성한다. 입력을 여러 개의 AND 게이트로 묶은 뒤, 이 출력을 모두 OR 로 연결하여 구성이 가능하다. 그런데, 드 모르간 법칙을 이용하면 이들을 모두 NAND 게이트만으로 구성이 가능하게 된다. 예를 들어 $$X = A \cdot B + \overline{A} \cdot C + B \cdot C \cdot D $$ 라고 할 때, 드 모르간 법칙을 이용해서 변환하면, $$X = \overline{\overline{ A \cdot B} \cdot \overline{\overline{A} \cdot C} \cdot \overline{B \cdot C \cdot D}} $$ 로 바꿔 쓸 수 있는데, 이는 NAND 게이트만으로 회로 구성이 가능하다는 것을 의미한다.
전자회로에서 NAND 게이트는 구조가 가장 간단하고 입력이 많아져도 큰 지장이 없기에 가장 널리 쓰인다. 이것만으로 만든 메모리가 바로 우리가 일반적으로 부르는 낸드 플래시 메모리(NAND flach memory)이다. NAND게이트 만으로 만든 녀석이라 낸드플래시라고 부른다. 비슷한 원리로 NOR만으로 만든 녀석도 있는데, 이쪽은 노어(NOR)플래시라고 부른다. 다만 속도가 빠르다는 장점이 있지만, 낸드에 비해 가성비가 안 나와서 거의 도태되고, 특수 분야에서 한정된 용도로만 사용된다.