De Morgan's laws

In propositional logic and boolean algebra, De Morgan's laws^[1][2][3] are a pair of transformation rules that are both valid rules of inference. 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 conjunction is the disjunction of the negations; and

the negation of a disjunction is the conjunction of the negations;

or

the complement of the union of two sets is the same as the intersection of their complements; and

the complement of the intersection of two sets is the same as the union of their complements.

In set theory and Boolean algebra, these are written formally as

${\displaystyle {\begin{aligned}{\overline {A\cup B}}&={\overline {A}}\cap {\overline {B}},\\{\overline {A\cap B}}&={\overline {A}}\cup {\overline {B}},\end{aligned}}}$

where

• A and B are sets,
• A is the complement of A,
• ∩ is the intersection, and
• ∪ is the union.

In formal language, the rules are written as

${\displaystyle \neg (P\land Q)\iff (\neg P)\lor (\neg Q)}$,

and

${\displaystyle \neg (P\lor Q)\iff (\neg P)\land (\neg Q),}$

where

• P and Q are propositions,
• ${\displaystyle \neg }$ is the negation logic operator (NOT),
• ${\displaystyle \land }$ is the conjunction logic operator (AND),
• ${\displaystyle \lor }$ is the disjunction logic operator (OR),
• ${\displaystyle \iff }$ is a metalogical symbol meaning "can be replaced in a logical proof with".

Applications of the rules include simplification of logical expressions in computer programs and digital circuit designs. De Morgan's laws are an example of a more general concept of mathematical duality.