# [ACCEPTED]-XOR using mathematical operators-xor

# (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)=> 2*2*2

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

More Related questions

We use cookies to improve the performance of the site. By staying on our site, you agree to the terms of use of cookies.