How to prove that $(A \vee B) + (A \wedge B) \equiv A + B$?
Here $\vee$ and $\wedge$ are bitwise OR and bitwise AND operators, respectively. "$+$" is the arithmetic operator.
Example :- $(5 \vee 6) + (5 \wedge 6) \equiv 5 + 6 = 11$.
Any hints would be appreciated.
On
You can use structural induction.
First show that it holds for the base case $A = B = 0$.
Then show that if it holds for $(A, B)$ with $A_k = 0$, then it holds for $(A + 2^k, B)$.
Case 1, $B_k = 0$ : $$( (A + 2^k) \lor B) + ((A + 2^k) \land B) = ((A \lor B) + 2^k) + (A \land B)$$
Case 2, $B_k = 1$ : $$( (A + 2^k) \lor B) + ((A + 2^k) \land B) = (A \lor B) + ((A \land B) + 2^k)$$
Hint: first check that it's true for $A = B = 2^n$ and for $A = 2^n$, $B = 0$.