[include(틀:이산수학·수리논리학)] [목차] == 개요 == [[논리학]]과 [[수학]]의 법칙 중 하나이다. [[논리 연산]]에서 논리합은 논리곱과 부정기호로, 논리곱은 논리합과 부정기호로 표현할 수 있음을 가리키는 법칙이다. 일반적인 표현으로 > [math(\mathsf{not}(A \ \mathsf{ or } \ B) = (\mathsf{not}\ A)\ \mathsf{ and }\ (\mathsf{not}\ B))] [br] [math(\mathsf{not} (A \ \mathsf{ and }\ B) = (\mathsf{not}\ A)\ \mathsf{ or }\ (\mathsf{not} \ B))] 논리곱(합)의 부정은 각각 부정의 논리합(곱)과 같다는 법칙. 이는 논리학과 동일하게 집합론, 전자회로등에서도 똑같이 사용된다. 아래는 동일한 내용을 각각의 학문에서 주로 사용하는 수식으로 표현한 것이다. 표기법이 조금씩 다르지만, 모두 동일한 내용이다. > 논리학 > [math(\neg (p \lor q) = \neg p \land \neg q)] [br] [math(\neg (p \land q) = \neg p \lor \neg q)] > 집합론 > [math((A\cup B)^c = A^c \cap B^c )] [br] [math((A\cap B)^c = A^c \cup B^c )] > 전자회로 > [math(\overline{(A + B)} = \overline{A} \cdot \overline{B})] [br] [math(\overline{(A \cdot B)} = \overline{A} + \overline{B})] 수학자 [[오거스터스 드 모르간]]에 의해 증명되었으며, 이 수학자의 이름이 붙어 있다. == 벤 다이어그램으로 본 법칙 == 제일 먼저 이를 접하게 되는 것은 집합에서 [[벤 다이어그램]]'으로 이 둘이 같다는 것을 보여주는 형태로 나타난다. [[파일:external/upload.wikimedia.org/400px-Demorganlaws.svg.png]] == [[논리회로|전자회로]]에서의 응용 == 전자회로 등에서는 약간 응용해서 [math(A + B = \overline{ \overline{A} \cdot \overline{B}})] 나 [math(A \cdot B = \overline{\overline{A} + \overline{B}})] 형식으로 표현하는 경우도 있지만, 위의 같은 식이란 것을 쉽게 유도할 수 있다. [[파일:external/hyperphysics.phy-astr.gsu.edu/demorgan2.gif|bgcolor=white]] 전자회로는 일반적으로 회로식을 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 flach memory)이다. NAND게이트 만으로 만든 녀석이라 낸드플래시라고 부른다. 비슷한 원리로 NOR만으로 만든 녀석도 있는데, 이쪽은 노어(NOR)플래시라고 부른다. 다만 속도가 빠르다는 장점이 있지만, 낸드에 비해 [[가성비]]가 안 나와서 거의 도태되고, 특수 분야에서 한정된 용도로만 사용된다. [[분류:논리학]][[분류:집합론]]