What is the truth table for demorgan's law?

From Demorgan's law:

$(A \cup B)^c = A^c \cap B^c$

I constructed the truth table as follows:

$$\begin{array}{cccccc|cc} x\in A & x \in B & x \notin A & x \notin B & x \in A^c & x \in B^c & x\notin A \text{ or } x \notin B & x \in A^c \text{ and } x \in B^c & \\ \hline T & T & F & F & F & F & F & F & \\ T & F & F & T & F & T & T & F & \\ F & T & T & F & T & F & T & F & \\ F & F & T & T & T & T & T & T & \end{array}$$

Clearly I've made a mistake somewhere. What did I do wrong?

In my mind, $x \notin A$ is the same as saying $x \in A^c$. Is this wrong too?

EDIT:

I think $x \in (A \cup B)^c$ is equal to $x \notin A \text{ or } x \notin B$ because:

$\begin{array} {cc} x \in (A \cup B)^c &\Rightarrow & x \notin A \cup B ,\text{ by definition of set complement}\\ & \Rightarrow & x \notin A \text{ or } x \notin B, \text{ by definition of set union} \\\end{array}$

Did I wrongly apply the definition(s)?

How do I start from $x \in (A \cup B)^c$ and arrive at $x \notin A \text{ and } x \notin B$?

• Well formulated question - shows your attempt at resolution. In naive set theory, $x \notin A$ is the same as $x \in A^c$. – Tom Collinge Jul 1 '14 at 8:21
• $(A \cup B)^c$ corresponds to "$\text{not } (x \in A \text{ or } x \in B)$", not "$x \notin A \text{ or } x \notin B$". – Tunococ Jul 1 '14 at 8:35
• Why you do not read the answers below ? $x∈(A \cup B)^c$ is $x∉ A \cup B$, but this is not $x∉A$ or $x∉B$. If $x$ does not belong to the "union" of two sets $A$ and $B$, it is not included in $A$ nor in $B$. Thus we have $x∉A$ and $x∉B$. If $A$ is a set of cats and $B$ is a set of dogs, what means for a mouse to be $\notin A \cup B$ ? It means that it is not a cat nor a dog; i.e. mouse $\notin A$ and mouse $\notin B$. – Mauro ALLEGRANZA Jul 1 '14 at 10:16

This is essentially a rephrasing of Mauro's answer. But focusing on the exact spot in your derivation where you go wrong.

$x \notin A \cup B \Rightarrow x \notin A \text{ or } x \notin B, \text{ by definition of set union}$

This is false. The definition of set union does not use the $\notin$ relation.

A correct derivation can go;

$\begin{array} {cc} x \in (A \cup B)^c &\Rightarrow & x \notin A \cup B &,\text{ by definition of set complement}\\ &\Rightarrow & \text{not }(x\in (A \cup B))&, \text{ by definition of}\notin\\ &\Rightarrow & \text{not }(x\in A \text{ or } x \in B)&, \text{ by definition of set union} \\\end{array}$

• Thanks, your answer is really useful. How do you justify $x \notin A \text{ and } x \notin B$ from the last implication? Is it just "by logical equivalence" or are there more intervening steps? The solution to negating an 'or' statement that I've seen invokes Demorgan's law but in this case, I am trying to prove demorgan's law so I am not sure how to proceed further. – mauna Jul 1 '14 at 15:57
• @mauna De Morgan's laws for boolean algebra ($\neg(a\vee b)\rightarrow (\neg a)\wedge(\neg b)$). This only involve two propositions, so only four cases. It can be proven by inspection. – Taemyr Jul 2 '14 at 7:33

It is correct to say that :

$x \notin A$ is the same as saying $x \in A^c$.

But your mistake is that, the truth-table for :

$(A \cup B)^c$

must be entered for the rows :

$x \in A$ or $x \in B$

and then "complemented", i.e. exchanging $T$ with $F$ and vice versa. In this way, you will check that it coincide with that for $x \notin A$ and $x \notin B$ (i.e.$A^c \cap B^c$).

You have "calculated" : $x \notin A$ or $x \notin B$, which is : $A^c \cup B^c$, and this clearly does not "match" with : $A^c \cap B^c$.

Note

Set union is "equivalent" to disjunction (or) while set intersection is "equivalent" to conjunction (and) and complementation is like negation (not).

Thus, De Morgan's laws acts on set operators in the same way as in propositional logic or boolean algebra.

In propositional logic we have that :

$\lnot (P \land Q) \Leftrightarrow (\lnot P \lor \lnot Q)$

and :

$\lnot (P \lor Q) \Leftrightarrow (\lnot P \land \lnot Q)$.

These formulae can be easily translated into "set language" as :

$(A \cap B)^c = A^c \cup B^c$

and :

$(A \cup B)^c = A^c \cap B^c$.

Your problem is in equating $(A \cup B)^c$ with $x \notin A$ or $x \notin B$. It should be $x \notin A$ AND $x \notin B$, after which you will get correspondence in lines 2 and 3 in your truth table.

$A \cup B$ = $x \in A$ or $x \in B$

$(A \cup B)^c$ = not ($x \in A$ or $x \in B$ ) = $x \notin A$ AND $x \notin B$

You're just fine! The truth table for $x\in (A\cup B)^c$ is: $$\begin{array}{ccc|c} x\in A & x \in B & x \in A\cup B & x \in (A\cup B)^c \\ \hline T & T & T& F\\ T & F & T& F\\ F & T & T& F\\ F & F & F& T \end{array}$$

The truth table for $x\in A^c \cap B^c$ is:

$$\begin{array}{cccc|c} x\in A & x \in B & x \in A^c & x \in B^c & x\in A^c\wedge x\in B^c\\ \hline T & T & F& F & F\\ T & F & F& T & F\\ F & T & T& F & F\\ F & F & T& T & T \end{array}$$

So they are the same!

• You haven't explained where the OP has gone wrong. – jwg Jul 1 '14 at 14:07