(a − b)²

This works because:

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

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

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

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

The simplest expression I can come up with 1 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 2 linear programming formulation for the XOR 1 can be found:

Z3 = Z1 XOR Z2

resolves to

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

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 120 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 119 conditions together to get...

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

Computational Alternatives

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

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

If x is binary (either 115 1 or 0), then we can disregard powers since 114 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 113 to be computationally equivalent to the 112 one above. For instance...

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

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

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

Allowing 110 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 109 want to XOR(A,B,C...)? The problem here 108 is that if we try to discern all truth conditions 107 like we did in the composite logic for 2-factor 106 XOR, it doesn't scale very nicely, as you 105 have to add every permutation of truth. However, logic 104 being what it is, we can arrive at XOR the 103 complimentary way...

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

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

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

Here's some 100 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 99 last tidbit here. Sometimes you want a condition 98 to be true if any n number of inputs are 97 true. This can be viewed as a relaxed AND condition, whereby 96 you're willing to accept a&b or a&c 95 or b&c for instance. This can be arithmetically 94 modeled from the composite logic...

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

and applying 93 our translations...

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

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

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

Where c1 82 through ck are all n-variable combinations.

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

abc + abe + ace + bce - 3abce

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

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

Thinking about Non-Binary Values and Fuzzy Region

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

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

When it comes to 58 translating Boolean logic into arithmetic, your 57 basic building blocks are the AND and NOT operators, with 56 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 55 if you're thinking about the decimal region, then 54 it's worth thinking about how we defined 53 these operators and how they behave in that 52 region.

Non-Binary Meaning of NOT

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

Non-Binary Meaning of AND

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

Non-Binary Values in Summary

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

Weellllllllllll........

It's not quite as 40 simple as that.

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

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

In math, the 38 above can be written as:

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

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

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

First, we 32 expand the terms:

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

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

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

Linear XOR Formulation

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

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

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

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

Reference

See 16 here for a list of standard integer formulations 15 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 14 an LP, we pose inequality constraints that 13 have to be satisfied at the solution point 12 -- what we're doing here is playing a trick 11 to "squeeze" H to the right value. For 10 instance, given the tuple (A,B) = (0,0), the 9 constraints for H would be:

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

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

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

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

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

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

Can you do something like:

(a + b) % 2

0

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

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

abs(A+B-1). if it doesn't do abs, then (A+B-1)*(A+B-1) should 1 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 5 => number in Z collection and positive, x>=0

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

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

pow(2,3)=> 222

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