XOR使用数学运算符

Question

如何使用+, - ,*,/等基本数学运算符实现XOR

更新:实际上,我需要跟踪具有布尔值的两个矩阵的变化.这可以使用XORing每个值与其他矩阵中的对应值来完成.但是,Lp_Solve库不支持XOR操作.此外,它只接受线性方程.

Answer 1

(a - b)²

这是因为:

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

由于ℤ2中的乘法是conjuction(&),并且1 - a是否定(!),因此上述公式相当于XOR a, b ? {0, 1}:

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

请参阅Pascal Cuoq下面的评论,解释为什么这不能是一个线性方程式.

Answer 2

我能想出的最简单的表达方式是:a != b.

(以前的最佳努力是(a + b) == 1)

Answer 3

TL; 博士

XOR 任何数字输入

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

异或二进制输入

a + b - 2ab 或者 (a-b)²

推导

基本逻辑运算符

NOT = (1-x)

AND = x*y

从这些运营商我们可以得到...

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

注意：如果 a 和 b 是互斥的，那么它们的and条件将始终为零 - 从维恩图的角度来看，这意味着没有重叠。在那种情况下，我们可以写OR= a + b，因为a*b = 0对于 a & b 的所有值。

2 因子异或

将异或定义为(a OR B) AND (NOT (a AND b))：

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

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

AND 这些条件加在一起就可以得到...

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

计算替代方案

如果输入值是二进制的，则可以忽略幂项以获得简化的计算等效形式。

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

如果 x 是二进制的（1 或 0），那么我们可以忽略幂，因为1² = 1和0² = 0...

a + b - ab - a²b - ab² + a²b² -- 删除权限 --> a + b - 2ab

XOR （二进制） =a + b - 2ab

二进制还允许其他方程在计算上与上述方程等效。例如...

给定(a-b)²=a² + b² - 2ab

如果输入是二进制的，我们可以忽略幂，所以......

a² + b² - 2ab -- 删除权限 --> a + b - 2ab

允许我们写...

XOR （二进制） =(a-b)²

多因素异或

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

当你想要 XOR(A,B,C...) 时呢？这里的问题是，如果我们像在 2-factor XOR 的复合逻辑中那样尝试辨别所有真值条件，它就不能很好地扩展，因为您必须添加真值的每个排列。然而，逻辑就是这样，我们可以以互补的方式达到异或......

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

您可以从中以...的形式为任意数量的因子构造算术异或。

(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

k 中的任意 n

最后一个花絮在这里。有时，如果任意 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

这使得因为我们所拥有的是加完美的逻辑意义上OR的AND减号条件重叠的AND条件。

如果您开始查看 n = k-2、k-3 等。模式变得更加复杂，因为我们有更多的重叠要减去。如果这完全扩展到 n = 1 的最小值，那么我们只会得到一个常规OR条件。

关于非二元值和模糊区域的思考

实际的代数 XOR 方程a + b - ab(1 + a + b - ab)比计算等效的二元方程（如x + y - 2xy和 ）复杂得多(x-y)²。这有什么意义吗，这种增加的复杂性有什么价值吗？

显然，为此，您必须关心离散点 (0,0)、(0,1)、(1,0) 和 (1,1) 之外的十进制值。为什么这会很重要？有时您想放宽离散问题的整数约束。在这种情况下，您必须查看用于将逻辑运算符转换为方程的前提。

在将布尔逻辑转换为算术时，您的基本构建块是ANDandNOT运算符，您可以使用它构建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)？事实证明，四分之一真值对于完全离散的条件实际上是真的，部分真值代表概率。例如，您现在和第二次是否会翻转尾部（二元条件，50% 的概率）？答案是 0.5 * 0.5 = 0.25，或 25% 正确。累积实际上没有意义，因为它基本上是对OR条件建模（请记住OR，+当AND条件不存在时可以建模，因此总和是特征性的OR）。如果您查看一致性和测量值，则平均值是有意义的，但它实际上是对AND和的混合建模OR. 例如，请 2 个人从 1 到 10 的范围内说出他们对“外面很冷”这句话的同意程度如何？如果他们都说 5，那么“外面很冷”这句话的真实性是 50%。

非二进制值摘要

从这种非二进制值的角度来看，我们可以在选择运算符时捕捉实际逻辑并从头开始构建方程，但我们必须牢记数值行为。我们习惯于将逻辑视为离散（二进制）并将计算机处理视为离散，但非二进制逻辑正变得越来越普遍，并且可以帮助使离散逻辑难以解决的问题更容易/可能解决。您需要考虑价值观如何在该地区相互作用以及如何将它们转化为有意义的东西。

Answer 4

Weellllllllllll ........

它并不那么简单.

为了模拟XOR(我们称之为X),我们从逻辑开始.

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

在数学中,以上可以写成:

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

但是上面的表达式是非线性的(由于双线性项 - 为了保持线性,我们不允许将变量相互相乘).

但是!因为我们可以使用约束,所以我们可以用线性形式重写上面的表达式.

首先,我们扩展条款:

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"条件.

Answer 5

在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

Answer 6

你可以这样做:

(a + b) % 2