Autor Tema: Fórmulas abiertas versus instancias de tautologías

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

07 Mayo, 2014, 08:41 pm
Leído 1888 veces

alemunozgar

  • AlexD
  • Novato
  • Mensajes: 183
  • Karma: +0/-0
  • Sexo: Masculino
  • La esencia de la matemática reside en su libertad.
Buenas tardes para todos.

Tengo una traba con la demostración de la siguiente propiedad:
Exhiba una fórmula bien formada lógicamente válida que no es una instancia de una tautología.
Sin embargo, muestre que todo fórmula bien formada abierta (i.e., sin cuantificadores) tiene que ser una instancia de una tautología.

Spoiler
Una f.b.f. se dice lógicamente válida si es verdadera para toda interpretación.
Una instancia de una forma proposicional es una f.b.f. obtenida de la forma proposicional por sustitución de cada una de las letras proposicionales por una f.b.f. (todas las ocurrencias de la letra proposicional por la misma f.b.f).
[cerrar]

La primera parte es más sencilla y ya logré obtener un ejemplo válido, pero con la segunda no veo salida alguna.
Le agradezco mucho a quien me pueda colaborar.

Saludos.
Antes de imprimir este mensaje, reflexiona si es necesario hacerlo. 17 árboles mueren por 1TON papel

08 Mayo, 2014, 03:51 am
Respuesta #1

luis

  • Aprendiz
  • Mensajes: 304
  • Karma: +1/-0
  • Sexo: Masculino
supongo que lo que quieres probar es ...

muestre que todo fórmula bien formada abierta LÓGICAMENTE VÁLIDA tiene que ser una instancia de una tautología.

en ese caso, yo intentaría el contrarrecíproco

1. tomo una fbf phi abierta que no sea instancia de tautología
2. como phi no tiene cuantificadores, la pienso proposicionalmente
3. como no es instancia de tautología, pero es instancia de alguna proposición, me tengo que ingeniar para convertir una valuación que falsea la visión proposicional en alguna estructura que falsee phi

saludos

luis

13 Mayo, 2014, 02:36 am
Respuesta #2

alemunozgar

  • AlexD
  • Novato
  • Mensajes: 183
  • Karma: +0/-0
  • Sexo: Masculino
  • La esencia de la matemática reside en su libertad.
Gracias Luis por tus respuestas.
Efectivamente es como dices, lógicamente válida y abierta.

Llevo ya varios días con este ejercicio y le pensé como dijiste y además lo intenté por inducción sobre el número de conectivos lógicos y no he dado con la solución....
¿Tienes alguna otra idea Luis?
¿Alguien me echa una mano?

Saludos.
Antes de imprimir este mensaje, reflexiona si es necesario hacerlo. 17 árboles mueren por 1TON papel

13 Mayo, 2014, 10:12 am
Respuesta #3

Carlos Ivorra

  • Administrador
  • Mensajes: 9,060
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Eso es fácil de probar (creo) a partir del teorema de eliminación de cortes de Gentzen, pero si, como sospecho, no has visto eso, ya no sé qué decirte. Posiblemente habrá otras formas de probarlo. En cuanto tenga un rato miro a ver si encuentro algo en internet.

13 Mayo, 2014, 03:41 pm
Respuesta #4

alemunozgar

  • AlexD
  • Novato
  • Mensajes: 183
  • Karma: +0/-0
  • Sexo: Masculino
  • La esencia de la matemática reside en su libertad.
Hola Carlos Ivorra.

En efecto, estuve mirando el teorema que mencionas es una artillería bastante pesada que no creo pueda utilizar...

Sigo en el trabajo de ideármelas con la prueba.

Saludos.
Antes de imprimir este mensaje, reflexiona si es necesario hacerlo. 17 árboles mueren por 1TON papel

14 Mayo, 2014, 01:50 am
Respuesta #5

Carlos Ivorra

  • Administrador
  • Mensajes: 9,060
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
He encontrado una prueba que no usa el teorema de Gentzen. Está en la página 184 de la Introduction to Mathematical Logic de Church. Consiste en probar que si una fórmula sin cuantificadores es un teorema lógico, entonces tiene una demostración sin cuantificadores (esto es lo que se prueba fácilmente con el teorema de Gentzen, pero Church lo prueba directamente) y entonces tiene que poder probarse a partir de los axiomas del cálculo proposicional, por lo que tiene que ser una instancia de una tautología.

14 Mayo, 2014, 05:32 am
Respuesta #6

luis

  • Aprendiz
  • Mensajes: 304
  • Karma: +1/-0
  • Sexo: Masculino
Voy a poner un ejemplo que sigue la línea que había esbozado.

1. tomo la siguiente phi: P(x) -> Q(x,y)
2. phi es una instancia de la proposición p -> q
3. existe una valuación v, la que cumple que v.p = 1 y v.q = 0, que falsea p -> q
4. considero una estructura M con universo U unitario, interpretación vacía para Q y U para P, <{0}, {0}, vacío>
5. es claro que M no modela phi, y por lo tanto phi no es lógicamente válida

creo que generalizar este argumento debería ser suficiente

saludos

luis