Autor Tema: Secuencias de formación y subfórmulas

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

06 Abril, 2012, 07:04 pm
Leído 4499 veces

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,447
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Para entender mejor este post, conviene leer la introducción que se hace aquí.

Definición 2
A sequence \( \varphi_0,\varphi_1,\dots,\varphi_n \) is called a formation sequence of \( \varphi \) if \( \varphi_n=\varphi \) and for all \( i\leq n \):
1-\( \varphi_i \) is atomic, or
2-\( \varphi=(\varphi_j\square\varphi_k) \) for certain \( j,k<i \) or
3-\( \varphi=(\lnot \varphi_j) \) for certain \( j<i \).

Un ejemplo podría ser el siguiente. Supongamos que \( \varphi=((\bot \vee p_{32})\wedge (\lnot p_2)) \). Entonces una secuencia de formación para \( \varphi \) es: \( \bot,\ p_{32},\ (\bot \vee p_{32}),\ p_2,\ (\lnot p_2), ((\bot \vee p_{32})\wedge (\lnot p_2)) \). Una observación que se hace en el libro es que las secuencias de formación pueden tener "garbage". Por ejemplo, \( \bot,\ p_{32},\ (\bot \vee p_{32}),\ p_2,\ (\lnot p_2),\ {\red p_9},\ ((\bot \vee p_{32})\wedge (\lnot p_2)) \). El hecho de que se agregue \( p_9 \) no hace que lo anterior deje de ser una secuencia de formación para \( \varphi \).

Definición 3
\( \varphi \) is subformula of \( \psi \) if:
1-\( \varphi=\psi \), or
2-\( \psi=(\psi_1\square \psi_2) \) and \( \varphi \) is a subformula of \( \psi_1 \) or of \( \psi_2 \), or
3-\( \psi=(\lnot \psi_1) \) and \( \varphi \) is a subformula of \( \psi_1 \).

Dadas estas definiciones, en el práctico aparecen estos dos ejercicios:

A) Sea la siguiente propiedad:

Para toda \( \varphi \) subfórmula de \( \psi \), \( \varphi \) ocurre en cualquier secuencia de formación para \( \psi \).

Dé una prueba inductiva de la misma.

Prueba
No sabía si la inducción era en \( \varphi \) o \( \psi \) o en qué. Al final se me ocurrió lo siguiente, espero que esté bien.

Sea \( \psi_0,\psi_1,\dots, \psi_n \) una secuencia de formación para \( \psi \), y \( \varphi \) una subfórmula de \( \psi \). Hay que probar que \( \varphi=\psi_i \) para algún \( i \). Entonces lo hago por inducción sobre \( n \).

Si \( n=0 \): \( \psi=\psi_0 \) y por definición de secuencia de formación, \( \psi \) es atómica. Como \( \varphi \) es subfórmula de \( \psi \) no hay otra posibilidad que \( \varphi=\psi=\psi_0 \).

Supongamos ahora que la propiedad es cierta para todo \( k<n \) y probemos que también se cumple cuando \( k=n \). Tenemos que \( \psi_0,\psi_1,\dots, \psi_n \) es una secuencia de formación para \( \psi \), y que \( \varphi \) es una subfórmula de \( \psi \). Por definición de subfórmula, estamos ante uno de los siguientes casos:

-\( \varphi=\psi \). Es inmediato, puesto que por definición de secuencia de formación \( \psi_n=\psi=\varphi \).

-\( \psi=\psi_n=(\psi_i\square\psi_j) \), para \( i,j<n \) donde \( \varphi \) es subfórmula de \( \psi_i \) o de \( \psi_j \). Supongamos, sin pérdida de generalidad, que \( \varphi \) es subfórmula de \( \psi_i \). Observar que \( \psi_0,\psi_1,\dots, \psi_i \) es una secuencia de formación para \( \psi_i \) de largo menor a \( n \) y por hipótesis de inducción, existe algún \( \psi_k \) con \( k\leq i \) tal que \( \psi_k=\varphi \).

