java - precedencia - XOR utilizando operadores matemáticos
operadores relacionales en java (8)
¿Cómo puedo implementar XOR usando operadores matemáticos básicos como +, -, *, /
Actualización: En realidad, necesito rastrear el cambio en dos matrices que tienen valores booleanos. Esto se puede hacer usando XORing cada valor con el valor correspondiente en otra matriz. Pero, la biblioteca Lp_Solve no admite la operación XOR. Además, solo acepta ecuaciones lineales.
(a - b) ²
Esto funciona porque:
(a − b)² = a * (a − b) + b * (b − a)
Dado que la multiplicación en ℤ₂ es conjunción ( & ), y 1 - a es negación ( ! ), La fórmula anterior es equivalente a XOR para a, b ∈ {0, 1} :
(a & !b) | (b & !a)
Vea el comentario a continuación de Pascal Cuoq explicando por qué esto no puede ser una ecuación lineal.
¿Puedes hacer algo como:
(a + b) % 2
En Brown, G. y Dell, R., Formulación de programas lineales y enteros lineales: en una galería de pícaros, se puede encontrar la siguiente formulación de programación lineal para XOR:
Z3 = Z1 XOR Z2
resuelve a
Z3 <= Z1 + Z2
Z3 >= Z1 - Z2
Z3 >= -Z1 + Z2
Z3 <= 2 - Z1 - Z2
Exclusive-OR es una función lineal, pero la definition de "lineal" con respecto a una función booleana no es la misma que con una función polinomial. Tendrá que revisar la documentación de su biblioteca lp_solve para ver si es capaz de manejar funciones booleanas lineales. Por lo que he leído, no sospecho que pueda.
Edición: después de analizar más a fondo el algoritmo símplex que usa lp_solve , estoy bastante seguro de que no puede hacer lo que está tratando de hacer.
La expresión más simple que se me ocurre es: a != b
(El mejor esfuerzo anterior fue (a + b) == 1 )
Weellllllllllll ........
No es tan simple como eso.
Para modelar un XOR (llamémoslo X), comenzamos con la lógica.
X = (A & !B) | (!A & B)
En matemáticas, lo anterior se puede escribir como:
X = A*(1-B) + B*(1-A)
Pero la expresión anterior es no lineal (debido a los términos bilineales: para preservar la linealidad, no se nos permite multiplicar variables entre sí).
Pero ! Debido a que se nos permite usar restricciones, podemos reescribir la expresión anterior en forma lineal.
Primero, ampliamos los términos:
X = A*(1-B) + B*(1-A) = A + B - 2*A*B
Ahora debemos ocuparnos del término A * B (que esencialmente significa A y B). Deje que una variable H represente la condición lógica A y B. Ahora podemos escribir la condición AND de la siguiente manera: (vea el PDF de referencia citado a continuación)
H <= A
H <= B
H >= A + B - 1
H >= 0
Formulación lineal XOR
Finalmente, pongamos todo junto. Esta es su formulación XOR, utilizando solo restricciones lineales.
X = A + B - 2*H
H <= A
H <= B
H >= A + B - 1
H >= 0
Sé que parece complicado (para una operación simple como un XOR). Puede haber una formulación más compacta.
Pero en general, la escritura de condiciones lógicas en un contexto de programación lineal es complicada porque, por lo general, una de las operaciones que se pueden realizar es muy restringida, para evitar destruir las propiedades teóricas del problema.
Referencia
Vea aquí una lista de formulaciones de enteros estándar para representar la lógica linealmente. http://brblog.typepad.com/files/mipformref-1.pdf
Editar :
Explicación sobre cómo las restricciones H modelan la condición lógica "Y" . Esencialmente, en un LP, planteamos restricciones de desigualdad que deben satisfacerse en el punto de solución; lo que estamos haciendo aquí es jugar un truco para "exprimir" H al valor correcto. Por ejemplo, dada la tupla (A, B) = (0,0), las restricciones para H serían:
H <= 0
H <= 0
H >= -1
H >= 0
En el caso anterior, el único valor que H puede tomar es 0, porque H pertenece al intervalo [0,0]. Por lo tanto obtenemos (A, B) = (0,0) => H = 0.
Probemos con otro ejemplo, (A, B) = (1,1).
H <= 1
H <= 1
H >= 1
H >= 0
De lo anterior, verá inmediatamente que 1 <= H <= 1 implica que H = 1. Obtenemos (A, B) = (1,1) => H = 1.
Y así. Verá que las restricciones H modelan exactamente la condición "Y".
abs (A + B-1). si no hace abdominales, entonces (A + B-1) * (A + B-1) debería hacerlo.
2 Factor XOR
Mientras que (xy)² es una gran ecuación compacta para XOR de 2 factores, esta forma es engañosa de varias maneras.
Aunque la evaluación de estas ecuaciones es la misma para los valores de 1 y 0, no son algebraicamente iguales ...
(a − b)² ≠ a * (1 − b) + b * (1 − a)
Además, el operador lógico OR no se traduce aritméticamente como + sin restricciones. Eso le daría un valor de 2 para la condición AND de dos 1. Si primero considera las traducciones de NOT y AND ...
NOT = (1-x)
AND = x*y
Lo que realmente necesitas es algo como esto ...
OR = (1-(1-a)(1-b)) = a + b - ab
Tenga en cuenta que, característicamente, OR es puramente aditivo, por lo que ha unido dos conjuntos, PERO no quiere duplicar ninguna superposición de los conjuntos, por lo que resta la condición AND que se encuentra al multiplicar. Por lo tanto, tiene su término aditivo a+b menos su superposición o condición AND a*b . Si está seguro de que sus conjuntos no se superpondrán, entonces puede usar
OR = a + b , si sabemos que a*b = 0 para todos los valores de a y b
Del mismo modo, podemos derivar una ecuación para XOR. Usando la lógica compuesta (a && !b) || (!a && b) (a && !b) || (!a && b) obtendrías ...
XOR = 1 - (1 - a(1-b))(1 - b(1-a)) ≠ (ab)²
Entonces (ab)² es algo engañoso en su traducción de lógica y álgebra. Como resultado, estos errores se enmascaran por la restricción de la entrada binaria y porque las condiciones a(1-b) y b(1-a) son mutuamente excluyentes, lo que relaja la restricción del operador OR que maneja la condición AND y permite para ser modelado como + .
La respuesta de Gilead ayuda a explicar por qué (xy)² realmente funciona. Cuando x² + y² - 2xy (xy)² = x² + y² - 2xy puedes ver cómo satisface este modelo básico ...
X = A + B - 2*H
H <= A
H <= B
H >= A + B - 1
H >= 0
Usando ese poco de conocimiento, puedes ver que hay una serie de ecuaciones que funcionarán. Por ejemplo, la ecuación más básica real que satisface estas condiciones es ...
x + y - 2xy
Esta es exactamente la misma que la ecuación a la que llegamos para OR excepto que ahora no solo eliminamos el duplicado de la condición AND ( -xy ), sino que rechazamos la condición AND completo ( -2xy ). Como resultado, este también es el equivalente algebraico real para (ab)² ...
a * (1 − b) + b * (1 − a) = a + b - 2ab ≠ (ab)² .
(ab)² se puede usar en lugar de esto porque,
(ab)² = a² + b² - 2ab
y para valores de 1 y 0,
a² + b² - 2ab = a + b - 2ab (para mí, este es el mejor modelo para usar en el código por dos razones: 1.) Es computacionalmente más simple que usar las potencias 2.) Es más fácil ver la lógica detrás de él , dado que a se agrega a b seguido de la negación completa (x2) de su superposición a y b)
Más allá de 2 factores
¿Qué pasa cuando quieres XOR (A, B, C ...)? El problema aquí es que si tratamos de discernir todas las condiciones de verdad como lo hicimos en la lógica compuesta para el XOR de 2 factores, no se ajusta muy bien, ya que tiene que agregar cada permutación de verdad. Sin embargo, dado que la lógica es lo que es, podemos llegar a XOR de manera gratuita ...
XOR = !(A & B & C...) & !(!A & !B & !C...)
Desde donde puede construir un XOR aritmético para cualquier número de factores en forma de ...
(1 - A*B*C...)(1 - (1-A)(1-B)(1-C)...)
divertido divertido ... quieres probarlo? Aquí hay algunos Excel VBA a XOR en toda una gama de celdas ...
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
Obteniendo borrosa
Es interesante detenerse y reflexionar por un segundo que si usamos la ecuación de factores múltiples de arriba para una ecuación de 2 factores obtenemos lo siguiente ...
a + b - ab(1 + a + b - ab)
Lo primero que se debe tener en cuenta es que esto es similar pero no igual a la ecuación de 2 factores que derivamos de las condiciones de verdad ...
1 - (1 - a(1-b))(1 - b(1-a)) = a + b - ab(3 - a - b + ab)
De hecho, la diferencia está en los siguientes términos ...
1 + a + b - ab ≠ 3 - a - b + ab
Entonces, ¿qué da? Creo que este es un artefacto aritmético del uso de cumplidos. Si se dan cuenta, estos dos términos se complementan, están haciendo lo mismo desde diferentes direcciones: uno sube de 1 a 2 y el otro baja de 3 a 2. Ambos llegan a 2, pero sus direcciones de llegada difieren porque Se están acercando como cumplidos.
La segunda cosa a tener en cuenta es que ambas ecuaciones son mucho más complicadas que las ecuaciones mínimas como x + y - 2xy y (xy)² . ¿Esto significa algo, y hay algún valor en esta complejidad agregada?
Obviamente, para que esto importe, debe preocuparse por los valores decimales fuera de los puntos discretos (0,0), (0,1), (1,0) y (1,1). ¿Por qué esto alguna vez importa? A veces desea relajar la restricción de enteros para un problema discreto. En ese caso, debe observar las premisas utilizadas para convertir los operadores lógicos en ecuaciones.
Cuando se trata de convertir la lógica booleana en aritmética, sus bloques de construcción básicos son los operadores AND y NOT , con los que puede construir tanto OR como XOR .
OR = (1-(1-a)(1-b)(1-c)...)
XOR = (1 - a*b*c...)(1 - (1-a)(1-b)(1-c)...)
Entonces, si está pensando en la región decimal, entonces vale la pena pensar en cómo definimos estos operadores y cómo se comportan en esa región.
Traduciendo NOT
No expresamos como 1-x . Obviamente, esta simple ecuación funciona para valores binarios de 0 y 1, pero lo que es realmente bueno es que también proporciona el complemento fraccionario o porcentual para valores entre 0 y 1. Esto es útil porque NOT también se conoce como El Compliment en la lógica booleana, y cuando se trata de conjuntos, NOT refiere a todo lo que está fuera del conjunto actual.
Traduciendo AND
Expresamos AND como x*y . Una vez más, obviamente funciona para 0 y 1, pero su efecto es un poco más arbitrario para valores entre 0 y 1, donde la multiplicación da como resultado verdades parciales (valores decimales) que disminuyen entre sí. Es posible imaginar que desearía modelar la verdad como promediada o acumulativa en esta región. Por ejemplo, si dos condiciones hipotéticamente son mitad verdaderas, ¿es la condición AND solo una cuarta parte (0.5 * 0.5), o es completamente verdadera (0.5 + 0.5 = 1), o permanece la mitad verdadera ((0.5 + 0.5)? / 2)? Resulta que la verdad del cuarto es en realidad cierta para las condiciones que son completamente discretas y la verdad parcial representa la probabilidad. Por ejemplo, ¿volteará las colas (condición binaria, 50% de probabilidad) ahora y otra vez por segunda vez? La respuesta es 0.5 * 0.5 = 0.25, o 25% verdadera. La acumulación realmente no tiene sentido porque básicamente es un modelo de una condición OR (recuerde que OR puede ser modelado por + cuando la condición AND no está presente, por lo que la suma es característicamente OR ). El promedio tiene sentido si se busca acuerdo y medidas, pero en realidad se trata de un modelo híbrido de AND y OR . Por ejemplo, pida a 2 personas que digan en una escala de 1 a 10 ¿en qué medida están de acuerdo con la afirmación "Hace frío afuera"? Si ambos dicen 5, entonces la verdad de la afirmación "Hace frío afuera" es del 50%.
Lo que se quita aquí es que, si se relajan las restricciones de enteros, entonces la región decimal tiene algún significado. Es posible que desee hacer esto para facilitar / resolver posibles problemas discretos. Deberá reflexionar sobre cómo interactúan los valores en esta región y cómo se volverán a convertir.
Cualquier n de k
Un último detalle aquí. A veces desea que una condición sea verdadera si cualquier número n de entradas es verdadero. Esto puede verse como una condición relajada AND , por lo que está dispuesto a aceptar a & b o a & c o b & c, por ejemplo. Esto puede ser modelado aritméticamente desde la lógica compuesta ...
(a && b) || (a && c) || (b && c) ...
y aplicando nuestras traducciones ...
1 - (1-ab) (1-ac) (1-bc) ...
Eso es útil por sí solo, pero también hay un patrón interesante al expandir los términos. Hay un patrón de combinaciones de variables y exponentes, pero esto se vuelve muy largo; sin embargo, puede simplificar ignorando poderes para un contexto binario. El patrón exacto depende de cómo n se relaciona con k. Para n = k-1, donde k es el número total de condiciones que se están probando, el resultado es el siguiente:
c1 + c2 + c3 ... ck - n * ∏
Donde c1 a ck son todas las combinaciones de n variables.
Por ejemplo, es cierto si 3 de 4 condiciones cumplidas serían
abc + abe + ace + bce - 3abce
Esto tiene un sentido lógico perfecto, ya que lo que tenemos es la condición OR aditiva de AND menos la condición AND superpuesta.
Si comienza a mirar n = k-2, k-3, etc. El patrón se vuelve más complicado porque tenemos más superposiciones para restar. Si esto se extiende completamente al valor más pequeño de n = 1, entonces no llegamos a nada más que una condición OR normal.