De Morgan's laws Guide, Meaning , Facts, Information and Description
In
logic,
De Morgan's laws (or De Morgan's theorem), named for nineteenth century logician and mathematician
Augustus De Morgan, are the two rules of
propositional logic,
boolean algebra and
set theory
- not (P and Q) = (not P) or (not Q)
- not (P or Q) = (not P) and (not Q)
which allow us to move a negation over a conjunction or a disjunction.
In formal logic the laws are usually written
and in set theory
Common uses of De Morgan's rules are in
digital circuit design, where it is used to manipulate the types of logic gates, and in formal logic, where it is one of the rules used to transform logical formulae into
negation normal form, a prerequisite for
conjunctive or
disjunctive normal form. 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.
Each propositional expression P(p, q, ...) depending on elementary propositions p, q, ... has a De Morgan dual in which each elementary proposition is replaced by its negation and conjunction and disjunction are interchanged. It can be written as
This idea can be generalised to include the
universal and existential quantifiers in classical logic as De Morgan duals, as follows:
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
-
and
- .
But, using De Morgan's laws,
-
and
-
verifying the quantifier dualities in the model.
Then, the quantifier dualities can be extended further to modal logic, relating the necessity and possibility operators:
- ,
- .
The relationship of these modal operators to the quantification can be understood by setting up models using
Kripke semantics.
See also
This is an Article on De Morgan's laws. Page Contains Information, Facts Details or Explanation Guide About De Morgan's laws
