Autor Tema: deduccion natural

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

24 Enero, 2008, 04:55 am
Leído 2566 veces

lonrot

  • Junior
  • Mensajes: 63
  • Karma: +0/-0
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.

\( \displaystyle\lnot(\lnot p \lor \lnot q) \vdash p \land q \)
\( \displaystyle\lnot(\lnot p \lor q) \vdash p  \)

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

24 Enero, 2008, 08:08 am
Respuesta #1

León

  • Lathi
  • Mensajes: 941
  • Karma: +0/-0
  • Sexo: Masculino
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):

\(
\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}
 \)

24 Enero, 2008, 01:25 pm
Respuesta #2

lonrot

  • Junior
  • Mensajes: 63
  • Karma: +0/-0
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

24 Enero, 2008, 04:54 pm
Respuesta #3

León

  • Lathi
  • Mensajes: 941
  • Karma: +0/-0
  • Sexo: Masculino
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) \( \lnot p\vdash (\lnot p \lor q) \) (Con la introducción de la disyunción aplicada a \( \lnot p \) y q)
2) \( (\lnot p\vdash(\lnot p \lor q))\land\lnot(\lnot p \lor q)\right)\vdash\lnot\lnot p \) (Modus Tollens)
3) \( \lnot(\lnot p \lor q)\vdash\lnot\lnot p \) (De 2 y 1, por eliminación de la conjunción)
4) \( \lnot(\lnot p \lor q) \vdash p  \) (De 3 por eliminación de la doble negación).

(Agrego: la otra es efectivamente muy parecida y puede probarse rápido usando ésta).

25 Enero, 2008, 09:34 am
Respuesta #4

Ked

  • Experto
  • Mensajes: 942
  • Karma: +0/-0
  • Sexo: Masculino
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 \( \perp \) 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 :P

Saludos

25 Enero, 2008, 11:12 pm
Respuesta #5

lonrot

  • Junior
  • Mensajes: 63
  • Karma: +0/-0
Gracias a todos por su ayuda, intente hacer el segundo y así es como me quedo

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

Es esto correcto?

26 Enero, 2008, 06:03 pm
Respuesta #6

Ked

  • Experto
  • Mensajes: 942
  • Karma: +0/-0
  • Sexo: Masculino
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