Editing De Morgan's laws (section)

==Formal notation==
The ''negation of conjunction'' rule may be written in [[sequent]] notation:
:<math>\begin{align}
\neg(P \land Q) &\vdash (\neg P \lor \neg Q), \text{and} \\
(\neg P \lor \neg Q) &\vdash \neg(P \land Q).
\end{align}</math>

The ''negation of disjunction'' rule may be written as:
:<math>\begin{align}
\neg(P \lor Q) &\vdash (\neg P \land \neg Q), \text{and} \\
(\neg P \land \neg Q) &\vdash \neg(P \lor Q).
\end{align}</math>

In [[Rule of inference|rule form]]: ''negation of conjunction''
<div style="margin-left: 2em">
<math>
\frac{\neg (P \land Q)}{\therefore \neg P \lor \neg Q}
\qquad
\frac{\neg P \lor \neg Q}{\therefore \neg (P \land Q)}
</math>
</div>

and ''negation of disjunction''
<div style="margin-left: 2em">
<math>
\frac{\neg (P \lor Q)}{\therefore \neg P \land \neg Q}
\qquad
\frac{\neg P \land \neg Q}{\therefore \neg (P \lor Q)}
</math>
</div>

and expressed as truth-functional [[Tautology (logic)|tautologies]] or [[theorem]]s of propositional logic:

:<math>\begin{align}
  \neg (P \land Q) &\leftrightarrow (\neg P \lor \neg Q), \\
   \neg (P \lor Q) &\leftrightarrow (\neg P \land \neg Q). \\
\end{align}</math>

where <math>P</math> and <math>Q</math> are propositions expressed in some formal system.

The '''generalized De Morgan's laws''' provide an equivalence for negating a conjunction or disjunction involving multiple terms.<br />For a set of propositions <math>P_1, P_2, \dots,P_n</math>, the generalized De Morgan's Laws are as follows:
:<math>\begin{align}
\lnot(P_1 \land P_2 \land \dots \land P_n) \leftrightarrow \lnot P_1 \lor \lnot P_2 \lor \ldots \lor \lnot P_n \\
\lnot(P_1 \lor P_2 \lor \dots \lor P_n) \leftrightarrow \lnot P_1 \land \lnot P_2 \land \ldots \land \lnot P_n
\end{align}</math>

These laws generalize De Morgan's original laws for negating conjunctions and disjunctions.

===Substitution form===
De Morgan's laws are normally shown in the compact form above, with the negation of the output on the left and negation of the inputs on the right. A clearer form for substitution can be stated as:

:<math>\begin{align}
(P \land Q) &\Longleftrightarrow \neg (\neg P \lor \neg Q), \\
(P \lor Q) &\Longleftrightarrow \neg (\neg P \land \neg Q).
\end{align}</math>

This emphasizes the need to invert both the inputs and the output, as well as change the operator when doing a substitution.

===Set theory===
In set theory, it is often stated as "union and intersection interchange under complementation",<ref name="r l goodstein">''Boolean Algebra'' by R. L. Goodstein. {{ISBN|0-486-45894-6}}</ref> which can be formally expressed as:
:<math>\begin{align}
  \overline{A \cup B} &= \overline{A} \cap \overline{B}, \\
  \overline{A \cap B} &= \overline{A} \cup \overline{B},
\end{align}</math>

where:
* <math>\overline{A}</math> is the negation of <math>A</math>, the [[overline]] being written above the terms to be negated,
* <math>\cap</math> is the [[Intersection (set theory)|intersection]] operator (AND),
* <math>\cup</math> is the [[Union (set theory)|union]] operator (OR).

==== Unions and intersections of any number of sets ====
The generalized form is
: <math>\begin{align}
  \overline{\bigcap_{i \in I} A_{i}} &\equiv \bigcup_{i \in I} \overline{A_{i}}, \\
  \overline{\bigcup_{i \in I} A_{i}} &\equiv \bigcap_{i \in I} \overline{A_{i}},
\end{align}</math>

where {{math|''I''}} is some, possibly countably or uncountably infinite, indexing set.

In set notation, De Morgan's laws can be remembered using the [[mnemonic]] "break the line, change the sign".<ref>[https://books.google.com/books?id=NdAjEDP5mDsC&pg=PA81 ''2000 Solved Problems in Digital Electronics''] by S. P. Bali</ref>

===Boolean algebra===

In Boolean algebra, similarly, this law which can be formally expressed as:
:<math>\begin{align}
  \overline{A \land B} &= \overline{A} \lor \overline{B}, \\
  \overline{A \lor B} &= \overline{A} \land \overline{B},
\end{align}</math>

where:
* <math>\overline{A}</math> is the negation of <math>A</math>, the [[overline]] being written above the terms to be negated,
* <math>\land</math> is the [[logical conjunction]] operator (AND),
* <math>\lor</math> is the [[logical disjunction]] operator (OR).

which can be generalized to

: <math>\begin{align}
  \overline{A_1 \land A_2 \land \ldots \land A_{n}} = \overline{A_1} \lor \overline{A_2} \lor \ldots \lor \overline{A_{n}}, \\
  \overline{A_1 \lor A_2 \lor \ldots \lor A_{n}} = \overline{A_1} \land \overline{A_2} \land \ldots \land \overline{A_{n}}.
\end{align}</math>
===Engineering===
In [[Electrical engineering|electrical]] and [[computer engineering]], De Morgan's laws are commonly written as:
: <math>\overline{(A \cdot B)} \equiv (\overline {A} + \overline {B})</math>

and
: <math>\overline{(A + B)} \equiv (\overline {A} \cdot \overline {B}),</math>

where:
* <math> \cdot </math> is the logical AND,
* <math>+</math> is the logical OR,
* the {{overline|overbar}} is the logical NOT of what is underneath the overbar.

===Text searching===
De Morgan's laws commonly apply to text searching using Boolean operators AND, OR, and NOT. Consider a set of documents containing the words "cats" and "dogs". De Morgan's laws hold that these two searches will return the same set of documents:

:Search A: NOT (cats OR dogs)
:Search B: (NOT cats) AND (NOT dogs)

The corpus of documents containing "cats" or "dogs" can be represented by four documents:
:Document 1: Contains only the word "cats".
:Document 2: Contains only "dogs".
:Document 3: Contains both "cats" and "dogs".
:Document 4: Contains neither "cats" nor "dogs".

To evaluate Search A, clearly the search "(cats OR dogs)" will hit on Documents 1, 2, and 3. So the negation of that search (which is Search A) will hit everything else, which is Document 4.

Evaluating Search B, the search "(NOT cats)" will hit on documents that do not contain "cats", which is Documents 2 and 4. Similarly the search "(NOT dogs)" will hit on Documents 1 and 4. Applying the AND operator to these two searches (which is Search B) will hit on the documents that are common to these two searches, which is Document 4.

A similar evaluation can be applied to show that the following two searches will both return Documents 1, 2, and 4:
:Search C: NOT (cats AND dogs),
:Search D: (NOT cats) OR (NOT dogs).