Mezclado Booleano Aritmética De Identidad

Question

Estoy tratando de demostrar que/se derivan de la equivalencia de la siguiente fórmula:

$$ x*y = (x \de la tierra y) * (x \lor y) + (x \de la tierra \neg y) * (\neg x \de la tierra y) $$

mientras que $(\land, \lor, \neg)$ corresponden a operaciones bit a bit sobre el álgebra Booleana ( $B^n, \land , \lor, \neg)$ , y las operaciones aritméticas son en números enteros modulares anillo de $Z/(2^n)$.

Reorganización mediante el uso de DeMorgan reglas me da: $x * (x \lor y) \land y * (x \lor y)$. Sin embargo, no puedo factor $(x \lor y)$ así que estoy atascado en ese punto. El problema parece ser, que todo esto es un no-lineal de la expresión.

Me encontré con esta identidad en este papel y se preguntaba cómo se podría derivar/generar tales identidades. Identidades similares se pueden encontrar en los Hackers Delicia capítulo 2 (y son mucho más simples, es decir, las combinaciones lineales de las 16 funciones booleanas).

Es porque el último término siempre es igual a cero? ¿Cómo se podía demostrar que? El último término no es siempre cero (por ejemplo,$1*524288$).

Ejemplo de $Z/2^{32}$

$$ 4 * 5 = (4 \de la tierra 5) * (4 \lor 5) + (4 \la tierra \lnot 5) * (\lnot 4 \de la tierra 5) \equiv (4) * (5) + (4 \la tierra 4294967290) * (4294967291 \de la tierra 5) \equiv (4) * (5) + (0) * (0) \equiv 20 $$

Actualización:

Vamos a dividir la fórmula en las dos partes para facilitar la referencia: $$ t0 = (x \de la tierra y) * (x \lor y) \\ t1 = (x \de la tierra \neg y) * (\neg x \de la tierra y) $$

He usado un SMT solver (z3) demostrar que para todos los valores de $x,y$ $t0$ o $t1$$\neq 0$, pero no ambos al mismo tiempo.

Contador de ejemplo: $x = 1431655427, y = 427$

Answer 1

Tenga en cuenta que han $x \land \neg y = x - x \land y$. El uso de este hecho

$$(x \land y) (x \lor y) + (x \land \neg y) (\neg x \land y) = x y$$

se convierte en

$$(x \land y) (x \lor y) + (x - x \land y) (y - x \land y) = x y$$

la expansión,

$$(x \land y) (x \lor y) + x y - (x + y) (x \land y) + (x \land y)^2 = x y$$

$$(x \land y) (x \lor y) - (x + y) (x \land y) + (x \land y)^2 = 0$$

Dividir por $x \land y$:

$$(x \lor y) - (x + y) + (x \land y) = 0$$

$$(x \lor y) + (x \land y) = x + y$$

Para demostrar esta igualdad, escriba $x$ $y$ en binario: $x = \sum_{i=0}^{n-1} x_i 2^i$ $y = \sum_{i=0}^{n-1} y_i 2^i$ donde $x_i, y_i \in \{0,1\}$. Tenga en cuenta que$x \land y = \sum_{i=0}^{n-1} \min (x_i, y_i) 2^i$$x \lor y = \sum_{i=0}^{n-1} \max (x_i, y_i) 2^i$. Queremos mostrar

$$\sum_{i=0}^{n-1} 2^i \max (x_i, y_i) + \sum_{i=0}^{n-1} 2^i \min (x_i, y_i) = \sum_{i=0}^{n-1} 2^i x_i + \sum_{i=0}^{n-1} 2^i y_i$$

que es el mismo que

$$\sum_{i=0}^{n-1} 2^i (\max (x_i, y_i) + \min (x_i, y_i)) = \sum_{i=0}^{n-1} 2^i (x_i + y_i)$$

pero para cualquier número $x_i, y_i$ tenemos $\max (x_i, y_i) + \min(x_i, y_i) = x_i + y_i$.