25 Consecuencia logica

Estudia si el razonamiento:

“Socrates es humano. Todo humano es mortal. Por tanto, Socrates es mortal.”

formalizado mediante

es correcto.

Como son formulas cerradas, basta con considerar interpretaciones, no hace falta considerar asignaciones.

Queremos ver que $\left\{\varphi_{1},\varphi_{2}\right\}\vDash\psi$ o lo que es lo mismo, $\varphi_{1}\wedge\varphi_{2}\rightarrow\psi$ es una tautologia.

Sea $(D,I)$ una interpretacion tal que $\varphi_{1}=1$ y $\varphi_{2}=1$.

La condicion de que $\varphi^{I}_{1}=1$ es que $(H(s))^{I}=1$.

$s^{I}\in H^{I}\subseteq D$ si la formula es verdadera. Entonces tengo que $s^{I}\in H^{I}$.

La condicion de $\varphi^{I}_{2}=1$ es $\forall x(H(x)\rightarrow M(x))^{I}=1$. Esto es lo mismo que decir que $H^{I}\subseteq M^{I}$.

Uniendo $s^{I}\in H^{I}$ y que $H^{I}\subseteq M^{I}$ tengo $s^{I}\in M^{I}\Rightarrow(M(s))^{I}=1$.

Estudia si el razonamiento:

es correcto.

Es incorrecto. Tengo que demostrarlo con un contraejemplo.

Por ejemplo, $D=\mathbb{N}$.

$H(x)=x$ es multiplo de 4

$M(x)=x$ es par

Mas formal: $H^{I}=\left\{x\mid x\text{ es multiplo de 4}\right\}$ y $M^{I}=\left\{x\mid x\text{ es multiplo de }2\right\}$.

$\varphi^{I}_{2}=1$ porque si se cumple que un elemento es multiplo de 4 entonces tambien es multiplo de $2$.

$S^{I}=6$. Con esta interpretacion $M(s)^{I}=1$ porque $2|6$ pero $H(s)^{I}=0$ porque $4\nmid 6$.

Otra alternativa es elegir conjuntos finitos sencillos.

Esta interpretacion tambien es un contraejemplo al razonamiento.

$\varphi^{I}_{1}=1$ porque $s^{I}\in M^{I}$

$\varphi^{I}_{2}=1$ porque $H^{I}\subseteq M^{I}$ $\psi^{I}=0$ porque $S^{I}\not\in H^{I}$

Sean $\varphi$ y $\psi$ formulas cualesquiera y $\alpha$ una formula donde no aparece libre la variable $x$.

1. 1.
   ​

   $\neg\forall x\varphi\equiv\exists x\neg\varphi$

   Vamos a ver que $\varphi_{1}\vDash\varphi_{2}$.

   Sean $(D,I)$ interpretacion y $A$ asignacion tales que $(\neg\forall x\varphi)^{I,A}=1\Rightarrow(\forall x\varphi)^{I,A}=0\Rightarrow\varphi^{I,A[x/d]}=0$ para algun $d\in D\Rightarrow(\neg\varphi)^{I,A[x/d]}=1$ para algun $d\in D\Rightarrow(\exists x\neg\varphi)^{I,A}=1$.

   ¿Como demuestro que $\varphi_{2}\vDash\varphi_{1}$?

   Son los reciprocos del argumento anterior. En realidad, se puede escribir la demostracion como una cadena de dobles implicaciones.

2. 2.
   ​

   $\neg\exists x\varphi\equiv\forall x\neg\varphi$

   Vamos a utilizar $(1)$.

   $\neg\exists x\varphi\equiv\neg\exists x\neg\neg\varphi\overset{(1)}{\equiv}\neg\neg\forall x\neg\varphi\equiv\forall x\neg\varphi$.

3. 3.
   ​

   $\forall x(\varphi\wedge\psi)\equiv\forall x\varphi\wedge\forall x\psi$

   Sean $(D,I)$ una interpretacion y $A$ una asignacion.

   $\forall x(\varphi\wedge\psi)^{I,A}=1\Rightarrow$ para todos los valores $d\in D(\varphi\wedge\psi)^{I,A[x/d]}=1\iff\varphi^{I,A[x/d]}=1\text{ y }\psi^{I,A[x/d]}\iff(\forall x\varphi)^{I,A[x/d]}\text{ y }(\forall x\psi)^{I,A[x/d]}=1\iff((\forall x\varphi)\wedge(\forall x\psi))^{I,A}=1$

4. 4.
   ​

   $\exists x(\varphi\vee\psi)\equiv\exists x\varphi\vee\exists x\psi$

   $\exists x(\varphi\vee\psi)\equiv\neg\neg\exists x(\varphi\vee\psi)\equiv\neg\forall x\neg(\varphi\vee\psi)\equiv\neg\forall x(\neg\varphi\wedge\neg\psi)\equiv\neg(\forall x\neg\varphi\wedge\forall x\neg\psi)\equiv\neg\forall x\neg\varphi\vee\neg\forall x\neg\psi\equiv\exists x\neg\neg\varphi\vee\exists x\neg\neg\psi\equiv\exists x\varphi\vee\exists x\psi$

