10/12/2019, 01:21:19 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: Homenaje a NUMERARIUS
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Dado un conjunto de hipótesis cuantificadas hallar la única tesis válida  (Leído 970 veces)
0 Usuarios y 1 Visitante están viendo este tema.
manooooh
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 2.445


Ver Perfil
« : 01/06/2019, 09:29:56 pm »

Hola!

Debo usar deducción natural para el siguiente enunciado, que dice que, teniendo en cuenta todas las hipótesis, ¿cuál es la única tesis válida?:

[texx]\forall x(Px\vee Mx\to Ax\vee Cx\vee Lx)[/texx]
[texx]\forall x(Ax\wedge Tx\to Cx\wedge Qx)[/texx]
[texx]\forall x(Gx\to Cx\wedge Qx)[/texx]
[texx]\exists x(Lx\vee Sx\to Gx\wedge Nx)[/texx]

  • [texx]\exists x(Px\vee Tx\to Cx)[/texx]
  • [texx]\exists x(Px\wedge Tx\to Cx)[/texx]
  • [texx]\exists x(Px\wedge Tx\to Cx\wedge Qx)[/texx]
  • [texx]\forall x(Px\wedge Qx)[/texx]



Algunas preguntas:

1) ¿Es posible que la (4) quede descartada pues existe al menos un cuantificador existencial en la hipótesis, y la tesis tiene un cuantificador universal?
2) ¿Es el orden siguiente de precedencia de los operadores correcto: [texx]\forall x((Px\vee Mx)\to(Ax\vee Cx\vee Lx))[/texx]?
3) ¿Cuál es la estrategia de resolución en estos casos?

Yo creo que podemos pensar a lo anterior como un razonamiento, y podemos usar reglas de inferencia para encontrar cuál es la conclusión, pero no sé si con esto se descartan las otras o no :¿eh?:.

¿Acaso podríamos empezar así?:

[texx]\begin{array}{lll}
1)&\forall x(Px\vee Mx\to Ax\vee Cx\vee Lx)&\text{Premisa}\\
2)&\forall x(Ax\wedge Tx\to Cx\wedge Qx)&\text{Premisa}\\
3)&\forall x(Gx\to Cx\wedge Qx)&\text{Premisa}\\
4)&\exists x(Lx\vee Sx\to Gx\wedge Nx)&\text{Premisa}\\
5)&Px\vee Mx\to Ax\vee Cx\vee Lx&\text{Particularización Universal 1)}\\
6)&Ax\wedge Tx\to Cx\wedge Qx&\text{Particularización Universal 2)}\\
7)&Gx\to Cx\wedge Qx&\text{Particularización Universal 3)}\\
8)&Lx\vee Sx\to Gx\wedge Nx&\text{Particularización Existencial 4)}\\
\end{array}[/texx]

¿y ahora qué? Parece muy tedioso de resolver usando reglas de inferencia.

¿Quizás con el método del condicional asociado?

Gracias!!
Saludos
En línea
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 8.616



Ver Perfil
« Respuesta #1 : 01/06/2019, 09:41:01 pm »


Hola, manooooh.

Yo sé que es la primera, pero no sé cómo lo sé (a vista de pájaro) así que no te servirá de nada, pero por lo menos te saludo, que hace mucho que no te saludaba.

Buenas noches.
En línea

manooooh
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 2.445


Ver Perfil
« Respuesta #2 : 01/06/2019, 09:46:23 pm »

Hola feriva! Cuánto tiempo señor, lo extrañaba :sonrisa:

Yo sé que es la primera, pero no sé cómo lo sé (a vista de pájaro) así que no te servirá de nada, pero por lo menos te saludo, que hace mucho que no te saludaba.

Pues, me pone contento que ya hayas dado con tu solución, pero me intriga saber cómo lo pensaste :rodando_los_ojos:.

Cualquier novedad publicala y lo vamos viendo.

Saludos
En línea
noisok
Semi pleno
***

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 72


Ver Perfil
« Respuesta #3 : 01/06/2019, 09:57:12 pm »

Sólo quería comentarte que cuando particularizamos, lo hacemos sobre una constante creada al efecto para eso mismo. En el caso de particularizaciones sobre cuantificadores universales, se puede hacer con tantas constante uno quiera, pero con el cuantificador existencial, sólo sobre una. Es por eso que en general primero se particulariza sobre un cuantificador existencial, para aplicar luego esa misma constante en las de cuantificador universal.
Si no se especifica, el operador condicional tiene mayor precedencia que los disyuntivos o conjuntivos. Al menos, es lo más habitual. Pero siempre debería estar indicado.
En línea
manooooh
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 2.445


Ver Perfil
« Respuesta #4 : 01/06/2019, 10:01:36 pm »

Hola

Sólo quería comentarte que cuando particularizamos, lo hacemos sobre una constante creada al efecto para eso mismo. En el caso de particularizaciones sobre cuantificadores universales, se puede hacer con tantas constante uno quiera, pero con el cuantificador existencial, sólo sobre una. Es por eso que en general primero se particulariza sobre un cuantificador existencial, para aplicar luego esa misma constante en las de cuantificador universal.

De acuerdo. Me equivoqué.

Saludos
En línea
geómetracat
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 809



Ver Perfil
« Respuesta #5 : 02/06/2019, 06:02:53 am »

Si quieres dar una prueba formal, con deducción natural, lo primero que debes hacer es dar una prueba informal y después formalizarla. Lo bueno de la deducción natural, como su propio nombre indica, es que sigue más o menos los pasos que seguiría uno en una prueba informal
Esto quiere decir qur la formalización suele ser sencilla, una vez tienes la práctica suficiente.

Lo primero es seguir el sabio consejo de noisok, particularizar primero el cuantificador existencial y después los universales con la misma constante.
Entonces tendrás:

[texx]1. Pc\vee Mc\to Ac\vee Cc\vee Lc[/texx]
[texx]2. Ac\wedge Tc\to Cc\wedge Qc[/texx]
[texx]3. Gc\to Cc\wedge Qc[/texx]
[texx]4. Lc\vee Sc\to Gc\wedge Nc[/texx]

Afirmo que la opción buena es la segunda. Para probarla, solamente hay que probar [texx]Pc \wedge Tc \rightarrow Cc[/texx]. Ahora se trata de jugar un poco con las premisas: supón que tienes [texx]Pc \wedge Tc[/texx]. Quieres probar [texx]Cc[/texx].
Pongo el resto de la demostración informal en spoiler. Intenta hacerla tú y si no te sale (o si te sale y lo quieres comprobar), mira el spoiler.

Spoiler (click para mostrar u ocultar)

