next up previous contents
Siguiente: El primer problema completo-NP Un nivel arriba: Formas proposicionales y el Anterior: Formas proposicionales y el

Formas booleanas

Utilizaremos los siguientes símbolos constantes Sea $\mbox{\bf X}=\left[X_j\right]_{j=1,\ldots,n_0}$ una lista de variables. Consideremos las siguientes estructuras sintácticas:
Literales
Variables o negaciones de variables: $L\mbox{\rm es {\em literal} si }\exists X\in\mbox{\bf X}:\:(L=X)\lor(L=\neg X).$
Cláusulas
Disyunciones de literales: Para cada $\mbox{\boldmath$\epsilon$ }\in\{-1,0,1\}^{n_0}$ hacemos ${\displaystyle\mbox{\rm Claus}(\mbox{\boldmath$\epsilon$ }) =\bigvee_{1\leq j\leq n}X_j^{\downarrow\epsilon_j}}$ donde

\begin{displaymath}\forall j=1,\ldots,n:\:X_j^{\downarrow\epsilon_j}=\left\{\beg...
...\\
\neg X_j &\mbox{\rm si }\epsilon_j=-1
\end{array}\right.\end{displaymath}

En una cláusula $\mbox{\rm Claus}(\mbox{\boldmath$\epsilon$ })$ tenemos

\begin{displaymath}\epsilon_j=\left\{\begin{array}{rl}
1 &\mbox{\rm si $X_j$ ap...
... en Claus$(\mbox{\boldmath $\epsilon$})$.}
\end{array}\right.\end{displaymath}

Frases
Conjunciones de literales: Para cada $\mbox{\boldmath$\epsilon$ }\in\{-1,0,1\}^{n_0}$ hacemos ${\displaystyle\mbox{\rm Frase}(\mbox{\boldmath$\epsilon$ }) =\bigwedge_{1\leq j\leq n}X_j^{\uparrow\epsilon_j}}$ donde

\begin{displaymath}\forall j=1,\ldots,n:\:X_j^{\uparrow\epsilon_j}=\left\{\begin...
...\\
\neg X_j &\mbox{\rm si }\epsilon_j=-1
\end{array}\right.\end{displaymath}

Como en el caso de las cláusulas $\mbox{\boldmath$\epsilon$ }$ indica cuáles variables aparecen en la frase, y en este caso indica a su signo de aparición.
Formas conjuntivas
Conjunciones de cláusulas. Si ${\displaystyle\mbox{\it FC}=\bigwedge_{1\leq i\leq m} C_i=\bigwedge_{1\leq i\leq m} \bigvee_{1\leq j\leq n} L_{ij}}$ entonces representamos a $\mbox{\it FC}$ por la matriz $\mbox{\it FC}=\left[L_{ij}\right]_{i,j}^C$.
Formas disyuntivas
Disyunciones de frases. Si ${\displaystyle\mbox{\it FD}=\bigvee_{1\leq i\leq m} F_i=\bigvee_{1\leq i\leq m} \bigwedge_{1\leq j\leq n} L_{ij}}$ entonces representamos a $\mbox{\it FD}$ por la matriz $\mbox{\it FD}=\left[L_{ij}\right]_{i,j}^D$.
Formas proposicionales
Puesto recursivamente,
Sea $\mbox{\rm Dos}=\{0,1\}$ el conjunto de los dos valores de verdad booleanos. Toda forma proposicional F determina una función $F:\mbox{\rm Dos}^{n_0}\rightarrow\mbox{\rm Dos}$. Para cada $\mbox{\bf x}\in\mbox{\rm Dos}^{n_0}$ $F(\mbox{\bf x})$ es el valor de verdad que asume F bajo la asignación $\mbox{\bf x}$. Dos formas son equivalentes si definen a una misma función. Confundiremos voluntariamente a una forma proposicional con la función $\mbox{\rm Dos}^{n_0}\rightarrow\mbox{\rm Dos}$ que define. Una forma proposicional F es
next up previous contents
Siguiente: El primer problema completo-NP Un nivel arriba: Formas proposicionales y el Anterior: Formas proposicionales y el
Guillermo Morales-Luna
2000-07-10