De Morgan's Laws

Negating Membership in a Union or Intersection

The complement of a set contains the elements of a fixed universe that do not belong to that set. When the set is itself a union or an intersection, deciding which elements fail to belong requires careful attention to the logical meaning of “or” and “and.” De Morgan's laws state exactly how the complement interacts with these two operations.

Throughout this tutorial, let $U$ be a fixed universe, and let $A,B\subseteq U$. Complements are taken relative to this same $U$. Recall the membership characterizations of union and intersection: an object belongs to $A\cup B$ when it belongs to at least one of $A,B$, and it belongs to $A\cap B$ when it belongs to both. Also, $x\in A^c$ means $x\in U$ and $x\notin A$.

To be outside a union, an element must fail to belong to both sets: it must be outside $A$ and outside $B$. To be outside an intersection, an element need only fail one of the two membership conditions: it is outside $A$, or it is outside $B$, or both. These statements lead to the two identities $$ (A\cup B)^c=A^c\cap B^c, \qquad (A\cap B)^c=A^c\cup B^c. $$ The first law exchanges union for intersection under complementation. The second exchanges intersection for union.

Keep the negation attached to the whole membership condition. Not belonging to “$A$ or $B$” means belonging to neither. Not belonging to “$A$ and $B$” means failing at least one of the two requirements.

First Law: The Complement of a Union

An element of $A\cup B$ is in $A$ or in $B$, with “or” inclusive: it may be in either set or in both. Its complement therefore contains precisely the elements of $U$ that are in neither set. Membership in $A^c\cap B^c$ says just that: the element lies in $U$, is not in $A$, and is not in $B$.

