Autor Tema: Lógica de predicados: Deducción. Duda sobre cómo continuar.

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

13 Noviembre, 2020, 08:39 am
Leído 906 veces

Raul C

  • Cura y creyente
  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 20
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Estoy ahora con ejercicios de Deducción natural y este no lo pillo por ningún sitio....

Creo que aquí el secreto esta en jugar con las letras de las nuevas variables, pero la verdad es que me va a estallar la cabeza. alguna pista por donde empezar?
Las premisas:
\( ∀x

y
(
¬
(
R
(
x
)

¬
T
(
x
,
y
)
)
) \)
\( ∀x ∃y (P(x) →Q(x,y)) \)
\( ∃
x

y
(
R
(
x
)

Q
(
x
,
y
)

¬
T
(
x
,
y
)
) \)
conclusión: \( ∃y ¬(P(x) \)

\( ∀x ∃y (P(x) →Q(x,y)) = P(x)→Q(x, a) \) donde la a es la nueva variable que hay que meter al quitar el "existe"
\[ ∀
x

y
(
¬
(
R
(
x
)

¬
T
(
x
,
y
)
)
)
=
¬
(
R
(
x
)

¬
T
(
x
,
x
)
) \] este es mas facil, pues son dos universales, y se puede poner cualquier cosa.
\[ ∃
x

y
(
R
(
x
)

Q
(
x
,
y
)

¬
T
(
x
,
y
)
)
=
R
(
i
)

Q
(
i
,
x
)

¬
T
(
i
,
x
) \] este no se me ocurre mas que quitar el exis y el universal, pero hay que meter variable nueva.
Y a partir de aquí me pierdo....

Un saludo cordial y gracias de antemano

13 Noviembre, 2020, 08:59 am
Respuesta #1

geómetracat

  • Moderador Global
  • Mensajes: 2,662
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Los detalles exactos pueden depender de las reglas concretas que te hayan dado.

Hay que tener un cierto cuidado al quitar los cuantificadores, porque el orden es importante. Por ejemplo, aquí
$$∀x ∃y (P(x) →Q(x,y)) = P(x)→Q(x, a)$$
hay que tener cuidado porque el \( a \) depende del \( x \). Por otra parte, no es muy ortodoxo eliminar el cuantificador universal y dejar \( x \) como si fuera una variable.

Yo haría lo siguiente para quitar cuantificadores. Primero quitas el cuantificador existencial de la tercera premisa y obtienes:
$$\forall y (R(a)\wedge Q(a,y) \to \neg T(a,y))$$
Ahora quitas el primer cuantificador universal de la primera y de la segunda premisa usando el \( a \) de antes, con lo que tienes:
$$\forall y(\neg(R(a) \to \neg T(a,y)))$$
$$\exists y (P(a) \to Q(a,y))$$

Ahora quitas el existencial de la segunda:
$$P(a) \to Q(a,b)$$
Y finalmente quitas el universal de la primera y de la tercera usando el \( b \):
$$\neg(R(a) \to \neg T(a,b))$$
$$R(a)\wedge Q(a,b) \to \neg T(a,b)$$

Resumiendo, ahora tienes:
$$\neg(R(a) \to \neg T(a,b))$$
$$P(a) \to Q(a,b)$$
$$R(a)\wedge Q(a,b) \to \neg T(a,b)$$

Con esto debes demostrar $$\neg P(a)$$, que te da ya el resultado usando introducción del cuantificador existencial. Para ello te puede ayudar probar primero que la primera premisa (con los cuantificadores ya instanciados) es equivalente a \( R(a) \wedge T(a,b) \).

La ecuación más bonita de las matemáticas: \( d^2=0 \)

13 Noviembre, 2020, 09:24 am
Respuesta #2

Raul C

  • Cura y creyente
  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 20
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Lo malo es que en la segunda premisa: P(a) -> Q(a,b) no se puede utilizar la letra B de nuevo, puesto que tiene que ser una constante  nueva, sin usar. y se usa en la premisa 1.
Cada extracion de existencial, necesita una constante nueva, y no se puede repetir letra.

13 Noviembre, 2020, 09:38 am
Respuesta #3

geómetracat

  • Moderador Global
  • Mensajes: 2,662
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Pero si sigues el orden que te indico \( b \) es nueva. Solamente hay dos existenciales a quitar: en el primero introduzco \( a \) y en el segundo \( b \).
Lo demás son cuantificadores universales, y con esos sí que puedes poner lo que te dé la gana.
La ecuación más bonita de las matemáticas: \( d^2=0 \)

13 Noviembre, 2020, 09:47 am
Respuesta #4

Raul C

  • Cura y creyente
  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 20
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
tienes razón disculpa, es super importante el orden para quitar los universales y existenciales. Sin duda, una leccion que he aprendido.
Un saludo cordial!

13 Noviembre, 2020, 10:35 am
Respuesta #5

Carlos Ivorra

  • Administrador
  • Mensajes: 9,908
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Si estás aprendiendo a resolver este tipo de problemas, saber que en éste en concreto conviene quitar tal cuantificador aquí y aplicar tal regla allá te servirá de poco a la hora de resolver otro similar. Es como tratar de acertar una contraseña probando a poner unos números y, si no funcionan, otros.

Los problemas de este tipo sólo pueden resolverse (en el sentido de encontrar la deducción que te piden) si ya sabes antes la solución (si ya sabes por qué el razonamiento es correcto). Intentar encontrar la solución a ciegas, sin conocerla de antemano no tiene futuro, salvo en ejemplos muy simples.

En este caso en concreto, lo que tendrías que pensar para estar en condiciones de llegar a la deducción es algo como esto:

1) Me piden probar que existe un \( x \) que cumple algo. (Tienes una errrata en el enunciado: has puesto y cuando es \( x \))
2) La única premisa que afirma la existencia de algo es la tercera, luego, salvo que cualquier x te sirva para la conclusión, lo cual es muy poco probable, el \( x \) que estás buscando tiene que ser el  x cuya existencia te da la tercera premisa.
3) Por lo tanto el razonamiento tiene que empezar tomando un x que cumpla la tercera premisa.
4) Ahora queremos probar que ese \( x \) cumple \( \lnot P(x) \)
5) Si miramos las premisas, sólo hay una en la que aparezca \( P \), y es la segunda, luego la única forma que tenemos de probar que nuestro \( x \) no cumple \( P \), es probar que no existe ningún y que cumpla \( Q(x, y) \). De acuerdo con la premisa, eso implica que no se cumple \( P(x) \).
6) Por lo tanto, el siguiente paso natural sería tomar un y arbitrario y suponer, por reducción al absurdo que cumple \( Q(x, y) \), para llegar a una contradicción.
7) Pero la única premisa que puede ayudarnos para probar que no se cumple\( Q(x, y) \) es precisamente la tercera, es decir que ahora tenemos que aprovechar que \( x \) no es cualquiera, sino alguien que cumple la tercera premisa, porque así lo hemos tomado.
8) En la tercera premisa aparece \( R \). Si se cumple \( Q(x, y) \), nos dice que, si se cumple \( R(x) \), también se cumplirá \( \lnot T(x, y) \). Si queremos llegar a una contradicción, nuestra única esperanza es que esto contradiga lo que la primera premisa dice de \( R(x) \) y \( T(x, y) \).
9) Y, en efecto, la primera premisa dice que no es cierto que R implique no T, es decir, que se cumple \( R(x) \) y no se cumple \( T(x, y) \), que es justo lo contrario de lo que nos dice la tercera premisa. Esta contradicción termina la prueba de que se cumple \( \lnot P(x) \).

