|
In logic, De Morgan's laws or De Morgan's theorem are rules in formal logic relating pairs of dual logical operators in a systematic manner expressed in terms of negation. The relationship so induced is called De Morgan duality.
- not (P and Q) = (not P) or (not Q)
- not (P or Q) = (not P) and (not Q)
DeMorgan's laws are based on the equivalent truth-values of each pair of statements.
The law is named after Augustus De Morgan (1806–1871)[1] who introduced a formal version of the laws to classical propositional logic. De Morgan's formulation was influenced by algebraisation 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[2], DeMorgan is given credit for stating the laws formally and incorporating them in to the language of logic. DeMorgan's Laws can be proved easily, and may even seem trivial.[3] Nonetheless, these laws are helpful in making valid inferences in proofs and deductive arguments.
Mathematical formulation
In strict mathematical terms, the rule states that each of the following claims is logically equivalent to the one next to it and may be transformed from one to the other in either direction:
- Failed to parse (Missing texvc executable; please see math/README to configure.): \neg(p\vee q)\iff(\neg p)\wedge(\neg q)
- Failed to parse (Missing texvc executable; please see math/README to configure.): \neg(p\wedge q)\iff(\neg p)\vee(\neg q)
where:
- Failed to parse (Missing texvc executable; please see math/README to configure.): \neg
is the negation operator (NOT)
- Failed to parse (Missing texvc executable; please see math/README to configure.): \wedge
is the conjunction operator (AND)
- Failed to parse (Missing texvc executable; please see math/README to configure.): \vee
is the disjunction operator (OR)
Logical applications
DeMorgan'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 A or B is true, which is written as:
- Failed to parse (Missing texvc executable; please see math/README to configure.): \neg(A\vee B)
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:
- Failed to parse (Missing texvc executable; please see math/README to configure.): (\neg A)\wedge(\neg B)
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 would be false, also. However the negation of said disjunction would yield a true result that is logically equivalent to the original claim. Presented in English, this would follow the logic that "Since two things are false, it's also false that either of them are true."
Negation of a conjunction
The application of DeMorgan'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:
- Failed to parse (Missing texvc executable; please see math/README to configure.): \neg(A\wedge B)
In order for this claim to be true, either or both of A or B must be false, in that 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 "Either A is false or B is false", or "Either not A is true or not B is true".
- Failed to parse (Missing texvc executable; please see math/README to configure.): (\neg A)\vee(\neg B)
Presented in English, this would follow the logic that "Since it is false that two things together are true, at least one of them must be false."
Further explanation
In set theory and Boolean algebra the law is stated "Union and intersection interchange under complementation."[4] Or, in symbols:
- Failed to parse (Missing texvc executable; please see math/README to configure.): \overline{A \cap B}=\overline{A} \cup \overline{B}
- Failed to parse (Missing texvc executable; please see math/README to configure.): \overline{A \cup B}=\overline{A} \cap \overline{B}.
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 circuit design, where it is used to manipulate the types of logic gates, 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 change a complicated statement like IF ... AND (... OR ...) THEN ... into its opposite. 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 Failed to parse (Missing texvc executable; please see math/README to configure.): \mbox{P}^d
defined by
- Failed to parse (Missing texvc executable; please see math/README to configure.): \mbox{P}^d(p, q, ...) = \neg P(\neg p, \neg q, \dots).
This idea can be generalised to quantifiers, so for example the universal quantifier and existential quantifier are duals:
- Failed to parse (Missing texvc executable; please see math/README to configure.): \forall x \, P(x) \equiv \neg \exists x \, \neg P(x),
- Failed to parse (Missing texvc executable; please see math/README to configure.): \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
- Failed to parse (Missing texvc executable; please see math/README to configure.): \forall x \, P(x) \equiv P(a) \wedge P(b) \wedge P(c)
and
- Failed to parse (Missing texvc executable; please see math/README to configure.): \exists x \, P(x) \equiv P(a) \vee P(b) \vee P(c).\,
But, using De Morgan's laws,
- Failed to parse (Missing texvc executable; please see math/README to configure.): P(a) \wedge P(b) \wedge P(c) \equiv \neg (\neg P(a) \vee \neg P(b) \vee \neg P(c))
and
- Failed to parse (Missing texvc executable; please see math/README to configure.): P(a) \vee P(b) \vee P(c) \equiv \neg (\neg P(a) \wedge \neg P(b) \wedge \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:
- Failed to parse (Missing texvc executable; please see math/README to configure.): \Box p \equiv \neg \Diamond \neg p,
- Failed to parse (Missing texvc executable; please see math/README to configure.): \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 Electrical Engineering
In electrical engineering contexts, the negation operator can be written as an overline above the terms to be negated. Thus, electrical engineering students are often taught to remember DeMorgan's laws using the mnemonic "break the line, change the sign".[5]
References
- ^ DeMorgan’s Theorems at mtsu.edu
- ^ Bocheński's History of Formal Logic
- ^ Augustus DeMorgan (1806 -1871) by Robert H. Orr
- ^ Boolean Algebra By R. L. Goodstein. ISBN 0486458946
- ^ 2000 Solved Problems in Digital Electronics By S. P. Bali
See also
External links
de:De Morgansche Gesetze es:Leyes de De Morgan fr:Lois de De Morgan ko:드 모르간의 법칙 is:De Morgan reglan it:Teoremi di De Morgan he:כללי דה מורגן lt:Dualioji funkcija nl:Wetten van De Morgan ja:ド・モルガンの法則 pl:Prawa De Morgana pt:Teoremas de De Morgan ru:Законы де Моргана sk:De Morganove zákony fi:De Morganin lait sv:De Morgans lagar th:กฎเดอมอร์แกน vi:Luật De Morgan
| 
