Nov 162016

 

Si tenemos la siguiente función suma de productos:

f (A,B,C,D,E) = ⅀(0, 1, 2, 3, 4, 5, 6, 7,  16, 17, 18, 19, 20, 21, 22, 23, 27) = (ABCDE) + (ABCDE) + (ABCDE) + (ABCDE) + (ABCDE) + (ABCDE) + (ABCDE)  + (ABCDE)  + (ABCDE) + (ABCDE) + (ABCDE) + (ABCDE) + (ABCDE) + (ABCDE) + (ABCDE)  + (ABCDE) + (ABCDE)

El bit de menor peso es la variable E y el de mayor la A lo podríamos haber hecho al revés, es cuestión de adoptar un convenio en el que estemos cómodos con las letras escogidas y su orden.

La simplificación es parecida como con 4 variables, sin embargo, a la hora de encontrar casillas adyacentes, las casillas situadas en ambos mapas en la misma posición relativa se “tocan”.  Es decir, es como si el mapa de la izquierda estuviera situado sobre el de la derecha de forma que las casillas ABCD=0000 de ambos mapas son adyacentes y así con el resto de casillas cuyos valores ABCD sean iguales.

En el mapa de Karnaugh cada intersección de una fila y columna crea una celda única que le asignamos un número según el peso de las variables en la que este situada, en este ejemplo esta coloreado en rojo.

Valores numéricos para los mapas de Karnaugh de 5 variables

Valores numéricos para las casillas del mapa de Karnaugh de 5 variables

Rellenamos las celdas del mapa con los términos de la función a simplificar.

Ejemplo de Karnaugh 5 variables

Ejemplo de Karnaugh 5 variables

La función f (A,B,C,D,E) = ⅀(0, 1, 2, 3, 4, 5, 6, 7,  16, 17, 18, 19, 20, 21, 22, 23, 27) quedará simplificada como:

f = ACDE + B

 

Tabla de la verdad de la función 
#ABCDEf(A,B,C,D,E)
0000001
1000011
2000101
3000111
4001001
5001011
6001101
7001111
8010000
9010010
10010100
11010110
12011000
13011010
14011100
15011110
16100001
17100011
18100101
19100111
20101001
21101011
22101101
23101111
24110000
25110010
26110100
27110111
28111000
29111010
30111100
31111110


Nov 082016

 

El metodo de Karnaugh es un sistema visual utilizado para la simplificación de funciones algebraicas Booleanas. Es también conocido como diagrama de Veitch o tabla de Karnaugh y consiste en una representación bidimensional de la tabla de la verdad de la función a simplificar.

Cuando agrupamos los “1” hay que tener en cuenta:

  • Debemos utilizar todos los unos del mapa.
  • Hay que crear el menor número de grupos incluyendo todos los unos.
  • Los unos pueden estar en varios grupos.
  • El número de unos dentro de un grupo debe ser cualquier potencia de 2.
  • Cuanto más grande sea un grupo, la simplificación de la función será mejor.
  • Los grupos pueden ser de diferentes tamaños, siempre potencia de 2.
  • Al hacer la simplificación agrupando unos se dice que estamos obteniendo la suma de productos la utilizada en los ejemplos, y si escogemos los ceros se convierte en un producto de sumas.

En el mapa de Karnaugh se muestran todos los posibles valores de la salida para cada combinación posible de las entradas, en cada celda de la tabla se representa un valor binario de las entradas.

Mapas de Karnaugh

Mapas de Karnaugh

 

El número de celdas de un mapa de Karnaugh es igual al número de posibles combinaciones de los valores de las variables de entrada. Por ejemplo, un mapa de Karnaugh de 3 variables tendría 23 = 8 celdas y uno de 4 variables tendría 24 = 16 celdas.

Utilizar mas de 5 variables resulta mas compleja la simplificación hallando los grupos de unos, y puede derivar en errores, hay programas que nos pueden ayudar para hacer esta simplificación a este nivel.

El orden dado a las variables por ejemplo en la tabla de 4 variables no tiene porque ser el mismo, podemos darle el orden que queramos y utilizar las letras que nos gusten mas.

Las celdas de un mapa de Karnaugh se disponen de manera que entre dos celdas adyacentes sólo cambie el valor de una única variable. Cada celda es adyacente a las que están situadas inmediatamente junto a cualquiera de sus cuatro lados excluyendo las diagonales.

Además el mapa lo podemos imaginar como grabado en un cilindro horizontalmente y verticalmente, las celdas de la fila inferior son adyacentes a la superior y las celdas de la columna izquierda son adyacentes a la derecha y viceversa.

Una vez tengamos resuelto el mapa de Karnaugh podemos implementar la función minimizada con puertas AND y OR para llevarla a la práctica.

 

Ejercicios de simplificación de funciones por Karnaugh

1.- Si tenemos la siguiente función suma de productos:

f (A,B,C) = ⅀(0,3,5,7) = (ABC) + (ABC) + (ABC) + (ABC)

Tabla de la verdad de la función 
#ABCf(A,B,C)
00001
10010
20100
30111
41000
51011
61100
71111

Pasaremos cada término a una tabla de la verdad, asignando una letra según el peso de cada bit que interviene en la función, en este caso A B C, y si el termino nos aparece en la función le ponemos un uno sino un cero.

Una vez creada la tabla de la verdad, rellenamos las celdas del mapa de Karnaugh.

 

Mapa de Karnaugh

Mapa de Karnaugh

 

 

En el mapa de Karnaugh hacemos la agrupación de unos contiguos, consiguiendo dos grupos y un uno suelto, quedando la función simplificada o minimizada como:

f = AC + BC +ABC

 

 

 

 


2.- Si tenemos la siguiente función suma de productos:

f (A,B,C) = ⅀(0,2,4,6) = (ABC) + ( ABC) + (ABC) + (ABC)

Tabla de la verdad de la función 
#ABCf(A,B,C)
00001
10010
20101
30110
41001
51010
61101
71110

Pasaremos cada término a una tabla de la verdad, asignando una letra según el peso de cada bit que interviene en la función, en este caso A B C, y si el termino nos aparece en la función le ponemos un uno sino un cero.

Una vez creada la tabla de la verdad, rellenamos las celdas del mapa de Karnaugh.

 

Mapa de Karnaugh

Mapa de Karnaugh

En el mapa de Karnaugh hacemos la agrupación de unos contiguos, consiguiendo un grupo, quedando la función simplificada o minimizada como:

f = C

Si nos fijamos en la tabla de la verdad vemos que cada vez que C vale 0 la función es 1 validando la función minimizada.

 

 

 

 


3.- Si tenemos la siguiente función suma de productos:

f (A,B,C) = ⅀(0,4,5,6,7) = (ABC) + (ABC) + (ABC) + (ABC) + (ABC)

Tabla de la verdad de la función 
#ABCf(A,B,C)
00001
10010
20100
30110
41001
51011
61101
71111

Pasaremos cada término a una tabla de la verdad, asignando una letra según el peso de cada bit que interviene en la función, en este caso A B C, y si el termino nos aparece en la función le ponemos un uno sino un cero.

Una vez creada la tabla de la verdad, rellenamos las celdas del mapa de Karnaugh.

 

Mapa de Karnaugh

Mapa de Karnaugh

En el mapa de Karnaugh hacemos la agrupación de unos contiguos, consiguiendo un grupo de cuatro unos y otro de dos, quedando la función simplificada o minimizada como:

f = A + BC

Mirando la tabla de la verdad podemos volver a corroborar los resultados obtenidos.

 

 

 

 


4.- Si tenemos la siguiente función suma de productos:

f (A,B,C,D) = ⅀(0,1,2,3,5,7,8,9,10,11,14) = (ABCD) + (ABCD) + (ABCD) + (ABCD) + (ABCD) + (ABCD) + (ABCD) + (ABCD) + (ABCD) + (ABCD) + (ABCD)

Tabla de la verdad de la función 
#ABCDf(A,B,C,D)
000001
100011
200101
300111
401000
501011
601100
701111
810001
910011
1010101
1110111
1211000
1311010
1411101
1511110

Pasaremos cada término a una tabla de la verdad, asignando una letra según el peso de cada bit que interviene en la función, en este caso A B C, y si el termino nos aparece en la función le ponemos un uno sino un cero.

Una vez creada la tabla de la verdad, rellenamos las celdas del mapa de Karnaugh.

 

Mapa de Karnaugh 4 variables

Mapa de Karnaugh 4 variables

En el mapa de Karnaugh hacemos la agrupación de unos contiguos, consiguiendo un grupo de ocho unos, otro de cuatro y otro de dos, quedando la función simplificada o minimizada como:

f = B  + A+ACD

Con 4 variables el proceso se complica un poco mas, pero si miramos la tabla de la verdad veremos que la simplificación es correcta.

 

 


 

Para 5 variables duplicaríamos la tabla y así sucesivamente para mas variables, quedando superpuestas una encima de la otra, los grupos se forman buscando la adyacencia entre todas las tablas.

Ejemplo de resolución de Karnaugh con 5 variables.

En la web hay programas comerciales como Gorgeous Karnaugh que permite simplificar funciones de hasta 16 variables generando los mapas de Karnaugh y los diagramas lógicos, un buen programa que se puede alquilar o comprar.



Ene 172014

 

George Boole

Matemático británico especializado en temas de lógica, nacido el 2 de noviembre de 1815 y murió el 8 de diciembre de 1864.

Como inventor del álgebra de Boole, marcaría los fundamentos de la aritmética computacional moderna, Boole es considerado como uno de los fundadores del campo de las Ciencias de la Computación. En 1854 publicó “An Investigation of the Laws of Thought” en el que desarrollaba un sistema de reglas que le permitían expresar, manipular y simplificar problemas lógicos y filosóficos cuyos argumentos admiten dos estados (verdadero o falso) por procedimientos matemáticos.

Gracias a el se desarrollo toda la matemática que hace posible hacer funcionar los computadores de hoy en día.

Definición de álgebra de Boole

Sea K un conjunto en el cual se definen dos operaciones binarias, + y *, y una operación unitaria denotada   ; sean 0 y 1 dos elementos diferentes de K. Tendremos la siguiente séxtupla:

(K, +, *, , 0, 1)

Se denomina álgebra de Boole si se cumplen los siguientes axiomas (proposiciones que se consideran evidentes y se aceptan sin requerir demostración previa) para cualesquiera de los elementos a, b, c del conjunto K:

Conmutatividad:

a + b = b + a
a * b = b * a

Distributividad:

a + (b * c) = (a + b) * (a + c)
a * (b + c) = (a * b) + (a * c)

Identidad:

a + 0 = a
a * 1 = a

Complemento:

a + a = 1
a * a = 0

Terminología y convenciones:

  • Las operaciones + y * se denominan suma y producto , respectivamente.
  • La operación a se denomina complemento de a .
  • El elemento 0 se denomina elemento cero (neutro respecto de la suma).
  • El elemento 1 se denomina elemento unidad (neutro respecto del producto).
  • Por convención, omitimos el símbolo *, usándose en su lugar la yuxtaposición, como en el siguiente ejemplo:  a + bc = ( a + b ) ( a + c ).
  • Por convención, establecemos que + es más fuerte que *,  y * es más fuerte que   

por ejemplo: Continúa leyendo »