De Morgan's laws


De Morgan's laws

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:

\overline{A \cdot B} = \overline {A} + \overline {B}
\overline{A + B} = \overline {A} \cdot \overline {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 conjunction is the disjunction of the negations." and
"The negation of a disjunction is the conjunction of the negations."

Contents

Formal definition

In propositional calculus form:

\neg(p\lor q)\iff(\neg p)\land(\neg q)
\neg(p\land q)\iff(\neg p)\lor(\neg q)

where:

In set theory and Boolean algebra, it is often stated as "Union and intersection interchange under complementation."[1]:

\overline{A \cup B}=\overline{A} \cap \overline{B}
\overline{A \cap B}=\overline{A} \cup \overline{B}

where:

  • A is the negation of A, the overline being written above the terms to be negated
  • ∩ is the intersection operator (AND)
  • ∪ is the union operator (OR)

The generalized form is:

\overline{\bigcap_{i \in I} A_{i}}=\bigcup_{i \in I} \overline{A_{i}}
\overline{\bigcup_{i \in I} A_{i}}=\bigcap_{i \in I} \overline{A_{i}}

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".[2]

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:

A \cdot B = \overline{ \overline A + \overline B }
A + B = \overline{ \overline {A} \cdot \overline {B} }

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 Morgan (1806–1871)[3] 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 [4] (in the 14th century William of Ockham wrote down the words that would result by reading the laws out[5]), 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.[6] 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 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 is true 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 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:

(\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 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:

\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. 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".

(\neg A)\lor(\neg B)

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."

Formal proof

By truth table

The laws may be proven directly using truth tables; "1" represents true, "0" represents false.

First we prove: ¬(pq) ⇔ (¬p) ∧ (¬q).

p q pq ¬(pq) ¬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 ¬(pq) ⇔ (¬p) ∨ (¬q) by the same method:

p q pq ¬(pq) ¬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 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 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 Pd defined by

\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:

 \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 with some small number of elements in its domain D, such as

D = {a, b, c}.

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 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.

See also

References

  1. ^ Boolean Algebra By R. L. Goodstein. ISBN 0486458946
  2. ^ 2000 Solved Problems in Digital Electronics By S. P. Bali
  3. ^ DeMorgan’s Theorems at mtsu.edu
  4. ^ Bocheński's History of Formal Logic
  5. ^ William of Ockham, Summa Logicae, part II, sections 32 & 33.
  6. ^ Augustus De Morgan (1806 -1871) by Robert H. Orr

External links


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • De Morgan's laws — The equivalences (i) not (A or B) if and only if not A and not B, and (ii) not (A and B), if and only if not A or not B, are known as De Morgan s laws, although De Morgan himself gave the equivalent statements in Boolean algebra . Each… …   Philosophy dictionary

  • De Morgan's laws — 1. Logic. two laws, one stating that the denial of the conjunction of a class of propositions is equivalent to the disjunction of the denials of a proposition, and the other stating that the denial of the disjunction of a class of propositions is …   Universalium

  • De Morgan's laws — 1. Logic. two laws, one stating that the denial of the conjunction of a class of propositions is equivalent to the disjunction of the denials of a proposition, and the other stating that the denial of the disjunction of a class of propositions is …   Useful english dictionary

  • Morgan Robertson — Morgan Andrew Robertson (September 30, 1861–March 24, 1915) was a well known American author of short stories and novels, and the self claimed inventor of the periscope. He is best known for his short novel Futility, first published in 1898. This …   Wikipedia

  • Morgan's Raid — Part of the American Civil War Date June 11 (1963 06 11) – July 26, 1863 ( …   Wikipedia

  • Morgan v. Hennigan — The case that defined the school busing controversy in Boston, Massachusetts during the 1970s was Morgan v. Hennigan. On 14 March 1972 the Boston chapter of the NAACP filed a class action lawsuit against the Boston School Committee on behalf of… …   Wikipedia

  • Morgan Creek Vineyards (Alabama) — Morgan Creek Vineyards Location Harpersville, Alabama, United States Coordinates 33°19′34″N 86° …   Wikipedia

  • Morgan Motor Company — Type Private Industry Motoring Founded 1910 Founder(s) H.F.S. Morgan …   Wikipedia

  • MORGAN (L. H.) — Considéré comme le «fondateur» de la science anthropologique, admiré par G. Bandelier, J. W. Powell, L. Fison, A. W. Howitt, pionniers à des titres divers de l’ethnographie américaine et australienne, loué par Marx et Engels pour avoir… …   Encyclopédie Universelle

  • Morgan Plus 8 — Manufacturer Morgan Motor Company Production 1968 2004 Assembly Malvern, Worcestershire, England …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.