Fórmula proposicional para representar un conjunto de cadenas binarias

Question

Me estoy "familiarizando" con la lógica matemática y he encontrado un ejercicio en Internet cuya solución no entiendo. Se pide la representación más compacta de un conjunto de cadenas binarias

{000000),(100000),(110000),(111000),(111100),(111110),

(111111),(011111),(001111),(000111),(000011),(000001)}

como una fórmula proposicional. Se da una posible solución: $$ \bigvee_{k=0}^5 \left( \biggl( \bigwedge_{i=0}^k \neg b_i \land \bigwedge_{i=k+1}^5 b_i \biggr) \lor \biggl( \bigwedge_{i=0}^k b_i \land \bigwedge_{i=k+1}^5 \neg b_i \biggr) \right) $$

Primero pensé que se trataba de algo sobre uniones de conjuntos arbitrarios (por la notación que recuerda), lo investigué, pero no encontré nada con respecto a algún "anidado". Supongo que esto demuestra lo rudimentaria que es mi comprensión de todo el tema. Pensé que la clave estaba en cómo se evaluaba la expresión completa, porque tenía ese aspecto anidado en su estructura, pero tampoco entiendo cómo actúan las conectivas en esto.

¿Puede alguien explicarme qué está pasando? Además, ¿cómo puedo saber lo que debería buscar, cómo debería enfocar generalmente un problema así? Supongo que tener un buen recurso que le proporcione a uno una base firme es el primer paso. ¿Tienes alguna recomendación que cubra la lógica matemática y la teoría de conjuntos, o incluso mejor que ilumine sus interconexiones?

Answer 1

La clave que hay que entender aquí es que, lo que has citado es no es realmente una fórmula proposicional . Cosas como " $\bigwedge\limits_{i=0}^k$ " son no ellos mismos parte de la sintaxis de las fórmulas proposicionales.

En cambio, lo que tienes es una receta abreviada de cómo construir una fórmula. El actual La fórmula que la notación le pide que imagine es bastante larga; comienza con

$$ \big( (\neg b_0 \land (b_1 \land b_2 \land b_3 \land b_4 \land b_5)) \lor (b_0 \land (\neg b_1 \land \neg b_2 \land \neg b_3 \land \neg b_4 \land \neg b_5) ) \big ) \\ \lor \big( ((\neg b_0 \land \neg b_1) \land (b_2 \land b_3 \land b_4 \land b_5)) \lor ((b_0 \land b_1) \land (\neg b_2 \land \neg b_3 \land \neg b_4 \land \neg b_5) ) \big ) \\ \lor \big( ((\neg b_0 \land \neg b_1 \land \neg b_2) \land (b_3 \land b_4 \land b_5)) \lor ((b_0 \land b_1 \land b_2) \land (\neg b_3 \land \neg b_4 \land \neg b_5) ) \big ) \\ \vdots$$

Obsérvese que esta fórmula "desplegada" sólo contiene conjunciones y disyunciones binarias ordinarias, y no contiene las variables ficticias $k$ y $i$ que sólo se utilizaron como una forma de describir la enorme fórmula de forma que quepa en una sola línea.

También observará que la enorme fórmula no es especialmente inteligente: sólo contiene una disyuntiva para cada una de las cadenas que deben aceptarse, y en efecto dice "acepta esta cadena, y acepta esta cadena, y acepta esta cadena...".

El ejercicio debe consistir en encontrar algo mejor que eso (lo que requiere cierta astucia). Encontrar el mejor La representación parece ser bastante dura y probablemente no se espera.

Answer 2

Las cadenas de interés como las que aumentan o disminuyen. Escribir $x \Rightarrow y$ como abreviatura de $\lnot x \lor y$ se pueden caracterizar de la siguiente manera compacta: $$ \begin{align*} &[(b_1 \Rightarrow b_2) \land (b_2 \Rightarrow b_3) \land (b_3 \Rightarrow b_4) \land (b_4 \Rightarrow b_5)]\\ \lor \quad&[(b_5 \Rightarrow b_4) \land (b_4 \Rightarrow b_3) \land (b_3 \Rightarrow b_2) \land (b_2 \Rightarrow b_1)] \end{align*} $$

Si se le pide que demuestre que se trata de la representación más compacta, entonces habrá que trabajar un poco más.