11 Modelos y contraejemplos. Clasificacion de formulas ‣ Parte III Semantica de la logica proposicional ‣ Lógica‣ Parte III Semantica de la logica proposicional ‣ Lógica

Observación.

Cuando hablemos de una formula $\displaystyle\varphi$ y su valor de verdad bajo una valoracion $\displaystyle u$ , supondremos siempre que los simbolos de proposicion atomica que aparecen en $\displaystyle\varphi$ pertenecen al dominio de $\displaystyle u$ .

Definición 11.1.

Sean $\displaystyle\varphi$ una formula y $\displaystyle u$ una valoracion.

Si $\displaystyle\varphi^{u}=1$

Definición 11.2.

Sea $\displaystyle\varphi$ una formula. Decimos que $\displaystyle\varphi$ es:

satisfacible si $\displaystyle\exists u$ valoracion tal que $\displaystyle\varphi^{u}=1$ .
insatisfacible si no es satisfacible.
tautologia si $\displaystyle\forall u$ valoracion se tiene que $\displaystyle\varphi^{u}=1$
contradiccion si $\displaystyle\forall u$ valoracion se tiene que $\displaystyle\varphi^{u}=0$
contingencia si no es tautologia ni contradiccion

Observación.

Esta clasificacion puede resumirse en la tabla

Satisfacible	Tautologia o contingencia
Insatisfacible	Contradiccion

Cuando hablemos de “clasificar una formula” nos referiremos a decidir si es tautologia, contingencia o contradiccion.

Ejemplo.

Clasifica la formula

\displaystyle\varphi=(p\rightarrow\neg(q\wedge r))\leftrightarrow(p\vee\neg q% \rightarrow\neg r)

Ya hemos encontrado 2 modelos. Sabemos que es satisfacible.

Voy a buscar un contraejemplo. w para conseguir esto

Si $\displaystyle w(p)=0\Rightarrow(p\rightarrow\neg(q\wedge r))^{w}=1$ .

Voy a intentar que la segunda parte sea falsa.

$\displaystyle w(q)=0\Rightarrow(\neg q)^{w}=1\Rightarrow(\neg q)^{w}=1$ . $\displaystyle(p\vee\neg q)^{w}=1$ .

Si $\displaystyle w(r)=1\Rightarrow(\neg r)^{w}=0\Rightarrow(p\vee\neg q% \rightarrow\neg r)^{w}=0$ .

$\displaystyle\varphi^{w}=0$ . Luego w es un contraejemplo de $\displaystyle\varphi$ , por tanto $\displaystyle\varphi$ es una contingencia.

Ejemplo.

Demuestra que la siguiente formula es una tautologia

\displaystyle\varphi=(p\rightarrow q)\wedge(q\rightarrow r)\rightarrow(p% \rightarrow r)

Lo demostraremos utilizando una tabla de verdad.

p	q	r	$\displaystyle p\rightarrow q$	$\displaystyle q\rightarrow r$	$\displaystyle(p\rightarrow q)\wedge(q\rightarrow r)$	$\displaystyle p\rightarrow r$	$\displaystyle\varphi$
0	0	0	1	1	1	1	1
0	0	1	1	1	1	1	1
0	1	0	1	0	0	1	1
0	1	1	1	1	1	1	1
1	0	0	0	1	0	0	1
1	0	1	0	1	0	1	1
1	1	0	1	0	0	0	1
1	1	1	1	1	1	1	1

He visto que las 8 valoraciones posibles son modelos de $\displaystyle\varphi$ . Por tanto, $\displaystyle\varphi$ es una tautologia.

Ejemplo.

Demuestra que la siguiente formula es una contradiccion

\displaystyle\varphi=(p\rightarrow q)\wedge(r\rightarrow s)\wedge p\wedge r% \wedge(\neg q\vee\neg s)

$\displaystyle(p\wedge q)\wedge r$ y $\displaystyle p(q\wedge r)$ son verdaderas si y solo si $\displaystyle p=q=r=1$ . Son formulas distintas sintacticamente pero son equivalentes semanticamente.

$\displaystyle(p\wedge q)\wedge r\equiv p\wedge(q\wedge r)\equiv p\wedge q\wedge r$ .

Caso 1: Si $\displaystyle p=0\Rightarrow\varphi=0$ (son 8 valoraciones).
Caso 2: $\displaystyle p=1$ .
- •
  
  Caso 2.1: $\displaystyle r=0\Rightarrow\varphi=0$ (son 4 valoraciones)
- •
  
  Caso 2.2 : $\displaystyle r=1$
  
  Hacer tabla de verdad con $\displaystyle q$ y $\displaystyle s$ (4 filas). Salen todas falsas.

Luego $\displaystyle\varphi$ es una contradiccion.

Alternativa: por reduccion al absurdo. Supongo que $\displaystyle\varphi$ no es contradiccion $\displaystyle\Rightarrow$ existe $\displaystyle u$ modelo de $\displaystyle\varphi$ . Como es una conjuncion de varias formulas, tenemos que

\displaystyle u\begin{dcases}p\rightarrow q=1(a)\\ r\rightarrow s=1(b)\\ p=1(c)\\ r=1(d)\\ \neg q\vee\neg s=1(e)\end{dcases}

\displaystyle\begin{rcases}(a)+(c)\Rightarrow q=1\Rightarrow\neg q=0\\ (b)+(d)\Rightarrow s=1\Rightarrow\neg s=0\end{rcases}\Rightarrow\neg q\vee\neg s% =0\text{ Contradicion con (e)}\Rightarrow

Por tanto, $\displaystyle\varphi$ es contradiccion.