**This is an old revision of the document!**


Set Theory Identities

\begin{align} A \cup \overline{A} & = & \Omega \qquad & \mbox{Complementation law}\\ A \cap \overline{A} & = & \emptyset \qquad & \mbox{Exclusion law}\\ \\ A \cap \Omega & = & A \qquad & \mbox{Identity laws} \\ A \cup \emptyset& = & A \qquad & \\ \\ A \cup \Omega &= & \Omega \qquad & \mbox{Domination laws} \\ A \cap \emptyset & = & \emptyset \qquad & \\ \\ A \cup A & = & A \qquad & \mbox{Idempotent laws} \\ A \cap A & = & A \qquad & \\ \\ \overline{\left(\overline{A}\right)} & = & A \qquad & \mbox{Double Complement} \\ \\ A \cup B & = & B \cup A \qquad & \mbox{Commutative laws} \\ A \cap B & = & B \cap A \qquad & \\ \\ \left(A \cup B\right) \cup C & = & A \cup \left(B \cup C\right) \qquad & \mbox{Associative laws} \\ \left(A \cap B\right) \cap C & = & A \cap \left(B \cap C\right) \qquad & \\ \\ A \cup \left(B \cap C\right) & = & \left(A \cup B\right) \cap \left(A \cup C\right) \qquad & \mbox{Distributive laws} \\ A \cap \left(B \cup C\right) & = & \left(A \cap B\right) \cup \left(A \cap C\right) \qquad \\ \\ \overline{\left(A \cap B \right)} & = & \overline{A} \cup \overline{B} \qquad & \mbox{De Morgans laws} \\ \overline{\left(A \cup B \right)} & = & \overline{A} \cap \overline{B} \qquad & \\ \end{align}

Other Useful Identities

\begin{align} B - A \equiv B \cap \overline{A} \qquad & \mbox{Definition of set difference} \\ \left(R \cap S\right) \cup \left(R \cap \overline{S}\right) = R \end{align}

Further Reference

cs-401r/set-theory-identities.1410318026.txt.gz · Last modified: 2014/09/10 03:00 by ringger
Back to top
CC Attribution-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0