Set Operations
Union
The union of two sets $A$ and $B$ is the set: \(A\cup B = \{x\vert x\in A\ \text{or} \in B\}\)
This is the same as logical OR ($+$)
Example
Suppose \(A=\{4,7,8\},\ B=\{4,9,10\}\) Then \(A\cup B = \{4,7,8,9,10\}\)
In bit vectors you just perform a logical OR on both of the bit vectors. The result of the OR is the bit vector of the result of the union.
Intersection
The intersection of two sets $A$ and $B$ is the set: \(A\cap B = \{x\vert x\in A\ \text{and}\ x\in B\}\)
This is the same as logical AND.
Example
Suppose \(A=\{4,7,8\},\ B=\{4,9,10\}\) Then \(A\cap B = \{4\}\)
In bit vectors the result of the intersection is the same as a logical AND on the bit vectors.
Relative Complement
The relative complement of a set $B$ to a set $A$ is the set: \(A-B=\{x\vert x\in A\ \text{and}\ x\notin B\}\)
This is the same as XOR ($\oplus$)
This is also sometimes called the set difference.
Example
Suppose \(A=\{4,7,8\},\ B=\{4,9,10\}\) Then \(A - B = \{7,8\}\)
In bit vectors perform an XOR on both of the bit vectors to get the result.
Complement
When we are dealing with subsets of some large set $U$, then we call $U$ the universal set fro the problem in question.
The complement of a set $A$ is the set: \(\sim A=\{x\vert x\notin A\}=U-A\)
This is the same as a binary NOT $\neg$.
Example
Let \(S=\langle1,2,3,4,5\rangle,\ A=\{1,3,5\}\) Then \(\sim A = \{2,4\}\)
The Symmetric Difference
The symmetric difference of two sets $A$ and $B$ is the set: \(\begin{aligned} A\Delta B=&\{x\vert (x\in A\ \text{and}\ x \notin B)\ \text{or}\\ &(x\notin A\ \text{and}\ x \notin B)\} \end{aligned}j\)
This is the same as the logical operator NAND.
Example
Suppose \(A=\{4,7,8\},\ B=\{4,9,10\}\) Then \(A - B = \{7,8,9,10\}\)
In bit vectors perform an NAND on both of the bit vectors to get the result.
Proving the Identity of $A\Delta B=(A\cup B)-(A\cap B)$
Proof
Suppose that $x$ is a particular but arbitrarily chosen element. Consider all cases of this element:
Case 1
$x\notin A,\ x\notin B$. By definition of $\Delta,\ x\notin A\Delta B$.
By definition of $\cup,\ x\notin A\cup B$.
Hence $(A\cup B)-(A\cap B)$.
Case 2
$x\in A,\ x\notin B$. By definition of $\Delta,\ x\in A\Delta B$
By definition of $\cup,\ x\in A\cup B$ as $x\in A$.
As $x\notin B,\ x\notin A\cap B$.
So $x\in(A\cup B)-(A\cap B)$.
Case 3
$x\notin A,\ x\in B$. This case is symmetric to case 2.
Case 4
$x\in A,\ x\in B$. By definition of $\Delta,\ x\notin A\Delta B$.
As $x\in A$, by definition of $\cup,\ x\in A\cup B$.
As $x\in A,\ x\in B,\ x\in A\cap B$.
So $x\notin (A\cup B)-(A\cap B)$.
By the generalisation from the generic particular principle, the identity holds.
(As both sides are equal for all cases the identity must be valid.)