Número de soluciones para una ecuación lógica dada

Question

Me encontré con la siguiente pregunta mientras estudiaba lógica y no puedo encontrar una solución para ella en ninguna parte. Estoy estudiando por mi cuenta y creo que no conozco exactamente los términos adecuados para buscarla en internet (no estoy seguro de que se llame ecuación lógica así que disculpen el título de esta pregunta en caso de que no lo sea):

---

Dada la proposición $P$ su valor lógico se define como $[P] = 0$ , en caso de que $P$ es falso, y $[P] = 1$ , en caso de que $P$ es cierto.

Consideremos las siguientes sentencias abiertas definidas en el conjunto de los números enteros:

$ P_i(x): x \le 5$

$ P_{ii}(x): x \ge 3$

$ P_{iii}(x): $ x es impar

$ P_{iv}(x): x \ge 6$

¿Cuántas soluciones tiene la siguiente ecuación?

$ x = [P_i(x)] + 2 \cdot[P_{ii}(x)]+3\cdot[P_{iii}(x)]+4\cdot[P_{iv}(x)]$

---

He hecho esto jsfiddle y a partir de ahí, puedo contar el número de soluciones a través de un bucle. En este caso he hecho un bucle de 0 a 1000 y se obtienen 2 soluciones. Aunque puedo razonar claramente que no sería posible que un número muy grande funcionara aquí, ya que son todas sumas de multiplicaciones de 0s o 1s, me cuesta articular exactamente el porqué. ¿Cómo se podría encontrar el mayor número posible, en este caso tan específico? ¿Así que no tendrías que hacer un bucle a través de los valores de X demasiado lejos de él?

Answer 1

En primer lugar, observemos que $[P_i(x)]+4\cdot[P_{iv}(x)]=1+3\cdot[P_{iv}(x)]$ . Podemos comprobar tres casos:

1. $x<3$ : Nuestra ecuación se convierte en $x=1+3\cdot(x\%2)$ donde $\%$ es el operador mod. Está claro que ningún número par puede satisfacer esta ecuación, y tampoco un número impar. Por lo tanto, $x\geq3$ .

2. $3\leq x<6$ Podemos convertir la ecuación en $x=3+3\cdot(x\%2)$ . De nuevo, ningún número par o impar puede satisfacer esta ecuación, así que pasamos al caso tres.

3. $x\geq6$ Como sabemos que cualquier solución debe satisfacer esto, podemos convertir la ecuación en $6+3\cdot(x\%2)$ . Así que, $x=6$ y $x=9$ son soluciones.

Por lo tanto, hay $\color{red}{2}$ soluciones a esta ecuación.

Answer 2

Así es como se codificaría este problema en el formato SMT-LIB, entendido por la mayoría de los solucionadores SMT.

(define-fun Pi ((x Int)) Int (ite (<= x 5) 1 0))
(define-fun Pii ((x Int)) Int (ite (>= x 3) 1 0))
(define-fun Piii ((x Int)) Int (mod x 2))
(define-fun Piv ((x Int)) Int (ite (>= x 6) 1 0))
(declare-const x Int)
(assert (= x (+ (Pi x) (* 2 (Pii x)) (* 3 (Piii x)) (* 4 (Piv x)))))
(check-sat)
(get-model)
(assert (not (= x 6)))
(check-sat)
(get-model)
(assert (not (= x 9)))
(check-sat)
(exit)

Tras obtener la primera solución, añadimos una restricción que prohíba esa solución y volvemos a resolver. Cuando lo hacemos de nuevo, el solucionador SMT informa de que las restricciones son ahora insatisfactorias; por lo tanto, sabemos que hemos enumerado todas las soluciones.

Answer 3

Otras respuestas muestran cómo obtener una solución completa, con un poco de reflexión/trabajo. Pero una observación muy rápida que reduce las posibilidades es que ya que las funciones lógicas sólo pueden tomar valores $0$ y $1$ el lado derecho no puede ser mayor que $1 + 2\cdot1 + 3\cdot1 + 4\cdot1 = 10$ y no puede ser inferior a $0$ . Por lo tanto, los únicos valores que hay que probar para $x$ son $\{0, 1, …, 10\}$ .

Esto es algo en lo que siempre vale la pena pensar: cuando una función compleja (como el lado derecho aquí) se construye a partir de otras funciones, si se conocen las restricciones/límites de las piezas con las que se construye, entonces éstas a menudo darán restricciones/límites a la función compleja.

(Justificando los límites en detalle: si $a \geq 0$ y $0 \leq b \leq 1$ entonces $0 \leq ab \leq a$ . Así que $0 \leq 2\cdot [P_2(x)] \leq 2$ y así sucesivamente; por lo que para cualquier $x$ , $$0 = 0 + 0 + 0 + 0 \leq [P_1(x)] + 2\cdot [P_2(x)] + 3\cdot [P_3(x)] + 4\cdot [P_4(x)] \leq 1 + 2 + 3 + 4 = 10$$ y por lo tanto, en particular, si $x = [P_1(x)] + 2\cdot [P_2(x)] + 3\cdot [P_3(x)] + 4\cdot [P_4(x)]$ entonces $0 \leq x \leq 10$ .)

Answer 4

Además de la respuesta de @Rushabh Mehta:

nota que $[P_i]$ puede considerarse como una función "clásica" (también conocida como Pre-Cálculo). Por ejemplo, $f_1=[P_1]$ es simplemente la función $$f_1(x)=[P_1(x)]=\left\{ \begin{array}{rl} 1, & x \leqslant 5 \\ 0, &x>5 \end{array} \right.$$

Por lo tanto, se puede estudiar la ecuación dada $x=f_1(x)+2f_2(x)+3f_3(x)+4f_4(x)$ utilizando todas las técnicas que ya conoces para este tipo de problemas: considerar los casos (como en la respuesta de Rushabh Mehta), dibujar el gráfico cuidadosamente,...