XOR using mathematical operators

Question

How can I implement XOR using basic mathematical operators like +,-,*,/

Update: Actually, I need to track change in two matrix having Boolean values. This can be done using XORing each value with corresponding value in other matrix. But, Lp_Solve library doesn't support XOR operation. Also, it accepts only linear equations.

Answer 1

(a-b)*(a-b) works, there must be a much better way though.

1,1 = 0
0,1 = 1
1,0 = 1
0,0 = 0 

Answer 2

The simplest expression I can come up with is: a != b.

(Previous best effort was (a + b) == 1)

Answer 3

Can you do something like:

(a + b) % 2

Answer 4

Exclusive-OR is a linear function, but the definition of 'linear' with regards to a boolean function is not the same as with a polynomial function. You will have to look through the documentation for your lp_solve library to see if it is capable of handling linear boolean functions. From what I have read, I don't suspect that it can.

Edit: After looking further into the simplex algorithm that lp_solve uses, I'm fairly certain that you can't do what you are trying to do.

Answer 5

abs(A+B-1). if it doesn't do abs, then (A+B-1)*(A+B-1) should do it.

Answer 6

Weellllllllllll........

It's not quite as simple as that.

To model a XOR (let's call it X), we start with the logic.

X = (A & !B) | (!A & B)

In math, the above can be written as:

X = A*(1-B) + B*(1-A)

But the above expression is nonlinear (due to the bilinear terms -- to preserve linearity, we are not allowed to multiply variables with each other).

But! Because we are allowed to use constraints, we can rewrite the above expression in linear form.

First, we expand the terms:

X = A*(1-B) + B*(1-A) = A + B - 2*A*B

Now we need to take care of the A*B term (which essentially means A & B). Let a variable H represent the logical condition A & B. We can now write the AND condition as follows: (see cited reference PDF below)

H <= A
H <= B
H >= A + B - 1
H >= 0

Linear XOR Formulation

Finally, let's put everything together. This is your XOR formulation, using only linear constraints.

X = A + B - 2*H
H <= A
H <= B
H >= A + B - 1
H >= 0

I know it looks complicated (for a simple operation like a XOR). There may be a more compact formulation.

But in general, writing logical conditions in a linear programming context is complicated because one is usually severely restricted in the operations one can perform -- in order to avoid destroying the theoretical properties of the problem.

Reference

See here for a list of standard integer formulations for representing logic linearly. http://brblog.typepad.com/files/mipformref-1.pdf

---

Edit:

Explanation on how the H constraints model the "AND" logical condition. Essentially, in an LP, we pose inequality constraints that have to be satisfied at the solution point -- what we're doing here is playing a trick to "squeeze" H to the right value. For instance, given the tuple (A,B) = (0,0), the constraints for H would be:

H <= 0
H <= 0
H >= -1
H >= 0

In the above case, the only value H can take is 0, because H belongs in the interval [0,0]. Hence we get (A,B) = (0,0) => H = 0.

Let's try another example, (A,B) = (1,1).

H <= 1
H <= 1
H >= 1
H >= 0

From the above, you will immediately see that 1 <= H <= 1 implies that H = 1. We get (A,B) = (1,1) => H = 1.

And so on. You'll see that the H constraints model the "AND" condition exactly.