드 모르간의 법칙

드 모르간의 법칙(영어: De Morgan's laws), 또는 드 모르간의 정리^[1]는 수리 논리학이나 집합론, 컴퓨터 과학 등에서 논리곱(집합의 공통 부분), 논리합(집합의 모든 부분), 부정(여집합) 연산간의 관계(드 모르간의 상대성이라고 부름)를 기술하여 정리한 것으로, 수학자 오거스터스 드 모르간의 이름을 따서 드 모르간의 법칙이라고 한다.

전기, 전자 공학적으로는 논리 회로에서 응용되기도 하는데, AND 연산과 OR 연산을 이용한다.

개요

논리합 $\lor$ , 논리곱 $\land$ , 부정 $\neg$ 의 논리 기호를 사용하여 표시하면, 아래와 같다.

\neg (P\lor Q)=\neg P\land \neg Q

\neg (P\land Q)=\neg P\lor \neg Q

동일한 뜻을 집합의 기호로 바꾸면 다음과 같이 된다.

{\overline {(A\cap B)}}={\overline {A}}\cup {\overline {B}}

{\overline {(A\cup B)}}={\overline {A}}\cap {\overline {B}}

(다만, ￣ 기호는 전체 집합에 대한 여집합을 표현함) 벤 다이어그램을 사용하면 $\neg (P\lor Q)\equiv \neg P\land \neg Q$ 로 표시한다：

부정합 (OR) $P\lor Q$ 혹은 $P\cup Q$
논리 부정 $\neg (P\lor Q)$ 혹은 ${\overline {(P\cup Q)}}$

한쪽의 논리 부정 (NOT-P) $\neg P$ 혹은 ${\overline {P}}$
다른 한쪽의 논리 부정 (NOT-Q) $\neg Q$ 혹은 ${\overline {Q}}$
부정 두 개의 논리곱 $\neg P\land \neg Q$ 혹은 ${\overline {P}}\cap {\overline {Q}}$

여기에는 두 명제나 집합에 대한 법칙을 말하고 있지만, 더 많은 명제에서도 동일한 법칙이 성립한다. 여집합의 기록을 참조할 것.

논리 회로에서의 드 모르간의 법칙

아래 공식에서 *는 AND 연산자를, +는 OR 연산자를 뜻한다.

{\overline {(A+B)}}={\overline {A}}*{\overline {B}}

{\overline {(A*B)}}={\overline {A}}+{\overline {B}}

예시

「내 키는 160 cm 이상이고, 몸무게는 50 kg 이상」의 부정은 「내 키는 160 cm 미만이고, 몸무게는 50 kg 미만」이 아니다. 드 모르간의 법칙에 따르면 「내 키는 160 cm 미만이거나, 몸무게는 50 kg 미만」이다. 같은 식으로, 「이 공은 파랗거나, 빨갛다.」 의 부정은 「이 공은 파랗지도, 빨갛지도 않다.」 가 된다.

술어 논리에서 드 모르간의 법칙

드 모르간의 법칙을 확장한 것으로 1차 술어 논리에 대한 드 모르간의 법칙이 있다 : A(x)를 변수 x에 대한 서술자라고 할 때

「모든 x에 대한 A(x)」의 부정은 「어떤 x가 존재시 ￢A(x)」
「어떤 x가 존재시 A(x)」의 부정은「모든 x에 대한 ￢A(x)」

구체적인 예를 들면,

「모든 사람은 냉장고를 가지고 있다」의 부정은「어떤 사람은 냉장고를 가지고 있지 않다」（즉, 「냉장고를 가지고 있지 않은 사람은 적어도 한 명이상 있다」）
「어떤 사람은 냉장고를 가지고 있다」（즉, 「냉장고를 가지고 있는 사람이 적어도 한 명 이상 있다」)의 부정은 「모든 사람이 냉장고를 가지고 있지 않다」.

「모든 x에 대해〜」나 「어떤 x에 대한〜」을 양화자 기호로 $\forall x,\exists x$ 를 사용하여 표기하며, 술어 논리에서 드 모르간의 법칙은 다음과 같이 쓸 수 있다：

$\neg \forall x~A(x)\Leftrightarrow \exists x~\neg A(x)$
$\neg \exists x~A(x)\Leftrightarrow \forall x~\neg A(x)$

명제 논리에서 드 모르간의 법칙을 이용하면, 아래와 같은 술어 논리의 드 모르간의 법칙을 확인할 수 있다.

x가 1부터 100까지의 수를 나타내는 변수라고 하자. 이때 「모든 x에 대한 A(x)」가 있다면,「A(1)와 A(2)와… A(100)」를 의미한다. 이것을 부정하면

￢A(1) 또는 ￢「A(2)와... A(100)」

처럼 되며, 「A(2)와… A(100)」의 부정을 동일한 방법으로 반복하면「￢A(1) 또는 ￢A(2) 또는 … ￢A(100)」가 된다. 이것은 「어떤 x에 대한 ￢A(x)」를 뜻하고 있다. 반대로, 「어떤 x에 대한 A(x)」와 「A(1) 또는 A(2) 또는 … A(100)」라고 하는 것의 부정은

￢A(1)와 ￢「A(2)또는... A(100)」

이고, 이것을 계속하면 「모든 x에 대한 ￢A(x)」가 된다.

드 모르간의 법칙과 무한

위의 술어 논리에서 드 모르간의 법칙의 내용으로 「모든 x에 대한A(x)」를 「A(1)와 A(2)와…A(100)」로 정의하고 논의를 시작하였지만, 이러한 것은 변수 x가 유한할 경우에만 가능하다. x가 나타내는 것이 무한할 경우 위처럼 드 모르간의 법칙으로 기술할 수 없다. 보통 술어 논리 체계에서는 무한한 경우에 대한 드 모르간의 법칙에 해당되는 공리로 인정되지만, 기호 논리학자 중 일부는 이것을 인정하지 않을 경우에 대한 논리학 연구를 하기도 한다.

전 부정과 부분 부정

전 부정이나 부분 부정을 변경하는 방법은 (술어 논리에서) 드 모르간의 법칙과 관련이 있다. 예를 들어 x가 책을 나타내는 변수라고 하고, 「책 x를 좋아한다」를 A(x)라고 하면, 「모든 책을 좋아한다」는 「모든 x에 대하여 A(x)」가 된다

이것의 부분 부정 「모든 책을 좋아하는 것은 아니다」는 「모든 x에 대하여 A(x)」의 부정이며, 드 모르간의 법칙에 따라 「어떤 x에 대하여 ￢A(x)」, 즉 「좋아하지 않는 책도 있다」라고 하면 된다. 반면에 전 부정 「모든 책을 싫어한다」는 「모든 x에 대하여 ￢A(x)」를 가리키는 드 모르간의 법칙에 따르면 「어떤 책을 좋아한다」의 부정이 된다.