next up previous contents
Posterior: Filtros y homomorfismos Arriba: Algebras booleanas Anterior: Presentación algebraica

Conjuntos completos de operadores

En un álgebra booleana $(A,\land,\lor,\overline{\ },\mbox{\bf 1},\mbox{\bf0})$, definamos aún las siguientes operaciones $\rightarrow,\leftrightarrow:A^2 \to A$ haciendo $\forall x,y\in A$:

\begin{eqnarray*}
x\rightarrow y &=& \overline{x}\lor y \\
x\leftrightarrow y &=& (\overline{x}\lor y)\land (x\lor \overline{y})
\end{eqnarray*}



Se tendrá, equivalentemente:

\begin{eqnarray*}
x\rightarrow y &=& \mbox{\bf 1}\oplus x\oplus (x\odot y) \\
x\leftrightarrow y &=& \mbox{\bf 1}\oplus x\oplus y
\end{eqnarray*}



Observación 3.4   Con las operaciones introducidas se cumplen las identidades siguientes:
  1. En términos de $\{\overline{\ },\land\}$:

    \begin{displaymath}\begin{array}{rcl}
x\lor y &=& \overline{\overline{x}\land\o...
...erline{y}} \land \overline{ \overline{x} \land y}
\end{array}\end{displaymath}

  2. En términos de $\{\overline{\ },\lor\}$:

    \begin{displaymath}\begin{array}{rcl}
x\land y &=& \overline{\overline{x}\lor\o...
...line{x}\lor\overline{y}} \lor \overline{ x\lor y}
\end{array}\end{displaymath}

  3. En términos de $\{\overline{\ },\rightarrow\}$:

    \begin{displaymath}\begin{array}{rcl}
x\land y &=& \overline{x\rightarrow\overl...
...arrow y)\rightarrow \overline{ (y\rightarrow x)}}
\end{array}\end{displaymath}

Es en este sentido que los conjuntos de operadores $\{\overline{\ },\land\}$, $\{\overline{\ },\lor\}$ y $\{\overline{\ },\rightarrow\}$ se dicen ser COMPLETOS. Finalmente, consideremos los operadores NAND y NOR, $\uparrow,\downarrow:A^2\to A$ definidos como sigue:
$\displaystyle x \uparrow y$ $\textstyle =$ $\displaystyle \overline{x\land y} = \mbox{\bf 1}\oplus (x\odot y)$ (2)
$\displaystyle x \downarrow y$ $\textstyle =$ $\displaystyle \overline{x\lor y} = (\mbox{\bf 1}\oplus x)\odot (\mbox{\bf 1}\oplus y)%%\\
$ (3)

Entonces

\begin{displaymath}\begin{array}{rcl}
\overline{x} &=& x\uparrow x \\
x\land y &=& (x\uparrow y)\uparrow (x\uparrow y)
\end{array}\end{displaymath}

de donde resulta que cualquier otro operador puede expresarse únicamente en términos de $\{\uparrow\}$. Similarmente,

\begin{displaymath}\begin{array}{rcl}
\overline{x} &=& x\downarrow x \\
x\lor y &=& (x\downarrow y)\downarrow (x\downarrow y)
\end{array}\end{displaymath}

de donde resulta que cualquier otro operador puede expresarse únicamente en términos de $\{\downarrow\}$. Así pues, $\{\uparrow\}$ y $\{\downarrow\}$ son también completos.
next up previous contents
Posterior: Filtros y homomorfismos Arriba: Algebras booleanas Anterior: Presentación algebraica
Guillermo Morales-Luna
2004-07-27