Ésto (u otro razonamiento similar) es lo que hay de fondo en el problema, y es el primer paso que tienes que dar ante cualquier problema de este tipo para no esperar que probando numeritos aciertertes algún día la contraseña (salvo que la contraseña sea un número del 1 al 5). El segundo paso es ver cómo algo así se puede formalizar en una aplicación de las reglas de inferencia que conoces. Por ejemplo, compara con lo que te ha dicho geómetracat:

Primero quitas el cuantificador existencial de la tercera premisa y obtienes:
$$\forall y (R(a)\wedge Q(a,y) \to \neg T(a,y))$$

Eso se corresponde con "el razonamiento tiene que empezar tomando un \( x \) que cumpla la tercera premisa". Geómetracat ha preferido llamar \( a \) a dicho \( x \), pero eso es irrelevante (salvo que adoptes algún convenio de dar nombres diferentes a las variables libres y a las ligadas).

Ahora quitas el primer cuantificador universal de la primera y de la segunda premisa usando el \( a \) de antes, con lo que tienes:
$$\forall y(\neg(R(a) \to \neg T(a,y)))$$
$$\exists y (P(a) \to Q(a,y))$$

Esto significa aplicar las premisas al \( x \) (o \( a \)) que has tomado. Se puede hacer ahora o en el momento en que necesites aplicárselas.

Ahora quitas el existencial de la segunda:
$$P(a) \to Q(a,b)$$

Esto es una forma de posponer la reducción al absurdo que he usado yo. En lugar de tomar un \( y \) arbitrario y probar que no cumple \( Q(x, y) \), usamos que la premisa nos da que hay un \( y \) que cumple \( P(x)\rightarrow Q(x, y) \) (geómetracat prefiere llamarlo \( b \)). Al final tendremos igualmente que razonar que no se cumple \( Q(x, y) \) (o \( Q(a, b) \), con las letras que ha elegido geómetracat) para probar \( \lnot P(x) \).

