3.2 Formas canónicas
Toda función lógica se puede expresar como combinación de dos tipos de términos conocidos como canónicos: los minitérminos (o minterms) y los maxitérminos (o maxterms).
Un minitérmino o minterm es una cláusula formada por n literales (positivos o negativos) conectados únicamente por la conjunción lógica (AND). Ejemplos de minterms para n=3 son \(a·b·c\), \(a·\overline{b}·c\) y \(a·b·\overline{c}\). Se puede observar que cada minterm tiene una interpretación verdadera para una única combinación de valores de las variables. Por ejemplo, el minterm \(a·\overline{b}·c\) es verdadero solo cuando a y c son ciertos (valor ‘1’) y b es falso (valor ‘0’).
Un maxitérmino o maxterm es una cláusula formada por n literales (positivos o negativos) conectados únicamente por la disyunción lógica (OR). Por ejemplo, los siguientes términos son maxterms: \(a+b+c\), \(a+\overline{b}+c\) y \(a+b+\overline{c}\). Los maxterms y los minterms se pueden considerar complementarios, pues se puede pasar de uno a otro aplicando el operador complemento.
Se dice que una función lógica está en forma canónica cuando contiene un mismo tipo de términos canónicos unidos por una conectiva que depende de dicho tipo. Así, si la función lógica viene expresada como una disyunción lógica (OR) de minterms se dice que está en la forma normal disyuntiva (de aquí en adelante DNF, acrónimo de disjunctive normal form). Por contra, si la función lógica se expresa como una conjunción lógica (AND) de maxterms se dice que está en la forma normal conjuntiva (de aquí en adelante CNF, acrónimo de conjunctive normal form). La forma DNF suele denominarse informalmente “suma de productos”, mientras que la forma CNF recibe el apelativo de “producto de sumas”.
Examinamos a continuación cada forma canónica en detalle.
3.2.1 Forma normal disyuntiva (DNF)
Formalmente, sea \(\phi\) una fórmula lógica expresada en términos de DNF (sumas de productos), entonces:
\[\phi \equiv \sum_{1}^{n} C_i \mbox{ siendo } C_i = (\lambda_1 \cdot \lambda_2 \cdot ... \cdot \lambda_m )\]
Es posible obtener una expresión canónica para \(\phi\) a partir de todas sus interpretaciones que la satisfacen (combinaciones de valores de sus variables para las que \(\phi\) toma el valor ‘1’), un minitérmino por cada interpretación.
Por ejemplo, dada la tabla de verdad de la función XOR (Tabla 3.6), se observa que las filas con resultado ‘1’ son la segunda y la tercera. Consecuentemente, \(\phi\) puede escribirse como la suma de minterms siguiente:
\[\phi = \overline{a} · b + a · \overline{b}\]
El ejemplo muestra que existe una correspondencia entre cada minitérmino y las filas de la tabla de verdad con resultado ‘1’, así como entre los literales y los valores de verdad de las celdas.
3.2.2 Forma normal conjuntiva (CNF)
Formalmente, sea \(\phi\) una fórmula lógica expresada en términos de DNF (sumas de productos), entonces:
\[\phi \equiv \prod_{1}^{n} C_i \mbox{ siendo } C_i = (\lambda_1 + \lambda_2 + ... + \lambda_m )\]
Es posible obtener una expresión canónica para \(\phi\) a partir de todas las interpretaciones para las que \(\phi\) toma el valor ‘0’, un maxitérmino por cada combinación. Por ejemplo, dada la tabla de verdad de la función XOR (Tabla 3.6), se observa que las filas con resultado ‘0’ son la primera y la cuarta. Consecuentemente, \(\phi\) puede escribirse como la suma de maxterms siguiente:
\[f = (a+b) ·(\overline{a} + \overline{b})\]
El ejemplo muestra que existe una correspondencia entre cada maxitérmino y las filas de la tabla de verdad con resultado ‘0’. En este caso, y a diferencia de la forma DNF, los literales de cada maxitérmino toman signo opuesto a los valores de verdad de las celdas. Para entender esto, considere que cada maxitérmino está “impidiendo” que la fila correspondiente de la tabla de verdad (que tiene resultado ‘0’) sea una interpretación verdadera de \(\phi\). Siguiendo el razonamiento, la conjunción de todos estos maxitérminos elimina todas aquellas interpretaciones que no satisfacen \(\phi\), lo que equivale a la expresión lógica de la propia \(\phi\).
Ejercicio.- Demuestre que ambas fórmulas de la función XOR (DNF y CNF) son equivalentes.
Ejercicio.- Exprese la función lógica definida por la tabla de verdad que aparece en la Tabla 3.8, en las dos formas canónicas.
| a | b | c | y |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |