Usuario:Fercho/ejercicio 22

Demostrar que (P(x) → Q(y)) ^ (Q(y) → R(z)) → (P(z) → Q(z)) no es válida.

SOLUCION

No existe un método general para demostrar si es válida o no una expresión en el cálculo de predicados. Lo cual no quiere decir que no se pueda resolver el ejercicio. En la lógica existen infinidad razonamientos que se podemos hacer para demostrar algo, sólo se requiere de tener claro los conceptos y mucha imaginación y creatividad a la hora de aplicarlos en un problema determinado como éste.

A partir del cálculo proposicional podemos hacer uso de varias herramientas, como el teorema de la refutación, las cláusulas, la contradicción, etc. Empecemos por la más fácil de comprender, es una ley muy conocida: la contradicción, la cual es muy usada para demostrar que los argumentos lógicos son válidos. Hay que observar claro está que un argumento no puede ser válido si todas las premisas son verdaderas, pero llegaríamos entonces a una conclusión es falsa. De este modo las contradicciones están estrechamente ligadas a las tautologías. De hecho si A es una tautología decimos entonces que￢A es una contradicción, y viceversa.

Veamos lo siguiente, una contradicción es de la forma p ^￢p. En donde p bien puede ser una proposición atómica o compuesta. En general cualquier expresión que contenga cualquier conector se puede convertir en una implicación o viceversa. De modo que por medio de la equivalencia lógica llegamos a una nueva expresión en la cual no cambia en absoluto el valor de verdad de la expresión original. Observen lo siguiente:

Eliminación del condicional (Sean p y q proposiciones)

Archivo:Pensamiento algorítmico eliminación del condicional.jpg

Si desean hagan la tabla de verdad para ver que es cierto lo dicho anteriormente. En este sentido vemos que hay que tener claro el concepto de contradicción, equivalencia lógica,

Si en una expresión en donde tenemos una implicación en la cual tomamos los valores de verdad el valor de verdad de la expresión nos da (F). Entonces hay que hacer una suposición y luego al desarrollarla se pueden llegar a dos casos: 1) Que la suposición sea cierta (V) por lo cual podemos deducir que la expresión original es falsa (F). 2) Que la suposición sea falsa (F) por lo cual podemos deducir que la expresión original es cierta (V).

Cabe decir que lo anteriormente dicho sirve para entender el teorema que vamos a aplicar en el problema lo vamos a desarrollar por Resolución que es método para hacer derivaciones que posee las siguientes propiedades:

1) Las únicas expresiones que se permiten son las cláusulas que son disyunciones de todos los literales, un literal es una proposición o su complemento.

2) Se ajusta al principio de refutación, es decir, demuestra que la negación de la conclusión es inconsistente con las premisas.

3) Hay esencialmente una sola regla de inferencia, la resolución.

En un sistema de refutación se prueba que A1, A2,…,An y ￢C no pueden ser verdaderos. En otras palabras, se muestra que las proposiciones A1, A2,…,An, ￢C son inconsistentes. Esto se demuestra probando que para una cierta proposición P, se puede derivar ambas P ^￢P.

Bueno ahora si veamos lo siguiente: Se tiene la expresión (P(x) → Q(y)) ^ (Q(y) → R(z)) → (P(z) → Q(z)) de la cual vamos a demostrar que no es válida, para la cual vamos a negar el consecuente de lo cual llegamos a la siguiente expresión:

(P(x) → Q(y)) ^ (Q(y) → R(z)) →￢(P(z) → Q(z))

Luego por eliminación del condicional en el antecedente(￢P(x) v Q(y)) ^ (￢Q(y) v R(z)) y el consecuente tenemos ￢(￢P(z) v Q(z)) que nos da (P(z) ^ ￢Q(z)). Luego la expresión nos queda:

(￢P(x) v Q(y)) ^ (￢Q(y) v R(z)) ^ (P(z) ^ ￢Q(z))

De ésta última expresión utilizamos comas dentro de los corchetes para representar las disyunciones, y comas fuera de los corchetes para representar las conjunciones. En general se puede convertir cualquier proposición en una o más cláusulas. Para esto, primero se convierten todas las proposiciones en una conjunción de disyunciones, es decir, se convierten las proposiciones en formas normales conjuntivas. Cada término de la conjunción se convierte en una cláusula de si misma.

Llegamos entonces 4 cláusulas:

{￢P, Q} , {￢Q, R} , {P} , {￢Q}

De las cláusulas obtenidas procedemos a relacionarlas entre si por las conjunciones que están afuera de los corchetes lo cual nos genera varias contradicciones que vamos descartando hasta llegar contradicciones de manera que podríamos llegar a una cláusula vacía lo cual hace que de partir de la suposición se llega a una contradicción (de algo no se llega a la nada), caso contrario llegamos a algo luego la suposición es verdadera por lo que la expresión original es falsa.

Archivo:Pensamiento algorítmico ejercicio22).jpg

Como la negación de la conclusión en la suposición es verdadera entonces la conclusión de la expresión original es falsa. Por lo tanto (P(x) → Q(y)) ^ (Q(y) → R(z)) → (P(z) → Q(z)) no es válido.