Concept
De Morgan's laws
Overview
In propositional logic and Boolean algebra, De Morgan's laws, also known as De Morgan's theorem, 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 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" meaning at least one of A or B rather than an "exclusive or" that means exactly one of A or B.
Another form of De Morgan's law is the following as seen below.
A
−
(
B
∪
C
)
=
(
A
−
B
)
∩
(
A
−
C
)
,
{\displaystyle A-(B\cup C)=(A-B)\cap (A-C),}
A
−
(
B
∩
C
)
=
(
A
−
B
)
∪
(
A
−
C
)
.
{\displaystyle A-(B\cap C)=(A-B)\cup (A-C).}
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.
Overview adapted from Wikipedia (CC BY-SA 4.0; see the article history for authors).
Possible passages
Found by search and not yet checked by a person; they may only mention the idea in passing.
And so it has the same object matter as Practical Wisdom; yet the two faculties are not identical, because Practical Wisdom has the capacity for commanding and taking the initiative, for its End is “what one should do or not do:” but Judiciousness is only apt to decide upon suggestions (though we do in Greek put “well” on to the faculty and its concrete noun, these really mean exactly the same as the plain words)…
Aristotle, The Nicomachean ethics of Aristotle
States what De Morgan's laws is; the author is tied to De Morgan's laws in the knowledge graph.
The only laws of resemblance, therefore, which we are called upon to consider independently of causation, belong to the province of mathematics.
John Stuart Mill, A System of Logic, Ratiocinative and Inductive
States what De Morgan's laws is.
Thus there is a reference here to an external standard, for if the terms 'great' and 'small' were used absolutely, a mountain would never be called small or a grain large. Again, we say that there are many people in a village, and few in Athens, although those in the city are many times as numerous as those in the village: or we say that a house has many in it, and a theatre few, though those in the theatre far…
Aristotle, The Categories
States what De Morgan's laws is; the author is tied to De Morgan's laws in the knowledge graph.
Philosophers who discussed De Morgan's laws
Related ideas
- Exclusive or
- Negation
- Intuitionistic logic
- Jean Buridan
- Law of excluded middle
- Logical conjunction
- Propositional logic
- Augustus De Morgan
- Validity (logic)
- Domain of discourse
- Intersection (set theory)
- Probability theory
- Rule of inference
- Minimal logic
- Aristotle
- Theorem
- Modal logic
- William of Ockham
- George Boole
- Tautology (logic)
- Union (set theory)
- Complement (set theory)
- Boolean algebra
- Classical logic
Opposing perspectives
Place in the tradition
Part of Analytic philosophy.