Download algebra booleana

Álgebra Booleana y
Simplificación Lógica
M. en C. Erika Vilches
Parte 1
Operaciones Booleanas
y Expresiones
• Variable, complemento y literal son los
términos utilizados en álgebra booleana.
• Variable → símbolo utilizado para
representar una cantidad lógica
• Complemento → el inverso de una variable
y se indica con una barra sobre la variable
• Literal → una variable o el complemento de
una variable
Suma Booleana: Equivalente a la operación OR
Multiplicación Booleana: Equivalente a la operacion AND
Leyes del Algebra Booleana
Leyes conmutativas
Para la suma de dos variables se escribe:
A+B=B+A
El orden en que se OReen las variables no hace diferencia.
Para la multiplicación de dos variables se escribe:
AB = BA
El orden en que se ANDeen las variables no hace diferencia
Leyes asociativas
Para la suma de tres variables se escribe:
A + (B + C) = (A + B) + C
Cuando se ORean más de dos variables, el resultado es el
mismo sin importar la agrupación
Para la multiplicación de tres variables se escribe:
A(BC) = (AB)C
Cuando se ANDean dos o más variables, no importa el
orden en que se agrupen las variables
Ley Distributiva
Se escribe para tres variables como:
A(B + C) = AB + AC
ORear dos o más variables y ANDear posteriormente
el resultado con una sola variable es equivalente a
ANDear la variable sola con cada una de las dos o más
variables y despues ORear los productos
El proceso inverso (factorización) también es
expresado por esta ley. Una variable común se
factoriza de los términos.
Reglas del Algebra
Booleana
Reglas útiles para manipular y simplificar
expresiones Booleanas.
Regla 1. A + 0 = A. Una variable OReada con 0 es
siempre igual a la variable.
Regla 2. A + 1 = 1. Una variable OReada con 1 es
siempre igual a 1.
Regla 3. A ⋅ 0 = 0. Una variable ANDeada con 0 es
siempre igual a 0.
Regla 4. A ⋅ 1 = A. Una variable ANDeada con 1 es
siempre igual a la variable.
Regla 5. A + A = A. Una variable OReada con sigo misma
es siempre igual a la variable.
Regla 6.
. Una variable OReada con su
complemento es siempre igual a 1.
Regla 7. A ⋅ A = A. Una variable ANDeada con ella misma
es siempre igual a la variable.
Regla 8.
. Una variable ANDeada con su
complemento es siempre igual a 0.
Regla 9.
. El doble complemento de una variable es
siempre igual a la variable.
Regla 10. A + AB = A. Esta regla se puede probar
aplicando la ley distributiva, la regla 2 y la regla 4.
A + AB = A(1 + B)
= A⋅1
=A
Factorización (ley distributiva)
Regla 2: (1 + B) = 1
Regla 4: A⋅1 = A
Regla 11.
sigue:
. Esta regla se puede probar como
Regla 12. (A + B)(A + C) = A + BC. Esta regla se puede
probar como sigue:
Teoremas de DeMorgan
Primer Teorema de DeMorgan
• El complemento de un producto de variables
es igual a la suma de los complementos de
las variables
• En otras palabras: El complemento de dos o
más variables ANDeadas es equivalente al
OR de los complementos de las variables
individuales
Segundo Teorema de DeMorgan
• El complemento de la suma de variables es
igual al producto de los complementos de
las variables.
• En otras palabras: El complemento de dos o
más variables OReadas es equivalente al
AND de los complementos de las variables
individuales
Para el primer teorema de DeMorgan →
Para el segundo teorema de DeMorgan →
Los teoremas de DeMorgan pueden ser aplicados a
expresiones con más de dos variables.
Ejemplos:
Tres variables →
Cuatro variables →
Cada variable en los teoremas de DeMorgan puede
representar una combinación de otras variables.
Ejemplo:
Si aplicamos
obtenemos →
a la expresión →
Si a los 2 términos del resultado anterior
y
les aplicamos individualmente el teorema
nos queda →
Si volvemos a aplicar el teorema de DeMorgan a
nos queda →
ya
El resultado se podría simplificar más con las reglas y leyes
Booleanas, pero ya no más con con los teoremas de DeMorgan
Aplicación de los teoremas de DeMorgan y algebra
Booleana a la expresión →
1. Identificar los términos a los que se les puede aplicar
los teoremas de DeMorgan y pensar en ellos como si
fuesen 1 sola variable. Tomemos
y
.
2. Dado que
,
3. Utilizar la regla 9
para cancelar las barras dobles
sobre el término de la izquierda (esto no es parte de
los teoremas de DeMorgan) →
4. Aplicar el teorema de DeMorgan
término →
5. Utilizar la regla 9
sobre
→
al segundo
para cancelar las barras dobles
Ejemplo: Aplique los teoremas de DeMorgan
a la siguiente expresión →
Tomemos
y
. La expresión
se encuentra en la forma
y se puede
reescribir como →
Ahora, aplicar el teorema de DeMorgan
término
→
al
Ejemplo: Aplique los teoremas de DeMorgan
a la siguiente expresión →
Tomemos
y
. La expresión
se encuentra en la forma
y se puede
reescribir como →
Ahora, aplicar el teorema de DeMorgan
los términos
y
→
a
Ejemplo: Aplique los teoremas de DeMorgan
a la siguiente expresión →
Tomemos
,
y
. La expresión
se encuentra en la forma
y se puede
reescribir como →
Ahora, aplicar el teorema de DeMorgan
los términos , y →
a