Autor Tema: Deducción natural

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

27 Marzo, 2019, 07:25 am
Leído 1726 veces

Sdc

  • Nuevo Usuario
  • Mensajes: 4
  • Karma: +0/-0
  • Sexo: Masculino
Buenas a todos estoy empezando con las demostraciones a través de la deducción natural y me tope con el siguiente ejemplo:



Tengo la duda de si es posible demostrar \( q \rightarrow{s} \) con simplemente esa hipotesis anidada, es decir, yo pense que era necesario hacer una eliminación de la disyunción para poder dar por hecho el resultado de :

\( q \rightarrow{s} \)

Detallando un poco mas.... yo pensaría que primero debería dar como suposición que 'q' es verdadera como lo esta haciendo en la imagen para finalmente llegar a \( q \rightarrow{s} \) y posterior debería partir de 'r' para llegar a la misma conclusión y utilizar la regla de eliminación de disyunción. Tengo duda si solo realiza la hipótesis con 'q' debido a que una vez que da por supuesto eso también determina que 'r' es verdadero y ya no tiene que hacer la segunda suposición para quitar la disyunción.

Ademas de eso y para quitarme un poco el miedo... ¿Que puede ser tomado como hipótesis?, ¿absolutamente todo?, es decir que ¿ la deducción natural solo me ayuda a comprobar si algo es verdadero para algún caso posible ? ... O ¿ solo puedo tomar como hipótesis o suposición el antecedente exclusivamente de la conclusión o lo que quiero llegar a demostrar ?.

27 Marzo, 2019, 10:43 am
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 46,431
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Tengo la duda de si es posible demostrar \( q \rightarrow{s} \) con simplemente esa hipotesis anidada, es decir, yo pense que era necesario hacer una eliminación de la disyunción para poder dar por hecho el resultado de :

\( q \rightarrow{s} \)

Tienes tres hipótesis.

1. \( (p\to (q\wedge r)) \)
2. \( q\to r \)
3. \( r\to s \)

Por la transitividad de la implicación de (2) y (3) se deduce que \( q\to s \).

Citar
Detallando un poco mas.... yo pensaría que primero debería dar como suposición que 'q' es verdadera como lo esta haciendo en la imagen para finalmente llegar a \( q \rightarrow{s} \) y posterior debería partir de 'r' para llegar a la misma conclusión y utilizar la regla de eliminación de disyunción. Tengo duda si solo realiza la hipótesis con 'q' debido a que una vez que da por supuesto eso también determina que 'r' es verdadero y ya no tiene que hacer la segunda suposición para quitar la disyunción.

No estoy seguro de entender lo que dices; simplemente puedes demostrar la transitividad de la implicación o todo tu problema con una tabla de verdad del estilo de la que viene en el enlace anterior.

Citar
Ademas de eso y para quitarme un poco el miedo... ¿Que puede ser tomado como hipótesis?, ¿absolutamente todo?, es decir que ¿ la deducción natural solo me ayuda a comprobar si algo es verdadero para algún caso posible ? ... O ¿ solo puedo tomar como hipótesis o suposición el antecedente exclusivamente de la conclusión o lo que quiero llegar a demostrar ?.

Tampoco acabo de entender que estás diciendo aquí. Lo que te están pidiendo en este ejercicio es que muestres que de tres hipótesis se puede deducir una determinada tesis. ¿Cuál es el problema?.

Saludos.

27 Marzo, 2019, 01:52 pm
Respuesta #2

Sdc

  • Nuevo Usuario
  • Mensajes: 4
  • Karma: +0/-0
  • Sexo: Masculino
Una disculpa, me falto especificar mas el entorno del problema... Estoy viendo la deducción natural en el sistema axiomatico de kleene, a partir de el el solo puedo utilizar 8 reglas de inferencia que son la implicación y la eliminación de la conjunción,disyunción,negacion e implicación. He aquí un link que explica muy bien eso.
http://di002.edv.uniovi.es/~labra/Logica/apuntes/nd.pdf

Mi duda surge en la ley de la eliminación de una disyunción que es lo que creo que esta aplicando el autor del ejercicio anterior,esta regla tiene esta estructura.


Y yo la interpreto como que para eliminar la disyunción debo partir primero de una de las proposiciones de la disyunción como un supuesto y llegar a un resultado pero debo repetir ese proceso con la segunda proposición de la disyunción para yo afirmar que esa conclusión que se da es verdadera mientras que en el ejercicio anterior no hace estos dos sub bloques y simplemente supone que la primera proposición de la disyunción es verdadera... Llega a la conclusión y lo le importa comprobar esto para la segunda proposición y así manejar la regla como tal cual esta declarada.

A partir de lo anterior me causa la duda de  ¿ que puede ser manejado como un supuesto?, en los anteriores problemas yo solo había necesitado manejar como supuesto el antecedente de a lo que quería llegar pero no encontrado ninguna fuente que me deje muy claro que es lo que realmente puedo dar como supuesto en una deducción natural y eso me confunde un poco debido a que vengo de ver sistemas formales en los cuales solo tenia 3 reglas y eran muy rígidos en el sentido de que no podía dar nada por hecho pero en este sistema ahora se me permite crear suposiciones pero no sé si puedo suponer todo lo que yo quiera o solo el antecedente de una implicación o para ser mas específicos solo antecedente de la implicación que forma parte de lo que queremos demostrar.


27 Marzo, 2019, 01:52 pm
Respuesta #3

geómetracat

  • Moderador Global
  • Mensajes: 1,332
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
En deducción natural puedes tomar cualquier fórmula como hipótesis y luego usar introducción del implicador para descartar la hipótesis y obtener una implicación. Otra cosa es que eso te ayude a probar lo que quieras probar. Normalmente la parte difícil es saber qué hipótesis debes tomar para llegar a lo que quieres.

La prueba de \( q \rightarrow s \) de la imagen es correcta: asumes \( q \) como hipótesis, a partir de ahí pruebas \( s \) y por introducción del implicador descartas la hipótesis \( q \) y obtienes una prueba de \( q \rightarrow s \). En particular, esta parte no tiene nada que ver con eliminación del disyuntor, no usa 2 (la única disyunción que aparece ahí) para nada.

Más tarde, usa eliminación del disyuntor 2 \( q \vee r \) para obtener una prueba de \( s \): esto es lícito porque ya has probado antes tanto \( q \rightarrow s \) como \( r \rightarrow s \).

Añadido: Viendo la regla que te han dado, creo que el ejemplo es algo confuso, aunque son detalles sin demasiada importancia. Si quieres usar la regla tal cual, para eliminar el disyuntor no deberías probar \( q \rightarrow s \) y \( r \rightarrow s \) como hacen en el ejemplo, sino suponer \( q \) como hipótesis y llegar a \( s \) (como hacen ahí), ahora aparte suponer \( r \) como hipótesis y llegar a \( s \) (trivial: eliminación del implicador en p3) y ahora usar eliminación de la disyunción para obtener una prueba de \( s \) incondicional, es decir, sin suponer ni \( q \) ni \( r \).
La ecuación más bonita de las matemáticas: \( d^2=0 \)

27 Marzo, 2019, 02:01 pm
Respuesta #4

Sdc

  • Nuevo Usuario
  • Mensajes: 4
  • Karma: +0/-0
  • Sexo: Masculino
Ahora comprendo.. Entonces la razón por la cual no hace esa segunda parte es por que la esta suponiendo ya de la premisa. Solo reafirmando entonces podriamos decir que la suposición puede ser cualquier proposición que pueda aparecer en una disyunción,conjunción,implicacion o como parte de las otras proposiciones dentro de las premisas o de la conclusión a la que queremos llegar , simplemente debe ser algo que se me ocurra que me puede hacer llegar a la conclusión y que supongo que la única regla es que no sea la misma conclusión a la que quieres llegar. Entonces la deducción natural me va dar una demostración que no siempre va ser una tautología, es decir, ¿ se puede demostrar cosas que no siempre son tautologías pero que se cumplen cuando se hacen las suposiciones especificas que se planteo en el proceso?

27 Marzo, 2019, 02:31 pm
Respuesta #5

geómetracat

  • Moderador Global
  • Mensajes: 1,332
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
A ver, con deducción natural puedes demostrar exactamente lo mismo que con cualquier otro cálculo deductivo, ni más ni menos. Si no partes de ninguna premisa, puedes demostrar exactamente las tautologías. Si tienes premisas (como en el ejemplo), puedes demostrar exactamente las proposiciones que son verdaderas asumiendo que las premisas son verdaderas (más técnicamente, puedes demostrar exactamente las fórmulas que cumplen que cualquier valuación que hace verdaderas las premisas también hace verdadera la conclusión).

Otra cosa es que en mitad de una demostración en deducción natural puedas hacer hipótesis extra (las que quieras, como te he dicho antes) y usarlas libremente para probar lo que quieras. Pero lo importante es que toda hipótesis extra que hagas en mitad de una demostración debe descartarse. Es decir, no pueden haber hipótesis abiertas al final de la demostración (que no sean las premisas), sino no es una prueba válida.
La ecuación más bonita de las matemáticas: \( d^2=0 \)