Y finalmente quitas el universal de la primera y de la tercera usando el \( b \):
$$\neg(R(a) \to \neg T(a,b))$$
$$R(a)\wedge Q(a,b) \to \neg T(a,b)$$

Esto significa aplicar las premisas al \( y \) (o \( b \)) que hemos tomado.

Resumiendo, ahora tienes:
$$\neg(R(a) \to \neg T(a,b))$$
$$P(a) \to Q(a,b)$$
$$R(a)\wedge Q(a,b) \to \neg T(a,b)$$

Los pasos que faltan siguen el esquema que te había trazado antes:

Tenemos que probar \( \lnot P(a) \), y esto sólo nos lo puede dar la segunda premisa, para lo cual hay que probar \( \lnot Q(a, b) \), y el camino natural para ello es probar que \( Q(a, b) \) vuelve contradictorias las premisas primera y tercera.

Como los problemas de este tipo suelen ser muy sencillos y ajustados para que cada hipótesis sea necesaria en el momento oportuno, en muchos de ellos es posible "ir a ciegas" diciendo: aquí convendrá quitar tal cuantificador, aquí convendrá hacer tal otra cosa...  pero eso es engañoso. En un problema "de verdad", la única forma de llegar a una deducción formal es saber realmente por qué tiene que ser cierta la conclusión y luego formalizar el argumento, que es muy distinto de encontrar el argumento formalmente.


13 Noviembre, 2020, 11:13 am
Respuesta #6

Raul C

  • Cura y creyente
  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 20
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Muchas gracias Carlos por las aclaraciones y explicaciones.

Un saludo cordial.

13 Noviembre, 2020, 02:18 pm
Respuesta #7

manooooh

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,438
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Aprecio muchísimo el interés que pusieron Carlos y geómetracat en sus forma metódicas y bien presentadas para resolver el problema de deducción :aplauso:.

Tengo una duda, creo no haberla expresado anteriormente:

Si tenemos un razonamiento con al menos una variable cuantificada existencialmente y la conclusión tiene a la misma variable cuantificada universalmente, ¿podemos decir que el razonamiento siempre será inválido?

Esto parece lógico porque \( \exists x(Px)\not\to\forall x(Px) \) pero quisiera saber si sirve para razonamientos con predicados multivariables.

Gracias y saludos

13 Noviembre, 2020, 04:01 pm
Respuesta #8

geómetracat

  • Moderador Global
  • Mensajes: 2,662
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
No sé si entiendo correctamente la pregunta, pero yo diría que no, depende del razonamiento. Por ejemplo, podrías tener algo del estilo:
Premisa: \( \exists x (P(x) \wedge \forall y(y=x)) \)
Conclusión: \( \forall x P(x) \)
Este es un razonamiento válido.
La ecuación más bonita de las matemáticas: \( d^2=0 \)

13 Noviembre, 2020, 09:16 pm
Respuesta #9

manooooh

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,438
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

No sé si entiendo correctamente la pregunta, pero yo diría que no, depende del razonamiento. Por ejemplo, podrías tener algo del estilo:
Premisa: \( \exists x (P(x) \wedge \forall y(y=x)) \)
Conclusión: \( \forall x P(x) \)
Este es un razonamiento válido.

Ah, tienes razón, a ver si me expreso mejor:

Es obvio que si una propiedad se cumple para algunos valores de \( x \), no implica que lo cumplan todos.

Esto pensaba que se aplicaba a cualquier predicado unario, es decir, de la forma \( P(x) \). En el caso que muestras se tiene que \( \exists x(P(x)\land\forall y\,Px\leftrightarrow Py)\therefore\forall x\,P(x) \) es válido (Razonamiento 1)

Aclaración
Aquí he usado que \( a=b\iff P(a)\leftrightarrow P(b) \).
[cerrar]

mientras que por ejemplo el razonamiento siguiente:

Premisa 1: \( \forall x\,\forall y\,P(x,y)\lor Q(x,y) \)
Premisa 2: \( \exists x\,\forall y\,\neg Q(x,y) \)
Conclusión: \( \forall x\,\forall y\, P(x,y) \)

es inválido (Razonamiento 2) porque no es cierto en general que dado un valor particular de \( x \), tenga que valer para cualquier \( x \). Pero si cambiamos la premisa 2 en vez de \( \exists x \) por \( \forall x \) tenemos lo que (considero) se conoce como Silogismo Disyuntivo.

Aclaración
"considero" porque creo que es un caso particular de 2 variables, mientras que el SD se enuncia para cualquier razonamiento como \( A\lor B,\neg B\therefore A \).
[cerrar]

¿Qué diferencia hay entre el razonamiento 1 y 2 que hace que uno sea válido y el otro inválido? No creo que sea por la cantidad de variables de los predicados.

Gracias y saludos