Más o menos cada línea del spoiler corresponde a la aplicación de alguna regla de deducción natural (o a la introducción o descarte de hipótesis). Trata de formalizarlo, es un poco largo, pero no debería ser muy difícil.
En línea

La ecuación más bonita de las matemáticas: [texx]d^2=0[/texx]
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 8.616



Ver Perfil
« Respuesta #6 : 02/06/2019, 06:23:35 am »

Hola feriva! Cuánto tiempo señor, lo extrañaba :sonrisa:

Yo sé que es la primera, pero no sé cómo lo sé (a vista de pájaro) así que no te servirá de nada, pero por lo menos te saludo, que hace mucho que no te saludaba.

Pues, me pone contento que ya hayas dado con tu solución, pero me intriga saber cómo lo pensaste :rodando_los_ojos:.

Cualquier novedad publicala y lo vamos viendo.

Saludos

La pensé por encima, sin hacer nada :sonrisa: pero me pareció, no sé, la más conectada y menos restricitiva.

Ahora ya la he pensado y (si no he metido la pata) me parece que sí es.

[texx]\forall x(Px\vee Mx\to Ax\vee Cx\vee Lx)
 [/texx]

[texx]\forall x(Ax\wedge Tx\to Cx\wedge Qx)
 [/texx]

[texx]\forall x(Gx\to Cx\wedge Qx)
 [/texx]

[texx]\exists x(Lx\vee Sx\to Gx\wedge Nx)
 [/texx]

...

1ª [texx]\exists x(Px\vee Tx\to Cx)
 [/texx]

...

Tomando la segunda proposición

[texx]\forall x(Ax\wedge Tx\to Cx\wedge Qx)
 [/texx]

Se tiene

[texx](Ax\rightarrow Cx\vee Qx)\wedge(Tx\rightarrow Cx\vee Qx)
 [/texx]

Primer caso

Si [texx](Ax\rightarrow Cx)
 [/texx], entonces la primera se queda así [texx]\forall x(Px\vee Mx\to Cx\vee Lx)
 [/texx]

En consecuencia de este primer caso

[texx](Tx\rightarrow Qx)
 [/texx]

Eso hace que podamos escibir la tercera así

[texx]\forall x(Gx\to Cx\wedge Tx)
 [/texx]

Entramos con esto en la cuarta

[texx]\exists x(Lx\vee Sx\to Gx\wedge Nx)
 [/texx]

y si se diera [texx]Lx\rightarrow Gx
 [/texx], la primera se podría escribir así [texx]\forall x(Px\vee Mx\to Cx\vee Gx)
 [/texx], y a la vez se quedaría en [texx]\forall x(Px\vee Mx\to Cx)
 [/texx], con lo que tendríamos que esto sería cierto [texx]\exists x(Px\vee Tx\to Cx)
 [/texx] . Sería concretamente [texx]\exists x(Px\to Cx)
 [/texx], ya que, [texx](Tx\rightarrow Qx)
 [/texx].

...

Segundo caso

Si [texx](Ax\rightarrow Qx)
 [/texx], entonces la primera se queda así [texx]\forall x(Px\vee Mx\to Qx\wedge Cx\vee Lx)
 [/texx]

En consecuencia de este primer caso, [texx]\forall x(Ax\wedge Tx\to Cx\wedge Qx)[/texx]
 , nos lleva a [texx](Tx\rightarrow Cx)
 [/texx], con lo que [texx]\exists x(Px\vee Tx\to Cx)
 [/texx] también sería cierta.

Saludos.
En línea

geómetracat
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 809



Ver Perfil
« Respuesta #7 : 02/06/2019, 06:48:17 am »

La primera no puede ser cierta. Basta dar un modelo en el que las premisas son verdaderas pero [texx]\exists x(Px \vee Tx \rightarrow Cx)[/texx] es falsa.

Consideremos el modelo cuyo universo [texx]M = \{c \}[/texx] tiene un único punto, y con [texx]Pc,Ac[/texx], mientras que ningún elemento pertenece a la extensión de los demás predicados.
Entonces las premisas son verdaderas, pero la fórmula [texx]\exists x(Px \vee Tx \rightarrow Cx)[/texx] es falsa.
En línea

La ecuación más bonita de las matemáticas: [texx]d^2=0[/texx]
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 8.616



Ver Perfil
« Respuesta #8 : 02/06/2019, 06:55:28 am »

La primera no puede ser cierta. Basta dar un modelo en el que las premisas son verdaderas pero [texx]\exists x(Px \vee Tx \rightarrow Cx)[/texx] es falsa.

Consideremos el modelo cuyo universo [texx]M = \{c \}[/texx] tiene un único punto, y con [texx]Pc,Ac[/texx], mientras que ningún elemento pertenece a la extensión de los demás predicados.
Entonces las premisas son verdaderas, pero la fórmula [texx]\exists x(Px \vee Tx \rightarrow Cx)[/texx] es falsa.



Afirmo que la opción buena es la segunda.


Hola, geómetracat.

¿Pero la disyunción es exclusiva? Porque, si no, son ciertas las dos primeras; yo pensé que no era exclusiva.

Una vez vi (no me acuerdo dónde) que el símbolo de la disyunción exclusiva llevaba una raya debajo de la v, algo así _v_ pero sin ser discontinua 

Aquí está https://es.wikipedia.org/wiki/Disyunci%C3%B3n_exclusiva

Y al verlo así no analicé si se podía dar o no la conjunción por ser más restrictiva y por decir el enunciado que sólo había una verdadera; pero si es verdadera, pues entonces tiene que ser la que tú dices.


Saludos.
En línea

geómetracat
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 809



Ver Perfil
« Respuesta #9 : 02/06/2019, 07:07:19 am »

No,normalmente la disyunción en lógica no es exclusiva, y en cualquier caso la que se denota por [texx]\vee[/texx] nunca es exclusiva. Pero igualmente la primera no se sigue de las premisas. Si se pudiera deducir la primera de las premisas cualquier modelo que hiciera las premisas verdaderas también haría la fórmula verdadera, pero no es así como he indicado antes.
En línea

La ecuación más bonita de las matemáticas: [texx]d^2=0[/texx]
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 8.616



Ver Perfil
« Respuesta #10 : 02/06/2019, 07:24:03 am »

No,normalmente la disyunción en lógica no es exclusiva, y en cualquier caso la que se denota por [texx]\vee[/texx] nunca es exclusiva. Pero igualmente la primera no se sigue de las premisas. Si se pudiera deducir la primera de las premisas cualquier modelo que hiciera las premisas verdaderas también haría la fórmula verdadera, pero no es así como he indicado antes.

Ah, creo que lo entiendo ahora.

Pero esto sí es cierto, ¿no?

[texx]\exists x(Px\wedge Tx\rightarrow Cx)\rightarrow\exists x(Px\vee Tx\rightarrow Cx)
 [/texx]

