Resolución del valor de verdad de enunciados del cálculo de predicados (sólo la aproximación)

Question

¿Cuál o cuáles de las siguientes afirmaciones del cálculo de predicados son válidas?

1. $$\forall x, P(x)\lor \forall x,Q(x) \Rightarrow \forall x, (P(x)\lor Q(x))$$

2. $$\exists x, P(x)\land \exists x, Q(x) \Rightarrow \exists x, (P(x)\land Q(x)) $$

3. $$\exists x, P(x)\land \exists x, Q(x) \Rightarrow \forall x, P(x)\lor \forall x,Q(x)$$

4. $$\exists x, (P(x)\lor Q(x)) \Rightarrow \forall x, P(x)\lor \exists x,Q(x)$$

¿Cuál es el enfoque para resolver estas cuestiones? He aprendido que una forma de resolver estas cuestiones es considerar una $P(x)$ decir " todos los números son impar " y $Q(x)$ decir " todos los números son pares ", y luego razonar con cada opción para ver cuál es la verdadera.
Como soy estudiante de primer año de CS me ha costado mucho entender esto, así que ¿alguien me lo puede explicar de forma sencilla?
Además, ¿hay alguna forma mecánica (algebraica) de resolverlos utilizando reglas de lógica proposicional?

Answer 1

El planteamiento para resolver este tipo de problemas consiste en formular una prueba que demuestre que son ciertos o encontrar un contraejemplo. Tenga en cuenta que para falsedad, basta con un contraejemplo, pero para la verdad, un ejemplo no dice nada. no dice nada.

La primera afirmación es válida. Para saber por qué, digamos que P(x) representa para "x es rojo" y Q(x) para "x es amarillo". $\forall xP(x) \lor \forall xQ(x)$ traduciría al español que "todos los objetos son rojos o todos los objetos son amarillos". $\forall x(P(x) \lor Q(x))$ afirmaría que "todos los objetos son rojos o amarillos". Es obvio que esto último se deduce de la primera.

Una prueba construida mediante deducción natural tendría el aspecto siguiente siguiente:

1. $\forall xP(x) \lor \forall xQ(x)\quad\mathrm{Premise}$
2. $a\quad\mathrm{Variable}$
3. $\forall xP(x)\quad\mathrm{Assumption}$
4. $P(a)\quad\forall x e3$
5. $P(a) \lor Q(a)\quad\lor i_1 4$
6. $\forall xQ(x)\quad\mathrm{Assumption}$
7. $Q(a)\quad\forall x e6$
8. $P(a) \lor Q(a)\quad\lor i_2 7$
9. $P(a) \lor Q(a)\quad\lor e 1,3-5,6-8$
10. $\forall x(P(x) \lor Q(x))\quad\forall x i 2-9$

Puesto que podemos transformar la afirmación de la premisa en la deseada conclusión deseada, es válida.

La segunda afirmación no es válida. Consideremos $P(x): x = 1$ y $Q(x): x = 2$ entonces $\exists P(x) \land \exists Q(x)$ es cierto porque se puede insertar los valores $P(1) \land Q(2)$ . Pero $\exists x(P(x) \land Q(x))$ es falsa porque ningún $x$ puede ser a la vez igual a 1 y a 2 en el mismo tiempo. Por lo tanto, toda la afirmación es inválida.

Puede utilizar las mismas definiciones para $P(x)$ y $Q(x)$ para demostrar que la tercera afirmación no es válida. Si el dominio son todos los números entonces es que $\exists P(x) \land \exists Q(x)$ es cierto, pero tampoco $\forall x P(x)$ ni $\forall x Q(x)$ son verdaderas, por lo tanto $\forall x P(x) \lor \forall x Q(x)$ es falsa y la afirmación es inválida.

Para la cuarta declaración, establezca $P(x): x = 1$ y $Q(x): false$ para que sea falso para cada valor de $x$ . Entonces $\exists x(P(x) \lor Q(x))$ es cierto para $x = 1$ pero $\forall x P(x) \lor \exists x Q(x)$ no es cierto para cualquier valor de $x$ . De ello se deduce que la declaración no es válida