Forma canònica (àlgebra de Boole)

De Viquipèdia
Dreceres ràpides: navegació, cerca

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 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 coma conjunció lògica (AND) de maxterms.

Termes mínims[modifica | modifica el codi]

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 | modifica el codi]


   \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'b c'& 0 & 1 & 0 \\
      3 & m_3= & a'b c & 0 & 1 & 1 \\
      4 & m_4= & a b'c'& 1 & 0 & 0 \\
      5 & m_5= & a b'c & 1 & 0 & 1 \\
      6 & m_6= & a b c'& 1 & 1 & 0 \\
      7 & m_7= & a b c & 1 & 1 & 1 \\
      \hline
   \end{array}

En general, hom assigna a cada minterm (escrivint les variables que el composen 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  a b c' , i anomenem l'expressió  m_6 . Llavors  m_0 de tres variables és  a' b' c' i  m_7 hauria de ser  a b c , 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,  a b' c és cert només quan a i c són certs i b és fals; l'entrada a = 1, b = 0, c = 1 dóna com a resultat 1.


Funció equivalent[modifica | modifica el codi]


   \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.

Gràfic Gràfic Gràfic Gràfic Gràfic
Gràfic Gràfic Gràfic Gràfic Gràfic

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 | modifica el codi]

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 | modifica el codi]


   \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'b c'& 0 & 1 & 0 \\
      3 & M_3= & a + b'+ c'& m_3= & a'b c & 0 & 1 & 1 \\
      4 & M_4= & a'+ b + c & m_4= & a b'c'& 1 & 0 & 0 \\
      5 & M_5= & a'+ b + c'& m_5= & a b'c & 1 & 0 & 1 \\
      6 & M_6= & a'+ b'+ c & m_6= & a b c'& 1 & 1 & 0 \\
      7 & M_7= & a'+ b'+ c'& m_7= & a b c & 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 | modifica el codi]

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 forma 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 dóna 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 dóna com a resultat zero.

Funció equivalent[modifica | modifica el codi]


   \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.

Gràfic Gràfic Gràfic Gràfic Gràfic Gràfic
Gràfic Gràfic Gràfic Gràfic Gràfic Gràfic

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).

Aquest circuit està tancat només en dues de les quatre combinacions possibles.


 Ent. \, Gràfic Gràfic Gràfic Gràfic
 Sort. \, Gràfic Gràfic Gràfic Gràfic
Gràfic Gràfic Gràfic Gràfic
Gràfic Gràfic Gràfic Gràfic
Gràfic Gràfic Gràfic Gràfic

Aquest circuit i l'anterior són clarament diferents, però tots dos corresponen a la mateixa taula de veritat i, per tant, són equivalents.

Encara que partim de la mateixa expressió booleana, hom pot realitzar diferents configuracions equivalents, com podem veure en aquesta segona figura.

Es pot demostrar l'equivalència, simplificant la funció, partint de:

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

Realitzant les multiplicacions, tenim:

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

Simplificant:

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

amb la qual cosa tenim la funció obtinguda per minterms.

Vegeu també[modifica | modifica el codi]