11 Modelos y contraejemplos. Clasificacion de formulas

Observación.

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

Definición 11.1.

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

  •  

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

Definición 11.2.

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

  •  

    satisfacible si u\displaystyle\exists u valoracion tal que φu=1\displaystyle\varphi^{u}=1.

  •  

    insatisfacible si no es satisfacible.

  •  

    tautologia si u\displaystyle\forall u valoracion se tiene que φu=1\displaystyle\varphi^{u}=1

  •  

    contradiccion si u\displaystyle\forall u valoracion se tiene que φu=0\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

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

Voy a intentar que la segunda parte sea falsa.

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

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

φ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

φ=(pq)(qr)(pr)\displaystyle\varphi=(p\rightarrow q)\wedge(q\rightarrow r)\rightarrow(p% \rightarrow r)

Lo demostraremos utilizando una tabla de verdad.

p q r pq\displaystyle p\rightarrow q qr\displaystyle q\rightarrow r (pq)(qr)\displaystyle(p\rightarrow q)\wedge(q\rightarrow r) pr\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

φ=(pq)(rs)pr(¬q¬s)\displaystyle\varphi=(p\rightarrow q)\wedge(r\rightarrow s)\wedge p\wedge r% \wedge(\neg q\vee\neg s)

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

(pq)rp(qr)pqr\displaystyle(p\wedge q)\wedge r\equiv p\wedge(q\wedge r)\equiv p\wedge q\wedge r.

  •  

    Caso 1: Si p=0φ=0\displaystyle p=0\Rightarrow\varphi=0 (son 8 valoraciones).

  •  

    Caso 2: p=1\displaystyle p=1.

    • Caso 2.1: r=0φ=0\displaystyle r=0\Rightarrow\varphi=0 (son 4 valoraciones)

    • Caso 2.2 : r=1\displaystyle r=1

      Hacer tabla de verdad con q\displaystyle q y s\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 u\displaystyle u modelo de φ\displaystyle\varphi. Como es una conjuncion de varias formulas, tenemos que

u{pq=1(a)rs=1(b)p=1(c)r=1(d)¬q¬s=1(e)\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}
(a)+(c)q=1¬q=0(b)+(d)s=1¬s=0}¬q¬s=0 Contradicion con (e)\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.