automatizacion

ELO211: Sistemas Digitales
Tomás Arredondo Vidal
Este material está basado en:
❒ textos y material de apoyo:

Contemporary Logic Design 1st / 2nd edition. Gaetano

Borriello and Randy Katz. Prentice Hall, 1994, 2005
❒ material del curso ELO211 del Prof. Leopoldo Silva
❒ material en el sitio http://es.wikipedia.org

2: Funciones booleanas

1

2-Funciones y representacionesbooleanas
2.1 Lógica y álgebra de Boole
2.2 Funciones booleanas
2.3 Representaciones de funciones booleanas
2.4 Funciones de varias variables

2: Funciones booleanas

2

Lógica Booleana
❒ Definiciones básicas
❍ Una variable booleana (e.g. x, y) es un símbolo que
puede ser substituido por un elemento del
conjunto B={0,1}
❍ Una constante booleana es un valor perteneciente
al conjunto {0,1}❍ Una expresión (e.g. x+y, x·y, x’) esta compuesta de
variables, constantes y operadores (e.g. +, ·, ’)
❍ Una función booleana de n variables f(x1, x2, ..., xn)
es un expresión o formula que mapea f a un valor
del conjunto booleano B (0 o 1)
❍ Un literal es una variable o su complemento
2: Funciones booleanas

3

Álgebra de Boole
❒ Definición: el álgebra de Boole es un

sistemaalgebraico cerrado que contiene:
un conjunto de dos elementos {0, 1},
❍ dos operadores binarios {+, ·},
❍ un operador unitario { ‘ }.
❍

2: Funciones booleanas

4

Lógica y álgebra de Boole
❒ El álgebra de Boole es la fundación matemática de

los sistemas digitales.
❒ Las operaciones del álgebra de Boole deben regirse
por propiedades y reglas lógicas llamados leyes o
postulados.
❒Estos postulados se pueden usar para demostrar
leyes mas generales sobre expresiones booleanas.
❒ Estos postulados también se usan para simplificar
y optimizar expresiones booleanas y sistemas
digitales.
❍ Ejemplo: X AND (Y OR Y’) = X
(¿porque?)

2: Funciones booleanas

5

Álgebra de Boole
❒ Una expresión algebraica de Boole consiste de
❍
❍
❍

un conjunto de B
operacionesbinarias { + , • }
una operaciones unitaria { ’ }

❒ B tiene dos elementos : a, b y los siguientes postulados se cumplen:

Clausura:

a + b esta en B, a • b esta en B

Conmutatividad:

a + b = b + a,

Asociatividad:

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

Identidad:

a + 0 = a,

Distributividad:

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

a + a’ = 1,

a•b=b•a

a•1=a

a • a’ = 0
2: Funciones booleanas

6

Álgebra de Boole: Resumen
❒ Álgebra de Boole

B = {0, 1}
❍ variables
❍ + es el OR lógico, • es el AND lógico
❍ ’ es el NOT lógico
❒ Todos los postulados (axiomas) algebraicos se
cumplen
❒ La prioridad de los operadores es ‘, seguido por
AND y despues OR.
❒ El ‘ tiene la mayor prioridad.
❒Los ( ) pueden cambiar el orden de evaluación.
❍

2: Funciones booleanas

7

Álgebra de Boole: Teoremas
❒ Con la formulación de los postulados del

álgebra de Boole se pueden demostrar varias
proposiciones o teoremas de álgebra booleana
❒ Para las demostraciones de teoremas se
pueden usar:
tablas de verdad,
❍ postulados,
❍ y teoremas ya demostrados
❍

2: Funciones booleanas8

Álgebra de Boole: Teoremas
❒ Definición: El álgebra de boole es un sistema algebraico cerrado

que contiene un conjunto B de dos elementos {0,1} y tres
operadores {·, +, ‘}.
❒ igualdad: Dos expresiones son iguales si una puede ser substituida

por otra.
❒ identidad:

1. X + 0 = X

1D. X • 1 = X

❒ nulo (elementos únicos):

2. X + 1 = 1

2D. X • 0 = 0

❒ idempotencia:3. X + X = X

3D. X • X = X

❒ involución:

4. (X’)’ = X
❒ complementariedad:

5. X + X’ = 1

5D. X • X’ = 0
2: Funciones booleanas

9

Álgebra de Boole: Teoremas
❒
❒
❒
❒
❒

conmutatividad:
6. X + Y = Y + X
asociatividad:
7. (X + Y) + Z = X + (Y + Z)
distributividad:
8. X • (Y + Z) = (X • Y) + (X • Z)
unificación (fusión):
9. X • Y + X • Y’ = X
absorción:
10. X +...