martes, 12 de marzo de 2013

VIDEOS Y TUTORIALES DE ALGEBRA BOOLEANA
LOGICA Y PROGRAMACION
DOCENTE JUAN GUILLERMO NUÑEZ OSUNA



Estos videos sirven como referente para el trabajo
Video tutorial Mapas Karnaugh
Clara Monsalve Rios·


Explicación de cómo elaborar diagramas de escalera con una metodología

Javier Abonza
Videos sobre Método de Quine-Mclusskey


Metodo de Quine McCluskey Matemáticas Discretas Parte 2 


Método de simplificación de Quine McCluskey primera parte




Algoritmo Quine–McCluskey

 

 

M´ETODO DE QUINE-McCLUSKEY TUTORIAL VIDEO.. 




El Algoritmo Quine–McCluskey es un método de simplificación defunciones booleanas desarrollado por Willard Van Orman Quine y Edward J. McCluskey. Es funcionalmente idéntico a la utilización del Mapa de karnaugh, pero su forma tabular lo hace más eficiente para su implementación en lenguajes computacionales, y provee un método determinístico de conseguir la mínima expresión de una función booleana.

Pasos

El método consta de dos pasos:
  1. Encontrar todos los implicantes primos de la función.
  2. Usar esos implicantes en una tabla de implicantes primos para encontrar los implicantes primos esenciales, los cuales son necesarios y suficientes para generar la función.

Complejidad

Aunque es más práctico que el mapa de Karnaugh, cuando se trata de trabajar con más de cuatro variables, el tiempo de resolución del algoritmo Quine-McCluskey crece de forma exponencial con el aumento del número de variables. Se puede demostrar que para una función de n variables el límite superior del número de implicantes primos es 3n/n. Si n = 32 habrá más de 6.5 * 1015 implicantes primos. Funciones con un número grande de variables tienen que ser minimizadas con otros métodos heuristicos

Ejemplo

Paso 1: Encontrando implicantes primos

Minimizando una función arbitraria:
f \left( A,B,C,D \right ) =\sum m \left( 4,8,10,11,12,15 \right) + \sum d \left( 9,14 \right) \,

A B C D f
m0 0 0 0 0 0
m1 0 0 0 1 0
0 0 1 0 0
0 0 1 1 0
m4 0 1 0 0 1
m5 0 1 0 1 0
m6 0 1 1 0 0
m7 0 1 1 1 0
m8 1 0 0 0 1
m9 1 0 0 1 X
m10 1 0 1 0 1
m11 1 0 1 1 1
m12 1 1 0 0 1
m13 1 1 0 1 0
m14 1 1 1 0 X
m15 1 1 1 1 1
Uno fácilmente puede formar la expresion canomica suma de productos de esta tabla, simplemente sumando miniterminos (dejando fuera las redundancias) donde la función se evalúa con 1:
 \begin{matrix} f_{A,B,C,D} = A'BC'D' + AB'C'D' + AB'CD' + AB'CD + ABC'D' + ABCD \end{matrix}
Por supuesto, esta expresión no es mínima. Para optimizarla, primero son colocados todos los minitérminos evaluados en la función como 1 en una tabla Las redundancias también son agregadas a la tabla, estas pueden combinarse con los minitérminos:
N. de 1s Minterm Representación binaria
1 m4
m8
0100
1000
2 m9
m10
m12
1001
1010
1100
3 m11
m14
1011
1110
4 m15 1111
En este punto, uno puede empezar a combinar los minitérminos entre sí. Si dos minitérminos sólo varían en un solo dígito, ese dígito debe reemplazarse por un guion "-" indicando que ese bit no importa. Los términos que ya no pueden combinarse más son marcados con "*". Cuando van de tamaño 2 a 4, tratamos '-' como un valor de bit
Ejemplo: -110 y -100 o -11- pueden ser combinados, pero no -110 y 011-.
(Consejo: agrupar los '-' primero.)
Número de 1s  Minterm    Bin    | Implicantes de tamaño 2 | Implicantes de tamaño 4
--------------------------------|-------------------------|------------------------
1               m4       0100   |     m(4,12)  -100*      |   m(8,9,10,11)   10--*
                m8       1000   |     m(8,9)   100-       |   m(8,10,12,14)  1--0*
