Как я могу реализовать XOR, используя базовые математические операторы, такие как +, -, *,/
Ответ 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 моделируют условие "И" точно.
Ответ 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
.