 | This articlemay containoriginal research. Pleaseimprove it byverifying the claims made and addinginline citations. Statements consisting only of original research should be removed.(September 2025) (Learn how and when to remove this message) |
Inpropositional logic andBoolean algebra,De Morgan's laws,[1][2][3] also known asDe Morgan's theorem,[4] are a pair of transformation rules that are bothvalidrules of inference. They are named afterAugustus De Morgan, a 19th-century British mathematician. The rules allow the expression ofconjunctions anddisjunctions purely in terms of each other vianegation.
The rules can be expressed in English as:
or
or
where "A or B" is an "inclusive or" meaningat least one of A or B rather than an "exclusive or" that meansexactly one of A or B.
Another form of De Morgan's law is the following as seen below.
Applications of the rules include simplification of logicalexpressions incomputer programs and digital circuit designs. De Morgan's laws are an example of a more general concept ofmathematical duality.
Thenegation of conjunction rule may be written insequent notation:
Thenegation of disjunction rule may be written as:
Inrule form:negation of conjunction
andnegation of disjunction
and expressed as truth-functionaltautologies ortheorems of propositional logic:
where and are propositions expressed in some formal system.
Thegeneralized De Morgan's laws provide an equivalence for negating a conjunction or disjunction involving multiple terms.
For a set of propositions, the generalized De Morgan's Laws are as follows:
These laws generalize De Morgan's original laws for negating conjunctions and disjunctions.
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:
This emphasizes the need to invert both the inputs and the output, as well as change the operator when doing a substitution.
In set theory, it is often stated as "union and intersection interchange under complementation",[5] which can be formally expressed as:
where:
The generalized form is
whereI is some, possibly countably or uncountably infinite, indexing set.
In set notation, De Morgan's laws can be remembered using themnemonic "break the line, change the sign".[6]
In Boolean algebra, similarly, this law which can be formally expressed as:
where:
which can be generalized to
Inelectrical andcomputer engineering, De Morgan's laws are commonly written as:
and
where:
De Morgan's laws commonly apply to text searching using Boolean operators AND, OR, and NOT. Consider a set of documents containing the words "cats" and "dogs". De Morgan's laws hold that these two searches will return the same set of documents:
The corpus of documents containing "cats" or "dogs" can be represented by four documents:
To evaluate Search A, clearly the search "(cats OR dogs)" 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 cats)" will hit on documents that do not contain "cats", which is Documents 2 and 4. Similarly the search "(NOT dogs)" 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 both return Documents 1, 2, and 4:
The laws are named afterAugustus De Morgan (1806–1871),[7] who introduced a formal version of the laws to classicalpropositional logic. De Morgan's formulation was influenced by the algebraization of logic undertaken byGeorge Boole, which later cemented De Morgan's claim to the find. Nevertheless, a similar observation was made byAristotle, and was known to Greek and Medieval logicians.[8] For example, in the 14th century,William of Ockham wrote down the words that would result by reading the laws out.[9]Jean Buridan, in hisSummulae de Dialectica, also describes rules of conversion that follow the lines of De Morgan's laws.[10] 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.[11] Nonetheless, these laws are helpful in making valid inferences in proofs and deductive arguments.
De Morgan's theorem may be applied to the negation of adisjunction or the negation of aconjunction in all or part of a formula.
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:
In that it has been established thatneither A nor B is true, then it must follow that both A is not trueand B is not true, which may be written directly as:
If either A or Bwere 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.
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:
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,
Presented in a natural language like English, it is expressed as "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.
Here we use to denote the complement of A, as above in§ Set theory and Boolean algebra. The proof that is completed in 2 steps by proving both and.
Let. Then,.
Because, it must be the case that or.
If, then, so.
Similarly, if, then, so.
Thus,;
that is,.
To prove the reverse direction, let, and for contradiction assume.
Under that assumption, it must be the case that,
so it follows that and, and thus and.
However, that means, in contradiction to the hypothesis that,
therefore, the assumption must not be the case, meaning that.
Hence,,
that is,.
Ifand, then; this concludes the proof of De Morgan's law.
The other De Morgan's law,, is proven similarly.
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 onclassical logic, namely the existence ofnegation 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 indigital circuit design, where it is used to manipulate the types oflogic gates, and in formal logic, where it is needed to find theconjunctive normal form anddisjunctive normal form of a formula. Computer programmers use them to simplify or properly negate complicatedlogical conditions. They are also often useful in computations in elementaryprobability theory.
Let one define the dual of any propositional operator P(p,q, ...) depending on elementary propositionsp,q, ... to be the operator defined by
This duality can be generalised to quantifiers, so for example theuniversal quantifier andexistential quantifier are duals:
To relate these quantifier dualities to the De Morgan laws, consider adomain of discourseD (with some small number of entities) to which properties are ascribed universally and existentially, such as
Then express universal quantifier equivalently by conjunction of individual statements
and existential quantifier by disjunction of individual statements
But, using De Morgan's laws,
and
verifying the quantifier dualities in the model.
Then, the quantifier dualities can be extended further tomodal logic, relating the box ("necessarily") and diamond ("possibly") operators:
In its application to thealethic modalities of possibility and necessity,Aristotle observed this case, and in the case ofnormal modal logic, the relationship of these modal operators to the quantification can be understood by setting up models usingKripke semantics.
Three out of the four implications of de Morgan's laws hold inintuitionistic logic. Specifically, we have
and
The converse of the last implication does not hold in pure intuitionistic logic. That is, the failure of the joint proposition cannot necessarily be resolved to the failure of either of the twoconjuncts. For example, from knowing it not to be the case that both Alice and Bob showed up to their date, it does not follow who did not show up. The latter principle is equivalent to the principle of theweak excluded middle,
This weak form can be used as a foundation for anintermediate logic.For a refined version of the failing law concerning existential statements, see thelesser limited principle of omniscience, which however is different from.
The validity of the other three De Morgan's laws remains true if negation is replaced by implication for some arbitrary constant predicate C, meaning that the above laws are still true inminimal logic.
Similarly to the above, the quantifier laws:
and
are tautologies even in minimal logic with negation replaced with implying a fixed, while the converse of the last law does not have to be true in general.
Further, one still has
but their inversion impliesexcluded middle,.
| General |  | ||||
|---|---|---|---|---|---|
| Classical logics | |||||
| Principles | |||||
| Rules |
| ||||
| People | |||||
| Works | |||||
| Overview |  | |
|---|---|---|
| Axioms | ||
| Operations | ||
| ||
| Set types | ||
| Theories | ||
| ||
| Set theorists | ||
