La estructura profunda de las fórmulas lógicas

Question

Una pregunta de larga data a la que nunca encontré una respuesta concisa es:

¿Existe algo así como un estructura profunda de una fórmula de lógica proposicional, frente a su superficie comparativamente arbitraria de superficie?

Aquí, considero la lógica proposicional con las conectivas $\neg,\vee,\wedge,\rightarrow$ .

A nivel superficial está claro qué es una negación o una disyunción: una negación es de la forma $\neg (\phi)$ una disyunción es de la forma $(\phi)\vee(\varphi)$ y así sucesivamente.

Pero hay fórmulas equivalentes que no son del mismo tipo (la "estructura profunda" es un árbol de tipos):

• $\neg(\neg p) \equiv p $

• $(p \wedge q )\vee(p \wedge \neg q) \equiv p$

• $p \rightarrow q \equiv \neg p \vee q$

Por lo tanto, no se puede definir "es una fórmula del tipo X" sin más por "tiene una fórmula equivalente de la forma Y".

¿Existe eventualmente una regla sencilla para señalar un representante distinguido entre todas las fórmulas equivalentes que represente el tipo de una fórmula $\phi$ ? ¿Podría ser esta regla tan simple como "la fórmula con el mínimo número de variables, conectivos y ocurrencias de los mismos"?

¿O puede haber varias fórmulas con los mismos números mínimos, pero de distinto tipo?

Answer 1

Semántica del juego podría ser algo parecido a lo que estás buscando. Si tienes una fórmula y tomas todas las trazas de juego válidas para ella, y luego eliminas las jugadas que corresponden sólo a las visibles conectivos de la fórmula, manteniendo las que corresponden al átomos entonces es posible que el conjunto de trazos parciales que se obtiene pueda considerarse que codifica algún tipo de "estructura profunda" de la fórmula.

Ideas como éstas se han utilizado para razonar sobre la "equivalencia observacional" de las fórmulas, lo que suena como si estuviera al menos relacionado con lo que estás hablando.

Answer 2

Hay ciertamente formas normales de fórmulas proposicionales, por ejemplo CNF pero no creo que ningún particular La forma normal puede pretender ser la "única estructura profunda subyacente de las fórmulas a las que es equivalente". Al fin y al cabo, la sencillez de una fórmula depende sensiblemente de lo que pensemos hacer con ella.

Answer 3

Parece que estás hablando de una forma de elegir una estructura de superficie concreta para que sea la representación canónica de la fórmula.

Pero... ¿Es realmente necesario que la estructura profunda "se parezca" a una estructura superficial? Si no es así, todas las fórmulas de la lógica proposicional (clásica) pueden reducirse a una estructura profunda inequívoca en forma de tabla de verdad.

p  ¬(¬p)
-  -----
F  F
T  T

p  q  (p∧q)∨(p∧¬q)
-  -  ------------
F  F  F
F  T  F
T  F  T
T  T  T

p  q  p⊃q  ¬p∨q
-  -  ---  -----
F  F  T    T
F  T  T    T
T  F  F    F
T  T  T    T

Si quieres, puedes simplificar más la notación. Para $n$ construye una matriz de $n^2$ bits o una cadena de $n$ personajes de la serie $\{ ``F",`` T" \} -$ Por ejemplo, $(\lnot p \vee q)$ podría escribirse como 1 1 0 1 o 'TTFT' .

Por supuesto, el significado depende del orden de las filas y columnas de la tabla, así que para que no haya ambigüedad, necesitamos una convención: las columnas para las variables de entrada deben estar en orden alfabético de izquierda a derecha, y las filas dispuestas de manera que cuenten en binario desde $0$ a $n^2-1$ .

Por ejemplo, en la notación del lenguaje de programación J, 2b00 2b01 2b10 2b11 es la notación de base 2 para 0 1 2 3 y si se sustituye por F para 0 y T para 1 , puedes ver que así es como he ordenado los valores de $p$ y $q$ en las tablas anteriores.

Answer 4

"¿Existe eventualmente una regla sencilla para señalar un representante distinguido entre todas las fórmulas equivalentes que represente el tipo de una fórmula ϕ? ¿Podría esta regla ser tan simple como "la fórmula con el mínimo número de variables, conectivas y ocurrencias de las mismas"? "

No. La ley de conmutación es una verdad lógica. Es decir, [(p→(q→r)→(q→(p→r)] es una tautología. El resultado aquí hace imposible encontrar un representante tan distinguido en general, ya que junto con el modus ponens acaba implicando que (entre un sinfín de ejemplos posibles) [p→(q→r)] es equivalente a [q→(p→r)]. Pero, ambas fórmulas tienen el mismo número de variables, conectivas y ocurrencias de las mismas. Y 5 es el menor número posible de símbolos implicados aquí (en notación polaca) para cualquier fórmula que tenga tres variables... es decir, simplemente no puedes usar menos símbolos que 5 para representar una fórmula equivalente a [p→(q→r)], pero tal fórmula, en términos de lo que representa semánticamente, no es única. (y, por supuesto, ambas fórmulas son del tipo implicación)

Además, aunque ambos $\land$ y $\lor$ asociado, tienen aridad fija a través de las reglas de formación. En consecuencia, no existe un representante distinguido que sea único para los casos que sólo implican sólo conjunciones o sólo disyunciones. Por lo tanto, aunque se exija que la primera variable se etiquete siempre con el mismo símbolo, lo que hace que el razonamiento del párrafo anterior sea irrelevante, se seguirá teniendo [p $\land$ (q $\land$ r)] como no calificado como representante único y distinguido.

Answer 5

Si piensas en una "representación canónica de una fórmula", siguiendo la referencia de @Doug Spoonwood a notación de pulido y la referencia de @Peter Smith a Wittgenstein, podemos utilizar el Golpe de Sheffer .

Tenemos dos posibilidades:

(i) permanecer con la notación estándar de pulido : $D\phi\psi$ ;

en este caso, hemos minimizado el número de conectivas, y tenemos una fórmula como : $DpDpDDqqDpp$ .

(ii) En caso contrario (ver Wiki) :

ya que el único conectivo de esta lógica es $|$ el símbolo $|$ podría descartarse por completo, dejando sólo los paréntesis para agrupar las letras. Un par de paréntesis siempre debe encerrar un par de wffs. Ejemplos de teoremas en esta notación simplificada son $(p(p((qq)(pp))))$ .

¿Son esas representaciones único ? Yo creo que sí.

¿Son "legibles"? Creo que no.