[texx]\neg(\exists x(Px\wedge Tx\rightarrow Cx)\leftarrow\exists x(Px\vee Tx\rightarrow Cx))
 [/texx]

Saludos.
En línea

geómetracat
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 809



Ver Perfil
« Respuesta #11 : 02/06/2019, 10:42:58 am »

Pero esto sí es cierto, ¿no?

[texx]\exists x(Px\wedge Tx\rightarrow Cx)\rightarrow\exists x(Px\vee Tx\rightarrow Cx)
 [/texx]

Esto es cierto.

Cita
[texx]\neg(\exists x(Px\wedge Tx\rightarrow Cx)\leftarrow\exists x(Px\vee Tx\rightarrow Cx))
 [/texx]

Esto, tal cual lo escribes queda un poco raro. En lógica formal no se usan las implicaciones a la izquierda. Además, esta fórmula no es verdadera en general. Puede ser que en algún caso sí que tengas la implicación
[texx]\exists x(Px\vee Tx\rightarrow Cx)) \rightarrow \exists x(Px\wedge Tx\rightarrow Cx)[/texx].
Que la fórmula que escribes sea verdadera quiere decir que siempre, pase lo que pase, la implicación es falsa, y como ya he dicho, hay situaciones en las que no lo es.

Lo que querías expresar, según entiendo (y si no corrígeme) es que la primera implicación que escribes es siempre verdadera, mientras que la implicación al revés no es necesariamente verdadera. Si es así, estás en lo cierto: la implicación
[texx]\exists x(Px\vee Tx\rightarrow Cx)) \rightarrow \exists x(Px\wedge Tx\rightarrow Cx)[/texx]
no es verdadera en general.
En línea

La ecuación más bonita de las matemáticas: [texx]d^2=0[/texx]
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 8.616



Ver Perfil
« Respuesta #12 : 02/06/2019, 11:10:23 am »


Esto, tal cual lo escribes queda un poco raro. En lógica formal no se usan las implicaciones a la izquierda. Además, esta fórmula no es verdadera en general. Puede ser que en algún caso sí que tengas la implicación
[texx]\exists x(Px\vee Tx\rightarrow Cx)) \rightarrow \exists x(Px\wedge Tx\rightarrow Cx)[/texx].
Que la fórmula que escribes sea verdadera quiere decir que siempre, pase lo que pase, la implicación es falsa, y como ya he dicho, hay situaciones en las que no lo es.

Lo que querías expresar, según entiendo (y si no corrígeme) es que la primera implicación que escribes es siempre verdadera, mientras que la implicación al revés no es necesariamente verdadera. Si es así, estás en lo cierto: la implicación
[texx]\exists x(Px\vee Tx\rightarrow Cx)) \rightarrow \exists x(Px\wedge Tx\rightarrow Cx)[/texx]
no es verdadera en general.

Había cambiado la flechita así por comodidad (simplemente cortar y pegar en medio) pero sí, escrito normal sería esto

[texx]\neg(\exists x(Px\vee Tx\rightarrow Cx))\rightarrow\exists x(Px\wedge Tx\rightarrow Cx))
 [/texx].

Quería expresar exactamente eso que dices, sí.

Gracias, geómetracat, un saludo.
En línea

manooooh
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 2.445


Ver Perfil
« Respuesta #13 : 06/06/2019, 01:36:19 am »

Hola

Muchas gracias a todos! Me ha servido mucho su ayuda.

Si quieres dar una prueba formal, con deducción natural, lo primero que debes hacer es dar una prueba informal y después formalizarla. Lo bueno de la deducción natural, como su propio nombre indica, es que sigue más o menos los pasos que seguiría uno en una prueba informal
Esto quiere decir qur la formalización suele ser sencilla, una vez tienes la práctica suficiente.

Lo primero es seguir el sabio consejo de noisok, particularizar primero el cuantificador existencial y después los universales con la misma constante.
Entonces tendrás:

[texx]1. Pc\vee Mc\to Ac\vee Cc\vee Lc[/texx]
[texx]2. Ac\wedge Tc\to Cc\wedge Qc[/texx]
[texx]3. Gc\to Cc\wedge Qc[/texx]
[texx]4. Lc\vee Sc\to Gc\wedge Nc[/texx]

Afirmo que la opción buena es la segunda. Para probarla, solamente hay que probar [texx]Pc \wedge Tc \rightarrow Cc[/texx]. Ahora se trata de jugar un poco con las premisas: supón que tienes [texx]Pc \wedge Tc[/texx]. Quieres probar [texx]Cc[/texx].
Pongo el resto de la demostración informal en spoiler. Intenta hacerla tú y si no te sale (o si te sale y lo quieres comprobar), mira el spoiler.

Spoiler (click para mostrar u ocultar)

Más o menos cada línea del spoiler corresponde a la aplicación de alguna regla de deducción natural (o a la introducción o descarte de hipótesis). Trata de formalizarlo, es un poco largo, pero no debería ser muy difícil.

Veamos si lo formalicé correctamente:

[texx]
\begin{array}{lll}
1)&\forall x(Px\vee Mx\to Ax\vee Cx\vee Lx)&\text{Premisa}\\
2)&\forall x(Ax\wedge Tx\to Cx\wedge Qx)&\text{Premisa}\\
3)&\exists x(Lx\vee Sx\to Gx\wedge Nx)&\text{Premisa}\\
4)&\forall x(Gx\to Cx\wedge Qx)&\text{Premisa}\\
5)&Lc\vee Sc\to Gc\wedge Nc&\text{Particularización existencial 3)}\\
6)&Pc\vee Mc\to Ac\vee Cc\vee Lc&\text{Particularización universal 1)}\\
7)&Ac\wedge Tc\to Cc\wedge Qc&\text{Particularización universal 2)}\\
8)&Gc\to Cc\wedge Qc&\text{Particularización universal 4)}\\
9)&Pc\wedge Tc&\text{Premisa}\\
10)&Pc&\text{Eliminación conjunción 9)}\\
11)&Tc&\text{Eliminación conjunción 9)}\\
12)&Pc\vee Mc&\text{Introducción disyunción 10)}\\
13)&Ac\vee Cc\vee Lc&\text{Modus Ponens 6) y 12)}\\
14)&Ac&\text{Eliminación disyunción 13)}\\
15)&Ac\wedge Tc&\text{Introducción conjunción 14) y 12)}\\
16)&Cc\wedge Qc&\text{Modus Ponens 15) y 7)}\\
17)&Cc&\text{Eliminación conjunción 16)}\\
18)&Cc&\text{Eliminación disyunción 13)}\\
19)&Lc&\text{Eliminación disyunción 13)}\\
20)&Sc&\text{Premisa}\\
21)&Lc\vee Sc&\text{Introducción disyunción 20)}\\
22)&Gc\wedge Nc&\text{Modus Ponens 21) y 5)}\\
23)&Gc&\text{Eliminación conjunción 22)}\\
24)&Cc\wedge Qc&\text{Modus Ponens 23) y 8)}\\
25)&Cc&\text{Eliminación conjunción 24)}\\
26)&Pc\wedge Tc\to Cc&\text{Introducción implicador 9) y 25)}\\
27)&\exists x(Px\wedge Tx\to Cx)&\text{Introducción particularizador 26) y 9)}
\end{array}
[/texx]

