드 모르간의 법칙

\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

로 표시한다.

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

일반화된 드 모르간의 법칙은 여러 항을 포함하는 결합 또는 분리의 부정에 대한 동치를 제공한다. 명제의 집합

P_1, P_2, \dots,P_n

에 대해, 일반화된 드 모르간의 법칙은 다음과 같다.

:

\begin{align}\lnot(P_1 \land P_2 \land \dots \land P_n) \leftrightarrow \lnot P_1 \lor \lnot P_2 \lor \ldots \lor \lnot P_n \\\lnot(P_1 \lor P_2 \lor \dots \lor P_n) \leftrightarrow \lnot P_1 \land \lnot P_2 \land \ldots \land \lnot P_n\end{align}

이 법칙들은 결합과 분리의 부정에 대한 드 모르간의 원래 법칙을 일반화한 것이다.

임의의 명제

P, Q \in \{ \bot, \top \}

(P와 Q는 참 또는 거짓 중 하나)에 대해

: “P 또는 Q”가 아닌 것은, “P가 아닌” 그리고 “Q가 아닌”과 같다.

: “P 그리고 Q”가 아닌 것은, “P가 아닌” 또는 “Q가 아닌”과 같다.

가 성립한다. 여기서

\lor

는 논리합,

\land

는 논리곱,

\neg

는 부정을 나타내는 연산자이다.

C언어와 그 영향을 받은 프로그래밍 언어에서 일반적인 논리식으로 나타내면 다음과 같다.

: !(P || Q) == !P && !Q

: !(P && Q) == !P || !Q

여기서 ||는 논리합, &&는 논리곱, !는 부정을 나타내는 논리 연산자이다.

보다 일반적인 법칙으로서, 임의의 n개의 명제

P_{1}, P_{2}, \cdots, P_{n}\in \{ \bot, \top \}

(P₁부터 Pₙ는 참 또는 거짓 중 하나)에 대해

:

\neg \left ( \bigvee_{i=1}^{n}P_{i} \right ) = \bigwedge_{i=1}^{n} \neg P_{i} \, , \quad \neg \left ( \bigwedge_{i=1}^{n}P_{i} \right ) = \bigvee_{i=1}^{n} \neg P_{i}

가 성립한다.

2. 2. 설명

\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

를 다음과 같이 시각적으로 표현할 수 있다.

위 설명은 두 명제나 집합에 대한 법칙을 보여주지만, 더 많은 명제에서도 동일한 법칙이 성립한다.

일반화된 드 모르간의 법칙은 여러 항을 포함하는 결합 또는 분리의 부정에 대한 동치를 제공한다. 명제의 집합

P_1, P_2, \dots,P_n

에 대해, 일반화된 드 모르간의 법칙은 다음과 같다.

$\lnot(P_1 \land P_2 \land \dots \land P_n) \leftrightarrow \lnot P_1 \lor \lnot P_2 \lor \ldots \lor \lnot P_n$
$\lnot(P_1 \lor P_2 \lor \dots \lor P_n) \leftrightarrow \lnot P_1 \land \lnot P_2 \land \ldots \land \lnot P_n$

이 법칙들은 결합과 분리의 부정에 대한 드 모르간의 원래 법칙을 일반화한 것이다.

드 모르간의 법칙은 논리식의 일부 또는 전체에서 합집합의 부정 또는 논리곱의 부정에 적용될 수 있다. 예를 들어 "A 또는 B 중 어느 것도 참이 아니다"라는 주장은

\neg(A\lor B)

로 쓸 수 있으며, 이는 A도 B도 참이 아니라는 의미이므로,

(\neg A)\wedge(\neg B)

와 같이 표현할 수 있다.

C언어와 그 영향을 받은 프로그래밍 언어에서 일반적인 논리식으로 나타내면 다음과 같다.

`!(P || Q) == !P && !Q`
`!(P && Q) == !P || !Q`

(여기서 `||`는 논리합, `&&`는 논리곱, `!`는 부정을 나타내는 논리 연산자이다.)

2. 3. 예시

"내 키는 160cm 이상이고, 몸무게는 50kg 이상"이라는 명제의 부정은 드 모르간의 법칙에 따라 "내 키는 160cm 미만이거나, 몸무게는 50kg 미만"이다. "이 공은 파랗거나, 빨갛다"라는 명제의 부정은 "이 공은 파랗지도, 빨갛지도 않다"이다.

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

