Post on 21-Oct-2018
transcript
2: Funciones booleanas 1
2-Funciones y representaciones booleanas
2.1 Lógica y álgebra de Boole2.2 Funciones booleanas2.3 Representaciones de funciones
booleanas.2.4 Funciones de varias variables.
2: Funciones booleanas 2
Lógica Booleana
Definiciones básicas Una variable booleana (e.g. x, y) es un símbolo
que puede ser substituido por un elemento del conjunto B={0,1}
Una constante booleana es un valor perteneciente al conjunto {0,1}
Una expresión (e.g. x+y, x·y, x’) esta compuesta de variables, constantes y operadores (e.g. +, ·, ’)
Una función booleana de n variables f(x1, x2, ..., xn) es un expresión o fórmula que mapea f a un valor del conjunto booleano B (0 ó 1).
Un literal es una variable o su complemento.
2: Funciones booleanas 3
Álgebra de Boole
Definición: el álgebra de Boole es un sistema algebraico cerrado que contiene un conjunto de dos elementos {0, 1}, dos operadores binarios {+, ·}, un operador unitario { ‘ }.
2: Funciones booleanas 4
Lógica y álgebra de Boole
El álgebra de Boole es la fundación matemática de los sistemas digitales.
Las operaciones del álgebra de Boole deben regirse por propiedades y reglas lógicas llamados leyes o postulados.
Estos postulados se pueden usar para demostrar leyes mas generales sobre expresiones booleanas.
Estos postulados también se usan para simplificar y optimizar expresiones booleanas y sistemas digitales. Ejemplo: X AND (Y OR Y’) = X (¿porque?)
2: Funciones booleanas 5
Álgebra de Boole Una expresión algebraica de Boole consiste de
un conjunto de B operaciones binarias { + , • } una operaciones unitaria { ’ }
B tiene dos elementos : a, b y los siguientes postulados se cumplen:
Clausura: a + b esta en B, a • b esta en B
Commutatividad: a + b = b + a, a • b = b • a
Asociatividad: a + (b + c) = (a + b) + ca • (b • c) = (a • b) • c
Identidad: a + 0 = a a • 1 = a
Distributividad: a + (b • c) = (a + b) • (a + c)a • (b + c) = (a • b) + (a • c)
Complementariedad: a + a’ = 1 a • a’ = 0
2: Funciones booleanas 6
Álgebra de Boole: Resumen Algebra de Boole
B = {0, 1} variables + es el OR lógico, • es el AND lógico ’ es el NOT lógico
Todos los postulados (axiomas) algebraicos se cumplen. La prioridad de los operadores es ‘, seguido por AND y despues OR. El ‘ tiene la mayor prioridad. Los ( ) pueden cambiar el orden de evaluación.
2: Funciones booleanas 7
Álgebra de Boole: Teoremas
Con la formulación de los postulados del álgebra de Boole se pueden demostrar varias proposiciones o teoremas de álgebra booleana.
Para las demostraciones de teoremas se pueden usar tablas de verdad, postulados y teoremas ya demostrados.
2: Funciones booleanas 8
Álgebra de Boole: Teoremas Definición: El álgebra de boole es un sistema algebraico
cerrado que contiene un conjunto B de dos elementos {0,1} y tres operadores {·, +, ‘}.
igualdad: Dos expresiones son iguales si una puede ser substituida por otra.
identidad:1. X + 0 = X 1D. X • 1 = X
nulo (elementos únicos): 2. X + 1 = 1 2D. X • 0 = 0
idempotencia:3. X + X = X 3D. X • X = X
involución:4. (X’)’ = X
complementariedad:5. X + X’ = 1 5D. X • X’ = 0
2: Funciones booleanas 9
Álgebra de Boole: Teoremas conmutatividad:
6. X + Y = Y + X 6D. X • Y = Y • X asociatividad:
7. (X + Y) + Z = X + (Y + Z) 7D. (X • Y) • Z = X • (Y • Z) distributividad:
8. X • (Y + Z) = (X • Y) + (X • Z) 8D. X + (Y • Z) = (X + Y) • (X + Z) fusión (unificación):
9. X • Y + X • Y’ = X 9D. (X + Y) • (X + Y’) = X absorción:
10. X + X • Y = X 10D. X • (X + Y) = X
11. (X + Y’) • Y = X • Y 11D. (X • Y’) + Y = X + Y factorizar:
12. (X + Y) • (X’ + Z) = 12D. X • Y + X’ • Z = X • Z + X’ • Y (X + Z) • (X’ + Y)
consenso:13. (X • Y) + (Y • Z) + (X’ • Z) = 13D. (X + Y) • (Y + Z) • (X’ + Z) = X • Y + X’ • Z (X + Y) • (X’ + Z)
2: Funciones booleanas 10
Álgebra de Boole: Teoremas
de Morgan:
14. (X + Y + ...)’ = X’ • Y’ • ... 14D. (X • Y • ...)’ = X’ + Y’ + ...
de Morgan generalizado:
15. f’(X1,X2,...,Xn,0,1,+,•) = f(X1’,X2’,...,Xn’,1,0,•,+)
establece relaciones entre • y +
2: Funciones booleanas 11
Álgebra de Boole: Teoremas
Ejemplo: de Morgan:
(X + Y)’ = X’ • Y’NOR es equivalente a AND con inputs complementados
(X • Y)’ = X’ + Y’NAND es equivalente a OR con inputs complementados
X Y X’ Y’ (X + Y)’ X’ • Y’0 0 1 1 0 1 1 0 1 0 0 1 1 1 0 0
X Y X’ Y’ (X • Y)’ X’ + Y’0 0 1 1 0 1 1 0 1 0 0 1 1 1 0 0
1000
1110
1000
1110
2: Funciones booleanas 12
Álgebra de Boole: Teoremas
Dualidad El dual de una expresión booleana se puede obtener
remplazando • por +, + por •, 0 por 1, y 1 por 0, y dejando las variables
sin cambio Cualquier teorema demostrado también esta demostrado
para su dual! Un meta-teorema (teorema sobre teoremas)
Dualidad:16. X + Y + ... ⇔ X • Y • ...
Dualidad generalizado:17. f (X1,X2,...,Xn,0,1,+,•) ⇔ f(X1,X2,...,Xn,1,0,•,+) Diferente que ley de De Morgan’s No es una manera para manipular (cambiar) expresiones Ej: El dual del teorema X + 0 = X o (X + 0 = X)D es X • 1 =
X
2: Funciones booleanas 13
Álgebra de Boole: Teoremas Actividad:
Demuestre este teorema: X • Y + X • Y’ = X
Demuestre este teorema : X + X • Y = X
igualdad X • Y + X • Y’ = X • Y + X • Y’distributividad (8) = X • (Y + Y’)complementariedad (5) = X • (1)identidad (1D) = X
igualdad X + X • Y = X + X • Yidentidad (1D) = X • 1 + X • Ydistributividad (8) = X • (1 + Y)nulo (2) = X • (1)identidad (1D) = X
2: Funciones booleanas 14
Actividad: Álgebra de Boole
Demuestre lo siguiente usando álgebra booleana:
(X • Y) + (Y • Z) + (X’ • Z) = X • Y + X’ • ZIgualdad X Y + X’ Z = X Y + X’ Zabsorción (10) = (X Y + X Y Z) + (X’ Z + X’ Z Y)conmutatividad (6) = X Y + X’ Z + X Y Z + X’ Z Yconmutatividad (6D) = X Y + X’ Z + X Y Z + X’ Y Zdistributividad (8) = X Y + X’ Z + (X + X’) Y Zcomplementariedad (5) = X Y + X’ Z + (1) Y Zidentidad (1D) = X Y + X’ Z + Y Z conmutatividad (6) = X Y + Y Z + X’ Z
2: Funciones booleanas 15
2-Funciones y representaciones booleanas
2.1 Lógica y álgebra de Boole.2.2 Funciones booleanas. 2.3 Representaciones de funciones
booleanas.2.4 Funciones de varias variables.
2: Funciones booleanas 16
Funciones booleanas Espacios y funciones booleanas
Si se define un espacio booleano como B={0,1} Usando el producto cartesiano se puede definir B2
= {0,1} x {0,1} = {(00), (01), (10), (11)} Para X = (X1, X2) podemos definir una función
booleana f de dos variables según: f(X): B2 → B, cada punto de B2 se mapea a B
Para n variables booleanas con X = (X1, X2, ... Xn) se puede definir una función booleana f de n variables según:
f(X): Bn → B, cada punto de Bn se mapea a B La función booleana puede tomar valores de 1 o 0
dependiendo de los valores de sus variables.
2: Funciones booleanas 17
Funciones booleanas
Espacios y funciones booleanas El conjunto uno (on set) de f, puede definirse
como los puntos X de Bn que se mapean a 1.
f1 : {X | f(X) = 1} El conjunto zero (off set) de f puede definirse
como los puntos X de Bn que se mapean a 0.
f0 : {X | f(X) = 0} Si f1 = Bn = se dice que f es una tautología. Si f0 = Bn = se dice que f0 es vacío y no es
satisfacible.
2: Funciones booleanas 18
Funciones booleanas: tautología
En lógica, la tautología es un enunciado que es cierto por su propia definición, y es por lo tanto fundamentalmente no informativo. Las tautologías lógicas utilizan el razonamiento circular dentro de un argumento o enunciado. Por ejemplo: "El 100% de nuestros clientes compran nuestros productos".
En lingüística, una tautología es una redundancia debida a una calificación superflua (e.g. "innovación novedosa", "mundo mundial"). Suele entenderse como una falta de estilo, aunque a veces se utiliza intencionadamente para dar énfasis, por ejemplo "Le voy a entregar un obsequio gratis". En este sentido, también puede llamárselas 'pleonasmos'.
Las matemáticas pueden ser consideradas como la ciencia de hacer tautologías particularmente elaboradas de una forma rigurosa. Un teorema es un ejemplo de tautología útil.
2: Funciones booleanas 19
Funciones booleanas Espacios y funciones booleanas
Una función f es satisfacible cuando existe un elemento en el conjunto de f que es uno.
Dos funciones son equivalentes si para todo X є Bn se tiene que:
f(X) = g(X)
2: Funciones booleanas 20
2-Funciones y representaciones booleanas
2.1 Lógica y álgebra de Boole2.2 Funciones booleanas 2.3 Representaciones de funciones
booleanas2.4 Funciones de varias variables
2: Funciones booleanas 21
Representaciones Las funciones booleanas se pueden
describir de variadas formas incluyendo: álgebra booleana tablas de verdad, diagramas de compuertas, diagramas temporales, diagramas de Venn, mapas de Karnaugh, N-cubos, lenguajes de descripción de hardware (HDL:
Hardware description languages) como Verilog o VHDL
Por v
er s
e!
2: Funciones booleanas 22
Representaciones: álgebra booleana
Las funciones booleanas se pueden describir con una expresión de álgebra booleana.
Ejemplo: f(X, Y, Z) = XY + X’Z + XZ’ La función puede evaluarse para las diferentes
combinaciones de valores que tomen las variables.
Existen infinitas representaciones equivalentes de una función a través de expresiones.
El problema de síntesis lógica consiste en encontrar la mejor expresión para representar una función.
2: Funciones booleanas 23
Representaciones: tabla de verdad
Las funciones booleanas también se pueden representar como una tabla de verdad.
La tabla de verdad despliega todas las combinaciones de valores de las variables y el valor asociado de la función.
2: Funciones booleanas 24
Representaciones Ejemplos: tablas de verdad
X Y X • Y0 0 00 1 01 0 01 1 1
X Y X’ Y’ X • Y X’ • Y’ ( X • Y ) + ( X’ • Y’ )0 0 1 1 0 1 10 1 1 0 0 0 01 0 0 1 0 0 01 1 0 0 1 0 1
( X • Y ) + ( X’ • Y’ ) ≡ X = Y
X Y X’ X’ • Y0 0 1 00 1 1 11 0 0 01 1 0 0
Expresión booleana que es verdadera cuando X e Y son iguales y falso de otraforma
2: Funciones booleanas 25
Representaciones
• Las funciones booleanas también se pueden representar por diagramas compuestos de símbolos de compuertas.
• Existen múltiples diagramas que pueden representar la misma función.
• La ventaja de esta representación es que esta asociada a la implementación en un medio visual.
• Los circuitos combinacionales contienen solo compuertas.
• Los circuitos secuenciales contienen flip-flops y compuertas.
2: Funciones booleanas 26
X Y Z0 0 00 1 01 0 01 1 1
X Y0 11 0
X Y Z0 0 00 1 11 0 11 1 1
X Y
X
X
Y
Y
Z
Z
Diagramas de compuertas
NOT : X’, X, ~X
AND: X•Y, XY, X∧Y
OR: X+Y, X∨Y
2: Funciones booleanas 27
XY Z
X Y Z0 0 10 1 11 0 11 1 0
X Y Z0 0 10 1 01 0 01 1 0
ZX
Y
X
YZ
X Y Z0 0 10 1 01 0 01 1 1
X Y Z0 0 00 1 11 0 11 1 0
ZXY
Diagramas de compuertas
NAND
NOR
XOR X ⊕ Y
XNOR X = Y
2: Funciones booleanas 28
T1
T2
A
B
CD T2
T1
Z A
B
CD
Z
Diagramas de compuertas Existe mas de una forma de mapear
expresiones a compuertas
e.g., Z = A’ • B’ • (C + D) = (A’ • (B’ • (C + D)))
Cómo sería usando compuertas?
2: Funciones booleanas 29
Representaciones: diagrama temporal
Un diagrama temporal es una representación de las formas de las ondas de entradas y salidas de los circuitos.
Los bordes no se alinean exactamente (toma tiempo para que una compuerta cambie de output).
2: Funciones booleanas 30
Representaciones: diagrama temporal
Las señales de ondas se pueden apreciar usando varias herramientas como: un simulador, usando un analizador lógico o un osciloscopio.
Retardos de propagación en compuertas pueden causar que las señales de entrada de otras compuertas en cascada tengan carreras.
Estas carreras pueden causar errores o perturbaciones (glitches).
Los tiempos de propagación son acumulativos para compuertas en cascada.
2: Funciones booleanas 31
Representaciones: diagrama temporal
Existe un retardo entre la salida y la entrada de una compuerta, que se denomina retardo de propagación.
Los retardos de propagación han sido definidos como cotas superiores de retardos entre entradas válidas y salidas válidas.
2: Funciones booleanas 32
Representaciones: diagrama temporal
También pueden definirse los mínimos retardos de propagación o tiempos de contaminación como las cotas mínimas entre entradas inválidas y salidas inválidas.
2: Funciones booleanas 33
Representaciones: diagrama temporal
Ejemplo: y = x + x’
Cómo sería la perturbación?
X
X’
Y
X
X’
Y
t
perturbación
Carrera en señales de entrada
2: Funciones booleanas 34
Representaciones: diagramas de Venn
Los diagramas de Venn provienen de la rama de las matemáticas conocida como teoría de conjuntos.
Estos diagramas son usados para mostrar. gráficamente la relación entre diferentes conjuntos
Son equivalentes a las tablas de verdad al mostrar todas las relaciones lógicas entre los conjuntos de interés.
Ejemplos:
A BA · B
A + B
(A + B)’ (A + B)’
2: Funciones booleanas 35
2-Funciones y representaciones booleanas
2.1 Lógica y álgebra de Boole2.2 Funciones booleanas 2.3 Representaciones de funciones
booleanas2.4 Funciones de varias variables
2: Funciones booleanas 36
Funciones de n variables Si hay n variables la tabla de verdad tendrá 2n
filas. Cada fila tiene como resultado un 0 o un 1. El número de posibles funciones (que resultan en
0 o 1) crece rápidamente, en termino de n es: 22ⁿ
n = 0 indica una función con 0 variables.
X1
X2 F
Xn
2: Funciones booleanas 37
X Y f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f150 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 10 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 11 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 11 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
Funciones de n variables Ejemplo: para n=2 se tienen 22ⁿ = 16 funciones
Cómo son las funciones equivalentes a la tabla? f0=0, f1=XY, f2=XY’, f3=X, f4=X’Y, ..., f14=X’Y’ + X’Y +
XY’= A’ + B’ = (AB)’, f15=1
XY F
0
XYX Y
X + Y
Y’ X’ 1X xor Y
X nor Y=(X + Y)’
X = Y X nand Y=(XY)’
2: Funciones booleanas 38
Conjuntos funcionalmente Completos
Cualquier expresión booleana puede ser escrita mediante los operadores AND, OR y NOT.
Estos conjuntos constituyen un conjunto funcionalmente completo.
2: Funciones booleanas 39
Conjuntos funcionalmente Completos
La función NAND también es funcionalmente completa ya que puede implementar AND, OR y NOT: NAND(A,B) = AB NAND(A,A) = A NAND(A, B) = A+B
2: Funciones booleanas 40
Conjuntos funcionalmente Completos
La función NOR también es funcionalmente completa ya que puede implementar AND, OR y NOT: NOR(A, B) = A + B NOR(A,A) = A NOR(A, B) = AB
Todas estas funciones se pueden generalizar a funciones de n variables.
2: Funciones booleanas 41
Actividad: Determine la función de álgebra booleana
para un sumador de un bit. Inputs: A, B, Carry-in Outputs: Sum, Carry-out
A
B
CinCout
S
A A A A AB B B B B
S S S S S
CinCout
2: Funciones booleanas 42
Actividad:
Determine la tabla de verdad y la función de álgebra booleana para un sumador de un bit
Inputs: A, B, Carry-in Outputs: Sum, Carry-out
Cómo minimizar usando álgebra booleana?
A
B
CinCout
S
A A A A AB B B B B
S S S S S
CinCout
A B Cin Cout S0 0 0 0 0 1 0 1 0 0 1 11 0 0 1 0 1 1 1 0 1 1 1
01101001
00010111
Cout = A’ B Cin + A B’ Cin + A B Cin’ + A B Cin
S = A’ B’ Cin + A’ B Cin’ + A B’ Cin’ + A B Cin
2: Funciones booleanas 43
Minimizar Usando teoremas para minimizar el sumador
Cuales son los criterios de interés al minimizar?
Cout = A’ B Cin + A B’ Cin + A B Cin’ + A B Cin= A’ B Cin + A B’ Cin + A B Cin’ + A B Cin + A B Cin= A’ B Cin + A B Cin + A B’ Cin + A B Cin’ + A B Cin= (A’ + A) B Cin + A B’ Cin + A B Cin’ + A B Cin= (1) B Cin + A B’ Cin + A B Cin’ + A B Cin= B Cin + A B’ Cin + A B Cin’ + A B Cin + A B Cin= B Cin + A B’ Cin + A B Cin + A B Cin’ + A B Cin= B Cin + A (B’ + B) Cin + A B Cin’ + A B Cin= B Cin + A (1) Cin + A B Cin’ + A B Cin= B Cin + A Cin + A B (Cin’ + Cin)= B Cin + A Cin + A B (1)= B Cin + A Cin + A B sumar terminos
para factorizar
2: Funciones booleanas 44
Minimizar Algunos criterios de interés al minimizar son:
Criterios de reducción• Minimizar compuertas• Minimizar número de entradas a las compuertas. Esto
corresponde a minimizar el numero de literales y reduce el número de transistores en cada compuerta (reduce el costo).
• Disminuir el número de niveles, esto aumenta la velocidad de respuesta del circuito implementando la función.
Siempre van a existir compromisos entre velocidad y tamaño. Se suele denominar compromiso tiempo-espacio.
Diferentes implementaciones de la misma función tienen diferentes comportamientos: Retardos son diferentes. Perturbaciones (glitches) pueden ocurrir. Otras variaciones por diferencias en el número de compuertas y
estructura.
2: Funciones booleanas 45
A B C Z0 0 0 00 0 1 10 1 0 00 1 1 11 0 0 01 0 1 11 1 0 11 1 1 0
Hay que elegir entre diferentes realizaciones de una función
realización de dos niveles
compuerta XOR (fácil de dibujar pero mas costosa)
implementación multinivelcompuertas con menos inputs
2: Funciones booleanas 46
Hay que elegir entre diferentes realizaciones de una función
Las tres implementaciones anteriores son funcionalmente equivalentes pero tienen diferencias en su comportamiento