드모르간의 법칙 (De Morgan's Laws)
쉽게 풀면
"A 아니면 B다"의 반대는 "A도 아니고 B도 아니다"이고, "A이면서 B다"의 반대는 "A가 아니거나 B가 아니다"라는 걸 집합 기호로 정리한 것이 드모르간의 법칙입니다. 예를 들어 학급에서 "축구를 좋아하거나 야구를 좋아하는 학생"의 여집합(그 조건에 속하지 않는 학생)은 "축구도 야구도 좋아하지 않는 학생", 즉 "축구를 안 좋아하면서 동시에 야구도 안 좋아하는 학생"과 정확히 같습니다. 이렇게 "또는"의 부정은 "그리고"로, "그리고"의 부정은 "또는"으로 뒤집힌다는 것이 이 법칙의 핵심입니다.
왜 중요한가
드모르간의 법칙은 논리식을 동치인 다른 형태로 자유롭게 바꿀 수 있게 해주기 때문에, 디지털 논리회로 설계에서 게이트 구성을 단순화하거나, 프로그래밍 언어의 조건문·컴파일러 최적화에서 부정 조건을 다루기 쉬운 형태로 정규화하는 데 실용적으로 쓰입니다. 이런 이유로 전산학과 전자공학의 이론적 배경뿐 아니라 실제 시스템 최적화 논문의 수식 전개 과정에서도 흔히 근거로 인용됩니다.
논문에서는 이렇게 쓰입니다
이 문장은 논리 회로 설계, 프로그램 조건문 최적화, 데이터베이스 질의 조건 단순화 등을 다루는 논문에서, 복잡한 부정 조건식을 더 다루기 쉬운 형태로 바꾸는 근거로 이 법칙을 사용했다는 뜻입니다.
디지털 회로 설계에서, 여러 종류의 논리 게이트를 조합한 회로를 한 가지 게이트(NAND)만으로 동일하게 동작하도록 바꾸는 과정에 이 법칙이 사용되었다는 뜻입니다.
조금 더 깊게 보면
드모르간의 법칙은 집합론뿐 아니라 불 대수(Boolean algebra)의 핵심 항등식이기도 해서, 디지털 논리회로에서 AND·OR·NOT 게이트 사이의 변환을 정당화하는 근거로 쓰입니다. 특히 임의의 논리 회로를 NAND 게이트나 NOR 게이트만으로 재구성할 수 있다는 사실도 이 법칙에서 비롯되며, 이는 실제 반도체 회로 설계에서 게이트 종류를 줄여 생산 단가를 낮추는 데 활용되는 원리입니다.
주의할 점
드모르간의 법칙은 집합 두 개뿐 아니라 세 개 이상의 집합, 그리고 명제 논리의 "그리고(∧)"와 "또는(∨)" 연산자에도 똑같이 확장되어 적용됩니다. 다만 이때 반드시 전체집합(또는 전체 논의 영역) 안에서의 여집합을 기준으로 해야 하며, 이는 집합과 명제와 논리 개념을 함께 이해해야 정확히 적용할 수 있습니다.