Álgebra Booleana

Antonio Piedra
Agradecimiento a los profesores Ignacio Díaz, Kryscia Ramírez y Roxana
Vargas por el material compartido
 Algebra booleana

• Los circuitos en las computadoras y otros dispositivos electrónicos

tienen como entrada valores que son 0 o 1.
• Dichos circuitos siguen las reglas de la lógica propuestas por George
Boole
• El álgebra booleana es un conjunto de reglas matemáticas que
corresponden al comportamiento de los circuitos.
 Definición

• El algebra booleana trabaja sobre un conjunto B con dos o más elementos y dos
tipos de operaciones: la suma (+) u operación OR, el producto (*) u operación AND.
• Las operaciones siguen las siguientes reglas:
• Conmutatividad
• Distributividad
• Existencia de Neutros o Leyes de Identidad
• Existencia de Complementos
 Definición

• Sea B un conjunto donde se definieron dos operaciones binarias: + y * y una

operación unitaria ‘, sean 1 y 0 dos elementos distintos de B. Entonces la
sextupla <B,+,*,’,0,1> se le llama álgebra de Boole si se cumplen las cuatro
reglas indicadas anteriormente.
• Al elemento 0 se le llama elemento cero
• Al elemento 1 se le llama elemento unidad
• A la 0peración unitaria se le llama complemento
 Definición

• Conmutatividad:
• ∀ 𝑥, 𝑦 ∈ 𝐵, 𝑥 + 𝑦 = 𝑦 + 𝑥
• ∀ 𝑥, 𝑦 ∈ 𝐵, 𝑥 ∗ 𝑦 = 𝑦 ∗ 𝑥
• Distributividad:
• ∀ 𝑥, 𝑦, 𝑧 ∈ 𝐵, 𝑥 + 𝑦 ∗ 𝑧 = 𝑥 + 𝑦 ∗ (𝑥 + 𝑧)
• ∀ 𝑥, 𝑦 ∈ 𝐵, 𝑥 ∗ 𝑦 + 𝑧 = 𝑥 ∗ 𝑦 + (𝑥 ∗ 𝑧)
 Definición

• Existencia de Neutros o Ley de Identidad:

• ∀ 𝑥 ∈ 𝐵, 𝑥 + 0 = 0 + 𝑥 = 𝑥
• ∀ 𝑥 ∈ 𝐵, 𝑥 ∗ 1 = 1 ∗ 𝑥 = 𝑥
• Existencia de Complemento:
• ∀ 𝑥 ∈ 𝐵, ∃𝑥 ′ | 𝑥 + 𝑥 ′ = 1, 𝑥 ∗ 𝑥 ′ = 0
• También se representa como 𝑥ҧ
 Ejemplos

• B = {0, 1} y las operaciones + y * se definen de la siguiente forma:

+ 1 0 * 1 0
1 1 1 1 1 0
0 1 0 0 0 0

• Los complementos están definidos por 1’ = 0 y 0’ = 1

 Ejemplos
Sea Z una colección de conjuntos cerrados bajo uniones, intersecciones y complementos.

Se tiene como elemento cero al conjunto vacío ∅ y como elemento unidad al conjunto

universal U: < 𝑍, ∪, ∩, ′, ∅, 𝑈 >

• Identidad: El neutro de ∪ es el conjunto vacío ∅. El neutro de ∩ es el universo U. Para

cualquier conjunto arbitrario A:

• A∪∅=AyA∩U=A

• Conmutatividad: Para cualquieras conjuntos A y B:

• A ∪ B = B ∪ A yA ∩ B= B ∩ A
8
 Ejemplos

Tenemos < 𝑍, ∪, ∩, ′, ∅, 𝑈 >

• Distributividad: La unión de conjuntos es distributiva sobre la intersección y la intersección de

conjuntos es distributivas sobre la unión. Para cualquieras conjuntos A, B y C:

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) y A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

