25 Consecuencia logica ‣ Parte VI Semantica de la logica de predicados ‣ Lógica‣ Parte VI Semantica de la logica de predicados ‣ Lógica

Definición 25.1.

Sean $\displaystyle\phi=\{\varphi_{1},\varphi_{2},\ldots,\varphi_{n}\}$ un conjunto de formulas y $\displaystyle\psi$ otra formula. Decimos que $\displaystyle\psi$ es consecuencia logica de $\displaystyle\phi$ si para toda interpretacion $\displaystyle(D,I)$ y para toda asignacion $\displaystyle A$ se cumple:

\displaystyle(\forall i\exists\{1,\ldots,n\}\varphi^{I,A}_{i}=1)\Rightarrow% \psi^{I,A}=1

Tambien decimos que $\displaystyle\phi$ implica logicamente a $\displaystyle\psi$ .

Notacion: $\displaystyle\phi\vDash\psi$

Definición 25.2.

Recordemos que un razonamiento es una formula de tipo

\displaystyle\varphi_{1}\wedge\varphi_{2}\wedge\ldots\wedge\varphi_{n}% \rightarrow\psi.

Decimos que el razonamiento anterior es correcto si es una tautologia o formula valida.

Proposición 25.1.

Sean $\displaystyle\phi=\{\varphi_{1},\ldots,\varphi_{n}\}$

Ejemplo.

Estudia si el razonamiento:

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

formalizado mediante

\displaystyle\begin{array}[]{l}\varphi_{1}=H(s)\\ \varphi_{2}=\forall x(H(x)\rightarrow M(x))\\ \hline\cr\psi=M(s)\end{array}

es correcto.

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

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

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

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

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

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

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

Ejemplo.

Estudia si el razonamiento:

\displaystyle\begin{array}[]{l}\varphi_{1}=M(s)\\ \varphi_{2}=\forall x(H(x)\rightarrow M(x))\\ \hline\cr\psi=H(s)\end{array}

es correcto.

Es incorrecto. Tengo que demostrarlo con un contraejemplo.

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

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

$\displaystyle M(x)=x$ es par

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

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

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

Otra alternativa es elegir conjuntos finitos sencillos.

\displaystyle\begin{rcases}D=\{a,b\}\\ H^{I}=\{a\}\\ M^{I}=\{a,b\}\\ s^{I}=b\end{rcases}

Esta interpretacion tambien es un contraejemplo al razonamiento.

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

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

Definición 25.3.

Sean $\displaystyle\varphi$ y $\displaystyle\psi$ dos formulas. Decimos que son equivalentes si se cumple simultaneamente

Proposición 25.2.

Sean $\displaystyle\varphi$ y $\displaystyle\psi$ dos formulas. Las siguientes dos afirmaciones son equivalentes:

$\displaystyle\varphi\equiv\psi$

Ejemplo.

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

1.

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

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

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

¿Como demuestro que $\displaystyle\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.

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

Vamos a utilizar $\displaystyle(1)$ .

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

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

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

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

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

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

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

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

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

Ejemplo.

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

b)

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

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

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

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

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

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

$\displaystyle\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 $\displaystyle\varphi_{1}\not\equiv\varphi_{2}$ . ¿Alguna implica logicamente a la otra?

$\displaystyle\psi\vDash\varphi$

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

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

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

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

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

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

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

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

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

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

$\displaystyle\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 $\displaystyle\alpha=p$ simbolo de proposicion atomica y $\displaystyle\varphi=P(x)$ predicado de aridad 1.

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

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

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