Preguntas:

1) ¿Podemos tener como premisa en la línea [texx]9)\;Pc\wedge Tc[/texx] a [texx]Pc\vee Tc[/texx]? En ese caso sería todo exactamente igual salvo las líneas [texx]9[/texx], [texx]10[/texx] y [texx]11[/texx], pero el resto igual, por lo que podríamos garantizar que la opción (1) de las 4 es correcta, ¿verdad?

2) Entiendo que la respuesta a la pregunta anterior es falsa, porque podríamos dar un contraejemplo que lo invalide. Ahora bien, a primera vista es lógico elegir como premisa [texx]Pc\vee Tc[/texx] (la regla "Introducción disyunción" es una regla válida), por lo que la prueba sería igual de correcta. Con esto me refiero a que cualquier despistado como yo podría haber hecho lo mismo pero con una disyunción en vez de conjunción, así que con esto pregunto: como el enunciado pide "elegir la ÚNICA tesis válida", ¿no debemos probar (dando un contraejemplo) que las otras 3 opciones son FALSAS (no se desprenden de la hipótesis)? ¿Qué nos garantiza que con haber encontrado una válida (que no sé por qué sería válida si cambiar una conjunción por una disyunción como premisa da igual) automáticamente todas las demás sean falsas?

Gracias, como siempre.

Saludos
En línea
noisok
Semi pleno
***

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 72


Ver Perfil
« Respuesta #14 : 06/06/2019, 04:54:22 am »

Hola

Muchas gracias a todos! Me ha servido mucho su ayuda.

Si quieres dar una prueba formal, con deducción natural, lo primero que debes hacer es dar una prueba informal y después formalizarla. Lo bueno de la deducción natural, como su propio nombre indica, es que sigue más o menos los pasos que seguiría uno en una prueba informal
Esto quiere decir qur la formalización suele ser sencilla, una vez tienes la práctica suficiente.

Lo primero es seguir el sabio consejo de noisok, particularizar primero el cuantificador existencial y después los universales con la misma constante.
Entonces tendrás:

[texx]1. Pc\vee Mc\to Ac\vee Cc\vee Lc[/texx]
[texx]2. Ac\wedge Tc\to Cc\wedge Qc[/texx]
[texx]3. Gc\to Cc\wedge Qc[/texx]
[texx]4. Lc\vee Sc\to Gc\wedge Nc[/texx]

Afirmo que la opción buena es la segunda. Para probarla, solamente hay que probar [texx]Pc \wedge Tc \rightarrow Cc[/texx]. Ahora se trata de jugar un poco con las premisas: supón que tienes [texx]Pc \wedge Tc[/texx]. Quieres probar [texx]Cc[/texx].
Pongo el resto de la demostración informal en spoiler. Intenta hacerla tú y si no te sale (o si te sale y lo quieres comprobar), mira el spoiler.

Spoiler (click para mostrar u ocultar)

Más o menos cada línea del spoiler corresponde a la aplicación de alguna regla de deducción natural (o a la introducción o descarte de hipótesis). Trata de formalizarlo, es un poco largo, pero no debería ser muy difícil.

Veamos si lo formalicé correctamente:

[texx]
\begin{array}{lll}
1)&\forall x(Px\vee Mx\to Ax\vee Cx\vee Lx)&\text{Premisa}\\
2)&\forall x(Ax\wedge Tx\to Cx\wedge Qx)&\text{Premisa}\\
3)&\exists x(Lx\vee Sx\to Gx\wedge Nx)&\text{Premisa}\\
4)&\forall x(Gx\to Cx\wedge Qx)&\text{Premisa}\\
5)&Lc\vee Sc\to Gc\wedge Nc&\text{Particularización existencial 3)}\\
6)&Pc\vee Mc\to Ac\vee Cc\vee Lc&\text{Particularización universal 1)}\\
7)&Ac\wedge Tc\to Cc\wedge Qc&\text{Particularización universal 2)}\\
8)&Gc\to Cc\wedge Qc&\text{Particularización universal 4)}\\
9)&Pc\wedge Tc&\text{Premisa}\\
10)&Pc&\text{Eliminación conjunción 9)}\\
11)&Tc&\text{Eliminación conjunción 9)}\\
12)&Pc\vee Mc&\text{Introducción disyunción 10)}\\
13)&Ac\vee Cc\vee Lc&\text{Modus Ponens 6) y 12)}\\
14)&Ac&\text{Eliminación disyunción 13)}\\
15)&Ac\wedge Tc&\text{Introducción conjunción 14) y 12)}\\
16)&Cc\wedge Qc&\text{Modus Ponens 15) y 7)}\\
17)&Cc&\text{Eliminación conjunción 16)}\\
18)&Cc&\text{Eliminación disyunción 13)}\\
19)&Lc&\text{Eliminación disyunción 13)}\\
20)&Sc&\text{Premisa}\\
21)&Lc\vee Sc&\text{Introducción disyunción}\\
22)&Gc\wedge Nc&\text{Modus Ponens 21) y 5)}\\
23)&Gc&\text{Eliminación conjunción 22)}\\
24)&Cc\wedge Qc&\text{Modus Ponens 23) y 8)}\\
25)&Cc&\text{Eliminación conjunción 24)}\\
26)&Pc\wedge Tc\to Cc&\text{Introducción implicador 9) y 25)}\\
27)&\exists x(Px\wedge Tx\to Cx)&\text{Introducción particularizador 26) y 9)}
\end{array}
[/texx]

Preguntas:

1) ¿Podemos tener como premisa en la línea [texx]9)\;Pc\wedge Tc[/texx] a [texx]Pc\vee Tc[/texx]? En ese caso sería todo exactamente igual salvo las líneas [texx]9[/texx], [texx]10[/texx] y [texx]11[/texx], pero el resto igual, por lo que podríamos garantizar que la opción (1) de las 4 es correcta, ¿verdad?


Gracias, como siempre.