Theorem (De Morgan's Law for a Union). Let $A,B\subseteq U$. Then $$ (A\cup B)^c=A^c\cap B^c. $$

Proof. Both sets in the claimed equality are subsets of $U$. Let $x$ be any object. By the definition of complement and the membership characterization of union, $$ \begin{aligned} x\in(A\cup B)^c &\Longleftrightarrow x\in U\text{ and }x\notin A\cup B\\ &\Longleftrightarrow x\in U\text{ and }(x\notin A\text{ and }x\notin B). \end{aligned} $$ Here the second equivalence follows because $x\in A\cup B$ means $x\in A$ or $x\in B$: its negation is that $x$ is in neither set. Since $A,B\subseteq U$, the condition $x\in U$ together with $x\notin A$ is equivalent to $x\in A^c$, and the condition $x\in U$ together with $x\notin B$ is equivalent to $x\in B^c$. Thus $$ x\in(A\cup B)^c \quad\Longleftrightarrow\quad x\in A^c\text{ and }x\in B^c \quad\Longleftrightarrow\quad x\in A^c\cap B^c. $$ This membership equivalence holds for every object $x$, so equality by double inclusion gives $(A\cup B)^c=A^c\cap B^c$. $\square$

Worked Example: Complementing a Union in a Finite Universe

Take $$ U=\{a,b,c,d,e,f,g\},\qquad A=\{a,c,e\},\qquad B=\{b,c,f\}. $$ Their union is $A\cup B=\{a,b,c,e,f\}$, so its complement relative to $U$ is $$ (A\cup B)^c=\{d,g\}. $$ Separately, the complements are $$ A^c=\{b,d,f,g\},\qquad B^c=\{a,d,e,g\}. $$ The elements common to these two complements are $d$ and $g$, and hence $$ A^c\cap B^c=\{d,g\}=(A\cup B)^c. $$ For instance, $d$ belongs to neither $A$ nor $B$, so it belongs to both complements. The element $c$, by contrast, belongs to both original sets and cannot belong to the complement of their union.

Second Law: The Complement of an Intersection

An element belongs to $A\cap B$ only when it belongs to both $A$ and $B$. To be outside this intersection, an element must fail at least one of those requirements. It may be outside $A$, outside $B$, or outside both. This is exactly the membership condition for $A^c\cup B^c$.

Theorem (De Morgan's Law for an Intersection). Let $A,B\subseteq U$. Then $$ (A\cap B)^c=A^c\cup B^c. $$

Proof. The sets $(A\cap B)^c$ and $A^c\cup B^c$ are both subsets of $U$. Let $x$ be any object. Using the membership characterization of intersection, $$ \begin{aligned} x\in(A\cap B)^c &\Longleftrightarrow x\in U\text{ and }x\notin A\cap B\\ &\Longleftrightarrow x\in U\text{ and }(x\notin A\text{ or }x\notin B). \end{aligned} $$ The last step holds because $x\in A\cap B$ means that both $x\in A$ and $x\in B$ hold; the negation of that conjunction is that at least one of them fails. As $A,B\subseteq U$, we can rewrite the condition as $$ (x\in U\text{ and }x\notin A) \text{ or } (x\in U\text{ and }x\notin B). $$ Indeed, in either alternative $x\in U$, so placing that condition in both alternatives does not change the statement. By the definition of complement, this is equivalent to $$ x\in A^c\text{ or }x\in B^c, $$ which in turn is equivalent to $x\in A^c\cup B^c$. The equivalence holds for every object $x$. Equality by double inclusion gives $(A\cap B)^c=A^c\cup B^c$. $\square$

Worked Example: Complementing an Intersection

Let $$ U=\{1,2,3,4,5,6,7,8\},\qquad A=\{1,2,4,7\},\qquad B=\{2,3,4,6\}. $$ The intersection consists of elements common to both sets: $$ A\cap B=\{2,4\}. $$ It follows that $$ (A\cap B)^c=\{1,3,5,6,7,8\}. $$ Now compute each complement relative to the same universe: $$ A^c=\{3,5,6,8\},\qquad B^c=\{1,5,7,8\}. $$ Their union is $$ A^c\cup B^c=\{1,3,5,6,7,8\}=(A\cap B)^c. $$ The element $1$ illustrates why the union appears on the right: $1$ is in $A$ but not $B$, so it fails the requirement of belonging to both sets and therefore belongs to the complement of $A\cap B$.

Applying the Laws to Set-Builder Descriptions

De Morgan's laws also give a systematic way to negate conditions that combine membership requirements. If a set is described by “$P$ or $Q$,” its complement consists of the elements for which neither $P$ nor $Q$ holds. If it is described by “$P$ and $Q$,” its complement consists of elements for which at least one condition fails. The candidate elements still come from the specified universe.

Worked Example: Negating Two Conditions on Integers

Let $U=\{-4,-3,-2,-1,0,1,2,3,4,5\}$, and define $$ A=\{x\in U:x<0\},\qquad B=\{x\in U:x\text{ is even}\}. $$ The set $A\cup B$ consists of integers in $U$ that are negative or even. Its complement consists of elements that are not negative and are not even. Within this universe, those are the positive odd integers: $$ (A\cup B)^c =\{x\in U:x\geq0\text{ and }x\text{ is odd}\} =\{1,3,5\}. $$ The first De Morgan law gives the same result by intersecting the separate complements. Here $$ A^c=\{0,1,2,3,4,5\},\qquad B^c=\{-3,-1,1,3,5\}, $$ so $$ A^c\cap B^c=\{1,3,5\}. $$ The restriction $x\in U$ remains in the description. For example, $7$ is nonnegative and odd, but it is not in this complement because $7\notin U$.

A Reliable Membership-Check Method

When an identity contains several set operations, it is easy to rely on the visual appearance of the symbols and lose track of the meaning. A dependable method is to choose an arbitrary object $x$, translate each set operation into its membership condition, and simplify the condition using the meanings of “and,” “or,” and “not.” If the resulting condition is equivalent to membership in the other side, the two sets are equal by the equality criterion established earlier in this course.

Fix the universe: identify $U$ and ensure all complements in the identity are relative to this same set.

Choose an arbitrary object: write what it means for $x$ to belong to one side of the proposed identity.

Translate operations: replace union by “or,” intersection by “and,” and complement by “in $U$ and not in.”

Negate carefully: the negation of “$P$ or $Q$” requires not $P$ and not $Q$; the negation of “$P$ and $Q$” requires not $P$ or not $Q$.

Translate back: match the simplified membership condition with the other set, then conclude equality.

Parentheses, Complements, and Common Errors

Parentheses determine which set is being complemented. In $(A\cup B)^c$, the complement applies to the entire union. By contrast, $A^c\cup B$ complements only $A$ before taking the union with $B$. These expressions generally describe different sets. The De Morgan law transforms the first expression into $A^c\cap B^c$; it does not turn it into $A^c\cup B$.

A frequent error is to change the operation but leave the original sets unchanged, writing $(A\cup B)^c=A^c\cup B^c$. The right-hand side of that expression contains elements outside at least one of $A$ and $B$, whereas the left-hand side contains elements outside both. The correct operation on the right is intersection.

The converse error occurs for intersections. The complement of $A\cap B$ is not $A^c\cap B^c$: that intersection would require an element to be outside both $A$ and $B$, even though being outside just one already prevents it from belonging to $A\cap B$. The correct right-hand operation is union.

The universe condition is essential to the notation. Both laws assume $A,B\subseteq U$, and every complement uses that $U$. If complements are taken relative to different universes, the expressions no longer refer to the same complement operation, so these identities cannot be applied without first specifying the universes.

Expression	Membership condition	Equivalent form
$(A\cup B)^c$	In $U$, not in $A$, and not in $B$	$A^c\cap B^c$
$(A\cap B)^c$	In $U$, not in $A$ or not in $B$	$A^c\cup B^c$
$A^c\cap B^c$	Outside both $A$ and $B$, within $U$	$(A\cup B)^c$
$A^c\cup B^c$	Outside at least one of $A$ and $B$, within $U$	$(A\cap B)^c$

Operation changes under a complement. A union inside the complement becomes an intersection outside it, and an intersection inside the complement becomes a union outside it. The sets involved and the universe remain the same.

In each question, assume that all sets are subsets of the stated universe and that complements are taken relative to that universe. Translate membership conditions before evaluating an identity.

Check Your Understanding

Let $U=\{a,b,c,d,e,f\}$, $A=\{a,c,e\}$, and $B=\{b,c,f\}$. Find $(A\cup B)^c$ and verify it by computing $A^c\cap B^c$.
For any $A,B\subseteq U$, state the expression equal to $(A\cap B)^c$.
Let $U=\{-3,-2,-1,0,1,2,3,4\}$. Describe the complement of $\{x\in U:x\leq0\text{ or }x=3\}$ using a condition and list its elements.
Explain in words why an element can belong to $(A\cap B)^c$ even if it belongs to $A$.
Which operation replaces $\cup$ in the identity for the complement of a union? Which operation replaces $\cap$ in the identity for the complement of an intersection?
Why must the complements on both sides of a De Morgan identity be taken relative to one fixed universe?

Expression	Membership condition	Equivalent form
\((A\cup B)^c\)	In \(U\), not in \(A\), and not in \(B\)	\(A^c\cap B^c\)
\((A\cap B)^c\)	In \(U\), not in \(A\) or not in \(B\)	\(A^c\cup B^c\)
\(A^c\cap B^c\)	Outside both \(A\) and \(B\), within \(U\)	\((A\cup B)^c\)
\(A^c\cup B^c\)	Outside at least one of \(A\) and \(B\), within \(U\)	\((A\cap B)^c\)

What You'll Learn