De Morgan's laws
Encyclopedia
In formal logic
, De Morgan's laws are rules relating the logical operators "and
" and "or
" in terms of each other via negation. With two operands A and B:
In another form:
The rules can be expressed in English as:
form:
where:
In set theory and Boolean algebra, it is often stated as "Union and intersection interchange under complementation.":
where: is the negation of A, the overline
being written above the terms to be negated
The generalized form is:
where I is some, possibly uncountable, indexing set.
In set notation, De Morgan's law can be remembered using the mnemonic
"break the line, change the sign".
Or stated as functions:
This emphasizes the need to invert both the inputs and the output, as well as change the operator, when doing a substitution.
(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. Although a similar observation was made by Aristotle
and was known to Greek and Medieval logicians (in the 14th century William of Ockham
wrote down the words that would result by reading the laws out), De Morgan is given credit for stating the laws formally and incorporating them in to 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.
in all or part of a formula.
In that it has been established that neither A nor B is true, then it must follow that A is not true and B is not true. If either A or B were true, then the disjunction of A and B would be true, making its negation false.
Working in the opposite direction with the same type of problem, consider this claim:
This claim asserts that A is false and B is false (or "not A" and "not B" are true). Knowing this, a disjunction of A and B must be false also. However, the negation of said disjunction yields a true result that is logically equivalent to the original claim. Presented in English, this follows the logic that "Since two things are both false, it is also false that either of them is true."
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. So, the original claim may be translated as "A is false and/or B is false", or "'Not A' is true and/or 'not B' is true".
Presented in English, this would follow the logic that "Since it is false that two things are both true, at least one of them must be false."
s; "1" represents true, "0" represents false.
First we prove:
Since the values in the 4th and last columns are the same for all rows (which cover all possible truth value assignments to the variables), we can conclude that the two expressions are logically equivalent.
Now we prove by the same method:
design, where it is used to manipulate the types of logic gate
s, and in formal logic, where it is a prerequisite for finding 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 us define the dual of any propositional operator P(p, q, ...) depending on elementary propositions p, q, ... to be the operator
defined by
This idea can be generalised to quantifiers, so for example the universal quantifier and existential quantifier are duals:
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
Then
and
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
, relating the box ("necessarily") and diamond ("possibly") operators:
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
.
Formal logic
Classical or traditional system of determining the validity or invalidity of a conclusion deduced from two or more statements...
, De Morgan's laws are rules relating the logical operators "and
Logical conjunction
In logic and mathematics, a two-place logical operator and, also known as logical conjunction, results in true if both of its operands are true, otherwise the value of false....
" and "or
Logical disjunction
In logic and mathematics, a two-place logical connective or, is a logical disjunction, also known as inclusive disjunction or alternation, that results in true whenever one or more of its operands are true. E.g. in this context, "A or B" is true if A is true, or if B is true, or if both A and B are...
" in terms of each other via negation. With two operands A and B:
In another form:
- NOT (A AND B) = (NOT A) OR (NOT B)
- NOT (A OR B) = (NOT A) AND (NOT B)
The rules can be expressed in English as:
"The negation of a conjunctionLogical conjunctionIn logic and mathematics, a two-place logical operator and, also known as logical conjunction, results in true if both of its operands are true, otherwise the value of false....
is the disjunctionLogical disjunctionIn logic and mathematics, a two-place logical connective or, is a logical disjunction, also known as inclusive disjunction or alternation, that results in true whenever one or more of its operands are true. E.g. in this context, "A or B" is true if A is true, or if B is true, or if both A and B are...
of the negations." and
"The negation of a disjunction is the conjunction of the negations."
Formal definition
In propositional calculusPropositional calculus
In mathematical logic, a propositional calculus or logic is a formal system in which formulas of a formal language may be interpreted as representing propositions. A system of inference rules and axioms allows certain formulas to be derived, called theorems; which may be interpreted as true...
form:
where:
- ¬ is the negation operator (NOT)
is the conjunction operator (AND)
is the disjunction operator (OR)- ⇔ means logically equivalentLogical equivalenceIn logic, statements p and q are logically equivalent if they have the same logical content.Syntactically, p and q are equivalent if each can be proved from the other...
(if and only ifIf and only ifIn logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
)
In set theory and Boolean algebra, it is often stated as "Union and intersection interchange under complementation.":
where: is the negation of A, the overline
Overline
An overline or overbar or overscore , refers to the typographical feature of a line drawn immediately above the text, for example used to indicate medieval sigla. Specifically, a line drawn over one symbol is a macron, and a line over a collection of symbols is a vinculum...
being written above the terms to be negated
- ∩ is the intersectionIntersection (set theory)In mathematics, the intersection of two sets A and B is the set that contains all elements of A that also belong to B , but no other elements....
operator (AND) - ∪ is the unionUnion (set theory)In set theory, the union of a collection of sets is the set of all distinct elements in the collection. The union of a collection of sets S_1, S_2, S_3, \dots , S_n\,\! gives a set S_1 \cup S_2 \cup S_3 \cup \dots \cup S_n.- Definition :...
operator (OR)
The generalized form is:
where I is some, possibly uncountable, indexing set.
In set notation, De Morgan's law can be remembered using the mnemonic
Mnemonic
A mnemonic , or mnemonic device, is any learning technique that aids memory. To improve long term memory, mnemonic systems are used to make memorization easier. Commonly encountered mnemonics are often verbal, such as a very short poem or a special word used to help a person remember something,...
"break the line, change the sign".
Substitution form
De Morgan's laws are normally shown in the compact form above, with negation of the output on the left and negation of the inputs on the right. A clearer form for substitution can be stated as:Or stated as functions:
- P AND Q = NOT( (NOT P) OR (NOT Q) )
- P OR Q = NOT( (NOT P) AND (NOT Q) )
This emphasizes the need to invert both the inputs and the output, as well as change the operator, when doing a substitution.
History
The law is named after Augustus De MorganAugustus De Morgan
Augustus De Morgan was a British mathematician and logician. He formulated De Morgan's laws and introduced the term mathematical induction, making its idea rigorous. The crater De Morgan on the Moon is named after him....
(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
George Boole
George Boole was an English mathematician and philosopher.As the inventor of Boolean logic—the basis of modern digital computer logic—Boole is regarded in hindsight as a founder of the field of computer science. Boole said,...
, which later cemented De Morgan's claim to the find. Although a similar observation was made by Aristotle
Aristotle
Aristotle was a Greek philosopher and polymath, a student of Plato and teacher of Alexander the Great. His writings cover many subjects, including physics, metaphysics, poetry, theater, music, logic, rhetoric, linguistics, politics, government, ethics, biology, and zoology...
and was known to Greek and Medieval logicians (in the 14th century William of Ockham
William of Ockham
William of Ockham was an English Franciscan friar and scholastic philosopher, who is believed to have been born in Ockham, a small village in Surrey. He is considered to be one of the major figures of medieval thought and was at the centre of the major intellectual and political controversies of...
wrote down the words that would result by reading the laws out), De Morgan is given credit for stating the laws formally and incorporating them in to 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 conjunctionLogical conjunction
In logic and mathematics, a two-place logical operator and, also known as logical conjunction, results in true if both of its operands are true, otherwise the value of false....
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 A is true 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 A is not true and B is not true. If either A or B were true, then the disjunction of A and B would be true, making its negation false.
Working in the opposite direction with the same type of problem, consider this claim:
This claim asserts that A is false and B is false (or "not A" and "not B" are true). Knowing this, a disjunction of A and B must be false also. However, the negation of said disjunction yields a true result that is logically equivalent to the original claim. Presented in English, this follows the logic that "Since two things are both false, it is also false that either of them is true."
Negation of a conjunction
The application of De Morgan's theorem to a 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. So, the original claim may be translated as "A is false and/or B is false", or "'Not A' is true and/or 'not B' is true".
Presented in English, this would follow the logic that "Since it is false that two things are both true, at least one of them must be false."
By truth table
The laws may be proven directly using truth tableTruth table
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—to compute the functional values of logical expressions on each of their functional arguments, that is, on each combination of values taken by their...
s; "1" represents true, "0" represents false.
First we prove:
| p | q | p ∨ q | ¬(p ∨ q) | ¬p | ¬q | (¬p) ∧ (¬q) |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
Since the values in the 4th and last columns are the same for all rows (which cover all possible truth value assignments to the variables), we can conclude that the two expressions are logically equivalent.
Now we prove by the same method:
| p | q | p ∧ q | ¬(p ∧ q) | ¬p | ¬q | (¬p) ∨ (¬q) |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
Extensions
In extensions of classical propositional logic, the duality still holds (that is, to any logical operator we 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 circuitDigital circuit
Digital electronics represent signals by discrete bands of analog levels, rather than by a continuous range. All levels within a band represent the same signal state...
design, where it is used to manipulate the types of logic gate
Logic gate
A logic gate is an idealized or physical device implementing a Boolean function, that is, it performs a logical operation on one or more logic inputs and produces a single logic output. Depending on the context, the term may refer to an ideal logic gate, one that has for instance zero rise time and...
s, and in formal logic, where it is a prerequisite for finding the conjunctive normal form
Conjunctive normal form
In Boolean logic, a formula is in conjunctive normal form if it is a conjunction of clauses, where a clause is a disjunction of literals.As a normal form, it is useful in automated theorem proving...
and disjunctive normal form
Disjunctive normal form
In boolean logic, a disjunctive normal form is a standardization of a logical formula which is a disjunction of conjunctive clauses. As a normal form, it is useful in automated theorem proving. A logical formula is considered to be in DNF if and only if it is a disjunction of one or more...
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
Probability theory is the branch of mathematics concerned with analysis of random phenomena. The central objects of probability theory are random variables, stochastic processes, and events: mathematical abstractions of non-deterministic events or measured quantities that may either be single...
.
Let us define the dual of any propositional operator P(p, q, ...) depending on elementary propositions p, q, ... to be the operator
defined byThis idea can be generalised to quantifiers, so for example the universal quantifier and existential quantifier are duals:
To relate these quantifier dualities to the De Morgan laws, set up a model
Model theory
In mathematics, model theory is the study of mathematical structures using tools from mathematical logic....
with some small number of elements in its domain D, such as
- D = {a, b, c}.
Then
and
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
Modal logic is a type of formal logic that extends classical propositional and predicate logic to include operators expressing modality. Modals — words that express modalities — qualify a statement. For example, the statement "John is happy" might be qualified by saying that John is...
, relating the box ("necessarily") and diamond ("possibly") operators:
In its application to the alethic modalities
Subjunctive possibility
Subjunctive possibility is the form of modality most frequently studied in modal logic...
of possibility and necessity, Aristotle
Aristotle
Aristotle was a Greek philosopher and polymath, a student of Plato and teacher of Alexander the Great. His writings cover many subjects, including physics, metaphysics, poetry, theater, music, logic, rhetoric, linguistics, politics, government, ethics, biology, and zoology...
observed this case, and in the case of normal modal logic
Normal modal logic
In logic, a normal modal logic is a set L of modal formulas such that L contains:* All propositional tautologies;* All instances of the Kripke schema: \Box\toand it is closed under:...
, the relationship of these modal operators to the quantification can be understood by setting up models using Kripke semantics
Kripke semantics
Kripke semantics is a formal semantics for non-classical logic systems created in the late 1950s and early 1960s by Saul Kripke. It was first made for modal logics, and later adapted to intuitionistic logic and other non-classical systems...
.
See also
- List of Boolean algebra topics
- IsomorphismIsomorphismIn abstract algebra, an isomorphism is a mapping between objects that shows a relationship between two properties or operations. If there exists an isomorphism between two structures, the two structures are said to be isomorphic. In a certain sense, isomorphic structures are...
(NOT operator as isomorphism between positive logic and negative logic)