Prove a proposition (Boolean algebra)

Question

I'd like to prove the following proposition:

a=b if and only if (a∧¬b)∨(¬a∧b)= 0

Intuitively, the proposition is obvious because if a=b, then we could just substitute and have something like (a∧¬a)∨(¬a∧a)= 0∨0 = 0

However, I don't know how to express it in a formal proof, specially that the "if and only if" part usually require a two way demonstration.

Anybody has an idea how to address this problem?

Answer 1

Your L2R looks fine. Maybe:

$$(a=b) \implies (a\land \lnot b=a\land \lnot a)$$

to make it more formal.

To go R2L, we need to use the formula for conjunction and disjunction, namely:

$a \land b = ab$
$a \lor b=a+b-ab$

So:

$$(a \land \lnot b) \lor (\lnot a \land b)$$

becomes:

$$a(1-b) \lor (1-a)b$$

$$=a(1-b)+(1-a)b+ab(1-a)(1-b)$$

Remember that in Boolean algebra, conjunction (and disjunction) is idempotent, that is $xx=x$ (because $0^2=0, 1^2=1$ and that's the entire set of elements). Also $-x=-x\cdot -x=xx=x$, as in GF_2.

So the above equation simplifies to:

$$a-ab+b-ab+ab(1-a-b+ab)$$

$$=a-2ab+b+ab-aab-abb+aabb$$

$$=a-2ab+b+ab-ab-ab+ab$$

$$=a-2ab+b$$

$$=aa-2ab+bb$$

$$=(a-b)(a-b)$$

$$=a-b$$

which is $0$ iff $a=b$.

Answer 2

For right to left:

$a =a11=a(a + a')(b + b') = a(ab+ab'+a'b+a'b')=a(ab+0+a'b')=a(ab+a'b') = aab+aa'b'=ab+0b'=ab+0=ab+ a'0= abb+a'b'b=(ab+a'b')b=(ab+0+a'b')b=(ab+ab'+b'a+a'b')b=(a+a')(b+b')b=11b=b$