Parcial Mayo 2010 Ej 4

Parcial Mayo 2010 Ej 4

de Andres Fulloni Papaleo -
Número de respuestas: 1

Buenas estoy trancado en este ejercicio, más que nada en la parte a. La verdad no se me ocurre como encararlo y como usar la definición de DER0. Si alguien me puede guiar un poco le agradezco.

En respuesta a Andres Fulloni Papaleo

Re: Parcial Mayo 2010 Ej 4

de Romina Romero - InCo -

Te piden demostar que:

 \scriptstyle{(\bar{\forall} \varphi \in \mathcal{L}_0)(\bar{\forall} \Gamma \subseteq \mathcal{L}_0)(\Gamma \vdash \varphi \Leftrightarrow \Gamma \neq \oslash )}

Conviene demostrar el directo y el recíproco por separado:

Sean  \scriptstyle{\varphi \in \mathcal{L}_0} y  \scriptstyle{\Gamma \subseteq \mathcal{L}_0} cualesquiera.

Lema 1: Probar  \scriptstyle{\Gamma \vdash \varphi \Rightarrow 
\Gamma \neq \oslash} .

Lema 2: Probar  \scriptstyle{\Gamma \neq \oslash \Rightarrow \Gamma \vdash \varphi} .


Para el lema 1 te puede ser de utilidad demostrar la corrección del sistema (y para la parte b decís que eso ya se probó, y demostrás solo la completitud). El lema 2 me parece que es más fácil (sale más directo).

Recordá las cosas que se vieron en el ejercicio 1, te van a servir.


¡Saludos!