PDF de programación - Álgebra de Boole. Diseño Lógico

Álgebra de Boole. Diseño Lógico

Fundamentos de Computadores
Escuela Politécnica Superior. UAM

Alguna de las trasparencias utilizadas son traducción de las facilitadas con el libro “Digital Design & Computer Architecture, D.M Harris y S.L. Harris © Elsevier 2007.

Índice de la Unidad 1

U2. Álgebra de Boole y Diseño Lógico.

U1.1. Análogico vs Digital
U1.2. Sistema numérico binario. Conversión entre sistemas.
U1.3. Propiedades y teoremas básicos del álgebra booleana.

U1.3.1. Operaciones y expresiones booleanas.
U1.3.2. Leyes y reglas del álgebra de Boole. Leyes de De Morgan.

U1.4. Funciones lógicas.

U1.4.1. Expresiones booleanas y tabla de la verdad.
U1.4.2. Ampliación a varias entradas.
U1.4.3. Habilitación funcional.
U1.4.4. Implementaciones de puertas SOP y POS.

U1.5. Mapas de Karnaugh.

U1.5.1. Minimización de una suma de productos mediante el mapa K.
U1.5.2. Minimización de un producto de sumas mediante el mapa K.

Analógico vs Digital

Analógico vs Digital
Sistemas analógicos

 Trabajan con variables analógicas
 Señales físicas para representarlas: Señales

analógicas

 Señal analógica: Puede tomar infinitos valores

reales, puesto que varían de forma continua.

 Ejemplo: Termómetro de mercurio

3

Analógico vs Digital

Analógico vs Digital
Sistemas digitales
 Trabajan con variables digitales.

• Toma valores entre dos posibles
• Los valores se expresan por sentencias declarativas
• Los dos valores son excluyentes entre ellos

 Variables físicas para representarlas: Señales

digitales.

 Señal digital: Toma valores discretos.
 Ejemplos: Interruptor de la luz

Bombilla

¿Semáforo?

4

Sistema numérico binario.
Conversión entre sistemas

Sistema numérico posicional

El valor del dígito depende de su posición en el número.

 Sistema Decimal:

l

C
o
u
m
n
a



1
0
0
0
s

’

l

C
o
u
m
n
a



1
0
0
s

’

l

C
o
u
m
n
a



1
0
s

’

l

C
o
u
m
n
a



1
s

’

I

S
S
T
E
M
A

B
A
S
E



5 3 7 4 10

 Sistema binario:

l

C
o
u
m
n
a


8
’
s

l

C
o
u
m
n
a


4
’
s

l

C
o
u
m
n
a


2
’
s

l

C
o
u
m
n
a


1
’
s

1

1 0 1

I

S
S
T
E
M
A

B
A
S
E



2

Equivalente numérico en decimal

Equivalente numérico en decimal

Sistema numérico binario.
Conversión entre sistemas

Ejemplos de conversión entre sistemas
 Convertir de binario a decimal el número 101012

 Convertir de decimal a binario el número 4710

Sistema numérico binario.
Conversión entre sistemas

 210 = 1024 = 1 k

Se recomienda el aprendizaje de las siguientes potencias:
 20 = 1
 21 = 2
 22 = 4
 23 = 8
 24 = 16
Ejemplos:

******************
 220 = 1.048.576 = 1 M
 230 = 1.073.741.824 = 1 G
 232 = 22 * 230 = 4 G

 25 = 32
 26 = 64
 27 = 128
 28 = 256
 29 = 512

¿ 213 = ?

¿ 224 = ?

¿ 215 = ?

Sistema numérico binario.
Conversión entre sistemas

Rango de representación del sistema binario.

 Con un número de n dígitos decimales {0-9}, se representan

10n números diferentes en el rango [0, 10n-1].

 Ejemplo: con n = 3, 103 = 1000 números diferentes.

en el rango [0, 999]

 Con un número de n dígitos binarios {0, 1}, se representan

2n números diferentes en el rango [0, 2n-1].

 Ejemplo: con n = 3, 23 = 8 números diferentes

en el rango [0, 7]

Sistema numérico binario.
Conversión entre sistemas

Sistema Hexadecimal
Dígito
Hexadecimal

Binario
Equivalente

Decimal
Equivalente

Dígito
Hexadecimal