1차 술어 논리에서 드 모르간의 법칙은 전칭 양화사(∀)와 존재 양화사(∃)를 포함하는 식으로 확장된다. 핵심은 "모든 x에 대해 A(x)이다"의 부정은 "어떤 x에 대해 A(x)가 아니다"와 같고, "어떤 x에 대해 A(x)이다"의 부정은 "모든 x에 대해 A(x)가 아니다"와 같다는 것이다.

이러한 관계는 양상 논리에서 □("필연적으로")와 ◊("가능하게") 연산자와의 관계로 확장될 수 있다.

3. 1. 공식

A(x)를 변수 x에 대한 서술자라고 할 때, 1차 술어 논리에 대한 드 모르간의 법칙은 다음과 같다.

"모든 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)"가 된다.

전칭 양화사와 존재 양화사는 이중성을 가지므로, 다음과 같이 표현할 수도 있다.

:

\forall x \, P(x) \equiv \neg [ \exists x \, \neg P(x)]

:

\exists x \, P(x) \equiv \neg [ \forall x \, \neg P(x)]

이러한 양화사 이중성은 양상 논리로 더 확장되어, □("필연적으로")와 ◊("가능하게") 연산자를 관련지을 수 있다.

:

\Box p \equiv \neg \Diamond \neg p,

:

\Diamond p \equiv \neg \Box \neg p.

3. 2. 설명

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가 나타내는 것이 무한할 경우 위처럼 드 모르간의 법칙으로 기술할 수 없다. 보통 술어 논리 체계에서는 무한한 경우에 대한 드 모르간의 법칙에 해당되는 공리로 인정되지만, 기호 논리학자 중 일부는 이를 인정하지 않을 경우에 대한 논리학 연구를 하기도 한다.

전칭 양화사와 존재 양화사에도 이중성이 적용된다.

:

\forall x \, P(x) \equiv \neg [ \exists x \, \neg P(x)]

:

\exists x \, P(x) \equiv \neg [ \forall x \, \neg P(x)]

이러한 양화사 이중성을 드 모르간의 법칙과 관련짓기 위해, 영역 ''D''에 소수의 원소를 갖는 모델을 설정하면 (예: ''D'' = {''a'', ''b'', ''c''}), 다음과 같은 관계를 확인할 수 있다.

:

\forall x \, P(x) \equiv P(a) \land P(b) \land P(c)

:

\exists x \, P(x) \equiv P(a) \lor P(b) \lor P(c).

드 모르간의 법칙을 사용하면,

:

P(a) \land P(b) \land P(c) \equiv \neg (\neg P(a) \lor \neg P(b) \lor \neg P(c))

:

P(a) \lor P(b) \lor P(c) \equiv \neg (\neg P(a) \land \neg P(b) \land \neg P(c)),

가 되어 모델에서 양화사 이중성이 성립함을 알 수 있다.

나아가, 양화사 이중성은 양상 논리로 확장되어 □("필연적으로")와 ◊("가능하게") 연산자를 관련지을 수 있다.

:

\Box p \equiv \neg \Diamond \neg p,

:

\Diamond p \equiv \neg \Box \neg p.

아리스토텔레스는 가능성과 필연성의 알레틱 양상에 대한 적용에서 이와 같은 관계를 관찰했으며, 정규 양상 논리의 경우, 이러한 양상 연산자와 양화의 관계는 크립케 의미론을 사용하여 모델을 설정함으로써 이해할 수 있다.

3. 3. 예시

1차 술어 논리에서 드 모르간의 법칙을 설명하는 구체적인 예시는 다음과 같다.

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

3. 4. 전칭 명제와 존재 명제

전칭 명제와 존재 명제에서의 드 모르간의 법칙은 전 부정과 부분 부정을 바꿔 말하는 것과 관련이 있다. 예를 들어 x가 책을 나타내는 변수이고, "책 x를 좋아한다"를 A(x)라고 할 때, "모든 책을 좋아한다"는 "모든 x에 대하여 A(x)"가 된다.

이 명제의 부분 부정인 "모든 책을 좋아하는 것은 아니다"는 "모든 x에 대하여 A(x)"의 부정이 되며, 드 모르간의 법칙에 따라 "어떤 x에 대하여 ￢A(x)", 즉 "좋아하지 않는 책도 있다"와 같다.

