# Truth Table Logic XOR

I'm not sure if my solution is correct. Would be very happy if you can check and say what I did wrong.

a) Is to make A xor B with only conjunction, disjunction and negation. b) Is to check if A xor (B AND C) is equal to ((A xor B) AND (A xor C)) ## 3 Answers

In part (a), you made a mistake converting $\lnot (A \land B)$ to $\lnot A \land \lnot B$, double check your demorgans. Similarly, a mistake changing $\lnot (\lnot A \land \lnot B)$ to $A \land B$

The correct use of demorgan's is:

$\lnot (A \land B)$ is equal to $\lnot A \lor \lnot B$

and (try to figure these out on your own before looking at the solution)

$\lnot (\lnot A \land \lnot B)$ is equal to $A \lor B$

For part (b), I looked over it and didn't see any mistakes.

A sure way to test if your equivalency is correct is to exhaustively test it with a truth table, where if you set A to 1, B to 0 and C to 1, you will find: (1 ⊻ 0) ∧ (1 ⊻ 1) -> 0 ; (1 ⊻ (0 ∧ 1)) -> 1

(A ⊻ B) ∧ (A ⊻ C) is 1 only when A is 1, and B and C are both 0, or when A is 0, and both B and C are 1.

Incidentally, your expression happens to be the exact formula used in some emulators to calculate the overflow condition code (V = (arg ^ val) & (arg ^ res)) and I don't think there is a C language expression for it that generates fewer operations. (C, and most target architectures, does not offer the 'equiv' boolean operation as a primitive, which is what would be needed to use fewer operations)

a) No, your last substitution is wrong.

b) By reasoning: if $B$ and $C$ are equal, then both expressions reduce to $A\text{ xor }B$; but if they are different, the expressions reduce to $A\text{ xor }\text{false}$ and $\text{false}$.