Funció booleana
Es denomina funció lògica o booleana aquella funció matemàtica les variables de la qual són binàries i el resultat es calcula aplicant-los els operadors de l'àlgebra de Boole: les portes lògiques, porta O (OR), suma lògica (+), porta I (AND), producte lògic (·) o negació (NOT).
Maneres de representació[modifica]
Hi ha diferents formes de representar una funció lògica, entre les quals es poden destacar les següents:
- Algebraica
- Taula de veritat
- Numèrica
- Gràfica
L'ús d'una o una altra, dependrà de les necessitats concretes en cada cas.
Algebraica[modifica]
Es fa servir quan es realitzen operacions algebraiques. A continuació hi ha un exemple amb diferents formes com es pot expressar algebraicament una mateixa funció de tres variables.
- a) F = [(A + BC’)’ + ABC]’ + AB’C
- b) F = A’BC’ + AB’C’ + AB’C + ABC’
- c) F = (A + B + C)(A + B + C’)(A + B’ + C’)(A’ + B’ + C’)
- d) F = BC’ + AB’
- e) F = (A + B)(B’ + C’)
- f) F = [(BC’)’ · (AB’)’]’
- g) F = [(A + B)’ + (B’ + C’)’]’
L'expressió a) pot procedir d'un problema lògic plantejat o del pas d'unes especificacions a llenguatge algebraic. Les formes b) i c) reben el nom expressions canòniques: de suma de productes (sum-of-products, SOp, en anglès), la b), i de productes de sumes (product-of-sums, POST, en anglès), la c); la seva característica principal és l'aparició de cada una de les variables (A, B i C) en cada un dels sumands o productes. Les d) i e) són funcions simplificades, és a dir, reduït a la seva mínima expressió. Les dues últimes expressions tenen la particularitat que fan servir exclusivament funcions No-I (Nand), la f), o funcions No-O (NOR), la g).
Per taula de veritat[modifica]
Una taula de veritat conté tots els valors possibles d'una funció lògica depenent del valor de les seves variables. El nombre de combinacions possibles per a una funció de n variables és 2n.
Una funció lògica pot representar-se algebraicament de diferents formes, però només té una taula de veritat. La següent taula correspon a la funció lògica del punt anterior.
| A | B | C | F |
|---|---|---|---|
La forma més còmoda per veure l'equivalència entre una taula de veritat i una expressió algebraica és quan aquesta última es dona en la seva forma canònica. La funció canònica de suma de productes (o forma canònica disjuntiva):
- F = A'Bc' + Ab'C' + Ab'C + Abc'
Indica que serà 1 quan ho sigui un dels seus sumands, el que significa que tindrà quatre combinacions que ho seran (010 per a A'BC', 100 per a AB'C', 101 per a AB'C i 110 per a ABC') sent la resta de combinacions 0. Amb la funció canònica de producte de sumes (o forma canònica conjuntiva) es pot raonar de forma anàloga, però en aquest cas observant que la funció serà 0 quan ho sigui un dels seus productes.
També és fàcil obtenir la taula de veritat a partir de la funció simplificada, però no a la inversa.
Numèrica[modifica]
La representació numèrica és una forma simplificada de representar les expressions canòniques. Si es considera el criteri de substituir una variable sense negar per un 1 i una negada per un 0, es pot representar el terme, ja sigui una summa o un producte, per un nombre decimal equivalent al valor binari de la combinació. Per exemple, els següents termes canònics es representaran:
- AB'CD = 1011₂ = 1110
- A' + B + C' + D' = 0100₂ = 410
Per representar una funció canònica en suma de productes es fa servir el símbol Σn (sigma) i en producte de sumes Πn (pi), on n indicarà el nombre de variables. Així, la representació numèrica corresponent a la taula de veritat del punt anterior quedarà:
- F = Σ₃(2, 4, 5, 6) = Π₃(0, 1, 3, 7)
Matemàticament es demostra, que per a tot terme i d'una funció, es compleix la següent equació:
- F = [Σn(i)]' = Πn(2n-1-i)
Per exemple es pot fer servirr aquesta igualtat per obtenir el producte de sumes a partir de la suma de productes de l'exemple anterior:
- F = Σ₃(2, 4, 5, 6) = [Σ₃(2, 4, 5, 6)]' ' = [Σ₃(0, 1, 3, 7)]' = Π₃(0, 4, 6, 7)
Gràfica[modifica]
La representació gràfica és la que es fa servir en circuits i esquemes electrònics. A la següent figura es representen gràficament dues funcions algebraiques, una amb símbols no normalitzats, superior, i l'altra amb normalitzats, inferior (vegeu els símbols de les portes lògiques)
Mètodes de simplificació[modifica]
S'entén per simplificar una funció lògica l'obtenció de la seva mínima expressió. A l'hora d'implementar físicament una funció lògica se simplifica per reduir la complexitat del circuit.
A continuació s'indiquen les maneres més usuals de simplificar una funció lògica.
Algebraica[modifica]
Per a la simplificació per aquest mètode no n'hi ha prou amb conèixer totes les propietats i teoremes de l'àlgebra de boole, a més s'ha de desenvolupar una certa habilitat logicomatemàtica que s'adquireix fonamentalment amb l'experiència.
Com a exemple se simplificarà la següent funció:
- F = A'C' + Abc + Bc' + A'B'C + A'Bc
Observant cada un dels sumands es pot veure que hi ha factors comuns en els sumands 2n amb 5è i 4t amb 5è que comporten simplificació:
- F = A’C’ + BC’ + BC(A + A’) + A’C(B + B’)
Observeu que el terme 5è s'ha pres dues vegades, d'acord amb la propietat que A + A´ =1. Aplicant les propietats de l'àlgebra de Boole, queda
- F = A’C’ + BC’ + BC + A’C
Repetint el procés
- F = A’(C’ + C) + B(C’ + C) = A’ + B
No sempre les funcions són tan fàcils de simplificar com l'anterior. El mètode algebraic, en general, no resulta còmode per als no experts, que, una vegada simplificada una equació poden quedar seriosos dubtes d'haver aconseguit la màxima simplificació.
Gràfic de Karnaugh[modifica]
Aquest mètode consisteix a formar diagrames de 2n quadres, sent n el nombre de variables. Cada quadre representa una de les diferents combinacions possibles i es disposen de tal manera que es pot passar d'un quadre a un altre en les direccions horitzontal o vertical, canviant únicament una variable, ja sigui en forma negada o directa.
Aquest mètode s'empra fonamentalment per simplificar funcions de fins a quatre variables. Per a un nombre superior es fan servir altres mètodes com el numèric. A continuació hi ha els diagrames, també anomenats mapes de Karnaugh, per a dos, tres i quatre variables.
És pràctica habitual numerar cada cel·la amb el nombre decimal corresponent al terme canònic que allotgi, per facilitar el treball a l'hora de plasmar una funció canònica.
Per simplificar una funció lògica pel mètode de Karnaugh se seguiran els següents passos:
1r) Es dibuixa el diagrama corresponent al nombre de variables de la funció a simplificar.
2n) Es col·loca un 1 en els quadres corresponents als termes canònics que formen part de la funció.
3r) S'agrupen mitjançant llaços els uns de caselles adjacents seguint estrictament les següents regles:
- a) Dues caselles són adjacents quan es diferencien únicament en l'estat d'una sola variable.
- b) Cada llaç ha de contenir el major nombre d'uns possible, sempre que sigui potència de dos (1, 2, 4, etc.)
- c) Els llaços poden quedar superposats i no importa que hi hagi quadrícules que pertanyin a dos o a més llaços diferents.
- d) s'ha de tractar d'aconseguir el menor nombre de llaços amb el major nombre d'uns possible.
4t) La funció simplificada tindrà tants termes com llaços posseeixi el diagrama. Cada terme s'obté eliminant la o les variables que canviïn d'estat al mateix llaç.
Com a exemple es realitzen dues simplificacions d'una mateixa funció a partir de les seves dues formes canòniques:
- F = Σ₃(0,2,3,4,7) = Π₃(1,2,6)
D'acord amb els passos vistos anteriorment, el diagrama de cada funció quedarà de la següent manera:
framed|center|Simplificació d'una funció de tres variables
La funció simplificada tindrà tres sumands en un cas i dos productes en l'altre. Si observant en el mapa corresponent a la suma de productes, es veu que al llaç 1 canvia la variable A (a la cel·la 0 és negada i en la 4 directa), al llaç 2 és la C i al llaç 3 torna a ser A. per tant, l'equació simplificada és:
- F = B’C’ + A’B + BC
Raonant de manera similar al mapa de productes de sumes, quedarà:
- F = (B + C')(A' + B' + C)
Numèric de Quine-McCluskey[modifica]
L'algorisme de Quine-McCluskey permet la simplificació de funcions lògiques de qualsevol nombre de variables i és el que s'utilitza per dissenyar aplicacions informàtiques en les quals es necessiti obtenir funcions simplificades.
A continuació s'indiquen els passos a seguir en aquest mètode a partir d'un exemple.
1r) s'expressa la funció a simplificar en la seva forma canònica de suma de productes.
Sigui la següent funció a simplificar:
- F = S₄ (0,1,2,3,5,9,11,12,13,15)
2n) Es forma una taula amb el valor decimal de la combinació, l'estat de les variables i l'índex (nombre d'uns que conté l'estat de les variables).
| Comb. | Estat | Índex |
|---|---|---|
3r) S'agrupen les combinacions els estats de les quals difereixen en una sola variable, substituint-la per un guió baix (_). Les combinacions utilitzades es marquen amb una (X). Cal fixar-se en les combinacions la diferència de les quals entre els seus respectius índexs és la unitat.
4t) Es repeteix el procés anterior les vegades que siguin necessàries i es van eliminant estats idèntics.
5è) Es forma una taula amb les combinacions finals i les no agrupades. Es prenen com files les combinacions finals i les no agrupades i com columnes els valors decimals de les esmentades combinacions. Cada cel·la que contingui el valor decimal d'una combinació es marca amb (X). A continuació se cerquen aquelles columnes amb una sola X; les seves combinacions seran essencials. Finalment es prenen aquelles combinacions dels valors decimals no seleccionats, tenint precaució de no prendre aquelles combinacions els valors decimals de les quals hagin estat presos ja en altres combinacions. La funció simplificada final ve donada per les combinacions essencials i aquestes últimes.
Funcions incompletes[modifica]
Fins ara totes les funcions estudiades tenen definit un valor lògic, 0 o 1, per a cada una de les possibles combinacions. Aquestes funcions es denominen completes o totalment definides. També existeixen funcions amb una o diverses combinacions no definides, anomenades funcions incompletes. Aquesta situació pot ser gegut a les dues causes següents:
- Hi ha combinacions d'entrada que no existeixen, per la qual cosa a la sortida se li pot assignar indistintament el valor 0 o l'1.
- En certes combinacions d'entrada la sortida del sistema lògic està inhibida, sent per tant el seu valor indiferent.
A la taula de veritat d'una funció incompleta, els termes indiferents es designen mitjançant una (X). Quant a la forma canònica se separen els termes definits dels que no ho són (indicats mitjançant el símbol φ).
A l'hora de simplificar una funció incompleta, els termes indiferents serviran com a "comodins" a l'hora de prendre els llaços, això és, si interessa que sigui un 1 perquè així el llaç és major, es pren com 1, i en cas contrari com 0.