핵심답변
드모르간 법칙은 논리식 전체의 부정을 괄호 안으로 이동할 때 결합 연산이 바뀐다는 두 등가식이다. “A 또는 B가 아니다”는 “A가 아니고 B도 아니다”와 같고, “A와 B가 모두 성립하는 것은 아니다”는 “A가 아니거나 B가 아니다”와 같다. 기호로는 ¬(A∨B)≡¬A∧¬B, ¬(A∧B)≡¬A∨¬B다. 부정이 항마다 붙고 OR와 AND가 서로 교환되는 것이 핵심이다.
이 규칙은 문장 장난이 아니라 모든 가능한 진리값에서 두 식의 결과가 같다는 논리적 동치다. 집합에서는 합집합의 여집합이 각 여집합의 교집합이고, 교집합의 여집합이 각 여집합의 합집합이다. 디지털 회로에서는 출력에 부정이 붙은 NAND·NOR를 입력 부정과 쌍대 게이트로 바꿀 수 있다. 프로그램 조건문과 데이터베이스 검색에서도 같은 변환이 작동한다.
논리 연산부터 정확히 정의하기
명제는 참 또는 거짓을 판단할 수 있는 문장이다. A∧B는 둘 다 참일 때만 참이고, A∨B의 포괄적 OR는 둘 중 하나 이상이 참이면 참이다. ¬A는 A의 진리값을 뒤집는다. 일상어 “또는”이 때로 둘 중 하나만을 뜻하는 배타적 OR로 쓰이는 것과 구분해야 한다. 드모르간 법칙의 기본형은 포괄적 OR에 적용된다.
괄호 범위도 중요하다. ¬A∧B는 A만 부정한 뒤 B와 AND한 식이고, ¬(A∧B)는 결합 결과 전체를 부정한 식이다. 프로그래밍 언어의 연산자 우선순위를 외우더라도 사람이 읽기 쉬운 괄호를 명시하는 편이 안전하다. 이중부정 ¬¬A≡A와 함께 쓰면 부정을 안쪽이나 바깥쪽으로 이동할 수 있다.
진리표로 증명하는 과정
| A | B | ¬(A∨B) | ¬A∧¬B | ¬(A∧B) | ¬A∨¬B |
|---|---|---|---|---|---|
| 참 | 참 | 거짓 | 거짓 | 거짓 | 거짓 |
| 참 | 거짓 | 거짓 | 거짓 | 참 | 참 |
| 거짓 | 참 | 거짓 | 거짓 | 참 | 참 |
| 거짓 | 거짓 | 참 | 참 | 참 | 참 |
두 변수에는 네 가지 조합만 있으므로 모든 행을 비교하면 된다. 세 번째와 네 번째 열이 모든 행에서 같고, 다섯 번째와 여섯 번째 열도 같다. 특정 예시 몇 개가 맞는 것이 아니라 가능한 경우 전체에서 같으므로 등가식이다. 변수가 더 많아도 결합을 두 항씩 묶어 반복 적용할 수 있다.
문장으로 바꾸면 왜 헷갈리나
“민수와 지수가 모두 참석한 것은 아니다”는 둘 다 불참했다는 뜻이 아니다. 적어도 한 사람이 참석하지 않았다는 뜻이므로 “민수가 불참하거나 지수가 불참했다”와 같다. 반면 “민수 또는 지수가 참석한 것은 아니다”는 포괄적 OR 전체의 부정이라 둘 다 참석하지 않았다는 뜻이다. 자연어에서는 억양과 관습이 개입하므로 논리식을 먼저 적으면 범위가 분명해진다.
조건문의 부정도 자주 섞인다. “A이면 B다”의 부정은 “A이고 B가 아니다”이지 “A가 아니면 B가 아니다”가 아니다. 후자는 원 명제의 역·이를 혼동한 것이다. 드모르간 법칙은 조건문 자체를 바로 뒤집는 마법 규칙이 아니라, 조건문을 논리합으로 표현하거나 결론의 복합식을 부정할 때 정확히 적용한다.
집합에서는 같은 그림이 된다
전체집합 U에서 A∪B 밖에 있는 원소는 A에도 없고 B에도 없다. 따라서 (A∪B)ᶜ=Aᶜ∩Bᶜ다. 반대로 A∩B 밖에 있는 원소는 A에 없거나 B에 없으므로 (A∩B)ᶜ=Aᶜ∪Bᶜ다. 명제의 참·거짓 대신 원소가 집합에 속하는지를 쓰면 논리 법칙과 구조가 완전히 같다.
예를 들어 전체 고객 중 “서울 거주자 또는 유료회원”이 아닌 사람을 찾으면 서울 거주자가 아니면서 유료회원도 아닌 사람이다. “서울 거주자이면서 유료회원인 사람”이 아닌 집합은 서울 밖 거주자이거나 무료회원인 사람을 모두 포함한다. 여집합의 기준인 전체집합을 명시하지 않으면 결과 범위가 모호해진다.
논리·집합·회로 비교
| 영역 | OR에 해당 | AND에 해당 | NOT에 해당 | 드모르간 변환 |
|---|---|---|---|---|
| 명제논리 | ∨ | ∧ | ¬ | 결합 교환과 항별 부정 |
| 집합 | 합집합 | 교집합 | 여집합 | 합집합·교집합 교환 |
| 디지털 회로 | OR 게이트 | AND 게이트 | 인버터 | NOR↔입력 부정 AND, NAND↔입력 부정 OR |
| 프로그램 | || 또는 or | && 또는 and | ! 또는 not | 조건 범위를 등가 변환 |
| 데이터 검색 | 조건 중 하나 이상 | 모든 조건 | 제외 | NOT 괄호를 개별 제외로 분해 |
NAND와 NOR 회로에서의 활용
NAND는 AND 결과를 부정하고 NOR는 OR 결과를 부정한다. 드모르간 법칙에 따라 NAND 출력은 두 입력을 각각 부정한 뒤 OR한 것과 같고, NOR 출력은 두 입력을 각각 부정한 뒤 AND한 것과 같다. 회로도에서 게이트의 작은 원은 부정을 뜻하며 원을 입력 쪽으로 옮길 때 게이트 종류가 바뀌는 버블 푸싱 기법이 여기서 나온다.
NAND와 NOR는 각각 하나의 게이트 종류만으로 NOT·AND·OR를 모두 만들 수 있는 기능완전성을 가진다. 제조 공정이나 표준 셀에서 특정 게이트가 효율적이면 식을 그 형태로 바꿀 수 있다. 하지만 논리식의 게이트 수가 줄었다고 실제 지연·전력·면적이 항상 최소가 되는 것은 아니다. 팬인, 배선, 부하, 글리치와 공정 셀 특성을 함께 합성해야 한다.
실제 사례: 접근 권한 코드
사용자가 차단됐거나 계정이 만료된 경우 접근을 거부한다고 하자. 허용 조건은 “차단되지 않았고 만료되지 않았다”로 바꿀 수 있다. 즉 !(blocked || expired)는 !blocked && !expired와 같다. 긍정 조건으로 쓰면 읽기 쉬워질 수 있지만 변수 이름이 이미 부정형이면 이중부정이 늘어 오히려 위험하다.
또한 코드의 논리적 동치와 실행 동작은 구분해야 한다. 단락평가에서는 왼쪽 조건 결과에 따라 오른쪽 함수가 실행되지 않을 수 있다. 오른쪽 식에 로그 기록, 상태 변경, 예외 같은 부작용이 있으면 등가 변환 뒤 실행 순서가 달라질 수 있다. 조건식은 가능하면 부작용 없는 순수한 값으로 만들고 테스트로 경계를 확인한다.
검색과 필터에서의 활용
데이터베이스에서 NOT(country=’KR’ OR premium=true)는 country<>’KR’ AND premium<>true로 보이지만 NULL이 있으면 SQL의 세 값 논리 때문에 단순한 두 값 진리표와 결과가 달라질 수 있다. NULL 비교는 참도 거짓도 아닌 UNKNOWN이 될 수 있어 IS NULL 조건을 명시해야 한다. 드모르간 법칙이 틀린 것이 아니라 적용하는 논리 체계가 달라진 것이다.
검색엔진의 제외 연산도 마찬가지다. “고양이와 강아지를 모두 포함한 문서를 제외”하는 것과 “고양이 또는 강아지를 포함한 모든 문서를 제외”는 다르다. 자연어 요구를 합집합·교집합으로 그린 뒤 부정 범위를 정하면 과도한 제외를 줄일 수 있다.
오해하기 쉬운 점
- 부정만 각 항에 붙이면 된다? AND와 OR도 반드시 서로 바뀐다.
- OR는 항상 둘 중 정확히 하나다? 기본 논리의 OR는 하나 이상이 참인 포괄적 OR다.
- 조건문의 부정도 양쪽을 뒤집는다? “A이면 B”의 부정은 A∧¬B다.
- 회로가 등가면 물리 성능도 같다? 기능은 같아도 지연·전력·글리치는 다를 수 있다.
- 모든 프로그램에 그대로 적용된다? NULL, 단락평가와 부작용을 확인해야 한다.
활용과 한계
드모르간 법칙은 논리식을 읽기 쉬운 형태로 바꾸고, 부정을 변수 가까이 밀어 넣는 부정 정규형을 만들며, 증명과 회로 합성의 출발점이 된다. 테스트 조건의 누락을 찾고 보안 정책의 허용·거부 규칙을 검토할 때도 유용하다. 참·거짓 범주가 명확한 문제에서는 진리표로 즉시 검증할 수 있다.
하지만 모호한 자연어, 확률적 판단, 퍼지 논리나 SQL의 NULL처럼 두 값 논리가 아닌 체계에서는 전제부터 확인해야 한다. 양자 논리 등 모든 대수 구조가 고전 부울 대수와 같은 분배법칙을 가지는 것도 아니다. 도구를 넓게 쓰되 어떤 연산과 보수 개념을 쓰는지 명시해야 한다.
자주 묻는 질문
왜 부정이 들어가면 AND와 OR가 바뀌나요?
OR 전체가 거짓이려면 모든 항이 거짓이어야 하고, AND 전체가 거짓이려면 적어도 한 항이 거짓이면 되기 때문이다.
변수가 세 개여도 적용되나요?
된다. ¬(A∨B∨C)는 ¬A∧¬B∧¬C이고, ¬(A∧B∧C)는 ¬A∨¬B∨¬C다.
배타적 OR에도 같은 식을 쓰나요?
기본 두 식은 포괄적 OR와 AND에 대한 법칙이다. XOR의 부정은 두 입력이 같은 XNOR이므로 별도 정의로 다뤄야 한다.
드모르간 변환은 항상 코드를 빠르게 하나요?
아니다. 컴파일러가 같은 형태로 최적화할 수 있고 단락평가 순서가 성능과 동작에 영향을 준다. 가독성과 정확성을 먼저 본다.
결론
드모르간 법칙은 부정의 범위를 정확히 다루는 두 문장으로 논리·집합·회로를 연결한다. 괄호 전체를 부정할 때 각 항을 부정하고 AND와 OR를 교환하면 모든 진리값에서 같은 결과가 나온다. 진리표로 확인하고 집합의 원소 포함 관계로 이해하며 회로와 코드에 적용하면 암기식이 아니라 구조가 보인다. 다만 자연어의 OR 의미, NULL과 실행 부작용처럼 고전 두 값 논리 밖의 조건은 별도로 점검해야 한다.
한정자가 붙은 문장으로 확장하기
드모르간 구조는 “모든”과 “어떤”의 부정에도 나타난다. “모든 학생이 합격했다”의 부정은 “합격하지 않은 학생이 적어도 한 명 있다”이고, “합격한 학생이 한 명이라도 있다”의 부정은 “모든 학생이 합격하지 않았다”다. 기호로는 ¬∀xP(x)≡∃x¬P(x), ¬∃xP(x)≡∀x¬P(x)다. 전체와 존재가 교환되고 술어에 부정이 붙는다.
이 차이는 통계와 정책 문장을 읽을 때 중요하다. “모든 검사에서 문제가 발견되지 않았다”와 “어떤 검사에서도 문제가 발견되지 않았다”는 범위가 다르게 해석될 수 있다. 대상 집합과 예외 존재 여부를 명시하면 과도한 일반화를 막을 수 있다.
