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

Remark 11.1.

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

Definition 11.2.

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

•

Si $\varphi^{u}=1$

Definition 11.3.

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

•

satisfacible si $\exists u$ valoracion tal que $\varphi^{u}=1$ .
•

insatisfacible si no es satisfacible.
•

tautologia si $\forall u$ valoracion se tiene que $\varphi^{u}=1$
•

contradiccion si $\forall u$ valoracion se tiene que $\varphi^{u}=0$
•

contingencia si no es tautologia ni contradiccion

Remark 11.4.

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.

Example 11.5.

Clasifica la formula

\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 $w(p)=0\Rightarrow(p\rightarrow\neg(q\wedge r))^{w}=1$ .

Voy a intentar que la segunda parte sea falsa.

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

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

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

Example 11.6.

Demuestra que la siguiente formula es una tautologia

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

Lo demostraremos utilizando una tabla de verdad.

p	q	r	$p\rightarrow q$	$q\rightarrow r$	$(p\rightarrow q)\wedge(q\rightarrow r)$	$p\rightarrow r$	$\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 $\varphi$ . Por tanto, $\varphi$ es una tautologia.

Example 11.7.

Demuestra que la siguiente formula es una contradiccion

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

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

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

•

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

Luego $\varphi$ es una contradiccion.

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

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}

\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, $\varphi$ es contradiccion.