Forma canònica (àlgebra de Boole)

Plantilla:Falten referències 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

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, $a b c$ , $a b^{'} c$ i $a b c^{'}$ són exemples de minterms per a una funció booleana amb les tres variables $a$ , $b$ i $c$ .

Indexació de minterms

\begin{matrix} n & m & a & b & c \\ 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 \end{matrix}

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 $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 dona com a resultat 1.

Plantilla:Clear

Funció equivalent

\begin{matrix} n & a & b & f (a, b) \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 2 & 1 & 0 & 0 \\ 3 & 1 & 1 & 1 \end{matrix}

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^{'}) + (a b)

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 aPlantilla:' i bPlantilla:' posats en sèrie, la qual cosa és equivalent a aPlantilla:'b Plantilla:'; 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.

Plantilla:Clear

Termes màxims

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ó

\begin{matrix} n & M & m & a & b & c \\ 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 \end{matrix}

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

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

\begin{matrix} n & a & b & f (a, b) \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 2 & 1 & 0 & 0 \\ 3 & 1 & 1 & 1 \end{matrix}

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 aPlantilla:', i els inferiors bPlantilla:' i b.

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