De Morgan’s Laws

De Morgan’s laws are two fundamental equivalences in propositional logic and Boolean algebra: negating a conjunction produces a disjunction of negations, while negating a disjunction produces a conjunction of negations. They connect expressions involving “and,” “or,” and “not,” and have corresponding forms in set theory. Their name honors Augustus De Morgan, a nineteenth-century mathematician whose work contributed to the development of symbolic logic. (openstax.org)

Logical formulation

For propositions $P$ and $Q$, the laws are

Here $\neg$ denotes negation, $\land$ denotes conjunction, and $\lor$ denotes disjunction. The equivalence symbol means that both expressions have the same truth value under every assignment of truth values to their constituent propositions. The laws therefore permit replacement in either direction, not merely inference from left to right. (cs.cornell.edu)

The disjunction is inclusive: $P\lor Q$ is true when either proposition, or both, are true. It is not exclusive OR. Consequently, “not both” means that at least one proposition is false, whereas “neither” means that both are false. For example, negating “the door is locked and the window is closed” gives “the door is not locked or the window is not closed.” Negating the corresponding “or” statement gives “the door is not locked and the window is not closed.” (openstax.org)

Changing only the connective, or only negating the components, does not implement either law. The outer negation must be removed while each component is negated and conjunction and disjunction are exchanged. (openstax.org)

Verification and proof

In classical logic, a truth table provides a direct proof. There are four possible assignments to two propositions:

The matching columns establish both equivalences. Expressed as biconditionals, the laws are tautologies: they are true for every possible assignment, regardless of what $P$ and $Q$ describe. (openstax.org)

Repeated application extends the laws to any finite list of propositions. Thus, negating “$P_1$ and … and $P_n$” yields “not $P_1$ or … or not $P_n$.” Nested expressions can likewise be transformed one connective at a time; the grouping determines which subexpressions are negated at each step. (interactivetextbooks.tudelft.nl)

Set-theoretic form

For subsets $A$ and $B$ of a fixed universe $U$, let $A^c=U\setminus A$ denote the complement of $A$. The set versions are

The first states that being outside a union means being outside both sets. The second states that being outside an intersection means being outside at least one. The universe must remain fixed because complements are relative to it. (interactivetextbooks.tudelft.nl)

These identities follow by considering an arbitrary element $x\in U$. Membership in a union corresponds to disjunction, membership in an intersection corresponds to conjunction, and membership in a complement corresponds to negation. Applying the logical laws therefore proves equality of the relevant sets. (interactivetextbooks.tudelft.nl)

Quantifiers

In first-order logic, related equivalences exchange universal and existential quantification:

Negating “every object has property $P$” asserts the existence of a counterexample, not that every object lacks the property. Negating “some object has property $P$” asserts that no object has it. The domain of quantification remains unchanged during these transformations. (web.sas.upenn.edu)

For instance, “not every integer is even” becomes “there exists an integer that is not even.” With several quantifiers, negation moves inward successively, exchanging each universal quantifier with an existential quantifier and vice versa without reversing their order. (inf.ed.ac.uk)

Computational applications

In computer science, De Morgan’s laws help transform formulas into negation normal form, where negations occur only immediately before atomic propositions. After other connectives have been eliminated, repeated application of the laws and double-negation elimination pushes negations inward. This is a preparatory step in converting formulas to conjunctive normal form. (comp.nus.edu.sg)

In digital electronics, the laws give equivalent descriptions of logic gates. A NAND operation is equivalent to OR applied to inverted inputs; a NOR operation is equivalent to AND applied to inverted inputs. These equivalences allow circuit designers to exchange gate forms and relocate inversions while preserving the Boolean function computed by the circuit. (ocw.mit.edu)

Limits beyond classical logic

The two laws do not have identical status in intuitionistic logic. The equivalence

remains valid, as does the implication

However, $\neg(P\land Q)\rightarrow(\neg P\lor\neg Q)$ is not generally derivable. Constructively, a proof that $P$ and $Q$ cannot both hold need not supply a proof identifying either one as false. Classical principles such as the law of excluded middle restore this missing direction; ordinary two-valued truth-table verification does not establish its intuitionistic validity. (cs.cornell.edu)