XOR of two numbers AND third number ?

Question

If:

x & (a ^ b) != 0

Then one of the following holds:

x & a == 0; x & b != 0

or

x & b == 0; x & a != 0

What is the reason for this? And are there similar properties of AND/OR/NOT with XOR?

Thank you.

Answer 1

Let us look at the problem from another angle, a pure algebraic one.

Let $a,b,x$ be boolean variables taking values either $T$ or $F$ and $\alpha,\beta,\chi$ be numbers in $\mathbb{Z}/2\mathbb{Z}$, the equivalent classes of integers modulus 2, taking values either $1$ or $0 \pmod 2$.

If you look at the truth table for $a, b$ under logical AND/XOR operations and the multiplication/addition tables for $\alpha, \beta$ side by side,

$$\begin{array}{r|ll} a \text{ & } b & T & F\\ \hline T & T & F\\ F & F & F\\ \end{array} \;vs.\; \begin{array}{r|ll} \alpha \text{ * } \beta & 1 & 0\\ \hline 1 & 1 & 0\\ 0 & 0 & 0\\ \end{array} \quad\text{ AND }\quad \begin{array}{r|ll} a \text{ ^ } b & T & F\\ \hline T & F & T\\ F & T & F\\ \end{array} \;vs.\; \begin{array}{r|ll} \alpha \text{ + } \beta & 1 & 0\\ \hline 1 & 0 & 1\\ 0 & 1 & 0\\ \end{array} $$

You will find they are identical. In other words, the algebra generated by the logical AND and XOR operations is isomorphic to the algebra of multiplication/addition of integers under modulus $2$.

We know addition and multiplication of integers satisfy distributive law. So does the logical AND and XOR operation. i.e

$$\chi*(\alpha+\beta) = \chi*\alpha + \chi*\beta \quad vs. \quad x \text{ & } (a \text{ ^ } b ) = ( x \text{ & } a ) \text{ ^ } (x \text{ & } b)$$

Recall given any two boolean expression $u$ and $v$,

$$u \text{ ^ } v = T \quad\text{ iff }\quad u \ne v \quad\text{ iff }\quad ( u = T \text{ AND } v = F ) \text{ OR } ( u = F \text{ AND } v = T ). $$ We can transform the given logical condition as follows $$\begin{align} & x \text{ & } (a \text{ ^ } b) = T\\ \iff & ( x \text{ & } a ) \text{ ^ } ( x \text{ & } b ) = T\\ \iff & ( x \text{ & } a ) \ne ( x \text { & } b )\\ \iff & \bbox[4pt,border:1px solid]{ \begin{array}{rrcl} & (( x \text{ & } a ) = T & \text{ AND } & (x \text{ & } b) = F)\\ \text{ OR } & (( x \text{ & } a ) = F & \text{ AND } & (x \text{ & } b) = T) \end{array}} \end{align}$$

What you see is nothing special, but a consequence of the distributive law between the logical AND and XOR operation.

Answer 2

Notice that x is true, because our 'and' is evaluating to true. The xor has to evaluate to true as well, so we also require that a and b are different.

What does this imply?

To answer your further question. If an xor is only true if a and b are different then xnor is only true if a and b are the same.

There is nothing particularly interesting about an or with an xor.

Answer 3

x & (a^b) != 0

x & (a^b) == 1

x==1; a^b==1

For a^b==1 to hold, either a==0;b==1 must hold or a==1;b==0 must hold (i.e., a!=b). Doing the & operations with a gives you the two cases that you gave.