Rincón Matemático

Matemática => Lógica, Conjuntos, Lenguajes Formales => Mensaje iniciado por: Raul C en 13 Noviembre, 2020, 08:39 am

Título: Lógica de predicados: Deducción. Duda sobre cómo continuar.
Publicado por: Raul C en 13 Noviembre, 2020, 08:39 am
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
Título: Re: Logica predicados: Deducción. Duda de como continuar.
Publicado por: geómetracat en 13 Noviembre, 2020, 08:59 am
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) \).

Título: Re: Logica predicados: Deducción. Duda de como continuar.
Publicado por: Raul C en 13 Noviembre, 2020, 09:24 am
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.
Título: Re: Logica predicados: Deducción. Duda de como continuar.
Publicado por: geómetracat en 13 Noviembre, 2020, 09:38 am
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.
Título: Re: Logica predicados: Deducción. Duda de como continuar.
Publicado por: Raul C en 13 Noviembre, 2020, 09:47 am
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!
Título: Re: Logica predicados: Deducción. Duda de como continuar.
Publicado por: Carlos Ivorra en 13 Noviembre, 2020, 10:35 am
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.

Título: Re: Logica predicados: Deducción. Duda de como continuar.
Publicado por: Raul C en 13 Noviembre, 2020, 11:13 am
Muchas gracias Carlos por las aclaraciones y explicaciones.

Un saludo cordial.
Título: Re: Lógica predicados: Deducción. Duda de cómo continuar.
Publicado por: manooooh en 13 Noviembre, 2020, 02:18 pm
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
Título: Re: Logica predicados: Deducción. Duda de como continuar.
Publicado por: geómetracat en 13 Noviembre, 2020, 04:01 pm
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.
Título: Re: Logica predicados: Deducción. Duda de como continuar.
Publicado por: manooooh en 13 Noviembre, 2020, 09:16 pm
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) \) (https://en.wikipedia.org/wiki/Equality_(mathematics)#Logical_definitions).
[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
Título: Re: Logica predicados: Deducción. Duda de como continuar.
Publicado por: geómetracat en 13 Noviembre, 2020, 10:37 pm
Pues no sé si se puede decir nada muy interesante en general, más allá de que  \( \exists x Px \) por sí solo no implica \( \forall x Px \). Desde luego algo del estilo "si tienes una variable cuantificada existencialmente en las premisas y universalmente en la conclusión seguro que el razonamiento es inválido" es falso.
Depende mucho del razonamiento y de las otras premisas que tengas. Por poner otro ejemplo, si en tu razonamiento (inválido) 2 cambias la disyunción de la primera premisa por una conjunción el razonamiento pasa a ser válido, y no has tocado ni la premisa donde aparecía el \( \exists x \) ni la conclusión.
Título: Re: Logica predicados: Deducción. Duda de como continuar.
Publicado por: manooooh en 14 Noviembre, 2020, 01:18 am
Hola

(...) Por poner otro ejemplo, si en tu razonamiento (inválido) 2 cambias la disyunción de la primera premisa por una conjunción el razonamiento pasa a ser válido, y no has tocado ni la premisa donde aparecía el \( \exists x \) ni la conclusión.

Eso es trampa :laugh:, si la cambiamos usamos eliminación de la conjunción y listo el razonamiento!! :laugh:

Entiendo tu punto y me has aclarado que lo que pensaba como cierto en realidad no es así. Por hilar más fino:

(...) más allá de que  \( \exists x Px \) por sí solo no implica \( \forall x Px \). (...)

¿Qué significa ese "por sí solo"? ¿Cómo se lo expresaría genéricamente? ¿Puede tener cuantificadores por delante o por detrás y sigue siendo algo que no implique por el mero hecho de "Si una variable está cuantificada existencialmente entonces no implica que lo esté universalmente" o realmente depende de cómo esté armado el razonamiento? Si conoces de algún teorema o propiedad genérica relacionado a esto, me interesa, y si no hay pues lo dejo aquí.

Saludos
Título: Re: Logica predicados: Deducción. Duda de como continuar.
Publicado por: geómetracat en 14 Noviembre, 2020, 10:34 am
¿Qué significa ese "por sí solo"?

Sin premisas adicionales. Si tienes otras premisas puede pasar cualquier cosa. Por ejemplo, una variante de lo que te puse antes: si tienes premisas \( \exists x Px \) y \( \exists x \forall y (x=y) \), entonces se deduce \( \forall x Px \), ya que la segunda premisa te dice que solamente hay un elemento. O podría pasar que las otras premisas ya implicaran directamente \( \forall x Px \).

Citar
¿Cómo se lo expresaría genéricamente?
Yo lo pondría \[ \exists x Px \not\vdash \forall x Px \].

Citar
¿Puede tener cuantificadores por delante o por detrás y sigue siendo algo que no implique por el mero hecho de "Si una variable está cuantificada existencialmente entonces no implica que lo esté universalmente" o realmente depende de cómo esté armado el razonamiento? Si conoces de algún teorema o propiedad genérica relacionado a esto, me interesa, y si no hay pues lo dejo aquí.

No entiendo esta pregunta. La verdad es que no se me ocurre nada general que tenga que ver con esto, ni creo que se pueda decir gran cosa, ya que depende de qué otras premisas tengas.