Clase N 10
Páginas: 5 (1197 palabras)
Publicado: 24 de mayo de 2015
Implicantes Primos
Propiedades de funciones mínimas
Una función F (b0 , b1 ,....bn ) cubre a la función G (b0 , b1 ,.....bn ) si F
vale 1 para todas las combinaciones de variables en la cual G
vale1.
b3b 2
b3b 2
b 1 b 0 01
00
01
11
10
00
01
11
10
0
1
0
0
0
1
0
0
0
1
1
0
0
1
1
0
F (b0 , b1 ,....bn )
Electrónica Digital,
Clase Nº10
b1b 0
00
01
11
10
00
01 11 10
0
1
0
0
0
0
0
00
0
0
0
0
1
1
0
G (b0 , b1 ,.....bn )
1
Implicantes Primos
En este cado F cubre a G ( F ⊃ G ). F puede tener1 que G no
tiene, pero para que F cubra a G, F debe tener todos unos de G.
Si F ⊃ G
equivalentes.
∧G ⊃ F
Si F (b0 , b1 ,....bn )
P (b0 , b1 ,...bn )
P
implica que F y G son funciones
es una función de conmutación,
un producto de literales
implica
F , siF ⊃ P
Definición: P esimplicante primo de F, si F ⊃ P y al eliminar
cualquier literal de P, no se cumple con F ⊃ P .
Electrónica Digital,
Clase Nº10
2
Implicantes Primos
Ejemplo:
P = ab
F
ab
ab
ab ab
c 1
0
0
0
c 1
1
1
0
ab
c 1
c 1
ab ab
ab
0
0
0
0
0
0
F ⊃P
En este caso
, pero si se elimina cualquier literal de
P, F ya no cubriría a P, por lo tanto P es un implicante primo de
F.
ElectrónicaDigital,
Clase Nº10
3
Implicantes Primos
• Si se elimina el literal “b” como se muestra en
el mapa siguiente, resulta que F no cubre a P.
P=a
F
ab
ab
ab
ab
1
0
0
0
c 1
1
1
0
c
Electrónica Digital,
Clase Nº10
ab
ab
ab ab
c 1
1
0
0
c 1
1
0
0
4
Implicantes Primos
Teorema:
Cualquier función sin literales redundantes, equivalente a F es una
unión de implicantes primos de F.F∗
( ) = ( )+( )+( )+ ( )+( ) (suma de implicantes primos
Definición:
Un implicante primo es esencial si cubre al menos un mintérmino
que no es cubierto por ningún implicante primo.
Electrónica Digital,
Clase Nº10
5
Implicantes Primos
Ejemplo:
x1 x2
x3
0
1
00
01
F ( x1 , x2 , x3 ) = x1 x2 , x1 x3 ,x2 x3 , x1 x2 , x1 x3 , x2 x3
C
A B
F
D E
11
10
1 1 1
1
1 1
0 1 2 5
A
B
C
D
F ( x1 ,x2 , x3 ) = ∑ (0,1,2,5,6,7)
F ( x1 , x2 , x3 ) = A + C + E
F(x1, x2, x3) = x1 x2 + x2 x3 + x1x2
6 7
Otra alternativa:
F ( x1 , x2 , x3 ) = B + D + F
F(x1, x2 , x3 ) = x1 x3 + x1x2 + x2 x3
la idea es que todos los mintérminos de
la función sean cubierto por un conjunto
de implicantes primos.
E
F
Electrónica Digital,
Clase Nº10
6
Método de Quine – Mc Kluskey
•
El método de Quine – McKluskey es un técnica tabular.
•
Es una técnica fácil de programar, con lo que se logra una herramienta
algorítmica para la obtención de expresiones mínimas.
•
Una función f ( x, y , z ) = xz + y tiene dos términos “xz e y” y ambos son
implicantes primos.
•
La función f ( x, y , z ) = xyz + xy + z tiene 3 términos y dos de ellos
son implicantes primos el término “xyz”, no es implicante primopuesto
que si se elimina el literal “z” queda el término “xy” que ya existe.
Electrónica Digital,
Clase Nº10
7
Método de Quine – Mc Kluskey
•
•
El método de Quine- Mc Kluskey determina los implicantes
primos de una función dada.
Pasos para el desarrollo del método:
1.
2.
3.
4.
5.
6.
Para desarrollar el método se debe tener la función de la forma
canónica “Suma de Productos”.
Luego serepresenta cada mintérmino en binario.
Se agrupan los mintérminos de acuerdo al número de “unos” que
tengan.
Cada grupo , se vuelve agrupar con algún otro grupo adyacente
buscando diferencias de un solo bit. El bit en que se difiere es
reemplazado por “-”.
Se vuelve a aplicar el paso anterior. El símbolo “-” debe estar en la
misma posición.
Finalmente se deben cubrir todos los términos de la funciónoriginal
utilizando el mínimo número de implicantes primos.
Electrónica Digital,
Clase Nº10
8
Método de Quine – Mc Kluskey
Ejemplo:
Considerar la siguiente función: 1.
f ( w, x, y, z ) = ∑ (0,2,3,5,6,7,8,9)
2. Se escribe cada mintérmino de la forma binaria:
Electrónica Digital,
Clase Nº10
(0)
0000
(2)
0010
(3)
0011
(5)
0101
(6)
0110
(7)
0111
(8)
1000
(9)
1001
9
Método de Quine...
Propiedades de funciones mínimas
Una función F (b0 , b1 ,....bn ) cubre a la función G (b0 , b1 ,.....bn ) si F
vale 1 para todas las combinaciones de variables en la cual G
vale1.
b3b 2
b3b 2
b 1 b 0 01
00
01
11
10
00
01
11
10
0
1
0
0
0
1
0
0
0
1
1
0
0
1
1
0
F (b0 , b1 ,....bn )
Electrónica Digital,
Clase Nº10
b1b 0
00
01
11
10
00
01 11 10
0
1
0
0
0
0
0
00
0
0
0
0
1
1
0
G (b0 , b1 ,.....bn )
1
Implicantes Primos
En este cado F cubre a G ( F ⊃ G ). F puede tener1 que G no
tiene, pero para que F cubra a G, F debe tener todos unos de G.
Si F ⊃ G
equivalentes.
∧G ⊃ F
Si F (b0 , b1 ,....bn )
P (b0 , b1 ,...bn )
P
implica que F y G son funciones
es una función de conmutación,
un producto de literales
implica
F , siF ⊃ P
Definición: P esimplicante primo de F, si F ⊃ P y al eliminar
cualquier literal de P, no se cumple con F ⊃ P .
Electrónica Digital,
Clase Nº10
2
Implicantes Primos
Ejemplo:
P = ab
F
ab
ab
ab ab
c 1
0
0
0
c 1
1
1
0
ab
c 1
c 1
ab ab
ab
0
0
0
0
0
0
F ⊃P
En este caso
, pero si se elimina cualquier literal de
P, F ya no cubriría a P, por lo tanto P es un implicante primo de
F.
ElectrónicaDigital,
Clase Nº10
3
Implicantes Primos
• Si se elimina el literal “b” como se muestra en
el mapa siguiente, resulta que F no cubre a P.
P=a
F
ab
ab
ab
ab
1
0
0
0
c 1
1
1
0
c
Electrónica Digital,
Clase Nº10
ab
ab
ab ab
c 1
1
0
0
c 1
1
0
0
4
Implicantes Primos
Teorema:
Cualquier función sin literales redundantes, equivalente a F es una
unión de implicantes primos de F.F∗
( ) = ( )+( )+( )+ ( )+( ) (suma de implicantes primos
Definición:
Un implicante primo es esencial si cubre al menos un mintérmino
que no es cubierto por ningún implicante primo.
Electrónica Digital,
Clase Nº10
5
Implicantes Primos
Ejemplo:
x1 x2
x3
0
1
00
01
F ( x1 , x2 , x3 ) = x1 x2 , x1 x3 ,x2 x3 , x1 x2 , x1 x3 , x2 x3
C
A B
F
D E
11
10
1 1 1
1
1 1
0 1 2 5
A
B
C
D
F ( x1 ,x2 , x3 ) = ∑ (0,1,2,5,6,7)
F ( x1 , x2 , x3 ) = A + C + E
F(x1, x2, x3) = x1 x2 + x2 x3 + x1x2
6 7
Otra alternativa:
F ( x1 , x2 , x3 ) = B + D + F
F(x1, x2 , x3 ) = x1 x3 + x1x2 + x2 x3
la idea es que todos los mintérminos de
la función sean cubierto por un conjunto
de implicantes primos.
E
F
Electrónica Digital,
Clase Nº10
6
Método de Quine – Mc Kluskey
•
El método de Quine – McKluskey es un técnica tabular.
•
Es una técnica fácil de programar, con lo que se logra una herramienta
algorítmica para la obtención de expresiones mínimas.
•
Una función f ( x, y , z ) = xz + y tiene dos términos “xz e y” y ambos son
implicantes primos.
•
La función f ( x, y , z ) = xyz + xy + z tiene 3 términos y dos de ellos
son implicantes primos el término “xyz”, no es implicante primopuesto
que si se elimina el literal “z” queda el término “xy” que ya existe.
Electrónica Digital,
Clase Nº10
7
Método de Quine – Mc Kluskey
•
•
El método de Quine- Mc Kluskey determina los implicantes
primos de una función dada.
Pasos para el desarrollo del método:
1.
2.
3.
4.
5.
6.
Para desarrollar el método se debe tener la función de la forma
canónica “Suma de Productos”.
Luego serepresenta cada mintérmino en binario.
Se agrupan los mintérminos de acuerdo al número de “unos” que
tengan.
Cada grupo , se vuelve agrupar con algún otro grupo adyacente
buscando diferencias de un solo bit. El bit en que se difiere es
reemplazado por “-”.
Se vuelve a aplicar el paso anterior. El símbolo “-” debe estar en la
misma posición.
Finalmente se deben cubrir todos los términos de la funciónoriginal
utilizando el mínimo número de implicantes primos.
Electrónica Digital,
Clase Nº10
8
Método de Quine – Mc Kluskey
Ejemplo:
Considerar la siguiente función: 1.
f ( w, x, y, z ) = ∑ (0,2,3,5,6,7,8,9)
2. Se escribe cada mintérmino de la forma binaria:
Electrónica Digital,
Clase Nº10
(0)
0000
(2)
0010
(3)
0011
(5)
0101
(6)
0110
(7)
0111
(8)
1000
(9)
1001
9
Método de Quine...
Leer documento completo
Regístrate para leer el documento completo.