Autor Tema: Toda subfórmula occure en la secuencia de formación [demostración]

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

08 Abril, 2011, 05:48 pm
Leído 2203 veces

_fing

  • $$\Large \color{#5372a0}\pi\,\pi$$
  • Mensajes: 58
  • Karma: +0/-1
  • Sexo: Masculino
Bueno el ejercicio dice probar que \( \forall{\phi} \) subfórmula de \( \theta \), \( \phi \) ocurre en cualquier secuencia de formación para \( \theta \).
Uso inducción sobre \( \theta \).
Caso base: \( \theta \) es atómico, es decir \( pi \), entonces basta considerar \( \phi=pi \) que es subfórmula (ya que \( \phi=\theta \)) y \( pi \) ocurre en la secuencia de formación para \( \theta \) (por def. de secuencia de formación).
Caso inductivo: \( \theta= \theta_1 * \theta_2 \) , si \( \phi = \theta_1 \) (por def. de subfórmula) \( \theta_1 \) ocurre en la secuencia de formación (por def. de secuencia de formación). Si \( \phi= \theta \) idem.
Análogo para \( \theta=NOT \theta_1 \).

08 Abril, 2011, 07:40 pm
Respuesta #1

administrador

  • Administrador
  • Mensajes: 1,595
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Bueno el ejercicio dice probar que \( \forall{phi} \) subformula de theta, \( phi \) ocurre en cualquier secuencia de formacion para \( theta \)
Uso induccion sobre \( theta \)
Caso base: \( theta \) es atomico, es decir \( pi \), entonces basta considerar \( phi=pi \) que es subformula (ya que \( phi=theta \)) y \( pi \) ocurre en la secuencia de formacion para \( theta \) (por def. de secuencia de formacion).
Caso inductivo: \( theta=theta1 * theta2 \) , si \( phi = theta1 \) (por def. de subformula) \( theta1 \) ocurre en la secuencia de formacion (por def. de secuencia de formacion). Si \( phi=theta \) idem.
Analogo para \( theta=NOTtheta1 \).


Por favor, edita tu mensaje y corrige:

a) los acentos. (Te apartas de las reglas)
b) las griegas:  \alpha en vez de alpha, etcétera
c) los subíndices.
d) alguna otra cosa que encuentres. (Por ejemplo en el título hay cuatro errores)

Saludos.

09 Abril, 2011, 12:16 am
Respuesta #2

_fing

  • $$\Large \color{#5372a0}\pi\,\pi$$
  • Mensajes: 58
  • Karma: +0/-1
  • Sexo: Masculino
solucionado, mil disculpas.
Espero cualquier correción a la demostración.
Saludos

09 Abril, 2011, 12:48 am
Respuesta #3

Óscar Matzerath

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 567
  • Karma: +0/-0
  • Sexo: Masculino
Hola,

La idea no está mal, pero te estás dejando cosas.
En primer lugar no estaría mal que dieras la definicion de "secuencia de formación" que estás usando, pero en cualquier caso con cualquier definición razonable todo lo siguiente se debería aplicar en tu caso.

En el caso inductivo, debes considerar cualquier subfórmula de \( \theta_1 * \theta_2 \), mientras que tú sólo estás considerando dos subfórmulas: \( \theta_1 \) y \( \theta_2 \). Bien hecho sería algo así:

Suponemos que el resultado es cierto para \( \theta_1 \) y \( \theta_2 \), esta es la hipótesis de inducción.

Sea \( \phi \) una subfórmula de \( \theta_1 * \theta_2 \). Por definición de subfórmula, o bien \( \phi \) es una subfórmula de \( \theta_1 \), o bien \( \phi \) es una subfórmula de \( \theta_2 \) o bien \( \phi = \theta_1*\theta_2 \). En el primer caso, por hipótesis de inducción \( \phi \) ocurre en la secuencia de formación de \( \theta_1 \), y la secuencia de formación de \( \theta_1 \) es una subsecuencia de la secuencia de formación de \( \theta_1*\theta_2 \), por tanto \( \phi \) ocurre en la secuencia de formación de \( \theta_1*\theta_2 \). El segundo caso es exactamente igual que el primero.
Y el caso \( \phi= \theta_1*\theta_2 \) es trivial ya que \( \theta_1*\theta_2 \) ocurre en la secuencia de formación de \( \theta_1*\theta_2 \).

Para el caso de la negación, lo mismo que en este pero más sencillo.

Saludos

09 Abril, 2011, 01:02 am
Respuesta #4

_fing

  • $$\Large \color{#5372a0}\pi\,\pi$$
  • Mensajes: 58
  • Karma: +0/-1
  • Sexo: Masculino
^Perfectamente demostrado Oscar, tenes razón lo mio fue muy por arriba, muchas gracias.

09 Abril, 2011, 01:46 am
Respuesta #5

administrador

  • Administrador
  • Mensajes: 1,595
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Bueno el ejercicio dice probar que \( \forall{\phi} \) subfórmula de \( \theta \), \( \phi \) ocurre en cualquier secuencia de formación para \( \theta \).
Uso inducción sobre \( \theta \).
Caso base: \( \theta \) es atómico, es decir \( pi \), entonces basta considerar \( \phi=pi \) que es subfórmula (ya que \( \phi=\theta \)) y \( pi \) ocurre en la secuencia de formación para \( \theta \) (por def. de secuencia de formación).
Caso inductivo: \( \theta= \theta_1 * \theta_2 \) , si \( \phi = \theta_1 \) (por def. de subfórmula) \( \theta_1 \) ocurre en la secuencia de formación (por def. de secuencia de formación). Si \( \phi= \theta \) idem.
Análogo para \( \theta=NOT \theta_1 \).





Por favor, edita tu mensaje y corrige:

a) los acentos. (Te apartas de las reglas)
b) las griegas:  \alpha en vez de alpha, etcétera
c) los subíndices.
d) alguna otra cosa que encuentres. (Por ejemplo en el título hay cuatro errores)

Saludos.

Para \( \pi \) vale lo mismo que para las otras letras griegas: \pi

09 Abril, 2011, 02:43 am
Respuesta #6

_fing

  • $$\Large \color{#5372a0}\pi\,\pi$$
  • Mensajes: 58
  • Karma: +0/-1
  • Sexo: Masculino
Bueno el ejercicio dice probar que \( \forall{\phi} \) subfórmula de \( \theta \), \( \phi \) ocurre en cualquier secuencia de formación para \( \theta \).
Uso inducción sobre \( \theta \).
Caso base: \( \theta \) es atómico, es decir \( pi \), entonces basta considerar \( \phi=pi \) que es subfórmula (ya que \( \phi=\theta \)) y \( pi \) ocurre en la secuencia de formación para \( \theta \) (por def. de secuencia de formación).
Caso inductivo: \( \theta= \theta_1 * \theta_2 \) , si \( \phi = \theta_1 \) (por def. de subfórmula) \( \theta_1 \) ocurre en la secuencia de formación (por def. de secuencia de formación). Si \( \phi= \theta \) idem.
Análogo para \( \theta=NOT \theta_1 \).





Por favor, edita tu mensaje y corrige:

a) los acentos. (Te apartas de las reglas)
b) las griegas:  \alpha en vez de alpha, etcétera
c) los subíndices.
d) alguna otra cosa que encuentres. (Por ejemplo en el título hay cuatro errores)

Saludos.

Para \( \pi \) vale lo mismo que para las otras letras griegas: \pi

Ya corregí el título.
\( pi \) no es \( \pi \) , sino que es una proposición para cierto \( i\in{N}  \)