 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2013/discrete-mathematics-probability-and-continuous-mathematics/1/c/i/solution

An algebraic way to prove the set identity is to show that

D = \overline{A} \cup \overline{B}

A \cap B

(A \cap B) \cap D = (A \cap B \cap \overline{A}) \cup (A \cap B \cap \overline{B}) = \emptyset,

and

(A \cap B) \cup D = (A \cup D) \cap (B \cup D) = U \cap U = U .

D, E

both complement

S

, then

D = D \cap (S \cup E) = D \cap E

, and similarly

E = D \cap E

. Consequently

\overline{A \cap B} = \overline{A} \cup \overline{B} .

 New to topics? Read the docs here!