4.5 Symmetric difference

$(A \cup B) ∖ (A \cap B)$

$A Δ B = d e f {x ∣ (x \in A \lor x \in B) \land \neg (x \in A \land x \in B)}$ $= {x ∣ (x \in A \lor x \in B) \land (\neg (x \in A) \lor \neg (x \in B))}$ (de Morgan’s rule) $= {x ∣ ((x \in A \lor x \in B) \land (\neg (x \in A))) \lor ((x \in A \lor x \in B) \land (\neg (x \in B)))}$ (distributivity law) $= {x ∣ ((\neg (x \in A)) \land (x \in A \lor x \in B)) \lor ((\neg (x \in B)) \land (x \in A \lor x \in B))}$ (commutativity law) $= {x ∣ ((\neg (x \in A) \land x \in A) \lor (\neg (x \in A) \land x \in B)) \lor ((\neg (x \in B) \land x \in A) \lor (\neg (x \in B) \land x \in B))}$ (distributivity law) $= {x ∣ ((⊥ \lor (\neg (x \in A) \land x \in B)) \lor ((\neg (x \in B) \land x \in A) \lor ⊥)}$ ( $\neg F \land F =⊥$ ) $= {x ∣ (\neg (x \in A) \land x \in B) \lor (\neg (x \in B) \land x \in A)}$ ( $F \lor ⊥= F$ ) $= {x ∣ (x \in A \land \neg (x \in B)) \lor (x \in B \land \neg (x \in A))}$ (commutativity law) $= (A ∖ B) \cup (B ∖ A)$ (definition of $∖$ and $\cup$ ) The claim is proved

$\neg F \land F$ is unsatisfiable, and therefore $\neg F \land F =⊥$

$A Δ B = A Δ C$ $⟹ (A Δ B) Δ A = (A Δ C) Δ A$ (doing same operation on both sides of the equation) $⟺ B = C$ (by Side Proof below)

Side Proof: Claim: $(A Δ B) Δ A = B$ Proof: Let $a$ be $x \in A$ and $b$ be $x \in B$ , and let $a \oplus b \equiv (a \land \neg b) \lor (b \land \neg a)$ $x \in (A Δ B) Δ A$ $⟺ (a \oplus b) \oplus a$ (by definition of $A Δ B$ and definition of $\oplus$ ) $\equiv ((a \land \neg b) \lor (b \land \neg a)) \oplus a $ (by definition of $\oplus$ ) $\equiv (((a \land \neg b) \lor (b \land \neg a)) \land \neg a) \lor (\neg ((a \land \neg b) \lor (b \land \neg a)) \land a)$ (by definition $\oplus$ ) $\equiv (((a \land \neg b) \land \neg a) \lor ((b \land \neg a) \land \neg a)) \lor (\neg ((a \land \neg b) \lor (b \land \neg a)) \land a)$ (distributivity law) $\equiv (((a \land \neg b) \land \neg a) \lor ((b \land \neg a) \land \neg a)) \lor ((\neg (a \land \neg b) \land \neg (b \land \neg a)) \land a)$ (de Morgan’s law) $\equiv ((a \land \neg a \land \neg b) \lor (b \land \neg a \land \neg a)) \lor ((\neg (a \land \neg b) \land \neg (b \land \neg a)) \land a)$ (commutativity) $\equiv ((⊥ \land \neg b) \lor (b \land \neg a \land \neg a)) \lor ((\neg (a \land \neg b) \land \neg (b \land \neg a)) \land a)$ ( $F \land \neg F \equiv ⊥$ ) $\equiv ((⊥ \land \neg b) \lor (b \land \neg a)) \lor ((\neg (a \land \neg b) \land \neg (b \land \neg a)) \land a)$ (idempotence) $\equiv (⊥ \lor (b \land \neg a)) \lor ((\neg (a \land \neg b) \land \neg (b \land \neg a)) \land a)$ ( $F \land ⊥ \equiv ⊥$ ) $\equiv (b \land \neg a) \lor ((\neg (a \land \neg b) \land \neg (b \land \neg a)) \land a)$ ( $F \lor ⊥ \equiv F$ ) $\equiv (b \land \neg a) \lor (((\neg a \lor b) \land (\neg b \lor a)) \land a)$ (de Morgan’s law) $\equiv (b \land \neg a) \lor ((\neg a \lor b) \land ((\neg b \lor a) \land a))$ (associativity) $\equiv (b \land \neg a) \lor ((\neg a \lor b) \land a)$ (absorption) $\equiv (b \land \neg a) \lor ((a \land b) \lor (a \land \neg a))$ (distributivity law) $\equiv (b \land \neg a) \lor ((a \land b) \lor ⊥)$ ( $\neg F \land F =⊥$ ) $\equiv (b \land \neg a) \lor (a \land b)$ ( $F \lor ⊥ \equiv F$ ) $\equiv b \land (\neg a \lor a)$ (distributivity law) $\equiv b \land (\neg a \lor a)$ ( $F \land \neg F \equiv ⊥$ ) $\equiv b \land ⊥$ ( $F \land \neg F \equiv ⊥$ ) $\equiv b$ ( $F \lor ⊥ \equiv F$ ) $⟺ x \in B$ (by definition of $b$ ) Therefore, $\forall x (x \in (A Δ B) Δ A \leftrightarrow x \in B)$ , meaning $A \subseteq B$ and $B \subseteq A$ by definition of $\subseteq$ Hence, $(A Δ B) Δ A = B$ by Lemma 3.2 The claim is proved.

4.8 Short questions (exam 2022)

2 elements

$(\emptyset, {0, 1})$ $((0, 1), {0, 1})$

$A = {1, 2, 3}$ $B = {2, 3}$ $C = {3}$

$A = {\emptyset}$

4.9 Short questions (exam 2021)

False
False
False
False
False

Thomas Second Brain

Explorer

DiscMat assignment 4

4.5 Symmetric difference

4.8 Short questions (exam 2022)

4.9 Short questions (exam 2021)

Graph View

Table of Contents

Backlinks