¿Cómo verificar si tres números son iguales utilizando operadores lógicos (¡con una restricción!)?

Question

Por favor, lea a continuación, ya que hay una importante restricción a esta pregunta.

Piensa en un número como una matriz de 0 y 1. Los operadores lógicos que quiero utilizar son los habituales: AND, OR, XOR, NAND, NOT (negación o "!").

Para comprobar si DOS números a y b son iguales, basta con hacer

NOT(a XOR b)

Este será un array de 1's sólo si los dos números son iguales.

Así, para comprobar si tres números son iguales podría hacer simplemente

NOT(a XOR b) AND NOT(b XOR c)

Sin embargo, la restricción es que no puedo escribir ninguno de los números a,b,c más de una vez. Así que necesito algo similar a esto:

(a OPERADOR1 b) OPERADOR2 c,

donde cada uno de los números a,b,c aparecen exactamente una vez.

Estaré encantado de responder a las preguntas sobre el contexto de esta cuestión. Gracias de antemano.

Answer 1

Editar: Mi prueba no es válida, ya que me olvidé de $\mathtt{XOR}$ . Sin embargo, lo dejaré aquí, todavía puede ser útil para alguien.

Editar 2: Como no sé cómo arreglar simplemente este asunto, daré un breve argumento informal basado en la teoría de la información: con $x_i$ que se utiliza una sola vez, sólo tenemos 1 bit (la salida de alguna subexpresión) para transmitir 2 bits de información:

• si la comparación anterior tiene éxito,
• si estamos comparando con $0$ o a $1$ .

Es posible que $n = 2$ porque no necesitamos propagar el bit de "comparaciones previas exitosas" (no hay comparaciones previas). Si pudiéramos utilizar cada $x_i$ dos veces, sería posible que cualquier $n$ porque podríamos aplicar (0).

---

Esto es imposible. Como los diferentes índices/bits de los números de entrada se tratan de forma independiente, WLOG podemos asumir que toda la entrada $x_i \in \{0,1\}$ . Así que tenemos una secuencia $x_i$ y quiere construir una expresión lógica que sea equivalente a

$$\left(\forall i.\ x_i = 1\right) \lor \left(\forall i.\ x_i = 0\right), \tag{0}$$

de manera que cada $x_i$ se utiliza como máximo una vez. Se puede hacer para $n \leq 1$ pero imposible en caso contrario, es decir, para $n > 1$ . Supongamos que una función booleana $f(x_0,\ldots)$ utiliza $x_0$ sólo una vez, entonces $f$ está aumentando en $x_i$ o $f$ está disminuyendo en $x$ , más formalmente

$$\forall (x_i)\subset\{0,1\}^n.\ f(0,x_1,\ldots) \leq f(1,x_1,\ldots), \tag{1}$$

o

$$\forall (x_i)\subset\{0,1\}^n.\ f(0,x_1,\ldots) \geq f(1,x_1,\ldots). \tag{2}$$

La razón es que los operadores $\lor$ y $\land$ son monótonas y si $x_0$ se utiliza sólo una vez, entonces hay un número constante $k_0$ de negaciones en el camino. $\mathtt{NAND}$ es sólo $\mathtt{NOT} \circ \mathtt{AND}$ y si $k_0$ es par entonces (1), y para $k_0$ impar tenemos (2).

Por simetría, es lo mismo para $x_i$ para cualquier $i$ . Sin embargo, el funcionamiento deseado $equiv(x_0,x_1,x_2)$ no cumple (1) o (2), por ejemplo

\begin{align} equiv(0,0) &= 1 \\ equiv(1,0) &= 0 \\ equiv(0,1) &= 0 \\ equiv(1,1) &= 1 \end{align}

Concluyendo, $equiv(x_0,\ldots)$ para $n > 1$ no cumple (1) ni (2) y por tanto no es expresable en términos de $\lor, \land,\neg$ con variables que se utilizan una sola vez.

Espero que responda a su pregunta ;-)

Answer 2

Me temo que Not(a XOR b) AND NOT(b XOR c) es lo más conciso que vas a conseguir.

Es la expresión más compacta que devolverá $1$ si y sólo si $a = b = c$ . Todos los demás modos de expresar esto con las conectivas que enumeras implican múltiples apariciones de una o más de $a, b, c$ .

Si puede utilizar BOOLE ( $\Leftrightarrow$ ): entonces se puede limitar a una ocurrencia de cada uno de a, b, c:

$$a \Leftrightarrow b \Leftrightarrow c$$

---

Véase, por ejemplo: La elaboración de Wolfram

Answer 3

No hay ninguna expresión de la forma $(a *_1 b) *_2 c$ donde $a$ , $b$ y $c$ son bits arbitrarios y $*_1$ y $*_2$ son uno de los operadores a nivel de bits $and$ , $or$ , $xor$ o sus negaciones $nand$ , $nor$ y $nxor$ que se evalúa como verdadero siempre que $a = b = c$ . He utilizado un programa para probar que todas las posibles opciones de $*_1$ y $*_2$ no dará el resultado deseado en todos los casos.

https://gist.github.com/timjb/6587803

Answer 4

(a xor b)'.(b xor c)'
\= (a'b+b'a)'(b'c+c'b)'
\= (a'b+b'a+b'c+c'b)'
\= (b(a'+c')+b'(a+c))'
\= (b(a.c)'+b'(a'c')')'
\= (b xor (a y c))'