Saludos
[texx]
\begin{array}{lll}
1)&\forall x(Px\vee Mx\to Ax\vee Cx\vee Lx)&\text{Premisa}\\
2)&\forall x(Ax\wedge Tx\to Cx\wedge Qx)&\text{Premisa}\\
3)&\exists x(Lx\vee Sx\to Gx\wedge Nx)&\text{Premisa}\\
4)&\forall x(Gx\to Cx\wedge Qx)&\text{Premisa}\\
5)&Lc\vee Sc\to Gc\wedge Nc&\text{Particularización existencial 3)}\\
6)&Pc\vee Mc\to Ac\vee Cc\vee Lc&\text{Particularización universal 1)}\\
7)&Ac\wedge Tc\to Cc\wedge Qc&\text{Particularización universal 2)}\\
8)&Gc\to Cc\wedge Qc&\text{Particularización universal 4)}\\
9)&\ \ Pc\wedge Tc&\text{Premisa condicional}\\
10)&\ \ Pc&\text{Eliminación conjunción 9)}\\
11)&\ \ Tc&\text{Eliminación conjunción 9)}\\
12)&\ \ Pc\vee Mc&\text{Introducción disyunción 10)}\\
13)&\ \ Ac\vee Cc\vee Lc&\text{Modus Ponens 6) y 12)}\\
14)&\ \ \ \ Ac&\text{Premisa condicional}\\
15)&\ \ \ \ Ac\wedge Tc&\text{Introducción conjunción 14) y 11)}\\
16)&\ \ \ \ Cc\wedge Qc&\text{Modus Ponens 15) y 7)}\\
17)&\ \ \ \ Cc&\text{Eliminación conjunción 16)}\\
18)&\ \ Ac\to Cc&\text{Regla Condicional 14) y 17)}\\
19)&\ \ \ \ Lc&\text{Premisa condicional}\\
20)&\ \ \ \ Lc\vee Sc&\text{Introducción disyunción 19)}\\
21)&\ \ \ \ Gc\wedge Nc&\text{Modus Ponens 21) y 5)}\\
22)&\ \ \ \ Gc&\text{Eliminación conjunción 22)}\\
23)&\ \ \ \ Cc\wedge Qc&\text{Modus Ponens 23) y 8)}\\
24)&\ \ \ \ Cc&\text{Eliminación conjunción 23)}\\
25)&\ \ Lc\to Cc&\text{Regla Condicional 19) y 24)}\\
26)&\ \ Cc\to Cc&\text{Tautologia}\\
27)&\ \ Ac \vee Cc \to Cc&\text{Regla del Dilema 18) y 26)}\\
28)&\ \ Ac \vee Cc \vee Lc \to Cc&\text{Regla del Dilema 25) y 27)}\\
29)&\ \ Cc &\text{Modus Ponens 28) y 13)}\\
30)&Pc\wedge Tc\to Cc&\text{Regla Condicional 9) y 29)}\\
31)&\exists x(Px\wedge Tx\to Cx)&\text{Introducción particularizador 30)}
\end{array}
[/texx]

Hola, gran trabajo con la deducción.  He hecho algún cambio y creo que responde a tu primera pregunta, en parte al menos: En 9) introducimos una suposición a nuestro conjunto de premisas, por eso trabajamos la deducción desplazando todo a la derecha. También lo hacemos en 14) y 19). Cuando queramos volver a la izquierda, introducimos la regla condicional, en la cual se ve que nuestra premisa condicional es el antecedente de cualquier cosa deducida bajo la premisa. La 26) no se muy bien como expresarla, pero es una tautología y se pueden poner en cualquier momento.

Nota: algunos ponen palos en las deducciones condicionales, pero no se muy bien como va y seguramente quede mejor indexado todo.

Saludos


En línea
geómetracat
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 809



Ver Perfil
« Respuesta #15 : 06/06/2019, 07:50:26 am »

La deducción de noisok está perfecta, módulo detalles concretos que dependen de cómo te hayan introducido exactamente la deducción natural.
Sobre el uso e la tautología [texx]Cc \rightarrow Cc[/texx], siempre la puedes demostrar "desde cero" así:

[texx]
\begin{array}{lll}
1)&\ \ Cc&\text{Premisa}\\
2)&\ \ Cc&\text{1)}\\
1)&Cc \rightarrow Cc&\text{Introducción del implicador 1),2)}\\
\end{array}
[/texx]

En general, cuando trabajamos en deducción natural hay que prestar atención a las premisas que introducimos (aquí me refiero a lo que noisok llama premisa condicional, no a las premisas que forman parte del problema) y a cuándo las descargamos (vía introducción del implicador). Esto se suele hacer poniendo una línea vertical que abarca todas las filas desde que introduces la premisa hasta que  descartas, o con la solución de noisok de indentar las filas desde que introduces la premisa hasta que la descartas. Para que la deducción sea válida en la última línea debes haber descartado todas las premisas que hayas introducido.

Preguntas:

1) ¿Podemos tener como premisa en la línea [texx]9)\;Pc\wedge Tc[/texx] a [texx]Pc\vee Tc[/texx]? En ese caso sería todo exactamente igual salvo las líneas [texx]9[/texx], [texx]10[/texx] y [texx]11[/texx], pero el resto igual, por lo que podríamos garantizar que la opción (1) de las 4 es correcta, ¿verdad?

No. El problema es que si tienes [texx]Pc \vee Tc[/texx] para demostrar [texx]Pc \vee Tc \rightarrow Cc[/texx] necesitas primero asumir [texx]Pc[/texx] y probar [texx]Cc[/texx] (únicamente a partir de [texx]Pc[/texx]) y luego asumir [texx]Tc[/texx] y probar [texx]Cc[/texx]  (únicamente a partir de [texx]Cc[/texx]). Si intentas hacer esto verás que es imposible. Fíjate que en la demostración hay que usar tanto [texx]Pc[/texx] como [texx]Tc[/texx].

Cita
2) Entiendo que la respuesta a la pregunta anterior es falsa, porque podríamos dar un contraejemplo que lo invalide. Ahora bien, a primera vista es lógico elegir como premisa [texx]Pc\vee Tc[/texx] (la regla "Introducción disyunción" es una regla válida), por lo que la prueba sería igual de correcta. Con esto me refiero a que cualquier despistado como yo podría haber hecho lo mismo pero con una disyunción en vez de conjunción, así que con esto pregunto: como el enunciado pide "elegir la ÚNICA tesis válida", ¿no debemos probar (dando un contraejemplo) que las otras 3 opciones son FALSAS (no se desprenden de la hipótesis)? ¿Qué nos garantiza que con haber encontrado una válida (que no sé por qué sería válida si cambiar una conjunción por una disyunción como premisa da igual) automáticamente todas las demás sean falsas?

