Que és el

Método de Karnaugh?

Mapa de Karnaugh

El método de Karnaugh convierte una expresión a otra más simplificada. En nuestro caso, convierte una suma de productos en otra mínima denominada Minimal Sum Product (MSP o suma de productos minimal).

Tiene como características:

- Un mínimo número de términos en la expresión.
- Un mínimo número de variables en cada término de dicha expresión.

Inicialmente poseemos una expresión booleana constituida por una suma de productos de variables, que pueden tomar únicamente los valores de cero [1] o uno. El resultado de esta expresión es un valor booleano para cada uno de los valores que tomen dichas variables. Dichos valores se van almacenando en una tabla de verdad como la que ilustramos en el siguiente ejemplo:


f (c, b, a) = c b a + c’ a’

Tabla verdad función

cba
f
000
1
001
0
010
1
011
0
011
0
100
0
101
0
111
1

Mapa de Karnaugh de la función


Podemos hacer una representación gráfica de dicha tabla de verdad, mediante la matriz que se encuentra al lado, denominada mapa de Karnaugh. Así los unos de la tabla de la verdad se corresponden con los unos en azul indicados en la matriz. Igualmente se corresponden los ceros. Cada valor en esta matriz recibe el nombre de implicante o Minterm.

La simplificación de expresiones lógicas mediante el mapa de Karnaugh utiliza un método gráfico basado en la Suma de Productos.

 

 

Lógica de Boole

El álgebra de Boole fue introducida por el matemático inglés George Boole en 1854, desarrollando un método simbólico para el análisis de la lógica humana en su tratado An Investigation of the Laws of Thought. Posteriormente en 1939, Claude E. Shannon, en sus tratado A Symbolic Analysis of Relay and Switching Circuits, aplicó el álgebra de Boole en el estudio de los circuitos eléctricos con dos estados posibles, denominados circuitos de conmutación. Estos estudios han proporcionado las bases matemáticas para el diseño de los circuitos básico digitales.

Una estructura matemática, como es el álgebra de Boole, se construye a partir de un conjunto de elementos sobre los que se definen unos operadores que permiten realizar operaciones en ellos, estableciendo unos postulados o axiomas que relacionan tanto al conjunto de elementos como al conjunto de operadores.

Álgebra de Boole bivalente

Dependiendo del conjunto elegido y de cómo se especifiquen las operaciones + y * se pueden definir numerosas álgebras de Boole. La de mayor interés en el diseño de circuitos digitales es el álgebra de Boole Bivalente o de conmutación, denominada así por estar definida sobre un conjunto de dos elementos B={0.1} y las operaciones suma lógica y producto lógico *.


Suma y producto lógico

ab
a+b
a*b
00
0
0
01
1
0
10
1
0
11
1
1

Este tipo de tablas en las que se expresa, en cada fila, el valor que toma la expresión para cada una de las posibles combinaciones de valores de sus variables, se denominan tabla de verdad.

Una variable es como un símbolo, por ejemplo, a, que representa a cualquiera de los elementos de un conjunto B sobre el que se ha definido el álgebra de Boole. Así en el álgebra de conmutación la variables a puede tomar los valores 0 y 1, de ahí que se le designe como variable binaria.

Una función booleana es una correspondencia entre Bn y B, de tal forma que a cada n-upla de Bn se le hace corresponder con un elemento de B. Matemáticamente se expresa:


f : Bn ? B
(a1, a2, …., an) ? a


Donde (a1, a2, …., an) pertenece a Bn.

Tanto a las variables como a las funciones booleanas se las conoce como variables o funciones lógicas, ya que, el álgebra de Boole es una teoría matemática usada para formalizar el pensamiento y de la qu se deriva la lógica simbólica.

Una función de conmutación o función lógica f es una función booleana definida en Bn, cuya imagen pertenece al conjunto B = {0,1}, siendo su valor igual al de una expresión algebraica de variables ilógicas unidad mediante las operaciones de suma lógica +, producto lógico * y el operador complemento.

Las funciones lógicas se representan como:

f = (a1, a2, …., an) = f(…c,b,a)

donde, el valor lógico de f depende las variables binarias: … c,b,a.

Entre las variables, el símbolo *, correspondiente a la operación producto lógico, puede ser omitido.

Otra forma de representar una función lógica es mediante una table, llamada tabla de verdad, que indique el valor que toma la función para cada una de las combinaciones de los valores de las variables de entrada.

La construcción de la tabla de verdad de una función se realiza representando en la columna de la izquierda, de la tabla, todas las posibles combinaciones de las variables de entrada y en la columna de la derecha los valores asignados a la función de salida f para cada combinación de las variables de entrada.

La función f

f(c, b, a) = c’ b’ a + c’ b a’+ c b a

tiene como tabla de verdad:

Tabla verdad función f(c, b, a)

cba
f
000
0
001
1
010
1
011
0
011
0
100
0
101
0
111
1

 

Calculando el valor que toma la función para cada una de las posibles combinaciones de valores de las variables de entrada y representándolo en una tabla, se obtiene su tabla de verdad. El número de posibles combinaciones de valores de las variables de entrada es 2n, siendo n el número de variables de entrada.

Dos funciones son equivalentes si ambas tienen la misma tabla de verdad y por lo tanto describen la misma función de conmutación.

Entre las múltiples expresiones algebraicas con las que se puede representar una función lógica, destacan dos tipos según que la expresión esté formada por:

- suma de productos, como por ejemplo:

g = g (c, b, a) = c b a + c’ a + c’ b a’

- productos de sumas, como por ejemplo:

k = k (c, b, a) = (b + a) (b’ + a) (c’ + b + a)

Un término canónico de una función lógica es todo producto o suma en el que aparecen todas las variables en su forma directa a o complementada a’. Por ejemplo, en una función de tres variables son términos canónicos, entre otro: c b a y c + b + a.

Los productos canónicos o minitérminos (Minterms) son los términos productos. Esta denominación se debe al hecho de que, este término, toma el valor 1 para una sola combinación de las variables de entrada, de ahí el prefijo mino.

A los términos suma se les llama sumas canónicas o maxitérminos (Maxtems) por el hecho de que , este término, toma el valor 1 tantas veces como lo hagan los sumandos que lo forman, de ahí el prefijo maxi.

Función canónica es una función formada exclusivamente por términos de sumas canónicas o bien de productos canónicos. Si esta función tiene n variables, cada uno de sus productos o sumas canónicas tendrá n variables. Como cada variable se puede representar en su forma directa o complementada, el número de productos canónicos posibles será 2n, al igual que el de sumas canónicas.

Ejemplo: Una función de tres variables tiene 23 = 8 términos: 8 Minterms y 8 Maxterms.

Aplicando el principio de dualidad, cada Maxterm se obtiene sumando las n variables en su forma directa si toman el valor 0 y complementada si tiene valor 1.

Los Minterms se representan por mi y los Maxterms por Mi, siendo el subíndice i igual al valor decimal del número binario que corresponde al término canónico.