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 m开发者_运维知识库atrix. But, Lp_Solve library doesn't support XOR operation. Also, it accepts only linear equations.

(a − b)²

This works because:

(a − b)² = a * (a − b) + b * (b − a)

Since multiplication in ℤ₂ is conjuction (&), and 1 - a is negation (!), the above formula is equivalent to XOR for a, b ∈ {0, 1}:

(a & !b) | (b & !a)

See the comment below by Pascal Cuoq explaining why this cannot be a linear equation.

TL;DR

XOR any numerical input

a + b - ab(1 + a + b - ab)

XOR binary input

a + b - 2ab or (a-b)²

Derivation

Basic Logical Operators

NOT = (1-x)

AND = x*y

From those operators we can get...

OR = (1-(1-a)(1-b)) = a + b - ab

Note: If a and b are mutually exclusive then their and condition will always be zero - from a Venn diagram perspective, this means there is no overlap. In that case, we could write OR = a + b, since a*b = 0 for all values of a & b.

2-Factor XOR

Defining XOR as (a OR B) AND (NOT (a AND b)):

(a OR B) --> (a + b - ab)

(NOT (a AND b)) --> (1 - ab)

AND these conditions together to get...

(a + b - ab)(1 - ab) = a + b - ab(1 + a + b - ab)

XOR using mathematical operators

Computational Alternatives

If the input values are binary, then powers terms can be ignored to arrive at simplified computationally equivalent forms.

a + b - ab(1 + a + b - ab) = a + b - ab - a²b - ab² + a²b²

If x is binary (either 1 or 0), then we can disregard powers since 1² = 1 and 0² = 0...

a + b - ab - a²b - ab² + a²b² -- remove powers --> a + b - 2ab

XOR (binary) = a + b - 2ab

Binary also allows other equations to be computationally equivalent to the one above. For instance...

Given (a-b)² = a² + b² - 2ab

If input is binary we can ignore powers, so...

a² + b² - 2ab -- remove powers --> a + b - 2ab

Allowing us to write...

XOR (binary) = (a-b)²

Multi-Factor XOR

XOR = (1 - A*B*C...)(1 - (1-A)(1-B)(1-C)...)

What about when you want to XOR(A,B,C...)? The problem here is that if we try to discern all truth conditions like we did in the composite logic for 2-factor XOR, it doesn't scale very nicely, as you have to add every permutation of truth. However, logic being what it is, we can arrive at XOR the complimentary way...

XOR = !(A & B & C...) & !(!A & !B & !C...)

From which you can construct an arithmetic XOR for any number of factors in the form of...

(1 - A*B*C...)(1 - (1-A)(1-B)(1-C)...)

Here's some Excel VBA to XOR an entire range of cells...

Function ArithmeticXOR(R As Range, Optional EvaluateEquation = True)

Dim AndOfNots As String
Dim AndGate As String
For Each c In R
    AndOfNots = AndOfNots & "*(1-" & c.Address & ")"
    AndGate = AndGate & "*" & c.Address
Next
AndOfNots = Mid(AndOfNots, 2)
AndGate = Mid(AndGate, 2)

'Now all we want is (Not(AndGate) AND Not(AndOfNots))
ArithmeticXOR = "(1 - " & AndOfNots & ")*(1 - " & AndGate & ")"
If EvaluateEquation Then
    ArithmeticXOR = Application.Evaluate(xor2)
End If

End Function

Any n of k

One last tidbit here. Sometimes you want a condition to be true if any n number of inputs are true. This can be viewed as a relaxed AND condition, whereby you're willing to accept a&b or a&c or b&c for instance. This can be arithmetically modeled from the composite logic...

(a && b) || (a && c) || (b && c) ...

and applying our translations...

1 - (1-ab)(1-ac)(1-bc)...

That's useful on it's own, but there's also an interesting pattern when you expand the terms. There is a pattern of variable and exponent combinations, but this gets very long; however, you can simplify by ignoring powers for a binary context. The exact pattern is dependent on how n relates to k. For n = k-1, where k is the total number of conditions being tested, the result is as follows:

c1 + c2 + c3 ... ck - n*∏

