2.1 lógica y álgebra de boole 2.2 funciones booleanas...

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.


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.


Á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 { ‘ }.


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?)


Á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


Á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.


Á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.


Á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


Á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)



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 +



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



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


Á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


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.1 Lógica y álgebra de Boole.2.2 Funciones booleanas. 2.3 Representaciones de funciones

booleanas.2.4 Funciones de varias variables.


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.


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.


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.


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.1 Lógica y álgebra de Boole2.2 Funciones booleanas 2.3 Representaciones de funciones

booleanas2.4 Funciones de varias variables


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!


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.


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.


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


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.


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


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


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?


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).



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.



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.



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.



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


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.1 Lógica y álgebra de Boole2.2 Funciones booleanas 2.3 Representaciones de funciones

booleanas2.4 Funciones de varias variables


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


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)’


Conjuntos funcionalmente Completos

Cualquier expresión booleana puede ser escrita mediante los operadores AND, OR y NOT.

Estos conjuntos constituyen un conjunto funcionalmente completo.



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



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.


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


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


Minimizar Usando teoremas para minimizar el sumador

Cuáles 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


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.


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 más costosa)

implementación multinivelcompuertas con menos inputs


Hay que elegir entre diferentes realizaciones de una función

Las tres implementaciones anteriores son funcionalmente equivalentes pero tienen diferencias en su comportamiento

2.1 lógica y álgebra de boole 2.2 funciones booleanas...

Documents