Como he dicho antes, no es posible dar una prueba válida de 1). En general, se puede dar una demostración válida de una fórmula a partir de unas premisas si y solamente si no existe ningún modelo donde las premisas sean verdaderas y la conclusión falsa (es decir, no hay contraejemplos). Si das una demostración, pero eres capaz de construir además un contraejemplo (modelo donde las premisas son verdaderas y la conclusión falsa) es que algo has hecho mal.
El hecho de que una fórmula demostrada a partir de unas premisas es verdadera en todos los modelos en los que las premisas son verdaderas (no se pueden demostrar cosas "falsas") se conoce como teorema de adecuación (soundness en inglés), mientras que el hecho de que cualquier fórmula que sea verdadera en un modelo donde las premisas son verdaderas es demostrable a partir de las premisas se conoce como teorema de completitud (y es mucho más difícil de demostrar que el de adecuación).

Otro tema es que los que han puesto el problema nos podrían haber engañado y haber puesto varias opciones correctas, es decir, varias fórmulas que se deducen de las premisas que te dan. Para descartar este caso, en efecto hay que construir modelos donde las premisas sean verdaderas pero las conclusiones falsas. Yo lo hice más arriba con la fórmula de 1) en respuesta a feriva. Puedes probar a construir contraejemplos parecidos para 3) y 4). Si no me equivoco lo puedes hacer con un modelo con un único elemento, como el que usé yo para 1).
En línea

La ecuación más bonita de las matemáticas: [texx]d^2=0[/texx]
manooooh
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 2.445


Ver Perfil
« Respuesta #16 : 07/06/2019, 02:58:19 am »

Hola

En 9) introducimos una suposición a nuestro conjunto de premisas, por eso trabajamos la deducción desplazando todo a la derecha. También lo hacemos en 14) y 19). (...)

De acuerdo.

(...) Cuando queramos volver a la izquierda, introducimos la regla condicional, en la cual se ve que nuestra premisa condicional es el antecedente de cualquier cosa deducida bajo la premisa. (...)

No entiendo la última parte.

(...) La 26) no se muy bien como expresarla, pero es una tautología y se pueden poner en cualquier momento.

De acuerdo.

No entiendo cómo trabaja la regla "Regla Condicional". ¿Podrías esquematizarlo con la estructura de un razonamiento, por favor?



En general, cuando trabajamos en deducción natural hay que prestar atención a las premisas que introducimos (aquí me refiero a lo que noisok llama premisa condicional, no a las premisas que forman parte del problema) y a cuándo las descargamos (vía introducción del implicador). Esto se suele hacer poniendo una línea vertical que abarca todas las filas desde que introduces la premisa hasta que  descartas, o con la solución de noisok de indentar las filas desde que introduces la premisa hasta que la descartas. Para que la deducción sea válida en la última línea debes haber descartado todas las premisas que hayas introducido.

Esto debe ser clave y no logro entenderlo.

¿Se pueden agregar hipótesis como yo quiera? ¿Podría agregar la premisa [texx]p[/texx] en la línea 64 y [texx]\neg p[/texx] en la 119? ¿Bajo qué condiciones (si las hubiera) se pueden agregar hipótesis i.e. en nuestro caso, podría haber "sacado de la manga" las proposiciones [texx]Lc[/texx], [texx]Cc[/texx] y [texx]Mc[/texx] y ponerlas donde yo quiera?

Por último, no entiendo "Para que la deducción sea válida en la última línea debes haber descartado todas las premisas que hayas introducido", ¿a qué te referís con "Descartar": haber operado con ellas al menos 1 vez?

No. El problema es que si tienes [texx]Pc \vee Tc[/texx] para demostrar [texx]Pc \vee Tc \rightarrow Cc[/texx] necesitas primero asumir [texx]Pc[/texx] y probar [texx]Cc[/texx] (únicamente a partir de [texx]Pc[/texx]) y luego asumir [texx]Tc[/texx] y probar [texx]Cc[/texx]  (únicamente a partir de [texx]Cc[/texx]). Si intentas hacer esto verás que es imposible. Fíjate que en la demostración hay que usar tanto [texx]Pc[/texx] como [texx]Tc[/texx].

Pero a priori no conocíamos la demostración, así que no podíamos saber que necesitábamos de [texx]Pc[/texx] y [texx]Tc[/texx].

No entiendo por qué debe haber diferencias entre [texx]\vee[/texx] y [texx]\wedge[/texx], si ambas forman un sistema dual, como si [texx]p\wedge q=q\wedge p[/texx] entonces la dual también vale i.e. [texx]p\vee q=q\vee p[/texx]. Es decir no entendí la frase "El problema es que si tienes [texx]Pc \vee Tc[/texx] para demostrar [texx]Pc \vee Tc \rightarrow Cc[/texx] necesitas primero asumir [texx]Pc[/texx] y probar [texx]Cc[/texx] (únicamente a partir de [texx]Pc[/texx]) y luego asumir [texx]Tc[/texx] y probar [texx]Cc[/texx]  (únicamente a partir de [texx]Cc[/texx])".

Como he dicho antes, no es posible dar una prueba válida de 1). En general, se puede dar una demostración válida de una fórmula a partir de unas premisas si y solamente si no existe ningún modelo donde las premisas sean verdaderas y la conclusión falsa (es decir, no hay contraejemplos). Si das una demostración, pero eres capaz de construir además un contraejemplo (modelo donde las premisas son verdaderas y la conclusión falsa) es que algo has hecho mal.

Te entiendo.

El hecho de que una fórmula demostrada a partir de unas premisas es verdadera en todos los modelos en los que las premisas son verdaderas (no se pueden demostrar cosas "falsas") se conoce como teorema de adecuación (soundness en inglés), mientras que el hecho de que cualquier fórmula que sea verdadera en un modelo donde las premisas son verdaderas es demostrable a partir de las premisas se conoce como teorema de completitud (y es mucho más difícil de demostrar que el de adecuación).

Seguramente tiene que ver con Gödel y su teorema :lengua_afuera: pero no logro identificar la similitud entre el teorema de adecuación y el de completitud. ¿Acaso uno implica al otro y viceversa?

Otro tema es que los que han puesto el problema nos podrían haber engañado y haber puesto varias opciones correctas, es decir, varias fórmulas que se deducen de las premisas que te dan. Para descartar este caso, en efecto hay que construir modelos donde las premisas sean verdaderas pero las conclusiones falsas. Yo lo hice más arriba con la fórmula de 1) en respuesta a feriva. Puedes probar a construir contraejemplos parecidos para 3) y 4). Si no me equivoco lo puedes hacer con un modelo con un único elemento, como el que usé yo para 1).

Bajo el supuesto de que hay más de 1 opción correcta, ¿no es que la tesis es lo mismo que la conclusión? O sea, no entiendo por qué decís "fórmulas que se deducen de las premisas" (entendiendo "fórmula válidas" como "tesis verdaderas") y luego "conclusiones falsas" (entendidas como "tesis falsas").