• Complementos: El conjunto complemento A’ cumple con las propiedades: A ∪ A’ = U y A ∩ A’ =

9
 Dualidad
• La expresión dual (o simplemente el dual) de cualquier enunciado en un
álgebra de Boole B es el enunciado obtenido al intercambiar las operaciones
suma y producto + y *, e intercambiar los elementos identidad 0 y 1, en el
enunciado original.
• Ejemplos:
• a + b = 1 es dual de a*b = 0
• (1 + a) * (b + 0) = b es dual de (0 * a) + (b * 1) = b
• Principio de dualidad: Si una expresión booleana es verdadera entonces su
expresión dual lo es también.
 Dualidad
• Si revisamos las leyes o teoremas necesarias para que un álgebra sea
booleana, vemos que las expresiones a) y b) son siempre duales:

Conmutatividad: ∀ 𝑥, 𝑦 ∈ 𝐵 Identidad:

a) 𝑥 + 𝑦 = 𝑦 + 𝑥 a) ∃ 0 ∈ 𝐵 | ∀ 𝑥 ∈ 𝐵 𝑥 + 0 = 0 + 𝑥 = 𝑥

b) 𝑥 ∗ 𝑦 = 𝑦 ∗ 𝑥 b) ∃ 1 ∈ 𝐵 | ∀ 𝑥 ∈ 𝐵 𝑥 ∗ 1 = 1 ∗ 𝑥 = 𝑥

Distributividad: ∀ 𝑥, 𝑦, 𝑧 ∈ 𝐵 Complementos:

a) 𝑥 + 𝑦 ∗ 𝑧 = 𝑥 + 𝑦 ∗ (𝑥 + 𝑧) ∀ 𝑥 ∈ 𝐵, ∃ 𝑥′ ∈ 𝐵 |
b) 𝑥 ∗ 𝑦 + 𝑧 = 𝑥 ∗ 𝑦 + (𝑥 ∗ 𝑧) a) 𝑥 + 𝑥′ = 1
b) 𝑥 ∗ 𝑥′ = 0
 Teoremas y leyes

• Leyes de idempotencia: • Leyes de acotamiento:

• x+x=x • x+1=1
• x*x=x • x*0=0

• Leyes de absorción: • Leyes asociativas:

• x + (x * y) = x • x + (y + z) = (x + y) + z
• x * (x + y) = x • x * (y * z) = (x * y) * z
 Teoremas y leyes

• Unicidad del complemento: • Leyes de Morgan:

• Si x + a = 1 y x * a = 0 entonces a = x’
• (x + y)’ = x’ * y’ 𝑥 + 𝑦 = 𝑥ҧ ∗ 𝑦ത
• Ley de involución:
• x’’ = x • (x * y)’ = x’ + y’ 𝑥 ∗ 𝑦 = 𝑥ҧ + 𝑦ത

• Complementos: • Consenso:
• 0’ = 1 • (x * y) + (x’ * z) + (y * z) = (x * y) + (x’ * z)

• (x + y) * (x’ + z) * (y + z) = (x + y) * (x’ + z)
 Orden
• Una relación ≾ en un conjunto S se llama un orden parcial
en S si cumple las tres propiedades siguientes:

• a ≾ a, a  S.
• Si a ≾ b y b ≾ a, entonces a = b.
• Si a ≾ b y b ≾ c, entonces a ≾ c.
14
 Orden
• Un conjunto S junto con un orden parcial se llama conjunto
parcialmente ordenado. En tal caso se puede escribir y leer:
• a ≾ b  a precede a b.
• a ≺ b  a precede estrictamente a b, si a ≾ b pero a ≠ b.
• a ≿ b  a sigue a b, si b ≾ a.
• a ≻ b  a sigue estrictamente a b, si b ≺ a.
15
 Orden

• El término parcial se usa al definir un conjunto parcialmente ordenado S,

porque puede haber elementos a y b de S que no son comparables, o sea, tales
que ni a ≾ b ni b ≾ a.

• Si por otra parte, todo par de elementos de S es comparable, entonces se dice

que S es totalmente ordenado, o linealmente ordenado.

16
 Orden – Ejemplos:
• Sea Z una clase cualquiera de conjuntos, la relación de inclusión  es un
orden parcial de Z.

• En los números enteros positivos, se dice que “a divide a b”, escrito a | b, si

existe un entero c tal que ac = b; esta relación de divisibilidad es un orden
parcial en N. Notar que, por ejemplo, 3 y 5 no son comparables ya que
ninguno divide al otro.

• La relación ≤ también es un orden parcial de los enteros positivos N. Notar

que N es totalmente ordenado por medio de esta relación.
17
 Orden

• Sea B un álgebra de Boole; B es entonces parcialmente ordenado, siendo a ≾ b si y sólo si:

•a+b=b
•a*b=a
• a' + b = 1
• a * b’ = 0
Estas cuatro condiciones son equivalentes y el cumplimiento de 1 supone el cumplimiento
de las otras.
• Sea B un álgebra de Boole, B parcialmente ordenado, entonces:
∀ a de B, 0 ≾ a ≾ 1.
• Usando a + b = b vemos que 0 + a = a y a + 1 = 1.
18
 Expresiones booleanas
• Considere un conjunto de variables x1, x2, …, xn todas pertenecientes a un conjunto
sobre el cual tenemos un álgebra booleana.

• Una expresión booleana E sobre estas variables, a veces escrito E(x1, x2, …, xn) es
una variable o una expresión construida con estas variables (no necesariamente
todas) que usan las operaciones booleanas de suma (+), producto (*) y
complemento (‘).
• Ejemplo:
• E(x,y,z) = (x + y’ * z)’ + (x * y * z’ + x’y)
• Dos expresiones son equivalentes si tienen el mismo valor para todos los valores
posibles de sus variables
 Definiciones
• Literal: es una variable o una variable complementada
• Producto fundamental: literal o un producto de dos o más literales en los
cuales no hay dos literales con una misma variable.
• xz’, xy’z, x, y’ son productos fundamentales
• xyx’z, xyzy no son productos fundamentales
• Todo producto se puede reducir a 0 o a un producto fundamental
 Producto fundamental
• Un producto fundamental P1, se dice que está incluido o contenido en otro
producto fundamental P2, si los literales de P1 también son literales de P2.
Ejemplos:
• x’ z está incluido en x’ y z

• x’ z no está incluido en x y’ z ya que x’ no es un literal de x y’ z

• En caso de que P1 esté incluido en P2, entonces por la ley de absorción

𝑃1 + 𝑃2 = 𝑃1.
• Ejemplo: x' z + x’ y z = x’ z dado que x’ z ( 1 + y ) = x' z
 Minterm
• Una expresión de Boole E se dice que está en forma de suma de productos o
en forma minitérmino (minterm) si:
• E es un producto fundamental
• E es la suma de dos o más productos fundamentales, ninguno de los cuales está
incluido en otro.

Ejemplos:
• E1 = x’z + xy’z + x’yz (E1 no está en forma de suma de productos, ya que el primero está
contenido en el tercero)
• E2 = xz’ + x’yz’ + xy’z (E2 está en forma de suma de productos)
 Minterm
• A partir de una tabla de verdad (contiene todos los
valores posibles de una función lógica a partir del
valor de sus variables), se puede construir o
encontrar la expresión booleana que representa
esa función.
• Por ejemplo, las funciones F(x,y,z) y G(x,y,z):
• F toma el valor de 1 cuando x = 1, y = 0, z = 1, y 0 en
cualquier otro caso, que se representa con: x y’ z.
• G toma el valor de 1 cuando
• x = 1, y = 1, z = 0
• x = 0, y = 1, z = 0
• Lo que se representa con: x y z’ + x’ y z’
 Maxterm
