How to prove that $a \vee b \equiv (a / b) / (a \wedge b)$?

Question

If the symmetric difference is defined as $a / b \equiv (a \wedge \neg b) \vee (\neg a \wedge b)$, then prove that $$a \vee b \equiv (a / b) / (a \wedge b)$$

---

I tried to expand the right-hand side of the equivalence:

$$(a/ b)/(a\wedge b)\equiv (¬(a/b)\wedge(a\wedge b))\vee((a/b)\wedge¬(a\wedge b))$$

and then break the expansion of the disjunction:

1. $¬(a/b)\wedge(a\wedge b)$
2. $(a/b)\wedge¬(a\wedge b)$

For the first part:

$$¬(a/b)\wedge(a\wedge b)\equiv ¬((a\wedge¬b)\vee(¬a\wedge b))\wedge(a\wedge b)$$ $$\equiv (¬(a\wedge¬b)\wedge¬(¬a\wedge b))\wedge(a\wedge b)\equiv (¬a\vee b)\wedge(a\vee¬b)\wedge a\wedge b $$ $$\equiv ((¬a\vee b)\wedge a)\wedge((a\vee¬b)\wedge b)\equiv ((¬a\wedge a)\vee(b\wedge a))\wedge((a\wedge b)\vee(¬b\wedge b))$$ $$\equiv(0\vee(a\wedge b))\wedge((a\wedge b)\vee 0)\equiv (a\wedge b)\wedge(a\wedge b)\equiv a\wedge b $$

And for the second part:

$$(a/b)\wedge¬(a\wedge b)\equiv ((a\wedge¬b)\vee(¬a\wedge b))\wedge¬(a\wedge b) $$ $$\equiv (a\wedge¬b)\vee(¬a\wedge b)\vee¬a\vee¬b\equiv ((a\wedge¬b)\vee¬a)\vee((¬a\wedge b)\vee¬b)$$ $$\equiv ((¬a\vee a)\wedge(¬b\vee¬a))\vee((¬a\vee¬b)\wedge(b\vee¬b))\equiv(1\wedge¬(b\wedge a))\vee(¬(a\wedge b)\wedge 1) $$ $$¬(a\wedge b)\vee¬(a\wedge b)\equiv ¬(a\wedge b) $$

So I have that $(a/ b)/(a\wedge b)\equiv (a\wedge b)\vee ¬(a\wedge b)$. Expanding again gives$\dots$

$$(a\wedge b)\vee ¬(a\wedge b)\equiv (a\wedge b)\vee¬a\vee¬b\equiv(a\vee¬a\vee¬b)\wedge(b\vee¬a\vee¬b)$$ $$\equiv ¬b\wedge¬a\equiv ¬(a\vee b) $$

So given the algebraic manipulation I get $(a/ b)/(a\wedge b)\equiv ¬(a\vee b)$, which is the opposite of what I was looking for. How can I prove this?

Answer 1

For the second part,

$(a/b) \wedge \neg (a \wedge b)$

$\equiv ((a \wedge \neg b) \vee (\neg a \wedge b)) \wedge \neg (a \wedge b)$

$\equiv ((a \wedge \neg b) \vee (\neg a \wedge b)) \wedge ( \neg a \vee \neg b)$

$\equiv ((a \wedge \neg b) \wedge ( \neg a \vee \neg b)) \vee ((\neg a \wedge b) \wedge ( \neg a \vee \neg b))$

$\equiv (((a \wedge \neg b) \wedge \neg a) \vee ((a \wedge \neg b) \wedge \neg b)) \vee (((\neg a \wedge b) \wedge \neg a) \vee ((\neg a \wedge b) \wedge \neg b))$

$\equiv (0 \vee (a \wedge \neg b)) \vee ( (\neg a \wedge b) \vee 0)$

$\equiv (a \wedge \neg b) \vee (\neg a \wedge b)$

Putting all things together yields

$(a/b)/(a \wedge b)$

$\equiv (\neg (a/b) \wedge (a \wedge b)) \vee ((a/b) \wedge \neg (a \wedge b))$

$\equiv (a \wedge b) \vee ((a \wedge \neg b) \vee (\neg a \wedge b))$

$\equiv ((a \wedge b) \vee (a \wedge \neg b)) \vee (\neg a \wedge b)$

$\equiv (a \wedge (b \vee \neg b)) \vee (\neg a \wedge b)$

$\equiv (a \wedge 1) \vee (\neg a \wedge b)$

$\equiv a \vee (\neg a \wedge b)$

$\equiv ...$

Answer 2

I find the 'engineering' notation a little easier to manipulat, $a \oplus b = a \overline{b}+\overline{a}b$, note that coincidence $\overline{a \oplus b} = ab + \overline{a} \overline{b}$.

Then \begin{eqnarray} (a \oplus b) \oplus ab &=& (a \overline{b}+\overline{a}b)( \overline{a}+\overline{b}) + (ab + \overline{a} \overline{b}) ab\\ &=& a \overline{b}+\overline{a}b + ab \\ &=& a + b \end{eqnarray} Alternatively consider the four exhaustive cases $(a,b) \in \{(F,F), (F,T), (T,F), (T,T) \}$ and show equality for each assignment.

Addendum: Engineers working with digital logic use alternative notation:

$\overline{a}$ means $\lnot a$

$a+b $ means $a \lor b$

$ab$ or $a \cdot b$ means $a \land b$.

Exclusive or $\oplus$ and coincidence $\odot$ are defined above.