De Morgan's Laws

De Morgan's law represented with logic gates

The de-morgan's laws (and often de-Morganist rules ) are two basic rules for logical statements. They were named after the mathematician Augustus De Morgan , although they were already known to the medieval logician Wilhelm von Ockham . They apply in all Boolean algebras . They are particularly important in propositional logic and set theory . In technology, they are important for creating interlocks and programs.

Laws

In logic they are :

not (a and b) is equivalent to ((not a) or (not b))

not (a or b) is equivalent to ((not a) and (not b))

In mathematics, one can find numerous different representations of the De Morgan laws of propositional logic :

{\ displaystyle {\ begin {matrix} \ neg {(a \ wedge b)} \ iff \ neg {a} \ vee \ neg {b} \\\ neg {(a \ vee b)} \ iff \ neg { a} \ wedge \ neg {b} \ end {matrix}}}

or with a different notation:

{\ displaystyle {\ begin {matrix} {\ overline {(a \ wedge b)}} \ iff {\ overline {a}} \ vee {\ overline {b}} \\ {\ overline {(a \ vee b )}} \ iff {\ overline {a}} \ wedge {\ overline {b}} \ end {matrix}}}

The validity of De Morgan's laws can be proven using truth tables .

Its equivalent in set theory is (where A is the complement of A , the symbol for the intersection of two sets and the symbol for the union of two sets): ${\ displaystyle \ cap}$ ${\ displaystyle \ cup}$

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

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

The rules can also be extended to link any number of elements. So for any finite, countable or non-countable index set I :

{\ displaystyle {\ overline {\ bigcap _ {i \ in I} A_ {i}}} = \ bigcup _ {i \ in I} {\ overline {A_ {i}}}}

and .

{\ displaystyle {\ overline {\ bigcup _ {i \ in I} A_ {i}}} = \ bigcap _ {i \ in I} {\ overline {A_ {i}}}}

Inferences

A conjunction (AND link) can be represented by three negations and a disjunction (NOT or OR links) with the help of De-Morgan's law :

{\ displaystyle a \ wedge b \ iff \ neg (\ neg {a} \ vee \ neg {b})}

Accordingly, a disjunction can be represented by three negations and a conjunction:

{\ displaystyle a \ vee b \ iff \ neg (\ neg {a} \ wedge \ neg {b})}

application

The de-morgan's laws have important applications in discrete mathematics , the electrical , the physics and computer science . In particular, the de-morgan's laws are in the design of digital circuits used to the types of logic used switching elements replaced with another or to save components.

Examples

Example from everyday life

Suppose a person likes to drink coffee: To express that he only drinks it black and without sugar, he can make the following statements:

If there is milk or sugar in it, then I will not drink the coffee.

Converted from de Morgan and counterposition :

When I drink the coffee, there is no milk or sugar in it.

Both statements are of equal value.

Example in set theory

It's supposed to be based on the relationship

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

the validity of De Morgan's rules are illustrated. There are two sets A and B, which are subsets of a superset Ω. The graph 1 shows the location of the quantities and its counter quantities A and B .

Figure 2 shows how it is formed. Figure 3 shows the complement to , and you can see that both sets are equal. ${\ displaystyle {\ overline {A}} \ cup {\ overline {B}}}$ ${\ displaystyle A \ cap B}$


Division of the superset into A and B.	${\ displaystyle {\ overline {A}} \ cup {\ overline {B}}}$	${\ displaystyle {\ overline {A \ cap B}}}$

One interpretation would be:
In an acceptance test, high-quality chef's knives are checked to see whether the cutting edge is free of defects (quantity A) and whether the cutting edge is properly anchored in the handle (quantity B). A knife is not accepted, if there is the amount A or the amount of B is one or two, that is, when at least one complaint is present: . The knife is accepted if it fulfills both requirements, that is, if it belongs to the crowd , that is, it is not accepted if it belongs to. ${\ displaystyle {\ overline {A}} \ cup {\ overline {B}}}$ ${\ displaystyle A \ cap B}$ ${\ displaystyle {\ overline {A \ cap B}}}$

Web links