22/01/2020, 08:52:20 am *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: LISTADO ACTUALIZADO DE CURSOS
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Fórmulas abiertas versus instancias de tautologías  (Leído 1764 veces)
0 Usuarios y 1 Visitante están viendo este tema.
alemunozgar
AlexD
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Colombia Colombia

Mensajes: 183


La esencia de la matemática reside en su libertad.


Ver Perfil
« : 07/05/2014, 15:41:21 pm »

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 (click para mostrar u ocultar)

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.
En línea

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

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 304


Ver Perfil
« Respuesta #1 : 07/05/2014, 22:51:17 pm »

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
En línea
alemunozgar
AlexD
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Colombia Colombia

Mensajes: 183


La esencia de la matemática reside en su libertad.


Ver Perfil
« Respuesta #2 : 12/05/2014, 21:36:35 pm »

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.
En línea

Antes de imprimir este mensaje, reflexiona si es necesario hacerlo. 17 árboles mueren por 1TON papel
Carlos Ivorra
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 9.081


Ver Perfil WWW
« Respuesta #3 : 13/05/2014, 05:12:40 am »

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.
En línea
alemunozgar
AlexD
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Colombia Colombia

Mensajes: 183


La esencia de la matemática reside en su libertad.


Ver Perfil
« Respuesta #4 : 13/05/2014, 10:41:24 am »

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.
En línea

Antes de imprimir este mensaje, reflexiona si es necesario hacerlo. 17 árboles mueren por 1TON papel
Carlos Ivorra
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 9.081


Ver Perfil WWW
« Respuesta #5 : 13/05/2014, 20:50:16 pm »

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.
En línea
luis
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 304


Ver Perfil
« Respuesta #6 : 14/05/2014, 00:32:32 am »

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
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!