Circuito

Algebra de Boole y
puertas lógicas
© Luis Entrena, Celia López,
Mario García, Enrique San Millán

Universidad Carlos III de Madrid

1

Índice
l 

Postulados y propiedades fundamentales del
Álgebra de Boole

l 

Funciones y expresiones booleanas

l 

Puertas lógicas. Tecnologías digitales.
Implementación de funciones lógicas

l 

Minimización de funciones lógicas

© Luis Entrena, Celia López,Mario García, Enrique San Millán. Universidad Carlos III de Madrid, 2008

2

Álgebra de Boole
l 

Fundamentos matemáticos de los circuitos digitales

l 

Denominada Álgebra de Boole en honor de su
inventor, George Boole

•  “An Investigation of the Laws of Thought” (1854)

l 

Un álgebra se define por un conjunto de elementos
con unas operaciones. En nuestro caso:

•  B = {0, 1}
•  Φ = {+,•}

© Luis Entrena, Celia López, Mario García, Enrique San Millán. Universidad Carlos III de Madrid, 2008

3

Postulados del Álgebra de Boole
l 

Ley de composición interna

l 

Elementos neutros

•  ∀ a, b ∈ B ⇒ a + b ∈ B, a • b ∈ B
•  ∀ a ∈ B ⇒ ∃ elementos neutros (0 y 1 respectivamente)
a+0=a
a•1=a

l 

l 

Propiedad conmutativa

•  ∀ a, b ∈ B ⇒

a+b=b+a
a•b=b•a

Propiedad distributiva

•  ∀a, b, c ∈ B ⇒

a + b • c = (a + b) • (a + c)
a • (b + c) = a • b + a • c

© Luis Entrena, Celia López, Mario García, Enrique San Millán. Universidad Carlos III de Madrid, 2008

4

Postulados del Álgebra de Boole
l 

Elemento inverso o complementario

•  ∀ a ∈ B ⇒ ∃

a∈B

a+a =1
a•a = 0

© Luis Entrena, Celia López, Mario García, Enrique San Millán. Universidad Carlos III de Madrid, 2008

5Propiedades fundamentales del
Álgebra de Boole
l 

Dualidad: Toda ley válida tiene una dual, que se
obtiene cambiando 0 ↔ 1 y + ↔ •

l 

Idempotencia

•  ∀ a ∈ B ⇒

•  Demostración:

a+a=a
a•a=a

a = a + 0 = a + a a = (a + a)(a + a) = (a + a) • 1 = a + a
l 

∀a∈B⇒

a+1=1
a•0=0

© Luis Entrena, Celia López, Mario García, Enrique San Millán. Universidad Carlos III de Madrid, 2008

6

Propiedadesfundamentales del
Álgebra de Boole
l 

l 

De las propiedades anteriores se pueden definir las
operaciones básicas
a b a+b

a b a•b

a

a

0 0

0

0 0

0

0

1

0 1

1

0 1

0

1

0

1 0

1

1 0

0

1 1

1

1 1

1

Tabla de verdad: proporciona el valor de una función para
todas las posibles combinaciones de valores de las entradas

© Luis Entrena, Celia López, Mario García, Enrique San Millán.Universidad Carlos III de Madrid, 2008

7

Propiedades fundamentales del
Álgebra de Boole
l 

l 

Involución

•  ∀ a ∈ B ⇒

a=a

Absorción

•  ∀ a, b∈ B ⇒
•  Demostración:

a + ab = a
a (a+b) = a

a + ab = a • 1 + ab = a(1 + b) = a • 1 = a
l 

Propiedad asociativa

•  ∀ a, b, c ∈ B ⇒

(a + b) + c = a + (b + c)
(a • b) • c = a • (b • c)

© Luis Entrena, Celia López, Mario García, Enrique SanMillán. Universidad Carlos III de Madrid, 2008

8

Propiedades fundamentales del
Álgebra de Boole
l 

Leyes de De Morgan:

•  ∀ a, b∈ B ⇒

a+b = a b
a•b = a +b

•  Demostración:
(a + b) + a b = (a + b + a)(a + b + b) = 1• 1
(a + b) • a b = (aab) + (bab) = 0 + 0
luego (a+b) es el inverso de a b

© Luis Entrena, Celia López, Mario García, Enrique San Millán. Universidad Carlos III de Madrid, 2008

9Funciones y expresiones
booleanas
l 

Definiciones:

•  Una variable lógica o booleana es cualquier elemento
• 
• 

x ∈ B = {0, 1}
Un literal es una variable negada o sin negar
Función lógica o booleana:
f : Bn → B
(x1, x2, …, xn) → y

© Luis Entrena, Celia López, Mario García, Enrique San Millán. Universidad Carlos III de Madrid, 2008

10

Representación de funciones
lógicas
l 

Expresión

l Tabla de verdad
a b f(a,b)

f(a, b) = a + b

0 0

0

0 1

1

1 0

1

1 1

1

© Luis Entrena, Celia López, Mario García, Enrique San Millán. Universidad Carlos III de Madrid, 2008

11

Obtención de la tabla de verdad a
partir de una expresión
l 

Basta evaluar la expresión para cada una de las
combinaciones de valores de las entradas
a b c f

f (a,b, c ) = a + b c

0 0 0 0
0 0 1 1
0 1 0 0
0...