Gracias!
Saludos
En línea
geómetracat
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 809



Ver Perfil
« Respuesta #17 : 07/06/2019, 05:25:53 am »

Esto debe ser clave y no logro entenderlo.

¿Se pueden agregar hipótesis como yo quiera? ¿Podría agregar la premisa [texx]p[/texx] en la línea 64 y [texx]\neg p[/texx] en la 119? ¿Bajo qué condiciones (si las hubiera) se pueden agregar hipótesis i.e. en nuestro caso, podría haber "sacado de la manga" las proposiciones [texx]Lc[/texx], [texx]Cc[/texx] y [texx]Mc[/texx] y ponerlas donde yo quiera?

Por último, no entiendo "Para que la deducción sea válida en la última línea debes haber descartado todas las premisas que hayas introducido", ¿a qué te referís con "Descartar": haber operado con ellas al menos 1 vez?

Puedes agregar todas las hipótesis que quieras en mitad de la demostración (sí, cualquier fórmula que se te ocurra), pero para que sea válida la demostración las debes haber descartado todas al final. ¿Cómo se descartan las hipótesis? Mediante la aplicación o bien de la regla de introducción del implicador, o bien de la regla de eliminación de la disyunción.
Para demostrar una implicación como [texx]\phi \rightarrow \psi[/texx] en deducción natural, lo que debes hacer es asumir [texx]\phi[/texx] como hipótesis, a partir de ahí demostrar [texx]\psi[/texx] (usando quizás las premisas de las que partes u otras fórmulas ya demostradas), y finalmente aplicar la regla de introducción del implicador para descartar la hipótesis y obtener una prueba de [texx]\phi \rightarrow \psi[/texx].
De manera parecida, si tienes una disyunción [texx]\phi \vee \psi[/texx] y quieres probar otra fórmula [texx]\chi[/texx], puedes hacerlo suponiendo como hipótesis [texx]\phi[/texx] y probando [texx]\chi[/texx], y por otro lado suponiendo como hipótesis [texx]\psi[/texx] y probando [texx]\chi[/texx] (hay que usar dos ramas, es decir, no puedes suponer [texx]\phi[/texx] y [texx]\psi[/texx] a la vez). Entonces, usando la regla de eliminación del disyuntor obtienes una prueba de [texx]\chi[/texx], sin hipótesis.
De todas maneras los detalles pueden cambiar según la presentación de la deducción natural. Por ejemplo, noisok no usa la eliminación de la disyunción en este sentido, aunque esencialmente es lo mismo. Fíjate lo que hace en las líneas 13-18 de su demostración: asume como hipótesis cada término de la disyunción [texx]Ac \vee Cc \vee Lc[/texx] por separado y en los tres casos prueba que [texx]Cc[/texx] se cumple. Él usa primero introducción del implicador y luego la regla del dilema para obtener una prueba de [texx]Ac \vee Cc \vee Lc \rightarrow Cc[/texx]. Con la versión de la eliminación de la disyunción que he dado antes, lo que harías es asumir [texx]Ac[/texx] y probar [texx]Cc[/texx], asumir [texx]Cc[/texx] y probar [texx]Cc[/texx] y asumir [texx]Lc[/texx] y probar [texx]Cc[/texx] y usar eliminación de la disyunción para obtener una prueba (sin hipótesis) de [texx]Cc[/texx]. (Si quieres ser estricto de hecho deberías usar dos veces eliminación de la disyunción, porque estrictamente hablando la regla vale para una disyunción de dos fórmulas, no de tres.)

En fin, la verdad es que hablar de los detalles concretos es un rollo, y como ya he dicho varias veces depende de qué versión concreta de deducción natural te hayan explicado o hayas estudiado. Si quieres detalles completos primero habría que ponerse de acuerdo en las reglas exactas que podemos usar. Pero espero que al menos se haya entendido la idea y la filosofía de la deducción natural, asumir hipótesis y descartarlas.

Cita
Pero a priori no conocíamos la demostración, así que no podíamos saber que necesitábamos de [texx]Pc[/texx] y [texx]Tc[/texx].

No, claro. Lo que digo es que puedes intentar de todas las formas que quieras dar una demostración de [texx]\exists x (Px \vee Tx \rightarrow Cx)[/texx] a partir de las premisas, que te será totalmente imposible dar una demostración válida. Y la forma de demostrar que es imposible dar una demostración válida de [texx]\exists x(Px \vee Tx \rightarrow Cx)[/texx] es dar un contraejemplo: construir un modelo donde las premisas sean verdaderas pero [texx]\exists x(Px \vee Tx \rightarrow Cx)[/texx] sea falsa.

Cita
No entiendo por qué debe haber diferencias entre [texx]\vee[/texx] y [texx]\wedge[/texx], si ambas forman un sistema dual, como si [texx]p\wedge q=q\wedge p[/texx] entonces la dual también vale i.e. [texx]p\vee q=q\vee p[/texx]. Es decir no entendí la frase "El problema es que si tienes [texx]Pc \vee Tc[/texx] para demostrar [texx]Pc \vee Tc \rightarrow Cc[/texx] necesitas primero asumir [texx]Pc[/texx] y probar [texx]Cc[/texx] (únicamente a partir de [texx]Pc[/texx]) y luego asumir [texx]Tc[/texx] y probar [texx]Cc[/texx]  (únicamente a partir de [texx]Cc[/texx])".

Espero que ahora se entienda mejor la frase: lo que digo es que hay que usar la regla de eliminación de la disyunción para probar [texx]Cc[/texx] a partir de [texx]Pc \vee Tc[/texx].
Por otro lado, hay que tener cuidado con el tema de la dualidad. Desde luego que haya una dualidad entre [texx]\wedge[/texx] y [texx]\vee[/texx] no quiere decir para nada que si puedes demostrar una fórmula [texx]\phi[/texx] entonces puedes demostrar la fórmula resultante de cambiar [texx]\wedge[/texx] por [texx]\vee[/texx] en [texx]\phi[/texx]. Por ejemplo, [texx]p \vee \neg p[/texx] es una tautología, luego se puede demostrar, pero [texx]p \wedge \neg p[/texx] no.
Fíjate que esto tiene perfecto sentido, intuitivamente: uno espera ser capaz de demostrar más cosas teniendo dos fórmulas de partida, que si solamente tienes una de las fórmulas (y además no sabe cuál de ellas, de manera que tienes que dar una demostración para cada una por separado).

