Cuantificadores, los predicados, lógica de equivalencia

Question

Me pregunta si $(\exists x) (P(x) \rightarrow Q(x))$ $\forall x P(x) \rightarrow \exists xQ(x)$ son lógicamente equivalentes.

Yo no pienso que ellos son, pero ¿cómo puedo demostrarlo?

Se supone que voy a utilizar, ya sea de la prueba directa, contrapositivo o contradicción de las pruebas? O dar una interpretación?

Answer 1

Si usted puede probar que $(1)$ una declaración implica a los otros Y $(2)$ viceversa, entonces usted probar la lógica de la equivalencia. Es decir, nos muestran:

$(\exists x)(P(x) \rightarrow Q(x)) \implies (\forall x P(x) \rightarrow \exists x Q(x))\tag{1}$

$\forall x P(x) \rightarrow \exists x Q(x) \implies (\exists x)(P(x) \rightarrow Q(x))\tag{2}$

$(1)\to (2):$
Supongamos $(\exists x)(P(x)\to Q(x))$.
A continuación, $P(x_0)\to Q(x_0)$ algunos $x_0$.
Ahora supongamos $\forall xP(x)$. Si no hay $x$, entonces la implicación (2) es verdadera.
Otra cosa, entonces claramente hay algo de $x_0$ tal que $P(x_0)$.
Por lo tanto, $Q(x_0)$$\exists xQ(x)$.
Así que nos han mostrado $\forall xP(x)\to \exists xQ(x)$.

$(2)\to (1):$
Ahora suponga $\forall xP(x)\to \exists xQ(x)$.
(A) $\forall xP(x)$ o (b) $\lnot \forall x P(x) \equiv \exists x\neg P(x)$.
En el caso de (a), $\exists xQ(x)$, $Q(x_0)$ algunos $x_0$$P(x_0)\to Q(x_0)$.
En el caso de (b), $\neg P(x_1)$ algunos $x_1$
así que, a continuación,$P(x_1)\to Q(x_1)$.
Así, en (a), (b), $(\exists x)(P(x)\to Q(x))$.

• Es decir, han demostrado que la $(1) \iff (2)$. Ya sea enunciado es verdadero si y sólo si el otro es verdadero. I. e. $(1) \equiv (2)$.

---

Para desmentir la lógica de la equivalencia, es suficiente para encontrar un ejemplo contrario: encontrar cualquier interpretación en la que una de las afirmaciones es verdadera, pero la otra es falsa.

---

Tenga en cuenta que $$\forall x P(x) \rightarrow \exists xQ(x) \equiv \lnot\forall x P(x) \lor \exists xQ(x)$$ is false if and only if $\forall xP(x)$ is true, but $\exists x Q(x)$ is false. Put differently, the statement is true whenever $\forall xP(x)$ is false, and/or it is true whenever $\exists Q(x)$ es cierto.

Answer 2

Aquí está una tarde de pruebas alternativas (en un poco diferente de la notación de la que estoy más familiarizado con): \begin{align} & \langle \forall x :: P(x) \rangle \Rightarrow \langle \exists x :: Q(x) \rangle \\ \equiv & \;\;\;\;\;\text{"expand %#%#% in the simplest way possible"} \\ & \lnot \langle \forall x :: P(x) \rangle \lor \langle \exists x :: Q(x) \rangle \\ \equiv & \;\;\;\;\;\text{"simplify: DeMorgan on left hand side"} \\ & \langle \exists x :: \lnot P(x) \rangle \lor \langle \exists x :: Q(x) \rangle \\ \equiv & \;\;\;\;\;\text{"simplify: %#%#% distributes over %#%#% (since both are disjunctions)"} \\ & \langle \exists x :: \lnot P(x) \lor Q(x) \rangle \\ \equiv & \;\;\;\;\;\text{"reintroduce %#%#%"} \\ & \langle \exists x :: P(x) \Rightarrow Q(x) \rangle \\ \end{align} Así que estas expresiones son equivalentes.

Answer 3

Sugerencia: Utilice esta hecho de que $P\to Q$ es lógicamente equivalente a $\sim P\vee Q$. Más sobre sabemos que $\sim (\exists x,~ P(x))\equiv \forall x, \sim P(x)$ y viceversa.

Answer 4

Suponga $(\exists x)(P(x)\to Q(x))$. Por lo tanto $P(x_0)\to Q(x_0)$ algunos $x_0$. Suponga $\forall xP(x)$. A continuación, especialmente a $P(x_0)$. Por lo tanto $Q(x_0)$$\exists xQ(x)$. Así, hemos mostrado $\forall xP(x)\to \exists xQ(x)$.

Suponga $\forall xP(x)\to \exists xQ(x)$. Cualquiera de las $\forall xP(x)$ o $\exists x\neg P(x)$. En el primer caso $\exists xQ(x)$, es decir, $Q(x_0)$ algunos $x_0$ y, a continuación,$P(x_0)\to Q(x_0)$. En el segundo caso $\neg P(x_1)$ algunos $x_1$ y, a continuación,$P(x_1)\to Q(x_1)$. Así, en ambos casos $(\exists x)(P(x)\to Q(x))$.

Answer 5

Podemos pensar acerca de $P$ $Q$ como subconjuntos del universo (un arbitrario universo), que vamos a denominar como $U$. Esto es un poco de un análisis semántico de las oraciones, que puede ser esclarecedor.

La primera frase dice que cualquiera de las $P\neq U$ o $P\cap Q\neq\varnothing$.

La segunda dice que si $P=U$$Q\neq\varnothing$.

---

Ahora vamos a analizar si es o no estas dos frases son equivalentes o no.

Si $P=U$ $Q\neq\varnothing$ (la segunda frase tiene), entonces claramente $P\cap Q\neq\varnothing$, por lo que la primera frase contiene. Por otro lado, si $P\neq U$, la segunda frase es automático, y tenemos algunos $x$ tal que $P(x)$ es falso, y por lo que la primera frase también es cierto.

Los mismos argumentos también nos dicen que si la primera frase contiene, a continuación, la segunda sostiene así, en un caso vacuously y en otro caso menos vacuously.