¿Cómo comprobaremos si una expresión es una sentencia o no en la lógica funcional de la verdad?

Question

Estoy leyendo el capítulo 6 del libro de texto para todo x: Calgary Una introducción a la lógica formal . Citando el libro de texto:

1. Cada letra de la oración es una oración.
2. Si $\mathscr A$ es una frase, entonces $\lnot \mathscr A$ es una frase.
3. Si $\mathscr A$ y $\mathscr B$ son frases, entonces $\mathscr{(A\land B)}$ es una frase.
4. Si $\mathscr A$ y $\mathscr B$ son frases, entonces $\mathscr{(A\lor B)}$ es una sentencia.
5. Si $\mathscr A$ y $\mathscr B$ son frases, entonces $\mathscr{(A\rightarrow B)}$ es una sentencia.
6. Si $\mathscr A$ y $\mathscr B$ son frases, entonces $\mathscr{(A\leftrightarrow B)}$ es una sentencia.
7. Nada más es una sentencia.

Al igual que la definición inductiva permite construir oraciones complejas a partir de partes más simples, la definición nos permite descomponer las oraciones en sus partes más simples. Una vez que llegamos a las letras de las frases, sabemos que estamos bien.

A continuación, el autor da ejemplos de cómo podemos comprobar si una expresión es una frase o no. Pero el autor sólo da ejemplos de expresiones que son oraciones.

Mi problema es cómo vamos a demostrar que expresiones como $(A\lor B \land C)$ o $(\lnot A (B \lor C))$ (que sé que no es una oración) no son oraciones según las reglas dadas por el autor? ¿O las reglas dadas por el autor son insuficientes para decidir si son oraciones o no?

Answer 1

Sus ejemplos son fáciles, suponiendo $A$ , $B$ y $C$ son las letras de la frase. Según las reglas anteriores, cualquier frase es una letra de frase o de la forma $\neg\mathscr{A}$ o de la forma $(\mathscr{A}\circ\mathscr{B})$ , donde $\circ\in\{\wedge,\vee,\rightarrow,\leftrightarrow\}$ . Tampoco $\left(A\vee B\wedge C\right)$ ni $\left(\neg A\left(B\vee C\right)\right)$ es de cualquiera de estas formas, por lo que, no son, estrictamente hablando, oraciones. Por supuesto, si hay convenciones, como " introduciendo paréntesis de izquierda a derecha, para operaciones de igual alcance ", y si $\vee$ un $\wedge$ son de igual alcance, entonces $\left(A\vee B\wedge C\right)$ es en realidad $\left(\left(A\vee B\right)\wedge C\right)$ y es es una sentencia. Pero, para aplicar las reglas formales, primero hay que hay que transformar las fórmulas en sus formas formales.

Si todo es completamente formal, entonces lo que está pidiendo puede ser comprobado por un algoritmo. He aquí un esbozo: Primero comprueba si la es una oración atómica (aquí, la letra de la oración). Si lo es, devuelve " Es una sentencia ". Si no, comprueba si el primer símbolo es " $\neg$ ", " $($ " o ninguna de ellos. Si es " $\neg$ ", entonces su fórmula debe ser de la forma forma $\neg\mathscr{A}$ . Entonces, todo lo que sigue " $\neg$ " debe ser $\mathscr{A}$ por lo que el procedimiento de comprobación se llama de nuevo, al $\mathscr{A}$ . Si comienza con un paréntesis " $($ ", debe ser de la forma $(\mathscr{A}\circ\mathscr{B})$ . Compruebe si hay un paréntesis de cierre " $)$ " y si hay uno de $\wedge,\vee,\rightarrow,\leftrightarrow$ (llámese " $\circ$ ") en algún lugar del medio. Si no es así, entonces devuelve " no es una sentencia ". Si lo es, entonces todo lo que está entre " $($ " y " $\circ$ " debe ser $\mathscr{A}$ y todo que se encuentra entre " $\circ$ " y " $)$ " debe ser $\mathscr{B}$ . Por lo tanto, el procedimiento de comprobación se llama de nuevo, primero en $\mathscr{A}$ , y luego en $\mathscr{B}$ . Si el primer símbolo no es " $\neg$ " ni " $($ ", entonces devuelve " No es una sentencia ". Este es un procedimiento procedimiento recursivo, que se llama a sí mismo hasta llegar a una sentencia atómica sentencia atómica o un callejón sin salida. Si llega a un callejón sin salida, el veredicto es " No es una sentencia ", de lo contrario, el veredicto es " Es una sentencia ".

Por ejemplo, examinemos $\left(\left(A\vee B\right)\wedge C\right)$ :

1. No es una sentencia atómica.
2. Comienza con " $($ ", por lo que debe ser de la forma $(\mathscr{A}\circ\mathscr{B})$ .
3. De hecho, se cierra con " $)$ ", " $\circ$ " es " $\wedge$ ", $\mathscr{A}$ es " $\left(A\vee B\right)$ " y $\mathscr{B}$ es " $C$ ".
4. Llamada al procedimiento sobre $\mathscr{A}$ .
5. No es una sentencia atómica.
6. Comienza con " $($ ", por lo que debe ser de la forma $(\mathscr{A}\circ\mathscr{B})$ .
7. De hecho, se cierra con " $)$ ", " $\circ$ " es " $\vee$ ", $\mathscr{A}$ es " $A$ " y $\mathscr{B}$ es " $B$ ".
8. Llamada al procedimiento sobre $\mathscr{A}$ .
9. C'est $A$ . Es una frase atómica.
10. Procedimiento de finalización.
11. Llamada al procedimiento sobre $\mathscr{B}$ .
12. C'est $B.$ Es una sentencia atómica.
13. Procedimiento de finalización (vuelve al nivel de previsiones).
14. Llamada al procedimiento sobre $\mathscr{B}$ .
15. C'est $C$ . Es una frase atómica.
16. Procedimiento de finalización. Resultado: " Es una sentencia ".

Por otro lado, examinemos $\left(A\vee B\wedge C\right)$ :

1. No es una sentencia atómica.
2. Comienza con " $($ ", por lo que debe ser de la forma $(\mathscr{A}\circ\mathscr{B})$ .
3. De hecho, se cierra con " $)$ " Pero aquí, no puede decidir entre " $\vee$ " y " $\wedge$ ". Un callejón sin salida.
4. Procedimiento de finalización. Resultado: " No es una sentencia ".

Incluso si el procedimiento puede decidir entre " $\vee$ " y " $\wedge$ ", (por ejemplo, si funciona con la primera operación lógica que encuentra), entonces se detendrá en un paso posterior, cuando encuentre que " $B\wedge C$ " no empieza ni con " $\neg$ " ni con " $($ ".