In propositional logic and Boolean algebra, De Morgan's laws are a pair of transformation rules that are both valid rules of inference. They are named after Augustus De Morgan, a 19th-century British mathematician. The rules allow the expression of conjunctions and disjunctions purely in terms of each other via negation. The rules can be expressed in English as: the negation of a disjunction is the conjunction of the negations the negation of a conjunction is the disjunction of the negationsor the complement of the union of two sets is the same as the intersection of their complements the complement of the intersection of two sets is the same as the union of their complementsor not (A or B) = (not A) and (not B) not (A and B) = (not A) or (not B),where "A or B" is an "inclusive or" meaning at least one of A or B rather than an "exclusive or" that means exactly one of A or B. In set theory and Boolean algebra, these are written formally as A ∪ B ¯ = A ¯ ∩ B ¯ , A ∩ B ¯ = A ¯ ∪ B ¯ , {\displaystyle {\begin{aligned}{\overline {A\cup B}}&={\overline {A}}\cap {\overline {B}},\\{\overline {A\cap B}}&={\overline {A}}\cup {\overline {B}},\end{aligned}}} where A {\displaystyle A} and B {\displaystyle B} are sets, A ¯ {\displaystyle {\overline {A}}} is the complement of A {\displaystyle A} , ∩ {\displaystyle \cap } is the intersection, and ∪ {\displaystyle \cup } is the union.In formal language, the rules are written as ¬ ( P ∨ Q ) ⟺ ( ¬ P ) ∧ ( ¬ Q ) , {\displaystyle \neg (P\lor Q)\iff (\neg P)\land (\neg Q),} and ¬ ( P ∧ Q ) ⟺ ( ¬ P ) ∨ ( ¬ Q ) {\displaystyle \neg (P\land Q)\iff (\neg P)\lor (\neg Q)} where P and Q are propositions, ¬ {\displaystyle \neg } is the negation logic operator (NOT), ∧ {\displaystyle \land } is the conjunction logic operator (AND), ∨ {\displaystyle \lor } is the disjunction logic operator (OR), ⟺ {\displaystyle \iff } is a metalogical symbol meaning "can be replaced in a logical proof with".Applications of the rules include simplification of logical expressions in computer programs and digital circuit designs. De Morgan's laws are an example of a more general concept of mathematical duality. == Formal notation == The negation of conjunction rule may be written in sequent notation: ¬ ( P ∧ Q ) ⊢ ( ¬ P ∨ ¬ Q ) {\displaystyle \neg (P\land Q)\vdash (\neg P\lor \neg Q)} ,and ( ¬ P ∨ ¬ Q ) ⊢ ¬ ( P ∧ Q ) {\displaystyle (\neg P\lor \neg Q)\vdash \neg (P\land Q)} .The negation of disjunction rule may be written as: ¬ ( P ∨ Q ) ⊢ ( ¬ P ∧ ¬ Q ) {\displaystyle \neg (P\lor Q)\vdash (\neg P\land \neg Q)} ,and ( ¬ P ∧ ¬ Q ) ⊢ ¬ ( P ∨ Q ) {\displaystyle (\neg P\land \neg Q)\vdash \neg (P\lor Q)} .In rule form: negation of conjunction ¬ ( P ∧ Q ) ∴ ¬ P ∨ ¬ Q {\displaystyle {\frac {\neg (P\land Q)}{\therefore \neg P\lor \neg Q}}} ¬ P ∨ ¬ Q ∴ ¬ ( P ∧ Q ) {\displaystyle {\frac {\neg P\lor \neg Q}{\therefore \neg (P\land Q)}}} and negation of disjunction ¬ ( P ∨ Q ) ∴ ¬ P ∧ ¬ Q {\displaystyle {\frac {\neg (P\lor Q)}{\therefore \neg P\land \neg Q}}} ¬ P ∧ ¬ Q ∴ ¬ ( P ∨ Q ) {\displaystyle {\frac {\neg P\land \neg Q}{\therefore \neg (P\lor Q)}}} and expressed as a truth-functional tautology or theorem of propositional logic: ¬ ( P ∧ Q ) → ( ¬ P ∨ ¬ Q ) , ( ¬ P ∨ ¬ Q ) → ¬ ( P ∧ Q ) , ¬ ( P ∨ Q ) → ( ¬ P ∧ ¬ Q ) , ( ¬ P ∧ ¬ Q ) → ¬ ( P ∨ Q ) , {\displaystyle {\begin{aligned}\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{aligned}}} where P {\displaystyle P} and Q {\displaystyle Q} are propositions expressed in some formal system. === Substitution form === De Morgan's laws are normally shown in the compact form above, with the negation of the output on the left and negation of the inputs on the right. A clearer form for substitution can be stated as: ( P ∧ Q ) ⟺ ¬ ( ¬ P ∨ ¬ Q ) , ( P ∨ Q ) ⟺ ¬ ( ¬ P ∧ ¬ Q ) . {\displaystyle {\begin{aligned}(P\land Q)&\Longleftrightarrow \neg (\neg P\lor \neg Q),\\(P\lor Q)&\Longleftrightarrow \neg (\neg P\land \neg Q).\end{aligned}}} This emphasizes the need to invert both the inputs and the output, as well as change the operator when doing a substitution. The laws have an important gap to the ( ¬ ( ¬ p ) ⟺ p {\displaystyle \neg (\neg p)\iff p} ) double negation law. L {\displaystyle \mathbb {L} } , to become a formal logic system: p , q , r , . . . . , ∅ ∈ L {\displaystyle \ p,q,r,....,\emptyset \in \mathbb {L} \ } sequence reports symbols that are defined well formed at first order. The same system has those conjunctions: C | j : x | x ∈ s e t :: { ∧ , ∨ , ⟺ , ⊢ } {\displaystyle C_{|j}:x\ |\ x\in set::\{\land ,\lor ,\iff ,\vdash \}} . Obviously, C | j = s e t , x ∈ C | j {\displaystyle C_{|j}=set,\ x\in C_{|j}} is valid knowledge, then there is at least one x {\displaystyle x} conjunction, which - T {\displaystyle T} number —in the truth table, basic proposition of x {\displaystyle x} — is equal to atomic existence context of x {\displaystyle x} , of course according to the ∀ x : ( L ⊨ ∀ c ⊊ C | j , x ∈ c ) {\displaystyle \forall x:(\mathbb {L} \vDash \forall c\subsetneq C_{|j},\ x\in c)} knowledge. We regarded the equivalence theory, the logic does. At this point, De Morgan Laws show effect that is upward or downward, the atomic context of x {\displaystyle x} . === Set theory and Boolean algebra === In set theory and Boolean algebra, it is often stated as "union and intersection interchange under complementation", which can be formally expressed as: A ∪ B ¯ = A ¯ ∩ B ¯ , A ∩ B ¯ = A ¯ ∪ B ¯ , {\displaystyle {\begin{aligned}{\overline {A\cup B}}&={\overline {A}}\cap {\overline {B}},\\{\overline {A\cap B}}&={\overline {A}}\cup {\overline {B}},\end{aligned}}} where: A ¯ {\displaystyle {\overline {A}}} is the negation of A {\displaystyle A} , the overline being written above the terms to be negated, ∩ {\displaystyle \cap } is the intersection operator (AND), ∪ {\displaystyle \cup } is the union operator (OR). ==== Infinite unions and intersections ==== The generalized form is ⋂ i ∈ I A i ¯ ≡ ⋃ i ∈ I A i ¯ , ⋃ i ∈ I A i ¯ ≡ ⋂ i ∈ I A i ¯ , {\displaystyle {\begin{aligned}{\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{aligned}}} where I is some, possibly uncountable, indexing set. In set notation, De Morgan's laws can be remembered using the mnemonic "break the line, change the sign". === Engineering === In electrical and computer engineering, De Morgan's laws are commonly written as: A ⋅ B ¯ ≡ A ¯ + B ¯ {\displaystyle {\overline {A\cdot B}}\equiv {\overline {A}}+{\overline {B}}} and A + B ¯ ≡ A ¯ ⋅ B ¯ , {\displaystyle {\overline {A+B}}\equiv {\overline {A}}\cdot {\overline {B}},} where: ⋅ {\displaystyle \cdot } is the logical AND, + {\displaystyle +} is the logical OR, the overbar is the logical NOT of what is underneath the overbar. === Text searching === De Morgan's laws commonly apply to text searching using Boolean operators AND, OR, and NOT. Consider a set of documents containing the words “cars” and “trucks”. De Morgan's laws hold that these two searches will return the same set of documents: Search A: NOT (cars OR trucks) Search B: (NOT cars) AND (NOT trucks)The corpus of documents containing “cars” or “trucks” can be represented by four documents: Document 1: Contains only the word “cars”. Document 2: Contains only “trucks”. Document 3: Contains both “cars” and “trucks”. Document 4: Contains neither “cars” nor “trucks”.To evaluate Search A, clearly the search “(cars OR trucks)” will hit on Documents 1, 2, and 3. So the negation of that search (which is Search A) will hit everything else, which is Document 4. Evaluating Search B, the search “(NOT cars)” will hit on documents that do not contain “cars”, which is Documents 2 and 4. Similarly the search “(NOT trucks)” will hit on Documents 1 and 4. Applying the AND operator to these two searches (which is Search B) will hit on the documents that are common to these two searches, which is Document 4. A similar evaluation can be applied to show that the following two searches will return the same set of documents (Documents 1, 2, 4): Search C: NOT (cars AND trucks), Search D: (NOT cars) OR (NOT trucks). == History == The laws are named after Augustus De Morgan (1806–1871), who introduced a formal version of the laws to classical propositional logic. De Morgan's formulation was influenced by algebraization of logic undertaken by George Boole, which later cemented De Morgan's claim to the find. Nevertheless, a similar observation was made by Aristotle, and was known to Greek and Medieval logicians. For example, in the 14th century, William of Ockham wrote down the words that would result by reading the laws out. Jean Buridan, in his Summulae de Dialectica, also describes rules of conversion that follow the lines of De Morgan's laws. Still, De Morgan is given credit for stating the laws in the terms of modern formal logic, and incorporating them into the language of logic. De Morgan's laws can be proved easily, and may even seem trivial. Nonetheless, these laws are helpful in making valid inferences in proofs and deductive arguments. == Informal proof == De Morgan's theorem may be applied to the negation of a disjunction or the negation of a conjunction in all or part of a formula. === Negation of a disjunction === In the case of its application to a disjunction, consider the following claim: "it is false that either of A or B is true", which is written as: ¬ ( A ∨ B ) . {\displaystyle \neg (A\lor B).} In that it has been established that neither A nor B is true, then it must follow that both A is not true and B is not true, which may be written directly as: ( ¬ A ) ∧ ( ¬ B ) . {\displaystyle (\neg A)\wedge (\neg B).} If either A or B were true, then the disjunction of A and B would be true, making its negation false. Presented in English, this follows the logic that "since two things are both false, it is also false that either of them is true". Working in the opposite direction, the second expression asserts that A is false and B is false (or equivalently that "not A" and "not B" are true). Knowing this, a disjunction of A and B must be false also. The negation of said disjunction must thus be true, and the result is identical to the first claim. === Negation of a conjunction === The application of De Morgan's theorem to conjunction is very similar to its application to a disjunction both in form and rationale. Consider the following claim: "it is false that A and B are both true", which is written as: ¬ ( A ∧ B ) . {\displaystyle \neg (A\land B).} In order for this claim to be true, either or both of A or B must be false, for if they both were true, then the conjunction of A and B would be true, making its negation false. Thus, one (at least) or more of A and B must be false (or equivalently, one or more of "not A" and "not B" must be true). This may be written directly as, ( ¬ A ) ∨ ( ¬ B ) . {\displaystyle (\neg A)\lor (\neg B).} Presented in English, this follows the logic that "since it is false that two things are both true, at least one of them must be false". Working in the opposite direction again, the second expression asserts that at least one of "not A" and "not B" must be true, or equivalently that at least one of A and B must be false. Since at least one of them must be false, then their conjunction would likewise be false. Negating said conjunction thus results in a true expression, and this expression is identical to the first claim. == Formal proof == Here we use A ∁ {\displaystyle A^{\complement }} to denote the complement of A. The proof that ( A ∩ B ) ∁ = A ∁ ∪ B ∁ {\displaystyle (A\cap B)^{\complement }=A^{\complement }\cup B^{\complement }} is completed in 2 steps by proving both ( A ∩ B ) ∁ ⊆ A ∁ ∪ B ∁ {\displaystyle (A\cap B)^{\complement }\subseteq A^{\complement }\cup B^{\complement }} and A ∁ ∪ B ∁ ⊆ ( A ∩ B ) ∁ {\displaystyle A^{\complement }\cup B^{\complement }\subseteq (A\cap B)^{\complement }} . === Part 1 === Let x ∈ ( A ∩ B ) ∁ {\displaystyle x\in (A\cap B)^{\complement }} . Then, x ∉ A ∩ B {\displaystyle x\not \in A\cap B} . Because A ∩ B = { y | y ∈ A ∧ y ∈ B } {\displaystyle A\cap B=\{\,y\ |\ y\in A\wedge y\in B\,\}} , it must be the case that x ∉ A {\displaystyle x\not \in A} or x ∉ B {\displaystyle x\not \in B} . If x ∉ A {\displaystyle x\not \in A} , then x ∈ A ∁ {\displaystyle x\in A^{\complement }} , so x ∈ A ∁ ∪ B ∁ {\displaystyle x\in A^{\complement }\cup B^{\complement }} . Similarly, if x ∉ B {\displaystyle x\not \in B} , then x ∈ B ∁ {\displaystyle x\in B^{\complement }} , so x ∈ A ∁ ∪ B ∁ {\displaystyle x\in A^{\complement }\cup B^{\complement }} . Thus, ∀ x ( x ∈ ( A ∩ B ) ∁ → x ∈ A ∁ ∪ B ∁ ) {\displaystyle \forall x(x\in (A\cap B)^{\complement }\rightarrow x\in A^{\complement }\cup B^{\complement })} ; that is, ( A ∩ B ) ∁ ⊆ A ∁ ∪ B ∁ {\displaystyle (A\cap B)^{\complement }\subseteq A^{\complement }\cup B^{\complement }} . === Part 2 === To prove the reverse direction, let x ∈ A ∁ ∪ B ∁ {\displaystyle x\in A^{\complement }\cup B^{\complement }} , and for contradiction assume x ∉ ( A ∩ B ) ∁ {\displaystyle x\not \in (A\cap B)^{\complement }} . Under that assumption, it must be the case that x ∈ A ∩ B {\displaystyle x\in A\cap B} , so it follows that x ∈ A {\displaystyle x\in A} and x ∈ B {\displaystyle x\in B} , and thus x ∉ A ∁ {\displaystyle x\not \in A^{\complement }} and x ∉ B ∁ {\displaystyle x\not \in B^{\complement }} . However, that means x ∉ A ∁ ∪ B ∁ {\displaystyle x\not \in A^{\complement }\cup B^{\complement }} , in contradiction to the hypothesis that x ∈ A ∁ ∪ B ∁ {\displaystyle x\in A^{\complement }\cup B^{\complement }} , therefore, the assumption x ∉ ( A ∩ B ) ∁ {\displaystyle x\not \in (A\cap B)^{\complement }} must not be the case, meaning that x ∈ ( A ∩ B ) ∁ {\displaystyle x\in (A\cap B)^{\complement }} . Hence, ∀ x ( x ∈ A ∁ ∪ B ∁ → x ∈ ( A ∩ B ) ∁ ) {\displaystyle \forall x(x\in A^{\complement }\cup B^{\complement }\rightarrow x\in (A\cap B)^{\complement })} , that is, A ∁ ∪ B ∁ ⊆ ( A ∩ B ) ∁ {\displaystyle A^{\complement }\cup B^{\complement }\subseteq (A\cap B)^{\complement }} . === Conclusion === If A ∁ ∪ B ∁ ⊆ ( A ∩ B ) ∁ {\displaystyle A^{\complement }\cup B^{\complement }\subseteq (A\cap B)^{\complement }} and ( A ∩ B ) ∁ ⊆ A ∁ ∪ B ∁ {\displaystyle (A\cap B)^{\complement }\subseteq A^{\complement }\cup B^{\complement }} , then ( A ∩ B ) ∁ = A ∁ ∪ B ∁ {\displaystyle (A\cap B)^{\complement }=A^{\complement }\cup B^{\complement }} ; this concludes the proof of De Morgan's law. The other De Morgan's law, ( A ∪ B ) ∁ = A ∁ ∩ B ∁ {\displaystyle (A\cup B)^{\complement }=A^{\complement }\cap B^{\complement }} , is proven similarly. == Generalising De Morgan duality == In extensions of classical propositional logic, the duality still holds (that is, to any logical operator one can always find its dual), since in the presence of the identities governing negation, one may always introduce an operator that is the De Morgan dual of another. This leads to an important property of logics based on classical logic, namely the existence of negation normal forms: any formula is equivalent to another formula where negations only occur applied to the non-logical atoms of the formula. The existence of negation normal forms drives many applications, for example in digital circuit design, where it is used to manipulate the types of logic gates, and in formal logic, where it is needed to find the conjunctive normal form and disjunctive normal form of a formula. Computer programmers use them to simplify or properly negate complicated logical conditions. They are also often useful in computations in elementary probability theory. Let one define the dual of any propositional operator P(p, q, ...) depending on elementary propositions p, q, ... to be the operator P d {\displaystyle {\mbox{P}}^{d}} defined by P d ( p , q , . . . ) = ¬ P ( ¬ p , ¬ q , … ) . {\displaystyle {\mbox{P}}^{d}(p,q,...)=\neg P(\neg p,\neg q,\dots ).} == Extension to predicate and modal logic == This duality can be generalised to quantifiers, so for example the universal quantifier and existential quantifier are duals: ∀ x P ( x ) ≡ ¬ [ ∃ x ¬ P ( x ) ] {\displaystyle \forall x\,P(x)\equiv \neg [\exists x\,\neg P(x)]} ∃ x P ( x ) ≡ ¬ [ ∀ x ¬ P ( x ) ] {\displaystyle \exists x\,P(x)\equiv \neg [\forall x\,\neg P(x)]} To relate these quantifier dualities to the De Morgan laws, set up a model with some small number of elements in its domain D, such as D = {a, b, c}.Then ∀ x P ( x ) ≡ P ( a ) ∧ P ( b ) ∧ P ( c ) {\displaystyle \forall x\,P(x)\equiv P(a)\land P(b)\land P(c)} and ∃ x P ( x ) ≡ P ( a ) ∨ P ( b ) ∨ P ( c ) . {\displaystyle \exists x\,P(x)\equiv P(a)\lor P(b)\lor P(c).} But, using De Morgan's laws, P ( a ) ∧ P ( b ) ∧ P ( c ) ≡ ¬ ( ¬ P ( a ) ∨ ¬ P ( b ) ∨ ¬ P ( c ) ) {\displaystyle P(a)\land P(b)\land P(c)\equiv \neg (\neg P(a)\lor \neg P(b)\lor \neg P(c))} and P ( a ) ∨ P ( b ) ∨ P ( c ) ≡ ¬ ( ¬ P ( a ) ∧ ¬ P ( b ) ∧ ¬ P ( c ) ) , {\displaystyle P(a)\lor P(b)\lor P(c)\equiv \neg (\neg P(a)\land \neg P(b)\land \neg P(c)),} verifying the quantifier dualities in the model. Then, the quantifier dualities can be extended further to modal logic, relating the box ("necessarily") and diamond ("possibly") operators: ◻ p ≡ ¬ ◊ ¬ p , {\displaystyle \Box p\equiv \neg \Diamond \neg p,} ◊ p ≡ ¬ ◻ ¬ p . {\displaystyle \Diamond p\equiv \neg \Box \neg p.} In its application to the alethic modalities of possibility and necessity, Aristotle observed this case, and in the case of normal modal logic, the relationship of these modal operators to the quantification can be understood by setting up models using Kripke semantics. == In Intuitionistic logic == Three out of the four implications of de Morgan's laws hold in intuitionistic logic. Specifically, we have ¬ ( P ∨ Q ) ⟺ ( ¬ P ) ∧ ( ¬ Q ) , {\displaystyle \neg (P\lor Q)\iff (\neg P)\land (\neg Q),} and ( P ∨ Q ) → ¬ ( ( ¬ P ) ∧ ( ¬ Q ) ) , {\displaystyle (P\lor Q)\rightarrow \neg ((\neg P)\land (\neg Q)),} ( P ∧ Q ) → ¬ ( ( ¬ P ) ∨ ( ¬ Q ) ) , {\displaystyle (P\land Q)\rightarrow \neg ((\neg P)\lor (\neg Q)),} ( ¬ P ) ∨ ( ¬ Q ) → ¬ ( P ∧ Q ) {\displaystyle (\neg P)\lor (\neg Q)\rightarrow \neg (P\land Q)} while the converse of the last implication does not hold in pure intuitionistic logic and would be equivalent to the law of the weak excluded middle ¬ P ∨ ¬ ¬ P {\displaystyle \neg P\lor \neg \neg P} which can be used as a foundation for an intermediate logic. == In Popular Culture == The 2nd most-famous quote from Sherlock Holmes stories, used several times, is a restatement of de Morgan's law: How often have I said to you that when you have eliminated the impossible, whatever remains, however improbable, must be the truth? == See also == Isomorphism – NOT operator as isomorphism between positive logic and negative logic List of Boolean algebra topics List of set identities and relations Positive logic == References == == External links == "Duality principle", Encyclopedia of Mathematics, EMS Press, 2001 [1994] Weisstein, Eric W. "de Morgan's Laws". MathWorld. de Morgan's laws at PlanetMath. Duality in Logic and Language, Internet Encyclopedia of Philosophy.