In propositional logic and boolean algebra, De Morgan's laws are a pair of transformation rules that are both valid rules of inference. 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 conjunction is the disjunction of the negations.
The negation of a disjunction is the conjunction of the negations.
The rules can be expressed in formal language with two propositions P and Q as:
where:
- ¬ is the negation operator (NOT)
- is the conjunction operator (AND)
- is the disjunction operator (OR)
- ⇔ is a metalogical symbol meaning "can be replaced in a logical proof with"
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.
Read more about De Morgan's Laws: Formal Notation, History, Informal Proof, Formal Proof, Extensions
Famous quotes containing the words morgan and/or laws:
“The best protection parents can have against the nightmare of a daycare arrangement where someone might hurt their child is to choose a place that encourages parents to drop in at any time and that facilitates communication among parents using the program. If parents are free to drop in and if they exercise this right, it is not likely that adults in that place are behaving in ways that harm children.”
—Gwen Morgan (20th century)
“The tide which, after our former relaxed government, took a violent course towards the opposite extreme, and seemed ready to hang every thing round with the tassils and baubles of monarchy, is now getting back as we hope to a just mean, a government of laws addressed to the reason of the people, and not to their weaknesses.”
—Thomas Jefferson (1743–1826)