This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
cs-401r:set-theory-identities [2014/09/09 14:44] ringger |
cs-401r:set-theory-identities [2014/10/06 07:08] (current) ringger [Further Reference] |
||
---|---|---|---|
Line 1: | Line 1: | ||
+ | = Set Theory Identities = | ||
\begin{align} | \begin{align} | ||
A \cup \overline{A} & = & \Omega \qquad & \mbox{Complementation law}\\ | A \cup \overline{A} & = & \Omega \qquad & \mbox{Complementation law}\\ | ||
A \cap \overline{A} & = & \emptyset \qquad & \mbox{Exclusion law}\\ \\ | A \cap \overline{A} & = & \emptyset \qquad & \mbox{Exclusion law}\\ \\ | ||
- | A \cap \Omega &\equiv & A \qquad & \mbox{Identity laws} \\ | + | A \cap \Omega & = & A \qquad & \mbox{Identity laws} \\ |
- | A \cup \emptyset& \equiv & A \qquad & \\ \\ | + | A \cup \emptyset& = & A \qquad & \\ \\ |
- | A \cup \Omega &\equiv & \Omega \qquad & \mbox{Domination laws} \\ | + | A \cup \Omega &= & \Omega \qquad & \mbox{Domination laws} \\ |
- | A \cap \emptyset &\equiv & \emptyset \qquad & \\ \\ | + | A \cap \emptyset & = & \emptyset \qquad & \\ \\ |
- | A \cup A &\equiv & A \qquad & \mbox{Idempotent laws} \\ | + | A \cup A & = & A \qquad & \mbox{Idempotent laws} \\ |
- | A \cap A &\equiv & A \qquad & \\ \\ | + | A \cap A & = & A \qquad & \\ \\ |
- | \overline{\left(\overline{A}\right)} &\equiv & A \qquad & \mbox{Double Complement} \\ \\ | + | \overline{\left(\overline{A}\right)} & = & A \qquad & \mbox{Double Complement} \\ \\ |
- | A \cup B &\equiv & B \cup A \qquad & \mbox{Commutative laws} \\ | + | A \cup B & = & B \cup A \qquad & \mbox{Commutative laws} \\ |
- | A \cap B &\equiv & B \cap A \qquad & \\ \\ | + | A \cap B & = & 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 \cup B\right) \cup C & = & 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 & \\ \\ | + | \left(A \cap B\right) \cap C & = & 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 \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) &\equiv & \left(A \cap B\right) \cup \left(A \cap C\right) \qquad \\ \\ | + | 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)} &\equiv & \overline{A} \cup \overline{B} \qquad & \mbox{De Morgans laws} \\ | + | \overline{\left(A \cap B \right)} & = & \overline{A} \cup \overline{B} \qquad & \mbox{De Morgans laws} \\ |
- | \overline{\left(A \cup B \right)} &\equiv & \overline{A} \cap \overline{B} \qquad & \\ | + | \overline{\left(A \cup B \right)} & = & \overline{A} \cap \overline{B} \qquad & \\ |
\end{align} | \end{align} | ||
Line 23: | Line 24: | ||
\begin{align} | \begin{align} | ||
- | B - A \equiv B \cap \overline{A} \\ | + | 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) \equiv R | + | \left(R \cap S\right) \cup \left(R \cap \overline{S}\right) = R |
\end{align} | \end{align} | ||
== Further Reference == | == Further Reference == | ||
+ | |||
+ | You may use the identities available in the following Wikipedia article, as long as they are not the identity you are currently trying to prove: | ||
[http://en.wikipedia.org/wiki/Algebra_of_sets Article on the "algebra of sets" on Wikipedia.] | [http://en.wikipedia.org/wiki/Algebra_of_sets Article on the "algebra of sets" on Wikipedia.] | ||
+ | |||