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{array}{rcl} x\lor y &=& \overline{\overline{x}\land\o... ...erline{y}} \land \overline{ \overline{x} \land y} \end{array}$$
   
   

2. En términos de $\{\overline{\ },\lor\}$:
   
   $$\begin{array}{rcl} x\land y &=& \overline{\overline{x}\lor\o... ...line{x}\lor\overline{y}} \lor \overline{ x\lor y} \end{array}$$
   
   

3. En términos de $\{\overline{\ },\rightarrow\}$:
   
   $$\begin{array}{rcl} x\land y &=& \overline{x\rightarrow\overl... ...arrow y)\rightarrow \overline{ (y\rightarrow x)}} \end{array}$$
   
   

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:

$$x \uparrow y = \overline{x\land y} = \mbox{\bf 1}\oplus (x\odot y)$$ (2)

$$x \downarrow y = \overline{x\lor y} = (\mbox{\bf 1}\oplus x)\odot (\mbox{\bf 1}\oplus y)%%\\$$ (3)

Entonces

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

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

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

de donde resulta que cualquier otro operador puede expresarse únicamente en términos de $\{\downarrow\}$. Así pues, $\{\uparrow\}$ y $\{\downarrow\}$ son también completos.
Posterior: Filtros y homomorfismos Arriba: Algebras booleanas Anterior: Presentación algebraica