Download algebra de bool

Álgebra Booleana y
Simplificación Lógica
M. en C. Erika Vilches
Parte 2
Simplificación utilizando
Álgebra Booleana
Simplificar la expresión → AB + A(B + C) + B(B + C)
1. Aplicar la ley distributiva al segundo y tercer términos
en la expresión → AB + AB + AC + BB + BC
2. Aplicar la regla 7 (BB = B) al cuarto término →
AB + AB + AC + B + BC
3. Aplicar la regla 5 (AB + AB = AB) a los primeros 2
términos → AB + AC + B + BC
4. Aplicar la regla 10 (B + BC = B) a los últimos dos
términos → AB + AC + B
5. Aplicar la regla 10 (AB + B = B) al primer y tercer
términos → B + AC
•
•
•
En este punto la expresión esta lo más
simplificada posible
Este camino no es necesariamente el único
Una vez que se ha ganado experiencia, se
pueden combinar muchos pasos individuales
Simplificar la expresión Booleana →
1. Aplicar la ley distributiva a los términos entre
brackets →
2. Aplicar la regla 8
paréntesis →
al segundo término entre
3. Aplicar la regla 3 (A⋅0⋅D = 0) al segundo término
entre paréntesis →
4. Aplicar la regla 1 (eliminar el 0) entre los paréntesis
→
5. Aplicar la ley distributiva →
6. Aplicar la regla 7 (CC = C) al primer término →
7. Factorizar
→
8. Aplicar la regla 6
→
9. Aplicar la regla 4 (eliminar el 1) →
Ejercicios
• Simplificar las siguientes expresiones
Booleanas:
•
Implemente cada expresión en la columna de la
derecha tal cual se muestra con las compuertas
lógicas apropiadas. Posteriormente implemente la
expresión simplificada y compare el número de
compuertas.
Formas Estándar de las
Expresiones Booleanas
Suma de Productos (SOP)
• Un término producto, también llamado
minitérmino, es un término que consiste del
producto (multiplicación Booleana) de
literales (variables o sus complementos).
• Cuando dos o más términos producto se
suman en una suma Booleana, la expresion
resultante es una suma de productos.
• Suma de Productos (SOP, del inglés sum-ofproducts) → AB + ABC
• Una expresión SOP puede tener un término
con una sola variable → A + ABC
• En una expresión SOP, una sola barra no se
puede extender a más de una variable, sin
embargo más de una variable en un término
puede tener una barra. Se puede tener el
término
pero no .
• El dominio de una expresión Booleana es el
conjunto de variables contenidas en la
expresión complementadas o sin
complementar. El dominio de la expresión
es A, B, C, D, E.
• Implementar una expresión SOP requiere
simplemente ORear los productos de 2 o
más compuertas AND.
• Un término producto es producido por una
operación AND, y la suma de dos o más
términos producto se produce con una
operación OR.
Implementación de la expresión SOP
AB + BCD + AC
Conversión de una expresión general a la
forma SOP
• Cualquier expresión lógica se puede cambiar
a la forma SOP aplicando las técnicas de
Álgebra Booleana.
• Ejemplo: A(B + CD) puede ser cambiado a
la forma SOP aplicando la ley distributiva →
A(B + CD) = AB + ACD
• Ejercicio: Convierta las siguientes
expresiones Booleanas a la forma SOP:
Forma SOP Estándar
• Una expresión SOP estándar es aquella en
donde todas las variables en el dominio
aparecen en cada término producto en la
expresión. Por ejemplo:
• Las expresiones SOP estándar son
importantes en la construcción de tablas de
verdad y en el método de simplificación
mapas de Karnaugh.
• Cualquier SOP no estándar (referido
solamente como SOP) se puede convertir a
la forma estándar utilizando álgebra
Booleana
Convirtiendo Términos Producto a SOP
Estándar
• Regla 6 →
Cualquier cosa se puede multiplicar por 1
sin cambiar su valor.
1. Multiplicar cada término producto no
estándar por un término hecho con la suma
de una variable faltante y su complemento.
Esto resulta en dos términos producto.
2. Repetir el paso 1 hasta que todos los
términos producto resultantes contengan
todas las variables en el dominio en forma
complementada o sin complementar
Ejemplo: Convertir la expresión
SOP estándar.
a la forma
Dominio → A, B, C, D. Tomar un término a la vez. Al
primer término
le falta ya variable o . Entonces
multiplicar el primer término por
como sigue:
En el segundo término,
faltan las variables o y
o , entonces primero multiplicar el segundo término
por
como sigue:
A ambos términos resultantes les falta la variable
Multiplicar ambos términos por
como sigue:
o .
El tercer término
estándar.
ya se encuentra en forma
La forma SOP estándar completa de la expresión original
es como sigue:
Una expresión SOP (estándar o no) es igual a 1 solo
cuando uno o más de los términos producto en la
expresión es igual a 1.
Ejercicio: Convierta la expresión
a la forma SOP estándar.
Producto de Sumas (POS)
Un término suma, también llamado
maxitérmino, consiste de la suma Booleana
de literales (variables o sus complementos).
•
• Cuando dos o más términos suma son
multiplicados, la expresión resultante es un
producto de sumas.
• Producto de sumas (POS, del inglés productof-sums) →
• Puede contener un término con una sola
variable →
• Una expresión POS (estándar o no) es igual
a 0 solo cuando uno o más de los términos
suma en la expresión es igual a 0.
• En una expresión POS, una barra no se
puede extender sobre mas de una variable,
sin embargo mñas de una variable en un
término puede tener una barra. Se puede
tener el término
pero no
.
• Implementar una expresión POS requiere
simplemente ANDear las salidas de dos o
mas compuertas OR.
Implementación de la expresión POS
(A + B)(B + C + D)(A + C)
Forma POS Estándar
• Una expresión POS estándar es aquella en la
que todas las variables en el dominio
aparecen en cada término suma en la
expresión. Ejemplo:
• Cualquier expresión POS no estándar se
puede convertir a una expresión POS
estándar utilizando Álgebra Booleana.
Convirtiendo Términos Suma a POS Estándar
• Regla 8 →
Se puede sumar 0 a cualquier cosa sin
cambiar su valor.
1. Sumar a cada término suma no estándar un
término hecho con el producto de una
variable faltante y su complemento. Esto
resulta en dos términos suma.
2. Aplicar la regla 12 →
3. Repetir el paso 1 hasta que todos los
términos suma resultantes contengan a
todas las variables del dominio en forma
complementada o sin complementar.
Ejemplo: Convertir la expresión
a la forma POS estándar.
Dominio → A, B, C, D. Tomar un término a la vez. Al
primer término
le falta ya variable o .
Entonces sumar
y aplicar la regla 12 como sigue:
Al segundo término
le falta ya variable o .
Entonces sumar
y aplicar la regla 12 como sigue:
El tercer término
ya se encuentra en forma
POS estándar. La forma POS estándar de la expresión
original es como sigue:
Convirtiendo SOP Estándar a POS Estándar
1. Evaluar cada término producto en la
expresión SOP, de modo que la expresión
sea igual a 1. (Determinar los números
binarios que representan los términos
producto)
2. Determinar todos los números binarios no
incluidos en la evaluación del paso 1.
3. Escribir el término suma equivalente para
cada número binario del paso 2 y expresar
en forma POS (La expresión debe ser igual a
cero).
Convertir la siguiente expresión SOP a su expresión POS
equivalente →
La evaluación para que la expresión sea igual a 1 es
como sigue: 000 + 010 + 101 + 111
Hay 3 variables, por lo tanto hay 2^3 = 8 posibles
combinaciones. La expresión SOP contiene 5 de esas
posibles combinaciones, por lo tanto el POS debe
contener las otras tres, que son 001, 100 y 110.
La expresión POS equivalente (su evaluación es 0) es:
Utilizando un procedimiento similar, se puede ir de
POS a SOP