반대로, 전 부정인 "모든 책을 싫어한다"는 "모든 x에 대하여 ￢A(x)"를 의미하며, 드 모르간의 법칙에 따르면 "어떤 책을 좋아한다"의 부정이 된다.

"모든 사람은 냉장고를 가지고 있다"의 부정은 "어떤 사람은 냉장고를 가지고 있지 않다"(즉, "냉장고를 가지고 있지 않은 사람이 최소한 한 명 있다")가 된다.^[1]

4. 집합론에서의 드 모르간의 법칙

드 모르간의 법칙은 교집합(∩), 합집합(∪), 여집합(￣) 연산 간의 관계를 나타내는 법칙이다.

$\overline{(A\cap B)}=\overline{A}\cup \overline{B}$ 임을 증명하는 과정은 다음과 같다.

먼저, $x \in \overline{A \cap B}$ 라고 하면, $x \not\in A \cap B$ 이다. $A \cap B = \{\,y\ |\ y\in A \wedge y \in B\,\}$ 이므로, $x \not\in A$ 이거나 $x \not\in B$ 이어야 한다.

$x \not\in A$ 이면, $x \in \overline{A}$ 이고, 따라서 $x \in \overline{A} \cup \overline{B}$ 이다. 마찬가지로, $x \not\in B$ 이면, $x \in \overline{B}$ 이고, 따라서 $x \in \overline{A}\cup \overline{B}$ 이다. 따라서, $\forall x\Big( x \in \overline{A\cap B} \implies x \in \overline{A} \cup \overline{B}\Big)$ 이므로, $\overline{A\cap B} \subseteq \overline{A} \cup \overline{B}$ 이다.

반대로, $x \in \overline{A} \cup \overline{B}$ 라고 하고, $x \not\in \overline{A\cap B}$ 라고 가정하면, $x \in A\cap B$ 여야 한다. 따라서 $x \in A$ 이고 $x \in B$ 이며, $x \not\in \overline{A}$ 이고 $x \not\in \overline{B}$ 이다. 하지만 이는 $x \not\in \overline{A} \cup \overline{B}$ 를 의미하며, $x \in \overline{A} \cup \overline{B}$ 라는 가정과 모순된다. 따라서 $x \not\in \overline{A\cap B}$ 라는 가정은 틀렸고, $x \in \overline{A\cap B}$ 이다. 그러므로 $\forall x\Big( x \in \overline{A} \cup \overline{B} \implies x \in \overline{A\cap B}\Big)$ 이고, 즉 $\overline{A} \cup \overline{B} \subseteq \overline{A\cap B}$ 이다.

$\overline{A} \cup \overline{B} \subseteq \overline{A\cap B}$ 이고 $\overline{A \cap B} \subseteq \overline{A} \cup \overline{B}$ 이면, $\overline{A\cap B} = \overline{A} \cup \overline{B}$ 이다.

$\overline{A \cup B} = \overline{A} \cap \overline{B}$ 도 위와 비슷한 방식으로 증명할 수 있다.

4. 1. 공식

\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}

(다만, ￣ 기호는 전체 집합에 대한 여집합을 표현함)

집합론에서 이는 종종 "여집합에 대한 합집합과 교집합의 교환 법칙"으로 표현되며,^[5] 다음과 같이 공식적으로 표현할 수 있다.

:

\begin{align}\overline{A \cup B} &= \overline{A} \cap \overline{B}, \\\overline{A \cap B} &= \overline{A} \cup \overline{B},\end{align}

여기서:

$\overline{A}$ 는 $A$ 의 여집합(보수)이며, overline는 부정할 항 위에 쓰여진다.
$\cap$ 는 교집합 연산자(AND)이다.
$\cup$ 는 합집합 연산자(OR)이다.

일반화된 형태는 다음과 같다.

:

\begin{align}\overline{\bigcap_{i \in I} A_{i}} &\equiv \bigcup_{i \in I} \overline{A_{i}}, \\\overline{\bigcup_{i \in I} A_{i}} &\equiv \bigcap_{i \in I} \overline{A_{i}},\end{align}

여기서 는 유한하거나, 셀 수 있거나, 셀 수 없을 정도로 무한한 색인 집합이다.

집합 기호를 사용하면 드 모르간의 법칙은 "선을 끊고, 부호를 바꾼다"라는 기억술을 이용하여 기억할 수 있다.^[6]

