Sobre las Asignaciones de los Valores de Verdad

Anteriormente revisamos la sintaxis y los sistemas deductivos de la lógica proposicional. Si bien esto nos sirvió para revisar la forma en que se pueden obtener unas expresiones a partir de otras, con todo esto no hemos dicho nada sobre la asignación de los valores de verdad. Debido a que ya hemos dicho todo lo que hay que decir sobre las técnicas de deducción en la lógica proposicional, comenzaremos nuestro estudio sobre la semántica de la lógica proposicional, donde se revisa la forma en que se propagan las asignaciones de los valores de verdad de una expresión a otra.

Semántica de los Conectores de la Lógica Proposicional

La semántica de los conectores se introduce a través de las tablas de verdad, ya que proporcionan una forma sencilla y ordenada de representar todas las asignaciones posibles sobre una expresión.

Tabla de Verdad de la Negación Conjunta

En primer lugar partiremos con el conector más fundamental de todos, que es la negación conjunta. Su tabla de verdad es la siguiente:

Los valores «1» y «0» se corresponden con «Verdadero» y «Falso», respectivamente. Cada fila en la tabla de verdad es una posible asignación sobre las variables (o expresiones atómicas) que componen la expresión (o expresiones) a estudiar. De manera similar, cada columna donde se encuentra una expresión formada por estas variables tiene los posibles resultados de dichas asignaciones. De esta forma, la interpretación de esta tabla nos dice que \alpha\downarrow\beta es verdadero sólo cuando \alpha y \beta son ambos falsos al mismo tiempo, y falso en otro caso. Por esa razón, el conector \downarrow recibe el nombre de negación conjunta.

Tablas de Verdad de los Conectores Derivados

A partir de la semántica de la negación conjunta se puede obtener la de los demás conectores a través de sus definiciones. Estas son:

A partir de estas definiciones es posible calcular las tablas de verdad de los demás conectores:

Negación

De aquí viene el hecho de que el conector de negación tiene la propiedad de invertir el valor de verdad de la expresión sobre la que se aplica.

Disyunción Inclusiva

Es por ello que la disyunción inclusiva (o simplemente «disyunción») entre dos expresiones es verdadera si por lo menos una de las expresiones es verdadera, y es falsa cuando ambas expresiones son falsas a la vez.

Conjunción

Como resultado, la conjunción entre dos expresiones es verdadera sólo si ambas expresiones son verdaderas al mismo tiempo, y falsa en otro caso. Por esto es que un nombre adecuado para este conector también puede ser el de «afirmación conjunta».

Implicancia

De modo que la tabla de verdad de la implicancia resume la noción de que una expresión verdadera sólo puede implicar una expresión verdadera, pero una falsa puede implicar cualquier cosa.

Doble Implicancia

La doble implicancia forma una expresión verdadera siempre que las dos expresiones que la forman tengan los mismos valores de verdad, y es falsa en otro caso.

Disyunción Exclusiva

La disyunción exclusiva entre dos expresiones es verdadera cuando una, y sólo una de las expresiones es verdadera, y falsa en otro caso.

Asignaciones en la lógica proposicional

Con lo anteriormente descrito tenemos una noción sencilla de lo que es una asignación; sin embargo, para los desarrollos que veremos más adelante necesitaremos algo más preciso. Si S=\{A_1, A_2, \cdots, A_n\} un conjunto de expresiones atómicas y \mathcal{F}(S) el conjunto de todas las expresiones que se puden construir a partir de las expresiones de S, entonces se tiene la siguiente definición:

DEFINICIÓN: Una asignación sobre S es una función \mathcal{A}: S \longrightarrow \{0,1\}

En otras palabras, una asignación sobre S proporciona un valor de verdad a cada expresión atómica de S. Una asignación \mathcal{A} de S se extiende naturalmente sobre todos los elementos de \mathcal{F}(S). Si tenemos una expresión F\in \mathcal{F}(S), entonces una asignación \mathcal{A} sobre S se corresponde con una única fila en la tabla de verdad de F y se dice que \mathcal{A}(F) es el valor de verdad de F en esa fila.

Una asignación \mathcal{A} de S también se puede extender a ciertas expresiones que no están en \mathcal{F}(S). Si F_0 es una expresión que no está en \mathcal{F}(S) y S_0 es el conjunto de subfórmulas atómicas de F_0, entonces si todas las extensiones de \mathcal{A} para S\cup S_0 tienen el mismo valor para F_0, entonces se define \mathcal{A}(F_0) como ese valor.

