XOR使用数学运算符
如何使用+， – ，*，/等基本数学运算符实现XOR
更新：实际上，我需要跟踪具有布尔值的两个矩阵的变化。 这可以通过使用其他矩阵中的相应值对每个值进行异或来完成。 但是，Lp_Solve库不支持XOR操作。 此外，它只接受线性方程。
（a – b）²
这是因为：
(a − b)² = a * (a − b) + b * (b − a)
由于ℤ2中的乘法是结合（ & ），而1 - a是否定（ ! ），上述公式相当于a, b ∈ {0, 1} XOR：
(a & !b) | (b & !a)
请参阅Pascal Cuoq下面的评论，解释为什么这不能是一个线性方程式 。
我能想出的最简单的表达方式是： a != b 。
（以前的最佳努力是(a + b) == 1 ）
在Brown，G。和Dell，R.， Formulating linear and integer linear programs：A rogues’gallery中，可以找到以下用于XOR的线性规划公式：
Z3 = Z1 XOR Z2
解决了
Z3 <= Z1 + Z2 Z3 >= Z1 - Z2 Z3 >= -Z1 + Z2 Z3 <= 2 - Z1 - Z2
你可以这样做：
(a + b) % 2
Weellllllllllll ……..
它并不那么简单。
为了模拟XOR（我们称之为X），我们从逻辑开始。
X = (A & !B) | (!A & B)
在数学中，以上可以写成：
X = A*(1-B) + B*(1-A)
但上面的表达式是非线性的（由于双线性项 – 为了保持线性，我们不允许将变量相互相乘）。
但是 ！ 因为我们可以使用约束，所以我们可以用线性forms重写上面的表达式。
首先，我们扩展条款：
X = A*(1-B) + B*(1-A) = A + B - 2*A*B
现在我们需要处理A * B术语（这实际上意味着A和B）。 设一个变量H表示逻辑条件A和B.我们现在可以按如下方式编写AND条件:(参见下面引用的参考文献PDF）
H <= A H <= B H >= A + B - 1 H >= 0
线性XOR配方
最后，让我们把所有东西放在一起。 这是您的XOR公式，仅使用线性约束。
X = A + B - 2*H H <= A H <= B H >= A + B - 1 H >= 0
我知道它看起来很复杂（对于像XOR这样的简单操作）。 可能有更紧凑的配方。
但一般而言，在线性编程上下文中编写逻辑条件是复杂的，因为人们通常可以严格限制操作 – 以避免破坏问题的理论属性。
参考
请参阅此处以获取用于线性表示逻辑的标准整数公式列表。 http://brblog.typepad.com/files/mipformref-1.pdf
编辑 ：
关于H约束如何模拟“AND”逻辑条件的说明 。 本质上，在LP中，我们提出必须在解决点处满足的不等式约束 – 我们在这里所做的是发挥一种技巧，将H“挤压”到正确的值。 例如，给定元组（A，B）=（0,0），H的约束将是：
H <= 0 H <= 0 H >= -1 H >= 0
在上面的情况中，H可以采用的唯一值是0，因为H属于区间[0,0]。 因此我们得到（A，B）=（0,0）=> H = 0。
让我们尝试另一个例子，（A，B）=（1,1）。
H <= 1 H <= 1 H >= 1 H >= 0
从上面可以看出，1 <= H <= 1意味着H = 1.我们得到（A，B）=（1,1）=> H = 1。
等等。 您将看到H约束准确地模拟“AND”条件。
2因子异或
虽然(xy)²是一个非常紧凑的双因子XOR方程，但这种forms在某些方面具有误导性。
虽然这些方程的评估对于1和0的值是相同的，但它们在代数上并不相等……
(a − b)² ≠ a * (1 − b) + b * (1 − a)
此外，逻辑OR运算符不会在没有约束的情况下以算术方式转换为+ 。 对于两个1的AND条件，这将给你一个值2。 如果你首先考虑NOT和AND翻译..
NOT = (1-x)
AND = x*y
你真正需要的是这样的……
OR = (1-(1-a)(1-b)) = a + b - ab
请注意，在特征上， OR是纯粹的加法，因此您加入了两个集合，但是您不想复制集合的任何重叠，因此您减去通过乘法找到的AND条件。 因此，您的附加项a+b减去重叠或AND条件a*b 。 如果您确定您的套装不会重叠，那么您可以使用
OR = a + b ，如果我们知道a＆b的所有值的a a*b = 0
同样，我们可以推导出XOR方程。 使用复合逻辑(a && !b) || (!a && b) (a && !b) || (!a && b)你会得到……
XOR = 1 - (1 - a(1-b))(1 - b(1-a)) ≠ (ab)²
所以(ab)²在逻辑和代数的翻译中有些误导。 事实certificate，这些错误被二进制输入的约束所掩盖，并且因为条件a(1-b)和b(1-a)是互斥的，这放松了处理AND条件的OR运算符的约束并允许它被建模为+ 。
吉利德的回答有助于解释为什么(xy)²实际上有效。 展开(xy)² = x² + y² - 2xy您可以看到它是如何满足这个基本模型的……
X = A + B - 2*H H <= A H <= B H >= A + B - 1 H >= 0
利用这些知识，您可以看到有许多方程式可行。 例如，满足这些条件的实际最基本方程是……
x + y - 2xy
这与我们为OR得到的等式完全相同，除了现在我们不仅要删除AND条件（ -xy ）的副本，而且一起拒绝AND条件（ -2xy ）。 事实certificate，这也是(ab)²的实际代数等价物……
a * (1 − b) + b * (1 − a) = a + b - 2ab ≠ (ab)² 。
(ab)²可以代替这个，因为，
(ab)² = a² + b² - 2ab
对于1和0的值，
a² + b² - 2ab = a + b - 2ab （对我而言，这是在代码中使用的最佳模型，原因有两个：1。）它比计算机更简单2.）更容易看到它背后的逻辑，因为a被添加到b，然后是完全否定（x2）它们的重叠a和b）
超越2个因素
你什么时候想要XOR（A，B，C ……）？ 这里的问题是，如果我们试图像在双因子XOR的复合逻辑中那样辨别所有真值条件，它就不能很好地扩展，因为你必须添加每个真值的排列。 然而，逻辑就是这样，我们可以免费获得XOR ……
XOR = !(A & B & C...) & !(!A & !B & !C...)
您可以从中以……的forms为任意数量的因子构造算术XOR。
(1 - A*B*C...)(1 - (1-A)(1-B)(1-C)...)
有趣的乐趣……想要测试一下吗？ 这里有一些Excel VBA可以对整个范围的单元格进行异或…
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
得到模糊
有趣的是停下来思考一下，如果我们使用上面的多因子方程得到一个双因子方程式，我们得到以下结果……
a + b - ab(1 + a + b - ab)
首先要注意的是，这与我们从真实条件中得出的2因子方程相似但不相等…
1 - (1 - a(1-b))(1 - b(1-a)) = a + b - ab(3 - a - b + ab)
事实上，区别在于……
1 + a + b - ab ≠ 3 - a - b + ab
什么赋予了什么？ 我认为这是使用赞美的算术神器。 如果你注意到，这两个术语相互补充，它们从不同的方向做同样的事情：一个从1升到2，另一个从3降到2.两者都到达2，但他们的到达方向不同，因为他们正在接近恭维。
需要注意的第二点是，两个方程都比x + y - 2xy和(xy)²等最小方程复杂得多。 这是否意味着什么，这增加了复杂性是否有任何价值？
显然，为此，您必须关注离散点（0,0），（0,1），（1,0）和（1,1）之外的十进制值。 这为什么会这么重要？ 有时您希望放宽离散问题的整数约束。 在这种情况下，您必须查看用于将逻辑运算符转换为方程的前提。
在将布尔逻辑转换为算术时，您的基本构建块是AND和NOT运算符，您可以使用它们构建OR和XOR 。
OR = (1-(1-a)(1-b)(1-c)...)
XOR = (1 - a*b*c...)(1 - (1-a)(1-b)(1-c)...)
因此，如果您正在考虑小数区域，那么值得思考我们如何定义这些运算符以及它们在该区域中的行为方式。
翻译NOT
我们表示NOT 1-x 。 显然，这个简单的等式适用于0和1的二进制值，但真正酷的是它还为0到1之间的值提供了分数或百分比的补码。这很有用，因为NOT也被称为布尔逻辑中的Compliment ，当涉及到集合时， NOT指的是当前集合之外的所有内容。
翻译AND
我们将AND表示为x*y 。 再一次，显然它适用于0和1，但是对于0到1之间的值，它的效果更加随意，其中乘法导致部分真值（十进制值）相互减小。 可以想象你想要将真相模拟为在该区域中的平均或累积。 例如，如果两个条件假设为半真，则AND条件仅为四分之一真（0.5 * 0.5），或者它是完全正确（0.5 + 0.5 = 1），还是保持半真（（0.5 + 0.5）） / 2）？ 事实certificate，对于完全离散且部分真理代表概率的条件，四分之一真理实际上是正确的。 例如，你现在和第二次翻转尾巴（二进制条件，50％概率）吗？ 答案是0.5 * 0.5 = 0.25，或25％为真。 累积并不真正有意义，因为它基本上是对OR条件进行建模（记住OR可以在AND条件不存在时通过+建模，因此求和特征为OR ）。 如果您正在查看协议和度量，那么平均值是有意义的，但它实际上是对AND和OR的混合建模。 例如，要求2个人以1到10的等级说出他们对“外面很冷”的说法多少赞同？ 如果他们都说5，那么“外面很冷”这句话的真实性是50％。
这里带走的是，如果放宽整数约束，则对小数区域有一些含义。 您可能希望这样做以使离散问题更容易/可能解决。 您需要考虑价值在这个区域如何相互作用以及它们如何被转换回来。
k的任何一个
最后一点消息。 如果任意n个输入为真，有时您希望条件为真。 这可以被视为一种放松的AND条件，例如，您愿意接受a＆b或a＆c或b＆c。 这可以从复合逻辑算术建模……
(a && b) || (a && c) || (b && c) ...
并应用我们的翻译……
1 – （1-ab）（1-ac）（1-bc）……
这对它本身很有用，但是当你扩展这些术语时，也有一个有趣的模式。 有一个变量和指数组合的模式，但这会变得很长; 但是，您可以通过忽略二进制上下文的权限来简化。 确切的模式取决于n与k的关系。 对于n = k-1，其中k是被测试条件的总数，结果如下：
c1 + c2 + c3 … ck – n *Π
其中c1到ck都是n变量组合。
例如，如果满足4个条件中的3个则为真
abc + abe + ace + bce – 3abce
这具有完美的逻辑意义，因为我们所拥有的是AND条件的加性OR减去重叠的AND条件。
如果你开始看n = k-2，k-3等等。模式变得更复杂，因为我们有更多的重叠来减去。 如果这完全扩展到n = 1的最小值，那么我们只得到一个正常的OR条件。
异或是线性函数，但关于布尔函数的“线性”的定义与多项式函数的定义不同。 您将不得不浏览lp_solve库的文档，看看它是否能够处理线性布尔函数。 从我所读到的，我不怀疑它可以。
编辑：在进一步研究lp_solve使用的单纯形算法lp_solve ，我相当肯定你不能做你想要做的事情。
ABS（A + B-1）。 如果它不做abs，则（A + B-1）*（A + B-1）应该这样做。