--------------------------------|     m(8,10)  10-0       |------------------------
2               m9       1001   |     m(8,12)  1-00       |   m(10,11,14,15) 1-1-*
                m10      1010   |-------------------------|
                m12      1100   |     m(9,11)  10-1       |
--------------------------------|     m(10,11) 101-       |
3               m11      1011   |     m(10,14) 1-10       |
                m14      1110   |     m(12,14) 11-0       |
--------------------------------|-------------------------|
4               m15      1111   |     m(11,15) 1-11       |
                                |     m(14,15) 111-       |

Paso 2: tabla de implicantes primos

Los términos marcados con "*" ya no pueden combinarse más, en este punto ya tenemos la tabla de implicantes primos. En el costado van los implicantes primos recientemente generados, y en la parte superior los minitérminos utilizados. Los minitérminos correspondientes a las redundancias son omitidos en este paso, no se colocan en la parte superior.

4 8 10 11 12 15
m \left( 4,12 \right)* X


X
- 1 0 0
m \left( 8,9,10,11 \right)
X X X

1 0 - -
m \left( 8,10,12,14 \right)
X X
X
1 - - 0
m \left( 10,11,14,15 \right)*

X X
X 1 - 1 -
En esta tabla vemos los minitérminos que "cubre" cada implicante primo. Ninguno de los implicantes de esta tabla está incluido dentro de otro (esto queda garantizado en el paso uno), pero si puede estar "cubierto" por dos o más implicantes. Es el caso de m \left( 8,9,10,11 \right) que está cubierto por m \left( 8,10,12,14 \right) y m \left( 10,11,14,15 \right) o m \left( 8,10,12,14 \right) que está cubierto por m \left( 8,9,10,11 \right) y m \left( 4,12 \right).
Por este motivo, cada uno de estos dos implicantes sólo son esenciales en ausencia del otro. Un proceso adicional simple para reducir estos implicantes es prueba y error, pero un proceso más sistemático es el metodo de pretrick. En el caso que estamos analizando, los dos implicantes primos m \left( 4,12 \right) y m \left( 10,11,14,15 \right) no llegan a incluir todos los minitérminos por lo que podemos combinar estos implicantes con cada uno de los implicantes no esenciales para conseguir dos funciones mínimas:
 \begin{matrix} f_{A,B,C,D} = BC'D' + AB' + AC \end{matrix}
 \begin{matrix} f_{A,B,C,D} = BC'D' + AD' + AC \end{matrix}
Las dos son equivalentes a esta función original:
 \begin{matrix} f_{A,B,C,D} = A'BC'D' + AB'C'D' + AB'C'D + AB'CD' + AB'CD + ABC'D' + ABCD' + ABCD \end{matrix}


MAPAS DE KARNAUGH

 Mapa de Karnaugh ejemplo... Tutorial video

 

 

 

 Mapa de Karnaugh ejemplo...



 

Reglas de simplificación

1.  Las agrupaciones son exclusivamente de unos. Esto implica que ningún grupo puede contener ningún cero.
2. Las agrupaciones únicamente pueden hacerse en horizontal y vertical. Esto implica que las diagonales están prohibidas.
3.  Los grupos han de contener 2n elementos. Es decir que cada grupo tendrá 1,2,4,8... número de unos.
 
4.  Cada grupo ha de ser tan grande como sea posible. Tal y como lo ilustramos en el ejemplo.
5.  Todos los unos tienen que pertenecer como mínimo a  un grupo. Aunque pueden pertenecer a más de uno.
6.  Pueden existir solapamiento de grupos.
7.  La formación de grupos también se puede producir con las celdas extremas de la tabla. De tal forma que la parte inferior se podría agrupar con la superior y la izquierda con la derecha tal y como se explica en el ejemplo.
8.  Tiene que resultar el menor número de grupos posibles siempre y cuando no contradiga ninguna de las reglas anteriores. Esto es el número de grupos ha de ser minimal.








martes, 5 de marzo de 2013






Presentación.


TIC( Tecnologia de la informacion y la comunicacion)




Presentado por:


Kevin Steven Rodriguez Busstos


Oscar Daniel Pita Sanchez



Presentado a :


Juan Guillermo Nuñez 



Institucion unipanamericana