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

• 1: Valor verdadero. Es la unidad de ``$\land$'': $F\land\mbox{\bf 1}=\mbox{\bf 1}\land F=F$.
• 0: Valor falso. Es la unidad de ``$\lor$'': $C\lor\mbox{\bf0}=\mbox{\bf0}\lor C=C$.

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

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

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

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

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

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

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,

• $\mbox{\bf0},\mbox{\bf 1}$ son formas proposicionales.
• Las variables son formas proposicionales.
• Las negaciones de formas proposicionales son también formas proposicionales.
• Las conjunciones y las disyunciones de formas proposicionales son también formas proposicionales.

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

• satisfactible si hay una asignación que la satisface, es decir, si $F\not=\mbox{\bf0}$,
• tautología si es satisfecha por todas las posibles asignaciones, es decir, si $F=\mbox{\bf 1}$,
• refutable si hay una asignación que la refuta, es decir, si $F\not=\mbox{\bf 1}$,
• insatisfactible si es refutada por todas las posibles asignaciones, es decir, si $F=\mbox{\bf0}$.

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