Ejemplos de lógica proposicional

En el artículo veremos varias fórmulas y sus posibles asignaciones con ayuda de la tabla de verdad.

Primer ejemplo

Intentaremos averiguar cuándo es verdadera esta fórmula: ϕ = (p ∧ q) ∨ ¬q. Escribimos en la tabla las variables proposicionales p y q:

$$\begin{array}{cc}p& q\\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

A continuación añadimos a la tabla la primera parte de la fórmula, (p ∧ q), la negación ¬q y después la fórmula entera:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Ahora calculamos los valores de la tercera columna, que es una conjunción sencilla, y también los de la negación; ahí solo ponemos los valores contrarios a los de la segunda columna:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1& 1& 0\\ 1& 0& 0& 1\\ 0& 1& 0& 0\\ 0& 0& 0& 1\end{array}$$

Por último calculamos los valores de la última columna. Es la fórmula entera. Según nuestra tabla, calculamos por tanto la disyunción «entre la tercera y la cuarta columna». Resultado:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1& 1& 0& 1\\ 1& 0& 0& 1& 1\\ 0& 1& 0& 0& 0\\ 0& 0& 0& 1& 1\end{array}$$

Segundo ejemplo

Mismo enunciado, otra fórmula: ϕ = (p ∧ ¬q) ⇔ (¬p ⇒ q). Vemos que en la fórmula aparecen las variables proposicionales p y q y sus negaciones. Así que primero creamos una tabla con los dos símbolos y sus negaciones:

$$\begin{array}{cccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q\\ 1& 1& 0& 0\\ 1& 0& 0& 1\\ 0& 1& 1& 0\\ 0& 0& 1& 1\end{array}$$

A continuación añadimos las fórmulas p ∧ ¬q y ¬p ⇒ q, que ya sabemos evaluar fácilmente, porque en la tabla tenemos tanto las asignaciones de cada proposición como las de sus negaciones. La tabla queda así:

$$\begin{array}{cccccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q& (p\wedge \mathrm{\neg }q)& (\mathrm{\neg }p\Rightarrow q)\\ 1& 1& 0& 0& 0& 1\\ 1& 0& 0& 1& 1& 1\\ 0& 1& 1& 0& 0& 1\\ 0& 0& 1& 1& 0& 0\end{array}$$

Por último, nos falta evaluar la fórmula entera, que es la equivalencia entre las dos últimas columnas:

$$\begin{array}{ccccccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q& (p\wedge \mathrm{\neg }q)& (\mathrm{\neg }p\Rightarrow q)& \varphi \\ 1& 1& 0& 0& 0& 1& 0\\ 1& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 0& 0& 1& 0\\ 0& 0& 1& 1& 0& 0& 1\end{array}$$

Tercer ejemplo

El tercer ejemplo será algo más complicado: probaremos con tres variables proposicionales, con lo que el cálculo de la tabla se complica. La fórmula será así: ϕ = (¬(p ⇒ q)) ∧ (r ⇔ (¬p ∨ q)).

Como tenemos tres variables proposicionales, el número total de asignaciones será ocho:

$$\begin{array}{ccc}p& q& r\\ 1& 1& 1\\ 1& 1& 0\\ 1& 0& 1\\ 1& 0& 0\\ 0& 1& 1\\ 0& 1& 0\\ 0& 0& 1\\ 0& 0& 0\end{array}$$

A partir de aquí procedemos igual que en el caso anterior: evaluamos cada columna en las ocho filas. La tabla completa queda así:

$$\begin{array}{ccccccccc}p& q& r& \mathrm{\neg }p& (p\Rightarrow q)& (\mathrm{\neg }p\vee q)& \mathrm{\neg }(p\Rightarrow q)& (r\iff (\mathrm{\neg }p\vee q))& \varphi \\ 1& 1& 1& 0& 1& 1& 0& 1& 0\\ 1& 1& 0& 0& 1& 1& 0& 0& 0\\ 1& 0& 1& 0& 0& 0& 1& 0& 0\\ 1& 0& 0& 0& 0& 0& 1& 1& 1\\ 0& 1& 1& 1& 1& 1& 0& 1& 0\\ 0& 1& 0& 1& 1& 1& 0& 0& 0\\ 0& 0& 1& 1& 1& 1& 0& 1& 0\\ 0& 0& 0& 1& 1& 1& 0& 0& 0\end{array}$$

Cuarto ejemplo

Este ejemplo no lo plantearemos como una fórmula normal, sino como un problema. Tres amigos que quieren ir a una fiesta salvaje, donde habrá modelos en topless repartiendo aperitivos, no se caen del todo bien y se ponen condiciones para ir a la fiesta. Se llaman Martín, Jaime y Pedro. Las reglas son las siguientes:

1. Si va Martín, entonces va también Jaime.
2. A la fiesta viene Pedro o, si viene Martín, entonces Jaime no viene.
3. Pedro viene si y solo si no viene Martín o no viene Jaime.

La pregunta es: ¿pueden ir todos a la fiesta? Si no, ¿quién puede ir a la fiesta sin romper ninguna regla?

Primero tenemos que reescribir las proposiciones anteriores con variables proposicionales y fórmulas. Así que designemos las variables proposicionales M, J y P (Martín, Jaime, Pedro), y siempre significarán una proposición del tipo «Martín irá a la fiesta». La primera regla la podríamos reescribir así: M ⇒ J, es decir, «si M, entonces J», o sea, «si Martín va a la fiesta, entonces Jaime va a la fiesta».

La segunda regla la reescribiríamos así. La regla empieza con la oración «A la fiesta viene Pedro o…», así que evidentemente necesitaremos una disyunción. Por ahora escribimos esto: P ∨ … La siguiente parte de la oración dice: «si viene Martín, entonces Jaime no viene». Es una implicación, y en el lado derecho todavía tenemos que usar una negación. «Jaime no viene» = ¬J. La implicación entera quedaría así: M ⇒ ¬J. Se la unimos a la disyunción anterior: P ∨ (M ⇒ ¬J).

La tercera regla la reescribimos así: empezamos con «Pedro viene si y solo si». Eso significa una equivalencia: P ⇔ … Después tenemos «no viene Martín o no viene Jaime», que reescribimos así: ¬M ∨ ¬J. Lo juntamos todo: (P ⇔ (¬M ∨ ¬J)).

Ahora metemos todas las fórmulas en la tabla y calculamos los valores:

$$\begin{array}{cccccc}M& J& P& (M\Rightarrow J)& (P\vee (M\Rightarrow \mathrm{\neg }J))& (P\iff (\mathrm{\neg }M\vee \mathrm{\neg }J))\\ 1& 1& 1& 1& 1& 0\\ 1& 1& 0& 1& 0& 1\\ 1& 0& 1& 0& 1& 1\\ 1& 0& 0& 0& 1& 0\\ 0& 1& 1& 1& 1& 1\\ 0& 1& 0& 1& 1& 0\\ 0& 0& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0\end{array}$$

La pregunta era si pueden ir los tres chicos a la fiesta salvaje. La respuesta la encontramos en la primera fila. Esa fila corresponde al caso en que van todos los chicos, lo que se indica con tres unos en las tres primeras columnas. ¿Se cumplen todas las condiciones? La primera sí (cuarta columna), la segunda también (quinta columna), pero la última no (última columna), ahí hay un cero. Significa que si van los tres, no se cumplirá la tercera condición.

Buscamos, por tanto, las filas en las que en las posiciones que representan las condiciones (es decir, las tres últimas columnas) hay solo unos. Un uno significa que la condición se cumple. Vemos que eso ocurre en dos casos: cuando van Jaime y Pedro, pero Martín no, y cuando va solo Pedro.

También puedes calcularlo añadiendo a la tabla una fórmula ϕ que sea la conjunción de las tres condiciones. Quedaría así: ϕ = ((M ⇒ J) ∧ (P ∨ (M ⇒ ¬J)) ∧ (P ⇔ (¬M ∨ ¬J))). Eso representa lo que queremos: que se cumplan todas las fórmulas (todas las condiciones). La tabla quedaría así:

$$\begin{array}{ccccccc}M& J& P& (M\Rightarrow J)& (P\vee (M\Rightarrow \mathrm{\neg }J))& (P\iff (\mathrm{\neg }M\vee \mathrm{\neg }J))& \varphi \\ 1& 1& 1& 1& 1& 0& 0\\ 1& 1& 0& 1& 0& 1& 0\\ 1& 0& 1& 0& 1& 1& 0\\ 1& 0& 0& 0& 1& 0& 0\\ 0& 1& 1& 1& 1& 1& 1\\ 0& 1& 0& 1& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0& 0\end{array}$$

Algunos ejemplos más del método de la tabla de verdad

Como he escrito un programa que sabe construir automáticamente la tabla entera a partir de una fórmula dada, tengo que aprovecharlo como es debido, y por eso siguen todavía unas cuantas fórmulas resueltas:

Fórmula: ((a ∧ ¬b) ∨ (b ∧ (b ⇒ a))). Tabla:

$$\begin{array}{ccccc}a& b& (a\wedge \mathrm{\neg }b)& (b\wedge (b\Rightarrow a))& ((a\wedge \mathrm{\neg }b)\vee (b\wedge (b\Rightarrow a)))\\ 1& 1& 0& 1& 1\\ 1& 0& 1& 0& 1\\ 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0\end{array}$$

Fórmula: (a ∨ ¬a) ⇔ (b ∧ ¬b). Tabla:

$$\begin{array}{ccccc}a& b& (a\vee \mathrm{\neg }a)& (b\wedge \mathrm{\neg }b)& ((a\vee \mathrm{\neg }a)\iff (b\wedge \mathrm{\neg }b))\\ 1& 1& 1& 0& 0\\ 1& 0& 1& 0& 0\\ 0& 1& 1& 0& 0\\ 0& 0& 1& 0& 0\end{array}$$

Fórmula: ¬(a ∨ b) ⇔ (¬b ∧ ¬a). Tabla:

$$\begin{array}{ccccc}a& b& \mathrm{\neg }(a\vee b)& (\mathrm{\neg }b\wedge \mathrm{\neg }a)& (\mathrm{\neg }(a\vee b)\iff (\mathrm{\neg }b\wedge \mathrm{\neg }a))\\ 1& 1& 0& 0& 1\\ 1& 0& 0& 0& 1\\ 0& 1& 0& 0& 1\\ 0& 0& 1& 1& 1\end{array}$$

Fórmula: ϕ = (¬p ⇔ (q ∧ r)) ⇒ (p ∨ ¬(p ∧ q)). Tabla:

$$\begin{array}{cccccccc}p& q& r& (q\wedge r)& \mathrm{\neg }(p\wedge q)& (\mathrm{\neg }p\iff (q\wedge r))& (p\vee \mathrm{\neg }(p\wedge q))& \varphi \\ 1& 1& 1& 1& 0& 0& 1& 1\\ 1& 1& 0& 0& 0& 1& 1& 1\\ 1& 0& 1& 0& 1& 1& 1& 1\\ 1& 0& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 1& 1& 1& 1& 1\\ 0& 1& 0& 0& 1& 0& 1& 1\\ 0& 0& 1& 0& 1& 0& 1& 1\\ 0& 0& 0& 0& 1& 0& 1& 1\end{array}$$

Fórmula: ϕ = ¬(p ⇔ ¬q) ∧ (r ⇒ ¬p) ∧ (p ∨ r). Tabla:

$$\begin{array}{ccccccc}p& q& r& \mathrm{\neg }(p\iff \mathrm{\neg }q)& (r\Rightarrow \mathrm{\neg }p)& (p\vee r)& \varphi \\ 1& 1& 1& 1& 0& 1& 0\\ 1& 1& 0& 1& 1& 1& 1\\ 1& 0& 1& 0& 0& 1& 0\\ 1& 0& 0& 0& 1& 1& 0\\ 0& 1& 1& 0& 1& 1& 0\\ 0& 1& 0& 0& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0& 0\end{array}$$