Algebra de Boole y

puertas lógicas

.n
.

1
Índice
Postulados y propiedades fundamentales del Álgebra
de Boole
Funciones y expresiones booleanas
Puertas lógicas. Tecnologías digitales. Implementación
de funciones lógicas.
Minimización de funciones lógicas

2
Álgebra de Boole
Fundamentos matemáticos de los circuitos digitales
Denominada Álgebra de Boole en honor de su
inventor, George Boole “An Investigation of the
Laws of Thought” (1854)
Un álgebra se define por un conjunto de elementos
con unas operaciones. En nuestro caso:
B = {0, 1}
Φ = {+, •}

3
Postulados del Álgebra de Boole
Ley de composición interna
∀ a, b ∈ B ⇒ a + b ∈ B, a • b ∈ B
Elementos neutros
∀ a ∈ B ⇒ ∃ elementos neutros (0 y 1 respectivamente)
a+0=a
a•1=a
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

4
Postulados del Álgebra de Boole
Elemento inverso o complementario
• ∀a∈ B⇒ ∃ a∈ B
a+a=1
a•a=0

5
Propiedades fundamentales del
Álgebra de Boole
Dualidad: Toda ley válida tiene una dual, que se
obtiene cambiando 0 ↔ 1 y + ↔ •
Idempotencia
• ∀a∈ B⇒ a+a=a
a•a=a
• Demostración:
a = a + 0 = a + aa = (a + a)(a + a) = (a + a) •1= a + a

∀ a∈ B⇒ a+1=1
a• 0 = 0

6
 Propiedades fundamentales del
Álgebra de Boole
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

7
Propiedades fundamentales del
Álgebra de Boole
Involución
• ∀a∈ B⇒ a= a

Absorción
• ∀ a, b∈ B ⇒ a + ab = a
a (a+b) = a
• Demostración:
a + ab= a •1 + = a(1 + b) = a •1 = a
ab
Propiedad asociativa
• ∀ a, b, c ∈ B ⇒ (a + b) + c = a + (b + c)
(a • b) • c = a • (b • c)

8
Propiedades fundamentales del
Álgebra de Boole
Leyes de De Morgan:
• ∀ a, b∈ B ⇒
a+b=ab
a •b= a + b

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

9
Funciones y expresiones
booleanas
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:
n
f: B → B
(x1, x2, …, xn) → y

10
 Representación de funciones
lógicas
 Expresión  Tabla de verdad

a b f(a,b)
0 0 0
f(a, b) = a + b 0 1 1
1 0 1
1 1 1
 Obtención de la tabla de verdad a
partir de una expresión
 Basta evaluar la expresión para cada una de
las combinaciones de valores de las entradas
a b c f
0 0 0 0
f(a,b,c) = a + bc
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1
 Función mintérmino
 Expresión: un producto en el que aparecen todas las
variables, negadas o no
 Tabla de verdad: tiene un 1 en una posición y 0 en todas las demás
 Ejemplo: a b c f
f(a,b,c) = = m2 0 0 0 0
abc 0 0 1 0
0 1 0 1
0 1 1 0
 Regla para obtener la expresión:
• 0 → variable negada 1 0 0 0
• 1 → variable sin negar 1 0 1 0
1 1 0 0
1 1 1 0
Función mintérmino
 Función maxtérmino
 Expresión: una suma en la que aparecen todas las variables,
negadas o no
 Tabla de verdad: tiene un 0 en una posición y 1 en todas las demás
 Ejemplo: a b c f
0 0 0 1
f(a,b,c) = (a + b + c) = M2
0 0 1 1
0 1 0 0
 Regla para obtener la expresión: 0 1 1 1
• 0 → variable sin negar 1 0 0 1
• 1 → variable negada
1 0 1 1

CUIDADO: al contrario que los mintérminos! 1 1 0 1

1 1 1 1
Teorema de Expansión de
Shannon
 Toda función booleana se puede descomponer de
las siguientes formas

f(x1,x 2,...,xn ) = xi f(x1,...,xi−1,0,xi+1,...,xn ) + xi f(x1,...,xi−1,1,xi+1,...,xn )

f(x1,x 2,...,xn ) = [xi + f(x1,...,xi−1,1,xi+1,...,xn )][xi +
f(x1,...,xi−1,0,xi+1,...,xn )]

 Demostración
xi = 0 ⇒ f(x1, x 2,..., xn ) =1• f(x1,...,0,..., xn ) + 0 • f(x1,...,1,..., xn ) =
= f(x1,...,0,..., xn )
xi = 1 ⇒ f(x1, x 2,..., xn ) = 0 • f(x1,...,0,..., xn ) + 1• f(x1,...,1,..., xn ) =
= f(x1,...,1,..., xn )

• La otra forma se demuestra por dualidad

Corolario del Teorema de
Expansión de Shannon
 Aplicando recursivamente el Teorema:
f(a,b,c) = a f(0,b,c) + a f(1,b,c) =
= a(b f(0,0,c) + b f(0,1,c)) + a(b f(1,0,c) + b f(0,1,c)) =
= ab f(0,0,c) + ab f(0,1,c)) + ab f(1,0,c) + ab f(0,1,c)
=
= ab c f(0,0,0) + ab c f(0,0,1) + ab c f(0,1,0) + ab c
f(0,1,1) +
+ab c f(1,0,0) + ab c f(1,0,1) + ab c f(1,1,0) + ab c
f(1,1,1) =
= ∑ mik i
3
 Una función es igual a la suma de todos los mintérminos (mi)
afectados por un coeficiente (ki) igual al valor que toma la
16
función al sustituir cada variable por un 0 o un 1 según que en
el mintérmino aparezca la variable negada o sin negar,
respectivamente

17
Primera forma canónica
 Una función se puede expresar como la suma de
los mintérminos para los que la función vale 1
a b c f
f(a,b,c) = ∑ (0,2,5) ∑ m(0,2,5) =
0 0 0 1 = 3
0 0 1 0 3
0 1 0 1 = abc + abc + abc
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 0

18
 Segunda forma canónica
 Una función se puede expresar como el producto
de los maxtérminos para los que la función vale 0
a b c f
f(a,b,c) = ∏ (1,3,4,6,7) ∏ M(1,3,4,6,7)
0 0 0 1
= =
0 0 1 0 3 3
0 1 0 1 = (a + b + c)(a + b + c )(a +
0 1 1 0 b + c)
1 0 0 0 (a + b + c)(a + b + c)
1 0 1 1
1 1 0 0
CUIDADO:1al 1contrario
1 0 que los mintérminos!

19
Puertas lógicas
 Las puertas lógicas son circuitos electrónicos que
realizan las funciones básicas del Álgebra de Boole
 Para cada puerta utilizaremos un símbolo
  Puerta NOT o inversor
Identidad z= a
z=a
a a
a a
0 1
0 0
1 0
1 1

20
Puertas AND y OR
 Puerta Puerta OR
AND z=a+b
z=a•b
a b a+b
a b a•b 0 0 0
0 0 0 0 1 1
0 1 0 1 0 1
1 0 0 1 1 1
1 1 1

21
 Puertas NAND y NOR
 Puerta NAND  Puerta NOR
z = a •b =a+b z= a+ = ab
b
a b a+
0 0 b1
0 1 0
1 0 0
1 1 0

22
a b a•b
0 0 1
0 1 1
1 0 1
1 1 0

66