4. 2. 설명

\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

로 표시한다.

두 명제나 집합뿐만 아니라 더 많은 명제에서도 동일한 법칙이 성립한다.

집합론에서 "여집합에 대한 합집합과 교집합의 교환 법칙"으로 표현되며,^[5] 다음과 같이 공식적으로 표현할 수 있다.

:

\begin{align}\overline{A \cup B} &= \overline{A} \cap \overline{B}, \\\overline{A \cap B} &= \overline{A} \cup \overline{B},\end{align}

여기서:

$\overline{A}$ 는 $A$ 의 여집합(보수)
$\cap$ 는 교집합 연산자(AND)
$\cup$ 는 합집합 연산자(OR)

일반화된 형태는 다음과 같다.

:

\begin{align}\overline{\bigcap_{i \in I} A_{i}} &\equiv \bigcup_{i \in I} \overline{A_{i}}, \\\overline{\bigcup_{i \in I} A_{i}} &\equiv \bigcap_{i \in I} \overline{A_{i}},\end{align}

여기서 `I`는 유한하거나, 셀 수 있거나, 셀 수 없을 정도로 무한한 색인 집합이다.

집합 기호를 사용하면 드 모르간의 법칙은 "선을 끊고, 부호를 바꾼다"라는 기억술을 이용하여 기억할 수 있다.^[6]

4. 3. 벤 다이어그램

벤 다이어그램을 사용하면 드 모르간의 법칙을 시각적으로 표현할 수 있다. 예를 들어

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

는 다음과 같이 나타낼 수 있다.

일반적인 집합론에서도 벤 다이어그램을 통해 드 모르간의 법칙을 확인할 수 있다.

5. 부울 대수에서의 드 모르간의 법칙

부울 대수는 논리 연산을 대수적으로 표현하는 방법으로, 드 모르간의 법칙은 부울 대수에서도 중요한 역할을 한다. 드 모르간의 법칙은 논리식의 일부 또는 전체에서 논리합의 부정 또는 논리곱의 부정에 적용될 수 있다.

5. 1. 공식

논리합(''or''), 논리곱(and), 부정(not)의 논리 기호를 사용하여 드 모르간의 법칙을 표시하면 아래와 같다.

:

\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

로 나타낼 수 있다.

드 모르간의 법칙은 두 명제나 집합뿐만 아니라 더 많은 명제에서도 동일하게 성립한다.

부울 대수(Boolean algebra)에서 드 모르간의 법칙을 표현하면 다음과 같다.

:

A = {0,1} , B = B' ,  \;\; '

는 부정

부울대수	결과값	비고
$A + 0$ $A \cdot 0$	$A$ $0$	일반 논리식
$(A+B)$ $(A \cdot B)$	$A$ \cdot B $A$ + B	드 모르간의 법칙

부울 대수에서 드모르간의 법칙은 다음과 같이 공식으로 표현할 수 있다.

: $\begin{align}\overline{A \land B} &= \overline{A} \lor \overline{B}, \\\overline{A \lor B} &= \overline{A} \land \overline{B},\end{align}$

여기서:

$\overline{A}$ 는 $A$ 의 부정(negation)을 나타내며, 부정할 항 위에 overline가 표기된다.
$\land$ 는 논리곱(logical conjunction) 연산자(AND)이다.
$\lor$ 는 논리합(logical disjunction) 연산자(OR)이다.

이 법칙은 다음과 같이 일반화할 수 있다.

:

\begin{align}\overline{A_1 \land A_2 \land \ldots \land A_{n}} = \overline{A_1} \lor \overline{A_2} \lor \ldots \lor \overline{A_{n}}, \\\overline{A_1 \lor A_2 \lor \ldots \lor A_{n}} = \overline{A_1} \land \overline{A_2} \land \ldots \land \overline{A_{n}}.\end{align}

임의의 명제

P, Q \in \{ \bot, \top \}

(P와 Q는 참 또는 거짓 중 하나)에 대해:

“P 또는 Q”가 아닌 것은, “P가 아닌 것”과 “Q가 아닌 것”이 모두 참인 것과 같다.
“P 그리고 Q”가 아닌 것은, “P가 아닌 것” 또는 “Q가 아닌 것” 중 적어도 하나가 참인 것과 같다.

여기서