5. 5.
   ​

   $\forall x\varphi\wedge\alpha\equiv\forall x(\varphi\wedge\alpha)$

   Sean $(D,I)$ una interpretacion y $A$ una asignacion.

   $\forall x(\varphi\wedge\alpha)=1\iff(\varphi\wedge\alpha)^{I,A[x/d]}=1$ para todo $d\in D\iff\varphi^{I,A[x/d]}=1$ y $\psi^{I,A[x/d]}=1$ para todo $d\in D\iff\varphi^{I,A[x/d]}=1$ para todo $d\in D$ y $\alpha^{I,A}=1$ (porque $x$ no aparece libre en $\alpha$) $\iff\forall x\varphi^{I,A}=1$, $\alpha^{I,A}=1\iff(\forall x\varphi\wedge\alpha)^{I,A}=1$

Sean $\varphi$ y $\psi$ cualesquiera y $\alpha$ una formula donde no aparece libre la variable $x$. En general las siguientes formulas no son equivalentes:

1. b)
   ​

   $\forall(\varphi\vee\psi)\not\equiv\forall x\varphi\vee\forall x\psi$

   Elijo $P,Q$ dos predicados de aridad 1.

   $D=\left\{a,b\right\}$, $P^{I}=\left\{a\right\}$, $Q^{I}=\left\{b\right\}$.

   $$\begin{dcases}\forall x(P(x)\vee Q(x))=\varphi_{1}\\ \forall xP(x)\vee\forall xQ(x)=\varphi_{2}\end{dcases}$$

   $\varphi^{I}_{1}=1$ porque si $x=a$ $\underbrace{\underbrace{P(a)}_{1}\vee Q(a)}_{1}$ y si $x=b$, $\underbrace{P(b)\vee\underbrace{Q(b)}_{1}}_{1}$.

   $\varphi^{I}_{2}=0$ porque

   $$\begin{dcases}\forall xP(x)^{I}=0\text{ porque }x=b\text{ es un contraejemplo}\\ \forall xP(x)^{I}=0\text{ porque }x=a\text{ es un contraejemplo}\end{dcases}$$

   Hemos visto que $\varphi_{1}\not\equiv\varphi_{2}$. ¿Alguna implica logicamente a la otra?

   $\psi\vDash\varphi$

   Si $\varphi_{2}^{I,A}=1\Rightarrow$ o bien $(\forall xP(x))^{I,A}=1\Rightarrow\varphi^{I,A}=1$ o bien $(\forall x(Q(x)))^{I,A}=1\Rightarrow\varphi^{I,A}=1$.

2. c)
   ​

   $\exists x(P(x)\wedge Q(x))=\varphi_{1}$

   $\exists xP(x)\wedge(\exists xQ(x))=\varphi_{2}$

   $D=\left\{a,b\right\}$, $P^{I}=\left\{a\right\}$, $Q^{I}=\left\{b\right\}$

   $\varphi^{I}_{2}=1$ porque $\exists xP(x)^{I}=1$ como $x=a$ y $\exists xQ(x)^{I}=1$ con $x=b$.

   $\varphi^{I}_{1}=0$ porque si $x=a$ $\underbrace{\underbrace{P(a)}_{1}\wedge Q(a)}_{0}$ y si $x=b$ $(\underbrace{P(b)\wedge\underbrace{Q(b)}_{1}}_{0})$.

   Se que $\varphi_{1}$ porque $\varphi_{2}\not\vDash\varphi_{1}$.

   Es cierto que $\varphi_{1}\vDash\varphi_{2}$?

   Si $I$ es una interpretacion tal que $\varphi_{1}=1\Rightarrow$ Existe $d\in D$ tal que $d\in P^{I}$ y $d\in Q^{I}\Rightarrow\exists xP(x)^{I}=1$ y $\exists xQ(x)^{I}=1\Rightarrow\varphi^{I}_{2}=1$.

3. d)
   ​

   $\forall x\varphi\to\alpha\not\equiv\forall x(\varphi\to\alpha)$

   $\forall x(\varphi\to\alpha)\equiv\forall x(\neg\varphi\vee\alpha)\equiv\forall x\neg\varphi\vee\alpha\equiv\neg\exists\varphi\vee\alpha\equiv\exists x\varphi\to\alpha\not\equiv\forall x\varphi\to\alpha$.

   Justificacion de que no son equivalentes:

   Con $\alpha=p$ simbolo de proposicion atomica y $\varphi=P(x)$ predicado de aridad 1.

   $\exists P(x)\to p\not\equiv\forall xP(x)\to p$

   $D=\left\{a,b\right\}$, $P^{I}=\left\{a\right\}$ y $p^{I}=0$

   $\underbrace{\underbrace{\exists xP(x)}_{1}\to\underbrace{p}_{0}}_{0}\quad\underbrace{\underbrace{\forall xP(x)}_{0}\to\underbrace{p}_{0}}_{1}$