La prueba de que WFFs con indistinguibles entre paréntesis única de descomposición/legibilidad
(El crédito GitGud, ProofWiki)
Teorema 1
Dejar que Un ser WFF de la lógica proposicional.
Let' S ser una parte inicial de Una.
Entonces S no es un WFF de la lógica proposicional.
Prueba
Vamos a l(Q) denota la longitud de una cadena Q.
Por definición, S es una parte inicial de Un iff =ST para algunos no nulo de la cadena de T.
Así, observamos que l(S)<l(Un).
Dejar que Un ser WFF tal que l(Un)=1
Luego de una primera parte S, l(S)<1=0.
Es decir, S debe ser la cadena nula, que no es un WFF.
Por lo que el resultado vale para WFFs de longitud 1.
Ahora, asumimos una inducción hipótesis: que el resultado es válido para todos WFFs de longitud k o menos.
Dejar que Un ser WFF tal que l(Un)=k+1.
Supongamos que D es una parte inicial de Una que pasa a ser un WFF.
Es decir, A=DT donde T es no nulo.
Hay dos casos:
A=B, donde B es un WFF de longitud k. D es un WFF empezando , por lo que D=E donde E es también un WFF. Quitamos la inicial de UN=DT para obtener B=ET. Pero entonces B es un WFF de longitud k que tiene E como una parte inicial que es en sí mismo un WFF. Esto contradice la hipótesis de inducción. Por lo tanto, ninguna parte inicial de A=B puede ser un WFF.
A=|B∘C| donde ∘ es una de las conectivas binarias. En este caso, D es un WFF empiezan con"|", por lo que D=|E∗F| para algunos binario conectivo ∗ y algunos WFFs E y F. Por Lo Tanto B∘C|=E∗F|T. Ambos B y E son WFFs de longitud inferior a k+1. Por la hipótesis inductiva, entonces, ni B, ni el Correo puede ser una parte inicial de la otra. Pero desde que ambos B y E inicio en el mismo lugar en Una, deben ser de la misma: B=E. Por Lo Tanto B∘C|=B∗F|T. Así ∘=∗ y C|=F|T. Pero entonces la WFF F es una parte inicial de la WFF C de longitud inferior a k+1. Esto contradice nuestra hipótesis inductiva. Por lo tanto, ninguna parte inicial de A=(B∘C) puede ser un WFF.
Así que no hay parte inicial de cualquier WFF de longitud k+1 puede ser un WFF.
El resultado de la siguiente manera por la fuerte inducción.
Teorema 2
Cada WFF de la lógica proposicional, que comienza con una | o una negación signo tiene exactamente una de las principales conectivo.
Por lo tanto, en un nivel superior, sólo hay una forma de interpretar la semántica de un determinado WFF de la lógica proposicional.
La prueba Hay dos casos a considerar.
Considere el caso donde A=|B∘C| para algunos WFFs B y C y algunos binario conectivo ∘.
Supongamos también que A=|D∗E| donde D y E también son WFFs, y ∗ es otro binario conectivo.
El WFFs B y D son cadenas de caracteres que empiecen en el mismo lugar, justo después de la primera a la izquierda | en Una.
Por el Teorema 1, ni B ni D puede ser una parte inicial de la otra.
Por Lo Tanto B=D.
De ello se desprende que ∗=∘ y C=E.
Ahora considere el caso donde A=B.
El resultado se sigue directamente de la definición de las principales conectivo para un WFF de este formulario.
De ahí el resultado.
■
