HOME

TheInfoList



OR:

In
propositional logic Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions (which can be true or false) and relations b ...
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 variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas i ...
, De Morgan's laws, also known as De Morgan's theorem, are a pair of transformation rules that are both valid
rules of inference In the philosophy of logic, a rule of inference, inference rule or transformation rule is a logical form consisting of a function which takes premises, analyzes their syntax, and returns a conclusion (or conclusions). For example, the rule of ...
. 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 disjunction is the conjunction of the negations * The negation of a conjunction is the disjunction of the negations or * The
complement A complement is something that completes something else. Complement may refer specifically to: The arts * Complement (music), an interval that, when added to another, spans an octave ** Aggregate complementation, the separation of pitch-clas ...
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 is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor S ...
" meaning ''at least'' one of A or B rather than an "
exclusive or Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false). It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , ...
" that means ''exactly'' one of A or B. In
set theory Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly conce ...
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 variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas i ...
, these are written formally as :\begin \overline &= \overline \cap \overline, \\ \overline &= \overline \cup \overline, \end where * A and B are sets, * \overline is the complement of A, * \cap is the intersection, and * \cup is the
union Union commonly refers to: * Trade union, an organization of workers * Union (set theory), in mathematics, a fundamental operation on sets Union may also refer to: Arts and entertainment Music * Union (band), an American rock group ** ''Un ...
. In
formal language In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of sy ...
, the rules are written as :\neg(P\lor Q)\iff(\neg P)\land(\neg Q), and :\neg(P\land Q)\iff(\neg P)\lor(\neg Q) where * ''P'' and ''Q are propositions,'' * \neg is the negation logic operator (NOT), * \land is the conjunction logic operator (AND), * \lor is the disjunction logic operator (OR), * \iff is a
metalogic Metalogic is the study of the metatheory of logic. Whereas ''logic'' studies how logical systems can be used to construct valid and sound arguments, metalogic studies the properties of logical systems.Harry GenslerIntroduction to Logic Routledge, ...
al symbol meaning "can be replaced in a logical proof with". 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 execute. Computer programs are one component of software, which also includes documentation and other intangible components. A computer program ...
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: :\neg(P \land Q) \vdash (\neg P \lor \neg Q), and :(\neg P \lor \neg Q) \vdash \neg(P \land Q). The ''negation of disjunction'' rule may be written as: :\neg(P \lor Q) \vdash (\neg P \land \neg Q), and :(\neg P \land \neg Q) \vdash \neg(P \lor Q). In rule form: ''negation of conjunction'' :\frac :\frac and ''negation of disjunction'' :\frac :\frac and expressed as a truth-functional tautology or
theorem In mathematics, a theorem is a statement that has been proved, or can be proved. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to establish that the theorem is a logical consequence of t ...
of propositional logic: :\begin \neg (P \land Q) &\to (\neg P \lor \neg Q), \\ (\neg P \lor \neg Q) &\to \neg (P \land Q), \\ \neg (P \lor Q) &\to (\neg P \land \neg Q), \\ (\neg P \land \neg Q) &\to \neg (P \lor Q), \end where P and Q are propositions expressed in some formal system.


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: :\begin (P \land Q) &\Longleftrightarrow \neg (\neg P \lor \neg Q), \\ (P \lor Q) &\Longleftrightarrow \neg (\neg P \land \neg Q). \end This emphasizes the need to invert both the inputs and the output, as well as change the operator when doing a substitution. The laws have an important gap to the (\neg(\neg p) \iff p) double negation law. \mathbb, to become a formal logic system: \ p, q, r, ...., \emptyset \in \mathbb\ sequence reports symbols that are defined well formed at first order. The same system has those conjunctions: C_:x\ , \ x \in set :: \. Obviously, C_ = set, \ x \in C_ is valid knowledge, then there is at least one x conjunction, which -T number —in the truth table, basic proposition of x— is equal to atomic existence context of x, of course according to the \forall x:(\mathbb\vDash \forall c \subsetneq C_, \ x\in c) knowledge. We regarded the equivalence theory, the logic does. At this point, De Morgan Laws show effect that is upward or downward, the atomic context of x.


Set theory and Boolean algebra

In set theory 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 variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas i ...
, it is often stated as "union and intersection interchange under complementation", which can be formally expressed as: :\begin \overline &= \overline \cap \overline, \\ \overline &= \overline \cup \overline, \end where: * \overline is the negation of A, the
overline An overline, overscore, or overbar, is a typographical feature of a horizontal line drawn immediately above the text. In old mathematical notation, an overline was called a '' vinculum'', a notation for grouping symbols which is expressed in m ...
being written above the terms to be negated, * \cap is the intersection operator (AND), * \cup is the
union Union commonly refers to: * Trade union, an organization of workers * Union (set theory), in mathematics, a fundamental operation on sets Union may also refer to: Arts and entertainment Music * Union (band), an American rock group ** ''Un ...
operator (OR).


