Funció booleana

En matemàtiques, una funció booleana és una funció que el seu domini són les paraulas conformades pels valors binarios 0 o 1 ("fals" o "verdader", respectivament), i que el seu codominio són abdós valors 0 i 1.

Formalment, són les funcions de la forma ƒ: Bⁿ → B, a on B = {0,1} i n un sancer no negatiu corresponent a l'aridad de la funció.

Modos de representació

Existixen distintes formes de representar una funció llògica, entre les que podem destacar les següents:

L'us d'una o una atra dependrà de cada cas.

Algebraica

S'utilisa quan es realisen operacions algebraiques. A continuació s'oferix un eixemple en distintes formes en les que es pot expressar algebraicamente una mateixa funció de tres variables.

F = [(A + BC’)’ + ABC]’ + AB’C
F = A’BC’ + AB’C’ + AB’C + ABC’
F = (A + B + C)(A + B + C’)(A + B’ + C’)(A’ + B’ + C’)
F = BC’ + AB’
F = (A + B)(B’ + C’)
F = [(BC’)’(CB)´ (AB’)’]’
F = [(A + B)’ + (B’ + C’)’]’

L'expressió 1. pot procedir d'un problema llògic plantejat o del pas d'unes especificacions a llenguage algebraic. Les formes 2. i 3. reben el nom expressions canòniques: de suma de productes (sum-of-products, SOP, en anglés), la 2., i de productes de sumes (product-of-sums, POS, en anglés), la 3.; la seua característica principal és l'aparició de cada una de les variables (A, B i C) en cada u dels sumants o productes.

Per taula de veres

AP

\begin{matrix} A & B & C & F (A, B, C) \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{matrix}

Una taula de veres conté tots els valors possibles d'una funció llògica depenent del valor dels seus variables. El número de combinacions possibles per a una funció de n variables vindrà dau per 2ⁿ. Una funció llògica pot representar-se algebraicamente de distintes formes com acabem de vore, pero solament té una taula de veres. La següent taula correspon a la funció llògica del punt anterior.

La forma més cómoda per a vore l'equivalència entre una taula de veres i una expressió algebraica és quan esta última es dona en la seua forma canònica. Aixina, la funció canònica de suma de productes (o forma canònica disyuntiva)

F = A’BC’ + AB’C’ + AB’C + ABC’

nos indica que serà 1 quan lo siga un dels seus sumants, lo que significa que tindrà per lo tant quatre combinacions que ho seran (010 para A’BC’, 100 per a AB’C’, 101 per a AB’C i 110 per a ABC’) sent el restant de combinacions 0. En la funció canònica de producte de sumes (o forma canònica conjuntiva) es pot raonar de forma anàloga, pero en este cas observant que la funció serà 0 quan lo siga un dels seus productes.

També és fàcil obtindre la taula de veres a partir de la funció simplificada, pero no aixina a l'inversa.

Numèrica

La representació numèrica és una forma simplificada de representar les expressions canòniques. Si considerem el criteri de substituir una variable sense negar per un 1 i una negada per un 0, podrem representar el terme, ya siga una suma o un producte, per un número decimal equivalent al valor binario de la combinació. Per eixemple, els següents térmens canònics es representaran del següent modo (observe que es pren l'orde d'a D com de major a menor pes):

