1
$\begingroup$

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))

enter image description here

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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)

$\endgroup$
0
$\begingroup$

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}$.

$\endgroup$

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.