Autor Tema: ¡Problema de cálculo de predicados!

0 Usuarios y 1 Visitante están viendo este tema.

21 Noviembre, 2012, 02:20 pm
Leído 1620 veces

yotas

  • Sé valiente, no voluble, no maleable.
  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 725
  • Karma: +0/-0
  • Sexo: Masculino
  • Plop, plop.
¡Buenas, buenas!

Me gustaría preguntar sobre este ejercicio:

Si una wf \( \mathcal A \) sin cuantificadores es probable en un cálculo de predicados, pruebe que \( \mathcal A \) es una instancia de una tautología.

Para resolverlo, dan el siguiente hint: si \( \mathcal A \) no fuera tautología, se podría construir una interpretación teniendo como al conjunto de términos de \( \mathcal A \) como su dominio, para el cual \( \mathcal A \) no es cierto. Esto contradice que todo teorema de cálculo de predicados es lógicamente válido.

Entiendo la idea, lo que no entiendo es cómo construir dicho modelo.

¡Ya tengo el teorema de completitud de Gödel!  :P

¡Muchas gracias por las ayudas y sugerencias!  ;D
Citar
Creo debes tener un problema en tu mente por el cual complicas las cosas y las afirmaciones más sencillas.

Sí, es un problema muy frecuente en este foro. Se llama saber matemáticas.

24 Noviembre, 2012, 05:34 am
Respuesta #1

specu

  • $$\Large \color{#5372a0}\pi\,\pi$$
  • Mensajes: 62
  • Karma: +0/-0
  • Sexo: Masculino
    • Especulación pura
Pero la 'hint' prueba lo que pide el ejercicio. Supongamos una fórmula bien formada del cálculo de predicados sin cuantificadores que no sea instancia de una tautología del cálculo proposicional. En ese caso, puede darse una interpretación de las variables y las letras de predicado tales que cada subfórmula que sustituye a cada una de las variables predicativas de la fórmula de la que es instancia tenga un valor de verdad que haga falsa a la fórmula. Entonces no puede ofrecerse una prueba, dado que sabemos ya que todo teorema es válido.

En el libro de Church de introducción a la lógica (Cap. III) hay una prueba de esto que se basa en: los axiomas del cálculo usado son instancias de tautologías y su regla el modus ponens. Se prueba que para cada teorema sin cuantificadores de la lógica proposicional puede proporcionarse una prueba también sin cuantificadores. Como la única regla es el modus ponens, cada fórmula surgida en la prueba de la fórmula en cuestión es instancia de un teorema de la lógica proposicional (y por ende de una tautología; esto es así dado que, por la definición de implicación, si una implicación es verdadera y el antecedente es verdadero, también habrá de serlo el consecuente, y por ende toda fórmula probada es verdadera), incluyendo la que resulta al final.

Saludos

26 Noviembre, 2012, 03:37 pm
Respuesta #2

yotas

  • Sé valiente, no voluble, no maleable.
  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 725
  • Karma: +0/-0
  • Sexo: Masculino
  • Plop, plop.
¡Muchas gracias por la respuesta y por la recomendación de un libro!  :D
Citar
Creo debes tener un problema en tu mente por el cual complicas las cosas y las afirmaciones más sencillas.

Sí, es un problema muy frecuente en este foro. Se llama saber matemáticas.