# de morgan law $A\setminus (B \cap C) = (A\setminus B) \cup (A\setminus C)$

First part :

I want to prove the following De Morgan's law : ref.(dfeuer)

$$A\setminus (B \cap C) = (A\setminus B) \cup (A\setminus C)$$

Second part:

Prove that $$(A\setminus B) \cup (A\setminus C) = A\setminus (B \cap C)$$

Proof:

Let $$y\in (A\setminus B) \cup (A\setminus C)$$

$$(A\setminus B) \cup (A\setminus C) = (y \in A\; \land y \not\in B\;) \vee (y \in A\; \land y \not\in C\;)$$

$$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;= y \in A\ \land ( y \not\in B\; \vee \; y \not\in C )$$

$$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;= y \in A \land (\lnot ( y\in B) \lor \lnot( y\in C) )$$

According to De-Morgan's theorem :

$$\lnot( B \land C) \Longleftrightarrow (\lnot B \lor \lnot C)$$ thus

$$y \in A \land (\lnot ( y\in B) \lor \lnot( y\in C) ) = y \in A \land y \not\in (B \land C)$$

We can conclude that $$(A\setminus B) \cup (A\setminus C) = A\setminus (B \cap C)$$

• That is not very clear English. Perhaps you could parenthesize it or something? – dfeuer Dec 7 '13 at 23:49