(a − b)²

Это работает, потому что:

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

Поскольку умножение в ℤ₂ является конъюкцией (&), а 1 - a является отрицанием (!), приведенная выше формула эквивалентна XOR для a, b ∈ {0, 1}:

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

См. ниже комментарий Паскаля Куока, объясняющий, почему это не может быть линейным уравнением.

Самое простое выражение, которое я могу придумать, это: a != b.

(Предыдущее лучшее усилие было (a + b) == 1)

В книге Браун Г. и Делл Р. Формулирование линейных и целочисленных линейных программ: галерея мошенников можно найти следующую формулировку линейного программирования для XOR:

Z3 = Z1 XOR Z2

решает

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

TL;DR

Исключающее ИЛИ любого числового ввода

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

Двоичный ввод XOR

a + b - 2ab or (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.

Двухфакторное исключающее ИЛИ

Определение XOR как (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...)? Проблема здесь в том, что если мы попытаемся различить все условия истинности, как мы это делали в составной логике для двухфакторного исключающего ИЛИ, масштабирование будет не очень хорошим, поскольку вам придется добавлять каждую перестановку истинности. Тем не менее, логика такова, что мы можем прийти к XOR комплементарным способом...

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

Из которого можно построить арифметическое XOR для любого количества факторов в виде...

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

Вот некоторый Excel VBA для XOR всего диапазона ячеек...

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

Любое n из 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 переменными.

Например, true, если выполняются 3 из 4 условий, будет

abc + abe + туз + 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). Почему это когда-либо имеет значение? Иногда вы хотите ослабить целочисленное ограничение для дискретной задачи. В этом случае вы должны посмотреть на предпосылки, используемые для преобразования логических операторов в уравнения.

Когда дело доходит до перевода булевой логики в арифметику, вашими основными строительными блоками являются операторы 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)? Как оказалось, четверть истины на самом деле верна для полностью дискретных условий, а частичная истина представляет собой вероятность. Например, перевернете ли вы решку (бинарное условие, вероятность 50%) и сейчас, И снова во второй раз? Ответ: 0,5 * 0,5 = 0,25, или 25% правды. Накопление на самом деле не имеет смысла, потому что оно в основном моделирует состояние OR (помните, что OR может быть смоделировано с помощью +, когда условие AND отсутствует, поэтому суммирование характерно OR). Среднее значение имеет смысл, если вы смотрите на согласование и измерения, но на самом деле оно моделирует гибрид AND и OR. Например, попросите двух человек сказать по шкале от 1 до 10, насколько они согласны с утверждением На улице холодно? Если они оба говорят 5, то истинность утверждения На улице холодно составляет 50%.

Недвоичные значения в сводке

Вывод из этого взгляда на недвоичные значения заключается в том, что мы можем уловить реальную логику в нашем выборе операторов и построить уравнения с нуля, но мы должны помнить о числовом поведении. Мы привыкли думать о логике как о дискретной (бинарной) и компьютерной обработке как о дискретной, но небинарная логика становится все более и более распространенной и может помочь упростить/возможность решения сложных проблем с дискретной логикой. Вам нужно подумать о том, как ценности взаимодействуют в этой области и как преобразовать их во что-то значимое.

Нуууууууу........

Это не так просто.

Чтобы смоделировать 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. Теперь мы можем записать условие И следующим образом: (см. приведенную ссылку в формате PDF ниже)

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

Формулировка линейного исключающего ИЛИ

Наконец, давайте все вместе. Это ваша формулировка 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 моделируют логическое условие "И". По сути, в 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 точно моделируют условие «И».

Можете ли вы сделать что-то вроде:

(a + b) % 2

Исключающее ИЛИ является линейной функцией, но определение «линейный» в отношении булевой функции не совпадает с полиномиальной функцией. Вам придется просмотреть документацию по вашей lp_solve библиотеке, чтобы узнать, способна ли она обрабатывать линейные булевы функции. Из того, что я читал, я не подозреваю, что это возможно.

Редактировать: После дальнейшего изучения симплексного алгоритма, который использует lp_solve, я почти уверен, что вы не можете делать то, что пытаетесь сделать.

абс(А+В-1). если он не делает пресс, то (A+B-1)*(A+B-1) должен это делать.

вы можете использовать это:

Xor(n,x,y)=x+y - Pow(2,n+1)(этаж((x+y)/Pow(2,n+1)));

когда

x =› число в коллекции Z и положительное, x›=0

y =› число в коллекции Z и положительное, y›=0

n =› — длина бит данных, например, 32 или 64.

pow(2,3)=› 222

этаж(1,6594565)=1 или этаж(4562,21)=4562