\lor

는 논리합,

\land

는 논리곱,

\neg

는 부정을 나타내는 연산자이다.

C언어와 그 영향을 받은 프로그래밍 언어에서 드 모르간의 법칙은 다음과 같이 나타낸다.

: `!(P || Q) == !P && !Q`

: `!(P && Q) == !P || !Q`

여기서 `||`는 논리합, `&&`는 논리곱, `!`는 부정을 나타내는 논리 연산자이다.

더 일반적인 법칙으로서, 임의의 n개의 명제

P_{1}, P_{2}, \cdots, P_{n}\in \{ \bot, \top \}

(P₁부터 Pₙ는 참 또는 거짓 중 하나)에 대해:

:

\neg \left ( \bigvee_{i=1}^{n}P_{i} \right ) = \bigwedge_{i=1}^{n} \neg P_{i} \, , \quad \neg \left ( \bigwedge_{i=1}^{n}P_{i} \right ) = \bigvee_{i=1}^{n} \neg P_{i}

가 성립한다.

L을 임의의 부울 대수라 하고, 임의의

x,y \in L

에 대해서:

:

(x \cup y)^{c} = x^{c} \cap y^{c} \, ,

:

(x \cap y)^{c} = x^{c} \cup y^{c}

가 성립한다.

\{ a_{\lambda} | \lambda \in \Lambda \}

를 L의 임의의 부분집합이라 하자.

\textstyle \sup_{\lambda \in \Lambda} a_{\lambda}

가 존재할 때,

\textstyle \inf_{\lambda \in \Lambda} a_{\lambda}^{c}

도 존재하며,

:

\left ( \sup_{\lambda \in \Lambda} a_{\lambda} \right )^{c} = \inf_{\lambda \in \Lambda} a_{\lambda}^{c}

가 성립한다. 또,

\textstyle \inf_{\lambda \in \Lambda} a_{\lambda}

가 존재할 때,

\textstyle \sup_{\lambda \in \Lambda} a_{\lambda}^{c}

도 존재하며,

:

\left ( \inf_{\lambda \in \Lambda} a_{\lambda} \right )^{c} = \sup_{\lambda \in \Lambda} a_{\lambda}^{c}

가 성립한다. 이를 드 모르간의 일반 법칙이라고 한다.

5. 2. 설명

\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

로 표시한다.

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

논리학이나 컴퓨터 과학 등에서 부울 대수(Boolean algebra)에 대한 드 모르간의 법칙의 예는 다음과 같다.

:

A = {0,1} , B = B' ,  \;\; '

는 부정

부울대수	결과값
$A + 0$ $A \cdot 0$	$A$ $0$	일반 논리식
$(A+B)$ $(A \cdot B)$	$A$ \cdot B $A$ + B	드 모르간의 법칙

부울 대수에서도 마찬가지로, 다음과 같이 공식적으로 표현할 수 있는 드 모르간의 법칙이 존재한다.

: $\begin{align}\overline{A \land B} &= \overline{A} \lor \overline{B}, \\\overline{A \lor B} &= \overline{A} \land \overline{B},\end{align}$

여기서:

$\overline{A}$ 는 $A$ 의 부정(negation)을 나타내며, 부정할 항 위에 overline가 표기된다.
$\land$ 는 논리곱(logical conjunction) 연산자(AND)이다.
$\lor$ 는 논리합(logical disjunction) 연산자(OR)이다.

이는 다음과 같이 일반화할 수 있다.

:

\begin{align}\overline{A_1 \land A_2 \land \ldots \land A_{n}} = \overline{A_1} \lor \overline{A_2} \lor \ldots \lor \overline{A_{n}}, \\\overline{A_1 \lor A_2 \lor \ldots \lor A_{n}} = \overline{A_1} \land \overline{A_2} \land \ldots \land \overline{A_{n}}.\end{align}

C언어와 그 영향을 받은 프로그래밍 언어에서 일반적인 논리식으로 나타내면 다음과 같다.

:!(P || Q) == !P && !Q

:!(P && Q) == !P || !Q

여기서 ||는 논리합, &&는 논리곱, !는 부정을 나타내는 논리 연산자이다.

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

드 모르간의 법칙은 컴퓨터 공학 및 디지털 논리에서 회로 설계를 단순화하는 데 널리 사용된다.^[12]

6. 1. 공식

\lor

\land