Ответ 1

(a - b) ²

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

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

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

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

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

Ответ 2

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

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

Ответ 3

В Brown, G. и Dell, R., Формулируя линейные и целочисленные линейные программы: галерея мошенников можно найти следующую формулировку линейного программирования для XOR:

Z3 = Z1 XOR Z2

разрешает

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

Ответ 4

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

(a + b) % 2

Ответ 5

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 моделируют условие "И" точно.

Ответ 6

Эксклюзивный-OR является линейной функцией, но определение "linear" относительно булевой функции не совпадает с полиномиальная функция. Вам нужно будет просмотреть документацию для вашей библиотеки lp_solve, чтобы узнать, способна ли она обрабатывать линейные логические функции. Из того, что я прочитал, я не подозреваю, что это возможно.

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

Ответ 7

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

Ответ 8

2 Фактор XOR

Хотя (x-y)² является большим компактным уравнением для 2-факторного XOR, это раздражает меня тем, что объяснение от glebm неверно несколькими способами.

Хотя оценка этих уравнений одинакова для значений 1 и 0, они не являются алгебраически равными...

(a − b)² ≠ a * (1 − b) + b * (1 − a)

Кроме того, логический оператор OR не выполняет арифметически как + без ограничений. Это даст вам значение 2 для условия AND двух 1. Если вы сначала рассмотрите переводы 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 = 0 для всех значений a и b

Аналогично, мы можем получить уравнение для XOR. Используя композитную логику (a && !b) || (!a && b), вы получите...

XOR= 1 - (1 - a(1-b))(1 - b(1-a)) ≠ (a-b)²

Таким образом, объяснение неверно в его переводе логики и алгебры. Как оказалось, эти ошибки маскируются ограничением двоичного входа и потому, что условия a(1-b) и b(1-a) являются взаимоисключающими, что ослабляет ограничение оператора OR, обрабатывающего условие AND, и позволяет ему быть смоделированным как +.

Ответ Gilead помогает объяснить, почему (x-y)² действительно работает. Когда вы развернете (x-y)²= 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). Как оказалось, это также фактический алгебраический эквивалент выражения glebm, упомянутого...

a * (1 − b) + b * (1 − a)= a + b - 2ab ≠ (a-b)².

(a-b)² можно использовать вместо этого, потому что

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

и для значений 1 и 0,

a² + b² - 2ab= a + b - 2ab

поэтому уравнение (a-b)² действительно просто использует два ограничения: упрощение оператора OR из-за взаимоисключающих членов, а также компактность и двоичную эквивалентность обозначения мощности для того, чтобы скомпилировать запись уравнения.

Помимо 2 факторов

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

Получение нечетких

Интересно остановиться и на секунду задуматься, что если мы используем многофакторное уравнение выше для 2-факторного уравнения, получим следующее...

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 и (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. Например, попросите 2 человека сказать по шкале от 1 до 10, насколько они согласны с утверждением "Холодно снаружи"? Если они оба скажут 5, то истина утверждения "Холодно снаружи" составляет 50%.

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

Любое n из k

Последний лакомый кусочек. Иногда вы хотите, чтобы условие было истинным, если любое число входов истинно. Это можно рассматривать как расслабленное условие AND, в соответствии с которым вы соглашаетесь, например, с помощью & b или или 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 + ace + bce - 3abce

Это имеет логичный смысл, поскольку у нас есть добавка OR условий AND минус перекрывающееся условие AND.

Если вы начнете смотреть на n = k-2, k-3 и т.д. Шаблон становится более сложным, потому что у нас больше совпадений, чтобы вычесть. Если это полное расширение до наименьшего значения n = 1, то мы приходим к не более чем к регулярному условию OR.