5.4: Legibilidad única
- Page ID
- 103692
La forma en que definimos las fórmulas garantiza que cada fórmula tenga una lectura única, es decir, esencialmente solo hay una forma de construirla de acuerdo a nuestras reglas de formación para fórmulas y sólo una forma de “interpretarla”. Si esto no fuera así, tendríamos fórmulas ambiguas, es decir, fórmulas que tienen más de una lectura o interpretación —y eso es claramente algo que queremos evitar. Pero lo más importante, sin esta propiedad, la mayoría de las definiciones y pruebas que vamos a dar no pasarán por ellas.
Quizás la mejor manera de dejar esto claro es ver qué pasaría si hubiéramos dado malas reglas para formar fórmulas que no garantizarían una legibilidad única. Por ejemplo, podríamos haber olvidado los paréntesis en las reglas de formación para conectivos, por ejemplo, podríamos haber permitido esto:
Si\(A\) y\(B\) son fórmulas, entonces así es\(A \lif B\).
Partiendo de una fórmula atómica\(D\), esto nos permitiría formar\(D \lif D\). De esto, junto con\(D\), obtendríamos\(D \lif D \lif D\). Pero hay dos formas de hacerlo:
-
Tomamos\(D\) ser\(A\) y\(D \lif D\) ser\(B\).
-
Tomamos\(A\) para ser\(D \lif D\) y\(B\) es\(D\).
Correspondientemente, hay dos formas de “leer” la fórmula\(D \lif D \lif D\). Es de la forma\(B \lif C\) donde\(B\) está\(D\) y\(C\) es\(D \lif D\), pero también es de la forma\(B \lif C\) con\(B\) ser\(D \lif D\) y \(C\)siendo\(D\).
Si esto sucede, nuestras definiciones no siempre funcionarán. Por ejemplo, cuando definimos el operador principal de una fórmula, decimos: en una fórmula de la forma\(B \lif C\), el operador principal es la ocurrencia indicada de\(\lif\). Pero si podemos hacer coincidir la fórmula\(D \lif D \lif D\) con\(B \lif C\) las dos formas diferentes mencionadas anteriormente, entonces en un caso obtenemos la primera ocurrencia de\(\lif\) como operador principal, y en el segundo caso la segunda ocurrencia. Pero pretendemos que el operador principal sea una función de la fórmula, es decir, cada fórmula debe tener exactamente una ocurrencia de operador principal.
Lema\(\PageIndex{1}\)
El número de paréntesis izquierdo y derecho en una fórmula\(A\) es igual.
Comprobante. Esto lo demostramos por inducción en el camino\(A\) se construye. Esto requiere de dos cosas: a) Tenemos que probar primero que todas las fórmulas atómicas tienen la propiedad en cuestión (la base de inducción). (b) Entonces tenemos que probar que cuando construimos nuevas fórmulas a partir de fórmulas dadas, las nuevas fórmulas tienen la propiedad siempre que las antiguas sí.
\(l(A)\)Sea el número de paréntesis izquierdos, y\(r(A)\) el número de paréntesis derecho en\(A\),\(l(t)\) y de\(r(t)\) manera similar el número de paréntesis izquierdo y derecho en un término\(t\). Dejamos la prueba de que para cualquier término\(t\),\(l(t) = r(t)\) como ejercicio.
-
\(\indcase{A}{\lfalse}\)\(\indfrm\)tiene 0 paréntesis izquierdo y 0 derecho.
-
\(\indcase{A}{\Atom{R}{t_1,\dots,t_n}}\)\(l(\indfrm) = 1 + l(t_1) + \dots + l(t_n) = 1 + r(t_1) + \dots + r(t_n) = r(\indfrm)\). Aquí hacemos uso del hecho, dejado como ejercicio, que\(l(t) = r(t)\) para cualquier término\(t\).
-
\(\indcase{A}{\eq[t_1][t_2]}\)\(l(\indfrm) = l(t_1) + l(t_2) = r(t_1) + r(t_2) = r(\indfrm)\).
-
\(\indcase{A}{\lnot B}\)Por hipótesis de inducción,\(l(B) = r(B)\). Así\(l(\indfrm) = l(B) = r(B) = r(\indfrm)\).
-
\(\indcase{A}{(B \ast C)}\)Por hipótesis de inducción,\(l(B) = r(B)\) y\(l(C) = r(C)\). Así\(l(\indfrm) = 1 + l(B) + l(C) = 1 + r(B) + r(C) = r(\indfrm)\).
-
\(\indcase{A}{\lforall{x}{B}}\)Por hipótesis de inducción,\(l(B) = r(B)\). Por lo tanto,\(l(\indfrm) = l(B) = r(B) = r(\indfrm)\).
-
\(\indcase{A}{\lexists{x}{B}}\)De igual manera.
◻
Definición\(\PageIndex{1}\): Proper prefix
Una cadena de símbolos\(B\) es un prefijo apropiado de una cadena de símbolos\(A\) si la concatenación\(B\) y una cadena de símbolos no vacía rinde\(A\).
Si\(A\) es una fórmula, y\(B\) es un prefijo apropiado de\(A\), entonces no\(B\) es una fórmula.
Comprobante. Ejercicio. ◻
Problema\(\PageIndex{1}\)
Demostrar Lema\(\PageIndex{2}\).
Si\(A\) es una fórmula atómica, entonces satisface una, y sólo una de las siguientes condiciones.
-
\(A \ident \lfalse\).
-
\(A \ident \Atom{R}{t_1,\dots,t_n}\)donde\(R\) es un símbolo predicado\(n\) -lugar,,...\(t_1\),\(t_n\) son términos, y cada uno de\(R\),,...\(t_1\),\(t_n\) está determinado de manera única.
-
\(A \ident \eq[t_1][t_2]\)donde\(t_1\) y\(t_2\) son términos determinados de manera única.
Comprobante. Ejercicio. ◻
Problema\(\PageIndex{2}\)
Probar Proposición\(\PageIndex{1}\) (Pista: Formular y probar una versión de Lema\(\PageIndex{2}\) para términos.)
Proposición\(\PageIndex{2}\): Unique Readability
Cada fórmula satisface una, y sólo una de las siguientes condiciones.
-
\(A\)es atómico.
-
\(A\)es de la forma\(\lnot B\).
-
\(A\)es de la forma\((B \land C)\).
-
\(A\)es de la forma\((B \lor C)\).
-
\(A\)es de la forma\((B \lif C)\).
-
\(A\)es de la forma\(\lforall{x}{B}\).
-
\(A\)es de la forma\(\lexists{x}{B}\).
Además, en cada caso\(B\), o\(B\) y\(C\), están determinados de manera única. Esto significa que, por ejemplo, no hay pares diferentes\(B\),\(C\) y\(B'\),\(C'\) así que eso\(A\) es tanto de la forma\((B \lif C)\) and \((B' \lif C')\).
Comprobante. Las reglas de formación requieren que si una fórmula no es atómica, debe comenzar con un paréntesis de apertura (,\(\lnot\), o con un cuantificador. Por otro lado, toda fórmula que comience con uno de los siguientes símbolos debe ser atómica: un símbolo predicado, un símbolo de función, un símbolo constante,\(\lfalse\).
Entonces realmente solo tenemos que demostrar que si\(A\) es de la forma\((B \ast C)\) y también de la forma\((B' \mathbin{\ast'} C')\), entonces\(B \ident B'\),\(C \ident C'\), y\(\ast = {\ast'}\).
Entonces supongamos ambos\(A \ident (B \ast C)\) y\(A \ident (B' \mathbin{\ast'} C')\). Entonces,\(B \ident B'\) o no. Si es así, claramente\(\ast = {\ast'}\) y\(C \ident C'\), ya que entonces son subcadenas de\(A\) que comienzan en el mismo lugar y son de la misma longitud. El otro caso es\(B \not\ident B'\). Dado que\(B\) y\(B'\) son ambas subcadenas de\(A\) que comienzan en el mismo lugar, una debe ser un prefijo propio del otro. Pero esto es imposible por Lemma\(\PageIndex{2}\). ◻