Unions and intersections of any number of sets

The generalized form is : \begin \overline &\equiv \bigcup_ \overline, \\ \overline &\equiv \bigcap_ \overline, \end 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, or memory device, is any learning technique that aids information retention or retrieval (remembering) in the human memory for better understanding. Mnemonics make use of elaborative encoding, retrieval cues, and imag ...
"break the line, change the sign".


Engineering

In
electrical Electricity is the set of physical phenomena associated with the presence and motion of matter that has a property of electric charge. Electricity is related to magnetism, both being part of the phenomenon of electromagnetism, as described ...
and computer engineering, De Morgan's laws are commonly written as: : \overline \equiv \overline + \overline and : \overline \equiv \overline \cdot \overline , where: * \cdot 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 return the same set of documents (Documents 1, 2, 4): :Search C: NOT (cats AND dogs), :Search D: (NOT cats) OR (NOT dogs).


History

The laws are named after Augustus De Morgan (1806–1871), who introduced a formal version of the laws to classical
propositional logic Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions (which can be true or false) and relations b ...
. De Morgan's formulation was influenced by 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 ...
, which later cemented De Morgan's claim to the find. Nevertheless, a similar observation was made by
Aristotle Aristotle (; grc-gre, Ἀριστοτέλης ''Aristotélēs'', ; 384–322 BC) was a Greek philosopher and polymath during the Classical period in Ancient Greece. Taught by Plato, he was the founder of the Peripatetic school of ph ...
, and was known to Greek and Medieval logicians. For example, in the 14th century,
William of Ockham William of Ockham, OFM (; also Occam, from la, Gulielmus Occamus; 1287 – 10 April 1347) was an English Franciscan friar, scholastic philosopher, apologist, and Catholic theologian, who is believed to have been born in Ockham, a small vil ...
wrote down the words that would result by reading the laws out.
Jean Buridan Jean Buridan (; Latin: ''Johannes Buridanus''; – ) was an influential 14th-century French philosopher. Buridan was a teacher in the faculty of arts at the University of Paris for his entire career who focused in particular on logic and the wor ...
, in his ''Summulae de Dialectica'', 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.


Informal proof

De Morgan's theorem may be applied to the negation of a
disjunction In logic, disjunction is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor S ...
or the negation of a
conjunction Conjunction may refer to: * Conjunction (grammar), a part of speech * Logical conjunction, a mathematical operator ** Conjunction introduction, a rule of inference of propositional logic * Conjunction (astronomy), in which two astronomical bodies ...
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: :\neg(A\lor B). In that it has been established that ''neither'' A nor B is true, then it must follow that both A is not true
and or AND may refer to: Logic, grammar, and computing * Conjunction (grammar), connecting two words, phrases, or clauses * Logical conjunction in mathematical logic, notated as "∧", "⋅", "&", or simple juxtaposition * Bitwise AND, a boolea ...
B is not true, which may be written directly as: :(\neg A)\wedge(\neg B). 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: :\neg(A\land B). 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, :(\neg A)\lor(\neg B). Presented in English, this follows the logic that "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.


Formal proof

Here we use A^\complementto denote the complement of A. The proof that (A\cap B)^\complement = A^\complement \cup B^\complement is completed in 2 steps by proving both (A\cap B)^\complement \subseteq A^\complement \cup B^\complement and A^\complement \cup B^\complement \subseteq (A\cap B)^\complement.


Part 1

Let x \in (A \cap B)^\complement. Then, x \not\in A \cap B. Because A \cap B = \, it must be the case that x \not\in A or x \not\in B. If x \not\in A, then x \in A^\complement, so x \in A^\complement \cup B^\complement. Similarly, if x \not\in B, then x \in B^\complement, so x \in A^\complement\cup B^\complement. Thus, \forall x\Big( x \in (A\cap B)^\complement \implies x \in A^\complement \cup B^\complement\Big); that is, (A\cap B)^\complement \subseteq A^\complement \cup B^\complement.


Part 2

To prove the reverse direction, let x \in A^\complement \cup B^\complement, and for contradiction assume x \not\in (A\cap B)^\complement. Under that assumption, it must be the case that x \in A\cap B, so it follows that x \in A and x \in B, and thus x \not\in A^\complement and x \not\in B^\complement. However, that means x \not\in A^\complement \cup B^\complement, in contradiction to the hypothesis that x \in A^\complement \cup B^\complement, therefore, the assumption x \not\in (A\cap B)^\complement must not be the case, meaning that x \in (A\cap B)^\complement. Hence, \forall x\Big( x \in A^\complement \cup B^\complement \implies x \in (A\cap B)^\complement\Big), that is, A^\complement \cup B^\complement \subseteq (A\cap B)^\complement.


