18/01/2020, 17:48:58 pm *
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 aladan
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: deduccion natural  (Leído 2451 veces)
0 Usuarios y 1 Visitante están viendo este tema.
lonrot
Semi pleno
***

Karma: +0/-0
Desconectado Desconectado

Mensajes: 63


Ver Perfil
« : 24/01/2008, 00:55:42 am »

Hola:

Tengo que resolver este problema pero no se como hacerlo, de hecho la manera que lo hice estoy casi seguro que esta mal no me agrada para nada a ver si me puede orientar un poco.

[texx]\displaystyle\lnot(\lnot p \lor \lnot q) \vdash p \land q[/texx]
[texx]\displaystyle\lnot(\lnot p \lor q) \vdash p [/texx]

como verán los dos son muy parecidos, todo sería muy fácil si pudiera usar De Morgan's pero no puedo, he ahí el detalle.

Gracias
En línea
León
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Mensajes: 941


Ver Perfil
« Respuesta #1 : 24/01/2008, 04:08:53 am »

Hola. No me queda claro si tenés una lista de axiomas/definiciones que sí se pueden usar.

Una manera de que esas expresiones son tautológicas es armar las tablas de verdad y verificar que la tabla final queda verdadera para todas la combinaciones de verdad/falsedad de p y q.

Por ejemplo, para la segunda expresión, que es mas corta, podrías demostrarlo así (quizás quieras agregar mas expresiones intermedias para que quede mas explícito):

[texx]
\begin{tabular}{| c || c | c | c | c | c |}
\hline
p&F&F&V&V\\
\hline
q&F&V&F&V\\
\hline
\hline
\lnot p \lor q&V&V&F&V\\
\hline
\lnot(\lnot p \lor q) \vdash p&V&V&V&V\\
\hline
\end{tabular}
[/texx]
En línea
lonrot
Semi pleno
***

Karma: +0/-0
Desconectado Desconectado

Mensajes: 63


Ver Perfil
« Respuesta #2 : 24/01/2008, 09:25:32 am »

Disculpa se me olvido mencionar que debo de deducirlas por deducción natural no por tablas de verdad, las reglas que tengo son:

 Introducción de la conjunción
 Eliminación de la conjunción
 Introducción de la implicación
 Eliminación de la implicación
 Introducción de la disyunción
 Eliminación de la disyunción
 Introducción de la negación
 Eliminación de la negación
 Reducción al absurdo
 Exclusión de un tercero
 Modus Tollens
 eliminación de la doble negación
 prueba por contradicción
En línea
León
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Mensajes: 941


Ver Perfil
« Respuesta #3 : 24/01/2008, 12:54:00 pm »

Quizás lo mejor sea que muestres lo que hiciste y te ayudamos si hay errores.

Interpretando a mi manera tus axiomas por su nombre, la segunda proposición puede demostrarse así (insisto en que no estoy seguro de cuales son exactamente, o mas bien cómo están escritos, tus axiomas).

1) [texx]\lnot p\vdash (\lnot p \lor q)[/texx] (Con la introducción de la disyunción aplicada a [texx]\lnot p[/texx] y q)
2) [texx](\lnot p\vdash(\lnot p \lor q))\land\lnot(\lnot p \lor q)\right)\vdash\lnot\lnot p[/texx] (Modus Tollens)
3) [texx]\lnot(\lnot p \lor q)\vdash\lnot\lnot p[/texx] (De 2 y 1, por eliminación de la conjunción)
4) [texx]\lnot(\lnot p \lor q) \vdash p [/texx] (De 3 por eliminación de la doble negación).

(Agrego: la otra es efectivamente muy parecida y puede probarse rápido usando ésta).
En línea
Ked
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 942


Ver Perfil
« Respuesta #4 : 25/01/2008, 05:34:41 am »

Hola, hace bastante que no hago esto (derivaciones) así que espero que no haya ningún error.

Acá un PDF con las reglas que usabamos en mi curso de lógica: http://www.fing.edu.uy/inco/cursos/logica/teorico/703Prop6.pdf

Ahora te escribo la derivación de la segunda (con abs indico [texx]\perp[/texx] o sea el absurdo):


                ¬p
            ---------- Introducción v
¬(¬p v q)     ¬p v q
--------------------- Eliminación ¬
   Abs
   -------------- RAA (introduce ¬p como hipótesis)
          p

La hipótesis ¬p se cancela al aplicar RAA por lo tanto la única hipótesis que usamos es ¬(¬p v q).

Si todavía te da problemas la primera (es más complicada que la segunda) postea y la intento hacer :lengua_afuera:

Saludos
En línea
lonrot
Semi pleno
***

Karma: +0/-0
Desconectado Desconectado

Mensajes: 63


Ver Perfil
« Respuesta #5 : 25/01/2008, 19:12:46 pm »

Gracias a todos por su ayuda, intente hacer el segundo y así es como me quedo

1 [texx]\lnot (\lnot p \lor \lnot q)[/texx]            Hipotesis
2 [texx]\lnot p[/texx]                       premisa
3 [texx]\lnot p \lor \lnot q[/texx]                Intro [texx]\lor[/texx]
4 [texx]\perp[/texx]                        Eliminacion [texx]\lnot[/texx]  1,3
5 [texx]p[/texx]                        RAA 2-4
6 [texx]\lnot q[/texx]                       premisa           
7 [texx]\lnot p \lor \lnot q[/texx]                 Intro [texx]\lor[/texx]
8 [texx]\perp[/texx]                         Eliminacion [texx]\lnot[/texx]  1,7
9 [texx]q[/texx]                         RAA 6-8
[texx]p \land q[/texx]                                Intro [texx]\land[/texx] 5,9

Es esto correcto?
En línea
Ked
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 942


Ver Perfil
« Respuesta #6 : 26/01/2008, 14:03:42 pm »

Es correcto, pero sería mucho más claro si lo escribes en forma de árbol:

                 ¬p            ¬q
             ---------- Iv  --------- Iv
¬(¬p v ¬q)     ¬p v ¬q       ¬p v ¬q       ¬(¬p v ¬q)
----------------------- E¬   ------------------------- E¬
          Abs                         Abs
   --------------- RAA        ------------------ RAA
          p                            q
        ---------------------------------- I ^
                         p ^ q


Así se ve claramente cómo es la mecánica de la prueba: se demuestran por separado las dos ramas de forma análoga.


Saludos
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!