-\( \psi=\psi_n=(\lnot\psi_i) \), para \( i<n \) donde \( \varphi \) es subfórmula de \( \psi_i \). Análogo al caso anterior.
[cerrar]

¿Está bien?

B)
i) Considere una secuencia de formación \( \varphi_1,\dots, \varphi_n\equiv \psi \) de la fórmula \( \psi \). Sea \( \varphi_i \) la fórmula de la secuencia que no es subfórmula de \( \psi \), y que aparece más a la derecha en la secuencia. Pruebe que si se elimina \( \psi_i \) de la secuencia de formación dada, la secuencia resultante sigue siendo una secuencia de formación para \( \psi \).
ii) A partir del resultado anterior, demueste que si \( \varphi \) ocurre en una secuencia de formación de largo mínimo para \( \psi \), entonces \( \varphi \) es una subfórmula de \( \psi \).

¿Alguna idea?

Saludos
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

07 Abril, 2012, 08:08 pm
Respuesta #1

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,447
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
También referido a estos conceptos, tengo el siguiente ejercicio:

C)
i) Defina la función \( \text{sub}:\text{PROP}\rightarrow 2^{\text{PROP}} \), que a cada fórmula proposicional \( \varphi \) le asigna el conjunto \( \mbox{sub}(\varphi) \) de sus subfórmulas.

ii) Demuestre que la relación "ser subfórmula de" es transitiva.

Hice el apartado i). Por recursión primitiva:

\( \left\{\begin{array}{lll}\mbox{sub}(\varphi) &=& \mbox{$\{\varphi\}$ si $\varphi=\bot$ o $\varphi=p_i$}\\ \mbox{sub}((\varphi\square\psi)) &=& \{(\varphi\square\psi)\}\cup\mbox{sub}(\varphi)\cup\mbox{sub}(\psi) \\ \mbox{sub}((\lnot\varphi))} &=& \{(\lnot\varphi)\}\cup \mbox{sub}(\varphi) \end{array}\right. \)

Ahora en el apartado ii) es intuitivamente claro que si \( \alpha \) es subfórmula de \( \beta \) y \( \beta \) es subfórmula de \( \gamma \), entonces \( \alpha \) es subfórmula de \( \gamma \). Incluso más, me animaría a decir que el subconjunto \( R\subset\text{PROP}\times \text{PROP} \) tal que \( (\alpha,\beta)\in R \) sii \( \alpha \) es subfórmula de \( \beta \), es una relación de orden. Pero al momento de probar la transitividad se me complica, porque si analizo caso por caso, se me multiplican las posibilidades y se vuelve todo muy farragoso.

¿Cómo puedo probarlo?

Gracias
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

07 Abril, 2012, 10:23 pm
Respuesta #2

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
¿Está bien?

Yo te diría que sí, pero:

Hay un problema. Y es que en el curso en que estoy, no se nos permite hacer demostraciones por inducción fuerte. Sí nos dejaban hacer eso en un curso anterior que tuve de matemática discreta. De hecho, es lo mismo que uso acá, ¿no? Pues resulta que ahora en Lógica no nos dejan usar eso. Supuestamente es porque definen el lenguaje de la lógica proposicional de manera inductiva (le llaman PROP a ese lenguaje) y enuncian un principio de inducción primitiva para PROP y prueban propiedades a partir de ese principio. Siguen el enfoque del libro que cité antes. Por eso es que sólo les interesa la inducción primitiva.

 ???

B)
i) Considere una secuencia de formación \( \varphi_1,\dots, \varphi_n\equiv \psi \) de la fórmula \( \psi \). Sea \( \varphi_i \) la fórmula de la secuencia que no es subfórmula de \( \psi \), y que aparece más a la derecha en la secuencia. Pruebe que si se elimina \( \psi_i \) de la secuencia de formación dada, la secuencia resultante sigue siendo una secuencia de formación para \( \psi \).
ii) A partir del resultado anterior, demueste que si \( \varphi \) ocurre en una secuencia de formación de largo mínimo para \( \psi \), entonces \( \varphi \) es una subfórmula de \( \psi \).

¿Alguna idea?

Comprueba que cumple la definición de sucesión de formación.

Toma una fórmula de la sucesión con la fórmula eliminada. Sigue acabando en \( \psi \), porque no puedes haber eliminado \( \psi \).

Toma una de sus fórmulas. Si es atómica, no hay nada que probar.

Si es \( \phi_i\square \phi_j \), sólo hay que ver que ninguna de las dos subfórmulas es la eliminada. Si lo fuera, la fórmula eliminada estaría más a la izquierda de ésta, luego ésta sería una subfórmula de \( \psi \), luego la subfórmula eliminada sería una subfórmula de una subfórmula de \( \psi \), luego sería una subfórmula de \( \psi \), contradicción.

El caso de la negación es parecido.

ii) se sigue inmediatamente de i), pues si una sucesión de formación contiene una fórmula que no es subfórmula de la última, se puede eliminar, luego su longitud no es mínima.

Me acabo de dar cuenta de que en la prueba anterior he usado que ser una subfórmula es transitivo, que es lo que planteas en el post siguiente. Espero que no haya ningún inconveniente en demostrar esto primero para a su vez probar lo otro.

También referido a estos conceptos, tengo el siguiente ejercicio:

C)
i) Defina la función \( sub:\text{PROP}\rightarrow 2^{\text{PROP}} \), que a cada fórmula proposicional \( \varphi \) le asigna el conjunto \( \mbox{sub}(\varphi) \) de sus subfórmulas.

ii) Demuestre que la relación "ser subfórmula de" es transitiva.

Hice el apartado i). Por recursión primitiva:

\( \left\{\begin{array}{lll}\mbox{sub}(\varphi) &=& \mbox{$\{\varphi\}$ si $\varphi=\bot$ o $\varphi=p_i$}\\ \mbox{sub}((\varphi\square\psi)) &=& \{(\varphi\square\psi)\}\cup\mbox{sub}(\varphi)\cup\mbox{sub}(\psi) \\ \mbox{sub}((\lnot\varphi))} &=& \{(\lnot\varphi)\}\cup \mbox{sub}(\varphi) \end{array}\right. \)

La verdad es que no entiendo por qué hay que demostrar nada. El enunciado ya es de por sí una definición válida.

Ahora en el apartado ii) es intuitivamente claro que si \( \alpha \) es subfórmula de \( \beta \) y \( \beta \) es subfórmula de \( \gamma \), entonces \( \alpha \) es subfórmula de \( \gamma \). Incluso más, me animaría a decir que el subconjunto \( R\subset\text{PROP}\times \text{PROP} \) tal que \( (\alpha,\beta)\in R \) sii \( \alpha \) es subfórmula de \( \beta \), es una relación de orden. Pero al momento de probar la transitividad se me complica, porque si analizo caso por caso, se me multiplican las posibilidades y se vuelve todo muy farragoso.

¿Cómo puedo probarlo?

Toma como propiedad \( A(\phi) \) la dada por

Para toda subfórmula \( \psi \) de \( \phi \) se cumple que las subfórmulas de \( \psi \) son subfórmulas de \( \phi \).

Intenta aplicar el principio de inducción para PROP. No creo que surja ningún inconveniente, pero si te encuentras algún problema en el que no caigo, dilo.



08 Abril, 2012, 01:06 am
Respuesta #3

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,447
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Uff, muchas gracias Carlos.

Yo te diría que sí, pero:

Hay un problema. Y es que en el curso en que estoy, no se nos permite hacer demostraciones por inducción fuerte. Sí nos dejaban hacer eso en un curso anterior que tuve de matemática discreta. De hecho, es lo mismo que uso acá, ¿no? Pues resulta que ahora en Lógica no nos dejan usar eso. Supuestamente es porque definen el lenguaje de la lógica proposicional de manera inductiva (le llaman PROP a ese lenguaje) y enuncian un principio de inducción primitiva para PROP y prueban propiedades a partir de ese principio. Siguen el enfoque del libro que cité antes. Por eso es que sólo les interesa la inducción primitiva.

 ???

Tienes toda la razón; en ese entonces estaba yo confundido con lo que se podía y lo que no se podía usar. Pero más adelante, me di cuenta que sobre los naturales sí se puede usar inducción fuerte, porque en el libro no recuerdo en qué momento se usó esa técnica. Así que disculpas por aquel post. Tu demostración era completamente válida.

Comprueba que cumple la definición de sucesión de formación.

Toma una fórmula de la sucesión con la fórmula eliminada. Sigue acabando en \( \psi \), porque no puedes haber eliminado \( \psi \).

Toma una de sus fórmulas. Si es atómica, no hay nada que probar.

Si es \( \phi_i\square \phi_j \), sólo hay que ver que ninguna de las dos subfórmulas es la eliminada. Si lo fuera, la fórmula eliminada estaría más a la izquierda de ésta, luego ésta sería una subfórmula de \( \psi \), luego la subfórmula eliminada sería una subfórmula de una subfórmula de \( \psi \), luego sería una subfórmula de \( \psi \), contradicción.

El caso de la negación es parecido.

ii) se sigue inmediatamente de i), pues si una sucesión de formación contiene una fórmula que no es subfórmula de la última, se puede eliminar, luego su longitud no es mínima.

Esto está clarísimo. Ahora que veo la solución, no sé cómo no se me ocurrió a mi. Cuando lo intentaba yo, se me multiplicaban los casos y llegaba a un árbol que crecía en ramas, y me perdía. Ya ni sabía lo que estaba haciendo. Creí que se podría aplicar inducción, porque sospeché que ese crecimiento exponencial de los casos se podría "matar" con un argumento inductivo. Pero tampoco supe cómo. Lo más difícil es hacer que las cosas parezcan fáciles, que es lo que has hecho tú.

Me acabo de dar cuenta de que en la prueba anterior he usado que ser una subfórmula es transitivo, que es lo que planteas en el post siguiente. Espero que no haya ningún inconveniente en demostrar esto primero para a su vez probar lo otro.

No, no hay problema. Incluso más. El ejercicio en que se prueba la transitividad antecede a los ejercicios de mi primer post. No respeté el orden al momento de plantearlos.

La verdad es que no entiendo por qué hay que demostrar nada. El enunciado ya es de por sí una definición válida.

Esto es lo único que me quedó colgado. No sé a lo que te estás refiriendo. La definición de esa función \( \text{sub} \) no es parte del enunciado; es mi resolución del apartado i).

Toma como propiedad \( A(\phi) \) la dada por

Para toda subfórmula \( \psi \) de \( \phi \) se cumple que las subfórmulas de \( \psi \) son subfórmulas de \( \phi \).

Intenta aplicar el principio de inducción para PROP. No creo que surja ningún inconveniente, pero si te encuentras algún problema en el que no caigo, dilo.

Claro. Si entendí bien, la idea es probar primero que dada una fórmula proposicional \( \varphi\in \text{PROP} \) se cumple que para toda \( \alpha \) subfórmula de \( \varphi \) se tiene que \( \text{sub}(\alpha)\subseteq \text{sub}(\varphi) \).

Lo que había que probar inicialmente era que si \( \alpha \) es subfórmula de \( \beta \), y \( \beta \) es subfórmula de \( \gamma \), entonces \( \alpha \) es subfórmula de \( \gamma \).

Teniendo probada la propiedad que mencionas, la transitividad de la relación "ser subfórmula de" se desprende de la transitividad de la inclusión de conjuntos. Por hipótesis, \( \alpha \) es subfórmula de \( \beta \) por lo tanto \( \text{sub}(\alpha)\subseteq \text{sub}(\beta) \). De la misma manera, como \( \beta \) es subfórmula de \( \gamma \), \( \text{sub}(\beta)\subseteq \text{sub}(\gamma) \). Como \( \text{sub}(\alpha)\subseteq \text{sub}(\beta)\wedge \text{sub}(\beta)\subseteq \text{sub}(\gamma)\Longrightarrow \text{sub}(\alpha)\subseteq \text{sub}(\gamma) \). Pero \( \alpha\in \text{sub}(\alpha) \) (toda fórmula es subfórmula de sí misma) luego \( \alpha\in \text{sub}(\gamma) \) como se quería probar.

Otra demostración que se me ocurre ahora es la siguiente:

Demostración alternativa
\( \alpha \) es subfórmula de \( \beta \); entonces por el primer ejercicio de todos (el que probé usando inducción fuerte), \( \alpha \) ocurre en cualquier secuencia de formación para \( \beta \). En particular, para una de largo mínimo. Sea \( \beta_0,\dots,\beta_{i-1},\alpha,\beta_{i+1},\dots, \beta \) dicha secuencia.

Análogamente, \( \beta \) es subfórmula de \( \gamma \); entonces \( \beta \) ocurre en cualquier secuencia de formación para \( \gamma \). En particular para una de largo mínimo. Sea \( \gamma_0,\dots,\gamma_{j-1},\beta,\gamma_{j+1},\dots, \gamma \) dicha secuencia.

Entonces debiera poderse probar que \( \beta_0,\dots,\beta_{i-1},\alpha,\beta_{i+1},\dots, \beta,\gamma_{j+1},\dots, \gamma \) es una secuencia de formación para \( \gamma \) de largo mínimo en la que ocurre \( \alpha \). Por el ejercicio B) apartado ii) \( \alpha \) es subfórmula de \( \gamma \).
[cerrar]

¿Está bien?

Saludos
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

08 Abril, 2012, 01:42 am
Respuesta #4

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
La verdad es que no entiendo por qué hay que demostrar nada. El enunciado ya es de por sí una definición válida.

Esto es lo único que me quedó colgado. No sé a lo que te estás refiriendo. La definición de esa función \( \text{sub} \) no es parte del enunciado; es mi resolución del apartado i).

Si esto vale como definición:

Definición 3
\( \varphi \) is subformula of \( \psi \) if:
1-\( \varphi=\psi \), or
2-\( \psi=(\psi_1\square \psi_2) \) and \( \varphi \) is a subformula of \( \psi_1 \) or of \( \psi_2 \), or
3-\( \psi=(\lnot \psi_1) \) and \( \varphi \) is a subformula of \( \psi_1 \).

Entonces esto también vale:

\( \text{sub}(\phi) = \{\psi\in \text{PROP}\mid \psi \text{ es subf\'ormula de }\phi\} \),

puesto que "ser subfórmula de" ya está definido previamente. Otra cosa es que este ejercicio se entienda como justificación de que la definición precedente es correcta, pero si es así, tendría que ser previo a cualquier teorema sobre subfórmulas.

Claro. Si entendí bien, la idea es probar primero que dada una fórmula proposicional \( \varphi\in \text{PROP} \) se cumple que para toda \( \alpha \) subfórmula de \( \varphi \) se tiene que \( \text{sub}(\alpha)\subseteq \text{sub}(\varphi) \).

Sí, así queda expresado de forma más elegante que como lo había expresado yo, y lo que sigue queda más claro aún.

Otra demostración que se me ocurre ahora es la siguiente:

Demostración alternativa
\( \alpha \) es subfórmula de \( \beta \); entonces por el primer ejercicio de todos (el que probé usando inducción fuerte), \( \alpha \) ocurre en cualquier secuencia de formación para \( \beta \). En particular, para una de largo mínimo. Sea \( \beta_0,\dots,\beta_{i-1},\alpha,\beta_{i+1},\dots, \beta \) dicha secuencia.

Análogamente, \( \beta \) es subfórmula de \( \gamma \); entonces \( \beta \) ocurre en cualquier secuencia de formación para \( \gamma \). En particular para una de largo mínimo. Sea \( \gamma_0,\dots,\gamma_{j-1},\beta,\gamma_{j+1},\dots, \gamma \) dicha secuencia.

Entonces debiera poderse probar que \( \beta_0,\dots,\beta_{i-1},\alpha,\beta_{i+1},\dots, \beta,\gamma_{j+1},\dots, \gamma \) es una secuencia de formación para \( \gamma \) de largo mínimo en la que ocurre \( \alpha \). Por el ejercicio B) apartado ii) \( \alpha \) es subfórmula de \( \gamma \).
[cerrar]

¿Está bien?

No veo por qué la concatenación de las dos sucesiones de formación tiene que ser una sucesión de formación de longitud mínima. Por el contrario, si las fórmulas \( \beta \) y \( \gamma \) tienen subfórmulas en común, sus sucesiones de definición tendrán fórmulas en común, por lo que al concatenarlas habrá fórmulas repetidas que se podrán eliminar, luego la concatenación no será de longitud mínima.

Por otra parte, en la demostración que yo te he dado del ejercicio B), he usado la transitividad de las subfórmulas, si pretendes usar ese ejercicio para probar la transitividad, necesitarás dar una prueba de B) que no dependa de ella, si no, el argumento sería circular.

08 Abril, 2012, 02:47 am
Respuesta #5

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,447
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Si esto vale como definición:

Definición 3
\( \varphi \) is subformula of \( \psi \) if:
1-\( \varphi=\psi \), or
2-\( \psi=(\psi_1\square \psi_2) \) and \( \varphi \) is a subformula of \( \psi_1 \) or of \( \psi_2 \), or
3-\( \psi=(\lnot \psi_1) \) and \( \varphi \) is a subformula of \( \psi_1 \).

Entonces esto también vale:

\( \text{sub}(\phi) = \{\psi\in \text{PROP}\mid \psi \text{ es subf\'ormula de }\phi\} \),

puesto que "ser subfórmula de" ya está definido previamente. Otra cosa es que este ejercicio se entienda como justificación de que la definición precedente es correcta, pero si es así, tendría que ser previo a cualquier teorema sobre subfórmulas.

Tienes razón. Tu definición de la función \( \text{sub} \) es igualmente válida.

No veo por qué la concatenación de las dos sucesiones de formación tiene que ser una sucesión de formación de longitud mínima.

No estoy seguro de si es cierto o no. Pero hago dos observaciones:

1-No son dos secuencias de formación cualesquiera. Tienen largo mínimo, una para \( \beta \) y otra para \( \gamma \).

2-No las concatené una seguida de la otra, sino que concatené un pedazo de una a continuación de la otra. Si te fijas en los subíndices, es la primer secuencia de formación, o sea, la de \( \beta \), a la que le anexé el trozo \( \gamma_{j+1},\gamma_{j+2},\dots,\gamma \). Es más, mi intuición me dice que toda la primer secuencia \( \beta_0,\dots,\beta_{i-1},\alpha,\beta_{i+1},\dots, \beta \) es la misma que \( \gamma_0,\dots,\gamma_{j-1},\beta \) a no ser, quizás, por el orden de alguna de las fórmulas. Me baso en la creencia de que si dos secuencias de formación tienen largo mínimo, entonces han de ser la misma (a no ser, quizás, como dije antes, por reordenación de alguna fórmula).

Entonces debiera poderse probar que \( \beta_0,\dots,\beta_{i-1},\alpha,\beta_{i+1},\dots, \beta,\gamma_{j+1},\dots, \gamma \) es una secuencia de formación para \( \gamma \) de largo mínimo en la que ocurre \( \alpha \). Por el ejercicio B) apartado ii) \( \alpha \) es subfórmula de \( \gamma \).

Ese "debiera poderse" en la demostración debiera cambiarse por "aquí está la prueba". Pero no sé como hacerla. En realidad (en caso de ser secuencia de formación), que es de largo mínimo es bastante inmediato. Porque si suponemos que no es de largo mínimo, hay una fórmula que se puede eliminar. Si eliminas una antes de la ocurrencia de \( \beta \), tienes que la primer secuencia (o sea la de \( \beta \), no sería de largo mínimo, lo cual es una contradicción). De la misma manera, si puedes eliminar una fórmula de la tira \( \gamma_{j+1},\gamma_{j+2},\dots,\gamma \) también la podrías eliminar de \( \gamma_0,\dots,\gamma_{j-1},\beta,\gamma_{j+1},\dots, \gamma \), ¿o no? Y ésa se supone que es de largo mínimo, por lo que también se llegaría a una contradicción.

Por el contrario, si las fórmulas \( \beta \) y \( \gamma \) tienen subfórmulas en común, sus sucesiones de definición tendrán fórmulas en común, por lo que al concatenarlas habrá fórmulas repetidas que se podrán eliminar, luego la concatenación no será de longitud mínima.

Claro, pero ese problema no ocurre (creo) porque lo que se concatenan no son las secuencias enteras, sino que a una se le añade un pedazo de otra.

Por otra parte, en la demostración que yo te he dado del ejercicio B), he usado la transitividad de las subfórmulas, si pretendes usar ese ejercicio para probar la transitividad, necesitarás dar una prueba de B) que no dependa de ella, si no, el argumento sería circular.

Esto sí es incuestionable. Tienes toda la razón, tendría que buscar otra prueba para el ejercicio B) i). Pero en el hipotético caso que encuentre otra demostración, me gustaría saber si hay fallo en la mía y cómo se puede completar.

Muchísimas gracias por todo lo que me estás ayudando en estos temas, Carlos.

Saludos
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

08 Abril, 2012, 01:03 pm
Respuesta #6

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
No veo por qué la concatenación de las dos sucesiones de formación tiene que ser una sucesión de formación de longitud mínima.

No estoy seguro de si es cierto o no. Pero hago dos observaciones:

1-No son dos secuencias de formación cualesquiera. Tienen largo mínimo, una para \( \beta \) y otra para \( \gamma \).

2-No las concatené una seguida de la otra, sino que concatené un pedazo de una a continuación de la otra. Si te fijas en los subíndices, es la primer secuencia de formación, o sea, la de \( \beta \), a la que le anexé el trozo \( \gamma_{j+1},\gamma_{j+2},\dots,\gamma \). Es más, mi intuición me dice que toda la primer secuencia \( \beta_0,\dots,\beta_{i-1},\alpha,\beta_{i+1},\dots, \beta \) es la misma que \( \gamma_0,\dots,\gamma_{j-1},\beta \) a no ser, quizás, por el orden de alguna de las fórmulas. Me baso en la creencia de que si dos secuencias de formación tienen largo mínimo, entonces han de ser la misma (a no ser, quizás, como dije antes, por reordenación de alguna fórmula).

Entonces debiera poderse probar que \( \beta_0,\dots,\beta_{i-1},\alpha,\beta_{i+1},\dots, \beta,\gamma_{j+1},\dots, \gamma \) es una secuencia de formación para \( \gamma \) de largo mínimo en la que ocurre \( \alpha \). Por el ejercicio B) apartado ii) \( \alpha \) es subfórmula de \( \gamma \).

Ese "debiera poderse" en la demostración debiera cambiarse por "aquí está la prueba". Pero no sé como hacerla.

Sí, cuando dije "concatenar" era una forma de resumir en una palabra lo que haces pero soy consciente de que no es una simple concatenación y estoy de acuerdo en que tu respuesta refuta mi objeción, pero ahora te planteo otra distinta: imagina que en \( \gamma \) aparece una fórmula atómica \( p \) que no aparece en \( \beta \). Nada impide que \( p \) aparezca en primer lugar en la sucesión de formación de \( \gamma \) en particular antes que \( \beta \), y según la forma en que enlazas las sucesiones, estás quitando \( p \), luego la sucesión resultante no es una sucesión de formación para \( \gamma \).

Muchísimas gracias por todo lo que me estás ayudando en estos temas, Carlos.

No hay de qué. No me cuesta nada hacerlo.

09 Abril, 2012, 02:07 pm
Respuesta #7

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,447
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
(...)estoy de acuerdo en que tu respuesta refuta mi objeción, pero ahora te planteo otra distinta: imagina que en \( \gamma \) aparece una fórmula atómica \( p \) que no aparece en \( \beta \). Nada impide que \( p \) aparezca en primer lugar en la sucesión de formación de \( \gamma \) en particular antes que \( \beta \), y según la forma en que enlazas las sucesiones, estás quitando \( p \), luego la sucesión resultante no es una sucesión de formación para \( \gamma \).

Tienes razón. Por ejemplo, si \( \gamma=(((\lnot p_2)\rightarrow (p_3\vee (p_1\leftrightarrow p_2)))\vee p_4) \), \( \alpha=(p_1\leftrightarrow p_2) \) y \( \beta=(p_3\vee (p_1\leftrightarrow p_2)) \) se tiene que \( \alpha \) es subfórmula de \( \beta \), y a su vez \( \beta \) es subfórmula de \( \gamma \).

Una secuencia de formación de largo mínimo para \( \gamma \) es:

\( {p_4,\ p_2,\ (\lnot p_2),\ p_3,\ (p_1\leftrightarrow p_2),\ \underbrace{(p_3\vee (p_1\leftrightarrow p_2))}_{=\beta},\ {\red ((\lnot p_2)\rightarrow (p_3\vee (p_1\leftrightarrow p_2))),\ (((\lnot p_2)\rightarrow (p_3\vee (p_1\leftrightarrow p_2)))\vee p_4)}} \)

Y una de largo mínimo para \( \beta \):

\( {\blue p_3,\ p_1,\ p_2,\ (p_1\leftrightarrow p_2),\ (p_3\vee (p_1\leftrightarrow p_2))} \)

Yo lo que estaba afirmando en mi demostración es que la tira

\( {{\blue p_3,\ p_1,\ p_2,\ (p_1\leftrightarrow p_2),\ (p_3\vee (p_1\leftrightarrow p_2))},\ {\red ((\lnot p_2)\rightarrow (p_3\vee (p_1\leftrightarrow p_2))),\ (((\lnot p_2)\rightarrow (p_3\vee (p_1\leftrightarrow p_2)))\vee p_4)}} \)

es secuencia de formación de largo mínimo para \( \gamma \), lo cual no es cierto porque no es secuencia de formación (eliminé \( p_4 \) sin querer :-\).

Hay una forma de solucionar ésto (creo), y es considerando un árbol de subórmulas definido por recursión como sigue:

\( -T(\varphi):=\ \varphi \) si \( \varphi \) es atómica.

\( -T((\varphi\square\psi)):=\ \xymatrix{\ar@{-}[r] & (\varphi\square\psi) \ar@{-}[r] & \\ T(\varphi)\ar@{-}[u] & & T(\psi) \ar@{-}[u]} \)

\( -T((\lnot \varphi)):=\ \xymatrix{(\lnot\varphi)\\ T(\varphi)\ar@{-}[u]} \)

Entonces la idea es armar la secuencia de formación para \( \gamma \), recorriendo el árbol correspondiente \( T(\gamma) \) de izquierda a derecha. De esta manera la secuencia \( \gamma_0,\dots,\gamma_{j-1},\beta \) es secuencia de formación de largo mínimo para \( \beta \) con lo cual nos aseguramos que no aparezcan allí fórmulas atómicas que sean usadas en los \( \gamma_k \) para \( j>k \).

De todas formas, sería un argumento algo rebuscado. Mucho mejor es la primer demostración que sugeriste. Primero, por su sencillez, y segundo, porque evita tener que encontrar una demostración alternativa para el ejercicio B) apartado i).

¡Muchas gracias por todo, Carlos!

Saludos
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print