Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Discrete mathematics, continuous mathematics and probability (resit) / 1 / a

Write $C^c=\mathcal{U}\setminus C$. The rules for set difference, set intersection, and complement of a set giveThe second step is De Morgan's laws; the third distributes set intersection over set union. The fourth uses $A\cap A^c=\varnothing$.

Using set difference as intersection with a complement of a set, then De Morgan's laws and distribution, givesFor the third equality, expand the two set unions: the terms $A\cap C^c$ and $A\cap B$ are absorbed by $A$, and $A\cap A=A$. This proves the required identity entirely by set algebra.