EJEMPLO: Si A y B son expresiones atómicas y \mathcal{A} es una asignación sobre \{A,B\} definida a través de \mathcal{A}(A)=1 y \mathcal{A}(B)=0, entonces se tendrá que:

\mathcal{A}(A\wedge B)=0 y \mathcal{A}(A\vee B)=1

Y a pesar de que no se ha establecido una asignación sobre una variable C, se puede decir que:

\mathcal{A}(A\wedge (C\vee \neg C))=1 y \mathcal{A}(B\vee (C\wedge \neg C))=0

Esto ocurre con las últimas dos expresiones porque, sin importar la asignación de C, siempre ocurrirá que

\mathcal{A}(C\vee\neg C)=1 y \mathcal{A}(C\wedge\neg C)=0

Cosa que podemos revisar rápidamente calculando sus tablas de verdad.

■ Fin del Ejemplo

Modelos en la Lógica Proposicional

Consideremos una asignación \mathcal{A} sobre un conjunto de expresiones S. Si F\in S es tal que \mathcal{A}(F)=1, entonces se dice que la asignación \mathcal{A} modela a F, o que la expresión F es sostenida por la asignación \mathcal{A} y lo representamos a través de la escritura

\mathcal{A}\models F.

Y, a partir de esto se establecen las siguientes definiciones:

DEFINICIÓN: Se dice que una expresión es válida cuando se sostiene bajo cualquier asignación. Si F es válida, entonces se escribe \models F . Las expresiones válidas también se llaman tautología.

EJEMPLO: La expresión (C\vee \neg C), que ya hemos visto, es una tautología.

■ Fin del Ejemplo

DEFINICIÓN: Una expresión se dice satisfacible si es sostenida por alguna asignación. Las expresiones satisfacibles que no son tautologías se llaman contingencias.

DEFINICIÓN: Una expresión se dice insatisfacible si no sostenida por ninguna asignación. Las expresiones insatisfacibles se llaman contradicciones. Si F es una contradicción, entonces se escribe \not\models F .

EJEMPLO: La expresión (C\wedge \neg C), que ya hemos visto, es una contradicción..

■ Fin del Ejemplo

Ejemplos de Tautologías y Contradicciones

Supongamos que queremos ver si una expresión es válida o no. Esto que acabamos de plantear es un problema de decisión dentro de la Semántica de la Lógica Proposicional. Un problema de decisión es cualquier problema que, dada cierta entrada, tiene por resultado un «sí» o un «no». Si nos dan una expresión F y preguntamos si es o no válida, entonces estamos ante un problema de decisión que llamamos problema de validez. De forma análoga, si preguntamos si es o no satisfacible, estamos ante un problema de satisfacibilidad. En la lógica proposicional, las tablas de verdad ofrecen un enfoque sistemático para resolver estos problemas de decisión: si todos los valores de verdad posibles de F son «1», entonces F es válida; si sólo algunos son «1», entonces es satisfacible; y finalmente, si todos son «0», entonces es insatisfacible.

EJEMPLO: Consideremos la expresión ((A\wedge (A \rightarrow B)) \rightarrow B). Para determinar si esta expresión es válida, satisfacible o contradictoria, hacemos su tabla de verdad.

Con esto vemos que ((A\wedge(A\rightarrow B))\rightarrow B) tiene valor de verdad «1» para todas las asignaciones posibles, de modo que la expresión resulta ser una tautología.

■ Fin del Ejemplo

EJEMPLO: Consideremos ahora la expresión (((A\rightarrow B)\rightarrow A)\wedge \neg A). El cálculo de la tabla de verdad no da lo que se muestra a continuación:

De modo que el resultado es una contradicción.

■ Fin del Ejemplo

Un Problema de Eficiencia Acecha a la Semántica de la Lógica Proposicional

En teoría, podemos determinar si una expresión es válida, contingente o insatisfacible simplemente calculando su tabla de verdad, cosa que no es especialmente difícil; desafortunadamente, la facilidad de la ejecución se paga a cambio de eficiencia. Si tenemos una expresión F compuesta de n expresiones atómicas, entonces tendremos que calcular una tabla de verdad con 2^n filas; de modo que, si por ejemplo F está compuesta de 23 expresiones atómicas, entonces su tabla de verdad tendrá 8.388.608 filas que deben ser calculadas. Procediendo de esta manera, aunque mecánico y fácil de realizar, el cálculo rápidamente comienza a dejar de ser factible conforme aumenta la complejidad de las expresiones. Debido a esto, uno de nuestros objetivos futuros será encontrar una forma de resolver los problemas de validez o satisfacibilidad sin la necesidad de calcular tablas de verdad. La búsqueda de tales métodos es uno de los problemas centrales de cualquier lógica.