Lo complicado es el conjunto de tautologías?

Question

Consideremos el conjunto a $\mathcal T$ de todas las tautologías en el cálculo proposicional en la que únicamente los operadores permitidos $\to$$\neg$, y la participación de sólo dos variables $x$$y$.

Lo complicado es $\mathcal T$? Es un contexto libre de idioma?

La respuesta dependerá de la fija el número de variables? Supongo que no... Si se quita la limitación del número de variables (y de alguna manera se adapta a las nociones de contexto-libertad para jugar bien con esto...), hace que la respuesta al cambio? Supongo que sí...

Esta pregunta es un resultado natural de Doug recientes pregunta aquí.

Answer 1

Sí, es independiente del contexto. Una fórmula es un árbol, la cual se puede recorrer con una pila. Como los que atravesamos, estamos evaluando cuatro cosas:

• x = 0, y = 0;
• x = 0, y = 1;
• x = 1, y = 0;
• x = 1, y = 1.

En efecto, estamos evaluando cuatro "probados de las fórmulas" en paralelo. Corroborada de fórmula uno con las variables reemplazado por 0 o por 1.

Seamos más precisos y definir la tabla de transición. Suponemos que la fórmula está en pre-orden, es decir, el operador antes de los operandos.

• El estado inicial:
  • Si el símbolo actual es "$\lnot$", empujar a la pila el símbolo "($\lnot$, operador de, ?, ?, ?, ?)" y vaya a su estado inicial.
  • Si el símbolo actual es "$\to$", empujar a la pila el símbolo "($\to$, operador de, ?, ?, ?, ?)" y vaya a su estado inicial.
  • Si el símbolo actual es "x", vaya a la (0, 0, 1, 1) estado.
  • Si el símbolo actual es "y", vaya a la (0, 1, 0, 1) estado.
• El (a, b, c, d) estado:
  • Si la parte superior el símbolo de la pila es "($\lnot$, operador de, ?, ?, ?, ?)", pop de la pila y vaya a la ($\lnot$a, $\lnot$b, $\lnot$c, $\lnot$d) estado.
  • Si la parte superior el símbolo de la pila es "($\to$, operador de, ?, ?, ?, ?)", pop de la pila push "($\to$, primer operando, a, b, c, d)", ir al estado inicial.
  • Si la parte superior el símbolo de la pila es "($\to$, primer operando, e, f, g, h)", el pop de la pila, vaya a la (e $\to$ a, f $\to$ b, g $\to$ c, h $\to$ d) estado.

El (a, b, c, d) el estado es una plantilla. En realidad, hay 16 de estos estados: el (0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 1, 0), (0, 0, 1, 1) estado y así sucesivamente.

Del mismo modo, la regla de la tercera parte en el genérico (a, b, c, d) el estado es una regla genérica. Hay 16 de tales normas, con (e, f, g, h) = (0, 0, 0, 0), (0, 0, 0, 1), y así sucesivamente.

El (1, 1, 1, 1) el estado tiene una regla:

• Si la pila está vacía, ir a la aceptación de un estado.

---

OK, este programa tiene un punto débil como se discutió en el segundo comentario. Ahora vamos a definir una versión perfecta.

Asumir dos cosas: 1) La fórmula está en pre-orden, y 2) hay un par de paréntesis alrededor de cada sub-fórmula.

Ahora, la tabla de transición:

• inicio:
  • si = (, vaya al operador.
• operador:
  • si leer = ~, empuje (~, ?, ?, ?, ?), ir a inicio.
  • si leer = ->, empuje (->, ?, ?, ?, ?), ir a inicio.
  • si leer = x, push (ret, 0, 0, 1, 1), ir a eval.
  • si leer = y, push (ret, 0, 1, 0, 1), ir a eval.
• eval:
  • si leer = ), vamos a la parte superior del elemento de ser (ret, a, b, c, d), pop, vaya a (a, b, c, d).
• (a, b, c, d):
  • si leer = ) y la parte superior = (~, ?, ?, ?, ?), pop, vaya a (~a, ~b, ~c, ~d).
  • si leer = ) y top = (->, e, f, g, h), el pop, vaya a (e -> f -> b, g -> c, h -> d).
  • si = ( y superior = (->, ?, ?, ?, ?), pop, push (->, a, b, c, d), vaya al operador.
• (1, 1, 1, 1) tiene una regla:
  • si la pila está vacía, aceptar.

Answer 2

Para un número fijo de variables de contexto libre, independientemente del número exacto de las conectivas utilizado. Para mostrar esto, vamos a construir una gramática independiente del contexto para el conjunto de tautologías.

Deje que el número de variables se $n$. Para cada una de las $f\colon \{0,1\}^n \rightarrow \{0,1\}$, le corresponde un no-terminal de la $S_f$ generación de todas las fórmulas en la tabla de verdad de $f$. La partida símbolo es $S_1$ donde $1$ es la constante de $1$ función.

Para su conectivas, aquí es el de la construcción. Para cada función de proyección de $p_i$, añadimos la producción $$S_{p_i} \rightarrow x_i$$ ($x_i$ is a variable). For each $f$, we add the production $$S_f \rightarrow \lnot S_{1-f}.$$ For each $f_1,f_2$, we add the production $$S_{1-f_1(1-f_2)} \rightarrow S_{f_1} \Rightarrow S_{f_2}.$$

Ahora, considere el caso de un número infinito de variables. Si hubo una CFG para el conjunto de todas las tautologías (con algún capricho de codificación), entonces usted podría decidir si una fórmula es una tautología en el polinomio de tiempo, por lo que P=NP.

Más al punto, supongamos que la codificación de nosotros desea utilizar cadenas en algunos apropiado finito (alfabeto). Si el idioma de todas las tautologías fueron contexto libre, entonces así que $\{ x_i \Rightarrow x_i : i \in \mathbb{N} \}$ (se cruzan con un lenguaje regular). De ello se deduce que el lenguaje de los cuadrados de los dígitos es independiente del contexto, lo cual es falso.

Answer 3

La generalización de Yuval la respuesta:

Para cualquier conjunto finito $A$ y las operaciones de $o_i \colon A^2 \to A$ el lenguaje de expresiones de uso de elementos de $A$ y operadores de infijo $o_i$ que evaluar a fijos $a \in A$ es independiente del contexto. Aquí $A = \{0,1\}^n \to \{0,1\}$.

Si consideramos que las expresiones como árboles, sin palabras, va a ser un habitual de árbol (lenguaje reconocible con finito de árbol autómata).

Recuerdo que en un ejercicio de teoría de autómatas: el conjunto de fórmulas Booleanas (como las palabras) el uso de 0,1,$\vee$,$\wedge$,$\neg$,(,) la evaluación a 1 es regular, siempre que arbitraria respuesta es permitido cuando la entrada no coinciden entre corchetes.

Como consecuencia de esto debería de existir un lenguaje regular $L$ de manera tal que el conjunto de tautologías es $L \cap R$ donde $R$ es el contexto de un lenguaje libre de todos los bien formados fórmulas (tautologías o no).