¿Fórmulas válidas y bien formadas en el cálculo de predicados?

Question

¿Cuál de las siguientes fórmulas bien formadas en el cálculo de predicados NO es válida?

1. $(\forall x~p(x) \implies \forall x~q(x)) \implies( \exists x~\lnot p(x) \lor \forall x~q(x))$
2. $(\exists x~p(x) \lor \exists x~q(x)) \implies \exists x~(p(x) \lor q(x))$
3. $\exists x~(p(x) \land q(x)) \implies( \exists x~p(x) \land \exists x~q(x))$
4. $\forall x~(p(x) \lor q(x)) \implies( \forall x~p(x) \lor \forall x~q(x))$

---

Mi intento :

Dejemos que $p(x)=\text{x is even}$ y $q(x)=\text{x is odd}$ en el conjunto de números naturales. Entonces :

1. Cierto, y lo contrario también es cierto.
2. Cierto, y lo contrario también es cierto.
3. Cierto, y lo contrario no es cierto.
4. Falso, pero lo contrario es cierto.

¿Puede explicarlo de manera formal, por favor?

Answer 1

$P$ y $Q$ son relaciones unarias, por lo que se puede modelar cada una de ellas como conjuntos $P_s$ y $Q_s$ , donde $P(x)$ si $x \in P_s$ y $Q(x)$ si $x \in Q_s$ . Sea $W$ ser todos los objetos del universo.

Así que traduce cada afirmación en conjuntos:

1. $(\forall x~p(x) \implies \forall x~q(x)) \implies( \exists x~\lnot p(x) \lor \forall x~q(x))$

Convertir el $\lor$ a $\implies$ lo consigues:

$$(\forall x~p(x) \implies \forall x~q(x)) \implies( \lnot \exists x~\lnot p(x) \implies \forall x~q(x))$$ $$(\forall x~p(x) \implies \forall x~q(x)) \implies( \forall x~p(x) \implies \forall x~q(x))$$

Por tanto, la fórmula es válida si, para cualquier modelo en el que $(\forall x~p(x) \implies \forall x~q(x))$ sostiene, que $(\forall x~p(x) \implies \forall x~q(x))$ también tiene.

2. $(\exists x~p(x) \lor \exists x~q(x)) \implies \exists x~(p(x) \lor q(x))$

Si $P_s$ no está vacío o $Q_s$ no está vacío, entonces $P_s \cup Q_s$ no está vacío. Es bastante fácil establecer que esto es válido para cualquier modelo.

3. $\exists x~(p(x) \land q(x)) \implies( \exists x~p(x) \land \exists x~q(x))$

Si $P_s \cap Q_s$ es no vacía, entonces $P_s$ es no vacía y $Q_s$ es no vacía. Cualquier cosa modelará esto.

4. $\forall x~(p(x) \lor q(x)) \implies( \forall x~p(x) \lor \forall x~q(x))$

Si $P_s \cup Q_s = W$ entonces $P_s = W$ o $Q_s = W$ . Es evidente que esto no es cierto para cualquier elección de $P_s$ y $Q_s$ . De hecho las únicas veces que será cierto es:

• cuando $P_s = W$ , lo que significa $P(x) = \text{True}$ o
• cuando $Q_s = W$ , lo que significa $Q(x) = \text{True}$ o
• cuando $P_s \cap Q_s \ne W$ es decir, cuando hay un valor de $x$ donde ambos $P(x)$ y $Q(x)$ no aguantan.

De lo contrario, la elección de $P()$ y $Q()$ no modelará (4).