Encadenamiento hacia atrás

Procedimiento 4.2 (Encadenamiento hacia atrás)

Entrada:
$\begin{pagi}{27}Una proposici\'on $\phi$.\end{pagi}$
Salida:
$\begin{pagi}{27}El conjunto $\mbox{\rm Spt}(\phi)$\ de asignaciones que hacen ... ...to $\mbox{\rm Nul}(\phi)$\ de asignaciones que hacen falsa a $\phi$.\end{pagi}$

Algoritmo: Dada una proposición $\phi$ revise cuál es su conectivo principal.

Si es `` $\leftrightarrow$ '' o `` $\rightarrow$ '' transforme $\phi$ a una proposición equivalente $\phi'$ en términos de $\neg , \lor, \land$ , según las fórmulas

$\begin{eqnarray*} \phi \rightarrow \psi &\equiv& \neg \phi \lor \psi \\ \phi ... ... &\equiv& (\neg \phi \lor \psi) \land (\phi \lor \neg \psi). \end{eqnarray*}$

Tendremos

$\begin{displaymath}\mbox{\rm Spt}(\phi) = \mbox{\rm Spt}(\phi')\mbox{\it y } \mbox{\rm Nul}(\phi) = \mbox{\rm Nul}(\phi').\end{displaymath}$
Si es `` $\lor$ '' entonces $\phi$ es de la forma $\phi = \phi_1 \lor \phi_2$ . En este caso,

$\begin{eqnarray*} \mbox{\rm Spt}(\phi)&=& \mbox{\rm Spt}(\phi_1)\cup \mbox{\rm ... ...ul}(\phi)&=& \mbox{\rm Nul}(\phi_1)\cap \mbox{\rm Nul}(\phi_2). \end{eqnarray*}$
Si es `` $\land$ '' entonces $\phi$ es de la forma $\phi = \phi_1 \land \phi_2$ . En este caso,

$\begin{eqnarray*} \mbox{\rm Spt}(\phi)&=& \mbox{\rm Spt}(\phi_1)\cap \mbox{\rm ... ...ul}(\phi)&=& \mbox{\rm Nul}(\phi_1)\cup \mbox{\rm Nul}(\phi_2). \end{eqnarray*}$
Si es `` $\neg$ '', entonces $\phi$ es de la forma $\phi =\neg \phi_1$ . En este caso,

$\begin{eqnarray*} \mbox{\rm Spt}(\phi)&=& \mbox{\rm Nul}(\phi_1) \\ \mbox{\rm Nul}(\phi)&=& \mbox{\rm Spt}(\phi_1). \end{eqnarray*}$
Si no hubiera conectivos, entonces $\phi$ ha de ser una variable proposicional . En este caso,

$\begin{eqnarray*} \mbox{\rm Spt}(\phi)&=& \{\mbox{\bf a} \vert (\mbox{\bf a})_i... ...\rm Nul}(\phi)&=& \{\mbox{\bf a} \vert (\mbox{\bf a})_i = 0\}. \end{eqnarray*}$

$\bullet$