2
$\begingroup$

Here is the definition of the Symmetric Difference: $$ A \Delta B = (A \backslash B) \cup (B \backslash A), $$ Our goal is to prove: $$ A \Delta B = (A \cup B) \backslash(A \cap B). $$

I want to prove this and at the same time to check if my understanding of the Distributive Laws of Logic is correct.

My main goal is about Distributive Laws of Logic. I want to know if I can always break the parenthesis with this method.

I know that there are similar proofs in the website but I feel that I need help with the Distributive Laws.

Please check if this is correct:

We start with

$(x \in A$ $\land$ $x \notin B)$ $\vee$ $(x \notin A$ $\land$ $x \in B)$

This is the part that I want to know if I am correct, and I want to know if I can do this for any parenthesis regarding of what is inside of the parenthesis of the right part:

$(x \in A$ $\land$ $x \notin B)$ $\vee$ x $\notin$ A ) $\land$

$(x \in A$ $\land$ $x \notin B)$ $\vee$ x $\in$ B )

Now we can use the classic version of the Distributive Law:

$(x \in A$ $\vee$ x $\notin$ $A$ ) $\land$

$(x \notin B$ $\vee$ x $\notin$ $A$ ) $\land$

$(x \in A$ $\vee$ x $\in$ $B$ ) $\land$

$(x \notin B$ $\vee$ x $\in$ $B$ )

Now we can simplify:

******Universe****** $\land$

$(x \notin B$ $\vee$ x $\notin$ $A$ ) $\land$

$(x \in A$ $\vee$ x $\in$ $B$ ) $\land$

******Universe******

Finally we have,

$(x \in A$ $\vee$ x $\in$ $B$ ) $\land$

$(x \notin B$ $\vee$ x $\notin$ $A$ )

The last step is to use the Morgan Laws

$(x \in A$ $\vee$ x $\in$ $B$ ) $\land$

$\neg$ $(x \in A$ $\land$ $x$ $\in$ $B$ )

That is our goal:

Goal

Q.E.D.

$\endgroup$
5
  • 1
    $\begingroup$ I just happened to see this! I suppose 'pinging' me in a comment to your own question does not work ... anyway, yes, your proof is fine! And yes, you can use Distribution on part of a statement just as you are using DeMorgan on just part of the statement in your last step. $\endgroup$
    – Bram28
    Sep 28 '17 at 3:42
  • $\begingroup$ @Bram28 Thank you so much again for your amazing teachings! $\endgroup$
    – Beginner
    Sep 28 '17 at 14:50
  • $\begingroup$ You're welcome! And by the way, I definitely see your progress with this material!! :) $\endgroup$
    – Bram28
    Sep 28 '17 at 14:52
  • $\begingroup$ @Bram28 I have been using your teachings about Latex and Mathematical Logic. You are fantastic! Thank you so much! $\endgroup$
    – Beginner
    Sep 28 '17 at 15:16
  • $\begingroup$ :) I appreciate your kind words ... but you are doing the learning! $\endgroup$
    – Bram28
    Sep 28 '17 at 15:17
1
$\begingroup$

Yes, that is a permissible application of distribution.

It is basically using the proof for the quadratic distribution: $$(s\wedge t)\vee (u\wedge v)~{= (s\vee (u\wedge v))\wedge(t\vee (u\wedge v))\\ =(s\vee u)\wedge(s\vee v)\wedge(t\vee u)\wedge (t\vee v)}$$

Take an arbitrary $x$ such that $x\in (S\cap T)\cup(U\cap V)$.   By definition of union and disjunction, this is equivalent to $(x\in S\wedge x\in T)\vee(x\in U\wedge x\in V)$.   By distribution, that is equivalent to $(x\in S\vee(x\in U\wedge x\in V))\wedge (x\in T\vee(x\in U\wedge x\in V))$, and distributing again that is $(x\in S\vee x\in U)\wedge (x\in S\vee x\in V)\wedge (x\in T\vee x\in U)\wedge (x\in T\vee x\in V)$. Thus it is equivalent to $x\in(S\cup U)\cap (S\cup V)\cap (T\cup U)\cap (T\cup V)$.

More succinctly, using the set algebra:

$$(S\cap T)\cup(U\cap V)~{=(S\cup(U\cap V))\cap(T\cup(U\cap V))\\=(S\cup U)\cap (S\cup V)\cap (T\cup U)\cap (T\cup V)}$$

Just substitute the relevant sets.


If we presume complementation relative to some superset $\mathcal U$ (the "universe") of both $A,B$, then your proof is essentially:

$$\def\sm{\smallsetminus} {\begin{align} &\quad (A\Delta B) \\ &= (A\sm B)\cup(B\sm A) &&\text{definition of symmetric difference} \\& = (A\cap B^\complement)\cup(B\cap A^\complement) &&\text{definition of set minus} \\& = (A\cup (B\cap A^\complement))\cap(B^\complement\cup (B\cap A^\complement)) && \text{distribution} \\& = (A\cup B)\cap(A\cup A^\complement)\cap (B^\complement\cup B)\cap (B^\complement\cup A^\complement)&&\text{distribution} \\& = (A\cup B)\cap\mathcal U\cap\mathcal U\cap (B^\complement\cup A^\complement)&&\text{complementation} \\&= (A\cup B)\cap(B^\complement\cup A^\complement) && \text{identity} \\&= (A\cup B)\cap(A^\complement\cup B^\complement) && \text{commutivity} \\&= (A\cup B)\cap(A\cap B)^\complement & & \text{deMorgan's Rule} \\&= (A\cup B)\sm(A\cap B) && \text{definition of set minus}\end{align}}$$

$\endgroup$
2
  • $\begingroup$ Thank you so much! Amazing answer! I like very much the idea to treat the problem with Set Laws. In that way, the solution can be reduced to few steps. $\endgroup$
    – Beginner
    Sep 29 '17 at 16:45
  • $\begingroup$ I am using your teaching to apply set rules instead of logic rules and it reduces the work to be done at least 50%. Thank you so much! $\endgroup$
    – Beginner
    Oct 2 '17 at 21:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.