Post on 22-Jan-2016
transcript
SISTEMAS DIGITALES 1Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
ALGEBRA DE BOOLE
SISTEMAS DIGITALES 2Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
Introducción
• El álgebra booleana define constantes y funciones para describir sistemas binarios. Luego describe cierto número de teoremas que se pueden usar para manipular expresiones lógicas.
• CONSTANTES BOOLEANASCONSTANTES BOOLEANAS: consisten en "0" y "1". El primero representa el estado falso y el segundo el estado verdadero.
SISTEMAS DIGITALES 3Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
• VARIABLES BOOLEANASVARIABLES BOOLEANAS: Son magnitudes que pueden tomar diferentes valores en diferentes momentos. Pueden representar señales de entrada, de salida o intermedias y reciben nombres que de ordinario consisten en caracteres alfabéticos como "A", "B", "X" o "Y". Las variables sólo pueden tomar los valores "0" ó "1".
SISTEMAS DIGITALES 4Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales• FUNCIONES BOOLEANASFUNCIONES BOOLEANAS: Cada una de las
funciones lógicas elementales está representada dentro del álgebra booleana mediante un símbolo único, como se muestra en la siguiente tabla:
Función Símbolo Ejemplo
AND Punto
OR Más (+)
NOT Barra
C A B AB
C A B
C A
SISTEMAS DIGITALES 5Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
Postulados Básicos
Los postulados básicos utilizados en el álgebra booleana son los siguientes:
Postulado 1: 1xsi0x
0xsi1x
0 0 0
1 1 1
Postulado 2:
SISTEMAS DIGITALES 6Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
1 1 1
0 0 0
Postulado 3:
1 0 0 1 0
0 1 1 0 1
Postulado 4:
0 1
1 0
Postulado 5:
SISTEMAS DIGITALES 7Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
A B
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 1
BA A B
SISTEMAS DIGITALES 8Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
Teoremas Booleanos
• El álgebra booleana define varios teoremas que se pueden usar para cambiar la forma de una expresión.
• Estos teoremas son los siguientes:
SISTEMAS DIGITALES 9Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
0 0
0 0 0 0
1 0 1 0
x
Si x
Si x
Teorema 1: Dual: 1 1
0 1 0 1
1 1 1 1
x
Si x
Si x
Teorema 2:1
0 1 0 0
1 1 1 1
x x
Si x
Si x
Dual:
0 0
0 0 0 0
1 0 1 1
x
Si x
Si x
SISTEMAS DIGITALES 10Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
0 0 0 0
1 1 1 1
x x x
Si x
Si x
Teorema 3: Dual: 0 0 0 0
1 1 1 1
x x x
Si x
Si x
Teorema 4: Dual:
0
0 0 1 0
1 1 0 0
x x
Si x
Si x
0 0 1 1
1 1 0 1
x x x
Si x
Si x
x y y xTeorema 5: Dual: x y y x
SISTEMAS DIGITALES 11Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
Dual: x y z x y z x y z
Teorema 6: x y z y x z x y z x y z y x z x y z
Teorema 7: ...... .... x y z x y z
Dual: ... ...... x y z x y z
Teorema 8: ( , ,..... , , ) , ,....., , , f x y z x y z
SISTEMAS DIGITALES 12Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
Teoremas Simplificatorios
( ) xy xz x y zTeorema 9: Dual: x y x z x yz
xy x y xTeorema 10: Dual: x y x y x
x x y x yTeorema 11: Dual: x x y xy
x xy xTeorema 12: Dual:
SISTEMAS DIGITALES 13Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
xy xz yz xy xzTeorema 13:
Dual: x y x z y z x y x z
Ejemplo: Simplificar la siguiente expresión
EDBCDCEBCAf
SISTEMAS DIGITALES 14Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
Desarrollo
))()()(( EDDCBECCBAf
))(( EEDECEDCDACBf
0EE )()()( EDDAECDADCDAEDCECCDCCDEBECBDCBf
ECDCDEBf
))()(( DEBECDCf
))(( DEBDECf
DDEEDEBDEDCCECBf
BCDCDEECf BCDEECf
SISTEMAS DIGITALES 15Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
Formas Especiales de Expresiones
Booleanas
SISTEMAS DIGITALES 16Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
Formas Canónicas
• SUMA EXPANDIDA DE PRODUCTOS: En este caso para aplicar la expansión se aplica el teorema 10
xy x y x
Cada uno de los términos en forma canónica expresado en suma (OR de AND) se llama Mintérmino y se puede expresar en forma simplificada. Si en este caso a la variable natural se le asigna el valor lógico uno y la variable complementada el valor lógico cero.
SISTEMAS DIGITALES 17Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
DAACf
DACACDAC CDACDADA
f ACD ACD ACD ACD ACDmíntér min o
Ejemplo:
CDADCADACACDf
111 110 010 0007 6 2 0
f
)7,6,2,0(minf
)7,6,2,0(),,( DCAf
SISTEMAS DIGITALES 18Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
Formas Canónicas
• PRODUCTO EXPANDIDO DE SUMAS: Esta forma de expresar una función booleana se basa en el dual del teorema 10
Cada uno de los términos en forma canónica expresado en producto (AND de OR) se llama Máxtermino y se puede expresar en forma simplificada. Si en este caso a la variable natural se le asigna el valor lógico cero y la variable complementada el valor lógico uno.
x y x y x
SISTEMAS DIGITALES 19Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
Ejemplo: ),,())(( CBAfCABAf
))(( CBACBABA
))(( CBACBACA
f (A B C) (A B C)(A B C)
max tér min o
))()(( CBACBACBAf
(000) (001) (011)
0 1 3
f
)3,1,0máx(),,( CBAf
SISTEMAS DIGITALES 20Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
Formas Mínimas
1. Mínima Suma Productos
2. Mínima Productos de Sumas
• En este caso interesa que la función booleana sea lo más pequeña posible, es decir que si está expresada en la forma OR de AND el número de sumandos y el tamaño de cada sumando debe ser mínimo.
• Si la función está expresada en la forma AND de OR entonces el tamaño y el número de factores debe ser mínimo.
SISTEMAS DIGITALES 21Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
Métodos de Simplificación de
Expresiones Booleanas
SISTEMAS DIGITALES 22Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
Formas Canónicas
• MÉTODO ALGEBRAICO:Corresponde a los casos analizados anteriormente.
• MAPAS DE KARNAUGH: Los mapas o diagramas de Karnaugh representan una técnica gráfica para simplificar las ecuaciones de Boole. Es uno de los métodos más usuales para ecuaciones de hasta 4 ó 5 variables y se basa en el teorema 10:
xy x y x
SISTEMAS DIGITALES 23Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
Introducción Mapa de Karnaugh
• Los Mapas de Karnaugh, como se dijo anteriormente, se utilizan para simplificar funciones booleanas. El número de casilleros que tendrá el mapa dependerá de la cantidad de variables que tenga la función.
SISTEMAS DIGITALES 24Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
Ejemplo: BAf
Nº de variables: 2
Nº Casilleros: 2n=22=4
2n
Variables Binarias
Nº Variables
SISTEMAS DIGITALES 25Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
• Dentro de cada casillero del mapa se debe poner un uno (1) o un cero(0) lógico dependiendo si la función está expresada como OR de AND o AND de OR.
• Para el caso de los mintérminos corresponde un “1” en el casillero, por el contrario, para cada maxtérmino corresponde un “0” al casillero
0
1
0 1AB
SISTEMAS DIGITALES 26Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
Mapa para 3 Variables
0
1
0 0 1 101 10A
CB
AB
C 10
0 0
0 1
1 1
1 0
Código Gray
Código Gray
SISTEMAS DIGITALES 27Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
Mapa para 4 Variables
00 01 11 10
00
01
1
10
1
DC
BA
SISTEMAS DIGITALES 28Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
Representación de Variables en Mapa de Karnaugh
00 01 11 10
00
01
1
10
1
0
BA
DC
1
2
3
4
5
6
7
8
10
11
12
13
14
15
9
SISTEMAS DIGITALES 29Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
• Hay que hacer notar que antes de realizar la representación de las variables de una función en el Mapa de Karnaugh se debe definir las variables más significativas (MSB) y la menos significativa (LSB)
SISTEMAS DIGITALES 30Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
Ejemplo: Representar en mapa de Karnaugh
12,9,7,6,5,3,0minfLSDA
MSBDDCBAf
),,,(
00 01 11 10
00
01
1
10
1
DC
BA
1
1 1
1
1
1
10
0
0
0
0
0 0
0
0
SISTEMAS DIGITALES 31Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
• Existen algunos casos en que el valor lógico que se debe asignar a los casilleros del mapa no está definido y nosotros podemos asignar el valor lógico “1” ó “0” según la conveniencia para la simplificación. Estás condiciones reciben el nombre de “Superfluas” o “No Importa” y se designan con los simbolos o x
SISTEMAS DIGITALES 32Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
Ejemplo: Representar en Mapa la siguiente función
B 10AC
1
1
1
X
X
010
11
01
00
0
0
6,43,2,0min fLSDA
MSBCCBAf
),,(
SISTEMAS DIGITALES 33Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
Definición e Interpretación Mapas de Karnaugh
• Un diagrama de Karnaugh representa una ecuación de Boole de una forma bastante similar a una tabla de verdad.
• Ejemplo 1:
A B C Z
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 0
SISTEMAS DIGITALES 34Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
C
0
0
0
0
1
0
0 1
BA
0 1
00
01
0
11
1
CBABCAZ 1
SISTEMAS DIGITALES 35Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
• Del ejemplo anterior se deduce que para una función booleana de 3 variables se necesita un mapa de 8 casilleros. En cada casillero se representa un "1" lógico para cada mintérmino y un "0" lógico para cada máxtermino.
• Debe notarse que la asignación de las variables en los casilleros tanto en el sentido vertical como horizontal corresponden al código Gray.
SISTEMAS DIGITALES 36Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
Método de Simplificación
• Para simplificar una expresión booleana mediante el Mapa de Karnaugh se deben agrupar los casilleros que contienen 1 adyacente y en un número tal que sea potencia de 2 como agrupación de mintérminos, de lo que resulta un factor simplificado.
• Es posible representar esquemáticamente la cantidad de variables eliminadas producto de la agrupación:
SISTEMAS DIGITALES 37Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
• 20 variables eliminadas = 0
• 21 variables eliminadas = 1
• 22 variables eliminadas = 2
• 23 variables eliminadas = 3
• 24 variables eliminadas = 4
• 25 variables eliminadas = 5
SISTEMAS DIGITALES 38Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
• Criterios de AgrupaciónCriterios de Agrupación:
1. La agrupación debe ser lo más grande posible
2. Se debe tener el mínimo de agrupaciones
3. Se agrupan los adyacentes en un número que sea potencia de 2
• Criterios de AdyacenciaCriterios de Adyacencia:
1. Casilleros con un lado común
2. Reflexión de acuerdo al Código Gray
SISTEMAS DIGITALES 39Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
Simplificar el mapa:
0
1
0 0 1 101 10
1
11 1
11 1
0
CA
B
SISTEMAS DIGITALES 40Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
Solución 1:
0
1
0 0 1 101 10A
1
110 1
11 1
CB
0f
ABCf 0
f = A + + CBCB CB1
+
SISTEMAS DIGITALES 41Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
Solución 2:
0
1
0 0 1 101 10A
1
110 1
11 1
CB
0f
ABCf 0
f = A + +1
B C
SISTEMAS DIGITALES 42Autor: J.LL.A / F.A.R
Ingeniería de Ejecución en Sistemas ComputacionalesIngeniería de Ejecución en Sistemas Computacionales
• El ejemplo anterior demuestra que al no hacer agrupaciones lo más grande posible se obtiene una función correcta pero que no es la forma mínima