
In
propositional logic
The propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. Sometimes, it is called ''first-order'' propositional logic to contra ...
and
Boolean algebra
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variable (mathematics), variables are the truth values ''true'' and ''false'', usually denot ...
, De Morgan's laws, also known as De Morgan's theorem, are a pair of transformation rules that are both
valid rules of inference
Rules of inference are ways of deriving conclusions from premises. They are integral parts of formal logic, serving as norms of the logical structure of valid arguments. If an argument with true premises follows a rule of inference then the c ...
. They are named after
Augustus De Morgan
Augustus De Morgan (27 June 1806 – 18 March 1871) was a British mathematician and logician. He is best known for De Morgan's laws, relating logical conjunction, disjunction, and negation, and for coining the term "mathematical induction", the ...
, a 19th-century British mathematician. The rules allow the expression of
conjunctions and
disjunctions purely in terms of each other via
negation
In logic, negation, also called the logical not or logical complement, is an operation (mathematics), operation that takes a Proposition (mathematics), proposition P to another proposition "not P", written \neg P, \mathord P, P^\prime or \over ...
.
The rules can be expressed in English as:
* The negation of "A and B" is the same as "not A or not B".
* The negation of "A or B" is the same as "not A and not B".
or
* 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 complements
or
* 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
In logic, disjunction (also known as logical disjunction, logical or, logical addition, or inclusive disjunction) is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is ...
" meaning ''at least'' one of A or B rather than an "
exclusive or
Exclusive or, exclusive disjunction, exclusive alternation, logical non-equivalence, or logical inequality is a logical operator whose negation is the logical biconditional. With two inputs, XOR is true if and only if the inputs differ (on ...
" that means ''exactly'' 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 logical
expressions in
computer program
A computer program is a sequence or set of instructions in a programming language for a computer to Execution (computing), execute. It is one component of software, which also includes software documentation, documentation and other intangibl ...
s 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
In mathematical logic, a sequent is a very general kind of conditional assertion.
: A_1,\,\dots,A_m \,\vdash\, B_1,\,\dots,B_n.
A sequent may have any number ''m'' of condition formulas ''Ai'' (called " antecedents") and any number ''n'' of ass ...
notation:
:
The ''negation of disjunction'' rule may be written as:
:
In
rule form: ''negation of conjunction''
and ''negation of disjunction''
and expressed as truth-functional
tautologies or
theorem
In mathematics and formal logic, a theorem is a statement (logic), statement that has been Mathematical proof, proven, or can be proven. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to esta ...
s of propositional logic:
:
where
and
are propositions expressed in some formal system.
The generalized 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.
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:
:
This emphasizes the need to invert both the inputs and the output, as well as change the operator when doing a substitution.
Set theory
In set theory, it is often stated as "union and intersection interchange under complementation",
[''Boolean Algebra'' by R. L. Goodstein. ] which can be formally expressed as:
:
where:
*
is the negation of
, the
overline
An overline, overscore, or overbar, is a typographical feature of a horizontal and vertical, horizontal line drawn immediately above the text. In old mathematical notation, an overline was called a ''vinculum (symbol), vinculum'', a notation fo ...
being written above the terms to be negated,
*
is the
intersection
In mathematics, the intersection of two or more objects is another object consisting of everything that is contained in all of the objects simultaneously. For example, in Euclidean geometry, when two lines in a plane are not parallel, their ...
operator (AND),
*
is the
union operator (OR).
Unions and intersections of any number of sets
The generalized form is
:
where is some, possibly countably or uncountably infinite, indexing set.
In set notation, De Morgan's laws can be remembered using the
mnemonic
A mnemonic device ( ), memory trick or memory device is any learning technique that aids information retention or retrieval in the human memory, often by associating the information with something that is easier to remember.
It makes use of e ...
"break the line, change the sign".
Boolean algebra
In Boolean algebra, similarly, this law which can be formally expressed as:
:
where:
*
is the negation of
, the
overline
An overline, overscore, or overbar, is a typographical feature of a horizontal and vertical, horizontal line drawn immediately above the text. In old mathematical notation, an overline was called a ''vinculum (symbol), vinculum'', a notation fo ...
being written above the terms to be negated,
*
is the
logical conjunction
In logic, mathematics and linguistics, ''and'' (\wedge) is the Truth function, truth-functional operator of conjunction or logical conjunction. The logical connective of this operator is typically represented as \wedge or \& or K (prefix) or ...
operator (AND),
*
is the
logical disjunction
In logic, disjunction (also known as logical disjunction, logical or, logical addition, or inclusive disjunction) is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is ...
operator (OR).
which can be generalized to
:
Engineering
In
electrical
Electricity is the set of physical phenomena associated with the presence and motion of matter possessing an electric charge. Electricity is related to magnetism, both being part of the phenomenon of electromagnetism, as described by Maxwel ...
and
computer engineering
Computer engineering (CE, CoE, or CpE) is a branch of engineering specialized in developing computer hardware and software.
It integrates several fields of electrical engineering, electronics engineering and computer science.
Computer engi ...
, De Morgan's laws are commonly written as:
:
and
:
where:
*
is the logical AND,
*
is the logical OR,
* the 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 "cats" and "dogs". De Morgan's laws hold that these two searches will return the same set of documents:
:Search A: NOT (cats OR dogs)
:Search B: (NOT cats) AND (NOT dogs)
The corpus of documents containing "cats" or "dogs" can be represented by four documents:
:Document 1: Contains only the word "cats".
:Document 2: Contains only "dogs".
:Document 3: Contains both "cats" and "dogs".
:Document 4: Contains neither "cats" nor "dogs".
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:
:Search C: NOT (cats AND dogs),
:Search D: (NOT cats) OR (NOT dogs).
History
The laws are named after
Augustus De Morgan
Augustus De Morgan (27 June 1806 – 18 March 1871) was a British mathematician and logician. He is best known for De Morgan's laws, relating logical conjunction, disjunction, and negation, and for coining the term "mathematical induction", the ...
(1806–1871), who introduced a formal version of the laws to classical
propositional logic
The propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. Sometimes, it is called ''first-order'' propositional logic to contra ...
. De Morgan's formulation was influenced by the algebraization of logic undertaken by
George Boole
George Boole ( ; 2 November 1815 – 8 December 1864) was a largely self-taught English mathematician, philosopher and logician, most of whose short career was spent as the first professor of mathematics at Queen's College, Cork in Ireland. H ...
, which later cemented De Morgan's claim to the find. Nevertheless, a similar observation was made by
Aristotle
Aristotle (; 384–322 BC) was an Ancient Greek philosophy, Ancient Greek philosopher and polymath. His writings cover a broad range of subjects spanning the natural sciences, philosophy, linguistics, economics, politics, psychology, a ...
, and was known to Greek and Medieval logicians. For example, in the 14th century,
William of Ockham
William of Ockham or Occam ( ; ; 9/10 April 1347) was an English Franciscan friar, scholastic philosopher, apologist, and theologian, who was born in Ockham, a small village in Surrey. He is considered to be one of the major figures of medie ...
wrote down the words that would result by reading the laws out.
Jean Buridan
Jean Buridan (; ; Latin: ''Johannes Buridanus''; – ) was an influential 14thcentury French scholastic philosopher.
Buridan taught in the faculty of arts at the University of Paris for his entire career and focused in particular on logic and ...
, in his , 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.
Proof for Boolean algebra
De Morgan's theorem may be applied to the negation of a
disjunction
In logic, disjunction (also known as logical disjunction, logical or, logical addition, or inclusive disjunction) is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is ...
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:
:
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:
:
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:
:
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.
Proof for set theory
Here we use
to denote the complement of A, as above in . The proof that
is completed in 2 steps by proving both
and
.
Part 1
Let
. Then,
.
Because
, it must be the case that
or
.
If
, then
, so
.
Similarly, if
, then
, so
.
Thus,
;
that is,
.
Part 2
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,
.
Conclusion
If
''and''
, then
; this concludes the proof of De Morgan's law.
The other De Morgan's law,
, 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
Classical logic (or standard logic) or Frege–Russell logic is the intensively studied and most widely used class of deductive logic. Classical logic has had much influence on analytic philosophy.
Characteristics
Each logical system in this c ...
, 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
In theoretical computer science, a circuit is a model of computation in which input values proceed through a sequence of gates, each of which computes a function. Circuits of this kind provide a generalization of Boolean circuits and a mathematica ...
design, where it is used to manipulate the types of
logic gate
A logic gate is a device that performs a Boolean function, a logical operation performed on one or more binary inputs that produces a single binary output. Depending on the context, the term may refer to an ideal logic gate, one that has, for ...
s, and in formal logic, where it is needed to find the
conjunctive normal form
In Boolean algebra, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of one or more clauses, where a clause is a disjunction of literals; otherwise put, it is a product of sums or an AND of ORs.
In au ...
and
disjunctive normal form
In boolean logic, a disjunctive normal form (DNF) is a canonical normal form of a logical formula consisting of a disjunction of conjunctions; it can also be described as an OR of ANDs, a sum of products, or in philosophical logic a ''cluster c ...
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
Probability theory or probability calculus is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expre ...
.
Let one define the dual of any propositional operator P(''p'', ''q'', ...) depending on elementary propositions ''p'', ''q'', ... to be the operator
defined by
:
Extension to predicate and modal logic
This duality can be generalised to quantifiers, so for example the
universal quantifier
In mathematical logic, a universal quantification is a type of quantifier, a logical constant which is interpreted as "given any", "for all", "for every", or "given an arbitrary element". It expresses that a predicate can be satisfied by e ...
and
existential quantifier
Existentialism is a family of philosophy, philosophical views and inquiry that explore the human individual's struggle to lead an Authenticity (philosophy), authentic life despite the apparent Absurdity#The Absurd, absurdity or incomprehensibili ...
are duals:
:
:
To relate these quantifier dualities to the De Morgan laws, consider a
domain of discourse
In the formal sciences, the domain of discourse or universe of discourse (borrowing from the mathematical concept of ''universe'') is the set of entities over which certain variables of interest in some formal treatment may range.
It is also ...
''D'' (with some small number of entities) to which properties are ascribed universally and existentially, such as
:''D'' = .
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 to
modal logic
Modal logic is a kind of logic used to represent statements about Modality (natural language), necessity and possibility. In philosophy and related fields
it is used as a tool for understanding concepts such as knowledge, obligation, and causality ...
, relating the box ("necessarily") and diamond ("possibly") operators:
:
:
In its application to the
alethic modalities
Alethic modality (from Greek Aletheia, ἀλήθεια = truth) is a linguistic modality that indicates modalities of truth, in particular the modalities of logical necessity, contingency, possibility and impossibility.
Alethic modality is often ...
of possibility and necessity,
Aristotle
Aristotle (; 384–322 BC) was an Ancient Greek philosophy, Ancient Greek philosopher and polymath. His writings cover a broad range of subjects spanning the natural sciences, philosophy, linguistics, economics, politics, psychology, a ...
observed this case, and in the case of
normal modal logic
In logic, a normal modal logic is a set ''L'' of modal formulas such that ''L'' contains:
* All propositional tautology (logic), tautologies;
* All instances of the Kripke_semantics, Kripke schema: \Box(A\to B)\to(\Box A\to\Box B)
and it is closed ...
, the relationship of these modal operators to the quantification can be understood by setting up models using
Kripke semantics
Kripke semantics (also known as relational semantics or frame semantics, and often confused with possible world semantics) is a formal semantics for non-classical logic systems created in the late 1950s and early 1960s by Saul Kripke and André ...
.
In intuitionistic logic
Three out of the four implications of de Morgan's laws hold in
intuitionistic logic
Intuitionistic logic, sometimes more generally called constructive logic, refers to systems of symbolic logic that differ from the systems used for classical logic by more closely mirroring the notion of constructive proof. In particular, systems ...
. 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 two
conjuncts. 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 the
weak excluded middle ,
:
This weak form can be used as a foundation for an
intermediate logic
In mathematical logic, a superintuitionistic logic is a propositional logic extending intuitionistic logic. Classical logic is the strongest consistent superintuitionistic logic; thus, consistent superintuitionistic logics are called intermediate ...
.
For a refined version of the failing law concerning existential statements, see the
lesser 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 in
minimal 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 implies
excluded middle
In logic, the law of excluded middle or the principle of excluded middle states that for every proposition, either this proposition or its negation is true. It is one of the three laws of thought, along with the law of noncontradiction and th ...
,
.
In computer engineering
* De Morgan's laws are widely used in computer engineering and digital logic for the purpose of simplifying circuit designs.
* In modern programming languages, compilers and interpreters use De Morgan's laws to optimize boolean expressions. Therefore performance differences between logically equivalent expressions are usually negligible or completely absent.
See also
*
Conjunction/disjunction duality
*
Homogeneity (linguistics)
*
Isomorphism
In mathematics, an isomorphism is a structure-preserving mapping or morphism between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between the ...
*
List of Boolean algebra topics
This is a list of topics around Boolean algebra and propositional logic.
Articles with a wide scope and introductions
* Algebra of sets
* Boolean algebra (structure)
* Boolean algebra
* Field of sets
* Logical connective
* Propo ...
*
List of set identities and relations
This article lists mathematical properties and laws of sets, involving the set-theoretic operations of union, intersection, and complementation and the relations of set equality and set inclusion. It also provides systematic procedures for ...
*
Positive logic
In digital circuits, a logic level is one of a finite number of State (computer science), states that a digital signal can inhabit. Logic levels are usually represented by the voltage difference between the signal and Ground (electricity), ground ...
*
De Morgan algebra
References
External links
*
*
*
Duality in Logic and Language ''Internet Encyclopedia of Philosophy''.
{{Set theory
Boolean algebra
Duality theories
Rules of inference
Articles containing proofs
Theorems in propositional logic