Conclusion

If A^\complement \cup B^\complement \subseteq (A\cap B)^\complement ''and'' (A \cap B)^\complement \subseteq A^\complement \cup B^\complement, then (A\cap B)^\complement = A^\complement \cup B^\complement; this concludes the proof of De Morgan's law. The other De Morgan's law, (A \cup B)^\complement = A^\complement \cap B^\complement, 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, namely the existence of
negation normal form In mathematical logic, a formula is in negation normal form (NNF) if the negation operator (\lnot, ) is only applied to variables and the only other allowed Boolean operators are conjunction (\land, ) and disjunction (\lor, ). Negation normal for ...
s: 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 needed to find the
conjunctive normal form In Boolean logic, 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. As a cano ...
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 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 expressing it through a set ...
. Let one define the dual of any propositional operator P(''p'', ''q'', ...) depending on elementary propositions ''p'', ''q'', ... to be the operator \mbox^d defined by :\mbox^d(p, q, ...) = \neg P(\neg p, \neg q, \dots).


Extension to predicate and modal logic

This duality can be generalised to quantifiers, so for example the universal quantifier and
existential quantifier In predicate logic, an existential quantification is a type of quantifier, a logical constant which is interpreted as "there exists", "there is at least one", or "for some". It is usually denoted by the logical operator symbol ∃, which, w ...
are duals: : \forall x \, P(x) \equiv \neg \exists x \, \neg P(x) : \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 A model is an informative representation of an object, person or system. The term originally denoted the plans of a building in late 16th-century English, and derived via French and Italian ultimately from Latin ''modulus'', a measure. Models c ...
with some small number of elements in its domain ''D'', such as :''D'' = . Then : \forall x \, P(x) \equiv P(a) \land P(b) \land P(c) and : \exists x \, P(x) \equiv P(a) \lor P(b) \lor P(c). But, using De Morgan's laws, : P(a) \land P(b) \land P(c) \equiv \neg (\neg P(a) \lor \neg P(b) \lor \neg P(c)) and : P(a) \lor P(b) \lor P(c) \equiv \neg (\neg P(a) \land \neg P(b) \land \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: : \Box p \equiv \neg \Diamond \neg p, : \Diamond p \equiv \neg \Box \neg p. In its application to the
alethic modalities Alethic modality (from Greek ἀλήθεια = 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 associated ...
of possibility and necessity,
Aristotle Aristotle (; grc-gre, Ἀριστοτέλης ''Aristotélēs'', ; 384–322 BC) was a Greek philosopher and polymath during the Classical period in Ancient Greece. Taught by Plato, he was the founder of the Peripatetic school of ph ...
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 tautologies; * All instances of the Kripke schema: \Box(A\to B)\to(\Box A\to\Box B) and it is closed under: * Detachment rule (''modus po ...
, 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é Jo ...
.


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 :\neg(P\lor Q)\iff(\neg P)\land(\neg Q), and :(P\lor Q)\rightarrow \neg ((\neg P)\land(\neg Q)), :(P\land Q)\rightarrow \neg ((\neg P)\lor(\neg Q)), :(\neg P)\lor(\neg Q) \rightarrow \neg(P\land Q) while the converse of the last implication does not hold in pure intuitionistic logic and would be equivalent to the law of the weak excluded middle :\neg P \lor \neg \neg P which 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 l ...
. This remains true if negation \neg P is replaced by implication P \rightarrow C for some arbitrary constant predicate C, meaning that the above laws are still true in
minimal logic Minimal logic, or minimal calculus, is a symbolic logic system originally developed by Ingebrigt Johansson. It is an intuitionistic and paraconsistent logic, that rejects both the law of the excluded middle as well as the principle of explosion ...
. Similarly, the quantifier laws: : \forall x \, \neg P(x) \iff \neg \exists x \,P(x) and : \forall x \, P(x) \rightarrow \neg \exists x \, \neg P(x) : \exists x \, P(x) \rightarrow \neg \forall x \, \neg P(x) : \exists x \, \neg P(x) \rightarrow \neg \forall x \, P(x) are tautologies even in minimal logic with negation replaced with implying a fixed Q, while the converse of the last law does not have to be true in general.


In computer engineering

De Morgan's laws are widely used in computer engineering and digital logic for the purpose of simplifying circuit designs.


See also

*
Isomorphism In mathematics, an isomorphism is a structure-preserving mapping 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 them. The word i ...
– NOT operator as isomorphism between positive logic and negative logic *
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 * Prop ...
*
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


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