A B^{'} C D = 101 1_{2} = 1 1_{10}

A^{'} + B + C^{'} = 010 0_{2} = 4_{10}

Per a representar una funció canònica en suma de productes utilisarem el símbol $\sum_{n}$ (sigma) i en producte de sumes $\prod_{n}$ (pi), a on n indicarà el número de variables. Aixina, la representació numèrica corresponent a la taula de veres del punt anterior quedarà com:

F = \sum_{3} (2, 4, 5, 6) = \prod_{3} (0, 1, 3, 7)

Matemàticament es demostra, que para tot terme i d'una funció, es complix la següent equació:

F = {[\sum_{i} (i)]}^{'} = \prod_{n} (2^{n - 1} - i)

A modo d'eixemple es pot utilisar esta igualtat per a obtindre el producte de sumes a partir de la suma de productes de l'eixemple anterior:

F = \sum_{3} (2, 4, 5, 6) = {[\sum_{4} (2, 4, 5, 6)]}^{''} = {[\sum_{4} (0, 1, 3, 7)]}^{'} = \prod_{3} (0, 1, 3, 7)

Gràfica

La representació gràfica és la que s'utilisa en circuits i esquemes electrònics. En la següent figura es representen gràficament dos funcions algebraiques, una en símbols no normalisats, superior, i l'atra en normalisats, inferior (vegen-se els símbols de les portes llògiques)

Métodos de simplificació

Per simplificació d'una funció llògica s'entén l'obtenció de la seua mínima expressió. A l'hora d'implementar físicament una funció llògica se sol simplificar per a reduir aixina la complexitat del circuit.

A continuació s'indiquen els modos més usuals de simplificar una funció llògica.

Algebraic

AP Per a la simplificació per este método no només bastarà en conéixer totes les propietats i teoremes de l'àlgebra de Boole, ademés es deu desenrollar una certa habilitat llògic-matemàtica que s'adquirix fonamentalment en l'experiència.

Com a eixemple se simplificarà la següent funció:

F = AB+ A(B+C)+ B(B + C)

Observant cada u dels sumant podem vore que hi ha factors comuns en els sumants 2º en 5º i 4º en 5º que comporten simplificació:

F = A’C’ + BC’ + BC(A + A’) + A’C(B + B’)

Note que el terme 5º s'ha pres dos voltes, d'acort en la propietat que diu que A + A = A. Aplicant les propietats de l'àlgebra de Boole (A + A' = 1 i A . 1 = A), queda

F = A’C’ + BC’ + BC + A’C

Repetint novament 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étodo algebraic, per lo general, no resulta cómodo per als no experts, als quals, una volta simplificada una equació li poden quedar sérios dubtes d'haver conseguit la màxima simplificació.

Mapa de Karnaugh

AP Este método consistix en formar diagrames de 2ⁿ quadros, sent n el número de variables. Cada quadro representa una de les diferents combinacions possibles i es disponen de tal forma que es pot passar d'un quadro a un atre en les direccions horisontal o vertical, canviant únicament una variable, ya siga en forma negada o directa.

Este método s'ampra fonamentalment per a simplificar funcions de fins a quatre variables. Per a un número superior utilisen atres métodos com el numèric. A continuació poden observar-se els diagrames, també cridats mapes de Karnaugh, per a dos, tres i quatre variables.

Mapes de Karnaugh per a dos, tres i quatre variables

És una pràctica comuna numerar cada cela en l'número decimal corresponent al terme canònic que alberc, per a facilitar el treball a l'hora de plasmar una funció canònica.

Per a simplificar una funció llògica pel método de Karnaugh se seguiran els següents passos:

Es dibuixa el diagrama corresponent al número de variables de la funció a simplificar.
Es coloca un 1 en els quadros corresponents als térmens canònics que formen part de la funció.
S'agrupen per mig de llaços els uns de caselles adjacents seguint estrictament les següents regles:
1. Dos caselles són adjacents quan es diferencien únicament en l'estat d'una sola variable.
2. Cada llaç deu contindre el major número d'uns possible, sempre que dit número siga potència de dos (1, 2, 4, etc.)
3. Els llaços poden quedar superposts i no importa que hi haja cuadrículas que pertanyguen a dos o més llaços diferents.
4. Es deu tractar de conseguir el menor número de llaços en el major número d'uns possible.
La funció simplificada tindrà tants térmens com a llaços posseïxca el diagrama. Cada terme s'obté eliminant l'o les variables que canvien d'estat en el mateix llaç.

A modo d'eixemple es realisen dos simplificació d'una mateixa funció a partir de les seues dos formes canòniques:

F = \sum_{3} (0, 2, 3, 4, 7) = \prod_{3} (1, 5, 6)

D'acort en els passos vists anteriorment, el diagrama de cada funció quedarà del següent modo:

Simplificació d'una funció de tres variables

La funció simplificada tindrà tres sumants en un cas i dos productes en l'atre. Si nos fixem en el mapa corresponent a la suma de productes, observem que en el llaç 1 canvia la variable A (en la cela 0 és negada i en la 4 directa), en el llaç 2 és la C i en el llaç 3 torna a ser A. per lo tant, l'equació simplificada és:

F = B^{'} C^{'} + A^{'} B + B C

Raonant de modo similar en el mapa de productes de sumes, nos quedarà lo següent:

F = (B + C^{'}) (A^{'} + B^{'} + C)

Numèric de Quine-McCluskey

Artícul principal → Algoritme Quine–McCluskey.

L'algoritme Quine-McCluskey permet la simplificació de funcions llògiques de qualsevol número de variables i és el que s'utilisa per a dissenyar aplicacions informàtiques en les que es necessite obtindre funcions simplificades.

A continuació s'indiquen els passos a seguir en este método a partir d'un eixemple.

S'expressa la funció a simplificar en la seua forma canònica de suma de productes.
Siga la següent funció a simplificar:

$F = S_{4} (0, 1, 2, 3, 5, 9, 11, 12, 13, 15)$

Es forma una taula en el valor decimal de la combinació, l'estat de les variables i l'índex (número d'uns que conté l'estat de les variables).

Comb.	Estat	Índex
0	0000	0
1	0001	1
2	0010	1
3	0011	2
5	0101	2
9	1001	2
11	1011	3
12	1100	2
13	1101	3
15	1111	4

S'agrupen les combinacions els estats de les quals diferixen en una sola variable, substituint-la per un guion baix (_). Les combinacions utilisades es marquen en un aspa (X). Cal fixar-se en les combinacions la diferència de les quals entre els seus respectius índexs és l'unitat.

Agrupació de les combinacions
Comb.	Estat	Índex	Comb.	Estat	Índex
0 X	0000	0	0,1	000_	0
1 X	0001	1	0,2	00_0	0
2 X	0010	1	1,3	00_1	1
3 X	0011	2	1,5	0_01	1
5 X	0101	2	1,9	_001	1
9 X	1001	2	3,11	_011	2
11 X	1011	3	5,13	_101	2
12 X	1100	2	9,11	10_1	2
13 X	1101	3	9,13	1_01	2
15 X	1111	4	11,15	1_11	3
			12,13	110_	2
			13,15	11_1	3

Es repetix el procés anterior les voltes que siguen necessàries i es van eliminant estats idèntics.

Es forma una taula en les combinacions finals i les no agrupades. Es prenen com a files les combinacions finals i les no agrupades i com a columnes els valors decimals de dites combinacions. Cada cela que continga el valor decimal d'una combinació es marca en un aspa. A continuació nos fixem en aquelles columnes en una sola aspa; les seues 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 hagen segut ya presos en atres combinacions. La funció simplificada final ve donada per les combinacions essencials i estes últimes.

Vore també

Este artícul conté una traducció derivada de «Función booleana» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.