Posterior: Formas conjuntivas y formas Arriba: Semántica Anterior: Asignaciones

Reglas de propagación de valores de verdad

En lo sucesivo, consideraremos la clase $\mbox{\rm Pbf}_B(X)$ de proposiciones bien formadas con notación de enfijo. Los valores de verdad de proposiciones se calculan en términos de los valores de verdad de sus subproposiciones más sencillas:

• La negación $\neg p$ de una proposición $p$ es verdadera si y sólo si $p$ es falsa.
• La implicación $p \rightarrow q$ es falsa únicamente en el caso en el que su antecedente $p$ es verdadero y su consecuente $q$ es falso.

Para los otros conectivos:

• La disyunción de dos proposiciones es falsa si y sólo si ambas proposiciones son falsas.
• La conjunción de dos proposiciones es verdadera si y sólo si ambas proposiciones son verdaderas.
• La equivalencia de dos proposiciones es falsa si y sólo si las proposiciones tienen valores de verdad distintos entre sí.

Identifiquemos el valor Verdadero con el elemento $1\in\mbox{\rm Dos}$ y el valor Falso con el elemento $0\in\mbox{\rm Dos}$. Cualquier proposición $p(x_1 ,\ldots, x_n )$ determina así una función $f_p :\mbox{\rm Dos}^n \rightarrow \mbox{\rm Dos}$. $\forall\; \mbox{\boldmath$\delta$}=(\delta_1 ,\ldots , \delta_n ) \in \mbox{\rm Dos}^n$, $f_p (\delta_1 ,\ldots ,\delta_n)$ es el valor de verdad de $p$ cuando a cada variable $x_j$ se le asigna el valor $\delta_j$. Escribiremos $\langle \mbox{\boldmath$\delta$} \vert p\rangle :=f_p(\mbox{\boldmath$\delta$})$ para denotar al valor de verdad de $p$ bajo la asignación $\mbox{\boldmath$\delta$}$. Recordando las operaciones del álgebra booleana $(\mbox{\rm Dos},\land,\lor\overline{\ },1,0)$, las definiciones anteriores de propagación de valores pueden ser resumidas mediante las fórmulas siguientes: Para cualesquiera proposiciones $p,q\in\mbox{\rm Pbf}_B(X)$ y cualquier asignación $\mbox{\boldmath$\delta$}\in\mbox{\rm Dos}^n$,

$$\langle \mbox{\boldmath$\delta$} \vert \mbox{\bf0}\rangle = 0$$ (2)

$$\langle \mbox{\boldmath$\delta$} \vert \overline{p}\rangle = \overline{\langle \mbox{\boldmath$\delta$} \vert p\rangle}$$ (3)

$$\langle \mbox{\boldmath$\delta$} \vert p\land q\rangle = \langle \mbox{\boldmath$\delta$} \vert p\rangle \land \langle \mbox{\boldmath$\delta$} \vert q\rangle$$ (4)

$$\langle \mbox{\boldmath$\delta$} \vert p\lor q\rangle = \langle \mbox{\boldmath$\delta$} \vert p\rangle \lor \langle \mbox{\boldmath$\delta$} \vert q\rangle$$ (5)

$$\langle \mbox{\boldmath$\delta$} \vert p\rightarrow q\rangle = \langle \mbox{\boldmath$\delta$} \vert p\rangle \rightarrow \langle \mbox{\boldmath$\delta$} \vert q\rangle$$ (6)

$$\langle \mbox{\boldmath$\delta$} \vert p\leftrightarrow q\rangle = \langle \mbox{\boldmath$\delta$} \vert p\rangle \leftrightarrow \langle \mbox{\boldmath$\delta$} \vert q\rangle%%\\$$ (7)

Así pues, el cálculo de valores de verdad se hace de igual manera que el de expresiones booleanas en el álgebra mínima $\mbox{\rm Dos}$.

Definición 1.2   Los siguientes tipos de proposiciones son muy importantes:

TAUTOLOG´iA.

Proposición verdadera bajo toda asignación.

CONTRADICCIÓN.

Proposición cuya negación es tautología.

Distinguimos también las nociones siguientes: Decimos que $p$ es EQUIVALENTE a $q$, y escribimos $p \equiv q$, si $p \leftrightarrow q$ es tautología.

Lema 1.1   Las relaciones siguientes son todas verdaderas:

• $p$ es tautología $\Leftrightarrow \ p$ determina a la función constante 1
• $p$ es contradicción $\Leftrightarrow \ p$ determina a la función constante 0
• $p \equiv q \ \Leftrightarrow \ p$ y $q$ determinan a una misma función.

De hecho, $(\mbox{\rm Pbf}_B(X)/\equiv, \lor , \land , \neg , 0, 1)$ es un álgebra booleana. Su cardinalidad es $2^{2^n}$ y su longitud es $2^n$, donde $n$ es el número de variables en $X$. Las proposiciones equivalentes al supremo de esa álgebra booleana son las tautologías y las equivalentes al ínfimo son las contradicciones.


Decimos que $p$ es CONSECUENCIA LÓGICA de $\{p_1 ,\ldots , p_n \}$, y escribimos $\{p_1 ,\ldots , p_n \} \models p$, si la proposición compuesta $\left(p_1 \land \cdots \land p_n \ \rightarrow \ p\right)$ es una tautología.

Lema 1.2   Las relaciones siguientes son verdaderas para cualesquiera proposiciones involucradas:

• $\{p_1 ,\ldots , p_n \} \models p$.
• Para cualquier asignación $\mbox{\boldmath$\delta$}\in\mbox{\rm Dos}^n$:
  

  $$\langle \mbox{\boldmath$\delta$} \vert p_1 \land \cdots \la... ...tarrow\ \langle \mbox{\boldmath$\delta$} \vert p\rangle = 1.$$ (8)

  
  

En otras palabras, una proposición es consecuencia lógica de un conjunto de hipótesis cuando y sólo cuando toda asignación que haga verdaderas a las hipótesis, ha de hacer también verdadera a esa proposición. Demostración
Supongamos $\{p_1 ,\ldots , p_n \} \models p$. Si acaso hubiese una asignación $\mbox{\boldmath$\delta$}\in\mbox{\rm Dos}^n$ tal que $\langle \mbox{\boldmath$\delta$} \vert p_1 \land \cdots \land p_n\rangle = 1$ pero $\langle \mbox{\boldmath$\delta$} \vert p\rangle = 0$ entonces, para esa asignación: $\langle \mbox{\boldmath$\delta$} \vert p_1 \land \cdots \land p_n\rightarrow p\rangle = 0$, lo cual contradiría que $\{p_1 ,\ldots , p_n \} \models p$. Recíprocamente si se cumple la segunda condición, entonces la proposición $p_1 \land \cdots \land p_n\rightarrow p$ es una tautología. $\quad\Box$
Posterior: Formas conjuntivas y formas Arriba: Semántica Anterior: Asignaciones