De Morgan's laws

related topics
{math, number, function}
{theory, work, human}
{law, state, case}
{system, computer, user}
{acid, form, water}

In formal logic, De Morgan's laws are rules relating the logical operators "and" and "or" in terms of each other via negation, namely:

Contents

Formal definition

In propositional calculus form:

where:

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

where:

  • A is the negation of A, the overline is written above the terms to be negated
  • ∩ is the intersection operator (AND)
  • ∪ is the union 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 "break the line, change the sign".[2]

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.

Full article ▸

related documents
Theory of computation
Spectrum of a ring
Product topology
Mean value theorem
Discriminant
Least common multiple
Differential topology
Isomorphism theorem
Diffeomorphism
Automata theory
Golden ratio base
Tree (data structure)
Borel algebra
Algebraic topology
Graftal
Knight's tour
Monotonic function
Generalized Riemann hypothesis
Special linear group
Operator overloading
Quasigroup
Conjunctive normal form
Axiom of regularity
Cauchy-Riemann equations
Column space
Cotangent space
Linear subspace
Monotone convergence theorem
NaN
Cartesian product