• También es posible expresar una función lógica
como producto de sumas (o Maxterm).
• Por ejemplo, la función H(x,y,z) representada en la
tabla:
• H toma el valor 0 cuando:
• x = 1, y = 1, z = 0
• x = 1, y = 0, z = 0
• x = 0, y = 0, z = 1
• x = 0, y = 0, z = 0
• Entonces H se representa con:
• (x’ + y’ + z) (x’ + y + z) (x + y + z') (x + y + z)
 Minterm: algoritmo
• Toda expresión de Boole no nula E se puede expresar en forma de
suma de productos con el siguiente procedimiento:
• Usar las leyes de De Morgan y de Involución.
• Movemos el complemento dentro de cualquier paréntesis hasta que se aplique
solamente a variables. E consistirá entonces solamente en sumas y productos de
literales.

• Usar la ley distributiva

• Transformamos E en una “suma de productos” (no en el sentido de minterm).

• Usar las leyes conmutativas, de idempotencia y de complemento,

• Transformamos cada producto de E en 0 o en un producto fundamental.

• Usar la ley de absorción

• Ponemos E en forma de suma de productos.

 Ejemplo
• Ejemplo: 𝐸(𝑎, 𝑏, 𝑐) = ((𝑎𝑏)’𝑐)’ ((𝑎’ + 𝑐)(𝑏’ + 𝑐’))’
1. De Morgan / Involución 2. Distributiva
• ((𝑎𝑏)’𝑐)’ ((𝑎’ + 𝑐)(𝑏’ + 𝑐’))’ = • (𝑎𝑏𝑎𝑐’) + (𝑎𝑏𝑏𝑐) + (𝑐’𝑎𝑐’) + (𝑐’𝑏𝑐)
• ((𝑎𝑏)’’ + 𝑐’) ((𝑎’ + 𝑐)’ + (𝑏’ + 𝑐’)’) = 3. Conmutativa, Idempotencia, Complemento
• (𝑎𝑏 + 𝑐’) ((𝑎’’𝑐’) + (𝑏’’𝑐’’)) = • 𝑎𝑏𝑐’ + 𝑎𝑏𝑐 + 𝑎𝑐’ + 0
• (𝑎𝑏 + 𝑐’) (𝑎𝑐’ + 𝑏𝑐)
4. Absorción
• 𝑎𝑏𝑐 + 𝑎𝑐’
 Expresiones booleanas completas
• Una expresión de Boole no nula E(x1, x2, …, xn) se dice que está en forma
completa de suma de productos si E está en forma de suma de productos, y
en cada producto se usan todas las variables.

• Ejemplo: 𝐸(𝑥, 𝑦, 𝑧) = 𝑥𝑦𝑧 + 𝑥𝑦’𝑧 + 𝑥’𝑦’𝑧 + 𝑥𝑦𝑧’

• Teorema: Cualquier expresión de Boole E que sea una suma de productos se

puede escribir en forma completa de suma de productos y esa
representación es única.
27
 Expresiones booleanas completas
• Si un producto fundamental P de E no usa xi , entonces se puede multiplicar P
por xi + xi’ , dado que xi + xi’ = 1.
• Se repite el proceso para cada xi hasta que todos los productos usen todas
las variables.
• Ejemplo:
𝐸 𝑎, 𝑏, 𝑐 = 𝑎𝑐’ + 𝑎𝑏𝑐
= 𝑎𝑐’(𝑏 + 𝑏’) + 𝑎𝑏𝑐
= 𝑎𝑐’𝑏 + 𝑎𝑐’𝑏’ + 𝑎𝑏𝑐
= 𝑎𝑏𝑐 + 𝑎𝑏𝑐’ + 𝑎𝑏’𝑐’
28
Circuitos Lógicos
Compuertas lógicas
𝐴ഥ
𝐴′
¬𝐴

𝐴∙𝐵
𝐴𝐵
𝐴∗𝐵

𝐴+𝐵

30
Compuertas lógicas
𝐴∙𝐵
(𝐴𝐵)′
(𝐴 ∗ 𝐵)′

𝐴+𝐵
(𝐴 + 𝐵)′

31
Compuertas lógicas

𝐴⊕𝐵

𝐴′ 𝐵 + 𝐴𝐵′

𝐴⊕𝐵

𝐴′ 𝐵′ + 𝐴𝐵

32
 Circuitos lógicos

• Se pueden visualizar como máquinas que contienen uno o más dispositivos de

entrada y exactamente un dispositivo de salida.

• En cada instante cada dispositivo de entrada tiene exactamente un bit de

información (0 ó 1); estos datos son procesados por el circuito para dar un bit de
salida en el dispositivo de salida.

• Se les puede asignar sucesiones de bits de entrada que son procesadas por el
circuito bit por bit, para producir una sucesión con el mismo número de bits.
33
 Circuitos lógicos

• Un bit se puede interpretar como un voltaje a través de un dispositivo de

entrada/salida; aun más, una sucesión de bits es una sucesión de voltajes que
pueden subir o bajar (encendido o apagado).

• Se puede suponer que el circuito siempre procesa la sucesión de izquierda a

derecha o de derecha a izquierda. Si no se dice se adopta la primera convención.

34
 Circuitos lógicos

• Las tablas de verdad para las compuertas lógicas AND, OR y NOT son
idénticas a las correspondientes operadores +, *, ‘ de las expresiones
booleanas.

• Entonces, las compuertas lógicas, junto con 0 y 1 forman un álgebra de

Boole.

35
 Circuitos lógicos

• Los circuitos lógicos pueden escribirse mediante varios patrones. Uno de ellos
corresponde a una expresión de Boole de suma de productos.
• Un circuito AND-OR tiene varias entradas, con algunas de las entradas o sus
complementos alimentando cada compuerta AND.
• Las salidas de todas las compuertas AND alimentan una sola compuerta OR, la cual da la
salida para el circuito.
• En casos extremos, puede haber una sola compuerta AND sin una compuerta OR, o
ninguna compuerta AND y una sola compuerta OR.
36
 Circuitos lógicos
• Ejemplo:

37
 Circuitos lógicos

• Dado cualquier circuito lógico L, se quiere averiguar el efecto en L de cualquier

entrada arbitraria; usualmente esto se especifica por medio de una tabla de verdad.

• La tabla de verdad de L se obtiene escribiendo primero L como una expresión de

Boole L(A,B,C,…), y calculando entonces la tabla de verdad paso por paso.

• La expresión de Boole se obtiene del circuito, siguiendo las entradas a través de

todas las compuertas.

38
 Circuitos lógicos

AND AND AND OR

39
 Circuitos lógicos
• Como los circuitos lógicos forman un álgebra de Boole,
se puede usar los teoremas (axiomas y propiedades) del
álgebra para simplificar los circuitos.
• Y = ABC + AB’C + A’B
= AC(B + B’) + A’B
= AC (1) + A’B
= AC + A’B

40
 Circuitos lógicos
• Así un circuito puede ser reemplazado por otro más sencillo que
se puede formar de la expresión de Boole resultante.

Ambos circuitos lógicos son equivalentes, es decir, tienen la

41

misma tabla de verdad.

 Circuitos lógicos

• La tabla de verdad (única) de una expresión de Boole equivale a la única

forma completa de suma de productos que se puede obtener de una
expresión de Boole.

• De la tabla de verdad se puede obtener, por inspección, la forma completa

de suma de productos y viceversa.

42
 Circuitos lógicos
• Por ejemplo:

• Y = AC + A’B
= AC(B + B’) + A’B(C + C’)
= ABC + AB’C + A’BC + A’BC’

• Que es la tabla de verdad que se

obtuvo del circuito original.
43