0
1
2
3
4
5
6
7

0
1
2
3
4
5
6
7

0000
0001
0010
0011
0100
0101
0110
0111

8
9
A
B
C
D
E
F

Equivalente
Decimal
8
9
10
11
12
13
14
15

Equivalente
Binario

1000
1001
1010
1011
1100
1101
1110
1111

El hexadecimal es un sistema numérico posicional con
base 16, que se utiliza para escribir de forma abreviada
números en binario.

Sistema numérico binario.
Conversión entre sistemas

Ejemplos de conversión entre sistemas
 Convertir de hexadecimal a binario el número 4AF16;

también (0x4AF)

 Convertir de hexadecimal a decimal el número 0x4AF

Sistema numérico binario.
Conversión entre sistemas

• Bits

• Bytes & Nibbles

• Bytes

1 0 0 1 1 0 1 1
bit mas

significativo

(msb)

bit menos
significativo

(lsb)

Byte = 8 bits

1 0 0 1 1 0 1 1
Nibble = 4 bits

FC A5 C0 8D
byte menos
byte mas
significativo
significativo

(msB)

(lsB)

Operaciones y expresiones booleanas

Álgebra de Boole: es la herramienta matemática
utilizada para el análisis y la síntesis de los
sistemas digitales binarios.

George Boole

Matemático inglés

(1815-1864)

Variable booleana: es una señal digital que en un instante
determinado sólo puede tomar uno de dos valores. Los
valores a tomar son mutuamente excluyentes.

 Se representan como: 0 y 1; OFF y ON; etc…

12

Operaciones y expresiones booleanas

• Variables lógicas y circuitos eléctricos:

A

F

Vcc

•Estado del interruptor A:

•Estado de la bombilla F:

•Abierto (0)
•Cerrado (1)

•Apagada (0)
•Encendida (1)

El estado de la variable lógica bombilla es función del estado de la
variable lógica interruptor

FUNCIÓN: “La bombilla está encendida si el interruptor está
cerrado”

13

Operaciones y expresiones booleanas

• Función lógica: Circuito que acepta valores lógicos a

la entrada y produce un valor lógico a la salida

• Tabla de verdad: describe el funcionamiento de las

funciones lógicas.

 Especifica la salida de la puerta o función
lógica para todas las posibles combinaciones
de entradas

 Son representaciones gráficas de todos los
casos que se pueden dar en una relación
algebraica y de sus respectivos resultados

A B F
0 0 0
0 1 1
1 0 1
1 1 0

• Puertas lógicas: Implementan a las funciones lógicas

más elementales.

14

Operaciones y expresiones booleanas
• EL AMPLIFICADOR (BUFFER)

 Puerta lógica más sencilla
 Una entrada (A) y una salida (Z)
 Tabla de verdad:

A
1
0

Z
1
0



 Ecuación lógica: Z = A

 Representación gráfica:

15

Operaciones y expresiones booleanas
• LA PUERTA NOT O INVERSOR
 Una entrada (A) y una salida (Z)
 Tabla de verdad:
Z
0
1

A
1
0



 Ecuación lógica:

 Representación gráfica:

16

Operaciones y expresiones booleanas
• LA PUERTA NOT O INVERSOR
 Lógica interna de la puerta NOT:

17

Operaciones y expresiones booleanas

0
1
0
1
0
1

0
1
0
1
0
1

1
0
1
0
1
0

1
0
1
0
1
0

Operaciones y expresiones booleanas
• LA PUERTA AND

 La puerta AND vista como interruptores:

A

B

Vcc

F

FUNCIÓN: La bombilla está encendida si:

“el interruptor A Y el interruptor B están cerrados”

19

Operaciones y expresiones booleanas
• LA PUERTA AND (2 entradas {A,B} y 1 salida {Z})

Z=1 sólo si las dos entradas están simultáneamente a 1
Tabla de verdad:

Z
0
0
0
1

B
0
1
0
1
Ecuación lógica: Z = A•B

A
0
0
1
1



Representación gráfica:

¿Puerta AND de varias entradas?

20

Operaciones y expresiones booleanas
• LA PUERTA AND

 Lógica interna de la puerta AND:

21

Operaciones y expresiones booleanas
• LA PUERTA OR

 La puerta OR vista como interruptores:

A

B

Vcc

F

FUNCIÓN: La bombilla está encendida si:

“el interruptor A, O el interruptor B O ambos están cerrados”

22

Operaciones y expresiones booleanas
• LA PUERTA OR: (2 entradas {A,B} y 1 salida {Z})

Z = 1 cuando alguna de las dos entradas vale 1
Tabla de verdad:

A
0
0
1
1

B
0
1
0
1

Z
0
1
1
1


Ecuación lógica: Z = A + B

Representación gráfica:

¿Puerta OR de varias entradas?

23

Operaciones y expresiones booleanas
• LA PUERTA NAND: (2 entradas {A,B} y 1 salida {Z})

Z=1 si al menos una de las dos entradas vale 0
Tabla de verdad:

A
0
0
1
1

B
0
1
0
1

Z
1
1
1
0



Ecuación lógica:

Representación gráfica:

¿Puerta NAND de varias entradas?

24

Operaciones y expresiones booleanas
• LA PUERTA NOR: (2 entradas {A,B} y 1 salida {Z})

Z=0 si al menos una de las dos entradas vale 1
Tabla de verdad:

A
0
0
1
1

B
0
1
0
1

Z
1
0
0
0


Ecuación lógica:

Representación gráfica:

¿Puerta NOR de varias entradas?

25

Operaciones y expresiones booleanas
• LA PUERTA XOR (OR-Exclusiva): (2 entradas {A,B} y 1 salida {Z})

Z=1 si y sólo si una de las entradas está a 1
Tabla de verdad:

Z
0
1
1
0

B
0
1
0
1
Ecuación lógica: Z = A  B

A
0
0
1
1



Representación gráfica:

¿Puerta XOR de varias entradas?

26

Leyes y reglas del álgebra de Boole

Nombre
T1
Identidad
T2
Elemento nulo
T3
Indempotencia
T4
Involución
T5
Complemento
Prop. Conmutativa T6
T7
Prop. Asociativa
T8
Prop. Distributiva
T12 /(B0 ● B1 ●…● Bn-2 ● Bn-1) =

T1’
T2’
T3’
//B = B
T5’
T6’
T7’
T8’
= (/B0 + /B1 +…+ /Bn-2 + /Bn-1) T12’

Ley de De Morgan

Teorema
B ● 1 = B
B ● 0 = 0
B ● B = B

B ● /B = 0
B ● C = C ● B
(B ● C) ● D = B ● (C ● D)
(B ● C) + (B ● D) = B ● (C + D)

Dual
B + 0 = B
B + 1 = 1
B + B = B

B + /B = 1
B + C = C + B
(B + C) + D = B + (C + D)
(B + C) ● (B + D) = B + (C ● D)
/(B0 + B1 +…+ Bn-2 + Bn-1) =

= (/B0 ● /B1 ●…● /Bn-2 ● /Bn-1)

Ecuaciones duales en el Álgebra de Boole

27

Circuitos lógicos

Las combinaciones de diferentes valores lógicos a la
entrada hacen que aparezcan distintos valores lógicos a
la salida => CIRCUITO LÓGICO

Un circuito lógico se compone de:

• Entradas
• Salidas
• Especificación funcional
• Especificación temporal

ENTRADAS

ESPECIFICACIONES:
 FUNCIONAL

TEMPORAL (Retardo)

SALIDAS

Cualquier función lógica puede expresarse como

función de las puertas AND, OR y NOT

Circuitos lógicos

Ejemplo de un circuito lógico:
• Entradas: A, B, C y D
• Salidas: Z1 y Z2
• Especificación funcional

 S = f1 (A, B)
 Z1 = f2 (C, D)
 Z2 = f3 (S, Z1) = (A, B, C, D)

ENTRADAS

A
B
C
D

S

f3

f1
f2

Z2
Z1

SALIDAS

• Especificación temporal: (∆tZ2 = MAX{∆tf1,∆tf2}+∆tf3)

Lógica combinacional: si el estado de las salidas depende sólo
del estado de las entradas. Sistema sin memoria.
Lógica secuencial: si el estado de la salida también depende
del estado anterior del sistema. El circuito tiene memoria.

Funciones lógicas

• Función lógica: Expresión Booleana que relaciona variables
lógicas directas o complementadas por medio de operacion