La expresión de la dualidad entre [texx]\wedge[/texx] y [texx]\vee[/texx] son las reglas de De Morgan, y una consecuencia es que si [texx]\phi, \psi[/texx] son fórmulas donde no aparecen implicaciones, entonces [texx]\phi \rightarrow \psi[/texx] es equivalente a [texx]\psi^* \rightarrow \phi^*[/texx], donde la estrella indica intercambiar [texx]\wedge[/texx] y [texx]\vee[/texx] (y si son fórmulas de primer orden también [texx]\forall[/texx] y [texx]\exists[/texx]). Además esto solo sirve para demostraciones sin premisas, si tienes premisas éstas también deben cambiar.

Cita
Seguramente tiene que ver con Gödel y su teorema :lengua_afuera: pero no logro identificar la similitud entre el teorema de adecuación y el de completitud. ¿Acaso uno implica al otro y viceversa?

La única relación con Gödel es que Gödel fue el primero en demostrar el teorema de completitud. Si estás pensando en los famosos teoremas de incompletitud de Gödel, no, no tienen mucho que ver.

Quizás sea mejor enunciarlo de una manera más formal. Si [texx]\phi[/texx] es una fórmula y [texx]\Gamma[/texx] es un conjunto de fórmulas, escribimos [texx]\Gamma \vdash \phi[/texx] para denotar que existe una demostración de [texx]\phi[/texx] con premisas en [texx]\Gamma[/texx]. De manera parecida, escibimos [texx]\Gamma \models \phi[/texx] para denotar que en todo modelo donde cada fórmula de [texx]\Gamma[/texx] es verdadera, [texx]\phi[/texx] también lo es.

Fíjate que la relación [texx]\Gamma \vdash \phi[/texx] es una relación puramente sintáctica, es decir, lo único que afirma es que existe un procedimiento mecánico para derivar [texx]\phi[/texx] a partir de fórmulas en [texx]\Gamma[/texx] usando una serie de reglas. Por el contrario, [texx]\Gamma \models \phi[/texx] es una relación semántica, es decir, es lo que entendemos cuando decimos [texx]\phi[/texx] se sigue de [texx]\Gamma[/texx]: que en toda situación que nos podamos imaginar en la que todas las fórmulas de [texx]\Gamma[/texx] sean verdaderas, también es verdadera [texx]\phi[/texx].
En matemáticas, o en lógica en general, lo que nos interesa realmente es la relación [texx]\Gamma \models \phi[/texx], que es la que lleva contenido semántico. Pero comprobar que algo es verdadero en todos los modelos posibles es normalmente muy difícil, pues primero habría que saber construir todos los modelos donde un conjunto de fórmulas es verdadero, y esto muchas veces no es factible, pues hay infinitos modelos. Además muchas veces no es nada fácil saber si una fórmula es verdadera o no en un modelo dado, porque implica hacer infinitas comprobaciones.
Entonces nos inventamos una relación [texx]\Gamma \vdash \phi[/texx] que es finitaria: una demostración de [texx]\phi[/texx] a partir de [texx]\Gamma[/texx] es un objeto finito, involucra un número finito de fórmulas. Pero por supuesto, estas demostraciones formales serían completamente inútiles si la relación [texx]\vdash[/texx] no tuviera nada que ver con [texx]\models[/texx]. Fíjate que las reglas de la lógica ya están hechas pensando en la semántica. Cuando uno dice que de la fórmula [texx]p \wedge q[/texx] se puede obtener [texx]p[/texx] (que es una regla formal, es como si te digo que hay una reglaque dice que de la cadena de símbolos [texx]a*b[/texx] se puede obtener [texx]a[/texx]) está ya pensando en que en un modelo [texx]p \wedge q[/texx] se interpretará como "tanto [texx]p[/texx] como [texx]q[/texx] son verdaderas en el modelo".
Entonces, la pregunta clave es ¿cuál es la relación entre [texx]\vdash[/texx] y [texx]\models[/texx]?
Aquí entran nuestros dos teoremas.

El teorema de adecuación dice que [texx]\Gamma \vdash \phi[/texx] implica [texx]\Gamma \models \phi[/texx]. Es decir, esto nos dice esencialmente que nunca vamos a poder demostrar cosas falsas. Si existe una demostración de [texx]\phi[/texx] a partir de fórmulas en [texx]\Gamma[/texx], en cualquier modelo posible donde las fórmulas de [texx]\Gamma[/texx] sean verdaderas, [texx]\phi[/texx] también lo será.
Este teorema es bastante fácil de demostrar: simplemente basta comprobar que para cada regla de tu cálculo deductivo (por ejemplo, deducción natural), si las premisas de la regla son verdadera en un modelo, entonces la conclución de la regla también lo es.
El teorema de adecuación es simplemente una comprobación de que tu cálculo deductivo es "correcto". Si te inventas un cálculo deductivo y no cumple el teorema de adecuación, ya lo puedes tirar, pues si te permite demostrar cosas falsas no sirve para nada.

El teorema de completitud es mucho más interesante, Dice que si [texx]\Gamma \models phi[/texx] entonces [texx]\Gamma \vdash \phi[/texx]. Esto es, que todo lo que es verdadero (en todo modelo) es demostrable. O usando el contrarecíproco, que si una fórmula no se puede demostrar, entonces existe algún modelo en el que es falsa. Este teorema es mucho más profundo, y su demostración es no trivial, a diferencia del teorema de adecuación.

Cita
Otro tema es que los que han puesto el problema nos podrían haber engañado y haber puesto varias opciones correctas, es decir, varias fórmulas que se deducen de las premisas que te dan. Para descartar este caso, en efecto hay que construir modelos donde las premisas sean verdaderas pero las conclusiones falsas. Yo lo hice más arriba con la fórmula de 1) en respuesta a feriva. Puedes probar a construir contraejemplos parecidos para 3) y 4). Si no me equivoco lo puedes hacer con un modelo con un único elemento, como el que usé yo para 1).

Bajo el supuesto de que hay más de 1 opción correcta, ¿no es que la tesis es lo mismo que la conclusión? O sea, no entiendo por qué decís "fórmulas que se deducen de las premisas" (entendiendo "fórmula válidas" como "tesis verdaderas") y luego "conclusiones falsas" (entendidas como "tesis falsas")

Esto no lo entiendo. Yo lo único que decía es que si no sabes de entrada que solamente una opción es correcta, para demostrar por ejemplo que no existe ninguna demostración de [texx]\exists x(Tx \vee Px \rightarrow Cx)[/texx] a partir de las cuatro premisas que te dan, hay que constuir un modelo donde las premisas sean verdaderas y la fórmula [texx]\exists x(Tx \vee Px \rightarrow Cx)[/texx] falsa.

En fin, espero que el rollo que te he soltado te sirva para aclararte un poco, y no para liarte más todavía.
En línea

La ecuación más bonita de las matemáticas: [texx]d^2=0[/texx]
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!