명제 논리(propositional logic)와 부울 대수(Boolean algebra)에서, 드 모르간의 법칙은 유효한(valid) 추론의 규칙(rules of inference) 둘 다인 변환 규칙의 한 쌍입니다. 그들은 19세기 영국의 수학자 오거스터스 드 모르간(Augustus De Morgan)의 이름을 따서 지어졌습니다. 규칙은 부정(negation)을 통해 순수하게 서로의 관점에서 곱(conjunctions)과 합(disjunctions)의 표현을 허용합니다.
그 규칙은 한글에서 다음처럼 표현될 수 있습니다:
- 논리합의 부정은 부정의 논리곱입니다; 그리고
- 논리곱의 부정은 부정의 논리합입니다;
또는
- 두 집합의 합집합의 여집합(complement)은 그들의 여집합의 교집합과 같습니다; 그리고
- 두 집합의 교집합의 여집합은 그들의 여집합의 합집합과 같습니다;
또는
- not (A or B) = not A and not B; and
- not (A and B) = not A or not B
집합 이론(set theory)과 부울 대수(Boolean algebra)에서, 이들은 공식적으로 다음으로 쓰입니다:
\(\quad \begin{align}
\overline{A \cup B} &= \overline{A} \cap \overline{B}, \\
\overline{A \cap B} &= \overline{A} \cup \overline{B},
\end{align}\)
여기서
- A와 B는 집합입니다,
- \(\overline{A}\)는 A의 여집합입니다,
- ∩는 교집합(intersection)이고,
- ∪는 합집합(union)입니다.
형식적 언어(formal language)에서, 그 규칙은 다음으로 쓰입니다:
\(\quad \neg(P\lor Q)\iff(\neg P)\land(\neg Q),\)
및
\(\quad \neg(P\land Q)\iff(\neg P)\lor(\neg Q)\)
여기서
- P와 Q는 제안입니다,
- \(\neg\)는 부정 논리적 연산자 (NOT)입니다,
- \(\land\)는 곱 논리 연산자 (AND)입니다,
- \(\lor\)는 합 논리 연산자 (OR)입니다,
- \(\iff\)는 "논리적 증명(logical proof)에서 ...로 대체될 수 있는"을 의미하는 메타-논리 기호입니다.
그 규칙의 응용은 컴퓨터 프로그램(computer program) 및 디지털 회로 설계에서 논리적 표현(expressions)의 단순화를 포함합니다. 드 모르간의 법칙은 수학적 이중성(mathematical duality)의 보다 일반적인 개념의 예제입니다.
Formal notation
곱의 부정 규칙은 시퀀트(sequent) 표기법에서 쓰일 수 있습니다:
\(\quad\displaystyle \neg(P \land Q) \vdash (\neg P \lor \neg Q)\),
및
\(\quad\displaystyle (\neg P \lor \neg Q) \vdash \neg(P \land Q)\).
합의 부정 규칙은 다음으로 쓰일 수 있습니다:
\(\quad\displaystyle \neg(P \lor Q) \vdash (\neg P \land \neg Q)\),
및
\(\quad\displaystyle (\neg P \land \neg Q) \vdash \neg(P \lor Q)\).
규칙 형식(rule form)에서: 곱의 부정
\(\quad\displaystyle \frac{\neg (P \land Q)}{\therefore \neg P \lor \neg Q}\)
\(\quad\displaystyle \frac{\neg P \lor \neg Q}{\therefore \neg (P \land Q)}\)
및 합의 부정
\(\quad\displaystyle \frac{\neg (P \lor Q)}{\therefore \neg P \land \neg Q}\)
\(\quad\displaystyle \frac{\neg P \land \neg Q}{\therefore \neg (P \lor Q)}\)
및 명제 논리의 진리-함수형 동의어-반복(tautology) 및 정리(theorem)로 표현됩니다:
\(\quad \begin{align}
\neg (P \land Q) &\to (\neg P \lor \neg Q), \\
(\neg P \lor \neg Q) &\to \neg (P \land Q), \\
\neg (P \lor Q) &\to (\neg P \land \neg Q), \\
(\neg P \land \neg Q) &\to \neg (P \lor Q),
\end{align}\)
여기서 \(P\)와 \(Q\)는 일부 형식적 시스템에서 표현된 명제입니다.
Substitution form
드 모르간의 법칙은 전형적으로 위의 간결한 형식으로 보이며, 왼쪽의 출력은 부정이고 오른쪽의 입력의 부정입니다. 대체에 대해 더 명확한 양식은 다음과 같이 말해질 수 있습니다:
\(\quad \begin{align}
(P \land Q) &\equiv \neg (\neg P \lor \neg Q), \\
(P \lor Q) &\equiv \neg (\neg P \land \neg Q).
\end{align}\)
이것은 대체를 행할 때 연산자를 바꾸는 것과 마찬가지로 입력과 출력 둘 다를 반전하는 것의 필요성을 강조합니다.
Set theory and Boolean algebra
집합 이론과 부울 대수(Boolean algebra)에서, 종종 "여집합 아래에서 합집합과 교집합 상호-교환"으로 표현되며, 공식적으로 다음과 같이 표현될 수 있습니다:
\(\quad \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)이 부정이 될 항 위에 쓰입니다,
- ∩는 연산자 교집합(intersection) (AND)입니다,
- ∪는 연산자 합집합(union) (OR)입니다.
Infinite unions and intersections
일반화된 형식은 다음입니다:
\(\quad \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는 어떤, 아마도 셀-수-없는, 인덱싱하는 집합입니다.
집합 표기법에서, 드 모르간의 법칙은 기억법(mnemonic) "줄을 자르면 기호를 바꿈"을 사용하여 기억될 수 있습니다.
Engineering
전기(electrical) 및 컴퓨터 공학(computer engineering)에서, 드 모르간의 법칙은 공통적으로 다음과 같이 쓰입니다:
\(\overline{A \cdot B} \equiv \overline {A} + \overline {B}\)
및
\(\overline{A + B} \equiv \overline {A} \cdot \overline {B},\)
여기서:
- \( \cdot \)는 논리적 AND입니다,
- \(+\)는 논리적 OR입니다,
- 윗줄은 그것 아래의 무엇의 논리적 NOT입니다.
Text searching
드 모르간의 법칙은 공통적으로 부울 연산자 AND, OR, 및 NOT을 사용하여 텍스트 검색에 적용됩니다. 단어 "자동차"와 "트럭"을 포함하는 문서의 집합을 생각해 보십시오. 드 모르간의 법칙은 이들 두 검색은 문서의 같은 집합을 반환할 것임을 유지합니다:
- 검색 A: NOT (자동차 OR 트럭)
- 검색 B: (NOT 자동차) AND (NOT 트럭)
"자동차" 또는 "트럭"을 포함하는 문서의 모음은 다음 네 가지 문서로 표시될 수 있습니다:
- 문서 1: 오직 단어 "자동차"를 포함합니다.
- 문서 2: 오직 단어 "트럭"을 포함합니다.
- 문서 3: "자동차"와 "트럭" 둘 다를 포함합니다.
- 문서 4: "자동차"도 "트럭"도 포함하지 않습니다.
검색 A를 평가하기 위해, 명확하게 검색 "(자동차 OR 트럭)"은 문서 1, 2 및 3에서 발견할 것입니다. 따라서 해당 검색의 부정 (이것이 검색 A입니다)은 그 밖의 모든 것을 발견할 것이며, 이것이 문서 4입니다.
검색 B, 검색 "(NOT 자동차)"를 평가하는 것은 "자동차"를 포함하지 않는 문서를 발견할 것이며, 이것은 문서 2와 4입니다. 비슷하게 검색 "(NOT 트럭)"은 문서 1과 4를 발견할 것입니다. 이들 두 검색에 AND 연산자를 적용하면 (이것이 검색 B입니다) 이들 두 검색에 공통인 문서를 발견할 것이며, 이것이 문서 4입니다.
비슷한 평가는 다음 두 검색이 문서의 같은 집합 (문서 1, 2, 4)를 반환할 것임을 보여주기 위해 적용될 수 있습니다:
- 검색 C: NOT (자동차 AND 트럭),
- 검색 D: (NOT 자동차) OR (NOT 트럭).
History
그 법칙은 오거스터스 드 모르간(Augustus De Morgan) (1806–1871)의 이름을 따서 지어졌으며, 그는 그 법칙의 형식적 버전을 고전적인 명제 논리(propositional logic)에 도입했습니다. 드 모르간의 공식화는 조지 부울(George Boole)에 의해 수행된 논리의 대수화에 의해 영향을 받았으며, 이것은 나중에 드 모르간의 주장에 근거를 두었습니다. 그럼에도 불구하고, 비슷한 관찰이 아리스토텔레스(Aristotle)에 의해 만들어졌고, 그리스와 중세의 논리 학자들에게 알려졌습니다. 예를 들어, 14세기에 오컴의 윌리엄(William of Ockham)은 법칙을 읽음으로써 초래될 수 있는 단어를 썼습니다. 장 뷔리당(Jean Buridan)은, 그의 Summulae de Dialectica에서, 드 모르간의 법칙의 줄을 따르는 변환의 규칙을 설명합니다. 여전히, 드 모르간은 현대 형식적 논리의 관점에서 법칙을 명시하고, 그것을 논리의 언어에 통합한 것에 대해 공인을 받았습니다. 드 모르간의 법칙은 쉽게 입증될 수 있고, 심지어 자명한 것처럼 보일 수 있습니다. 그럼에도 불구하고, 이들 법칙은 증명과 연역적 논증에서 유효한 추론을 만드는 것에 도움이 됩니다.
Informal proof
드 모르간의 정리는 논리합(disjunction)의 부정 또는 공식의 전부 또는 일부에서 논리곱(conjunction)의 부정에 적용될 수 있습니다.
Negation of a disjunction
논리합에 대한 그것의 응용의 경우에 대해, 다음 주장을 생각해 보십시오: "A 또는 B 중 하나가 참인 것에 부정합니다", 이것은 다음으로 쓰입니다:
\(\quad \neg(A\lor B).\)
A와 B가 모두 참이 아니라는 것이 입증되어야 하는 것에서, A가 참이 아님 그리고(and) B가 참이 아니 둘 다인 것을 반드시 따라야 하며, 이것은 다음으로 직접적으로 쓰일 수 있습니다:
\(\quad (\neg A)\wedge(\neg B).\)
만약 A 또는 B 중 하나가 참이 되면, A와 B의 논리합이 참이어야 하며, 그것의 부정을 부정으로 만듭니다. 한글로 제시된, 이것은 "두 가지가 모두 거짓이기 때문에 둘 중 하나가 참인 것도 역시 거짓"이라는 논리를 따릅니다.
반대 방향에서 작업할 때, 두 번째 표현은 A가 거짓이고 B가 거짓 (또는 동등하게 "A가 아님"과 "B가 아님"이 참)이라고 주장합니다. 이것을 알면, A와 B의 논리합은 역시 거짓이어야 합니다. 말했던 논리합의 부정은 따라서 사실이어야 하고, 그 결과는 첫 번째 주장과 동일합니다.
Negation of a conjunction
드 모르간의 정리를 논리곱에 응용은 형식과 이론적 해석에서 논리합에 대한 응용과 매우 유사합니다. 다음 주장을 생각해 보십시오: "A와 B가 모두 참인 것을 부정합니다", 이것은 다음으로 쓰입니다:
\(\quad \neg(A\land B).\)
이 주장을 참이 되기 위해, A 또는 B 중 하나 또는 둘 다가 거짓이어야 하며, 그들이 둘 다 참이면, A와 B의 논리곱이 참이어야 한다는 것에 대해, 그것의 부정을 거짓으로 만듭니다. 따라서, A와 B 중 하나 (적어도) 또는 그 이상은 거짓 (또는 동등하게, "A가 아님" 및 "B가 아님" 중 하나 이상이 참)이어야 합니다. 이것은 다음으로 직접적으로 쓰일 수 있습니다:
\(\quad (\neg A)\lor(\neg B).\)
한글로 제시된, 이것은 "두 가지가 모두 참이기 때문에, 그들의 적어도 하나가 거짓이어야 하는 것도 역시 거짓"이라는 논리를 따릅니다.
다시 반대 방향에서 작업할 때, 두 번째 표현은 "A가 아님"과 "B가 아님"의 적어도 하나가 참이어야 함, 또는 동등하게 A와 B의 적어도 하나가 거짓이어야 한다고 주장합니다. 그들의 적어도 하나가 거짓이어야 하기 때문에, 그들의 논리곱은 마찬가지로 거짓이어야 합니다. 말했던 논리곱의 부정은 따라서 참 표현을 초래하고, 그 표현은 첫 번째 주장과 동일합니다.
Formal proof
여기서 우리는 A의 여집합을 나타내기 위해 \(A^\complement\)를 사용합니다. \((A\cap B)^\complement = A^\complement \cup B^\complement\)인 것의 증명은 \((A\cap B)^\complement \subseteq A^\complement \cup B^\complement\) 및 \(A^\complement \cup B^\complement \subseteq (A\cap B)^\complement\) 둘 다를 입증함으로써 2 단계에서 완성됩니다.
Part 1
\(x \in (A \cap B)^\complement\)로 놓습니다. 그런-다음, \(x \not\in A \cap B\)입니다.
\(A \cap B = \{y | y \in A \land y \in B\}\)이기 때문에, \(x \not\in A\) 또는 \(x \not\in B\)인 경우여야 합니다.
만약 \(x \not\in A\)이면, \(x \in A^\complement\)이므로, \(x \in A^\complement \cup B^\complement\)입니다.
비슷하게, 만약 \(x \not\in B\)이면, \(x \in B^\complement\)이므로, \(x \in A^\complement\cup B^\complement\)입니다.
따라서, \(\forall x( x \in (A\cap B)^\complement \rightarrow x \in A^\complement \cup B^\complement)\)입니다;
즉, \((A\cap B)^\complement \subseteq A^\complement \cup B^\complement\)입니다.
Part 2
반대 방향을 입증하기 위해, \(x \in A^\complement \cup B^\complement\)로 놓고, 대우에 대해 \(x \not\in (A\cap B)^\complement\)임을 가정합니다.
해당 가정 아래에서, \(x \in A\cap B\)인 경우여야 하므로,
그것은 \(x \in A\) and \(x \in B\)임을 따르고, 따라서 \(x \not\in A^\complement\) 및 \(x \not\in B^\complement\)입니다.
어쨌든, 그것은 \(x \not\in A^\complement \cup B^\complement\)임을 의미하며, 가설에 대한 대우에서 \(x \in A^\complement \cup B^\complement\)인 것이며,
그러므로, 가정 \(x \not\in (A\cap B)^\complement\)은 그 경우에서 아니어야 하며, \(x \in (A\cap B)^\complement\)임을 의미합니다.
따라서, \(\forall x( x \in A^\complement \cup B^\complement \rightarrow x \in (A\cap B)^\complement)\)입니다,
즉, \(A^\complement \cup B^\complement \subseteq (A\cap B)^\complement\)입니다.
Conclusion
만약 \(A^\complement \cup B^\complement \subseteq (A\cap B)^\complement\) 그리고 \((A \cap B)^\complement \subseteq A^\complement \cup B^\complement\)이면, \((A\cap B)^\complement = A^\complement \cup B^\complement\)입니다; 이것이 드 모르간의 법칙의 증명을 매듭짓습니다.
나머지 드 모르간의 법칙, \((A \cup B)^\complement = A^\complement \cap B^\complement\)은 비슷하게 입증됩니다.
Generalising De Morgan duality
고전적 명제 논리의 확장에서, 이중성은 여전히 유지되는데 (즉, 임의의 논리적 연산자에 우리는 항상 그것의 이중을 찾을 수 있습니다), 왜냐하면 부정을 지배하는 항등식의 존재에서, 우리는 항상 다른 것의 드 모르간의 이중인 연산자를 도입할 수 있기 때문입니다. 이것은 고전적 논리(classical logic)에 기초한 논리학의 중요한 속성, 즉 부정 정규 형식(negation normal form)의 존재로 이어집니다: 임의의 공식은 부정이 공식의 비-논리적 원자에 오직 적용되는 또 다른 공식과 동등합니다. 부정 정규 형식의 존재는, 예를 들어 디지털 회로(digital circuit) 설계에서, 여기서 논리 회로(logic gate)의 유형을 조작하기 위해 사용되고, 형식적 논리에서, 여기서 공식의 논리곱 정규 형식(conjunctive normal form) 및 논리합 정규 형식(disjunctive normal form)을 찾기 위해 필요되는 것과 같은 많은 응용을 주도합니다. 컴퓨터 프로그래머는 그들을 복잡한 논리적 조건(logical conditions)을 단순화 또는 적절하게 부정하기 위해 사용합니다. 그들은 역시 종종 기초 확률 이론(probability theory)의 계산에 유용합니다.
우리는 기본 명제 p, q, ...에 따라 임의의 명제적 연산자 P(p, q, ...)의 이중을 다음에 의해 정의된 연산자 \(\mbox{P}^d\)가 되도록 정의합니다:
\(\quad \mbox{P}^d(p, q, ...) = \neg P(\neg p, \neg q, \dots).\)
Extension to predicate and modal logic
이 이중성은 한정어로 일반화될 수 있으므로, 예를 들어 보편 한정어(universal quantifier) 및 존재 한정어(existential quantifier)는 이중입니다:
\(\quad \forall x \, P(x) \equiv \neg [ \exists x \, \neg P(x)] \)
\(\quad \exists x \, P(x) \equiv \neg [ \forall x \, \neg P(x)] \)
이들 한정어 이중성을 드 모르간 법칙과 관련시키기 위해, 다음을 만족하는, 그것의 도메인 D에서 원소의 일부 작은 숫자를 갖는 모델(model)을 설정합니다:
\(\quad\) D = {a, b, c}.
그런-다음
\(\quad \forall x \, P(x) \equiv P(a) \land P(b) \land P(c) \)
및
\(\quad \exists x \, P(x) \equiv P(a) \lor P(b) \lor P(c).\)
그러나, 드 모르간의 법칙을 사용하여,
\(\quad P(a) \land P(b) \land P(c) \equiv \neg (\neg P(a) \lor \neg P(b) \lor \neg P(c)) \)
및
\(\quad P(a) \lor P(b) \lor P(c) \equiv \neg (\neg P(a) \land \neg P(b) \land \neg P(c)), \)
모델에서 한정어 이중성을 검증합니다.
그런-다음, 한정어 이중성은 더 나아가서 양식의 논리(modal logic)로 확장될 수 있으며, 네모 ("필연적으로") 및 다이아몬드 ("혹시") 연산자를 관련시킵니다:
\(\quad \Box p \equiv \neg \Diamond \neg p, \)
\(\quad \Diamond p \equiv \neg \Box \neg p.\)
가능성과 필연성의 논리 양식성(alethic modalities)에 대한 그것의 응용에서, 아리스토텔레스(Aristotle)는 이 경우를 관찰했었고, 정규 양식의 논리(normal modal logic)의 경우에서, 한정어에 대한 이들 양식의 연산자의 관계는 크립키 의미론(Kripke semantics)을 사용하여 모델을 설정함으로써 이해될 수 있습니다.
