Posterior: Formalización de problemas de Arriba: Semántica Anterior: Cláusulas y frases signadas

Cálculo de consecuencias lógicas

Según vimos en las ecs. (2)-(7), la propagación de valores de verdad se calcula mediante las operaciones del álgebra booleana mínima. Tal como se hizo en la definición 1.3.3, para una proposición $\phi\in\mbox{\rm Pbf}_B(X)$, definimos a su dual como la proposición $\phi^d\in\mbox{\rm Pbf}_B(X)$ obtenida al intercambiar $\mbox{\bf0}$ con $\mbox{\bf 1}$ y $\land$ con $\lor$. El procedimiento para calcular negaciones de proposiciones lo da la siguiente:

Proposición 1.1 (Leyes generalizadas de De Morgan)   Para cualquier proposición $\phi(x_1,\ldots,x_n)\in\mbox{\rm Pbf}_B(X)$ se tiene

$$\neg \phi(x_1,\ldots,x_n) \equiv \phi^d(\overline{x_1},\ldots,\overline{x_n})$$ (9)

Demostración
En efecto, procedamos a demostrar la equivalencia (9) por inducción en cuanto a la construcción de $\phi$. Caso base. Si $\phi(x_1,\ldots,x_n)=x_j$ es una variable, claramente:

$$\neg\phi(x_1,\ldots,x_n)=\overline{x_j}=\phi^d(\overline{x_1},\ldots,\overline{x_n}).$$

Caso inductivo. Si $\phi(x_1,\ldots,x_n)$ se compusiera de otras dos proposiciones más sencillas, digamos

$$\phi(x_1,\ldots,x_n)=\alpha(x_1,\ldots,x_n) \lor \beta(x_1,\ldots,x_n)$$

entonces, por las leyes de De Morgan (proposición 1.3.1) en álgebras booleanas, hemos de tener

$$\begin{eqnarray*} \neg\phi(x_1,\ldots,x_n) &=& \neg\alpha(x_1,\ldots,x_n) \land... ...e{x_n}) \\ &=& \phi^d(\overline{x_1},\ldots,\overline{x_n}) \end{eqnarray*}$$

Si acaso fuese

$$\phi(x_1,\ldots,x_n)=\alpha(x_1,\ldots,x_n) \land \beta(x_1,\ldots,x_n)$$

se procede de manera dual. $\quad\Box$ Ahora bien, para cualquier proposición $\phi(x_1,\ldots,x_n)\in\mbox{\rm Pbf}_B(X)$ definamos:

SOPORTE.

$\mbox{\it Spt}(\phi)=\{\mbox{\boldmath$\delta$}\in\mbox{\rm Dos}^n\vert \langle \mbox{\boldmath$\delta$} \vert \phi \rangle = 1\}$: Conjunto de asignaciones que satisfacen a $\phi$.

CONJUNTO NULO.

$\mbox{\it Nul}(\phi)=\{\mbox{\boldmath$\delta$}\in\mbox{\rm Dos}^n\vert \langle \mbox{\boldmath$\delta$} \vert \phi \rangle = 0\}$: Conjunto de asignaciones que refutan a $\phi$.

De la implicación (8) resulta la equivalencia:

$$\{\phi_1,\ldots,\phi_n\} \models \phi \Leftrightarrow \bigwedge_{i=1}^n \mbox{\it Spt}(\phi_i) \subset \mbox{\it Spt}(\phi)$$ (10)

$$\Leftrightarrow \bigvee_{i=1}^n \mbox{\it Nul}(\phi_i) \supset \mbox{\it Nul}(\phi)%%\\$$ (11)

Estas dos últimas relaciones proporcionan criterios conjuntistas para decidir cuándo es que una proposición es una consecuencia lógica de un conjunto de hipótesis. Veamos una serie de ejemplos:

Ejemplo 1.1 (Modus ponens)   Para cualesquiera dos proposiciones $p,q\in\mbox{\it Pbf}(X)$: $\{p\rightarrow q, p\}\models q$.

Explicación. Sea $\mbox{\boldmath$\epsilon$}$ una asignación tal que $\langle \mbox{\boldmath$\epsilon$},p\rightarrow q \rangle = 1$ y $\langle \mbox{\boldmath$\epsilon$},p \rangle = 1$. Entonces:

$$\begin{eqnarray*} 1 &=& \langle \mbox{\boldmath$\epsilon$},p\rightarrow q \rang... ...\rangle) \\ &=& \langle \mbox{\boldmath$\epsilon$},q\rangle \end{eqnarray*}$$

$\quad\Box$

Ejemplo 1.2 (Modus tollens)   Para cualesquiera dos proposiciones $p,q\in\mbox{\it Pbf}(X)$: $\{p\rightarrow q, \neg q\}\models \neg p$.

Explicación. Sea $\mbox{\boldmath$\epsilon$}$ una asignación tal que $\langle \mbox{\boldmath$\epsilon$},p\rightarrow q \rangle = 1$ y $\langle \mbox{\boldmath$\epsilon$},q \rangle = 0$. Entonces:

$$\begin{eqnarray*} 1 &=& \langle \mbox{\boldmath$\epsilon$},p\rightarrow q \rang... ... \\ &=& 1\oplus \langle \mbox{\boldmath$\epsilon$},p\rangle \end{eqnarray*}$$

o sea $\langle \mbox{\boldmath$\epsilon$},p\rangle=0$. $\quad\Box$

Ejemplo 1.3 (Silogismo tradicional)   Para cualesquiera tres proposiciones $p,q,r\in\mbox{\it Pbf}(X)$: $\{p\rightarrow q, q\rightarrow r\}\models p\rightarrow r$.

Explicación. Probemos, de manera equivalente que $\{p,p\rightarrow q, q\rightarrow r\}\models r$. Sea $\mbox{\boldmath$\epsilon$}$ una asignación tal que $\langle \mbox{\boldmath$\epsilon$},p \rangle = 1$, $\langle \mbox{\boldmath$\epsilon$},p\rightarrow q \rangle = 1$ y $\langle \mbox{\boldmath$\epsilon$},q\rightarrow r \rangle = 1$. Entonces, según se vió en el ejemplo 2.1.1: $\langle \mbox{\boldmath$\epsilon$},q \rangle = 1$; y por el mismo ejemplo, resulta $\langle \mbox{\boldmath$\epsilon$},r \rangle = 1$. $\quad\Box$
Posterior: Formalización de problemas de Arriba: Semántica Anterior: Cláusulas y frases signadas