Forma canònica (àlgebra de Boole)

En àlgebra booleana, es coneix com a terme canònic d'una funció lògica a tot producte o suma a la qual apareixen totes les variables en llur forma directa o inversa. Una funció lògica que estigui composta per operadors lògics pot expressar-se en forma canònica usant els conceptes de minterm i maxterm. Totes les funcions lògiques són expressables en forma canònica, tant com en "suma de minterms" com en "producte de maxterms". Això permet una millor anàlisi per a la simplificació d'aquestes funcions, la qual cosa és de gran importància per la minimització de circuits digitals.

Una funció booleana expressada com a disjunció lògica (OR) de minterms és coneguda com a "suma de productes", i la seva dual de De Morgan és el "producte de sumes", la qual és una funció expressada com a conjunció lògica (AND) de maxterms.

Termes mínims[modifica]

Per a una funció booleana de $n$ variables ${x_{1},...x_{n}}$ , un producte booleà on cadascuna de les $n$ variables apareix una sola vegada (negada o sense negar) s'anomena terme mínim o minterm. És a dir, un minterm és una expressió lògica de n variables que consisteix únicament en l'operador conjunció lògica (AND) i l'operador negació (NOT).

Per exemple, $abc$ , $ab'c$ i $abc'$ són exemples de minterms per a una funció booleana amb les tres variables $a$ , $b$ i $c$ .

Indexació de minterms[modifica]

{\begin{array}{|c|c l||c|c|c|}\hline n&m&&a&b&c\\\hline 0&m_{0}=&a'b'c'&0&0&0\\1&m_{1}=&a'b'c&0&0&1\\2&m_{2}=&a'bc'&0&1&0\\3&m_{3}=&a'bc&0&1&1\\4&m_{4}=&ab'c'&1&0&0\\5&m_{5}=&ab'c&1&0&1\\6&m_{6}=&abc'&1&1&0\\7&m_{7}=&abc&1&1&1\\\hline \end{array}}

En general, hom assigna a cada minterm (escrivint les variables que el componen en el mateix ordre), un índex basat en el valor binari del minterm.

Un terme negat, com ara $a'$ , es considera com el número binari 0, i el terme no negat $a$ es considera com un 1.

Per exemple, hom pot associar el nombre 6 amb $abc'$ , i anomenem l'expressió $m_{6}$ . Llavors $m_{0}$ de tres variables és $a'b'c'$ i $m_{7}$ hauria de ser $abc$ , ja que 7 en base 10 s'expressa com a 111 en base 2.

Hom pot observar que cada minterm només retorna el valor cert (1) amb una sola entrada de les possibles.

Per exemple, el minterm 5, $ab'c$ és cert només quan a i c són certs i b és fals; l'entrada a = 1, b = 0, c = 1 dona com a resultat 1.

Funció equivalent[modifica]

{\begin{array}{|c||c|c||c|}\hline n&a&b&f(a,b)\\\hline 0&0&0&1\\1&0&1&0\\2&1&0&0\\3&1&1&1\\\hline \end{array}}

Si tenim una taula de veritat d'una funció lògica f(a, b), llavors és possible escriure-la com a "suma de productes". Per exemple, donada la taula de veritat de la dreta, observem que les files amb resultat 1 són la primera i la quarta. Aleshores, podem escriure f com la suma dels minterms $f(a,b)=m_{0}+m_{3}$ .

Si volem verificar això:

f(a,b)=m_{0}+m_{3}=(a'b')+(ab)

tindrem que la taula de veritat de la funció, calculant-la directament, serà la mateixa.

Aquesta expressió aplicada a interruptors seria la de la figura; hom pot veure que hi ha dues branques: en la superior, dos interruptors inversos a' i b' posats en sèrie, la qual cosa és equivalent a a'b'; en la inferior, dos interruptors directes a i b també en sèrie, la qual cosa és equivalent a ab. Aquests dos circuits posats en paral·lel resulten en a'b' + ab.

Termes màxims[modifica]

Un terme màxim o maxterm és una expressió lògica de n variables que consisteix únicament en la disjunció lògica i l'operador complement o negació. Els maxterms són una expressió dual dels minterms. En comptes d'usar operacions AND, utilitzaem operacions OR i procedim de manera similar.

Per exemple, els següents termes canònics són maxterms:

a+b'+c

a'+b+c

Dualització[modifica]

{\begin{array}{|c|c l|c l||c|c|c|}\hline n&M&&m&&a&b&c\\\hline 0&M_{0}=&a+b+c&m_{0}=&a'b'c'&0&0&0\\1&M_{1}=&a+b+c'&m_{1}=&a'b'c&0&0&1\\2&M_{2}=&a+b'+c&m_{2}=&a'bc'&0&1&0\\3&M_{3}=&a+b'+c'&m_{3}=&a'bc&0&1&1\\4&M_{4}=&a'+b+c&m_{4}=&ab'c'&1&0&0\\5&M_{5}=&a'+b+c'&m_{5}=&ab'c&1&0&1\\6&M_{6}=&a'+b'+c&m_{6}=&abc'&1&1&0\\7&M_{7}=&a'+b'+c'&m_{7}=&abc&1&1&1\\\hline \end{array}}

El complement d'un minterm és el seu respectiu maxterm. Això es pot verificar fàcilment usant les Lleis de De Morgan. Per exemple:

m_{1}'=M_{1}

(a'b)'=a+b'

Indexació de maxterms[modifica]

Per tal d'indexar maxterms ho podem fer de la manera contrària a la que hem seguit pels minterms. Hom assigna a cada maxterm un índex basat en el complement del nombre binari que representa. Per exemple, per a una funció de tres variables f(a, b, c) podem assignar $M_{6}$ (maxterm 6) al maxterm: $a'+b'+c$ . De manera similar, $M_{0}$ de tres variables hauria de ser $a+b+c$ , i $M_{7}$ és $a'+b'+c'$ .

Hom pot veure fàcilment que un maxterm només dona com a resultat 0 per a una única entrada de la funció lògica. Per exemple, el maxterm 5, $a'+b+c'$ , és fals només quan a i c són certs i b és fals; l'entrada a = 1, b = 0, c = 1 dona com a resultat zero.

Funció equivalent[modifica]

{\begin{array}{|c||c|c||c|}\hline n&a&b&f(a,b)\\\hline 0&0&0&1\\1&0&1&0\\2&1&0&0\\3&1&1&1\\\hline \end{array}}

Si tenim una taula de veritat d'una funció lògica f(a, b), és possible escriure la funció com a "producte de sumes". Per exemple, donada la taula de veritat de la dreta, observem que les files que tenen com a sortida 0 són la segona i la tercera. Llavors, podem escriure f com a producte de maxterms $M_{1}M_{2}$ .

Si volem verificar això:

f(a,b)=(a+b')(a'+b)

tindrem que la taula de veritat de la funció, calculant-la directament, serà la mateixa.

L'aplicació en un circuit d'interruptors és la de l'esquema, on es poden veure els dos interruptors superiors a i a', i els inferiors b' i b.

En primer lloc, tenim posats en paral·lel a i b', la qual cosa correspon a a+b', i a continuació a' i b en paral·lel, la qual cosa correspon a a'+b. Aquests dos circuits parcials posats en sèrie són equivalents a (a+b')(a'+b).