Autor Tema: ¡Ejercicios de wf similares!

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

16 Noviembre, 2012, 08:02 pm
Leído 1433 veces

yotas

  • Sé valiente, no voluble, no maleable.
  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 725
  • Karma: +0/-0
  • Sexo: Masculino
  • Plop, plop.
¡Buenas buenas!

Quisiera preguntar sobre un ejercicio que logré hacer parcialmente pero me lié con la última parte del paso inductivo. Mucho de lo que mencione ya se mencionó en este post:
http://rinconmatematico.com/foros/index.php/topic,63145.0.html
y está mejor explicado.
Cabe añadir que se puede usar regla C.
Regla C
\( \gamma\vdash_c \mathcal A \) si y sólo si existe una secuencia de wfs \( \mathcal B_1,..., \mathcal B_n \) tal que \( \mathcal B_n \) es \( \mathcal A \) y las siguientes cuatro condiciones se mantienen:
1. Para cada \( i\leq n \), o:
    (a) \( \mathcal B_i \) es un axioma de \( K \), o
    (b) \( \mathcal B_i \) está en \( \gamma \), o
    (c) \( \mathcal B_i \) se sigue por MP o Gen de alguna wf precedente en la secuencia, o
    (d) Existe una wf precedente \( \exists x \mathcal C(x) \) tal que \( \mathcal B_i \) es \( \mathcal C(d) \) donde d es una nueva constante individual. (Regla C)
2.  Como axiomas en la condición 1(a), también se pueden usar todos los axiomas lógicos que envuelvan nuevas constantes individuales conseguidas por la aplicación de 1(d).
3. Ninguna aplicación de Gen es hecha usando variables que son libres en algún \( \exists x \mathcal C(x) \) en la cual Regla C ha sido aplicada.
4. \( \mathcal A \) no contiene ninguna de las nuevas constantes individuales introducidas por la aplicación de la Regla C.
[cerrar]

Proposición importante 1. Si \( \gamma\vdash_c\mathcal A \) entonces \( \gamma\vdash\mathcal A \).
Proposición importante 2. Todo teorema de cálculo de predicados de primer es lógicamente válido.

Último concepto importante antes de hacer la pregunta: Si \( x_i \) y \( x_j \) son variables distintas, entonces \( \mathcal A(x_i) \) y \( \mathcal A(x_j) \) se dicen similares si y sólo si \( xJ \) es libre para \( x_i \) en \( \mathcal A(x_i) \) y \( \mathcal A(x_i) \) no tiene ocurrencias libre de \( x_j \). Se asume que \( \mathcal A(x_j) \) se obtiene de \( \mathcal A_i \) por la sustitución de \( x_j \) para cada ocurrencia libre de \( x_i \). Si \( \mathcal A(x_i) \) y \( \mathcal A(x_j) \) son similares entonces \( x_i \) es libre para \( x_j \) en \( \mathcal A(x_j) \) y \( \mathcal A(x_i) \) no tiene ocurrencias libres de \( x_i \).

Una petición intermedia: me gustaría algún ejemplo de esta última definición.  :D

Lema importante (casi base del ejercicio): Si \( \mathcal A(x_i) \) y \( \mathcal A(x_j) \) son similares, entonces \( \vdash\forall \mathcal A(x_i)\Longleftrightarrow\mathcal A(x_j) \).

¡El ejercicio! (al fin):
Cambio de variables ligadas. Si \( \mathcal B(x) \) es similar a \( \mathcal B(y) \), \( \forall x\red{\mathcal B(x)} \) es una subfórmula de \( \mathcal A \), y \( \mathcal A' \) es el resultado de reemplazar una o más ocurrencias de \( \forall x\mathcal B(x) \) por \( \forall y\mathcal B(y) \), demuestre que \( \vdash\mathcal A\Longleftrightarrow \mathcal A'  \).

Ese es el ejercicio, del cual pude hacer casi todo, haciéndolo por inducción exceptuando el caso en que \( \mathcal A \) era \( \forall x_i\mathcal C \) y no lo logré hacer mucho.

Pensaba subir toda la parte que había hecho en la demostración, pero no me ha alcanzado el tiempo. Dándome el tiempo en la noche, lo subiré en la noche. Pero creo que esa información puede servir para ser aconsejado.  :P

¡Muchísimas gracias por los consejos y comentarios!  ;D

PD: ¡El servidor se está cayendo mucho!
Citar
Creo debes tener un problema en tu mente por el cual complicas las cosas y las afirmaciones más sencillas.

Sí, es un problema muy frecuente en este foro. Se llama saber matemáticas.

16 Noviembre, 2012, 10:02 pm
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 9,674
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Una petición intermedia: me gustaría algún ejemplo de esta última definición.  :D

Aproximadamente, quiere decir simplemente que \( \mathcal A(y) \) es la fórmula que resulta de cambiar cada \( x \) libre por una \( y \) en \( A(x) \). Pero esto no es exactamente así porque habría problemas si \( x \) estuviera libre en una subfórmula en la que \( y \) estuviera ligada.

Por ejemplo, si \( \mathcal A(x) = \forall y(y\,R\,x\rightarrow y\,R\,c) \), ahí no puedes cambiar la \( x \) por una \( y \) sin alterar el significado de la fórmula, por lo que \( \mathcal A(y)\equiv \forall y(y\,R\,y\rightarrow y\,R\,c) \) no es similar a \( \mathcal A(x) \). En cambio, si  \( \mathcal A(x) = \forall z(z\,R\,x\rightarrow z\,R\,c) \), entonces \( \mathcal A(y) \) sí que es similar a \( \mathcal A(x) \).

Respecto al ejercicio, dices que \( \forall x\mathcal A \) es una subfórmula de \( \mathcal A \). Obviamente hay alguna errata.

17 Noviembre, 2012, 10:31 pm
Respuesta #2

yotas

  • Sé valiente, no voluble, no maleable.
  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 725
  • Karma: +0/-0
  • Sexo: Masculino
  • Plop, plop.
Respecto al ejercicio, dices que \( \forall x\mathcal A \) es una subfórmula de \( \mathcal A \). Obviamente hay alguna errata.

¡Corregido! :D
Citar
Creo debes tener un problema en tu mente por el cual complicas las cosas y las afirmaciones más sencillas.

Sí, es un problema muy frecuente en este foro. Se llama saber matemáticas.

18 Noviembre, 2012, 12:10 am
Respuesta #3

Carlos Ivorra

  • Administrador
  • Mensajes: 9,674
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Ese es el ejercicio, del cual pude hacer casi todo, haciéndolo por inducción exceptuando el caso en que \( \mathcal A \) era \( \forall x_i\mathcal C \) y no lo logré hacer mucho.

¿Y cuál es el problema? Por hipótesis de inducción tienes que \( \mathcal C\longrightarrow \mathcal C' \), y sólo tienes que deducir de ahñi que \( \forall x\mathcal C\longrightarrow \forall x\mathcal C' \).

Supones \( \forall x\mathcal C \), eliminas el generalizador, aplicas la hipótesis de inducción y generalizas otra vez.

18 Noviembre, 2012, 01:50 am
Respuesta #4

yotas

  • Sé valiente, no voluble, no maleable.
  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 725
  • Karma: +0/-0
  • Sexo: Masculino
  • Plop, plop.
Ese es el ejercicio, del cual pude hacer casi todo, haciéndolo por inducción exceptuando el caso en que \( \mathcal A \) era \( \forall x_i\mathcal C \) y no lo logré hacer mucho.

¿Y cuál es el problema? Por hipótesis de inducción tienes que \( \mathcal C\longrightarrow \mathcal C' \), y sólo tienes que deducir de ahñi que \( \forall x\mathcal C\longrightarrow \forall x\mathcal C' \).

Supones \( \forall x\mathcal C \), eliminas el generalizador, aplicas la hipótesis de inducción y generalizas otra vez.
¡Aaaaaaah! ¡Claro! ¡Gracias!  ;D
Citar
Creo debes tener un problema en tu mente por el cual complicas las cosas y las afirmaciones más sencillas.

Sí, es un problema muy frecuente en este foro. Se llama saber matemáticas.