1 votos

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

¿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?

1voto

DanielV Puntos 11606

$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.

  1. $(\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.

  1. $ \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.

  1. $ \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).

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X