Where c1 through ck are all n-variable combinations.

For instance, true if 3 of 4 conditions met would be

abc + abe + ace + bce - 3abce

This makes perfect logical sense since what we have is the additive OR of AND conditions minus the overlapping AND condition.

If you begin looking at n = k-2, k-3, etc. The pattern becomes more complicated because we have more overlaps to subtract out. If this is fully extended to the smallest value of n = 1, then we arrive at nothing more than a regular OR condition.

Thinking about Non-Binary Values and Fuzzy Region

The actual algebraic XOR equation a + b - ab(1 + a + b - ab) is much more complicated than the computationally equivalent binary equations like x + y - 2xy and (x-y)². Does this mean anything, and is there any value to this added complexity?

Obviously, for this to matter, you'd have to care about the decimal values outside of the discrete points (0,0), (0,1), (1,0), and (1,1). Why would this ever matter? Sometimes you want to relax the integer constraint for a discrete problem. In that case, you have to look at the premises used to convert logical operators to equations.

When it comes to translating Boolean logic into arithmetic, your basic building blocks are the AND and NOT operators, with which you can build both OR and XOR.

OR = (1-(1-a)(1-b)(1-c)...)

XOR = (1 - a*b*c...)(1 - (1-a)(1-b)(1-c)...)

So if you're thinking about the decimal region, then it's worth thinking about how we defined these operators and how they behave in that region.

Non-Binary Meaning of NOT

We expressed NOT as 1-x. Obviously, this simple equation works for binary values of 0 and 1, but the thing that's really cool about it is that it also provides the fractional or percent-wise compliment for values between 0 to 1. This is useful since NOT is also known as the Compliment in Boolean logic, and when it comes to sets, NOT refers to everything outside of the current set.

Non-Binary Meaning of AND

We expressed AND as x*y. Once again, obviously it works for 0 and 1, but its effect is a little more arbitrary for values between 0 to 1 where multiplication results in partial truths (decimal values) diminishing each other. It's possible to imagine that you would want to model truth as being averaged or accumulative in this region. For instance, if two conditions are hypothetically half true, is the AND condition only a quarter true (0.5 * 0.5), or is it entirely true (0.5 + 0.5 = 1), or does it remain half true ((0.5 + 0.5) / 2)? As it turns out, the quarter truth is actually true for conditions that are entirely discrete and the partial truth represents probability. For instance, will you flip tails (binary condition, 50% probability) both now AND again a second time? Answer is 0.5 * 0.5 = 0.25, or 25% true. Accumulation doesn't really make sense because it's basically modeling an OR condition (remember OR can be modeled by + when the AND condition is not present, so summation is characteristically OR). The average makes sense if you're looking at agreement and measurements, but it's really modeling a hybrid of AND and OR. For instance, ask 2 people to say on a scale of 1 to 10 how much do they agree with the statement "It is cold outside"? If they both say 5, then the truth of the statement "It is cold outside" is 50%.

Non-Binary Values in Summary

The take away from this look at non-binary values is that we can capture actual logic in our choice of operators and construct equations from the ground up, but we have to keep in mind numerical behavior. We are used to thinking about logic as discrete (binary) and computer processing as discrete, but non-binary logic is becoming more and more common and can help make problems that are difficult with discrete logic easier/possible to solve. You'll need to give thought to how values interact in this region and how to translate them into something meaningful.

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

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

In Brown, G. and Dell, R., Formulating linear and integer linear programs: A rogues’ gallery the following linear programming formulation for the XOR can be found:

Z3 = Z1 XOR Z2

resolves to

Z3 <= Z1 + Z2
Z3 >= Z1 - Z2
Z3 >= -Z1 + Z2
Z3 <= 2 - Z1 - Z2

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.

Can you do something like:

(a + b) % 2

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.

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

you can use this :

Xor(n,x,y)=x+y - Pow(2,n+1)(floor((x+y)/Pow(2,n+1)));

when

x => number in Z collection and positive, x>=0

y => number in Z collection and positive, y>=0

n => is data bit length for example 32 or 64

pow(2,3)=> 222

floor(1.6594565)=1 or floor(4562.21)=4562