$\begingroup$

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$?

$\endgroup$ 3

4 Answers

$\begingroup$

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$.

$\endgroup$ $\begingroup$

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$

$\endgroup$ $\begingroup$

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}$

$\endgroup$ 2 $\begingroup$

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!

$\endgroup$ 1

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy