Autor Tema: Deduccion natural

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

06 Noviembre, 2026, 01:40 am
Leído 183 veces

Nub

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,458
  • País: 00
  • Karma: +0/-0
Hola :), como pruebo \( \text{Si }\vdash\varphi,\text{ entonces }\vdash\psi\to\varphi \) ?? lo que no se es como usar la hipotesis   \(  \vdash \varphi  \)

Por ejemplo para probar \( \vdash\psi\to\varphi \)
puedo usar la regla de introducción del implica
\( \displaystyle \frac{\psi\vdash\varphi}{\vdash\psi\to\varphi}\;(\to I) \)

Pero ahora como pruebo \( \psi\vdash\varphi \)? por axioma no puedo, algo me dice que es usando la hipotesis pero no se que regla podría usar

Gracias  :)

06 Noviembre, 2026, 03:41 am
Respuesta #1

Masacroso

  • “Lo que oigo, lo olvido; lo que veo, lo recuerdo; lo que hago, lo aprendo” (antiguo proverbio chino)
  • Moderador Global
  • Mensajes: 5,485
  • País: es
  • Karma: +0/-0
Pero ahora como pruebo \( \psi\vdash\varphi \)? por axioma no puedo, algo me dice que es usando la hipotesis pero no se que regla podría usar

Gracias  :)

Dentro de la deducción natural no lo tengo del todo claro, porque además hay varias formas esencialmente iguales de definir la deducción natural, por ejemplo yo he leído más veces sobre aquella que no utiliza secuentes más que la que utiliza secuentes. Pero esto \( \vdash \varphi  \) significa que, dentro de la teoría en la que estés, existe una demostración de \( \varphi  \), de ahí se hace evidente que entonces \( \psi \vdash \varphi  \) también se cumple si tienes en cuenta lo que es una demostración, como una sucesión finita de axiomas, premisas y proposiciones donde cualquier proposición de la lista finita que constituye la demostración se demuestra de proposiciones anteriores en la lista a través de las reglas de inferencia del sistema (en este caso, deducción natural).

Como las premisas de \( \vdash \varphi  \) es el conjunto vacío entonces una demostración se \( \varphi  \) existe de los axiomas de la teoría. Es decir, existe una derivación \( \varphi _1,\ldots ,\varphi _n,\varphi  \) donde \( \varphi _1 \) es un axioma y el resto de proposiciones \( \varphi _k \) o bien son otros axiomas o proposiciones que se siguen de proposiciones anteriores en la lista y el uso de alguna regla de inferencia. Entonces lo que tienes que demostrar es que si \( \varphi _1,\ldots ,\varphi _n,\varphi  \) es una derivación, entonces también lo es \( \psi ,\varphi _1,\ldots ,\varphi _n,\varphi  \).

La forma más "formal" de demostrar lo anterior es utilizar inducción estructural sobre las reglas de inducción del sistema, es decir que si \( A,B \vdash C \) es una regla de inferencia del sistema, entonces \( \psi ,A,B\vdash C \) es correcto. Aunque no sé si habrá otra manera más directa o sencilla. En verdad es todo bastante trivial, aunque engorroso de escribir correctamente, y yo ahora mismo tengo esto bastante olvidado.

Igualmente aclaro que podría estar equivocado en algún punto de lo que haya dicho, porque esto lo miré hace ya bastantes años y no me quedó 100% claro, especialmente la terminología utilizada. Esto que te piden es una "demostración" metateorética, para la cual debes utilizar una parte de "razonamiento común", que en esencia suele ser lógica proposicional junto al principio de inducción y unas vagas nociones de teoría de conjuntos naïve. Otros usuarios quizá sepan explicarte esto mejor que yo.

06 Noviembre, 2026, 10:15 am
Respuesta #2

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Para responderte sería necesario que especificaras qué definiciones estás manejando. Para empezar, es fundamental que aclares si \( \psi\vdash \varphi  \) es un secuente o significa que existe una deducción de \( \varphi \) con premisa \( \psi \). Sin eso, lo máximo que se puede decir es lo que te ha dicho masacroso:

Pero esto \( \vdash \varphi  \) significa que, dentro de la teoría en la que estés, existe una demostración de \( \varphi  \), de ahí se hace evidente que entonces \( \psi \vdash \varphi  \) también se cumple si tienes en cuenta lo que es una demostración, como una sucesión finita de axiomas, premisas y proposiciones donde cualquier proposición de la lista finita que constituye la demostración se demuestra de proposiciones anteriores en la lista a través de las reglas de inferencia del sistema (en este caso, deducción natural).

Como las premisas de \( \vdash \varphi  \) es el conjunto vacío entonces una demostración se \( \varphi  \) existe de los axiomas de la teoría. Es decir, existe una derivación \( \varphi _1,\ldots ,\varphi _n,\varphi  \) donde \( \varphi _1 \) es un axioma y el resto de proposiciones \( \varphi _k \) o bien son otros axiomas o proposiciones que se siguen de proposiciones anteriores en la lista y el uso de alguna regla de inferencia. Entonces lo que tienes que demostrar es que si \( \varphi _1,\ldots ,\varphi _n,\varphi  \) es una derivación, entonces también lo es \( \psi ,\varphi _1,\ldots ,\varphi _n,\varphi  \).

con una posible variante: es muy probable que tu definición de deducción a partir de unas premisas permita usar las premisas, pero no lo exija. Si es así, ni siquiera hay que demostrar lo que dice masacroso, sino que si \( \varphi _1,\ldots ,\varphi _n,\varphi  \) es una deducción de \( \varphi \) (sin premisas) también es una deducción de \( \varphi \) con premisa \( \psi \), y no hay nada que probar.

Pero insisto que esto es la idea de fondo y que falta saber el contexto concreto para saber si realmente hay algo que demostrar o no.

06 Noviembre, 2026, 06:09 pm
Respuesta #3

Nub

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,458
  • País: 00
  • Karma: +0/-0
Para responderte sería necesario que especificaras qué definiciones estás manejando. Para empezar, es fundamental que aclares si \( \psi\vdash \varphi  \) es un secuente o significa que existe una deducción de \( \varphi \) con premisa \( \psi \).
Tengo que:
"Escribiremos Γ ⊢ φ para denotar que, a partir del conjunto de formulas Γ (hipotesis), podemos obtener una prueba de φ (conclusión). A estas afirmaciones las llamamos secuentes. Si Γ = ∅, decimos que φ es un teorema, y lo escribimos ⊢ φ"

Y luego tengo todas las reglas de inferencia, conjunción,disyunción,implicación, si solo si, negación y absurdo

Y básicamente lo que hago yo para probar un secuente es tomar lo que quiero probar y ir haciendo un arbol aplicando reglas de inferencia hasta llegar a que las hojas del arbol son axiomas y ahí queda probado

Con lo que dijo Masacroso no se podria decir como \( \vdash \varphi \) se cumple siempre y no necesita hipotesis, entonces añadirle otra hipotesis da lo mismo y se cumplira de todas formas, osea añadirle esa hipotesis (en este caso \( \psi \)) seria como redundante ??

06 Noviembre, 2026, 08:39 pm
Respuesta #4

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Tengo que:
"Escribiremos Γ ⊢ φ para denotar que, a partir del conjunto de formulas Γ (hipotesis), podemos obtener una prueba de φ (conclusión). A estas afirmaciones las llamamos secuentes. Si Γ = ∅, decimos que φ es un teorema, y lo escribimos ⊢ φ"

Y luego tengo todas las reglas de inferencia, conjunción,disyunción,implicación, si solo si, negación y absurdo

Y básicamente lo que hago yo para probar un secuente es tomar lo que quiero probar y ir haciendo un arbol aplicando reglas de inferencia hasta llegar a que las hojas del arbol son axiomas y ahí queda probado

Puestos a entender la forma concreta en que trabajas, hay un detalle que sigue sin cuadrarme, porque dices que tienes "reglas de inferencia" (y no mencionas ningún axioma), pero luego dices que construyes árboles hasta que todas las hojas sean axiomas. ¿Qué axiomas?

¿Además de las reglas de inferencia tienes unos axiomas?

Por otro lado, entiendo que para demostrar \( \Gamma \vdash \varphi \) admitirás hojas de la forma \( \vdash \alpha \), con \( \alpha \) en \( \Gamma \), o algo así, pero no exigirás que tengan que aparecer necesariamente hojas así, que contengan las premisas admisibles, con lo cual, un árbol que te justifique \( \vdash \varphi \) también te justifica \( \psi\vdash \varphi \), sin cambio alguno, por lo que puedes concluir que si se cumple \( \vdash \varphi \), también se cumple \( \psi\vdash \varphi \).

Más en general, un hecho que supongo que tendrás que usar a menudo es que si \( \Delta\subset \Gamma \) son dos conjuntos de fórmulas y \( \Delta\vdash \varphi \), entonces \( \Gamma\vdash \varphi \), por la misma razón. En resumen:

Con lo que dijo Masacroso no se podria decir como \( \vdash \varphi \) se cumple siempre y no necesita hipotesis, entonces añadirle otra hipotesis da lo mismo y se cumplira de todas formas, osea añadirle esa hipotesis (en este caso \( \psi \)) seria como redundante ??

Sí, eso es. Me siguen faltando algunos detalles para saber qué haces exactamente, pero la idea es ésa.

06 Noviembre, 2026, 10:06 pm
Respuesta #5

Nub

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,458
  • País: 00
  • Karma: +0/-0
Puestos a entender la forma concreta en que trabajas, hay un detalle que sigue sin cuadrarme, porque dices que tienes "reglas de inferencia" (y no mencionas ningún axioma), pero luego dices que construyes árboles hasta que todas las hojas sean axiomas. ¿Qué axiomas?
Cuando dije axioma me referia a la regla:
Las hojas de los árboles deben ser instancias de la regla de axioma, que no tiene premisas:

\( \displaystyle \frac{}{\Gamma, \varphi \vdash \varphi}\quad ax \)
Esta regla permite probar una fórmula \( \varphi \) directamente si se encuentra entre las hipótesis, sin necesitar premisas.
Citar
¿Además de las reglas de inferencia tienes unos axiomas?
No, solo tengo la regla del axioma que dicho informalmente sirve para probar algo que ya lo tienes en el conjunto de las hipotesis

Para dar un ejemplo de lo que hago basicamente:

Para probar el secuente \( p \land q \vdash q \land p \) usando las reglas  para construir un árbol de derivación:

\( \Huge\displaystyle \frac{ \frac{ \frac{}{p \land q \vdash p \land q}\ ax }{ p \land q \vdash q }\land E \qquad \frac{ \frac{}{p \land q \vdash p \land q}\ ax }{ p \land q \vdash p }\land E }{ p \land q \vdash q \land p }\land I  \)

Y si lo ves como un arbol con raiz abajo y que va subiendo, las hojas osea el secuente por ejemplo \( \displaystyle p \land q \vdash p \land q \) se "prueba" por axioma o mejor dicho por la regla del axioma... :P

06 Noviembre, 2026, 10:21 pm
Respuesta #6

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Vale, entonces estás usando un cálculo secuencial. Hay algún detalle que me chirría, pero probablemente no sea esencial para lo que preguntas. En principio, lo que me sorprendería es que en las reglas de inferencia que te han dado no estuvieran las reglas de debilitación:

\( \begin{array}{rcl}
\Gamma&\vdash&\Delta\\
\hline
\alpha, \Gamma&\vdash&\Delta
\end{array}\qquad \begin{array}{rcl}
\Gamma&\vdash&\Delta\\
\hline
\Gamma&\vdash&\Delta, \alpha
\end{array} \)

Si tienes estas reglas, lo que planteabas es un caso particular de la regla de debilitación izquierda. Si no las tienes, no me acabo de hacer una idea de cómo puedes trabajar sin ellas.

06 Noviembre, 2026, 10:45 pm
Respuesta #7

Nub

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,458
  • País: 00
  • Karma: +0/-0
Vale, entonces estás usando un cálculo secuencial. Hay algún detalle que me chirría, pero probablemente no sea esencial para lo que preguntas. En principio, lo que me sorprendería es que en las reglas de inferencia que te han dado no estuvieran las reglas de debilitación:

\( \begin{array}{rcl}
\Gamma&\vdash&\Delta\\
\hline
\alpha, \Gamma&\vdash&\Delta
\end{array}\qquad \begin{array}{rcl}
\Gamma&\vdash&\Delta\\
\hline
\Gamma&\vdash&\Delta, \alpha
\end{array} \)

Si tienes estas reglas, lo que planteabas es un caso particular de la regla de debilitación izquierda. Si no las tienes, no me acabo de hacer una idea de cómo puedes trabajar sin ellas.
no, no tengo esas reglas :(

06 Noviembre, 2026, 10:54 pm
Respuesta #8

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
no, no tengo esas reglas :(

Y entonces, ¿cómo demostrarías tú esto?


06 Noviembre, 2026, 11:01 pm
Respuesta #9

Nub

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,458
  • País: 00
  • Karma: +0/-0
no, no tengo esas reglas :(

Y entonces, ¿cómo demostrarías tú esto?


Aplicaría dos veces la regla de introducción del implica, espera y ahora lo pongo en latex que esta dificil  :-[

\(
\Huge
\frac{
    \frac{
        \frac{}{
            A,B\vdash A
        }\;(Ax)
    }{
        A\vdash B\to A
    }\;(\to I)
}{
    \vdash A\to(B\to A)
}\;(\to I)
 \)