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


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

Other Useful Identities

\begin{align} B - A \equiv B \cap \overline{A} \\ \left(R \cap S\right) \cup \left(R \cap \overline{S}\right) \equiv R \end{align}

Further Reference

cs-401r/set-theory-identities.1409926173.txt.gz · Last modified: 2014/09/05 14:09 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