Posterior: Cláusulas y frases signadas Arriba: Semántica Anterior: Reglas de propagación de

Formas conjuntivas y formas disyuntivas

En esta sección hablaremos de cubos y de composiciones booleanas de cubos en términos de formas o fórmulas. El lector recordará que en Teoría de Circuitos se habla de las nociones de minitérminos y de sumas de minitérminos. Son éstas las que aquí intoduciremos. Las formas booleanas son precisamente las proposiciones bien formadas. Sea $X=\left[x_j\right]_{j=1,\ldots,n}$ una lista de variables. Además de las variables, 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$.

Consideremos las siguientes estructuras sintácticas:

LITERALES

Variables o negaciones de variables: $L$ es literal si $\exists x\in X:\:(L=x)\lor(L=\neg x).$ Si $L$ es una literal, su complementaria es $\overline{L}=\left\{\begin{array}{ll} \neg x &\mbox{\rm si $L=x$\ } \\ x &\mbox{\rm si $L=\neg x$\ } \end{array}\right.$.

CLÁUSULAS

Disyunciones de literales: Si $L_1,\ldots, L_m$ son $m$ literales, $C=\bigvee_i L_i$ es una cláusula. Escribiremos también $C=\{L_1,\ldots, L_m\}^D$ (el exponente $D$ se refiere a que ``el conjunto'' ha de interpretarse como una disyunción). Una manera de representar cláusulas es la siguiente: Para cada $\mbox{\boldmath$\epsilon$}\in\mbox{\rm Tres}^n$ hacemos ${\displaystyle\mbox{\rm Claus}(\mbox{\boldmath$\epsilon$}) =\bigvee_{1\leq j\leq n}x_j^{\epsilon_j}}$ donde

$$\forall j=1,\ldots,n:\:x_j^{\epsilon_j}=\left\{\begin{array}{... ...n_j=a \\ x_j &\mbox{\rm si }\epsilon_j=1 \end{array}\right.$$

Así pues tenemos $\forall j\in [\![1,n]\!]$:

$$\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: Si $L_1,\ldots, L_m$ son $m$ literales, $F=\bigwedge_i L_i$ es una frase. Escribiremos también $F=\{L_1,\ldots, L_m\}^C$ (el exponente $C$ se refiere a que ``el conjunto'' ha de interpretarse como una conjunción). Una manera de representar frases es la siguiente: Para cada $\mbox{\boldmath$\epsilon$}\in\mbox{\rm Tres}^n$ hacemos ${\displaystyle\mbox{\rm Frase}(\mbox{\boldmath$\epsilon$}) =\bigwedge_{1\leq j\leq n}x_j^{\epsilon_j}}$. Como en el caso de las cláusulas $\mbox{\boldmath$\epsilon$}$ indica cuáles variables aparecen, y con cuáles signos, en la frase.

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$ (el exponente $C$ se refiere a que ha de interpretarse como forma conjuntiva).

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$ (el exponente $D$ se refiere a que ha de interpretarse como forma disyuntiva).

FORMAS (PROPOSICIONALES)

Las literales, las frases, las cláusulas, las formas conjuntivas y las formas disyuntivas son formas proposicionales.

Alternativamente a como definimos antes, diremos que una asignación es una colección $A$ de literales tal que $\forall L\in\mbox{\it Literales}: L\in A\Rightarrow \overline{L}\not\in A$. La asignación es total si para toda $j\in [\![1,n]\!]$ bien $(x_j\in A)$ o bien $(\neg x_j\in A)$. Un vector $\mbox{\boldmath$\delta$}\in\mbox{\rm Dos}^n$ determina a la asignación total $A_{\mbox{\boldmath$\delta$}}=\left\{x_j^{\delta_j}\vert j=1,\ldots,n\right\}$. Toda forma asume un valor de verdad en el conjunto Tres bajo una asignación $A$ de acuerdo con las definiciones siguientes:

Constantes.

$\mbox{\bf0}(A)=0$, $\mbox{\bf 1}(A)=1$. O bien, usando la notación introducida antes para denotar el valor de verdad de una forma proposicional en una asignación: $\langle A \vert\mbox{\bf0}\rangle = 0$, $\langle A \vert\mbox{\bf 1}\rangle = 1$.

Literales.

Si $L=X_j^{\delta_j}$ es una literal entonces $\langle A \vert L\rangle =\left\{\begin{array}{ll} 1 &\mbox{\rm si }L\in A \\ ... ...rm si }\overline{L}\in A \\ a &\mbox{\rm en otro caso. } \end{array}\right.$

Cláusulas.

Para cada $\mbox{\boldmath$\epsilon$}\in\mbox{\rm Tres}^n$:

$$\langle A \vert \mbox{\rm Claus}(\mbox{\boldmath $\epsilon$})... ..._j}\in A \\ a &\mbox{\rm en otro caso. } \end{array}\right.$$

Así, por ejemplo, si $\mbox{\boldmath$\epsilon$}\in \mbox{\rm Dos}^n$ entonces para todo $\mbox{\boldmath$\delta$}\in\mbox{\rm Dos}^n$,

$$\langle A_{\mbox{\boldmath $\delta$}} \vert\mbox{\rm Claus}(\... ...ot =\overline{\mbox{\boldmath $\epsilon$}} \end{array}\right.$$

Frases.

Para cada $\mbox{\boldmath$\epsilon$}\in\mbox{\rm Tres}^n$:

$$\langle A \vert \mbox{\rm Frase}(\mbox{\boldmath $\epsilon$})... ..._j}\in A \\ a &\mbox{\rm en otro caso. } \end{array}\right.$$

Así, por ejemplo, si $\mbox{\boldmath$\epsilon$}\in \mbox{\rm Dos}^n$ entonces para todo $\mbox{\boldmath$\delta$}\in\mbox{\rm Dos}^n$,

$$\langle A_{\mbox{\boldmath $\delta$}} \vert \mbox{\rm Frase}(... ...$\delta$}\not =\mbox{\boldmath $\epsilon$} \end{array}\right.$$

Formas conjuntivas.

Si $\mbox{\it FC}=\bigwedge_{1\leq i\leq m} C_i$ entonces

$$\langle A \vert \mbox{\it FC} \rangle =\left\{\begin{array}{l... ...C_i(A)=1 \\ a &\mbox{\rm en otro caso. } \end{array}\right.$$

Formas disyuntivas.

Si $\mbox{\it FD}=\bigvee_{1\leq i\leq m} F_i$ entonces

$$\langle A \vert \mbox{\it FD} \rangle=\left\{\begin{array}{ll... ...F_i(A)=0 \\ a &\mbox{\rm en otro caso. } \end{array}\right.$$

Observación 1.6   Si $A$ es una asignación total, entonces para cualquier forma $\phi$ se tiene $\langle A \vert \phi \rangle \in\mbox{\rm Dos}$.

Recíprocamente, toda forma proposicional $\phi$ determina una función $\mbox{\it Fun}_{\phi}:\mbox{\rm Dos}^n\rightarrow\mbox{\rm Dos}$. Para cada vector $\mbox{\boldmath$\delta$}\in\mbox{\rm Dos}^n$, $\mbox{\it Fun}_{\phi}(\mbox{\boldmath$\delta$}) = \langle A \vert \phi \rangle$ es el valor de verdad que asume $\phi$ bajo la asignación total $A_{\mbox{\boldmath$\delta$}}$. Dos formas son equivalentes si definen a una misma función, es decir $\phi_1\equiv\phi_2 \Leftrightarrow \mbox{\it Fun}_{\phi_1}=\mbox{\it Fun}_{\phi_2}$. Confundiremos voluntariamente a la clase de equivalencia de formas proposicionales, bajo esta noción de equivalencia, con la función $\mbox{\rm Dos}^n\rightarrow\mbox{\rm Dos}$ que define. En lo sucesivo, consideraremos únicamente asignaciones totales. Una forma proposicional $\phi$ es

• SATISFACTIBLE si hay una asignación que la satisface, es decir, si $\mbox{\it Fun}_{\phi}\not=\mbox{\bf0}$,
• TAUTOLOG´iA si es satisfecha por todas las posibles asignaciones, es decir, si $\mbox{\it Fun}_{\phi}=\mbox{\bf 1}$,
• REFUTABLE si hay una asignación que la refuta, es decir, si $\mbox{\it Fun}_{\phi}\not=\mbox{\bf 1}$,
• INSATISFACTIBLE si es refutada por todas las posibles asignaciones, es decir, si $\mbox{\it Fun}_{\phi}=\mbox{\bf0}$.

Una forma insatisfactible es también una contradicción.

Observación 1.7   Las siguientes relaciones son válidas:

1. Leyes de De Morgan: La negación de una frase es la cláusula correspondiente a su complementario y la negación de una cláusula es la frase correspondiente a su complementario:
   
   $$\begin{array}{c@{\ ;\ }c} \neg{\mbox{\rm Frase}(\mbox{\boldm... ...rm Frase}(\overline{\mbox{\boldmath $\epsilon$}}) \end{array}$$
   
   

2. La negación de toda forma disyuntiva es una forma conjuntiva y viceversa. Más aún:
   $$\begin{eqnarray*} \mbox{\it FD}=\left[L_{ij}\right]_{i,j}^D &\Rightarrow& \neg\... ...g\mbox{\it FC}=\left[\;\overline{L_{ij}}\;\right]_{i,j}^D %%\\ \end{eqnarray*}$$
   
   
   
   
   

3. Para todo conjunto $S\subset \mbox{\rm Dos}^n$ existe una forma disyuntiva $\mbox{\it FD}_S$ tal que $\forall \mbox{\boldmath$\delta$}\in\mbox{\rm Dos}^n:\mbox{\boldmath$\delta$}\in... ...ftrightarrow \langle \mbox{\boldmath$\delta$} \vert \mbox{\it FD}_S \rangle = 1$. De hecho $\mbox{\it FD}_S=\bigvee_{\mbox{\boldmath$\epsilon$}\in S} \mbox{\rm Frase}(\mbox{\boldmath$\epsilon$})$.
4. Para todo conjunto $N\subset \mbox{\rm Dos}^n$ existe una forma conjuntiva $\mbox{\it FC}_N$ tal que $\forall \mbox{\boldmath$\delta$}\in\mbox{\rm Dos}^n:\mbox{\boldmath$\delta$}\in... ...ftrightarrow \langle \mbox{\boldmath$\delta$} \vert \mbox{\it FC}_N \rangle = 0$. De hecho $\mbox{\it FC}_N=\bigwedge_{\mbox{\boldmath$\epsilon$}\in N} \mbox{\rm Claus}(\overline{\mbox{\boldmath$\epsilon$}})$.
5. Toda función $f:\mbox{\rm Dos}^n\rightarrow\mbox{\rm Dos}$ es realizable mediante una forma $\phi_f$, es decir, la función definida por la forma $\phi_f$ coincide con $f$: $\mbox{\it Fun}_{\phi_f}=f$. De hecho, si $S=\{\mbox{\boldmath$\delta$}\in\mbox{\rm Dos}^n\vert f(\mbox{\boldmath$\delta$})=1\}$, entonces se podría tomar $\phi_f=\mbox{\it FD}_S$, o bien se podría tomar $\phi_f=\mbox{\it FC}_{N}$, donde $N={\mathbb{N}}^n-S$.

Ahora, para cláusulas y formas conjuntivas se tiene inmediatamente la

Observación 1.8   Las siguientes relaciones son válidas:

1. Una cláusula es falsa exactamente en el cubo correspondiente ``al complementario del vector que la define'':
   
   $$\forall \mbox{\boldmath $\delta$}\in\mbox{\rm Dos}^n:\: \lan... ...ta$}\in\mbox{\rm Cubo}(\overline{\mbox{\boldmath $\epsilon$}}).$$
   
   
   Así pues una cláusula se satisface en el complemento de un cubo.
2. Una forma conjuntiva se satisface, por una asignación, si cada una de las cláusulas que la componen se satisface, por esa asignación. En otras palabras, si $\mbox{\it FC}=\bigwedge_{1\leq i\leq m} \mbox{\rm Claus}(\mbox{\boldmath$\epsilon$}_i)$ entonces $\forall \mbox{\boldmath$\delta$}\in\mbox{\rm Dos}^n$:
   $$\begin{eqnarray*} \langle \mbox{\boldmath$\delta$} \vert \mbox{\it FC} \rangle ... ...ox{\rm Cubo}(\overline{\mbox{\boldmath$\epsilon$}_i})\right]^c \end{eqnarray*}$$
   
   
   
   
   

3. Por tanto, las siguientes relaciones son equivalentes a pares:
   • FC es satisfactible.
   • $\bigcap_{i=1}^n \left[\mbox{\rm Cubo}(\overline{\mbox{\boldmath$\epsilon$}_i})\right]^c\not= \emptyset$
   • $\bigcup_{i=1}^n\mbox{\rm Cubo}(\overline{\mbox{\boldmath$\epsilon$}_i})\not= \mbox{\rm Dos}^n$
   Y en consecuencia,

De manera dual, para frases y formas disyuntivas se tiene también inmediatamente la

Observación 1.9   Las siguientes relaciones son válidas:

1. Una frase es verdadera exactamente en su cubo correspondiente.
   
   $$\forall \mbox{\boldmath $\delta$}\in\mbox{\rm Dos}^n:\: \lan... ...dmath $\delta$}\in\mbox{\rm Cubo}(\mbox{\boldmath $\epsilon$}).$$
   
   
   Así pues una frase se refuta en el complemento de su cubo.
2. Una forma disyuntiva se refuta, por una asignación, si cada una de las frases que la componen se refuta, por esa asignación. En otras palabras, si $\mbox{\it FD}=\bigvee_{1\leq i\leq m} \mbox{\rm Frase}(\mbox{\boldmath$\epsilon$}_i)$ entonces $\forall \mbox{\boldmath$\delta$}\in\mbox{\rm Dos}^n$:
   $$\begin{eqnarray*} \langle \mbox{\boldmath$\delta$} \vert \mbox{\it FD} \rangle ... ..._{i=1}^n\mbox{\rm Cubo}(\mbox{\boldmath$\epsilon$}_i)\right]^c \end{eqnarray*}$$
   
   
   
   
   

3. Por tanto las siguientes relaciones son equivalentes a pares:
   • FD es insatisfactible.
   • $\bigcap_{i=1}^n\left[\mbox{\rm Cubo}(\mbox{\boldmath$\epsilon$}_i)\right]^c\not= \emptyset$
   • $\bigcup_{i=1}^n\mbox{\rm Cubo}(\mbox{\boldmath$\epsilon$}_i)\not= \mbox{\rm Dos}^n$
   Y en consecuencia,

Posterior: Cláusulas y frases signadas Arriba: Semántica Anterior: Reglas de propagación de