XOR Power

Logic Level 3

$A \text{ XOR } B$ is true if either $A$ is true or $B$ is true (but not both). ( $XOR$ stands for "exclusive or".)

Is it possible to make a statement equivalent to $A \text{ AND } B$ using only $XOR$ as an operation? (Please note: only XOR! NOT isn't allowed.)

Yes No

2 solutions

A Former Brilliant Member
Dec 13, 2016

Denote $A \,XOR \,B$ by $A \oplus B$ .

Then the following hold : $A \oplus B = B \oplus A \\ (A \oplus B) \oplus C = A \oplus (B \oplus C) \\ A \oplus 0 = A \\ A \oplus A = 0$

Hence any expression involving only $A,B$ and $\oplus$ is equivalent to one of the following :

$A \oplus B \\ A \\ B \\ 0$

None of the above are equivalent to $A \, AND \, B$ .

We conclude that such an expression doesn't exist.

Eric Kim
Dec 14, 2016

Not sure how mathematically sound this is.

We are only allowed A, B, and the XOR operator.

Note that the solution has to be X XOR Z, where X and Z are any combination of A and B (because XOR is our only operator)

Since we want a statement that says A AND B, we see that X and Y BOTH have to say A AND B.

But this is just a recurrence of the original problem statement, so we see that the statement X XOR Z can not be simplified into A, B, and XOR to say A AND B.

XOR Power

2 solutions

0 pending reports