27 Marzo, 2019, 02:57 pm
Respuesta #6

feriva

  • Matemático
  • Mensajes: 8,933
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
  • ¡EUKERA!... ¡UEREKA!... ¡EUREKA! (corregido)


Ademas de eso y para quitarme un poco el miedo...

Yo todo eso no lo entiendo muy bien, pero te digo mi deducción natural sin miedo (más natural que la mía, que no lo he estudiado, difícil que la haya) es la siguiente

Si \( p\rightarrow(q\vee r)
  \) y a la vez ocurre \( q\rightarrow r
  \), está diciendo que implica las dos conjuntamente \( p\rightarrow(q\wedge r)
  \).

Spoiler

Claro, piensa que eso es análogo a ver la equivalencia en estas perogrulladas, si \( p\rightarrow(q\vee q)
  \) entonces también \( p\rightarrow(q\wedge q)
  \), por que ambas quieren decir que \( p\rightarrow q
  \), no hay diferencia en ninguna.

[cerrar]

Por lo mismo, si \( r\rightarrow s
  \), entonces esto \( p\rightarrow(q\wedge r)
  \) implica a la vez esto \( p\rightarrow(q\wedge s)
  \).

De lo último, obviamente, por ser una conjunción, \( p\rightarrow s)
  \).

Saludos.

27 Marzo, 2019, 06:15 pm
Respuesta #7

geómetracat

  • Moderador Global
  • Mensajes: 1,332
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Yo todo eso no lo entiendo muy bien, pero te digo mi deducción natural sin miedo (más natural que la mía, que no lo he estudiado, difícil que la haya) es la siguiente

Si \( p\rightarrow(q\vee r)
  \) y a la vez ocurre \( q\rightarrow r
  \), está diciendo que implica las dos conjuntamente \( p\rightarrow(q\wedge r)
  \).

Esto es falso. Lo que implica es \( p \rightarrow r \). Pero podría ser que \( p \) y \( r \) fueran verdaderas y \( q \) falsa, en cuyo caso \( p \rightarrow (q \vee r), q \rightarrow r \) son verdaderas pero \( p \rightarrow (q \wedge r) \) es falsa.

De todas maneras, no sé si ha quedado claro, pero "deducción natural" no es una forma de hablar, es un concepto técnico que denota un tipo de cálculo deductivo concreto en lógica formal. No creo que Sdc dude de la veracidad de la inferencia de su ejemplo o pregunte por maneras de justificarla en general, sino que pregunta por su demostración usando este cálculo deductivo concreto, la deducción natural.
La ecuación más bonita de las matemáticas: \( d^2=0 \)

27 Marzo, 2019, 06:46 pm
Respuesta #8

feriva

  • Matemático
  • Mensajes: 8,933
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
  • ¡EUKERA!... ¡UEREKA!... ¡EUREKA! (corregido)
Yo todo eso no lo entiendo muy bien, pero te digo mi deducción natural sin miedo (más natural que la mía, que no lo he estudiado, difícil que la haya) es la siguiente

Si \( p\rightarrow(q\vee r)
  \) y a la vez ocurre \( q\rightarrow r
  \), está diciendo que implica las dos conjuntamente \( p\rightarrow(q\wedge r)
  \).

Esto es falso. Lo que implica es \( p \rightarrow r \). Pero podría ser que \( p \) y \( r \) fueran verdaderas y \( q \) falsa, en cuyo caso \( p \rightarrow (q \vee r), q \rightarrow r \) son verdaderas pero \( p \rightarrow (q \wedge r) \) es falsa.

Ah, sí, sí, perdón; tenrdía que ser \( q\leftrightarrow r
  \); en ese caso sí, ¿no?



Citar
De todas maneras, no sé si ha quedado claro, pero "deducción natural" no es una forma de hablar, es un concepto técnico que denota un tipo de cálculo deductivo concreto en lógica formal

Sí, lo suponía.

Gracias, geómetracat.

27 Marzo, 2019, 06:52 pm
Respuesta #9

geómetracat

  • Moderador Global
  • Mensajes: 1,332
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Sí, si la premisa fuera \( q \leftrightarrow r \) tu conclusión sería cierta.
La ecuación más bonita de las matemáticas: \( d^2=0 \)

27 Marzo, 2019, 07:04 pm
Respuesta #10

feriva

  • Matemático
  • Mensajes: 8,933
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
  • ¡EUKERA!... ¡UEREKA!... ¡EUREKA! (corregido)
Sí, si la premisa fuera \( q \leftrightarrow r \) tu conclusión sería cierta.

Muchas gracias.

Saludos.